Title: [237476] trunk
- Revision
- 237476
- Author
- [email protected]
- Date
- 2018-10-26 11:58:50 -0700 (Fri, 26 Oct 2018)
Log Message
HashMap should support selecting a random entry
https://bugs.webkit.org/show_bug.cgi?id=190814
Reviewed by Antti Koivisto.
Source/WTF:
* wtf/HashTable.h:
(WTF::HashTable::random):
(WTF::HashTable::random const): Draw a new random bucket any time we
have a miss, to avoid bias caused by lopsided tables.
Tools:
* TestWebKitAPI/Tests/WTF/HashMap.cpp: Updated the Random_IsRandom to
more thoroughly test for randomness.
Modified Paths
Diff
Modified: trunk/Source/WTF/ChangeLog (237475 => 237476)
--- trunk/Source/WTF/ChangeLog 2018-10-26 18:55:45 UTC (rev 237475)
+++ trunk/Source/WTF/ChangeLog 2018-10-26 18:58:50 UTC (rev 237476)
@@ -1,3 +1,15 @@
+2018-10-26 Geoffrey Garen <[email protected]>
+
+ HashMap should support selecting a random entry
+ https://bugs.webkit.org/show_bug.cgi?id=190814
+
+ Reviewed by Antti Koivisto.
+
+ * wtf/HashTable.h:
+ (WTF::HashTable::random):
+ (WTF::HashTable::random const): Draw a new random bucket any time we
+ have a miss, to avoid bias caused by lopsided tables.
+
2018-10-26 Antti Koivisto <[email protected]>
hashSet.remove(hashSet.random()) doesn't build
Modified: trunk/Source/WTF/wtf/HashTable.h (237475 => 237476)
--- trunk/Source/WTF/wtf/HashTable.h 2018-10-26 18:55:45 UTC (rev 237475)
+++ trunk/Source/WTF/wtf/HashTable.h 2018-10-26 18:58:50 UTC (rev 237476)
@@ -384,10 +384,13 @@
{
if (isEmpty())
return end();
- auto it = makeIterator(m_table + (weakRandomUint32() & m_tableSizeMask));
- if (it == end())
- return begin();
- return it;
+
+ while (1) {
+ ValueType* entry = m_table + (weakRandomUint32() & m_tableSizeMask);
+ if (isEmptyBucket(*entry) || isDeletedBucket(*entry))
+ continue;
+ return makeKnownGoodIterator(entry);
+ };
}
const_iterator random() const { return static_cast<const_iterator>(const_cast<HashTable*>(this)->random()); }
Modified: trunk/Tools/ChangeLog (237475 => 237476)
--- trunk/Tools/ChangeLog 2018-10-26 18:55:45 UTC (rev 237475)
+++ trunk/Tools/ChangeLog 2018-10-26 18:58:50 UTC (rev 237476)
@@ -1,3 +1,13 @@
+2018-10-26 Geoffrey Garen <[email protected]>
+
+ HashMap should support selecting a random entry
+ https://bugs.webkit.org/show_bug.cgi?id=190814
+
+ Reviewed by Antti Koivisto.
+
+ * TestWebKitAPI/Tests/WTF/HashMap.cpp: Updated the Random_IsRandom to
+ more thoroughly test for randomness.
+
2018-10-26 Antti Koivisto <[email protected]>
hashSet.remove(hashSet.random()) doesn't build
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp (237475 => 237476)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp 2018-10-26 18:55:45 UTC (rev 237475)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp 2018-10-26 18:58:50 UTC (rev 237476)
@@ -1022,7 +1022,7 @@
unsigned _ones_ = 0;
unsigned twos = 0;
- for (unsigned i = 0; i < 100; ++i) {
+ for (unsigned i = 0; i < 1000; ++i) {
auto it = map.random();
if (it->value == 1)
++ones;
@@ -1032,9 +1032,9 @@
}
}
- ASSERT_EQ(ones + twos, 100u);
- ASSERT_LE(ones, 99u);
- ASSERT_LE(twos, 99u);
+ ASSERT_EQ(ones + twos, 1000u);
+ ASSERT_LE(ones, 600u);
+ ASSERT_LE(twos, 600u);
}
} // namespace TestWebKitAPI
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
