1 /* SPDX-License-Identifier: GPL-2.0 */
5 #include <linux/bitops.h>
6 #include <linux/log2.h>
11 * Traversal for trees in eytzinger layout - a full binary tree layed out in an
16 * One based indexing version:
18 * With one based indexing each level of the tree starts at a power of two -
19 * good for cacheline alignment:
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
26 static inline unsigned eytzinger1_child(unsigned i, unsigned child)
30 return (i << 1) + child;
33 static inline unsigned eytzinger1_left_child(unsigned i)
35 return eytzinger1_child(i, 0);
38 static inline unsigned eytzinger1_right_child(unsigned i)
40 return eytzinger1_child(i, 1);
43 static inline unsigned eytzinger1_first(unsigned size)
45 return rounddown_pow_of_two(size - 1);
48 static inline unsigned eytzinger1_last(unsigned size)
50 return rounddown_pow_of_two(size) - 1;
54 * eytzinger1_next() and eytzinger1_prev() have the nice properties that
56 * eytzinger1_next(0) == eytzinger1_first())
57 * eytzinger1_prev(0) == eytzinger1_last())
59 * eytzinger1_prev(eytzinger1_first()) == 0
60 * eytzinger1_next(eytzinger1_last()) == 0
63 static inline unsigned eytzinger1_next(unsigned i, unsigned size)
67 if (eytzinger1_right_child(i) < size) {
68 i = eytzinger1_right_child(i);
70 i <<= __fls(size) - __fls(i);
79 static inline unsigned eytzinger1_prev(unsigned i, unsigned size)
83 if (eytzinger1_left_child(i) < size) {
84 i = eytzinger1_left_child(i) + 1;
86 i <<= __fls(size) - __fls(i);
96 static inline unsigned eytzinger1_extra(unsigned size)
98 return (size - rounddown_pow_of_two(size - 1)) << 1;
101 static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,
104 unsigned b = __fls(i);
105 unsigned shift = __fls(size - 1) - b;
108 EBUG_ON(!i || i >= size);
119 * i -= (i - extra) >> 1;
122 i += (s >> 1) & (s >> 31);
127 static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,
133 EBUG_ON(!i || i >= size);
147 i |= 1U << (__fls(size - 1) - shift);
152 static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)
154 return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));
157 static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)
159 return __inorder_to_eytzinger1(i, size, eytzinger1_extra(size));
162 #define eytzinger1_for_each(_i, _size) \
163 for ((_i) = eytzinger1_first((_size)); \
165 (_i) = eytzinger1_next((_i), (_size)))
167 /* Zero based indexing version: */
169 static inline unsigned eytzinger0_child(unsigned i, unsigned child)
173 return (i << 1) + 1 + child;
176 static inline unsigned eytzinger0_left_child(unsigned i)
178 return eytzinger0_child(i, 0);
181 static inline unsigned eytzinger0_right_child(unsigned i)
183 return eytzinger0_child(i, 1);
186 static inline unsigned eytzinger0_first(unsigned size)
188 return eytzinger1_first(size + 1) - 1;
191 static inline unsigned eytzinger0_last(unsigned size)
193 return eytzinger1_last(size + 1) - 1;
196 static inline unsigned eytzinger0_next(unsigned i, unsigned size)
198 return eytzinger1_next(i + 1, size + 1) - 1;
201 static inline unsigned eytzinger0_prev(unsigned i, unsigned size)
203 return eytzinger1_prev(i + 1, size + 1) - 1;
206 static inline unsigned eytzinger0_extra(unsigned size)
208 return eytzinger1_extra(size + 1);
211 static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,
214 return __eytzinger1_to_inorder(i + 1, size + 1, extra) - 1;
217 static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,
220 return __inorder_to_eytzinger1(i + 1, size + 1, extra) - 1;
223 static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)
225 return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));
228 static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)
230 return __inorder_to_eytzinger0(i, size, eytzinger0_extra(size));
233 #define eytzinger0_for_each(_i, _size) \
234 for ((_i) = eytzinger0_first((_size)); \
236 (_i) = eytzinger0_next((_i), (_size)))
238 typedef int (*eytzinger_cmp_fn)(const void *l, const void *r, size_t size);
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)
251 n = eytzinger0_child(i, cmp(search, base + i * size, size) >= 0);
255 /* @i was greater than @search, return previous node: */
257 if (i == eytzinger0_first(nr))
260 return eytzinger0_prev(i, nr);
266 #define eytzinger0_find(base, nr, size, _cmp, search) \
268 void *_base = (base); \
269 void *_search = (search); \
271 size_t _size = (size); \
276 (_res = _cmp(_search, _base + _i * _size, _size))) \
277 _i = eytzinger0_child(_i, _res > 0); \
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));
285 #endif /* _EYTZINGER_H */