On Sun, Nov 24, 2024 at 02:11:47PM +0100, Andreas Gruenbacher wrote:
> From: Andreas Gruenbacher <[email protected]>
>
> In this place in the code, eytzinger1_next() is trying to move the
> lowest child on the left, which is equivalent to doubling i until the
> next doubling would cause it to be greater than size. This is
> implemented by shifting i to the left so that the most significant bits
> of both numbers align, and then shifting i right by one if it is greater
> than size.
>
> The code accidentally computes the most significant bit of (size + 1)
> instead of size. This happens to be harmless because in that case, the
> right shifting will compensate, but it is confusing and unnecessary.
>
> Likewise, eytzinger1_prev() is trying to move the lowest child on the
> right. The same applies here.
>
> Signed-off-by: Andreas Gruenbacher <[email protected]>
Looks correct. There's eytzinger tests in fs/bcachefs/util.c, could you
run those?
If you're doing any more work with the eytzinger code we could also turn
those tests into more standard unit tests, right now there's no harness
to drive them.
> ---
> fs/bcachefs/eytzinger.h | 4 ++--
> 1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h
> index 0541192d7bc0..9fa63a624c92 100644
> --- a/fs/bcachefs/eytzinger.h
> +++ b/fs/bcachefs/eytzinger.h
> @@ -73,7 +73,7 @@ static inline unsigned eytzinger1_next(unsigned i, unsigned
> size)
> if (eytzinger1_right_child(i) <= size) {
> i = eytzinger1_right_child(i);
>
> - i <<= __fls(size + 1) - __fls(i);
> + i <<= __fls(size) - __fls(i);
> i >>= i > size;
> } else {
> i >>= ffz(i) + 1;
> @@ -89,7 +89,7 @@ static inline unsigned eytzinger1_prev(unsigned i, unsigned
> size)
> if (eytzinger1_left_child(i) <= size) {
> i = eytzinger1_left_child(i) + 1;
>
> - i <<= __fls(size + 1) - __fls(i);
> + i <<= __fls(size) - __fls(i);
> i -= 1;
> i >>= i > size;
> } else {
> --
> 2.46.2
>
