xref: /linux/fs/bcachefs/eytzinger.h (revision 820b9efe)
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 
eytzinger1_child(unsigned i,unsigned child)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 
eytzinger1_left_child(unsigned i)39 static inline unsigned eytzinger1_left_child(unsigned i)
40 {
41 	return eytzinger1_child(i, 0);
42 }
43 
eytzinger1_right_child(unsigned i)44 static inline unsigned eytzinger1_right_child(unsigned i)
45 {
46 	return eytzinger1_child(i, 1);
47 }
48 
eytzinger1_first(unsigned size)49 static inline unsigned eytzinger1_first(unsigned size)
50 {
51 	return size ? rounddown_pow_of_two(size) : 0;
52 }
53 
eytzinger1_last(unsigned size)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 
eytzinger1_next(unsigned i,unsigned size)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 
eytzinger1_prev(unsigned i,unsigned size)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 
eytzinger1_extra(unsigned size)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 
__eytzinger1_to_inorder(unsigned i,unsigned size,unsigned extra)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 
__inorder_to_eytzinger1(unsigned i,unsigned size,unsigned extra)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 
eytzinger1_to_inorder(unsigned i,unsigned size)160 static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)
161 {
162 	return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));
163 }
164 
inorder_to_eytzinger1(unsigned i,unsigned size)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 
eytzinger0_child(unsigned i,unsigned child)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 
eytzinger0_left_child(unsigned i)184 static inline unsigned eytzinger0_left_child(unsigned i)
185 {
186 	return eytzinger0_child(i, 0);
187 }
188 
eytzinger0_right_child(unsigned i)189 static inline unsigned eytzinger0_right_child(unsigned i)
190 {
191 	return eytzinger0_child(i, 1);
192 }
193 
eytzinger0_first(unsigned size)194 static inline unsigned eytzinger0_first(unsigned size)
195 {
196 	return eytzinger1_first(size) - 1;
197 }
198 
eytzinger0_last(unsigned size)199 static inline unsigned eytzinger0_last(unsigned size)
200 {
201 	return eytzinger1_last(size) - 1;
202 }
203 
eytzinger0_next(unsigned i,unsigned size)204 static inline unsigned eytzinger0_next(unsigned i, unsigned size)
205 {
206 	return eytzinger1_next(i + 1, size) - 1;
207 }
208 
eytzinger0_prev(unsigned i,unsigned size)209 static inline unsigned eytzinger0_prev(unsigned i, unsigned size)
210 {
211 	return eytzinger1_prev(i + 1, size) - 1;
212 }
213 
eytzinger0_extra(unsigned size)214 static inline unsigned eytzinger0_extra(unsigned size)
215 {
216 	return eytzinger1_extra(size);
217 }
218 
__eytzinger0_to_inorder(unsigned i,unsigned size,unsigned extra)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 
__inorder_to_eytzinger0(unsigned i,unsigned size,unsigned extra)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 
eytzinger0_to_inorder(unsigned i,unsigned size)231 static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)
232 {
233 	return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));
234 }
235 
inorder_to_eytzinger0(unsigned i,unsigned size)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 */
eytzinger0_find_le(void * base,size_t nr,size_t size,cmp_func_t cmp,const void * search)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 
eytzinger0_find_gt(void * base,size_t nr,size_t size,cmp_func_t cmp,const void * search)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 
eytzinger0_find_ge(void * base,size_t nr,size_t size,cmp_func_t cmp,const void * search)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