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
32static inline unsigned eytzinger1_child(unsigned i, unsigned child)
33{
34	EYTZINGER_BUG_ON(child > 1);
35
36	return (i << 1) + child;
37}
38
39static inline unsigned eytzinger1_left_child(unsigned i)
40{
41	return eytzinger1_child(i, 0);
42}
43
44static inline unsigned eytzinger1_right_child(unsigned i)
45{
46	return eytzinger1_child(i, 1);
47}
48
49static inline unsigned eytzinger1_first(unsigned size)
50{
51	return rounddown_pow_of_two(size);
52}
53
54static 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
69static 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
85static 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
102static inline unsigned eytzinger1_extra(unsigned size)
103{
104	return (size + 1 - rounddown_pow_of_two(size)) << 1;
105}
106
107static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,
108					      unsigned extra)
109{
110	unsigned b = __fls(i);
111	unsigned shift = __fls(size) - b;
112	int s;
113
114	EYTZINGER_BUG_ON(!i || i > size);
115
116	i  ^= 1U << b;
117	i <<= 1;
118	i  |= 1;
119	i <<= shift;
120
121	/*
122	 * sign bit trick:
123	 *
124	 * if (i > extra)
125	 *	i -= (i - extra) >> 1;
126	 */
127	s = extra - i;
128	i += (s >> 1) & (s >> 31);
129
130	return i;
131}
132
133static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,
134					       unsigned extra)
135{
136	unsigned shift;
137	int s;
138
139	EYTZINGER_BUG_ON(!i || i > size);
140
141	/*
142	 * sign bit trick:
143	 *
144	 * if (i > extra)
145	 *	i += i - extra;
146	 */
147	s = extra - i;
148	i -= s & (s >> 31);
149
150	shift = __ffs(i);
151
152	i >>= shift + 1;
153	i  |= 1U << (__fls(size) - shift);
154
155	return i;
156}
157
158static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)
159{
160	return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));
161}
162
163static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)
164{
165	return __inorder_to_eytzinger1(i, size, eytzinger1_extra(size));
166}
167
168#define eytzinger1_for_each(_i, _size)			\
169	for (unsigned (_i) = eytzinger1_first((_size));	\
170	     (_i) != 0;					\
171	     (_i) = eytzinger1_next((_i), (_size)))
172
173/* Zero based indexing version: */
174
175static inline unsigned eytzinger0_child(unsigned i, unsigned child)
176{
177	EYTZINGER_BUG_ON(child > 1);
178
179	return (i << 1) + 1 + child;
180}
181
182static inline unsigned eytzinger0_left_child(unsigned i)
183{
184	return eytzinger0_child(i, 0);
185}
186
187static inline unsigned eytzinger0_right_child(unsigned i)
188{
189	return eytzinger0_child(i, 1);
190}
191
192static inline unsigned eytzinger0_first(unsigned size)
193{
194	return eytzinger1_first(size) - 1;
195}
196
197static inline unsigned eytzinger0_last(unsigned size)
198{
199	return eytzinger1_last(size) - 1;
200}
201
202static inline unsigned eytzinger0_next(unsigned i, unsigned size)
203{
204	return eytzinger1_next(i + 1, size) - 1;
205}
206
207static inline unsigned eytzinger0_prev(unsigned i, unsigned size)
208{
209	return eytzinger1_prev(i + 1, size) - 1;
210}
211
212static inline unsigned eytzinger0_extra(unsigned size)
213{
214	return eytzinger1_extra(size);
215}
216
217static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,
218					       unsigned extra)
219{
220	return __eytzinger1_to_inorder(i + 1, size, extra) - 1;
221}
222
223static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,
224					       unsigned extra)
225{
226	return __inorder_to_eytzinger1(i + 1, size, extra) - 1;
227}
228
229static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)
230{
231	return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));
232}
233
234static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)
235{
236	return __inorder_to_eytzinger0(i, size, eytzinger0_extra(size));
237}
238
239#define eytzinger0_for_each(_i, _size)			\
240	for (unsigned (_i) = eytzinger0_first((_size));	\
241	     (_i) != -1;				\
242	     (_i) = eytzinger0_next((_i), (_size)))
243
244/* return greatest node <= @search, or -1 if not found */
245static inline int eytzinger0_find_le(void *base, size_t nr, size_t size,
246				     cmp_func_t cmp, const void *search)
247{
248	unsigned i, n = 0;
249
250	if (!nr)
251		return -1;
252
253	do {
254		i = n;
255		n = eytzinger0_child(i, cmp(base + i * size, search) <= 0);
256	} while (n < nr);
257
258	if (n & 1) {
259		/*
260		 * @i was greater than @search, return previous node:
261		 *
262		 * if @i was leftmost/smallest element,
263		 * eytzinger0_prev(eytzinger0_first())) returns -1, as expected
264		 */
265		return eytzinger0_prev(i, nr);
266	} else {
267		return i;
268	}
269}
270
271static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size,
272				     cmp_func_t cmp, const void *search)
273{
274	ssize_t idx = eytzinger0_find_le(base, nr, size, cmp, search);
275
276	/*
277	 * if eytitzinger0_find_le() returned -1 - no element was <= search - we
278	 * want to return the first element; next/prev identities mean this work
279	 * as expected
280	 *
281	 * similarly if find_le() returns last element, we should return -1;
282	 * identities mean this all works out:
283	 */
284	return eytzinger0_next(idx, nr);
285}
286
287#define eytzinger0_find(base, nr, size, _cmp, search)			\
288({									\
289	void *_base		= (base);				\
290	const void *_search	= (search);				\
291	size_t _nr		= (nr);					\
292	size_t _size		= (size);				\
293	size_t _i		= 0;					\
294	int _res;							\
295									\
296	while (_i < _nr &&						\
297	       (_res = _cmp(_search, _base + _i * _size)))		\
298		_i = eytzinger0_child(_i, _res > 0);			\
299	_i;								\
300})
301
302void eytzinger0_sort_r(void *, size_t, size_t,
303		       cmp_r_func_t, swap_r_func_t, const void *);
304void eytzinger0_sort(void *, size_t, size_t, cmp_func_t, swap_func_t);
305
306#endif /* _EYTZINGER_H */
307