Lines Matching refs:j
371 static unsigned int inorder_next(unsigned int j, unsigned int size) in inorder_next() argument
373 if (j * 2 + 1 < size) { in inorder_next()
374 j = j * 2 + 1; in inorder_next()
376 while (j * 2 < size) in inorder_next()
377 j *= 2; in inorder_next()
379 j >>= ffz(j) + 1; in inorder_next()
381 return j; in inorder_next()
388 static unsigned int inorder_prev(unsigned int j, unsigned int size) in inorder_prev() argument
390 if (j * 2 < size) { in inorder_prev()
391 j = j * 2; in inorder_prev()
393 while (j * 2 + 1 < size) in inorder_prev()
394 j = j * 2 + 1; in inorder_prev()
396 j >>= ffs(j); in inorder_prev()
398 return j; in inorder_prev()
415 static unsigned int __to_inorder(unsigned int j, in __to_inorder() argument
419 unsigned int b = fls(j); in __to_inorder()
422 j ^= 1U << (b - 1); in __to_inorder()
423 j <<= 1; in __to_inorder()
424 j |= 1; in __to_inorder()
425 j <<= shift; in __to_inorder()
427 if (j > extra) in __to_inorder()
428 j -= (j - extra) >> 1; in __to_inorder()
430 return j; in __to_inorder()
437 static unsigned int to_inorder(unsigned int j, struct bset_tree *t) in to_inorder() argument
439 return __to_inorder(j, t->size, t->extra); in to_inorder()
442 static unsigned int __inorder_to_tree(unsigned int j, in __inorder_to_tree() argument
448 if (j > extra) in __inorder_to_tree()
449 j += j - extra; in __inorder_to_tree()
451 shift = ffs(j); in __inorder_to_tree()
453 j >>= shift; in __inorder_to_tree()
454 j |= roundup_pow_of_two(size) >> shift; in __inorder_to_tree()
456 return j; in __inorder_to_tree()
463 static unsigned int inorder_to_tree(unsigned int j, struct bset_tree *t) in inorder_to_tree() argument
465 return __inorder_to_tree(j, t->size, t->extra); in inorder_to_tree()
479 unsigned int i = 1, j = rounddown_pow_of_two(size - 1);
486 if (__inorder_to_tree(i, size, extra) != j)
487 panic("size %10u j %10u i %10u", size, j, i);
489 if (__to_inorder(j, size, extra) != i)
490 panic("size %10u j %10u i %10u", size, j, i);
492 if (j == rounddown_pow_of_two(size) - 1)
495 BUG_ON(inorder_prev(inorder_next(j, size), size) != j);
497 j = inorder_next(j, size);
544 static struct bkey *tree_to_bkey(struct bset_tree *t, unsigned int j) in tree_to_bkey() argument
546 return cacheline_to_bkey(t, to_inorder(j, t), t->tree[j].m); in tree_to_bkey()
549 static struct bkey *tree_to_prev_bkey(struct bset_tree *t, unsigned int j) in tree_to_prev_bkey() argument
551 return (void *) (((uint64_t *) tree_to_bkey(t, j)) - t->prev[j]); in tree_to_prev_bkey()
592 static void make_bfloat(struct bset_tree *t, unsigned int j) in make_bfloat() argument
594 struct bkey_float *f = &t->tree[j]; in make_bfloat()
595 struct bkey *m = tree_to_bkey(t, j); in make_bfloat()
596 struct bkey *p = tree_to_prev_bkey(t, j); in make_bfloat()
598 struct bkey *l = is_power_of_2(j) in make_bfloat()
600 : tree_to_prev_bkey(t, j >> ffs(j)); in make_bfloat()
602 struct bkey *r = is_power_of_2(j + 1) in make_bfloat()
604 : tree_to_bkey(t, j >> (ffz(j) + 1)); in make_bfloat()
640 unsigned int j = roundup(t[-1].size, in bset_alloc_tree() local
643 t->tree = t[-1].tree + j; in bset_alloc_tree()
644 t->prev = t[-1].prev + j; in bset_alloc_tree()
694 unsigned int j, cacheline = 1; in bch_bset_build_written_tree() local
712 for (j = inorder_next(0, t->size); in bch_bset_build_written_tree()
713 j; in bch_bset_build_written_tree()
714 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()
741 unsigned int inorder, j = 1; in bch_bset_fix_invalidated_key() local
762 j = inorder_to_tree(inorder, t); in bch_bset_fix_invalidated_key()
764 if (j && in bch_bset_fix_invalidated_key()
765 j < t->size && in bch_bset_fix_invalidated_key()
766 k == tree_to_bkey(t, j)) in bch_bset_fix_invalidated_key()
768 make_bfloat(t, j); in bch_bset_fix_invalidated_key()
769 j = j * 2; in bch_bset_fix_invalidated_key()
770 } while (j < t->size); in bch_bset_fix_invalidated_key()
772 j = inorder_to_tree(inorder + 1, t); in bch_bset_fix_invalidated_key()
774 if (j && in bch_bset_fix_invalidated_key()
775 j < t->size && in bch_bset_fix_invalidated_key()
776 k == tree_to_prev_bkey(t, j)) in bch_bset_fix_invalidated_key()
778 make_bfloat(t, j); in bch_bset_fix_invalidated_key()
779 j = j * 2 + 1; in bch_bset_fix_invalidated_key()
780 } while (j < t->size); in bch_bset_fix_invalidated_key()
788 unsigned int j = bkey_to_cacheline(t, k); in bch_bset_fix_lookup_table() local
799 while (j < t->size && in bch_bset_fix_lookup_table()
800 table_to_bkey(t, j) <= k) in bch_bset_fix_lookup_table()
801 j++; in bch_bset_fix_lookup_table()
807 for (; j < t->size; j++) { in bch_bset_fix_lookup_table()
808 t->prev[j] += shift; in bch_bset_fix_lookup_table()
810 if (t->prev[j] > 7) { in bch_bset_fix_lookup_table()
811 k = table_to_bkey(t, j - 1); in bch_bset_fix_lookup_table()
813 while (k < cacheline_to_bkey(t, j, 0)) in bch_bset_fix_lookup_table()
816 t->prev[j] = bkey_to_cacheline_offset(t, j, k); in bch_bset_fix_lookup_table()
964 unsigned int inorder, j, n = 1; in bset_search_tree() local
972 j = n; in bset_search_tree()
973 f = &t->tree[j]; in bset_search_tree()
977 n = j * 2; in bset_search_tree()
979 n = j * 2 + 1; in bset_search_tree()
981 if (bkey_cmp(tree_to_bkey(t, j), search) > 0) in bset_search_tree()
982 n = j * 2; in bset_search_tree()
984 n = j * 2 + 1; in bset_search_tree()
988 inorder = to_inorder(j, t); in bset_search_tree()
998 f = &t->tree[inorder_next(j, t->size)]; in bset_search_tree()
1006 f = &t->tree[inorder_prev(j, t->size)]; in bset_search_tree()
1374 size_t j; in bch_btree_keys_stats() local
1382 for (j = 1; j < t->size; j++) in bch_btree_keys_stats()
1383 if (t->tree[j].exponent == 127) in bch_btree_keys_stats()