bset.c (6f10f7d1b02b1bbc305f88d7696445dd38b13881) bset.c (1fae7cf05293d3a2c9e59c1bc59372322386467c)
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Code for working with individual keys, and sorted sets of keys with in a
4 * btree node
5 *
6 * Copyright 2012 Google, Inc.
7 */
8

--- 571 unchanged lines hidden (view full) ---

580 * bkey->high too.
581 * See make_bfloat() to check when most significant bit of f->exponent
582 * is set or not.
583 */
584static inline unsigned int bfloat_mantissa(const struct bkey *k,
585 struct bkey_float *f)
586{
587 const uint64_t *p = &k->low - (f->exponent >> 6);
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Code for working with individual keys, and sorted sets of keys with in a
4 * btree node
5 *
6 * Copyright 2012 Google, Inc.
7 */
8

--- 571 unchanged lines hidden (view full) ---

580 * bkey->high too.
581 * See make_bfloat() to check when most significant bit of f->exponent
582 * is set or not.
583 */
584static inline unsigned int bfloat_mantissa(const struct bkey *k,
585 struct bkey_float *f)
586{
587 const uint64_t *p = &k->low - (f->exponent >> 6);
588
588 return shrd128(p[-1], p[0], f->exponent & 63) & BKEY_MANTISSA_MASK;
589}
590
591static void make_bfloat(struct bset_tree *t, unsigned int j)
592{
593 struct bkey_float *f = &t->tree[j];
594 struct bkey *m = tree_to_bkey(t, j);
595 struct bkey *p = tree_to_prev_bkey(t, j);

--- 363 unchanged lines hidden (view full) ---

959 * gets 1. If p >= t->size, the most significant bit is
960 * not set, right shifting 31 bits gets 0.
961 * So the following 2 lines equals to
962 * if (p >= t->size)
963 * p = 0;
964 * but a branch instruction is avoided.
965 */
966 unsigned int p = n << 4;
589 return shrd128(p[-1], p[0], f->exponent & 63) & BKEY_MANTISSA_MASK;
590}
591
592static void make_bfloat(struct bset_tree *t, unsigned int j)
593{
594 struct bkey_float *f = &t->tree[j];
595 struct bkey *m = tree_to_bkey(t, j);
596 struct bkey *p = tree_to_prev_bkey(t, j);

--- 363 unchanged lines hidden (view full) ---

960 * gets 1. If p >= t->size, the most significant bit is
961 * not set, right shifting 31 bits gets 0.
962 * So the following 2 lines equals to
963 * if (p >= t->size)
964 * p = 0;
965 * but a branch instruction is avoided.
966 */
967 unsigned int p = n << 4;
968
967 p &= ((int) (p - t->size)) >> 31;
968
969 prefetch(&t->tree[p]);
970
971 j = n;
972 f = &t->tree[j];
973
974 /*

--- 134 unchanged lines hidden (view full) ---

1109}
1110
1111static struct bkey *__bch_btree_iter_init(struct btree_keys *b,
1112 struct btree_iter *iter,
1113 struct bkey *search,
1114 struct bset_tree *start)
1115{
1116 struct bkey *ret = NULL;
969 p &= ((int) (p - t->size)) >> 31;
970
971 prefetch(&t->tree[p]);
972
973 j = n;
974 f = &t->tree[j];
975
976 /*

--- 134 unchanged lines hidden (view full) ---

1111}
1112
1113static struct bkey *__bch_btree_iter_init(struct btree_keys *b,
1114 struct btree_iter *iter,
1115 struct bkey *search,
1116 struct bset_tree *start)
1117{
1118 struct bkey *ret = NULL;
1119
1117 iter->size = ARRAY_SIZE(iter->data);
1118 iter->used = 0;
1119
1120#ifdef CONFIG_BCACHE_DEBUG
1121 iter->b = b;
1122#endif
1123
1124 for (; start <= bset_tree_last(b); start++) {

--- 199 unchanged lines hidden (view full) ---

1324{
1325 __btree_sort(b, iter, 0, b->page_order, true, state);
1326}
1327
1328void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new,
1329 struct bset_sort_state *state)
1330{
1331 uint64_t start_time = local_clock();
1120 iter->size = ARRAY_SIZE(iter->data);
1121 iter->used = 0;
1122
1123#ifdef CONFIG_BCACHE_DEBUG
1124 iter->b = b;
1125#endif
1126
1127 for (; start <= bset_tree_last(b); start++) {

--- 199 unchanged lines hidden (view full) ---

1327{
1328 __btree_sort(b, iter, 0, b->page_order, true, state);
1329}
1330
1331void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new,
1332 struct bset_sort_state *state)
1333{
1334 uint64_t start_time = local_clock();
1332
1333 struct btree_iter iter;
1335 struct btree_iter iter;
1336
1334 bch_btree_iter_init(b, &iter, NULL);
1335
1336 btree_mergesort(b, new->set->data, &iter, false, true);
1337
1338 bch_time_stats_update(&state->time, start_time);
1339
1340 new->set->size = 0; // XXX: why?
1341}

--- 56 unchanged lines hidden --- 		1337 bch_btree_iter_init(b, &iter, NULL);
1338
1339 btree_mergesort(b, new->set->data, &iter, false, true);
1340
1341 bch_time_stats_update(&state->time, start_time);
1342
1343 new->set->size = 0; // XXX: why?
1344}

--- 56 unchanged lines hidden ---