git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/eytzinger.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 #ifndef _EYTZINGER_H
   3 #define _EYTZINGER_H
   4
   5 #include <linux/bitops.h>
   6 #include <linux/log2.h>
   7
   8 #include "util.h"
   9
  10 /*
  11  * Traversal for trees in eytzinger layout - a full binary tree layed out in an
  12  * array
  13  */
  14
  15 /*
  16  * One based indexing version:
  17  *
  18  * With one based indexing each level of the tree starts at a power of two -
  19  * good for cacheline alignment:
  20  *
  21  * Size parameter is treated as if we were using 0 based indexing, however:
  22  * valid nodes, and inorder indices, are in the range [1..size) - that is, there
  23  * are actually size - 1 elements
  24  */
  25
  26 static inline unsigned eytzinger1_child(unsigned i, unsigned child)
  27 {
  28         EBUG_ON(child > 1);
  29
  30         return (i << 1) + child;
  31 }
  32
  33 static inline unsigned eytzinger1_left_child(unsigned i)
  34 {
  35         return eytzinger1_child(i, 0);
  36 }
  37
  38 static inline unsigned eytzinger1_right_child(unsigned i)
  39 {
  40         return eytzinger1_child(i, 1);
  41 }
  42
  43 static inline unsigned eytzinger1_first(unsigned size)
  44 {
  45         return rounddown_pow_of_two(size - 1);
  46 }
  47
  48 static inline unsigned eytzinger1_last(unsigned size)
  49 {
  50         return rounddown_pow_of_two(size) - 1;
  51 }
  52
  53 /*
  54  * eytzinger1_next() and eytzinger1_prev() have the nice properties that
  55  *
  56  * eytzinger1_next(0) == eytzinger1_first())
  57  * eytzinger1_prev(0) == eytzinger1_last())
  58  *
  59  * eytzinger1_prev(eytzinger1_first()) == 0
  60  * eytzinger1_next(eytzinger1_last()) == 0
  61  */
  62
  63 static inline unsigned eytzinger1_next(unsigned i, unsigned size)
  64 {
  65         EBUG_ON(i >= size);
  66
  67         if (eytzinger1_right_child(i) < size) {
  68                 i = eytzinger1_right_child(i);
  69
  70                 i <<= __fls(size) - __fls(i);
  71                 i >>= i >= size;
  72         } else {
  73                 i >>= ffz(i) + 1;
  74         }
  75
  76         return i;
  77 }
  78
  79 static inline unsigned eytzinger1_prev(unsigned i, unsigned size)
  80 {
  81         EBUG_ON(i >= size);
  82
  83         if (eytzinger1_left_child(i) < size) {
  84                 i = eytzinger1_left_child(i) + 1;
  85
  86                 i <<= __fls(size) - __fls(i);
  87                 i -= 1;
  88                 i >>= i >= size;
  89         } else {
  90                 i >>= __ffs(i) + 1;
  91         }
  92
  93         return i;
  94 }
  95
  96 static inline unsigned eytzinger1_extra(unsigned size)
  97 {
  98         return (size - rounddown_pow_of_two(size - 1)) << 1;
  99 }
 100
 101 static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,
 102                                               unsigned extra)
 103 {
 104         unsigned b = __fls(i);
 105         unsigned shift = __fls(size - 1) - b;
 106         int s;
 107
 108         EBUG_ON(!i || i >= size);
 109
 110         i  ^= 1U << b;
 111         i <<= 1;
 112         i  |= 1;
 113         i <<= shift;
 114
 115         /*
 116          * sign bit trick:
 117          *
 118          * if (i > extra)
 119          *      i -= (i - extra) >> 1;
 120          */
 121         s = extra - i;
 122         i += (s >> 1) & (s >> 31);
 123
 124         return i;
 125 }
 126
 127 static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,
 128                                                unsigned extra)
 129 {
 130         unsigned shift;
 131         int s;
 132
 133         EBUG_ON(!i || i >= size);
 134
 135         /*
 136          * sign bit trick:
 137          *
 138          * if (i > extra)
 139          *      i += i - extra;
 140          */
 141         s = extra - i;
 142         i -= s & (s >> 31);
 143
 144         shift = __ffs(i);
 145
 146         i >>= shift + 1;
 147         i  |= 1U << (__fls(size - 1) - shift);
 148
 149         return i;
 150 }
 151
 152 static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)
 153 {
 154         return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));
 155 }
 156
 157 static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)
 158 {
 159         return __inorder_to_eytzinger1(i, size, eytzinger1_extra(size));
 160 }
 161
 162 #define eytzinger1_for_each(_i, _size)                  \
 163         for ((_i) = eytzinger1_first((_size));          \
 164              (_i) != 0;                                 \
 165              (_i) = eytzinger1_next((_i), (_size)))
 166
 167 /* Zero based indexing version: */
 168
 169 static inline unsigned eytzinger0_child(unsigned i, unsigned child)
 170 {
 171         EBUG_ON(child > 1);
 172
 173         return (i << 1) + 1 + child;
 174 }
 175
 176 static inline unsigned eytzinger0_left_child(unsigned i)
 177 {
 178         return eytzinger0_child(i, 0);
 179 }
 180
 181 static inline unsigned eytzinger0_right_child(unsigned i)
 182 {
 183         return eytzinger0_child(i, 1);
 184 }
 185
 186 static inline unsigned eytzinger0_first(unsigned size)
 187 {
 188         return eytzinger1_first(size + 1) - 1;
 189 }
 190
 191 static inline unsigned eytzinger0_last(unsigned size)
 192 {
 193         return eytzinger1_last(size + 1) - 1;
 194 }
 195
 196 static inline unsigned eytzinger0_next(unsigned i, unsigned size)
 197 {
 198         return eytzinger1_next(i + 1, size + 1) - 1;
 199 }
 200
 201 static inline unsigned eytzinger0_prev(unsigned i, unsigned size)
 202 {
 203         return eytzinger1_prev(i + 1, size + 1) - 1;
 204 }
 205
 206 static inline unsigned eytzinger0_extra(unsigned size)
 207 {
 208         return eytzinger1_extra(size + 1);
 209 }
 210
 211 static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,
 212                                                unsigned extra)
 213 {
 214         return __eytzinger1_to_inorder(i + 1, size + 1, extra) - 1;
 215 }
 216
 217 static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,
 218                                                unsigned extra)
 219 {
 220         return __inorder_to_eytzinger1(i + 1, size + 1, extra) - 1;
 221 }
 222
 223 static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)
 224 {
 225         return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));
 226 }
 227
 228 static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)
 229 {
 230         return __inorder_to_eytzinger0(i, size, eytzinger0_extra(size));
 231 }
 232
 233 #define eytzinger0_for_each(_i, _size)                  \
 234         for ((_i) = eytzinger0_first((_size));          \
 235              (_i) != -1;                                \
 236              (_i) = eytzinger0_next((_i), (_size)))
 237
 238 typedef int (*eytzinger_cmp_fn)(const void *l, const void *r, size_t size);
 239
 240 /* return greatest node <= @search, or -1 if not found */
 241 static inline ssize_t eytzinger0_find_le(void *base, size_t nr, size_t size,
 242                                          eytzinger_cmp_fn cmp, const void *search)
 243 {
 244         unsigned i, n = 0;
 245
 246         if (!nr)
 247                 return -1;
 248
 249         do {
 250                 i = n;
 251                 n = eytzinger0_child(i, cmp(search, base + i * size, size) >= 0);
 252         } while (n < nr);
 253
 254         if (n & 1) {
 255                 /* @i was greater than @search, return previous node: */
 256
 257                 if (i == eytzinger0_first(nr))
 258                         return -1;
 259
 260                 return eytzinger0_prev(i, nr);
 261         } else {
 262                 return i;
 263         }
 264 }
 265
 266 #define eytzinger0_find(base, nr, size, _cmp, search)                   \
 267 ({                                                                      \
 268         void *_base     = (base);                                       \
 269         void *_search   = (search);                                     \
 270         size_t _nr      = (nr);                                         \
 271         size_t _size    = (size);                                       \
 272         size_t _i       = 0;                                            \
 273         int _res;                                                       \
 274                                                                         \
 275         while (_i < _nr &&                                              \
 276                (_res = _cmp(_search, _base + _i * _size, _size)))       \
 277                 _i = eytzinger0_child(_i, _res > 0);                    \
 278         _i;                                                             \
 279 })
 280
 281 void eytzinger0_sort(void *, size_t, size_t,
 282                     int (*cmp_func)(const void *, const void *, size_t),
 283                     void (*swap_func)(void *, void *, size_t));
 284
 285 #endif /* _EYTZINGER_H */