[17/21] bcachefs: add eytzinger0_find_ge tests

Commit Message

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

Add eytzinger0_find_ge() tests similar to the eytzinger0_find_gt()
tests.

Note that the current implementation of eytzinger0_find_ge() doesn't
always find the first element >= @search, so the tests will occasionally
fail.  The next commit fixes that.

Signed-off-by: Andreas Gruenbacher <[e-mail]>
---
 fs/bcachefs/util.c | 38 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)

Patch

diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c
index d84632870b56..e75329399c6e 100644
--- a/fs/bcachefs/util.c
+++ b/fs/bcachefs/util.c
@@ -856,10 +856,48 @@  static void eytzinger0_find_test_gt(u16 *test_array, unsigned nr, u16 search)
 	}
 }
 
+static void eytzinger0_find_test_ge(u16 *test_array, unsigned nr, u16 search)
+{
+	int r, s;
+	bool bad;
+
+	r = eytzinger0_find_ge(test_array, nr,
+			       sizeof(test_array[0]),
+			       cmp_u16, &search);
+	if (r >= 0) {
+		if (test_array[r] < search) {
+			bad = true;
+		} else {
+			s = eytzinger0_prev(r, nr);
+			bad = s >= 0 && test_array[s] >= search;
+		}
+	} else {
+		s = eytzinger0_first(nr);
+		bad = s >= 0 && test_array[s] >= search;
+	}
+
+	if (bad) {
+		s = -1;
+		eytzinger0_for_each(j, nr) {
+			if (test_array[j] >= search) {
+				s = j;
+				break;
+			}
+		}
+
+		eytzinger0_for_each(j, nr)
+			pr_info("[%3u] = %12u\n", j, test_array[j]);
+		pr_info("find_ge(%12u) = %3i should be %3i\n",
+			search, r, s);
+		BUG();
+	}
+}
+
 static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search)
 {
 	eytzinger0_find_test_le(test_array, nr, search);
 	eytzinger0_find_test_gt(test_array, nr, search);
+	eytzinger0_find_test_ge(test_array, nr, search);
 }
 
 void eytzinger0_find_test(void)