xref: /linux/fs/bcachefs/eytzinger.h (revision 1c6fdbd8f2465ddfb73a01ec620cbf3d14044e1a)

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _EYTZINGER_H
#define _EYTZINGER_H

#include <linux/bitops.h>
#include <linux/log2.h>

#include "util.h"

/*
 * Traversal for trees in eytzinger layout - a full binary tree layed out in an
 * array
 */

/*
 * One based indexing version:
 *
 * 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)
{
	EBUG_ON(child > 1);

	return (i << 1) + child;
}

static inline unsigned eytzinger1_left_child(unsigned i)
{
	return eytzinger1_child(i, 0);
}

static inline unsigned eytzinger1_right_child(unsigned i)
{
	return eytzinger1_child(i, 1);
}

static inline unsigned eytzinger1_first(unsigned size)
{
	return rounddown_pow_of_two(size - 1);
}

static inline unsigned eytzinger1_last(unsigned size)
{
	return rounddown_pow_of_two(size) - 1;
}

/*
 * eytzinger1_next() and eytzinger1_prev() have the nice properties that
 *
 * eytzinger1_next(0) == eytzinger1_first())
 * eytzinger1_prev(0) == eytzinger1_last())
 *
 * eytzinger1_prev(eytzinger1_first()) == 0
 * eytzinger1_next(eytzinger1_last()) == 0
 */

static inline unsigned eytzinger1_next(unsigned i, unsigned size)
{
	EBUG_ON(i >= size);

	if (eytzinger1_right_child(i) < size) {
		i = eytzinger1_right_child(i);

		i <<= __fls(size) - __fls(i);
		i >>= i >= size;
	} else {
		i >>= ffz(i) + 1;
	}

	return i;
}

static inline unsigned eytzinger1_prev(unsigned i, unsigned size)
{
	EBUG_ON(i >= size);

	if (eytzinger1_left_child(i) < size) {
		i = eytzinger1_left_child(i) + 1;

		i <<= __fls(size) - __fls(i);
		i -= 1;
		i >>= i >= size;
	} else {
		i >>= __ffs(i) + 1;
	}

	return i;
}

static inline unsigned eytzinger1_extra(unsigned size)
{
	return (size - rounddown_pow_of_two(size - 1)) << 1;
}

static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,
					      unsigned extra)
{
	unsigned b = __fls(i);
	unsigned shift = __fls(size - 1) - b;
	int s;

	EBUG_ON(!i || i >= size);

	i  ^= 1U << b;
	i <<= 1;
	i  |= 1;
	i <<= shift;

	/*
	 * sign bit trick:
	 *
	 * if (i > extra)
	 *	i -= (i - extra) >> 1;
	 */
	s = extra - i;
	i += (s >> 1) & (s >> 31);

	return i;
}

static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,
					       unsigned extra)
{
	unsigned shift;
	int s;

	EBUG_ON(!i || i >= size);

	/*
	 * sign bit trick:
	 *
	 * if (i > extra)
	 *	i += i - extra;
	 */
	s = extra - i;
	i -= s & (s >> 31);

	shift = __ffs(i);

	i >>= shift + 1;
	i  |= 1U << (__fls(size - 1) - shift);

	return i;
}

static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)
{
	return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));
}

static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)
{
	return __inorder_to_eytzinger1(i, size, eytzinger1_extra(size));
}

#define eytzinger1_for_each(_i, _size)			\
	for ((_i) = eytzinger1_first((_size));		\
	     (_i) != 0;					\
	     (_i) = eytzinger1_next((_i), (_size)))

/* Zero based indexing version: */

static inline unsigned eytzinger0_child(unsigned i, unsigned child)
{
	EBUG_ON(child > 1);

	return (i << 1) + 1 + child;
}

static inline unsigned eytzinger0_left_child(unsigned i)
{
	return eytzinger0_child(i, 0);
}

static inline unsigned eytzinger0_right_child(unsigned i)
{
	return eytzinger0_child(i, 1);
}

static inline unsigned eytzinger0_first(unsigned size)
{
	return eytzinger1_first(size + 1) - 1;
}

static inline unsigned eytzinger0_last(unsigned size)
{
	return eytzinger1_last(size + 1) - 1;
}

static inline unsigned eytzinger0_next(unsigned i, unsigned size)
{
	return eytzinger1_next(i + 1, size + 1) - 1;
}

static inline unsigned eytzinger0_prev(unsigned i, unsigned size)
{
	return eytzinger1_prev(i + 1, size + 1) - 1;
}

static inline unsigned eytzinger0_extra(unsigned size)
{
	return eytzinger1_extra(size + 1);
}

static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,
					       unsigned extra)
{
	return __eytzinger1_to_inorder(i + 1, size + 1, extra) - 1;
}

static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,
					       unsigned extra)
{
	return __inorder_to_eytzinger1(i + 1, size + 1, extra) - 1;
}

static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)
{
	return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));
}

static inline unsigned inorder_to_eytzinger0(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);

/* 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)
{
	unsigned i, n = 0;

	if (!nr)
		return -1;

	do {
		i = n;
		n = eytzinger0_child(i, cmp(search, base + i * size, size) >= 0);
	} while (n < nr);

	if (n & 1) {
		/* @i was greater than @search, return previous node: */

		if (i == eytzinger0_first(nr))
			return -1;

		return eytzinger0_prev(i, nr);
	} else {
		return i;
	}
}

static inline size_t eytzinger0_find(void *base, size_t nr, size_t size,
				     eytzinger_cmp_fn cmp, const void *search)
{
	size_t i = 0;
	int res;

	while (i < nr &&
	       (res = cmp(search, base + i * size, size)))
		i = eytzinger0_child(i, res > 0);

	return 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));

#endif /* _EYTZINGER_H */