32 static inline unsigned eytzinger1_child(unsigned i, unsigned child)  in eytzinger1_child()  argument
36 	return (i << 1) + child;  in eytzinger1_child()
39 static inline unsigned eytzinger1_left_child(unsigned i)  in eytzinger1_left_child()  argument
41 	return eytzinger1_child(i, 0);  in eytzinger1_left_child()
44 static inline unsigned eytzinger1_right_child(unsigned i)  in eytzinger1_right_child()  argument
46 	return eytzinger1_child(i, 1);  in eytzinger1_right_child()
69 static inline unsigned eytzinger1_next(unsigned i, unsigned size)  in eytzinger1_next()  argument
71 	EYTZINGER_BUG_ON(i > size);  in eytzinger1_next()
73 	if (eytzinger1_right_child(i) <= size) {  in eytzinger1_next()
74 		i = eytzinger1_right_child(i);  in eytzinger1_next()
76 		i <<= __fls(size + 1) - __fls(i);  in eytzinger1_next()
77 		i >>= i > size;  in eytzinger1_next()
79 		i >>= ffz(i) + 1;  in eytzinger1_next()
82 	return i;  in eytzinger1_next()
85 static inline unsigned eytzinger1_prev(unsigned i, unsigned size)  in eytzinger1_prev()  argument
87 	EYTZINGER_BUG_ON(i > size);  in eytzinger1_prev()
89 	if (eytzinger1_left_child(i) <= size) {  in eytzinger1_prev()
90 		i = eytzinger1_left_child(i) + 1;  in eytzinger1_prev()
92 		i <<= __fls(size + 1) - __fls(i);  in eytzinger1_prev()
93 		i -= 1;  in eytzinger1_prev()
94 		i >>= i > size;  in eytzinger1_prev()
96 		i >>= __ffs(i) + 1;  in eytzinger1_prev()
99 	return i;  in eytzinger1_prev()
109 static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,  in __eytzinger1_to_inorder()  argument
112 	unsigned b = __fls(i);  in __eytzinger1_to_inorder()
116 	EYTZINGER_BUG_ON(!i || i > size);  in __eytzinger1_to_inorder()
118 	i  ^= 1U << b;  in __eytzinger1_to_inorder()
119 	i <<= 1;  in __eytzinger1_to_inorder()
120 	i  |= 1;  in __eytzinger1_to_inorder()
121 	i <<= shift;  in __eytzinger1_to_inorder()
129 	s = extra - i;  in __eytzinger1_to_inorder()
130 	i += (s >> 1) & (s >> 31);  in __eytzinger1_to_inorder()
132 	return i;  in __eytzinger1_to_inorder()
135 static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,  in __inorder_to_eytzinger1()  argument
141 	EYTZINGER_BUG_ON(!i || i > size);  in __inorder_to_eytzinger1()
149 	s = extra - i;  in __inorder_to_eytzinger1()
150 	i -= s & (s >> 31);  in __inorder_to_eytzinger1()
152 	shift = __ffs(i);  in __inorder_to_eytzinger1()
154 	i >>= shift + 1;  in __inorder_to_eytzinger1()
155 	i  |= 1U << (__fls(size) - shift);  in __inorder_to_eytzinger1()
157 	return i;  in __inorder_to_eytzinger1()
160 static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)  in eytzinger1_to_inorder()  argument
162 	return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));  in eytzinger1_to_inorder()
165 static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)  in inorder_to_eytzinger1()  argument
167 	return __inorder_to_eytzinger1(i, size, eytzinger1_extra(size));  in inorder_to_eytzinger1()
177 static inline unsigned eytzinger0_child(unsigned i, unsigned child)  in eytzinger0_child()  argument
181 	return (i << 1) + 1 + child;  in eytzinger0_child()
184 static inline unsigned eytzinger0_left_child(unsigned i)  in eytzinger0_left_child()  argument
186 	return eytzinger0_child(i, 0);  in eytzinger0_left_child()
189 static inline unsigned eytzinger0_right_child(unsigned i)  in eytzinger0_right_child()  argument
191 	return eytzinger0_child(i, 1);  in eytzinger0_right_child()
204 static inline unsigned eytzinger0_next(unsigned i, unsigned size)  in eytzinger0_next()  argument
206 	return eytzinger1_next(i + 1, size) - 1;  in eytzinger0_next()
209 static inline unsigned eytzinger0_prev(unsigned i, unsigned size)  in eytzinger0_prev()  argument
211 	return eytzinger1_prev(i + 1, size) - 1;  in eytzinger0_prev()
219 static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,  in __eytzinger0_to_inorder()  argument
222 	return __eytzinger1_to_inorder(i + 1, size, extra) - 1;  in __eytzinger0_to_inorder()
225 static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,  in __inorder_to_eytzinger0()  argument
228 	return __inorder_to_eytzinger1(i + 1, size, extra) - 1;  in __inorder_to_eytzinger0()
231 static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)  in eytzinger0_to_inorder()  argument
233 	return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));  in eytzinger0_to_inorder()
236 static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)  in inorder_to_eytzinger0()  argument
238 	return __inorder_to_eytzinger0(i, size, eytzinger0_extra(size));  in inorder_to_eytzinger0()
250 	unsigned i, n = 0;  in eytzinger0_find_le()  local
256 		i = n;  in eytzinger0_find_le()
257 		n = eytzinger0_child(i, cmp(base + i * size, search) <= 0);  in eytzinger0_find_le()
267 		return eytzinger0_prev(i, nr);  in eytzinger0_find_le()
269 		return i;  in eytzinger0_find_le()