1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef _LINUX_EYTZINGER_H
3 #define _LINUX_EYTZINGER_H
5 #include <linux/bitops.h>
6 #include <linux/log2.h>
9 #define EYTZINGER_BUG_ON(cond) BUG_ON(cond)
11 #define EYTZINGER_BUG_ON(cond)
15 * Traversal for trees in eytzinger layout - a full binary tree layed out in an
18 * Consider using an eytzinger tree any time you would otherwise be doing binary
19 * search over an array. Binary search is a worst case scenario for branch
20 * prediction and prefetching, but in an eytzinger tree every node's children
21 * are adjacent in memory, thus we can prefetch children before knowing the
22 * result of the comparison, assuming multiple nodes fit on a cacheline.
24 * Two variants are provided, for one based indexing and zero based indexing.
26 * Zero based indexing is more convenient, but one based indexing has better
27 * alignment and thus better performance because each new level of the tree
28 * starts at a power of two, and thus if element 0 was cacheline aligned, each
29 * new level will be as well.
32 static inline unsigned eytzinger1_child(unsigned i, unsigned child)
34 EYTZINGER_BUG_ON(child > 1);
36 return (i << 1) + child;
39 static inline unsigned eytzinger1_left_child(unsigned i)
41 return eytzinger1_child(i, 0);
44 static inline unsigned eytzinger1_right_child(unsigned i)
46 return eytzinger1_child(i, 1);
49 static inline unsigned eytzinger1_first(unsigned size)
51 return rounddown_pow_of_two(size);
54 static inline unsigned eytzinger1_last(unsigned size)
56 return rounddown_pow_of_two(size + 1) - 1;
60 * eytzinger1_next() and eytzinger1_prev() have the nice properties that
62 * eytzinger1_next(0) == eytzinger1_first())
63 * eytzinger1_prev(0) == eytzinger1_last())
65 * eytzinger1_prev(eytzinger1_first()) == 0
66 * eytzinger1_next(eytzinger1_last()) == 0
69 static inline unsigned eytzinger1_next(unsigned i, unsigned size)
71 EYTZINGER_BUG_ON(i > size);
73 if (eytzinger1_right_child(i) <= size) {
74 i = eytzinger1_right_child(i);
76 i <<= __fls(size + 1) - __fls(i);
85 static inline unsigned eytzinger1_prev(unsigned i, unsigned size)
87 EYTZINGER_BUG_ON(i > size);
89 if (eytzinger1_left_child(i) <= size) {
90 i = eytzinger1_left_child(i) + 1;
92 i <<= __fls(size + 1) - __fls(i);
102 static inline unsigned eytzinger1_extra(unsigned size)
104 return (size + 1 - rounddown_pow_of_two(size)) << 1;
107 static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,
110 unsigned b = __fls(i);
111 unsigned shift = __fls(size) - b;
114 EYTZINGER_BUG_ON(!i || i > size);
125 * i -= (i - extra) >> 1;
128 i += (s >> 1) & (s >> 31);
133 static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,
139 EYTZINGER_BUG_ON(!i || i > size);
153 i |= 1U << (__fls(size) - shift);
158 static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)
160 return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));
163 static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)
165 return __inorder_to_eytzinger1(i, size, eytzinger1_extra(size));
168 #define eytzinger1_for_each(_i, _size) \
169 for (unsigned (_i) = eytzinger1_first((_size)); \
171 (_i) = eytzinger1_next((_i), (_size)))
173 /* Zero based indexing version: */
175 static inline unsigned eytzinger0_child(unsigned i, unsigned child)
177 EYTZINGER_BUG_ON(child > 1);
179 return (i << 1) + 1 + child;
182 static inline unsigned eytzinger0_left_child(unsigned i)
184 return eytzinger0_child(i, 0);
187 static inline unsigned eytzinger0_right_child(unsigned i)
189 return eytzinger0_child(i, 1);
192 static inline unsigned eytzinger0_first(unsigned size)
194 return eytzinger1_first(size) - 1;
197 static inline unsigned eytzinger0_last(unsigned size)
199 return eytzinger1_last(size) - 1;
202 static inline unsigned eytzinger0_next(unsigned i, unsigned size)
204 return eytzinger1_next(i + 1, size) - 1;
207 static inline unsigned eytzinger0_prev(unsigned i, unsigned size)
209 return eytzinger1_prev(i + 1, size) - 1;
212 static inline unsigned eytzinger0_extra(unsigned size)
214 return eytzinger1_extra(size);
217 static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,
220 return __eytzinger1_to_inorder(i + 1, size, extra) - 1;
223 static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,
226 return __inorder_to_eytzinger1(i + 1, size, extra) - 1;
229 static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)
231 return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));
234 static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)
236 return __inorder_to_eytzinger0(i, size, eytzinger0_extra(size));
239 #define eytzinger0_for_each(_i, _size) \
240 for (unsigned (_i) = eytzinger0_first((_size)); \
242 (_i) = eytzinger0_next((_i), (_size)))
244 /* return greatest node <= @search, or -1 if not found */
245 static inline ssize_t eytzinger0_find_le(void *base, size_t nr, size_t size,
246 cmp_func_t cmp, const void *search)
255 n = eytzinger0_child(i, cmp(search, base + i * size) >= 0);
259 /* @i was greater than @search, return previous node: */
261 if (i == eytzinger0_first(nr))
264 return eytzinger0_prev(i, nr);
270 #define eytzinger0_find(base, nr, size, _cmp, search) \
272 void *_base = (base); \
273 const void *_search = (search); \
275 size_t _size = (size); \
280 (_res = _cmp(_search, _base + _i * _size, _size))) \
281 _i = eytzinger0_child(_i, _res > 0); \
285 void eytzinger0_sort_r(void *, size_t, size_t,
286 cmp_r_func_t, swap_r_func_t, const void *);
287 void eytzinger0_sort(void *, size_t, size_t, cmp_func_t, swap_func_t);
289 #endif /* _LINUX_EYTZINGER_H */