Update bcachefs sources to 50847e296b34 bcachefs: Check subvol <-> inode pointers...

[bcachefs-tools-debian] / include / linux / eytzinger.h

diff --git a/libbcachefs/eytzinger.h b/include/linux/eytzinger.h
similarity index 78%
rename from libbcachefs/eytzinger.h
rename to include/linux/eytzinger.h
index b04750dbf870bc78c95ece35d363e3a4c0936b50..9565a5c26cd505584b3872d2b8898dfd2998e982 100644 (file)
--- a/libbcachefs/eytzinger.h
+++ b/include/linux/eytzinger.h
@@ -1,27 +1,37 @@
 /* SPDX-License-Identifier: GPL-2.0 */
-#ifndef _EYTZINGER_H
-#define _EYTZINGER_H
+#ifndef _LINUX_EYTZINGER_H
+#define _LINUX_EYTZINGER_H
 
 #include <linux/bitops.h>
 #include <linux/log2.h>
 
-#include "util.h"
+#ifdef EYTZINGER_DEBUG
+#define EYTZINGER_BUG_ON(cond)         BUG_ON(cond)
+#else
+#define EYTZINGER_BUG_ON(cond)
+#endif
 
 /*
  * Traversal for trees in eytzinger layout - a full binary tree layed out in an
- * array
- */
-
-/*
- * One based indexing version:
+ * array.
  *
- * With one based indexing each level of the tree starts at a power of two -
- * good for cacheline alignment:
+ * Consider using an eytzinger tree any time you would otherwise be doing binary
+ * search over an array. Binary search is a worst case scenario for branch
+ * prediction and prefetching, but in an eytzinger tree every node's children
+ * are adjacent in memory, thus we can prefetch children before knowing the
+ * result of the comparison, assuming multiple nodes fit on a cacheline.
+ *
+ * Two variants are provided, for one based indexing and zero based indexing.
+ *
+ * Zero based indexing is more convenient, but one based indexing has better
+ * alignment and thus better performance because each new level of the tree
+ * starts at a power of two, and thus if element 0 was cacheline aligned, each
+ * new level will be as well.
  */
 
 static inline unsigned eytzinger1_child(unsigned i, unsigned child)
 {
-       EBUG_ON(child > 1);
+       EYTZINGER_BUG_ON(child > 1);
 
        return (i << 1) + child;
 }
@@ -58,7 +68,7 @@ static inline unsigned eytzinger1_last(unsigned size)
 
 static inline unsigned eytzinger1_next(unsigned i, unsigned size)
 {
-       EBUG_ON(i > size);
+       EYTZINGER_BUG_ON(i > size);
 
        if (eytzinger1_right_child(i) <= size) {
                i = eytzinger1_right_child(i);
@@ -74,7 +84,7 @@ static inline unsigned eytzinger1_next(unsigned i, unsigned size)
 
 static inline unsigned eytzinger1_prev(unsigned i, unsigned size)
 {
-       EBUG_ON(i > size);
+       EYTZINGER_BUG_ON(i > size);
 
        if (eytzinger1_left_child(i) <= size) {
                i = eytzinger1_left_child(i) + 1;
@@ -101,7 +111,7 @@ static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,
        unsigned shift = __fls(size) - b;
        int s;
 
-       EBUG_ON(!i || i > size);
+       EYTZINGER_BUG_ON(!i || i > size);
 
        i  ^= 1U << b;
        i <<= 1;
@@ -126,7 +136,7 @@ static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,
        unsigned shift;
        int s;
 
-       EBUG_ON(!i || i > size);
+       EYTZINGER_BUG_ON(!i || i > size);
 
        /*
         * sign bit trick:
@@ -164,7 +174,7 @@ static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)
 
 static inline unsigned eytzinger0_child(unsigned i, unsigned child)
 {
-       EBUG_ON(child > 1);
+       EYTZINGER_BUG_ON(child > 1);
 
        return (i << 1) + 1 + child;
 }
@@ -231,11 +241,9 @@ static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned 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)
+                                        cmp_func_t cmp, const void *search)
 {
        unsigned i, n = 0;
 
@@ -244,7 +252,7 @@ static inline ssize_t eytzinger0_find_le(void *base, size_t nr, size_t size,
 
        do {
                i = n;
-               n = eytzinger0_child(i, cmp(search, base + i * size, size) >= 0);
+               n = eytzinger0_child(i, cmp(search, base + i * size) >= 0);
        } while (n < nr);
 
        if (n & 1) {
@@ -274,8 +282,8 @@ static inline ssize_t eytzinger0_find_le(void *base, size_t nr, size_t size,
        _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));
+void eytzinger0_sort_r(void *, size_t, size_t,
+                      cmp_r_func_t, swap_r_func_t, const void *);
+void eytzinger0_sort(void *, size_t, size_t, cmp_func_t, swap_func_t);
 
-#endif /* _EYTZINGER_H */
+#endif /* _LINUX_EYTZINGER_H */