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 think the test code would have to do short linear searches from the test element, and then verify the search functions against that. Have you spotted any issues with searching over arrays with duplicate elements?
