Oh, thanks!! Mea culpa. All you say is quite correct. As for (c), I
think it's slightly better to skip the first initialization (in the
ctor), setting an "Uninitialized" flag instead, and only initialize the
table in prepareForRun().
Would you mind being listed among the contributors in hash.cpp?
Thanks again for this great help.
Tom Kaiser
Tom Moog wrote:
> Hello,
>
> There appears to be an error in HashTable::expandWatching in hash.cpp.
>
> This problem can be reproduced by setting the initial value of the
> dictionary
> (#define PROC_DICTIONARY_LOGSIZE in proc.h) to some very small value
> (e.g. 4) in order to force the hash table to be resized by even a small test
> case.
>
> There are actually three bugs.
>
> (a) if an item which is not the final item in the old bucket is moved to the
> new bucket in the upper half AND it is the final item in the new bucket then
> its next pointer is left pointing to the item which followed it in the old
> bucket.
>
> (b) if all the items in an old bucket are moved to a new bucket then the old
> bucket's pointer is never reset to NULL, so it will point to the head of the
> items in the new bucket.
>
> (c) When (a) and (b) are fixed one discovers that the dictionary is
> initialized
> twice - once by the ctor and once by prepareForRun(). The double
> initialization causes twice as many buckets to be allocated as expected
> so that logSize and bucketCount are out of sync and this causes
> expandWatching to place the new items in the wrong bucket.
>
> Fix for (c) in proc.cpp:prepareForRun() near line 202:
> ------------------------------------------------------------------------
> old: dictionary.initialize();
> new: dictionary.destroy(); dictionary.initialize();
>
> Fix for (a) and (b) in hash.cpp:expandWatching near line 186:
> ----------------------------------------------------------------------------
> -------
> for (i = 0; i < oldBucketCount; i++)
> {
> upperTail = lowerTail = NULL;
> for (p = buckets[i]; p; p = p->next)
> {
> if (p -> code & distinguish)
> chain(p, upperTail, i + oldBucketCount)
> else
> chain(p, lowerTail, i);
> };
> if (lowerTail == NULL) {
> buckets[i] = NULL;
> }
> else {
> lowerTail->next = NULL;
> }
> if (upperTail != NULL) upperTail->next = NULL;
>
>
>
>
>
>
>
>
