320 lines · c
1/* SPDX-License-Identifier: GPL-2.0 */2#ifndef _EYTZINGER_H3#define _EYTZINGER_H4 5#include <linux/bitops.h>6#include <linux/log2.h>7 8#ifdef EYTZINGER_DEBUG9#define EYTZINGER_BUG_ON(cond) BUG_ON(cond)10#else11#define EYTZINGER_BUG_ON(cond)12#endif13 14/*15 * Traversal for trees in eytzinger layout - a full binary tree layed out in an16 * array.17 *18 * Consider using an eytzinger tree any time you would otherwise be doing binary19 * search over an array. Binary search is a worst case scenario for branch20 * prediction and prefetching, but in an eytzinger tree every node's children21 * are adjacent in memory, thus we can prefetch children before knowing the22 * 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 better27 * alignment and thus better performance because each new level of the tree28 * starts at a power of two, and thus if element 0 was cacheline aligned, each29 * new level will be as well.30 */31 32static inline unsigned eytzinger1_child(unsigned i, unsigned child)33{34 EYTZINGER_BUG_ON(child > 1);35 36 return (i << 1) + child;37}38 39static inline unsigned eytzinger1_left_child(unsigned i)40{41 return eytzinger1_child(i, 0);42}43 44static inline unsigned eytzinger1_right_child(unsigned i)45{46 return eytzinger1_child(i, 1);47}48 49static inline unsigned eytzinger1_first(unsigned size)50{51 return size ? rounddown_pow_of_two(size) : 0;52}53 54static 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 that61 *62 * eytzinger1_next(0) == eytzinger1_first())63 * eytzinger1_prev(0) == eytzinger1_last())64 *65 * eytzinger1_prev(eytzinger1_first()) == 066 * eytzinger1_next(eytzinger1_last()) == 067 */68 69static 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 85static 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 102static inline unsigned eytzinger1_extra(unsigned size)103{104 return size105 ? (size + 1 - rounddown_pow_of_two(size)) << 1106 : 0;107}108 109static 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 135static 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 160static inline unsigned eytzinger1_to_inorder(unsigned i, unsigned size)161{162 return __eytzinger1_to_inorder(i, size, eytzinger1_extra(size));163}164 165static 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 177static inline unsigned eytzinger0_child(unsigned i, unsigned child)178{179 EYTZINGER_BUG_ON(child > 1);180 181 return (i << 1) + 1 + child;182}183 184static inline unsigned eytzinger0_left_child(unsigned i)185{186 return eytzinger0_child(i, 0);187}188 189static inline unsigned eytzinger0_right_child(unsigned i)190{191 return eytzinger0_child(i, 1);192}193 194static inline unsigned eytzinger0_first(unsigned size)195{196 return eytzinger1_first(size) - 1;197}198 199static inline unsigned eytzinger0_last(unsigned size)200{201 return eytzinger1_last(size) - 1;202}203 204static inline unsigned eytzinger0_next(unsigned i, unsigned size)205{206 return eytzinger1_next(i + 1, size) - 1;207}208 209static inline unsigned eytzinger0_prev(unsigned i, unsigned size)210{211 return eytzinger1_prev(i + 1, size) - 1;212}213 214static inline unsigned eytzinger0_extra(unsigned size)215{216 return eytzinger1_extra(size);217}218 219static 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 225static 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 231static inline unsigned eytzinger0_to_inorder(unsigned i, unsigned size)232{233 return __eytzinger0_to_inorder(i, size, eytzinger0_extra(size));234}235 236static 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 */247static 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 expected266 */267 return eytzinger0_prev(i, nr);268 } else {269 return i;270 }271}272 273static 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 - we280 * want to return the first element; next/prev identities mean this work281 * as expected282 *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 289static 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 315void eytzinger0_sort_r(void *, size_t, size_t,316 cmp_r_func_t, swap_r_func_t, const void *);317void eytzinger0_sort(void *, size_t, size_t, cmp_func_t, swap_func_t);318 319#endif /* _EYTZINGER_H */320