On Tue, Jan 28, 2025 at 05:38:48PM +0100, Andreas Gruenbacher wrote: > Rename eytzinger0_find_test_val() to eytzinger0_find_test_le() and add a > new eytzinger0_find_test_val() wrapper that calls it. > > We have already established that the array is sorted in eytzinger order, > so we can use the eytzinger iterator functions and check the boundary > conditions to verify the result of eytzinger0_find_le(). > > Only scan the entire array if we get an incorrect result. When we need > to scan, use eytzinger0_for_each_prev() so that we'll stop at the > highest matching element in the array in case there are duplicates; > going through the array linearly wouldn't give us that.
For test code, wouldn't it be simpler to iterate over the test array, testing with every element as a search value? There's enough corner cases in lookup that I think it'd be worthwhile (and probably add some extra test values, e.g. first/last emelements +1/-1). > > Signed-off-by: Andreas Gruenbacher <[email protected]> > --- > fs/bcachefs/util.c | 41 ++++++++++++++++++++++++++++++----------- > 1 file changed, 30 insertions(+), 11 deletions(-) > > diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c > index 3fe9a3b8c696..c772629783f3 100644 > --- a/fs/bcachefs/util.c > +++ b/fs/bcachefs/util.c > @@ -782,29 +782,48 @@ static inline int cmp_u16(const void *_l, const void > *_r) > return (*l > *r) - (*r > *l); > } > > -static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 > search) > +static void eytzinger0_find_test_le(u16 *test_array, unsigned nr, u16 search) > { > - int i, c1 = -1, c2 = -1; > - ssize_t r; > + int r, s; > + bool bad; > > r = eytzinger0_find_le(test_array, nr, > sizeof(test_array[0]), > cmp_u16, &search); > - if (r >= 0) > - c1 = test_array[r]; > + if (r >= 0) { > + if (test_array[r] > search) { > + bad = true; > + } else { > + s = eytzinger0_next(r, nr); > + bad = s >= 0 && test_array[s] <= search; > + } > + } else { > + s = eytzinger0_last(nr); > + bad = s >= 0 && test_array[s] <= search; > + } > > - for (i = 0; i < nr; i++) > - if (test_array[i] <= search && test_array[i] > c2) > - c2 = test_array[i]; > + if (bad) { > + s = -1; > + eytzinger0_for_each_prev(j, nr) { > + if (test_array[j] <= search) { > + s = j; > + break; > + } > + } > > - if (c1 != c2) { > eytzinger0_for_each(j, nr) > pr_info("[%3u] = %12u\n", j, test_array[j]); > - pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i\n", > - i, r, c1, c2); > + pr_info("find_le(%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); > +} > + > void eytzinger0_find_test(void) > { > unsigned i, nr, allocated = 1 << 12; > -- > 2.48.1 >
