diff mbox series

[13/21] bcachefs: convert eytzinger0_find_le to be 1-based

Message ID 20250128163859.1883260-14-agruenba@redhat.com (mailing list archive)
State New
Headers show
Series bcachefs: eytzinger code | expand

Commit Message

Andreas Gruenbacher Jan. 28, 2025, 4:38 p.m. UTC 
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>
---
 fs/bcachefs/eytzinger.h | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)
diff mbox series

Patch

diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h
index d3e8b9edf335..130f5fe30bd7 100644
--- a/fs/bcachefs/eytzinger.h
+++ b/fs/bcachefs/eytzinger.h
@@ -255,27 +255,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,