diff options
| author | Andreas Gruenbacher <agruenba@redhat.com> | 2025-01-28 10:56:04 +0100 |
|---|---|---|
| committer | Kent Overstreet <kent.overstreet@linux.dev> | 2025-03-07 16:16:26 -0500 |
| commit | 7d3a96eb08ed815d4104237c7748d23146f11d12 (patch) | |
| tree | 9dd95ca2c46b967dd520d89ef237606ca1eee1f6 | |
| parent | 84bd3ae12d9bcf72ded32fc161cdbc65f10b8bba (diff) | |
bcachefs: convert eytzinger0_find_le to be 1-based
eytzinger0_find_le() is also easy to concert to 1-based eytzinger (but
see the next commit).
Signed-off-by: Andreas Gruenbacher <agruenba@redhat.com>
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
| -rw-r--r-- | fs/bcachefs/eytzinger.h | 16 |
1 files changed, 8 insertions, 8 deletions
diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 99edae4bb995..08256fcaeeb7 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -253,27 +253,27 @@ static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size) static inline int eytzinger0_find_le(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) { - unsigned i, n = 0; + void *base1 = base - size; + unsigned i, n = 1; if (!nr) return -1; do { i = n; - n = eytzinger0_child(i, cmp(base + i * size, search) <= 0); - } while (n < nr); + n = eytzinger1_child(i, cmp(base1 + i * size, search) <= 0); + } while (n <= nr); - if (n & 1) { + if (!(n & 1)) { /* * @i was greater than @search, return previous node: * * if @i was leftmost/smallest element, - * eytzinger0_prev(eytzinger0_first())) returns -1, as expected + * eytzinger1_prev(eytzinger1_first())) returns 0, as expected */ - return eytzinger0_prev(i, nr); - } else { - return i; + i = eytzinger1_prev(i, nr); } + return i - 1; } static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size, |