swap() causing inconsistent internal state leading to failure of hashtable resize

[GoogleCodeExporter]

I just upgraded from an older version (1.7, I think) to 1.1.0, and the 
updating dense_hash_set began throwing asserts seemingly randomly. It 
turns out that the new sparse hash code does not support swap(), and 
results in corruption of the internal map/set state. 

In the past, it was enough to call set_xxx_key after each swap call to 
continue to use the same set. However, this is no longer the case. 
The following code is a small sample: 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
        dense_hash_set<uint64_t> test; 
        test.set_deleted_key(-1); 
        test.set_empty_key(0); 

        for(int i = 1; i < 10000; ++i) 
                std::pair<dense_hash_set<uint64_t>::iterator, bool> resultPair = 
test.insert(i); 

        swap(dense_hash_set<uint64_t>(), test); 

        test.set_deleted_key(-1); 
        test.set_empty_key(0); 

        for(int i = 1; i < 10000; ++i) 
                std::pair<dense_hash_set<uint64_t>::iterator, bool> resultPair = 
test.insert(i); 
        return 0; 
} 

Which results in an assertion on line 830 of densehashtable.h 
("Hashtable is full: an error in key_equal<> or hash<>"). It *seems* 
to always occur after 32nd insert, which leads me to believe there's 
an issue growing the hash table after calling swap(). 

Original issue reported on code.google.com by mqu...@gmail.com on 22 Apr 2011 at 9:43

[GoogleCodeExporter]

I finally had a chance to look into this, and it was a typo-bug in swap():
    ht.settings.reset_thresholds(bucket_count());

This should be
    ht.settings.reset_thresholds(ht.bucket_count());

I'm updating the test suite and getting it all code reviewed; I'll get a fix 
out (at least to svn) after that.

Original comment by csilv...@gmail.com on 26 Apr 2011 at 6:38

• Changed state: Fixed
• Added labels: Type-Defect, Priority-Medium

[GoogleCodeExporter]

Original comment by csilv...@gmail.com on 26 Apr 2011 at 6:39

• Changed state: Started

[GoogleCodeExporter]

Thanks, Craig. I looked over the swap() function myself, but completely missed 
that!

Original comment by mqu...@gmail.com on 27 Apr 2011 at 8:46

[GoogleCodeExporter]

This should be fixed in sparsehash 1.11, just released.

Original comment by csilv...@gmail.com on 24 Jun 2011 at 4:43

• Changed state: Fixed