[10/21] bcachefs: add eytzinger0_for_each_prev

Commit Message

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

Add an eytzinger0_for_each_prev() macro for iterating through an
eytzinger array in reverse.

Signed-off-by: Andreas Gruenbacher <[e-mail]>
---
 fs/bcachefs/eytzinger.h | 5 +++++
 fs/bcachefs/util.c      | 9 +++++++++
 2 files changed, 14 insertions(+)

Patch

diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h
index 6fa6d51a5420..f25c895aa184 100644
--- a/fs/bcachefs/eytzinger.h
+++ b/fs/bcachefs/eytzinger.h
@@ -246,6 +246,11 @@  static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)
 	     (_i) != -1;				\
 	     (_i) = eytzinger0_next((_i), (_size)))
 
+#define eytzinger0_for_each_prev(_i, _size)		\
+	for (unsigned (_i) = eytzinger0_last((_size));	\
+	     (_i) != -1;				\
+	     (_i) = eytzinger0_prev((_i), (_size)))
+
 /* return greatest node <= @search, or -1 if not found */
 static inline int eytzinger0_find_le(void *base, size_t nr, size_t size,
 				     cmp_func_t cmp, const void *search)
diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c
index 87502e1ac7ce..3fe9a3b8c696 100644
--- a/fs/bcachefs/util.c
+++ b/fs/bcachefs/util.c
@@ -763,6 +763,15 @@  void eytzinger0_test(void)
 			inorder++;
 		}
 		BUG_ON(inorder != size);
+
+		inorder = size - 1;
+		eytzinger0_for_each_prev(eytz, size) {
+			BUG_ON(eytz != eytzinger0_first(size) &&
+			       eytzinger0_next(eytzinger0_prev(eytz, size), size) != eytz);
+
+			inorder--;
+		}
+		BUG_ON(inorder != -1);
 	}
 }