1 /* SPDX-License-Identifier: GPL-2.0 */
11  * Traversal for trees in eytzinger layout - a full binary tree layed out in an
18  * With one based indexing each level of the tree starts at a power of two -
22 static inline unsigned eytzinger1_child(unsigned i, unsigned child)  in eytzinger1_child()  argument
26 	return (i << 1) + child;  in eytzinger1_child()
29 static inline unsigned eytzinger1_left_child(unsigned i)  in eytzinger1_left_child()  argument
31 	return eytzinger1_child(i, 0);  in eytzinger1_left_child()
34 static inline unsigned eytzinger1_right_child(unsigned i)  in eytzinger1_right_child()  argument
36 	return eytzinger1_child(i, 1);  in eytzinger1_right_child()
46 	return rounddown_pow_of_two(size + 1) - 1;  in eytzinger1_last()
59 static inline unsigned eytzinger1_next(unsigned i, unsigned size)  in eytzinger1_next()  argument
61 	EBUG_ON(i > size);  in eytzinger1_next()
63 	if (eytzinger1_right_child(i) <= size) {  in eytzinger1_next()
64 		i = eytzinger1_right_child(i);  in eytzinger1_next()
66 		i <<= __fls(size + 1) - __fls(i);  in eytzinger1_next()
67 		i >>= i > size;  in eytzinger1_next()
69 		i >>= ffz(i) + 1;  in eytzinger1_next()
72 	return i;  in eytzinger1_next()
75 static inline unsigned eytzinger1_prev(unsigned i, unsigned size)  in eytzinger1_prev()  argument
77 	EBUG_ON(i > size);  in eytzinger1_prev()
79 	if (eytzinger1_left_child(i) <= size) {  in eytzinger1_prev()
80 		i = eytzinger1_left_child(i) + 1;  in eytzinger1_prev()
82 		i <<= __fls(size + 1) - __fls(i);  in eytzinger1_prev()
83 		i -= 1;  in eytzinger1_prev()
84 		i >>= i > size;  in eytzinger1_prev()
86 		i >>= __ffs(i) + 1;  in eytzinger1_prev()
89 	return i;  in eytzinger1_prev()
94 	return (size + 1 - rounddown_pow_of_two(size)) << 1;  in eytzinger1_extra()
97 static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,  in __eytzinger1_to_inorder()  argument
100 	unsigned b = __fls(i);  in __eytzinger1_to_inorder()
101 	unsigned shift = __fls(size) - b;  in __eytzinger1_to_inorder()
104 	EBUG_ON(!i || i > size);  in __eytzinger1_to_inorder()
106 	i  ^= 1U << b;  in __eytzinger1_to_inorder()
107 	i <<= 1;  in __eytzinger1_to_inorder()
108 	i  |= 1;  in __eytzinger1_to_inorder()
109 	i <<= shift;  in __eytzinger1_to_inorder()
114 	 * if (i > extra)  in __eytzinger1_to_inorder()
115 	 *	i -= (i - extra) >> 1;  in __eytzinger1_to_inorder()
117 	s = extra - i;  in __eytzinger1_to_inorder()
118 	i += (s >> 1) & (s >> 31);  in __eytzinger1_to_inorder()
120 	return i;  in __eytzinger1_to_inorder()
123 static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,  in __inorder_to_eytzinger1()  argument
129 	EBUG_ON(!i || i > size);  in __inorder_to_eytzinger1()
134 	 * if (i > extra)  in __inorder_to_eytzinger1()
135 	 *	i += i - extra;  in __inorder_to_eytzinger1()
137 	s = extra - i;  in __inorder_to_eytzinger1()
138 	i -= s & (s >> 31);  in __inorder_to_eytzinger1()
140 	shift = __ffs(i);  in __inorder_to_eytzinger1()
142 	i >>= shift + 1;  in __inorder_to_eytzinger1()
143 	i  |= 1U << (__fls(size) - shift);  in __inorder_to_eytzinger1()
145 	return i;  in __inorder_to_eytzinger1()
148 static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)  in eytzinger1_to_inorder()  argument
150 	return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));  in eytzinger1_to_inorder()
153 static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)  in inorder_to_eytzinger1()  argument
155 	return __inorder_to_eytzinger1(i, size, eytzinger1_extra(size));  in inorder_to_eytzinger1()
165 static inline unsigned eytzinger0_child(unsigned i, unsigned child)  in eytzinger0_child()  argument
169 	return (i << 1) + 1 + child;  in eytzinger0_child()
172 static inline unsigned eytzinger0_left_child(unsigned i)  in eytzinger0_left_child()  argument
174 	return eytzinger0_child(i, 0);  in eytzinger0_left_child()
177 static inline unsigned eytzinger0_right_child(unsigned i)  in eytzinger0_right_child()  argument
179 	return eytzinger0_child(i, 1);  in eytzinger0_right_child()
184 	return eytzinger1_first(size) - 1;  in eytzinger0_first()
189 	return eytzinger1_last(size) - 1;  in eytzinger0_last()
192 static inline unsigned eytzinger0_next(unsigned i, unsigned size)  in eytzinger0_next()  argument
194 	return eytzinger1_next(i + 1, size) - 1;  in eytzinger0_next()
197 static inline unsigned eytzinger0_prev(unsigned i, unsigned size)  in eytzinger0_prev()  argument
199 	return eytzinger1_prev(i + 1, size) - 1;  in eytzinger0_prev()
207 static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,  in __eytzinger0_to_inorder()  argument
210 	return __eytzinger1_to_inorder(i + 1, size, extra) - 1;  in __eytzinger0_to_inorder()
213 static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,  in __inorder_to_eytzinger0()  argument
216 	return __inorder_to_eytzinger1(i + 1, size, extra) - 1;  in __inorder_to_eytzinger0()
219 static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)  in eytzinger0_to_inorder()  argument
221 	return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));  in eytzinger0_to_inorder()
224 static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)  in inorder_to_eytzinger0()  argument
226 	return __inorder_to_eytzinger0(i, size, eytzinger0_extra(size));  in inorder_to_eytzinger0()
231 	     (_i) != -1;				\
236 /* return greatest node <= @search, or -1 if not found */
240 	unsigned i, n = 0;  in eytzinger0_find_le()  local
243 		return -1;  in eytzinger0_find_le()
246 		i = n;  in eytzinger0_find_le()
247 		n = eytzinger0_child(i, cmp(search, base + i * size, size) >= 0);  in eytzinger0_find_le()
251 		/* @i was greater than @search, return previous node: */  in eytzinger0_find_le()
253 		if (i == eytzinger0_first(nr))  in eytzinger0_find_le()
254 			return -1;  in eytzinger0_find_le()
256 		return eytzinger0_prev(i, nr);  in eytzinger0_find_le()
258 		return i;  in eytzinger0_find_le()