From d148d804f2cc5f932ef840853958a36b77346a54 Mon Sep 17 00:00:00 2001 From: Andreas Gruenbacher Date: Tue, 28 Jan 2025 10:56:04 +0100 Subject: [PATCH] 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 Signed-off-by: Kent Overstreet --- fs/bcachefs/eytzinger.h | 16 ++++++++-------- 1 file 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, -- 2.25.1