fs/bcachefs/eytzinger.h

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