33 static inline unsigned eytzinger1_child(unsigned i, unsigned child)  in eytzinger1_child()  argument
37 	return (i << 1) + child;  in eytzinger1_child()
40 static inline unsigned eytzinger1_left_child(unsigned i)  in eytzinger1_left_child()  argument
42 	return eytzinger1_child(i, 0);  in eytzinger1_left_child()
45 static inline unsigned eytzinger1_right_child(unsigned i)  in eytzinger1_right_child()  argument
47 	return eytzinger1_child(i, 1);  in eytzinger1_right_child()
60 static inline unsigned eytzinger1_next(unsigned i, unsigned size)  in eytzinger1_next()  argument
62 	EYTZINGER_BUG_ON(i == 0 || i > size);  in eytzinger1_next()
64 	if (eytzinger1_right_child(i) <= size) {  in eytzinger1_next()
65 		i = eytzinger1_right_child(i);  in eytzinger1_next()
67 		i <<= __fls(size) - __fls(i);  in eytzinger1_next()
68 		i >>= i > size;  in eytzinger1_next()
70 		i >>= ffz(i) + 1;  in eytzinger1_next()
73 	return i;  in eytzinger1_next()
76 static inline unsigned eytzinger1_prev(unsigned i, unsigned size)  in eytzinger1_prev()  argument
78 	EYTZINGER_BUG_ON(i == 0 || i > size);  in eytzinger1_prev()
80 	if (eytzinger1_left_child(i) <= size) {  in eytzinger1_prev()
81 		i = eytzinger1_left_child(i) + 1;  in eytzinger1_prev()
83 		i <<= __fls(size) - __fls(i);  in eytzinger1_prev()
84 		i -= 1;  in eytzinger1_prev()
85 		i >>= i > size;  in eytzinger1_prev()
87 		i >>= __ffs(i) + 1;  in eytzinger1_prev()
90 	return i;  in eytzinger1_prev()
100 static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,  in __eytzinger1_to_inorder()  argument
103 	unsigned b = __fls(i);  in __eytzinger1_to_inorder()
107 	EYTZINGER_BUG_ON(!i || i > size);  in __eytzinger1_to_inorder()
109 	i  ^= 1U << b;  in __eytzinger1_to_inorder()
110 	i <<= 1;  in __eytzinger1_to_inorder()
111 	i  |= 1;  in __eytzinger1_to_inorder()
112 	i <<= shift;  in __eytzinger1_to_inorder()
117 	 * if (i > extra)  in __eytzinger1_to_inorder()
118 	 *	i -= (i - extra) >> 1;  in __eytzinger1_to_inorder()
120 	s = extra - i;  in __eytzinger1_to_inorder()
121 	i += (s >> 1) & (s >> 31);  in __eytzinger1_to_inorder()
123 	return i;  in __eytzinger1_to_inorder()
126 static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,  in __inorder_to_eytzinger1()  argument
132 	EYTZINGER_BUG_ON(!i || i > size);  in __inorder_to_eytzinger1()
137 	 * if (i > extra)  in __inorder_to_eytzinger1()
138 	 *	i += i - extra;  in __inorder_to_eytzinger1()
140 	s = extra - i;  in __inorder_to_eytzinger1()
141 	i -= s & (s >> 31);  in __inorder_to_eytzinger1()
143 	shift = __ffs(i);  in __inorder_to_eytzinger1()
145 	i >>= shift + 1;  in __inorder_to_eytzinger1()
146 	i  |= 1U << (__fls(size) - shift);  in __inorder_to_eytzinger1()
148 	return i;  in __inorder_to_eytzinger1()
151 static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)  in eytzinger1_to_inorder()  argument
153 	return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));  in eytzinger1_to_inorder()
156 static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)  in inorder_to_eytzinger1()  argument
158 	return __inorder_to_eytzinger1(i, size, eytzinger1_extra(size));  in inorder_to_eytzinger1()
168 static inline unsigned eytzinger0_child(unsigned i, unsigned child)  in eytzinger0_child()  argument
172 	return (i << 1) + 1 + child;  in eytzinger0_child()
175 static inline unsigned eytzinger0_left_child(unsigned i)  in eytzinger0_left_child()  argument
177 	return eytzinger0_child(i, 0);  in eytzinger0_left_child()
180 static inline unsigned eytzinger0_right_child(unsigned i)  in eytzinger0_right_child()  argument
182 	return eytzinger0_child(i, 1);  in eytzinger0_right_child()
195 static inline unsigned eytzinger0_next(unsigned i, unsigned size)  in eytzinger0_next()  argument
197 	return eytzinger1_next(i + 1, size) - 1;  in eytzinger0_next()
200 static inline unsigned eytzinger0_prev(unsigned i, unsigned size)  in eytzinger0_prev()  argument
202 	return eytzinger1_prev(i + 1, size) - 1;  in eytzinger0_prev()
210 static inline unsigned __eytzinger0_to_inorder(unsigned i, unsigned size,  in __eytzinger0_to_inorder()  argument
213 	return __eytzinger1_to_inorder(i + 1, size, extra) - 1;  in __eytzinger0_to_inorder()
216 static inline unsigned __inorder_to_eytzinger0(unsigned i, unsigned size,  in __inorder_to_eytzinger0()  argument
219 	return __inorder_to_eytzinger1(i + 1, size, extra) - 1;  in __inorder_to_eytzinger0()
222 static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)  in eytzinger0_to_inorder()  argument
224 	return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));  in eytzinger0_to_inorder()
227 static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)  in inorder_to_eytzinger0()  argument
229 	return __inorder_to_eytzinger0(i, size, eytzinger0_extra(size));  in inorder_to_eytzinger0()