372  * return array index next to j when does in-order traverse
375 static unsigned int inorder_next(unsigned int j, unsigned int size)  in inorder_next()  argument
377 	if (j * 2 + 1 < size) {  in inorder_next()
378 		j = j * 2 + 1;  in inorder_next()
380 		while (j * 2 < size)  in inorder_next()
381 			j *= 2;  in inorder_next()
383 		j >>= ffz(j) + 1;  in inorder_next()
385 	return j;  in inorder_next()
389  * return array index previous to j when does in-order traverse
392 static unsigned int inorder_prev(unsigned int j, unsigned int size)  in inorder_prev()  argument
394 	if (j * 2 < size) {  in inorder_prev()
395 		j = j * 2;  in inorder_prev()
397 		while (j * 2 + 1 < size)  in inorder_prev()
398 			j = j * 2 + 1;  in inorder_prev()
400 		j >>= ffs(j);  in inorder_prev()
402 	return j;  in inorder_prev()
413  * Also tested for every j, size up to size somewhere around 6 million.
419 static unsigned int __to_inorder(unsigned int j,  in __to_inorder()  argument
423 	unsigned int b = fls(j);  in __to_inorder()
426 	j  ^= 1U << (b - 1);  in __to_inorder()
427 	j <<= 1;  in __to_inorder()
428 	j  |= 1;  in __to_inorder()
429 	j <<= shift;  in __to_inorder()
431 	if (j > extra)  in __to_inorder()
432 		j -= (j - extra) >> 1;  in __to_inorder()
434 	return j;  in __to_inorder()
438  * Return the cacheline index in bset_tree->data, where j is index
441 static unsigned int to_inorder(unsigned int j, struct bset_tree *t)  in to_inorder()  argument
443 	return __to_inorder(j, t->size, t->extra);  in to_inorder()
446 static unsigned int __inorder_to_tree(unsigned int j,  in __inorder_to_tree()  argument
452 	if (j > extra)  in __inorder_to_tree()
453 		j += j - extra;  in __inorder_to_tree()
455 	shift = ffs(j);  in __inorder_to_tree()
457 	j >>= shift;  in __inorder_to_tree()
458 	j  |= roundup_pow_of_two(size) >> shift;  in __inorder_to_tree()
460 	return j;  in __inorder_to_tree()
465  * tree, j is the cacheline index of t->data.
467 static unsigned int inorder_to_tree(unsigned int j, struct bset_tree *t)  in inorder_to_tree()  argument
469 	return __inorder_to_tree(j, t->size, t->extra);  in inorder_to_tree()
483 		unsigned int i = 1, j = rounddown_pow_of_two(size - 1);
490 			if (__inorder_to_tree(i, size, extra) != j)
491 				panic("size %10u j %10u i %10u", size, j, i);
493 			if (__to_inorder(j, size, extra) != i)
494 				panic("size %10u j %10u i %10u", size, j, i);
496 			if (j == rounddown_pow_of_two(size) - 1)
499 			BUG_ON(inorder_prev(inorder_next(j, size), size) != j);
501 			j = inorder_next(j, size);
525  * bits we're going to store in bkey_float->mantissa. t->prev[j] stores the size
526  * of the previous key so we can walk backwards to it from t->tree[j]'s key.
548 static struct bkey *tree_to_bkey(struct bset_tree *t, unsigned int j)  in tree_to_bkey()  argument
550 	return cacheline_to_bkey(t, to_inorder(j, t), t->tree[j].m);  in tree_to_bkey()
553 static struct bkey *tree_to_prev_bkey(struct bset_tree *t, unsigned int j)  in tree_to_prev_bkey()  argument
555 	return (void *) (((uint64_t *) tree_to_bkey(t, j)) - t->prev[j]);  in tree_to_prev_bkey()
596 static void make_bfloat(struct bset_tree *t, unsigned int j)  in make_bfloat()  argument
598 	struct bkey_float *f = &t->tree[j];  in make_bfloat()
599 	struct bkey *m = tree_to_bkey(t, j);  in make_bfloat()
600 	struct bkey *p = tree_to_prev_bkey(t, j);  in make_bfloat()
602 	struct bkey *l = is_power_of_2(j)  in make_bfloat()
604 		: tree_to_prev_bkey(t, j >> ffs(j));  in make_bfloat()
606 	struct bkey *r = is_power_of_2(j + 1)  in make_bfloat()
608 		: tree_to_bkey(t, j >> (ffz(j) + 1));  in make_bfloat()
644 		unsigned int j = roundup(t[-1].size,  in bset_alloc_tree()  local
647 		t->tree = t[-1].tree + j;  in bset_alloc_tree()
648 		t->prev = t[-1].prev + j;  in bset_alloc_tree()
698 	unsigned int j, cacheline = 1;  in bch_bset_build_written_tree()  local
716 	for (j = inorder_next(0, t->size);  in bch_bset_build_written_tree()
717 	     j;  in bch_bset_build_written_tree()
718 	     j = inorder_next(j, t->size)) {  in bch_bset_build_written_tree()
724 		t->prev[j] = bkey_u64s(prev);  in bch_bset_build_written_tree()
725 		t->tree[j].m = bkey_to_cacheline_offset(t, cacheline++, k);  in bch_bset_build_written_tree()
734 	for (j = inorder_next(0, t->size);  in bch_bset_build_written_tree()
735 	     j;  in bch_bset_build_written_tree()
736 	     j = inorder_next(j, t->size))  in bch_bset_build_written_tree()
737 		make_bfloat(t, j);  in bch_bset_build_written_tree()
745 	unsigned int inorder, j = 1;  in bch_bset_fix_invalidated_key()  local
766 	j = inorder_to_tree(inorder, t);  in bch_bset_fix_invalidated_key()
768 	if (j &&  in bch_bset_fix_invalidated_key()
769 	    j < t->size &&  in bch_bset_fix_invalidated_key()
770 	    k == tree_to_bkey(t, j))  in bch_bset_fix_invalidated_key()
772 			make_bfloat(t, j);  in bch_bset_fix_invalidated_key()
773 			j = j * 2;  in bch_bset_fix_invalidated_key()
774 		} while (j < t->size);  in bch_bset_fix_invalidated_key()
776 	j = inorder_to_tree(inorder + 1, t);  in bch_bset_fix_invalidated_key()
778 	if (j &&  in bch_bset_fix_invalidated_key()
779 	    j < t->size &&  in bch_bset_fix_invalidated_key()
780 	    k == tree_to_prev_bkey(t, j))  in bch_bset_fix_invalidated_key()
782 			make_bfloat(t, j);  in bch_bset_fix_invalidated_key()
783 			j = j * 2 + 1;  in bch_bset_fix_invalidated_key()
784 		} while (j < t->size);  in bch_bset_fix_invalidated_key()
792 	unsigned int j = bkey_to_cacheline(t, k);  in bch_bset_fix_lookup_table()  local
803 	while (j < t->size &&  in bch_bset_fix_lookup_table()
804 	       table_to_bkey(t, j) <= k)  in bch_bset_fix_lookup_table()
805 		j++;  in bch_bset_fix_lookup_table()
811 	for (; j < t->size; j++) {  in bch_bset_fix_lookup_table()
812 		t->prev[j] += shift;  in bch_bset_fix_lookup_table()
814 		if (t->prev[j] > 7) {  in bch_bset_fix_lookup_table()
815 			k = table_to_bkey(t, j - 1);  in bch_bset_fix_lookup_table()
817 			while (k < cacheline_to_bkey(t, j, 0))  in bch_bset_fix_lookup_table()
820 			t->prev[j] = bkey_to_cacheline_offset(t, j, k);  in bch_bset_fix_lookup_table()
970 	unsigned int inorder, j, n = 1;  in bset_search_tree()  local
978 		j = n;  in bset_search_tree()
979 		f = &t->tree[j];  in bset_search_tree()
983 				n = j * 2;  in bset_search_tree()
985 				n = j * 2 + 1;  in bset_search_tree()
987 			if (bkey_cmp(tree_to_bkey(t, j), search) > 0)  in bset_search_tree()
988 				n = j * 2;  in bset_search_tree()
990 				n = j * 2 + 1;  in bset_search_tree()
994 	inorder = to_inorder(j, t);  in bset_search_tree()
1004 			f = &t->tree[inorder_next(j, t->size)];  in bset_search_tree()
1012 			f = &t->tree[inorder_prev(j, t->size)];  in bset_search_tree()
1400 		size_t j;  in bch_btree_keys_stats()  local
1408 			for (j = 1; j < t->size; j++)  in bch_btree_keys_stats()
1409 				if (t->tree[j].exponent == 127)  in bch_btree_keys_stats()