From 2182f29545f385df9aa4861f9e08d0d378c26c9f Mon Sep 17 00:00:00 2001 From: Andreas Gruenbacher Date: Mon, 27 Jan 2025 17:52:39 +0100 Subject: [PATCH] bcachefs: implement eytzinger0_find_gt directly Instead of implementing eytzinger0_find_gt() in terms of eytzinger0_find_le() and adjusting the result, implement it directly. Signed-off-by: Andreas Gruenbacher Signed-off-by: Kent Overstreet --- fs/bcachefs/eytzinger.h | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-) diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index a530dbcde476c..568a04b16d093 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -262,20 +262,17 @@ static inline int eytzinger0_find_le(void *base, size_t nr, size_t size, return n - 1; } +/* return smallest node > @search, or -1 if not found */ static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) { - ssize_t idx = eytzinger0_find_le(base, nr, size, cmp, search); + void *base1 = base - size; + unsigned n = 1; - /* - * if eytitzinger0_find_le() returned -1 - no element was <= search - we - * want to return the first element; next/prev identities mean this work - * as expected - * - * similarly if find_le() returns last element, we should return -1; - * identities mean this all works out: - */ - return eytzinger0_next(idx, nr); + while (n <= nr) + n = eytzinger1_child(n, cmp(base1 + n * size, search) <= 0); + n >>= __ffs(n + 1) + 1; + return n - 1; } static inline int eytzinger0_find_ge(void *base, size_t nr, size_t size, -- 2.39.5