Commit | Line | Data |
---|---|---|
1c6fdbd8 KO |
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 | #include "util.h" | |
9 | ||
10 | /* | |
11 | * Traversal for trees in eytzinger layout - a full binary tree layed out in an | |
12 | * array | |
13 | */ | |
14 | ||
15 | /* | |
16 | * One based indexing version: | |
17 | * | |
18 | * With one based indexing each level of the tree starts at a power of two - | |
19 | * good for cacheline alignment: | |
1c6fdbd8 KO |
20 | */ |
21 | ||
22 | static inline unsigned eytzinger1_child(unsigned i, unsigned child) | |
23 | { | |
24 | EBUG_ON(child > 1); | |
25 | ||
26 | return (i << 1) + child; | |
27 | } | |
28 | ||
29 | static inline unsigned eytzinger1_left_child(unsigned i) | |
30 | { | |
31 | return eytzinger1_child(i, 0); | |
32 | } | |
33 | ||
34 | static inline unsigned eytzinger1_right_child(unsigned i) | |
35 | { | |
36 | return eytzinger1_child(i, 1); | |
37 | } | |
38 | ||
39 | static inline unsigned eytzinger1_first(unsigned size) | |
40 | { | |
72492d55 | 41 | return rounddown_pow_of_two(size); |
1c6fdbd8 KO |
42 | } |
43 | ||
44 | static inline unsigned eytzinger1_last(unsigned size) | |
45 | { | |
72492d55 | 46 | return rounddown_pow_of_two(size + 1) - 1; |
1c6fdbd8 KO |
47 | } |
48 | ||
49 | /* | |
50 | * eytzinger1_next() and eytzinger1_prev() have the nice properties that | |
51 | * | |
52 | * eytzinger1_next(0) == eytzinger1_first()) | |
53 | * eytzinger1_prev(0) == eytzinger1_last()) | |
54 | * | |
55 | * eytzinger1_prev(eytzinger1_first()) == 0 | |
56 | * eytzinger1_next(eytzinger1_last()) == 0 | |
57 | */ | |
58 | ||
59 | static inline unsigned eytzinger1_next(unsigned i, unsigned size) | |
60 | { | |
72492d55 | 61 | EBUG_ON(i > size); |
1c6fdbd8 | 62 | |
72492d55 | 63 | if (eytzinger1_right_child(i) <= size) { |
1c6fdbd8 KO |
64 | i = eytzinger1_right_child(i); |
65 | ||
72492d55 KO |
66 | i <<= __fls(size + 1) - __fls(i); |
67 | i >>= i > size; | |
1c6fdbd8 KO |
68 | } else { |
69 | i >>= ffz(i) + 1; | |
70 | } | |
71 | ||
72 | return i; | |
73 | } | |
74 | ||
75 | static inline unsigned eytzinger1_prev(unsigned i, unsigned size) | |
76 | { | |
72492d55 | 77 | EBUG_ON(i > size); |
1c6fdbd8 | 78 | |
72492d55 | 79 | if (eytzinger1_left_child(i) <= size) { |
1c6fdbd8 KO |
80 | i = eytzinger1_left_child(i) + 1; |
81 | ||
72492d55 | 82 | i <<= __fls(size + 1) - __fls(i); |
1c6fdbd8 | 83 | i -= 1; |
72492d55 | 84 | i >>= i > size; |
1c6fdbd8 KO |
85 | } else { |
86 | i >>= __ffs(i) + 1; | |
87 | } | |
88 | ||
89 | return i; | |
90 | } | |
91 | ||
92 | static inline unsigned eytzinger1_extra(unsigned size) | |
93 | { | |
72492d55 | 94 | return (size + 1 - rounddown_pow_of_two(size)) << 1; |
1c6fdbd8 KO |
95 | } |
96 | ||
97 | static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size, | |
98 | unsigned extra) | |
99 | { | |
100 | unsigned b = __fls(i); | |
72492d55 | 101 | unsigned shift = __fls(size) - b; |
1c6fdbd8 KO |
102 | int s; |
103 | ||
72492d55 | 104 | EBUG_ON(!i || i > size); |
1c6fdbd8 KO |
105 | |
106 | i ^= 1U << b; | |
107 | i <<= 1; | |
108 | i |= 1; | |
109 | i <<= shift; | |
110 | ||
111 | /* | |
112 | * sign bit trick: | |
113 | * | |
114 | * if (i > extra) | |
115 | * i -= (i - extra) >> 1; | |
116 | */ | |
117 | s = extra - i; | |
118 | i += (s >> 1) & (s >> 31); | |
119 | ||
120 | return i; | |
121 | } | |
122 | ||
123 | static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size, | |
124 | unsigned extra) | |
125 | { | |
126 | unsigned shift; | |
127 | int s; | |
128 | ||
72492d55 | 129 | EBUG_ON(!i || i > size); |
1c6fdbd8 KO |
130 | |
131 | /* | |
132 | * sign bit trick: | |
133 | * | |
134 | * if (i > extra) | |
135 | * i += i - extra; | |
136 | */ | |
137 | s = extra - i; | |
138 | i -= s & (s >> 31); | |
139 | ||
140 | shift = __ffs(i); | |
141 | ||
142 | i >>= shift + 1; | |
72492d55 | 143 | i |= 1U << (__fls(size) - shift); |
1c6fdbd8 KO |
144 | |
145 | return i; | |
146 | } | |
147 | ||
148 | static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size) | |
149 | { | |
150 | return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size)); | |
151 | } | |
152 | ||
153 | static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size) | |
154 | { | |
155 | return __inorder_to_eytzinger1(i, size, eytzinger1_extra(size)); | |
156 | } | |
157 | ||
158 | #define eytzinger1_for_each(_i, _size) \ | |
159 | for ((_i) = eytzinger1_first((_size)); \ | |
160 | (_i) != 0; \ | |
161 | (_i) = eytzinger1_next((_i), (_size))) | |
162 | ||
163 | /* Zero based indexing version: */ | |
164 | ||
165 | static inline unsigned eytzinger0_child(unsigned i, unsigned child) | |
166 | { | |
167 | EBUG_ON(child > 1); | |
168 | ||
169 | return (i << 1) + 1 + child; | |
170 | } | |
171 | ||
172 | static inline unsigned eytzinger0_left_child(unsigned i) | |
173 | { | |
174 | return eytzinger0_child(i, 0); | |
175 | } | |
176 | ||
177 | static inline unsigned eytzinger0_right_child(unsigned i) | |
178 | { | |
179 | return eytzinger0_child(i, 1); | |
180 | } | |
181 | ||
182 | static inline unsigned eytzinger0_first(unsigned size) | |
183 | { | |
72492d55 | 184 | return eytzinger1_first(size) - 1; |
1c6fdbd8 KO |
185 | } |
186 | ||
187 | static inline unsigned eytzinger0_last(unsigned size) | |
188 | { | |
72492d55 | 189 | return eytzinger1_last(size) - 1; |
1c6fdbd8 KO |
190 | } |
191 | ||
192 | static inline unsigned eytzinger0_next(unsigned i, unsigned size) | |
193 | { | |
72492d55 | 194 | return eytzinger1_next(i + 1, size) - 1; |
1c6fdbd8 KO |
195 | } |
196 | ||
197 | static inline unsigned eytzinger0_prev(unsigned i, unsigned size) | |
198 | { | |
72492d55 | 199 | return eytzinger1_prev(i + 1, size) - 1; |
1c6fdbd8 KO |
200 | } |
201 | ||
202 | static inline unsigned eytzinger0_extra(unsigned size) | |
203 | { | |
72492d55 | 204 | return eytzinger1_extra(size); |
1c6fdbd8 KO |
205 | } |
206 | ||
207 | static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size, | |
208 | unsigned extra) | |
209 | { | |
72492d55 | 210 | return __eytzinger1_to_inorder(i + 1, size, extra) - 1; |
1c6fdbd8 KO |
211 | } |
212 | ||
213 | static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size, | |
214 | unsigned extra) | |
215 | { | |
72492d55 | 216 | return __inorder_to_eytzinger1(i + 1, size, extra) - 1; |
1c6fdbd8 KO |
217 | } |
218 | ||
219 | static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size) | |
220 | { | |
221 | return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size)); | |
222 | } | |
223 | ||
224 | static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size) | |
225 | { | |
226 | return __inorder_to_eytzinger0(i, size, eytzinger0_extra(size)); | |
227 | } | |
228 | ||
229 | #define eytzinger0_for_each(_i, _size) \ | |
230 | for ((_i) = eytzinger0_first((_size)); \ | |
231 | (_i) != -1; \ | |
232 | (_i) = eytzinger0_next((_i), (_size))) | |
233 | ||
234 | typedef int (*eytzinger_cmp_fn)(const void *l, const void *r, size_t size); | |
235 | ||
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) | |
239 | { | |
240 | unsigned i, n = 0; | |
241 | ||
242 | if (!nr) | |
243 | return -1; | |
244 | ||
245 | do { | |
246 | i = n; | |
247 | n = eytzinger0_child(i, cmp(search, base + i * size, size) >= 0); | |
248 | } while (n < nr); | |
249 | ||
250 | if (n & 1) { | |
251 | /* @i was greater than @search, return previous node: */ | |
252 | ||
253 | if (i == eytzinger0_first(nr)) | |
254 | return -1; | |
255 | ||
256 | return eytzinger0_prev(i, nr); | |
257 | } else { | |
258 | return i; | |
259 | } | |
260 | } | |
261 | ||
7ef2a73a KO |
262 | #define eytzinger0_find(base, nr, size, _cmp, search) \ |
263 | ({ \ | |
264 | void *_base = (base); \ | |
265 | void *_search = (search); \ | |
266 | size_t _nr = (nr); \ | |
267 | size_t _size = (size); \ | |
268 | size_t _i = 0; \ | |
269 | int _res; \ | |
270 | \ | |
271 | while (_i < _nr && \ | |
272 | (_res = _cmp(_search, _base + _i * _size, _size))) \ | |
273 | _i = eytzinger0_child(_i, _res > 0); \ | |
274 | _i; \ | |
275 | }) | |
1c6fdbd8 KO |
276 | |
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)); | |
280 | ||
281 | #endif /* _EYTZINGER_H */ |