Lines Matching refs:j
372 static unsigned int inorder_next(unsigned int j, unsigned int size) in inorder_next() argument
374 if (j * 2 + 1 < size) { in inorder_next()
375 j = j * 2 + 1; in inorder_next()
377 while (j * 2 < size) in inorder_next()
378 j *= 2; in inorder_next()
380 j >>= ffz(j) + 1; in inorder_next()
382 return j; in inorder_next()
389 static unsigned int inorder_prev(unsigned int j, unsigned int size) in inorder_prev() argument
391 if (j * 2 < size) { in inorder_prev()
392 j = j * 2; in inorder_prev()
394 while (j * 2 + 1 < size) in inorder_prev()
395 j = j * 2 + 1; in inorder_prev()
397 j >>= ffs(j); in inorder_prev()
399 return j; in inorder_prev()
416 static unsigned int __to_inorder(unsigned int j, in __to_inorder() argument
420 unsigned int b = fls(j); in __to_inorder()
423 j ^= 1U << (b - 1); in __to_inorder()
424 j <<= 1; in __to_inorder()
425 j |= 1; in __to_inorder()
426 j <<= shift; in __to_inorder()
428 if (j > extra) in __to_inorder()
429 j -= (j - extra) >> 1; in __to_inorder()
431 return j; in __to_inorder()
438 static unsigned int to_inorder(unsigned int j, struct bset_tree *t) in to_inorder() argument
440 return __to_inorder(j, t->size, t->extra); in to_inorder()
443 static unsigned int __inorder_to_tree(unsigned int j, in __inorder_to_tree() argument
449 if (j > extra) in __inorder_to_tree()
450 j += j - extra; in __inorder_to_tree()
452 shift = ffs(j); in __inorder_to_tree()
454 j >>= shift; in __inorder_to_tree()
455 j |= roundup_pow_of_two(size) >> shift; in __inorder_to_tree()
457 return j; in __inorder_to_tree()
464 static unsigned int inorder_to_tree(unsigned int j, struct bset_tree *t) in inorder_to_tree() argument
466 return __inorder_to_tree(j, t->size, t->extra); in inorder_to_tree()
480 unsigned int i = 1, j = rounddown_pow_of_two(size - 1);
487 if (__inorder_to_tree(i, size, extra) != j)
488 panic("size %10u j %10u i %10u", size, j, i);
490 if (__to_inorder(j, size, extra) != i)
491 panic("size %10u j %10u i %10u", size, j, i);
493 if (j == rounddown_pow_of_two(size) - 1)
496 BUG_ON(inorder_prev(inorder_next(j, size), size) != j);
498 j = inorder_next(j, size);
545 static struct bkey *tree_to_bkey(struct bset_tree *t, unsigned int j) in tree_to_bkey() argument
547 return cacheline_to_bkey(t, to_inorder(j, t), t->tree[j].m); in tree_to_bkey()
550 static struct bkey *tree_to_prev_bkey(struct bset_tree *t, unsigned int j) in tree_to_prev_bkey() argument
552 return (void *) (((uint64_t *) tree_to_bkey(t, j)) - t->prev[j]); in tree_to_prev_bkey()
593 static void make_bfloat(struct bset_tree *t, unsigned int j) in make_bfloat() argument
595 struct bkey_float *f = &t->tree[j]; in make_bfloat()
596 struct bkey *m = tree_to_bkey(t, j); in make_bfloat()
597 struct bkey *p = tree_to_prev_bkey(t, j); in make_bfloat()
599 struct bkey *l = is_power_of_2(j) in make_bfloat()
601 : tree_to_prev_bkey(t, j >> ffs(j)); in make_bfloat()
603 struct bkey *r = is_power_of_2(j + 1) in make_bfloat()
605 : tree_to_bkey(t, j >> (ffz(j) + 1)); in make_bfloat()
641 unsigned int j = roundup(t[-1].size, in bset_alloc_tree() local
644 t->tree = t[-1].tree + j; in bset_alloc_tree()
645 t->prev = t[-1].prev + j; in bset_alloc_tree()
696 unsigned int j, cacheline = 1; in bch_bset_build_written_tree() local
714 for (j = inorder_next(0, t->size); in bch_bset_build_written_tree()
715 j; in bch_bset_build_written_tree()
716 j = inorder_next(j, t->size)) { in bch_bset_build_written_tree()
720 t->prev[j] = bkey_u64s(prev); in bch_bset_build_written_tree()
721 t->tree[j].m = bkey_to_cacheline_offset(t, cacheline++, k); in bch_bset_build_written_tree()
730 for (j = inorder_next(0, t->size); in bch_bset_build_written_tree()
731 j; in bch_bset_build_written_tree()
732 j = inorder_next(j, t->size)) in bch_bset_build_written_tree()
733 make_bfloat(t, j); in bch_bset_build_written_tree()
742 unsigned int inorder, j = 1; in bch_bset_fix_invalidated_key() local
763 j = inorder_to_tree(inorder, t); in bch_bset_fix_invalidated_key()
765 if (j && in bch_bset_fix_invalidated_key()
766 j < t->size && in bch_bset_fix_invalidated_key()
767 k == tree_to_bkey(t, j)) in bch_bset_fix_invalidated_key()
769 make_bfloat(t, j); in bch_bset_fix_invalidated_key()
770 j = j * 2; in bch_bset_fix_invalidated_key()
771 } while (j < t->size); in bch_bset_fix_invalidated_key()
773 j = inorder_to_tree(inorder + 1, t); in bch_bset_fix_invalidated_key()
775 if (j && in bch_bset_fix_invalidated_key()
776 j < t->size && in bch_bset_fix_invalidated_key()
777 k == tree_to_prev_bkey(t, j)) in bch_bset_fix_invalidated_key()
779 make_bfloat(t, j); in bch_bset_fix_invalidated_key()
780 j = j * 2 + 1; in bch_bset_fix_invalidated_key()
781 } while (j < t->size); in bch_bset_fix_invalidated_key()
790 unsigned int j = bkey_to_cacheline(t, k); in bch_bset_fix_lookup_table() local
801 while (j < t->size && in bch_bset_fix_lookup_table()
802 table_to_bkey(t, j) <= k) in bch_bset_fix_lookup_table()
803 j++; in bch_bset_fix_lookup_table()
809 for (; j < t->size; j++) { in bch_bset_fix_lookup_table()
810 t->prev[j] += shift; in bch_bset_fix_lookup_table()
812 if (t->prev[j] > 7) { in bch_bset_fix_lookup_table()
813 k = table_to_bkey(t, j - 1); in bch_bset_fix_lookup_table()
815 while (k < cacheline_to_bkey(t, j, 0)) in bch_bset_fix_lookup_table()
818 t->prev[j] = bkey_to_cacheline_offset(t, j, k); in bch_bset_fix_lookup_table()
967 unsigned int inorder, j, n = 1; in bset_search_tree() local
975 j = n; in bset_search_tree()
976 f = &t->tree[j]; in bset_search_tree()
980 n = j * 2; in bset_search_tree()
982 n = j * 2 + 1; in bset_search_tree()
984 if (bkey_cmp(tree_to_bkey(t, j), search) > 0) in bset_search_tree()
985 n = j * 2; in bset_search_tree()
987 n = j * 2 + 1; in bset_search_tree()
991 inorder = to_inorder(j, t); in bset_search_tree()
1001 f = &t->tree[inorder_next(j, t->size)]; in bset_search_tree()
1009 f = &t->tree[inorder_prev(j, t->size)]; in bset_search_tree()
1378 size_t j; in bch_btree_keys_stats() local
1386 for (j = 1; j < t->size; j++) in bch_btree_keys_stats()
1387 if (t->tree[j].exponent == 127) in bch_btree_keys_stats()