On Sun, Nov 24, 2024 at 8:24 PM Kent Overstreet <[email protected]> wrote: > 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?
Hmm, this actually breaks the following tests in util.c: BUG_ON(eytzinger1_prev(0, size) != eytzinger1_last(size)); BUG_ON(eytzinger0_prev(-1, size) != eytzinger0_last(size)); The inverse tests are fine: BUG_ON(eytzinger1_next(0, size) != eytzinger1_first(size)); BUG_ON(eytzinger0_next(-1, size) != eytzinger0_first(size)); And so are all the other tests. Are those identities actually relevant, or are they just a peculiarity? Do they justify an additional addition in eytzinger1_prev()? Note that these tests rely on the behavior of __fls(0), which is undefined. On x86_64, __fls(0) returns (long unsigned int)-1. Thanks, Andreas
