HashMap should support selecting a random entry
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 26 Oct 2018 18:58:50 +0000 (18:58 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 26 Oct 2018 18:58:50 +0000 (18:58 +0000)
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.

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

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

index 5c81074..4518b89 100644 (file)
@@ -1,3 +1,15 @@
+2018-10-26  Geoffrey Garen  <ggaren@apple.com>
+
+        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  <antti@apple.com>
 
         hashSet.remove(hashSet.random()) doesn't build
index b8fa7c6..1ca9b86 100644 (file)
@@ -384,10 +384,13 @@ namespace WTF {
         {
             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()); }
index f59c258..fdcfbeb 100644 (file)
@@ -1,3 +1,13 @@
+2018-10-26  Geoffrey Garen  <ggaren@apple.com>
+
+        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  <antti@apple.com>
 
         hashSet.remove(hashSet.random()) doesn't build
index 2e4e76c..d19524c 100644 (file)
@@ -1022,7 +1022,7 @@ TEST(WTF_HashMap, Random_IsRandom)
     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 @@ TEST(WTF_HashMap, Random_IsRandom)
         }
     }
 
-    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