git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/keylist.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "keylist.h"
   5
   6 int bch2_keylist_realloc(struct keylist *l, u64 *inline_u64s,
   7                         size_t nr_inline_u64s, size_t new_u64s)
   8 {
   9         size_t oldsize = bch2_keylist_u64s(l);
  10         size_t newsize = oldsize + new_u64s;
  11         u64 *old_buf = l->keys_p == inline_u64s ? NULL : l->keys_p;
  12         u64 *new_keys;
  13
  14         newsize = roundup_pow_of_two(newsize);
  15
  16         if (newsize <= nr_inline_u64s ||
  17             (old_buf && roundup_pow_of_two(oldsize) == newsize))
  18                 return 0;
  19
  20         new_keys = krealloc(old_buf, sizeof(u64) * newsize, GFP_NOIO);
  21         if (!new_keys)
  22                 return -ENOMEM;
  23
  24         if (!old_buf)
  25                 memcpy_u64s(new_keys, inline_u64s, oldsize);
  26
  27         l->keys_p = new_keys;
  28         l->top_p = new_keys + oldsize;
  29
  30         return 0;
  31 }
  32
  33 void bch2_keylist_add_in_order(struct keylist *l, struct bkey_i *insert)
  34 {
  35         struct bkey_i *where;
  36
  37         for_each_keylist_key(l, where)
  38                 if (bkey_cmp(insert->k.p, where->k.p) < 0)
  39                         break;
  40
  41         memmove_u64s_up((u64 *) where + insert->k.u64s,
  42                         where,
  43                         ((u64 *) l->top) - ((u64 *) where));
  44
  45         l->top_p += insert->k.u64s;
  46         bkey_copy(where, insert);
  47 }
  48
  49 void bch2_keylist_pop_front(struct keylist *l)
  50 {
  51         l->top_p -= bch2_keylist_front(l)->k.u64s;
  52
  53         memmove_u64s_down(l->keys,
  54                           bkey_next(l->keys),
  55                           bch2_keylist_u64s(l));
  56 }
  57
  58 #ifdef CONFIG_BCACHEFS_DEBUG
  59 void bch2_verify_keylist_sorted(struct keylist *l)
  60 {
  61         struct bkey_i *k;
  62
  63         for_each_keylist_key(l, k)
  64                 BUG_ON(bkey_next(k) != l->top &&
  65                        bkey_cmp(k->k.p, bkey_next(k)->k.p) >= 0);
  66 }
  67 #endif