Using float/double as WTF hash table key is unreliable.
authorkling@webkit.org <kling@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 8 Oct 2012 14:44:53 +0000 (14:44 +0000)
committerkling@webkit.org <kling@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 8 Oct 2012 14:44:53 +0000 (14:44 +0000)
<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):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@130639 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WTF/ChangeLog
Source/WTF/wtf/HashFunctions.h
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp

index 82247d5..58cffc5 100644 (file)
@@ -1,3 +1,20 @@
+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>
 
         Unreviewed, rolling out r130619.
index eb1b2f0..75fabcd 100644 (file)
@@ -105,16 +105,15 @@ namespace WTF {
     };
 
     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);
+            return intHash(bitwise_cast<Bits>(key));
+        }
+        static bool equal(T a, T b)
+        {
+            return bitwise_cast<Bits>(a) == bitwise_cast<Bits>(b);
         }
-        static bool equal(T a, T b) { return a == b; }
         static const bool safeToCompareToEmptyOrDeleted = true;
     };
 
index 2c86fc3..5e111d5 100644 (file)
@@ -1,3 +1,17 @@
+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>
 
         [EFL][WK2] Use URL instead of URI in the API
index b9f4c1f..e258fd3 100644 (file)
@@ -49,4 +49,30 @@ TEST(WTF, HashTableIteratorComparison)
     ASSERT_FALSE(map.end() == begin);
 }
 
+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