-
Notifications
You must be signed in to change notification settings - Fork 261
Description
Hi there. Was testing dense_hash_map and found it would hang on a certain test configuration
Load factor = 1
Completely fill map with items
delete an item
find() for that item
The find() should return failure but find_position never exits. It seems that find_position (in densehashtable) only exits when it finds the item or finds an empty item. If all items are either deleted or existing then it will never exit.
Now I'm not sure if the intention is to ensure there are always empty items by having more buckets than items (Never actually being loadfactor=1), or if it's an issue with find_position that needs to take into account hash tables full of only deleted and valid items. My fix took the latter approach
Below is one way to reproduce the error.
GOOGLE_NAMESPACE::dense_hash_map<int, int> google_dense;
google_dense.set_empty_key(0);
google_dense.set_deleted_key(1);
google_dense.max_load_factor(1);
size_t bc = google_dense.bucket_count();
for (int t = 0; t < bc; ++t)
{
google_dense.insert({ t + 2, t });
}
google_dense.erase(2);
google_dense.find(2);
My fix was to insert after ++num_probes the following. This may or may not suit the aims of the container in general
// We've searched everything, not found it, but we did find a deleted bucket.
if (num_probes == bucket_count() && insert_pos != ILLEGAL_BUCKET)
{
return std::pair<size_type, size_type>(ILLEGAL_BUCKET, insert_pos);
}