Rename from bcache-tools to bcachefs-tools

1 files changed, 196 insertions, 0 deletions

diff --git a/libbcachefs/eytzinger.h b/libbcachefs/eytzinger.h
new file mode 100644
index 00000000..13d54e5e
--- /dev/null
+++ b/libbcachefs/eytzinger.h
@@ -0,0 +1,196 @@
+#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
+ *
+ * We used one based indexing, not zero based: with one based indexing, each
+ * level of the tree starts at a power of two - leading to better alignment -
+ * and it's what you want for implementing next/prev and to/from inorder.
+ *
+ * To/from inorder also uses 1 based indexing.
+ *
+ * Size parameter is treated as if we were using 0 based indexing, however:
+ * valid nodes, and inorder indices, are in the range [1..size)
+ */
+
+static inline unsigned eytzinger_child(unsigned j, unsigned child)
+{
+	EBUG_ON(child > 1);
+
+	return (j << 1) + child;
+}
+
+static inline unsigned eytzinger_left_child(unsigned j)
+{
+	return eytzinger_child(j, 0);
+}
+
+static inline unsigned eytzinger_right_child(unsigned j)
+{
+	return eytzinger_child(j, 1);
+}
+
+static inline unsigned eytzinger_first(unsigned size)
+{
+	return rounddown_pow_of_two(size - 1);
+}
+
+static inline unsigned eytzinger_last(unsigned size)
+{
+	return rounddown_pow_of_two(size) - 1;
+}
+
+/*
+ * eytzinger_next() and eytzinger_prev() have the nice properties that
+ *
+ * eytzinger_next(0) == eytzinger_first())
+ * eytzinger_prev(0) == eytzinger_last())
+ *
+ * eytzinger_prev(eytzinger_first()) == 0
+ * eytzinger_next(eytzinger_last()) == 0
+ */
+
+static inline unsigned eytzinger_next(unsigned j, unsigned size)
+{
+	EBUG_ON(j >= size);
+
+	if (eytzinger_right_child(j) < size) {
+		j = eytzinger_right_child(j);
+
+		j <<= __fls(size) - __fls(j);
+		j >>= j >= size;
+	} else {
+		j >>= ffz(j) + 1;
+	}
+
+	return j;
+}
+
+static inline unsigned eytzinger_prev(unsigned j, unsigned size)
+{
+	EBUG_ON(j >= size);
+
+	if (eytzinger_left_child(j) < size) {
+		j = eytzinger_left_child(j);
+
+		j <<= __fls(size) - __fls(j);
+		j -= 1;
+		j >>= j >= size;
+	} else {
+		j >>= __ffs(j) + 1;
+	}
+
+	return j;
+}
+
+static inline unsigned eytzinger_extra(unsigned size)
+{
+	return (size - rounddown_pow_of_two(size - 1)) << 1;
+}
+
+static inline unsigned __eytzinger_to_inorder(unsigned j, unsigned size,
+					      unsigned extra)
+{
+	unsigned b = __fls(j);
+	unsigned shift = __fls(size - 1) - b;
+	int s;
+
+	EBUG_ON(!j || j >= size);
+
+	j  ^= 1U << b;
+	j <<= 1;
+	j  |= 1;
+	j <<= shift;
+
+	/*
+	 * sign bit trick:
+	 *
+	 * if (j > extra)
+	 *	j -= (j - extra) >> 1;
+	 */
+	s = extra - j;
+	j += (s >> 1) & (s >> 31);
+
+	return j;
+}
+
+static inline unsigned __inorder_to_eytzinger(unsigned j, unsigned size,
+					      unsigned extra)
+{
+	unsigned shift;
+	int s;
+
+	EBUG_ON(!j || j >= size);
+
+	/*
+	 * sign bit trick:
+	 *
+	 * if (j > extra)
+	 *	j += j - extra;
+	 */
+	s = extra - j;
+	j -= s & (s >> 31);
+
+	shift = __ffs(j);
+
+	j >>= shift + 1;
+	j  |= 1U << (__fls(size - 1) - shift);
+
+	return j;
+}
+
+static inline unsigned eytzinger_to_inorder(unsigned j, unsigned size)
+{
+	return __eytzinger_to_inorder(j, size, eytzinger_extra(size));
+}
+
+static inline unsigned inorder_to_eytzinger(unsigned j, unsigned size)
+{
+	return __inorder_to_eytzinger(j, size, eytzinger_extra(size));
+}
+
+#define eytzinger_for_each(_i, _size)			\
+	for ((_i) = eytzinger_first((_size));		\
+	     (_i) != 0;					\
+	     (_i) = eytzinger_next((_i), (_size)))
+
+#if 0
+void eytzinger_test(void)
+{
+	unsigned i, j, size;
+
+	for (size = 2;
+	     size < 65536000;
+	     size++) {
+		if (!(size % 4096))
+			printk(KERN_INFO "tree size %u\n", size);
+
+		assert(eytzinger_prev(0, size) == eytzinger_last(size));
+		assert(eytzinger_next(0, size) == eytzinger_first(size));
+
+		assert(eytzinger_prev(eytzinger_first(size), size) == 0);
+		assert(eytzinger_next(eytzinger_last(size), size) == 0);
+
+		eytzinger_for_each(j, size) {
+			assert(from_inorder(i, size) == j);
+			assert(to_inorder(j, size) == i);
+
+			if (j != eytzinger_last(size)) {
+				unsigned next = eytzinger_next(j, size);
+
+				assert(eytzinger_prev(next, size) == j);
+			}
+		}
+	}
+
+}
+#endif
+
+#endif /* _EYTZINGER_H */