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 <agruenba@xxxxxxxxxx>
---
fs/bcachefs/util.c | 38 ++++++++++++++++++++++++++++++++++++++
1 file changed, 38 insertions(+)
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)
--
2.48.1
