[18/21] bcachefs: implement eytzinger0_find_ge directly

Commit Message

Andreas Gruenbacher Jan. 28, 2025, 4:38 p.m. UTC

Implement eytzinger0_find_ge() directly instead of implementing it in
terms of eytzinger0_find_le() and adjusting the result.

Signed-off-by: Andreas Gruenbacher <[e-mail]>
---
 fs/bcachefs/eytzinger.h | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

Patch

diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h
index a5a1abae5b13..6a363b12bd21 100644
--- a/fs/bcachefs/eytzinger.h
+++ b/fs/bcachefs/eytzinger.h
@@ -277,15 +277,17 @@  static inline int eytzinger0_find_gt(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_ge(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);
-
-	if (idx < nr && !cmp(base + idx * size, search))
-		return idx;
+	void *base1 = base - size;
+	unsigned n = 1;
 
-	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;
 }
 
 #define eytzinger0_find(base, nr, size, _cmp, search)			\