+/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _EYTZINGER_H
#define _EYTZINGER_H
*
* With one based indexing each level of the tree starts at a power of two -
* good for cacheline alignment:
- *
- * Size parameter is treated as if we were using 0 based indexing, however:
- * valid nodes, and inorder indices, are in the range [1..size) - that is, there
- * are actually size - 1 elements
*/
static inline unsigned eytzinger1_child(unsigned i, unsigned child)
static inline unsigned eytzinger1_first(unsigned size)
{
- return rounddown_pow_of_two(size - 1);
+ return rounddown_pow_of_two(size);
}
static inline unsigned eytzinger1_last(unsigned size)
{
- return rounddown_pow_of_two(size) - 1;
+ return rounddown_pow_of_two(size + 1) - 1;
}
/*
static inline unsigned eytzinger1_next(unsigned i, unsigned size)
{
- EBUG_ON(i >= size);
+ EBUG_ON(i > size);
- if (eytzinger1_right_child(i) < size) {
+ if (eytzinger1_right_child(i) <= size) {
i = eytzinger1_right_child(i);
- i <<= __fls(size) - __fls(i);
- i >>= i >= size;
+ i <<= __fls(size + 1) - __fls(i);
+ i >>= i > size;
} else {
i >>= ffz(i) + 1;
}
static inline unsigned eytzinger1_prev(unsigned i, unsigned size)
{
- EBUG_ON(i >= size);
+ EBUG_ON(i > size);
- if (eytzinger1_left_child(i) < size) {
- i = eytzinger1_left_child(i);
+ if (eytzinger1_left_child(i) <= size) {
+ i = eytzinger1_left_child(i) + 1;
- i <<= __fls(size) - __fls(i);
+ i <<= __fls(size + 1) - __fls(i);
i -= 1;
- i >>= i >= size;
+ i >>= i > size;
} else {
i >>= __ffs(i) + 1;
}
static inline unsigned eytzinger1_extra(unsigned size)
{
- return (size - rounddown_pow_of_two(size - 1)) << 1;
+ return (size + 1 - rounddown_pow_of_two(size)) << 1;
}
static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,
unsigned extra)
{
unsigned b = __fls(i);
- unsigned shift = __fls(size - 1) - b;
+ unsigned shift = __fls(size) - b;
int s;
- EBUG_ON(!i || i >= size);
+ EBUG_ON(!i || i > size);
i ^= 1U << b;
i <<= 1;
unsigned shift;
int s;
- EBUG_ON(!i || i >= size);
+ EBUG_ON(!i || i > size);
/*
* sign bit trick:
shift = __ffs(i);
i >>= shift + 1;
- i |= 1U << (__fls(size - 1) - shift);
+ i |= 1U << (__fls(size) - shift);
return i;
}
(_i) != 0; \
(_i) = eytzinger1_next((_i), (_size)))
-#if 0
-void eytzinger0_test(void)
-{
- unsigned i, j, size;
-
- for (size = 2;
- size < 65536000;
- size++) {
- if (!(size % 4096))
- printk(KERN_INFO "tree size %u\n", size);
-
- assert(eytzinger1_prev(0, size) == eytzinger1_last(size));
- assert(eytzinger1_next(0, size) == eytzinger1_first(size));
-
- assert(eytzinger1_prev(eytzinger1_first(size), size) == 0);
- assert(eytzinger1_next(eytzinger1_last(size), size) == 0);
-
- eytzinger1_for_each(j, size) {
- assert(from_inorder(i, size) == j);
- assert(to_inorder(j, size) == i);
-
- if (j != eytzinger1_last(size)) {
- unsigned next = eytzinger1_next(j, size);
-
- assert(eytzinger1_prev(next, size) == j);
- }
- }
- }
-
-}
-#endif
-
/* Zero based indexing version: */
static inline unsigned eytzinger0_child(unsigned i, unsigned child)
return eytzinger0_child(i, 1);
}
-#if 0
static inline unsigned eytzinger0_first(unsigned size)
{
+ return eytzinger1_first(size) - 1;
}
static inline unsigned eytzinger0_last(unsigned size)
{
+ return eytzinger1_last(size) - 1;
}
static inline unsigned eytzinger0_next(unsigned i, unsigned size)
{
+ return eytzinger1_next(i + 1, size) - 1;
}
static inline unsigned eytzinger0_prev(unsigned i, unsigned size)
{
+ return eytzinger1_prev(i + 1, size) - 1;
}
-#endif
static inline unsigned eytzinger0_extra(unsigned size)
{
- return (size + 1 - rounddown_pow_of_two(size)) << 1;
+ return eytzinger1_extra(size);
}
static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,
unsigned extra)
{
- return __eytzinger1_to_inorder(i + 1, size + 1, extra) - 1;
+ return __eytzinger1_to_inorder(i + 1, size, extra) - 1;
}
static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,
unsigned extra)
{
- return __inorder_to_eytzinger1(i + 1, size + 1, extra) - 1;
+ return __inorder_to_eytzinger1(i + 1, size, extra) - 1;
}
static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)
return __inorder_to_eytzinger0(i, size, eytzinger0_extra(size));
}
+#define eytzinger0_for_each(_i, _size) \
+ for ((_i) = eytzinger0_first((_size)); \
+ (_i) != -1; \
+ (_i) = eytzinger0_next((_i), (_size)))
+
typedef int (*eytzinger_cmp_fn)(const void *l, const void *r, size_t size);
-static inline size_t eytzinger0_find(void *base, size_t nr, size_t size,
- eytzinger_cmp_fn cmp, void *search)
+/* return greatest node <= @search, or -1 if not found */
+static inline ssize_t eytzinger0_find_le(void *base, size_t nr, size_t size,
+ eytzinger_cmp_fn cmp, const void *search)
{
- size_t i = 0;
- int res;
+ unsigned i, n = 0;
- while (i < nr &&
- (res = cmp(search, base + i * size, size)))
- i = eytzinger0_child(i, res > 0);
+ if (!nr)
+ return -1;
- if (IS_ENABLED(CONFIG_BCACHEFS_DEBUG)) {
- bool found1 = i < nr, found2 = false;
- size_t j;
+ do {
+ i = n;
+ n = eytzinger0_child(i, cmp(search, base + i * size, size) >= 0);
+ } while (n < nr);
- for (j = 0; j < nr; j++)
- if (!cmp(base + j * size, search, size))
- found2 = true;
+ if (n & 1) {
+ /* @i was greater than @search, return previous node: */
- BUG_ON(found1 != found2);
- }
+ if (i == eytzinger0_first(nr))
+ return -1;
- return i;
+ return eytzinger0_prev(i, nr);
+ } else {
+ return i;
+ }
}
+#define eytzinger0_find(base, nr, size, _cmp, search) \
+({ \
+ void *_base = (base); \
+ void *_search = (search); \
+ size_t _nr = (nr); \
+ size_t _size = (size); \
+ size_t _i = 0; \
+ int _res; \
+ \
+ while (_i < _nr && \
+ (_res = _cmp(_search, _base + _i * _size, _size))) \
+ _i = eytzinger0_child(_i, _res > 0); \
+ _i; \
+})
+
void eytzinger0_sort(void *, size_t, size_t,
int (*cmp_func)(const void *, const void *, size_t),
void (*swap_func)(void *, void *, size_t));
projects / bcachefs-tools-debian / blobdiff