[boost] bug found in boost::intrusive::detail::ihashtable<...>::rehash

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...

Position
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){
                  ++before_i;
                ...  
Needs
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.
http://autos.yahoo.com/new_cars.html