md/bcache/bset.c

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