verity: handle trees with an odd node count correctly

verity: handle trees with an odd node count correctly

This fixes a bug we were seeing when setting root_depth=3.

BUG=none
TEST=Ran unittests.

Change-Id: I7241ccd97102638e9f003a694280ca0b53f317b9

R=wad@chromium.org

Committed: http://chrome-svn/viewvc/chromeos?view=rev&revision=b691323

[Will Drewry, 2011-03-25 02:52:49]

Nice catch!  I think it's fine to submit as is: LGTM, but it might be possible
to reduce the lengthiness a bit.

Thanks!
will

http://codereview.chromium.org/6742001/diff/1/dm-bht.c
File dm-bht.c (right):

http://codereview.chromium.org/6742001/diff/1/dm-bht.c#newcode848
dm-bht.c:848: if (i == (level->count - 1))
Could this just be:
unsigned int count = child_level->count % bht->node_count;
if (count == 0)
  count = bht->node_count;

?

[Mandeep Singh Baines, 2011-03-25 03:04:39]

On 2011/03/25 02:52:49, Will Drewry wrote:
> Nice catch!  I think it's fine to submit as is: LGTM, but it might be possible
> to reduce the lengthiness a bit.
> 
> Thanks!
> will
> 
> http://codereview.chromium.org/6742001/diff/1/dm-bht.c
> File dm-bht.c (right):
> 
> http://codereview.chromium.org/6742001/diff/1/dm-bht.c#newcode848
> dm-bht.c:848: if (i == (level->count - 1))
> Could this just be:
> unsigned int count = child_level->count % bht->node_count;
> if (count == 0)
>   count = bht->node_count;
> 
> ?

The "i == (level-> count - 1)" is important because its only the last block that
is odd.

You could do this:
                       if ((i == (level->count - 1)) &&
                            (child_level->count % count))
                                count = child_level->count % bht->node_count;


But it means a more complicated expression.

[Will Drewry, 2011-03-25 03:08:50]

On 2011/03/25 03:04:39, Mandeep Singh Baines wrote:
> On 2011/03/25 02:52:49, Will Drewry wrote:
> > Nice catch!  I think it's fine to submit as is: LGTM, but it might be
possible
> > to reduce the lengthiness a bit.
> > 
> > Thanks!
> > will
> > 
> > http://codereview.chromium.org/6742001/diff/1/dm-bht.c
> > File dm-bht.c (right):
> > 
> > http://codereview.chromium.org/6742001/diff/1/dm-bht.c#newcode848
> > dm-bht.c:848: if (i == (level->count - 1))
> > Could this just be:
> > unsigned int count = child_level->count % bht->node_count;
> > if (count == 0)
> >   count = bht->node_count;
> > 
> > ?
> 
> The "i == (level-> count - 1)" is important because its only the last block
that
> is odd.
> 
> You could do this:
>                        if ((i == (level->count - 1)) &&
>                             (child_level->count % count))
>                                 count = child_level->count % bht->node_count;
> 
> 
> But it means a more complicated expression.

Yup - that means that every "full" count up to the last one will cause count to
be == 0, and then be set to bht->node_count.  It's unpossible for the
level->count to be != bht->node_count if there is an adjacent, trailing node.

But either way is fine with me, I was just trying to simplify it a little.

thanks!