Boost logo

Boost :

From: Yoni Lavi (l_yoni_at_[hidden])
Date: 2007-06-10 16:04:29

<!-- DIV {margin:0px;}-->NOTE: I cross-posted this through gmane.comp.lib.boost.devel, I have no idea which is the correct group to post in - I rather have the gmane copy deleted if I should have posted it in here. I also made a minor correction to my post. Anyway...

of a contained element modulo m (new_buckets_len) is known to remain
equal to its previous position modulo n (old_buckets_len) ONLY IF m
< n AND n %m == 0, but the latter condition isn't being checked. The
code assumes it can skip rehashing of m first buckets if m < n:

         //If we are shrinking the bucket array, just rehash the last nodes
         if(same_buffer && (old_buckets_len > new_buckets_len)){
            n = new_buckets_len;
             //Iterate through nodes
 for(; n < old_buckets_len; ++n){

Also, the following comment:
               //If this is a buffer expansion don't move if it's not necessary
               if(same_buffer && new_n == n){
to be changed simply to "don't move if it's not necessary" - it needs
to be checked/may happen when shrinking the hash table also.

Here's a suggested bugfix:
- check if (old_bucket_len > new_buckets_len && 0 == old_bucket_len % new_buckets_len).
    if true, i'th bucket needs to store the contents of all previous
buckets at positions i + j*new_buckets_len for j in [0, old_buckets_len
/ new_buckets_len) spliced one after another. There is no need to check
on a per-element basis. I believe this optimization should be done even
when the rehash isn't in-place. A special case where this optimization
is useful is when using power-of-2 num_buckets.
   if false, buckets have to be re-scanned, using the existing code in
the body of the existing loop, but starting from n = 0 always:
         for(; n < old_buckets_len; ++n){ ... }

Please correct me if I'm wrong on this.. but just to be sure, I made a
test program that verified rehash() can break the container's invariants when shrinking the container's bucket array in place,
which was indeed found to be the case.

Don't pick lemons.
See all the new 2007 cars at Yahoo! Autos.

Boost list run by bdawes at, gregod at, cpdaniel at, john at