On Wed, Jan 29, 2025 at 10:21:31PM +0100, Andreas Gruenbacher wrote:
> On Wed, Jan 29, 2025 at 9:28 PM Kent Overstreet
> <kent.overstreet@xxxxxxxxx> wrote:
> > On Wed, Jan 29, 2025 at 07:21:49PM +0100, Andreas Gruenbacher wrote:
> > > 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.
> >
> > No, but we wouldn't expect to get the same index back if we're testing
> > every combination of elements (+0, -1, +1) x (le, ge, gt) - and it
> > sounds like perhaps we should, if you've been finding bugs. Thoughts?
>
> I don't really know what you're after here. Function
> eytzinger0_find_test() already tests every combination of elements
> (+0, -1, +1) x (le, ge, gt).
Ok - it can be hard to tell looking at isolated patches vs. being able
to fetch a git repo. Do you have it in a branch I can fetch from?
> The full scans of the array in eytzinger0_find_test_{le,gt,ge}() are
> not there to verify correctness; they're only there to produce
> slightly nicer debug output. I'm perfectly happy with removing that if
> you prefer.
No, not at all
> > I think the test code would have to do short linear searches from the
> > test element, and then verify the search functions against that.
>
> What for? We already know from the eytzinger0_for_each loop in
> eytzinger0_find_test() that the array is in eytzinger sort order, and
> we also know from eytzinger{0,1}_test() that the _prev() and _next()
> functions are doing "the right thing". So the one thing left to verify
> in eytzinger0_find_test_{le,gt,ge}() is that all the search functions
> always return the boundary element. That's done by going to the next
> element in search order and by verifying that it no longer fulfils the
> search criterion.
>
> > Have you spotted any issues with searching over arrays with duplicate
> > elements?
>
> Only that eytzinger0_find_ge() didn't always find the first matching
> element in the array; see patches 17 and 18.
Gotcha
Ok, it sounds like everything I'm after is there - give me a git branch
so I can read through it that way and I'll be happy to merge when you
say it's ready
