Update upstream source from tag 'v1.6.3'

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

diff --git a/libbcachefs/eytzinger.h b/include/linux/eytzinger.h
similarity index 73%
rename from libbcachefs/eytzinger.h
rename to include/linux/eytzinger.h
index 05429c9631cdad6eced17ff7638cd61651e12bf5..1031501030449d83482a1f4f2ebdb4153f69cd82 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:
@@ -156,7 +166,7 @@ static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)
 }
 
 #define eytzinger1_for_each(_i, _size)                 \
-       for ((_i) = eytzinger1_first((_size));          \
+       for (unsigned (_i) = eytzinger1_first((_size)); \
             (_i) != 0;                                 \
             (_i) = eytzinger1_next((_i), (_size)))
 
@@ -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;
 }
@@ -227,15 +237,13 @@ static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)
 }
 
 #define eytzinger0_for_each(_i, _size)                 \
-       for ((_i) = eytzinger0_first((_size));          \
+       for (unsigned (_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)
+                                        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) {
@@ -261,21 +269,21 @@ static inline ssize_t eytzinger0_find_le(void *base, size_t nr, size_t size,
 
 #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;                                            \
+       void *_base             = (base);                               \
+       const 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)))       \
+              (_res = _cmp(_search, _base + _i * _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));
+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 */