295 /* Auxiliary search trees */
394 /* Binary tree stuff for auxiliary search trees */
399  * t->tree is a binary search tree in an array; each node corresponds to a key
478  * maintain a full search tree, we just keep a simple lookup table in t->prev.
1044 				struct bpos *search)  in bset_search_write_set()  argument
1051 		if (bpos_lt(rw_aux_tree(b, t)[m].k, *search))  in bset_search_write_set()
1094 				const struct bpos *search,  in bset_search_tree()  argument
1121 		cmp = bkey_cmp_p_or_unp(b, k, packed_search, search);  in bset_search_tree()
1148 				struct bpos *search,  in __bch2_bset_search()  argument
1153 	 * First, we search for a cacheline, then lastly we do a linear search  in __bch2_bset_search()
1156 	 * To search for the cacheline, there's three different possibilities:  in __bch2_bset_search()
1157 	 *  * The set is too small to have a search tree, so we just do a linear  in __bch2_bset_search()
1158 	 *    search over the whole set.  in __bch2_bset_search()
1160 	 *    auxiliary search tree up to date would be too expensive, so we  in __bch2_bset_search()
1161 	 *    use a much simpler lookup table to do a binary search -  in __bch2_bset_search()
1163 	 *  * Or we use the auxiliary search tree we constructed earlier -  in __bch2_bset_search()
1171 		return bset_search_write_set(b, t, search);  in __bch2_bset_search()
1173 		return bset_search_tree(b, t, search, lossy_packed_search);  in __bch2_bset_search()
1182 				struct bpos *search,  in bch2_bset_search_linear()  argument
1190 					lossy_packed_search, search) < 0)  in bch2_bset_search_linear()
1195 		       bkey_iter_pos_cmp(b, m, search) < 0)  in bch2_bset_search_linear()
1203 					packed_search, search) >= 0);  in bch2_bset_search_linear()
1241 			      struct btree *b, struct bpos *search)  in btree_node_iter_init_pack_failed()  argument
1245 	trace_bkey_pack_pos_fail(search);  in btree_node_iter_init_pack_failed()
1250 	       bkey_iter_pos_cmp(b, k, search) < 0)  in btree_node_iter_init_pack_failed()
1259  * @b:		btree node to search
1260  * @search:	search key
1272  * If you search for k, the lookup code isn't guaranteed to return you any
1273  * specific k. The lookup code is conceptually doing a binary search and
1285  *    key strictly greater than your search key - an extent that compares equal
1286  *    to the search key is going to have 0 sectors after the search key.
1288  *    But this does mean that we can't just search for
1292  *    position and we'd get that when we search instead of the preceding extent
1295  *    So we've got to search for start_of_range, then after the lookup iterate
1300 			       struct btree *b, struct bpos *search)  in bch2_btree_node_iter_init()  argument
1307 	EBUG_ON(bpos_lt(*search, b->data->min_key));  in bch2_btree_node_iter_init()
1308 	EBUG_ON(bpos_gt(*search, b->data->max_key));  in bch2_btree_node_iter_init()
1313 	switch (bch2_bkey_pack_pos_lossy(&p, *search, b)) {  in bch2_btree_node_iter_init()
1321 		btree_node_iter_init_pack_failed(iter, b, search);  in bch2_btree_node_iter_init()
1326 		k[i] = __bch2_bset_search(b, b->set + i, search, &p);  in bch2_btree_node_iter_init()
1334 		k[i] = bch2_bset_search_linear(b, t, search,  in bch2_btree_node_iter_init()