fs/bcachefs/bset.c

297 /* Auxiliary search trees */
412 /* Binary tree stuff for auxiliary search trees */
417  * t->tree is a binary search tree in an array; each node corresponds to a key
505  * maintain a full search tree, we just keep a simple lookup table in t->prev.
1071 				struct bpos *search)
1078 		if (bpos_lt(rw_aux_tree(b, t)[m].k, *search))
1122 				const struct bpos *search,
1149 		cmp = bkey_cmp_p_or_unp(b, k, packed_search, search);
1176 				struct bpos *search,
1181 	 * First, we search for a cacheline, then lastly we do a linear search
1184 	 * To search for the cacheline, there's three different possibilities:
1185 	 *  * The set is too small to have a search tree, so we just do a linear
1186 	 *    search over the whole set.
1188 	 *    auxiliary search tree up to date would be too expensive, so we
1189 	 *    use a much simpler lookup table to do a binary search -
1191 	 *  * Or we use the auxiliary search tree we constructed earlier -
1199 		return bset_search_write_set(b, t, search);
1201 		return bset_search_tree(b, t, search, lossy_packed_search);
1210 				struct bpos *search,
1218 					lossy_packed_search, search) < 0)
1223 		       bkey_iter_pos_cmp(b, m, search) < 0)
1231 					packed_search, search) >= 0);
1269 			      struct btree *b, struct bpos *search)
1273 	trace_bkey_pack_pos_fail(search);
1278 	       bkey_iter_pos_cmp(b, k, search) < 0)
1287  * @b:		btree node to search
1288  * @search:	search key
1300  * If you search for k, the lookup code isn't guaranteed to return you any
1301  * specific k. The lookup code is conceptually doing a binary search and
1313  *    key strictly greater than your search key - an extent that compares equal
1314  *    to the search key is going to have 0 sectors after the search key.
1316  *    But this does mean that we can't just search for
1320  *    position and we'd get that when we search instead of the preceding extent
1323  *    So we've got to search for start_of_range, then after the lookup iterate
1328 			       struct btree *b, struct bpos *search)
1335 	EBUG_ON(bpos_lt(*search, b->data->min_key));
1336 	EBUG_ON(bpos_gt(*search, b->data->max_key));
1341 	switch (bch2_bkey_pack_pos_lossy(&p, *search, b)) {
1349 		btree_node_iter_init_pack_failed(iter, b, search);
1354 		k[i] = __bch2_bset_search(b, b->set + i, search, &p);
1362 		k[i] = bch2_bset_search_linear(b, t, search,