[14/21] bcachefs: simplify eytzinger0_find_le

Commit Message

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

Replace the over-complicated implementation of eytzinger0_find_le() by
an equivalent, simplifer version.

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

Patch

diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h
index 130f5fe30bd7..89a0e4192212 100644
--- a/fs/bcachefs/eytzinger.h
+++ b/fs/bcachefs/eytzinger.h
@@ -256,26 +256,12 @@  static inline int eytzinger0_find_le(void *base, size_t nr, size_t size,
 				     cmp_func_t cmp, const void *search)
 {
 	void *base1 = base - size;
-	unsigned i, n = 1;
-
-	if (!nr)
-		return -1;
-
-	do {
-		i = n;
-		n = eytzinger1_child(i, cmp(base1 + i * size, search) <= 0);
-	} while (n <= nr);
-
-	if (!(n & 1)) {
-		/*
-		 * @i was greater than @search, return previous node:
-		 *
-		 * if @i was leftmost/smallest element,
-		 * eytzinger1_prev(eytzinger1_first())) returns 0, as expected
-		 */
-		i = eytzinger1_prev(i, nr);
-	}
-	return i - 1;
+	unsigned n = 1;
+
+	while (n <= nr)
+		n = eytzinger1_child(n, cmp(base1 + n * size, search) <= 0);
+	n >>= __ffs(n) + 1;
+	return n - 1;
 }
 
 static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size,