Changeset 237522 in webkit

Timestamp:

Oct 28, 2018 11:18:57 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 Ryosuke Niwa.

Source/WTF:

• wtf/HashTable.h:

(WTF::HashTable::random):
(WTF::HashTable::random const): Merge the empty and deleted checks, and
use more idiomatic addressing.

Tools:

• 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.

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) (1 diff)

trunk/Source/WTF/ChangeLog

@@ +1 @@
+2018-10-28  Geoffrey Garen  <ggaren@apple.com>
+
+        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  <commit-queue@webkit.org>
 

trunk/Source/WTF/wtf/HashTable.h

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

trunk/Tools/ChangeLog

@@ +1 @@
+2018-10-28  Geoffrey Garen  <ggaren@apple.com>
+
+        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  <cturner@igalia.com>
 

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

@@ -1014 +1014 @@
 }
 
-TEST(WTF_HashMap, Random_IsRandom)
-{
-    HashMap<unsigned, unsigned> map;
+TEST(WTF_HashMap, Random_IsEvenlyDistributed)
+{
+    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);
+    }
 }