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

   1 #ifndef _EYTZINGER_H
   2 #define _EYTZINGER_H
   3
   4 #include <linux/bitops.h>
   5 #include <linux/log2.h>
   6
   7 #include "util.h"
   8
   9 /*
  10  * Traversal for trees in eytzinger layout - a full binary tree layed out in an
  11  * array
  12  *
  13  * We used one based indexing, not zero based: with one based indexing, each
  14  * level of the tree starts at a power of two - leading to better alignment -
  15  * and it's what you want for implementing next/prev and to/from inorder.
  16  *
  17  * To/from inorder also uses 1 based indexing.
  18  *
  19  * Size parameter is treated as if we were using 0 based indexing, however:
  20  * valid nodes, and inorder indices, are in the range [1..size)
  21  */
  22
  23 static inline unsigned eytzinger_child(unsigned j, unsigned child)
  24 {
  25         EBUG_ON(child > 1);
  26
  27         return (j << 1) + child;
  28 }
  29
  30 static inline unsigned eytzinger_left_child(unsigned j)
  31 {
  32         return eytzinger_child(j, 0);
  33 }
  34
  35 static inline unsigned eytzinger_right_child(unsigned j)
  36 {
  37         return eytzinger_child(j, 1);
  38 }
  39
  40 static inline unsigned eytzinger_first(unsigned size)
  41 {
  42         return rounddown_pow_of_two(size - 1);
  43 }
  44
  45 static inline unsigned eytzinger_last(unsigned size)
  46 {
  47         return rounddown_pow_of_two(size) - 1;
  48 }
  49
  50 /*
  51  * eytzinger_next() and eytzinger_prev() have the nice properties that
  52  *
  53  * eytzinger_next(0) == eytzinger_first())
  54  * eytzinger_prev(0) == eytzinger_last())
  55  *
  56  * eytzinger_prev(eytzinger_first()) == 0
  57  * eytzinger_next(eytzinger_last()) == 0
  58  */
  59
  60 static inline unsigned eytzinger_next(unsigned j, unsigned size)
  61 {
  62         EBUG_ON(j >= size);
  63
  64         if (eytzinger_right_child(j) < size) {
  65                 j = eytzinger_right_child(j);
  66
  67                 j <<= __fls(size) - __fls(j);
  68                 j >>= j >= size;
  69         } else {
  70                 j >>= ffz(j) + 1;
  71         }
  72
  73         return j;
  74 }
  75
  76 static inline unsigned eytzinger_prev(unsigned j, unsigned size)
  77 {
  78         EBUG_ON(j >= size);
  79
  80         if (eytzinger_left_child(j) < size) {
  81                 j = eytzinger_left_child(j);
  82
  83                 j <<= __fls(size) - __fls(j);
  84                 j -= 1;
  85                 j >>= j >= size;
  86         } else {
  87                 j >>= __ffs(j) + 1;
  88         }
  89
  90         return j;
  91 }
  92
  93 static inline unsigned eytzinger_extra(unsigned size)
  94 {
  95         return (size - rounddown_pow_of_two(size - 1)) << 1;
  96 }
  97
  98 static inline unsigned __eytzinger_to_inorder(unsigned j, unsigned size,
  99                                               unsigned extra)
 100 {
 101         unsigned b = __fls(j);
 102         unsigned shift = __fls(size - 1) - b;
 103         int s;
 104
 105         EBUG_ON(!j || j >= size);
 106
 107         j  ^= 1U << b;
 108         j <<= 1;
 109         j  |= 1;
 110         j <<= shift;
 111
 112         /*
 113          * sign bit trick:
 114          *
 115          * if (j > extra)
 116          *      j -= (j - extra) >> 1;
 117          */
 118         s = extra - j;
 119         j += (s >> 1) & (s >> 31);
 120
 121         return j;
 122 }
 123
 124 static inline unsigned __inorder_to_eytzinger(unsigned j, unsigned size,
 125                                               unsigned extra)
 126 {
 127         unsigned shift;
 128         int s;
 129
 130         EBUG_ON(!j || j >= size);
 131
 132         /*
 133          * sign bit trick:
 134          *
 135          * if (j > extra)
 136          *      j += j - extra;
 137          */
 138         s = extra - j;
 139         j -= s & (s >> 31);
 140
 141         shift = __ffs(j);
 142
 143         j >>= shift + 1;
 144         j  |= 1U << (__fls(size - 1) - shift);
 145
 146         return j;
 147 }
 148
 149 static inline unsigned eytzinger_to_inorder(unsigned j, unsigned size)
 150 {
 151         return __eytzinger_to_inorder(j, size, eytzinger_extra(size));
 152 }
 153
 154 static inline unsigned inorder_to_eytzinger(unsigned j, unsigned size)
 155 {
 156         return __inorder_to_eytzinger(j, size, eytzinger_extra(size));
 157 }
 158
 159 #define eytzinger_for_each(_i, _size)                   \
 160         for ((_i) = eytzinger_first((_size));           \
 161              (_i) != 0;                                 \
 162              (_i) = eytzinger_next((_i), (_size)))
 163
 164 #if 0
 165 void eytzinger_test(void)
 166 {
 167         unsigned i, j, size;
 168
 169         for (size = 2;
 170              size < 65536000;
 171              size++) {
 172                 if (!(size % 4096))
 173                         printk(KERN_INFO "tree size %u\n", size);
 174
 175                 assert(eytzinger_prev(0, size) == eytzinger_last(size));
 176                 assert(eytzinger_next(0, size) == eytzinger_first(size));
 177
 178                 assert(eytzinger_prev(eytzinger_first(size), size) == 0);
 179                 assert(eytzinger_next(eytzinger_last(size), size) == 0);
 180
 181                 eytzinger_for_each(j, size) {
 182                         assert(from_inorder(i, size) == j);
 183                         assert(to_inorder(j, size) == i);
 184
 185                         if (j != eytzinger_last(size)) {
 186                                 unsigned next = eytzinger_next(j, size);
 187
 188                                 assert(eytzinger_prev(next, size) == j);
 189                         }
 190                 }
 191         }
 192
 193 }
 194 #endif
 195
 196 #endif /* _EYTZINGER_H */