Jim Starkey wrote:
> Last week Kevin claimed he saw a bug in Bitmap.cpp. He did, but his
> description missed the edge case. This raises two questions. One is
> what was the bug. The other is why it went undiscovered for so long.
>
> The actual bug is in Bitmap::nextSet. The bitmap is actually a fixed
> width, variable depth free of bitmap segments, each containing 32 words
> of 32 bit. The operating starts by decomposing the start bit number
> into a vector of indexes, where index[0] is the bit number, index[1] is
> clump (i.e. word) number, index[2] is the slot into a first level vector
> of bitmap segments pointers, etc. The bug is around line 247:
>
> for (index = indexes[lvl]; index < BITMAP_VECTOR_SIZE &&
> !vec [index]; ++index)
> ;
>
> where the method is looking for a non-null pointer to a bitmap segment.
> In specific, the bug is the failure to reset the bit number and clump
> number to zero before checking the next bitmap segment. The code should
> have been something like:
>
> for (index = indexes[lvl]; index < BITMAP_VECTOR_SIZE &&
> !vec [index]; ++index)
> for (int n = 0; n < lvl; ++n)
> indexes[n] = 0;
>
> The reason why this ugliness hasn't reared it head in the past is a
> slight different in bitmap searching code. Other code has typically
> been of the form:
>
> for (int n = 0; (n = bitmap->nextSet(n)) >= 0; ++n)
> yada yada yada
>
> where next bit number of bumped to avoid a wasted nano-second skipped
> over an already processed number (also to avoid infinite loop in the
> non-destructive case). Chris, I believe, code his loop something like:
>
> for (int n = 0; (n = bitmap->nextSet(n)) >= 0;)
> ...
> bitmap->clear(n);
I remember this! It seemed a bit 'spendy' to manually clear each bitmap.
I should've challenged the design.
Don't we need a destructive *and* non-desctructive nextSet()?
> Now, if Chris had done a minisculy more efficient coding and / or Kevin
> had been less diligent in running bugs to earth, we wouldn't have caught
> this.
>
> So, Kevin 1, Chris 1, Jim 0.
>
> (Kevin, can I drop this on you?)
>
