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 #ifdef EYTZINGER_DEBUG
9 #define EYTZINGER_BUG_ON(cond) BUG_ON(cond)
10 #else
11 #define EYTZINGER_BUG_ON(cond)
12 #endif
13
14 /*
15 * Traversal for trees in eytzinger layout - a full binary tree layed out in an
16 * array.
17 *
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.
23 *
24 * Two variants are provided, for one based indexing and zero based indexing.
25 *
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.
30 */
31
32 static inline unsigned eytzinger1_child(unsigned i, unsigned child)
33 {
34 EYTZINGER_BUG_ON(child > 1);
35
36 return (i << 1) + child;
37 }
38
39 static inline unsigned eytzinger1_left_child(unsigned i)
40 {
41 return eytzinger1_child(i, 0);
42 }
43
44 static inline unsigned eytzinger1_right_child(unsigned i)
45 {
46 return eytzinger1_child(i, 1);
47 }
48
49 static inline unsigned eytzinger1_first(unsigned size)
50 {
51 return size ? rounddown_pow_of_two(size) : 0;
52 }
53
54 static inline unsigned eytzinger1_last(unsigned size)
55 {
56 return rounddown_pow_of_two(size + 1) - 1;
57 }
58
59 /*
60 * eytzinger1_next() and eytzinger1_prev() have the nice properties that
61 *
62 * eytzinger1_next(0) == eytzinger1_first())
63 * eytzinger1_prev(0) == eytzinger1_last())
64 *
65 * eytzinger1_prev(eytzinger1_first()) == 0
66 * eytzinger1_next(eytzinger1_last()) == 0
67 */
68
69 static inline unsigned eytzinger1_next(unsigned i, unsigned size)
70 {
71 EYTZINGER_BUG_ON(i > size);
72
73 if (eytzinger1_right_child(i) <= size) {
74 i = eytzinger1_right_child(i);
75
76 i <<= __fls(size + 1) - __fls(i);
77 i >>= i > size;
78 } else {
79 i >>= ffz(i) + 1;
80 }
81
82 return i;
83 }
84
85 static inline unsigned eytzinger1_prev(unsigned i, unsigned size)
86 {
87 EYTZINGER_BUG_ON(i > size);
88
89 if (eytzinger1_left_child(i) <= size) {
90 i = eytzinger1_left_child(i) + 1;
91
92 i <<= __fls(size + 1) - __fls(i);
93 i -= 1;
94 i >>= i > size;
95 } else {
96 i >>= __ffs(i) + 1;
97 }
98
99 return i;
100 }
101
102 static inline unsigned eytzinger1_extra(unsigned size)
103 {
104 return size
105 ? (size + 1 - rounddown_pow_of_two(size)) << 1
106 : 0;
107 }
108
109 static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,
110 unsigned extra)
111 {
112 unsigned b = __fls(i);
113 unsigned shift = __fls(size) - b;
114 int s;
115
116 EYTZINGER_BUG_ON(!i || i > size);
117
118 i ^= 1U << b;
119 i <<= 1;
120 i |= 1;
121 i <<= shift;
122
123 /*
124 * sign bit trick:
125 *
126 * if (i > extra)
127 * i -= (i - extra) >> 1;
128 */
129 s = extra - i;
130 i += (s >> 1) & (s >> 31);
131
132 return i;
133 }
134
135 static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,
136 unsigned extra)
137 {
138 unsigned shift;
139 int s;
140
141 EYTZINGER_BUG_ON(!i || i > size);
142
143 /*
144 * sign bit trick:
145 *
146 * if (i > extra)
147 * i += i - extra;
148 */
149 s = extra - i;
150 i -= s & (s >> 31);
151
152 shift = __ffs(i);
153
154 i >>= shift + 1;
155 i |= 1U << (__fls(size) - shift);
156
157 return i;
158 }
159
160 static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)
161 {
162 return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));
163 }
164
165 static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)
166 {
167 return __inorder_to_eytzinger1(i, size, eytzinger1_extra(size));
168 }
169
170 #define eytzinger1_for_each(_i, _size) \
171 for (unsigned (_i) = eytzinger1_first((_size)); \
172 (_i) != 0; \
173 (_i) = eytzinger1_next((_i), (_size)))
174
175 /* Zero based indexing version: */
176
177 static inline unsigned eytzinger0_child(unsigned i, unsigned child)
178 {
179 EYTZINGER_BUG_ON(child > 1);
180
181 return (i << 1) + 1 + child;
182 }
183
184 static inline unsigned eytzinger0_left_child(unsigned i)
185 {
186 return eytzinger0_child(i, 0);
187 }
188
189 static inline unsigned eytzinger0_right_child(unsigned i)
190 {
191 return eytzinger0_child(i, 1);
192 }
193
194 static inline unsigned eytzinger0_first(unsigned size)
195 {
196 return eytzinger1_first(size) - 1;
197 }
198
199 static inline unsigned eytzinger0_last(unsigned size)
200 {
201 return eytzinger1_last(size) - 1;
202 }
203
204 static inline unsigned eytzinger0_next(unsigned i, unsigned size)
205 {
206 return eytzinger1_next(i + 1, size) - 1;
207 }
208
209 static inline unsigned eytzinger0_prev(unsigned i, unsigned size)
210 {
211 return eytzinger1_prev(i + 1, size) - 1;
212 }
213
214 static inline unsigned eytzinger0_extra(unsigned size)
215 {
216 return eytzinger1_extra(size);
217 }
218
219 static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,
220 unsigned extra)
221 {
222 return __eytzinger1_to_inorder(i + 1, size, extra) - 1;
223 }
224
225 static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,
226 unsigned extra)
227 {
228 return __inorder_to_eytzinger1(i + 1, size, extra) - 1;
229 }
230
231 static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)
232 {
233 return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));
234 }
235
236 static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)
237 {
238 return __inorder_to_eytzinger0(i, size, eytzinger0_extra(size));
239 }
240
241 #define eytzinger0_for_each(_i, _size) \
242 for (unsigned (_i) = eytzinger0_first((_size)); \
243 (_i) != -1; \
244 (_i) = eytzinger0_next((_i), (_size)))
245
246 /* return greatest node <= @search, or -1 if not found */
247 static inline int eytzinger0_find_le(void *base, size_t nr, size_t size,
248 cmp_func_t cmp, const void *search)
249 {
250 unsigned i, n = 0;
251
252 if (!nr)
253 return -1;
254
255 do {
256 i = n;
257 n = eytzinger0_child(i, cmp(base + i * size, search) <= 0);
258 } while (n < nr);
259
260 if (n & 1) {
261 /*
262 * @i was greater than @search, return previous node:
263 *
264 * if @i was leftmost/smallest element,
265 * eytzinger0_prev(eytzinger0_first())) returns -1, as expected
266 */
267 return eytzinger0_prev(i, nr);
268 } else {
269 return i;
270 }
271 }
272
273 static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size,
274 cmp_func_t cmp, const void *search)
275 {
276 ssize_t idx = eytzinger0_find_le(base, nr, size, cmp, search);
277
278 /*
279 * if eytitzinger0_find_le() returned -1 - no element was <= search - we
280 * want to return the first element; next/prev identities mean this work
281 * as expected
282 *
283 * similarly if find_le() returns last element, we should return -1;
284 * identities mean this all works out:
285 */
286 return eytzinger0_next(idx, nr);
287 }
288
289 static inline int eytzinger0_find_ge(void *base, size_t nr, size_t size,
290 cmp_func_t cmp, const void *search)
291 {
292 ssize_t idx = eytzinger0_find_le(base, nr, size, cmp, search);
293
294 if (idx < nr && !cmp(base + idx * size, search))
295 return idx;
296
297 return eytzinger0_next(idx, nr);
298 }
299
300 #define eytzinger0_find(base, nr, size, _cmp, search) \
301 ({ \
302 void *_base = (base); \
303 const void *_search = (search); \
304 size_t _nr = (nr); \
305 size_t _size = (size); \
306 size_t _i = 0; \
307 int _res; \
308 \
309 while (_i < _nr && \
310 (_res = _cmp(_search, _base + _i * _size))) \
311 _i = eytzinger0_child(_i, _res > 0); \
312 _i; \
313 })
314
315 void eytzinger0_sort_r(void *, size_t, size_t,
316 cmp_r_func_t, swap_r_func_t, const void *);
317 void eytzinger0_sort(void *, size_t, size_t, cmp_func_t, swap_func_t);
318
319 #endif /* _EYTZINGER_H */
320
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.