summaryrefslogtreecommitdiff
path: root/fs/bcachefs/keylist.c
blob: 5da54ced9cadb736a1edf22e77ddf81b9292f6fd (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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