On Wed, Jan 29, 2025 at 9:28 PM Kent Overstreet kent.overstreet@linux.dev 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@linux.dev 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).
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.
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.
Thanks, Andreas