234 /* Auxiliary search trees */
254  * the auxiliar search tree - when we're done searching the bset_float tree we
255  * have this many bytes left that we do a linear search over.
259  * cacheline in the linear search - but the linear search might stop before it
276 /* Space required for the auxiliary search trees */
366 /* Binary tree stuff for auxiliary search trees */
510  * t->tree is a binary search tree in an array; each node corresponds to a key
557  * maintain a full search tree, we just keep a simple lookup table in t->prev.
685  * accelerate bkey search in a btree node (pointed by bset_tree->data in
686  * memory). After search in the auxiliar tree by calling bset_search_tree(),
689  * linear comparison does the exact search, see __bch_bset_search() for how
943 						     const struct bkey *search)  in bset_search_write_set()  argument
950 		if (bkey_cmp(table_to_bkey(t, m), search) > 0)  in bset_search_write_set()
963 						const struct bkey *search)  in bset_search_tree()  argument
979 			if (f->mantissa >= bfloat_mantissa(search, f))  in bset_search_tree()
984 			if (bkey_cmp(tree_to_bkey(t, j), search) > 0)  in bset_search_tree()
1019 			       const struct bkey *search)  in __bch_bset_search()  argument
1024 	 * First, we search for a cacheline, then lastly we do a linear search  in __bch_bset_search()
1027 	 * To search for the cacheline, there's three different possibilities:  in __bch_bset_search()
1028 	 *  * The set is too small to have a search tree, so we just do a linear  in __bch_bset_search()
1029 	 *    search over the whole set.  in __bch_bset_search()
1031 	 *    auxiliary search tree up to date would be too expensive, so we  in __bch_bset_search()
1032 	 *    use a much simpler lookup table to do a binary search -  in __bch_bset_search()
1034 	 *  * Or we use the auxiliary search tree we constructed earlier -  in __bch_bset_search()
1043 		 * Each node in the auxiliary search tree covers a certain range  in __bch_bset_search()
1049 		if (unlikely(bkey_cmp(search, &t->end) >= 0))  in __bch_bset_search()
1052 		if (unlikely(bkey_cmp(search, t->data->start) < 0))  in __bch_bset_search()
1055 		i = bset_search_tree(t, search);  in __bch_bset_search()
1060 		i = bset_search_write_set(t, search);  in __bch_bset_search()
1068 				search) > 0);  in __bch_bset_search()
1071 		       bkey_cmp(i.r, search) <= 0);  in __bch_bset_search()
1075 	       bkey_cmp(i.l, search) <= 0)  in __bch_bset_search()
1109 					  struct bkey *search,  in __bch_btree_iter_init()  argument
1122 		ret = bch_bset_search(b, start, search);  in __bch_btree_iter_init()
1131 				 struct bkey *search)  in bch_btree_iter_init()  argument
1133 	return __bch_btree_iter_init(b, iter, search, b->set);  in bch_btree_iter_init()