On Wed, Jan 29, 2025 at 7:04 PM Kent Overstreet
<kent.overstreet@xxxxxxxxx> wrote:
> 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 elements +1/-1).
If you expect to get the same index back, that won't work when there
are duplicates.
Andreas
> >
> > Signed-off-by: Andreas Gruenbacher <agruenba@xxxxxxxxxx>
> > ---
> > 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
> >
>
