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]> --- 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
