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:
22 static inline unsigned eytzinger1_child(unsigned i, unsigned child)
26 return (i << 1) + child;
29 static inline unsigned eytzinger1_left_child(unsigned i)
31 return eytzinger1_child(i, 0);
34 static inline unsigned eytzinger1_right_child(unsigned i)
36 return eytzinger1_child(i, 1);
39 static inline unsigned eytzinger1_first(unsigned size)
41 return rounddown_pow_of_two(size);
44 static inline unsigned eytzinger1_last(unsigned size)
46 return rounddown_pow_of_two(size + 1) - 1;
50 * eytzinger1_next() and eytzinger1_prev() have the nice properties that
52 * eytzinger1_next(0) == eytzinger1_first())
53 * eytzinger1_prev(0) == eytzinger1_last())
55 * eytzinger1_prev(eytzinger1_first()) == 0
56 * eytzinger1_next(eytzinger1_last()) == 0
59 static inline unsigned eytzinger1_next(unsigned i, unsigned size)
63 if (eytzinger1_right_child(i) <= size) {
64 i = eytzinger1_right_child(i);
66 i <<= __fls(size + 1) - __fls(i);
75 static inline unsigned eytzinger1_prev(unsigned i, unsigned size)
79 if (eytzinger1_left_child(i) <= size) {
80 i = eytzinger1_left_child(i) + 1;
82 i <<= __fls(size + 1) - __fls(i);
92 static inline unsigned eytzinger1_extra(unsigned size)
94 return (size + 1 - rounddown_pow_of_two(size)) << 1;
97 static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,
100 unsigned b = __fls(i);
101 unsigned shift = __fls(size) - b;
104 EBUG_ON(!i || i > size);
115 * i -= (i - extra) >> 1;
118 i += (s >> 1) & (s >> 31);
123 static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,
129 EBUG_ON(!i || i > size);
143 i |= 1U << (__fls(size) - shift);
148 static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)
150 return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));
153 static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)
155 return __inorder_to_eytzinger1(i, size, eytzinger1_extra(size));
158 #define eytzinger1_for_each(_i, _size) \
159 for ((_i) = eytzinger1_first((_size)); \
161 (_i) = eytzinger1_next((_i), (_size)))
163 /* Zero based indexing version: */
165 static inline unsigned eytzinger0_child(unsigned i, unsigned child)
169 return (i << 1) + 1 + child;
172 static inline unsigned eytzinger0_left_child(unsigned i)
174 return eytzinger0_child(i, 0);
177 static inline unsigned eytzinger0_right_child(unsigned i)
179 return eytzinger0_child(i, 1);
182 static inline unsigned eytzinger0_first(unsigned size)
184 return eytzinger1_first(size) - 1;
187 static inline unsigned eytzinger0_last(unsigned size)
189 return eytzinger1_last(size) - 1;
192 static inline unsigned eytzinger0_next(unsigned i, unsigned size)
194 return eytzinger1_next(i + 1, size) - 1;
197 static inline unsigned eytzinger0_prev(unsigned i, unsigned size)
199 return eytzinger1_prev(i + 1, size) - 1;
202 static inline unsigned eytzinger0_extra(unsigned size)
204 return eytzinger1_extra(size);
207 static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,
210 return __eytzinger1_to_inorder(i + 1, size, extra) - 1;
213 static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,
216 return __inorder_to_eytzinger1(i + 1, size, extra) - 1;
219 static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)
221 return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));
224 static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)
226 return __inorder_to_eytzinger0(i, size, eytzinger0_extra(size));
229 #define eytzinger0_for_each(_i, _size) \
230 for ((_i) = eytzinger0_first((_size)); \
232 (_i) = eytzinger0_next((_i), (_size)))
234 typedef int (*eytzinger_cmp_fn)(const void *l, const void *r, size_t size);
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)
247 n = eytzinger0_child(i, cmp(search, base + i * size, size) >= 0);
251 /* @i was greater than @search, return previous node: */
253 if (i == eytzinger0_first(nr))
256 return eytzinger0_prev(i, nr);
262 #define eytzinger0_find(base, nr, size, _cmp, search) \
264 void *_base = (base); \
265 void *_search = (search); \
267 size_t _size = (size); \
272 (_res = _cmp(_search, _base + _i * _size, _size))) \
273 _i = eytzinger0_child(_i, _res > 0); \
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));
281 #endif /* _EYTZINGER_H */