Lines Matching defs:search
236 /* Auxiliary search trees */
256 * the auxiliar search tree - when we're done searching the bset_float tree we
257 * have this many bytes left that we do a linear search over.
261 * cacheline in the linear search - but the linear search might stop before it
278 /* Space required for the auxiliary search trees */
365 /* Binary tree stuff for auxiliary search trees */
509 * t->tree is a binary search tree in an array; each node corresponds to a key
556 * maintain a full search tree, we just keep a simple lookup table in t->prev.
683 * accelerate bkey search in a btree node (pointed by bset_tree->data in
684 * memory). After search in the auxiliar tree by calling bset_search_tree(),
687 * linear comparison does the exact search, see __bch_bset_search() for how
936 const struct bkey *search)
943 if (bkey_cmp(table_to_bkey(t, m), search) > 0)
956 const struct bkey *search)
972 if (f->mantissa >= bfloat_mantissa(search, f))
977 if (bkey_cmp(tree_to_bkey(t, j), search) > 0)
1012 const struct bkey *search)
1017 * First, we search for a cacheline, then lastly we do a linear search
1020 * To search for the cacheline, there's three different possibilities:
1021 * * The set is too small to have a search tree, so we just do a linear
1022 * search over the whole set.
1024 * auxiliary search tree up to date would be too expensive, so we
1025 * use a much simpler lookup table to do a binary search -
1027 * * Or we use the auxiliary search tree we constructed earlier -
1036 * Each node in the auxiliary search tree covers a certain range
1042 if (unlikely(bkey_cmp(search, &t->end) >= 0))
1045 if (unlikely(bkey_cmp(search, t->data->start) < 0))
1048 i = bset_search_tree(t, search);
1053 i = bset_search_write_set(t, search);
1061 search) > 0);
1064 bkey_cmp(i.r, search) <= 0);
1068 bkey_cmp(i.l, search) <= 0)
1101 struct bkey *search,
1114 ret = bch_bset_search(b, start, search);
1123 struct bkey *search)
1125 return __bch_btree_iter_init(b, iter, search, b->set);