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
940 						     const struct bkey *search)  in bset_search_write_set()  argument
947 		if (bkey_cmp(table_to_bkey(t, m), search) > 0)  in bset_search_write_set()
960 						const struct bkey *search)  in bset_search_tree()  argument
976 			if (f->mantissa >= bfloat_mantissa(search, f))  in bset_search_tree()
981 			if (bkey_cmp(tree_to_bkey(t, j), search) > 0)  in bset_search_tree()
1016 			       const struct bkey *search)  in __bch_bset_search()  argument
1021 	 * First, we search for a cacheline, then lastly we do a linear search  in __bch_bset_search()
1024 	 * To search for the cacheline, there's three different possibilities:  in __bch_bset_search()
1025 	 *  * The set is too small to have a search tree, so we just do a linear  in __bch_bset_search()
1026 	 *    search over the whole set.  in __bch_bset_search()
1028 	 *    auxiliary search tree up to date would be too expensive, so we  in __bch_bset_search()
1029 	 *    use a much simpler lookup table to do a binary search -  in __bch_bset_search()
1031 	 *  * Or we use the auxiliary search tree we constructed earlier -  in __bch_bset_search()
1040 		 * Each node in the auxiliary search tree covers a certain range  in __bch_bset_search()
1046 		if (unlikely(bkey_cmp(search, &t->end) >= 0))  in __bch_bset_search()
1049 		if (unlikely(bkey_cmp(search, t->data->start) < 0))  in __bch_bset_search()
1052 		i = bset_search_tree(t, search);  in __bch_bset_search()
1057 		i = bset_search_write_set(t, search);  in __bch_bset_search()
1065 				search) > 0);  in __bch_bset_search()
1068 		       bkey_cmp(i.r, search) <= 0);  in __bch_bset_search()
1072 	       bkey_cmp(i.l, search) <= 0)  in __bch_bset_search()
1105 					  struct bkey *search,  in __bch_btree_iter_init()  argument
1118 		ret = bch_bset_search(b, start, search);  in __bch_btree_iter_init()
1127 				 struct bkey *search)  in bch_btree_iter_init()  argument
1129 	return __bch_btree_iter_init(b, iter, search, b->set);  in bch_btree_iter_init()