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);
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?)
--
Jim Starkey
President, NimbusDB, Inc.
978 526-1376
