Bug 130509 – HashTable::add() works wrong when inserting of an empty value causes rehash

• Status: RESOLVED
• Resolution: INVALID
• Component: Web Template Framework

[Mikhail Pozdnyakov]

HashTable::rehash() always skips re-inserting of an empty entry, this causes wrong result of the parent HashTable::add() call i.e. map.add( empty value ).iterator.get() == nullptr.

[Mikhail Pozdnyakov]

Created attachment 227288 [details]
patch

[Darin Adler]

Comment on attachment 227288 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=227288&action=review

> Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp:158
> +    ASSERT_TRUE(map.add(0, 0).iterator.get());

This doesn’t look right. We don’t support adding map entries where the key has the empty or deleted value. And 0 is the empty value from HashTraits<int>. So calling add(0, 0) is illegal and should cause an assertion in a debug build and undefined behavior in a release build.

[Mikhail Pozdnyakov]

(In reply to comment #2)
> (From update of attachment 227288 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=227288&action=review
> 
> > Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp:158
> > +    ASSERT_TRUE(map.add(0, 0).iterator.get());
> 
> This doesn’t look right. We don’t support adding map entries where the key has the empty or deleted value. And 0 is the empty value from HashTraits<int>. So calling add(0, 0) is illegal and should cause an assertion in a debug build and undefined behavior in a release build.

Ah, I see. Thanks for clarification. Does it depend however on whether 'HashFunctions::safeToCompareToEmptyOrDeleted' is true or false? or we just never expect adding empty values?

[Darin Adler]

Comment on attachment 227288 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=227288&action=review

>>> Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp:158
>>> +    ASSERT_TRUE(map.add(0, 0).iterator.get());
>> 
>> This doesn’t look right. We don’t support adding map entries where the key has the empty or deleted value. And 0 is the empty value from HashTraits<int>. So calling add(0, 0) is illegal and should cause an assertion in a debug build and undefined behavior in a release build.
> 
> Ah, I see. Thanks for clarification. Does it depend however on whether 'HashFunctions::safeToCompareToEmptyOrDeleted' is true or false? or we just never expect adding empty values?

No, it does not depend on that. The empty and deleted values are reserved values, and it’s illegal to use either of them as keys in the map.

HashFunctions::safeToCompareToEmptyOrDeleted is used to control optimizations inside the HashTable template. If it’s false, the template uses a more complex scheme to avoid ever comparing empty and deleted values with the hash function. If it’s true, then the template generates simpler, more efficient code. I’m not sure I remembered that exactly right, but it’s something like that.