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

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

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

index c8d622a..a39c59b 100644 (file)
@@ -1,3 +1,15 @@
+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>
 
         Unreviewed, rolling out r237479 and r237484.
index 1ca9b86..640cadb 100644 (file)
@@ -386,10 +386,9 @@ namespace WTF {
                 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);
             };
         }
 
index 84d38dd..8e62dc3 100644 (file)
@@ -1,3 +1,15 @@
+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>
 
         [GTK] Add bubblewrap feature option
index d19524c..d4ba35a 100644 (file)
@@ -1013,28 +1013,56 @@ TEST(WTF_HashMap, Random_WrapAround)
     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)
-            ++ones;
+        if (!it->value)
+            ++zeros;
         else {
-            ASSERT_EQ(it->value, 2u);
-            ++twos;
+            ASSERT_EQ(it->value, 1u);
+            ++ones;
         }
     }
 
-    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