Changeset 237476 in webkit

Timestamp:

Oct 26, 2018 11:58:50 AM (6 years ago)

Author:

ggaren@apple.com

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.

Location:

trunk

Files:

• Source/WTF/ChangeLog (modified) (1 diff)
• Source/WTF/wtf/HashTable.h (modified) (1 diff)
• Tools/ChangeLog (modified) (1 diff)
• Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp (modified) (2 diffs)

trunk/Source/WTF/ChangeLog

@@ +1 @@
+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>
 

trunk/Source/WTF/wtf/HashTable.h

@@ -385 +385 @@
             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);
+            };
         }
 

trunk/Tools/ChangeLog

@@ +1 @@
+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>
 

trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp

@@ -1023 +1023 @@
     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)
@@ -1033 +1033 @@
     }
 
-    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);
 }