| Message ID | 20250128163859.1883260-12-agruenba@redhat.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | bcachefs: eytzinger code | expand |
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 <agruenba@redhat.com> > --- > 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 >
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. Andreas > > > > Signed-off-by: Andreas Gruenbacher <agruenba@redhat.com> > > --- > > 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 > > >
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 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?
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
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@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). 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
On Wed, Jan 29, 2025 at 10:30 PM Kent Overstreet <kent.overstreet@linux.dev> wrote: > 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@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). > > 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 Sure, I've pushed the patches here: https://git.kernel.org/pub/scm/linux/kernel/git/agruen/linux.git/log/?h=bcachefs Note that you don't want to merge the following patch: bcachefs: Run the eytzinger tests on modprobe And this minor one should probably be changed to use __maybe_unused or dropped; not sure which of the two options you prefer: bcachefs: remove dead code in is_aligned I've only run the self tests. They seem to provide good coverage and I don't expect any trouble, but some real filesystem testing would be great. Thanks, Andreas
On Thu, Jan 30, 2025 at 12:17:51AM +0100, Andreas Gruenbacher wrote: > On Wed, Jan 29, 2025 at 10:30 PM Kent Overstreet > <kent.overstreet@linux.dev> wrote: > > 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@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). > > > > 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 > > Sure, I've pushed the patches here: > > https://git.kernel.org/pub/scm/linux/kernel/git/agruen/linux.git/log/?h=bcachefs > > Note that you don't want to merge the following patch: > > bcachefs: Run the eytzinger tests on modprobe > > And this minor one should probably be changed to use __maybe_unused or > dropped; not sure which of the two options you prefer: > > bcachefs: remove dead code in is_aligned That code is a cut and paste of sort.c, so we should just drop it - no reason for those to diverge (and perhaps add a giant comment on where it's from). > I've only run the self tests. They seem to provide good coverage and I > don't expect any trouble, but some real filesystem testing would be > great. I've fetched it to my repo and added it to the CI: https://evilpiepirate.org/~testdashboard/ci?user=kmo&branch=eytzinger
On Thu, Jan 30, 2025 at 12:36 AM Kent Overstreet <kent.overstreet@linux.dev> wrote: > I've fetched it to my repo and added it to the CI: > > https://evilpiepirate.org/~testdashboard/ci?user=kmo&branch=eytzinger Ah, the following went wrong in "bcachefs: convert eytzinger0_find to be 1-based": diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index d3e8b9edf335..3afb346b0738 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -308,7 +308,7 @@ static inline int eytzinger0_find_ge(void *base, size_t nr, size_t size, #define eytzinger0_find(base, nr, size, _cmp, search) \ ({ \ size_t _size = (size); \ - void *_base1 = (base) - _size; \ + void *_base1 = (void *)(base) - _size; \ const void *_search = (search); \ size_t _nr = (nr); \ size_t _i = 1; \ The eytzinger0_find() macro is still a bit of a mess. I've updated https://git.kernel.org/pub/scm/linux/kernel/git/agruen/linux.git/log/?h=bcachefs. Thanks, Andreas
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;
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. Signed-off-by: Andreas Gruenbacher <agruenba@redhat.com> --- fs/bcachefs/util.c | 41 ++++++++++++++++++++++++++++++----------- 1 file changed, 30 insertions(+), 11 deletions(-)