From 1c6fdbd8f2465ddfb73a01ec620cbf3d14044e1a Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Thu, 16 Mar 2017 22:18:50 -0800 Subject: bcachefs: Initial commit Initially forked from drivers/md/bcache, bcachefs is a new copy-on-write filesystem with every feature you could possibly want. Website: https://bcachefs.org Signed-off-by: Kent Overstreet --- fs/bcachefs/keylist.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 67 insertions(+) create mode 100644 fs/bcachefs/keylist.c (limited to 'fs/bcachefs/keylist.c') diff --git a/fs/bcachefs/keylist.c b/fs/bcachefs/keylist.c new file mode 100644 index 000000000000..5da54ced9cad --- /dev/null +++ b/fs/bcachefs/keylist.c @@ -0,0 +1,67 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include "bcachefs.h" +#include "keylist.h" + +int bch2_keylist_realloc(struct keylist *l, u64 *inline_u64s, + size_t nr_inline_u64s, size_t new_u64s) +{ + size_t oldsize = bch_keylist_u64s(l); + size_t newsize = oldsize + new_u64s; + u64 *old_buf = l->keys_p == inline_u64s ? NULL : l->keys_p; + u64 *new_keys; + + newsize = roundup_pow_of_two(newsize); + + if (newsize <= nr_inline_u64s || + (old_buf && roundup_pow_of_two(oldsize) == newsize)) + return 0; + + new_keys = krealloc(old_buf, sizeof(u64) * newsize, GFP_NOIO); + if (!new_keys) + return -ENOMEM; + + if (!old_buf) + memcpy_u64s(new_keys, inline_u64s, oldsize); + + l->keys_p = new_keys; + l->top_p = new_keys + oldsize; + + return 0; +} + +void bch2_keylist_add_in_order(struct keylist *l, struct bkey_i *insert) +{ + struct bkey_i *where; + + for_each_keylist_key(l, where) + if (bkey_cmp(insert->k.p, where->k.p) < 0) + break; + + memmove_u64s_up((u64 *) where + insert->k.u64s, + where, + ((u64 *) l->top) - ((u64 *) where)); + + l->top_p += insert->k.u64s; + bkey_copy(where, insert); +} + +void bch2_keylist_pop_front(struct keylist *l) +{ + l->top_p -= bch2_keylist_front(l)->k.u64s; + + memmove_u64s_down(l->keys, + bkey_next(l->keys), + bch_keylist_u64s(l)); +} + +#ifdef CONFIG_BCACHEFS_DEBUG +void bch2_verify_keylist_sorted(struct keylist *l) +{ + struct bkey_i *k; + + for_each_keylist_key(l, k) + BUG_ON(bkey_next(k) != l->top && + bkey_cmp(k->k.p, bkey_next(k)->k.p) >= 0); +} +#endif -- cgit v1.2.3