Title: [130639] trunk
- Revision
- 130639
- Author
- kl...@webkit.org
- Date
- 2012-10-08 07:44:53 -0700 (Mon, 08 Oct 2012)
Log 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):
Modified Paths
Diff
Modified: trunk/Source/WTF/ChangeLog (130638 => 130639)
--- trunk/Source/WTF/ChangeLog 2012-10-08 14:05:10 UTC (rev 130638)
+++ trunk/Source/WTF/ChangeLog 2012-10-08 14:44:53 UTC (rev 130639)
@@ -1,3 +1,20 @@
+2012-10-08 Andreas Kling <kl...@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....@gmail.com>
Unreviewed, rolling out r130619.
Modified: trunk/Source/WTF/wtf/HashFunctions.h (130638 => 130639)
--- trunk/Source/WTF/wtf/HashFunctions.h 2012-10-08 14:05:10 UTC (rev 130638)
+++ trunk/Source/WTF/wtf/HashFunctions.h 2012-10-08 14:44:53 UTC (rev 130639)
@@ -105,16 +105,15 @@
};
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 a == b; }
+ static bool equal(T a, T b)
+ {
+ return bitwise_cast<Bits>(a) == bitwise_cast<Bits>(b);
+ }
static const bool safeToCompareToEmptyOrDeleted = true;
};
Modified: trunk/Tools/ChangeLog (130638 => 130639)
--- trunk/Tools/ChangeLog 2012-10-08 14:05:10 UTC (rev 130638)
+++ trunk/Tools/ChangeLog 2012-10-08 14:44:53 UTC (rev 130639)
@@ -1,3 +1,17 @@
+2012-10-08 Andreas Kling <kl...@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.du...@intel.com>
[EFL][WK2] Use URL instead of URI in the API
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp (130638 => 130639)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp 2012-10-08 14:05:10 UTC (rev 130638)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp 2012-10-08 14:44:53 UTC (rev 130639)
@@ -49,4 +49,30 @@
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
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
http://lists.webkit.org/mailman/listinfo/webkit-changes
