Changeset 130639 in webkit

Timestamp:

Oct 8, 2012, 7:44:53 AM (14 years ago)

Author:

kling@webkit.org

Message:

Using float/double as WTF hash table key is unreliable.
<​http://webkit.org/b/98627>

Reviewed by Geoffrey Garen.

Source/WTF:

Change FloatHash::equal() to do a bitwise compare instead of a logical compare.
This fixes a problem where the keys with different binary representation but the
same logical value (e.g 0 and -0) could block each other from being found if they
ended up in the same hash bucket.

• wtf/HashFunctions.h:

(FloatHash):
(WTF::FloatHash::hash):
(WTF::FloatHash::equal):

Tools:

Add a test case checking that using double as the hash table key type won't
have problems distinguishing between keys that are considered equal by operator==
but have different binary representations.

• TestWebKitAPI/Tests/WTF/HashMap.cpp:

(TestDoubleHashTraits):

Location:

trunk

Files:

• Source/WTF/ChangeLog (modified) (1 diff)
• Source/WTF/wtf/HashFunctions.h (modified) (1 diff)
• Tools/ChangeLog (modified) (1 diff)
• Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp (modified) (1 diff)

trunk/Source/WTF/ChangeLog

@@ +1 @@
+2012-10-08  Andreas Kling  <kling@webkit.org>
+
+        Using float/double as WTF hash table key is unreliable.
+        <http://webkit.org/b/98627>
+
+        Reviewed by Geoffrey Garen.
+
+        Change FloatHash::equal() to do a bitwise compare instead of a logical compare.
+        This fixes a problem where the keys with different binary representation but the
+        same logical value (e.g 0 and -0) could block each other from being found if they
+        ended up in the same hash bucket.
+
+        * wtf/HashFunctions.h:
+        (FloatHash):
+        (WTF::FloatHash::hash):
+        (WTF::FloatHash::equal):
+
 2012-10-08  Sheriff Bot  <webkit.review.bot@gmail.com>
 

trunk/Source/WTF/wtf/HashFunctions.h

@@ -106 +106 @@
 
     template<typename T> struct FloatHash {
+        typedef typename IntTypes<sizeof(T)>::UnsignedType Bits;
         static unsigned hash(T key)
         {
-            union {
-                T key;
-                typename IntTypes<sizeof(T)>::UnsignedType bits;
-            } u;
-            u.key = key;
-            return intHash(u.bits);
-        }
-        static bool equal(T a, T b) { return a == b; }
+            return intHash(bitwise_cast<Bits>(key));
+        }
+        static bool equal(T a, T b)
+        {
+            return bitwise_cast<Bits>(a) == bitwise_cast<Bits>(b);
+        }
         static const bool safeToCompareToEmptyOrDeleted = true;
     };

trunk/Tools/ChangeLog

@@ +1 @@
+2012-10-08  Andreas Kling  <kling@webkit.org>
+
+        Using float/double as WTF hash table key is unreliable.
+        <http://webkit.org/b/98627>
+
+        Reviewed by Geoffrey Garen.
+
+        Add a test case checking that using double as the hash table key type won't
+        have problems distinguishing between keys that are considered equal by operator==
+        but have different binary representations.
+
+        * TestWebKitAPI/Tests/WTF/HashMap.cpp:
+        (TestDoubleHashTraits):
+
 2012-10-08  Christophe Dumez  <christophe.dumez@intel.com>
 

trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp

@@ -50 +50 @@
 }
 
+struct TestDoubleHashTraits : HashTraits<double> {
+    static const int minimumTableSize = 8;
+};
+
+typedef HashMap<double, int64_t, DefaultHash<double>::Hash, TestDoubleHashTraits> DoubleHashMap;
+
+TEST(WTF, DoubleHashCollisions)
+{
+    // The "clobber" key here is one that ends up stealing the bucket that the -0 key
+    // originally wants to be in. This makes the 0 and -0 keys collide and the test then
+    // fails unless the FloatHash::equals() implementation can distinguish them.
+    const double clobberKey = 6;
+    const double zeroKey = 0;
+    const double negativeZeroKey = -zeroKey;
+
+    DoubleHashMap map;
+
+    map.add(clobberKey, 1);
+    map.add(zeroKey, 2);
+    map.add(negativeZeroKey, 3);
+
+    ASSERT_EQ(map.get(clobberKey), 1);
+    ASSERT_EQ(map.get(zeroKey), 2);
+    ASSERT_EQ(map.get(negativeZeroKey), 3);
+}
+
 } // namespace TestWebKitAPI