Modified: trunk/Source/WTF/ChangeLog (237521 => 237522)
--- trunk/Source/WTF/ChangeLog 2018-10-28 14:34:13 UTC (rev 237521)
+++ trunk/Source/WTF/ChangeLog 2018-10-28 18:18:57 UTC (rev 237522)
@@ -1,3 +1,15 @@
+2018-10-28 Geoffrey Garen <[email protected]>
+
+ HashMap should support selecting a random entry
+ https://bugs.webkit.org/show_bug.cgi?id=190814
+
+ Reviewed by Ryosuke Niwa.
+
+ * wtf/HashTable.h:
+ (WTF::HashTable::random):
+ (WTF::HashTable::random const): Merge the empty and deleted checks, and
+ use more idiomatic addressing.
+
2018-10-26 Commit Queue <[email protected]>
Unreviewed, rolling out r237479 and r237484.
Modified: trunk/Source/WTF/wtf/HashTable.h (237521 => 237522)
--- trunk/Source/WTF/wtf/HashTable.h 2018-10-28 14:34:13 UTC (rev 237521)
+++ trunk/Source/WTF/wtf/HashTable.h 2018-10-28 18:18:57 UTC (rev 237522)
@@ -386,10 +386,9 @@
return end();
while (1) {
- ValueType* entry = m_table + (weakRandomUint32() & m_tableSizeMask);
- if (isEmptyBucket(*entry) || isDeletedBucket(*entry))
- continue;
- return makeKnownGoodIterator(entry);
+ auto& bucket = m_table[weakRandomUint32() & m_tableSizeMask];
+ if (!isEmptyOrDeletedBucket(bucket))
+ return makeKnownGoodIterator(&bucket);
};
}
Modified: trunk/Tools/ChangeLog (237521 => 237522)
--- trunk/Tools/ChangeLog 2018-10-28 14:34:13 UTC (rev 237521)
+++ trunk/Tools/ChangeLog 2018-10-28 18:18:57 UTC (rev 237522)
@@ -1,3 +1,15 @@
+2018-10-28 Geoffrey Garen <[email protected]>
+
+ HashMap should support selecting a random entry
+ https://bugs.webkit.org/show_bug.cgi?id=190814
+
+ Reviewed by Ryosuke Niwa.
+
+ * TestWebKitAPI/Tests/WTF/HashMap.cpp: Renamed IsRandom to
+ IsEvenlyDistributed to reflect the fact that we're only testing the
+ distribution. Added a test case that covers more table densities and
+ the remove() operation.
+
2018-10-27 Charlie Turner <[email protected]>
[GTK] Add bubblewrap feature option
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp (237521 => 237522)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp 2018-10-28 14:34:13 UTC (rev 237521)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp 2018-10-28 18:18:57 UTC (rev 237522)
@@ -1013,28 +1013,56 @@
ASSERT_EQ(result, map.begin());
}
-TEST(WTF_HashMap, Random_IsRandom)
+TEST(WTF_HashMap, Random_IsEvenlyDistributed)
{
- HashMap<unsigned, unsigned> map;
+ HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> map;
+ map.add(0, 0);
map.add(1, 1);
- map.add(2, 2);
+ unsigned zeros = 0;
unsigned _ones_ = 0;
- unsigned twos = 0;
for (unsigned i = 0; i < 1000; ++i) {
auto it = map.random();
- if (it->value == 1)
+ if (!it->value)
+ ++zeros;
+ else {
+ ASSERT_EQ(it->value, 1u);
++ones;
- else {
- ASSERT_EQ(it->value, 2u);
- ++twos;
}
}
- ASSERT_EQ(ones + twos, 1000u);
+ ASSERT_EQ(zeros + ones, 1000u);
+ ASSERT_LE(zeros, 600u);
ASSERT_LE(ones, 600u);
- ASSERT_LE(twos, 600u);
}
+TEST(WTF_HashMap, Random_IsEvenlyDistributedAfterRemove)
+{
+ for (size_t tableSize = 2; tableSize <= 2 * 6; ++tableSize) { // Our hash tables shrink at a load factor of 1 / 6.
+ HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> map;
+ for (size_t i = 0; i < tableSize; ++i)
+ map.add(i, i);
+ for (size_t i = 2; i < tableSize; ++i)
+ map.remove(i);
+
+ unsigned zeros = 0;
+ unsigned _ones_ = 0;
+
+ for (unsigned i = 0; i < 1000; ++i) {
+ auto it = map.random();
+ if (!it->value)
+ ++zeros;
+ else {
+ ASSERT_EQ(it->value, 1u);
+ ++ones;
+ }
+ }
+
+ ASSERT_EQ(zeros + ones, 1000u);
+ ASSERT_LE(zeros, 600u);
+ ASSERT_LE(ones, 600u);
+ }
+}
+
} // namespace TestWebKitAPI
