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