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