Add WeakHashSet
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 4 Mar 2019 21:52:32 +0000 (21:52 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 4 Mar 2019 21:52:32 +0000 (21:52 +0000)
https://bugs.webkit.org/show_bug.cgi?id=195152

Reviewed by Antti Koivisto.

Source/WTF:

Added WeakHashSet which is a HashSet of WeakPtr. When the object pointed by WeakPtr is deleted,
WeakHashSet treats the key to be no longer in the set. That is, WeakHashSet::contains returns false
and const_iterator skips such a WeakPtr in the set.

We decided not to make HashSet<WeahPtr<T>> work because it involves weird semantics such as making
find(X) delete the table entry as remove(find(X)) would be a no-op otherwise as find(X) would return
necessarily need to return HashSet<WeakPtr<T>>::end().

Furthermore, we cannot determine the true size of this set in O(1) because the objected pointed by
some of WeakPtr in the set may have already been deleted. This has implications that we can't have
size(), isEmpty(), random(), etc... as O(1) operation.

WeakHashSet is implemented as HashSet<WeakReference<T>>. HashTable::rehash has been updated to delete
WeakReference<T>'s whose m_ptr has become null, and HashTable::expand first deletes any such entry
before deciding an actual expansion is needed. This is accomplished via newly added hash trait,
hasIsReleasedWeakValueFunction, and HashTraits<Ref<WeakReference<T>>>::isReleasedWeakValue which
returns true for when WeakReference<T> pointed by Ref<WeakReference<T>> has null m_ptr, not to be
confused with Ref<WeakReference<T>> itself pointing to a null WeakReference<T>.

* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/Forward.h:
* wtf/HashSet.h:
(WTF::HashSet<T, U, V>::checkConsistency const): Added.
* wtf/HashTable.h:
(WTF::HashTable::isReleasedWeakBucket): Added.
(WTF::HashTable::expand): Delete WeakReference<T> with null m_ptr first. This updates m_keyCount
and may make mustRehashInPlace() return true.
(WTF::HashTable::deleteReleasedWeakBuckets): Added.
(WTF::HashTable::rehash): Delete WeakReference<T> with null m_ptr. Also refactored the code a bit
to avoid keep repeating oldTable[i].
* wtf/HashTraits.h:
(WTF::HashTraits<T>::isHashTraitsReleasedWeakValue): Added.
(WTF::RefHashTraits<T>): Extracted from HashTraits<Ref<P>> to share code with
HashTraits<Ref<WeakReference<T>>>.
(WTF::HashTraitsReleasedWeakValueChecker<Traits, hasIsReleasedWeakValueFunction>): Added.
(WTF::isHashTraitsReleasedWeakValue<Traits, hasIsReleasedWeakValueFunction>): Added.
* wtf/WeakHashSet.h: Added.
(WTF::WeakHashSet): Added.
(WTF::WeakHashSet::WeakHashSetConstIterator::WeakHashSetConstIterator):
(WTF::WeakHashSet::WeakHashSetConstIterator::get const):
(WTF::WeakHashSet::WeakHashSetConstIterator::operator* const):
(WTF::WeakHashSet::WeakHashSetConstIterator::operator-> const):
(WTF::WeakHashSet::WeakHashSetConstIterator::operator++):
(WTF::WeakHashSet::WeakHashSetConstIterator::skipEmptyBuckets):
(WTF::WeakHashSet::WeakHashSetConstIterator::operator== const):
(WTF::WeakHashSet::WeakHashSetConstIterator::operator!= const):
(WTF::WeakHashSet::WeakHashSet):
(WTF::WeakHashSet::begin const):
(WTF::WeakHashSet::end const):
(WTF::WeakHashSet::add):
(WTF::WeakHashSet::remove):
(WTF::WeakHashSet::contains const):
(WTF::WeakHashSet::capacity const):
(WTF::WeakHashSet::computeSize const): Deletes any WeakReference<T> with null m_ptr first.
(WTF::WeakHashSet::checkConsistency const):
(WTF::HashTraits<Ref<WeakReference<T>>>): Added. This hash traits triggers the new code in HashTable's
expand and rehash methods to delete WeakReference<T> with null m_ptr.
(WTF::HashTraits<Ref<WeakReference<T>>>::isReleasedWeakValue):
* wtf/WeakPtr.h:
(WTF::WeakReference::~WeakReference): Added so that we can keep track the number of live WeakReference
in API tests by template specializations.

Tools:

Added tests for WeakHashSet.

* TestWebKitAPI/Tests/WTF/WeakPtr.cpp:
(TestWebKitAPI::Base::Base): Moved.
(TestWebKitAPI::Derived::foo): Moved.
(WTF::WeakReference<TestWebKitAPI::Base>): Added to track the number of live WeakReference.
(WTF::WeakReference<TestWebKitAPI::Base>::WeakReference):
(WTF::WeakReference<TestWebKitAPI::Base>::~WeakReference):
(TestWebKitAPI::computeSizeOfWeakHashSet): Added.

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

Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/Forward.h
Source/WTF/wtf/HashSet.h
Source/WTF/wtf/HashTable.h
Source/WTF/wtf/HashTraits.h
Source/WTF/wtf/WeakHashSet.h [new file with mode: 0644]
Source/WTF/wtf/WeakPtr.h
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/WeakPtr.cpp

index fc430ce..1a9b19d 100644 (file)
@@ -1,3 +1,73 @@
+2019-02-28  Ryosuke Niwa  <rniwa@webkit.org>
+
+        Add WeakHashSet
+        https://bugs.webkit.org/show_bug.cgi?id=195152
+
+        Reviewed by Antti Koivisto.
+
+        Added WeakHashSet which is a HashSet of WeakPtr. When the object pointed by WeakPtr is deleted,
+        WeakHashSet treats the key to be no longer in the set. That is, WeakHashSet::contains returns false
+        and const_iterator skips such a WeakPtr in the set.
+
+        We decided not to make HashSet<WeahPtr<T>> work because it involves weird semantics such as making
+        find(X) delete the table entry as remove(find(X)) would be a no-op otherwise as find(X) would return
+        necessarily need to return HashSet<WeakPtr<T>>::end().
+
+        Furthermore, we cannot determine the true size of this set in O(1) because the objected pointed by
+        some of WeakPtr in the set may have already been deleted. This has implications that we can't have
+        size(), isEmpty(), random(), etc... as O(1) operation.
+
+        WeakHashSet is implemented as HashSet<WeakReference<T>>. HashTable::rehash has been updated to delete
+        WeakReference<T>'s whose m_ptr has become null, and HashTable::expand first deletes any such entry
+        before deciding an actual expansion is needed. This is accomplished via newly added hash trait,
+        hasIsReleasedWeakValueFunction, and HashTraits<Ref<WeakReference<T>>>::isReleasedWeakValue which
+        returns true for when WeakReference<T> pointed by Ref<WeakReference<T>> has null m_ptr, not to be
+        confused with Ref<WeakReference<T>> itself pointing to a null WeakReference<T>.
+
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/CMakeLists.txt:
+        * wtf/Forward.h:
+        * wtf/HashSet.h:
+        (WTF::HashSet<T, U, V>::checkConsistency const): Added.
+        * wtf/HashTable.h:
+        (WTF::HashTable::isReleasedWeakBucket): Added.
+        (WTF::HashTable::expand): Delete WeakReference<T> with null m_ptr first. This updates m_keyCount
+        and may make mustRehashInPlace() return true.
+        (WTF::HashTable::deleteReleasedWeakBuckets): Added.
+        (WTF::HashTable::rehash): Delete WeakReference<T> with null m_ptr. Also refactored the code a bit
+        to avoid keep repeating oldTable[i].
+        * wtf/HashTraits.h:
+        (WTF::HashTraits<T>::isHashTraitsReleasedWeakValue): Added.
+        (WTF::RefHashTraits<T>): Extracted from HashTraits<Ref<P>> to share code with
+        HashTraits<Ref<WeakReference<T>>>.
+        (WTF::HashTraitsReleasedWeakValueChecker<Traits, hasIsReleasedWeakValueFunction>): Added.
+        (WTF::isHashTraitsReleasedWeakValue<Traits, hasIsReleasedWeakValueFunction>): Added.
+        * wtf/WeakHashSet.h: Added.
+        (WTF::WeakHashSet): Added.
+        (WTF::WeakHashSet::WeakHashSetConstIterator::WeakHashSetConstIterator):
+        (WTF::WeakHashSet::WeakHashSetConstIterator::get const):
+        (WTF::WeakHashSet::WeakHashSetConstIterator::operator* const):
+        (WTF::WeakHashSet::WeakHashSetConstIterator::operator-> const):
+        (WTF::WeakHashSet::WeakHashSetConstIterator::operator++):
+        (WTF::WeakHashSet::WeakHashSetConstIterator::skipEmptyBuckets):
+        (WTF::WeakHashSet::WeakHashSetConstIterator::operator== const):
+        (WTF::WeakHashSet::WeakHashSetConstIterator::operator!= const):
+        (WTF::WeakHashSet::WeakHashSet):
+        (WTF::WeakHashSet::begin const):
+        (WTF::WeakHashSet::end const):
+        (WTF::WeakHashSet::add):
+        (WTF::WeakHashSet::remove):
+        (WTF::WeakHashSet::contains const):
+        (WTF::WeakHashSet::capacity const):
+        (WTF::WeakHashSet::computeSize const): Deletes any WeakReference<T> with null m_ptr first.
+        (WTF::WeakHashSet::checkConsistency const):
+        (WTF::HashTraits<Ref<WeakReference<T>>>): Added. This hash traits triggers the new code in HashTable's
+        expand and rehash methods to delete WeakReference<T> with null m_ptr.
+        (WTF::HashTraits<Ref<WeakReference<T>>>::isReleasedWeakValue):
+        * wtf/WeakPtr.h:
+        (WTF::WeakReference::~WeakReference): Added so that we can keep track the number of live WeakReference
+        in API tests by template specializations.
+
 2019-03-03  Darin Adler  <darin@apple.com>
 
         Prepare to improve handling of conversion of float to strings
index 0da16bf..4909afa 100644 (file)
                93F1993D19D7958D00C2390B /* StringView.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StringView.cpp; sourceTree = "<group>"; };
                974CFC8D16A4F327006D5404 /* WeakPtr.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakPtr.h; sourceTree = "<group>"; };
                996B17841EBA441C007E10EB /* DebugUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DebugUtilities.h; sourceTree = "<group>"; };
+               9B67F3F12228D5310030DE9C /* WeakHashSet.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = WeakHashSet.h; sourceTree = "<group>"; };
                9BC70F04176C379D00101DEC /* AtomicStringTable.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AtomicStringTable.cpp; sourceTree = "<group>"; };
                9BD8F40A176C2AD80002D865 /* AtomicStringTable.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = AtomicStringTable.h; sourceTree = "<group>"; };
                9C67C542589348E285B49699 /* IndexedContainerIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexedContainerIterator.h; sourceTree = "<group>"; };
                                A8A47372151A825B004123FF /* VMTags.h */,
                                0F66B2881DC97BAB004A1D3F /* WallTime.cpp */,
                                0F66B2891DC97BAB004A1D3F /* WallTime.h */,
+                               9B67F3F12228D5310030DE9C /* WeakHashSet.h */,
                                83ABB3C020B3823200BA3306 /* WeakObjCPtr.h */,
                                974CFC8D16A4F327006D5404 /* WeakPtr.h */,
                                0F3501631BB258C800F0A2A3 /* WeakRandom.h */,
index 27ef231..4e1f878 100644 (file)
@@ -258,6 +258,7 @@ set(WTF_PUBLIC_HEADERS
     VectorTraits.h
     WTFSemaphore.h
     WallTime.h
+    WeakHashSet.h
     WeakPtr.h
     WeakRandom.h
     WindowsExtras.h
index b83997c..9386b6e 100644 (file)
@@ -59,6 +59,7 @@ template<typename T, typename = DumbPtrTraits<T>> class Ref;
 template<typename T, typename = DumbPtrTraits<T>> class RefPtr;
 template<typename> class StringBuffer;
 template<typename, typename = void> class StringTypeAdapter;
+template<typename T> class WeakPtr;
 
 template<typename> struct DefaultHash { using Hash = void; };
 template<typename> struct HashTraits;
index a78a88c..afbf70a 100644 (file)
@@ -127,6 +127,8 @@ public:
     template<typename OtherCollection>
     bool operator!=(const OtherCollection&) const;
 
+    void checkConsistency() const;
+
 private:
     HashTableType m_impl;
 };
@@ -382,6 +384,12 @@ void HashSet<T, U, V>::add(std::initializer_list<std::reference_wrapper<const Va
         add(value);
 }
 
+template<typename T, typename U, typename V>
+inline void HashSet<T, U, V>::checkConsistency() const
+{
+    m_impl.checkTableConsistency();
+}
+
 } // namespace WTF
 
 using WTF::HashSet;
index 640cadb..05a9211 100644 (file)
@@ -424,6 +424,7 @@ namespace WTF {
         void clear();
 
         static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
+        static bool isReleasedWeakBucket(const ValueType& value) { return isHashTraitsReleasedWeakValue<KeyTraits>(Extractor::extract(value)); }
         static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
         static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
 
@@ -469,6 +470,8 @@ namespace WTF {
         ValueType* expand(ValueType* entry = nullptr);
         void shrink() { rehash(m_tableSize / 2, nullptr); }
 
+        void deleteReleasedWeakBuckets();
+
         ValueType* rehash(unsigned newTableSize, ValueType* entry);
         ValueType* reinsert(ValueType&&);
 
@@ -1178,6 +1181,9 @@ namespace WTF {
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand(ValueType* entry) -> ValueType*
     {
+        if (KeyTraits::hasIsReleasedWeakValueFunction)
+            deleteReleasedWeakBuckets();
+
         unsigned newSize;
         if (m_tableSize == 0)
             newSize = KeyTraits::minimumTableSize;
@@ -1190,6 +1196,19 @@ namespace WTF {
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
+    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deleteReleasedWeakBuckets()
+    {
+        for (unsigned i = 0; i < m_tableSize; ++i) {
+            auto& entry = m_table[i];
+            if (isReleasedWeakBucket(entry)) {
+                deleteBucket(entry);
+                ++m_deletedCount;
+                --m_keyCount;
+            }
+        }
+    }
+
+    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(unsigned newTableSize, ValueType* entry) -> ValueType*
     {
         internalCheckTableConsistencyExceptSize();
@@ -1213,20 +1232,28 @@ namespace WTF {
 
         Value* newEntry = nullptr;
         for (unsigned i = 0; i != oldTableSize; ++i) {
-            if (isDeletedBucket(oldTable[i])) {
-                ASSERT(std::addressof(oldTable[i]) != entry);
+            auto& oldEntry = oldTable[i];
+            if (isDeletedBucket(oldEntry)) {
+                ASSERT(std::addressof(oldEntry) != entry);
                 continue;
             }
 
-            if (isEmptyBucket(oldTable[i])) {
-                ASSERT(std::addressof(oldTable[i]) != entry);
+            if (isEmptyBucket(oldEntry)) {
+                ASSERT(std::addressof(oldEntry) != entry);
                 oldTable[i].~ValueType();
                 continue;
             }
 
-            Value* reinsertedEntry = reinsert(WTFMove(oldTable[i]));
-            oldTable[i].~ValueType();
-            if (std::addressof(oldTable[i]) == entry) {
+            if (isReleasedWeakBucket(oldEntry)) {
+                ASSERT(std::addressof(oldEntry) != entry);
+                oldEntry.~ValueType();
+                --m_keyCount;
+                continue;
+            }
+
+            Value* reinsertedEntry = reinsert(WTFMove(oldEntry));
+            oldEntry.~ValueType();
+            if (std::addressof(oldEntry) == entry) {
                 ASSERT(!newEntry);
                 newEntry = reinsertedEntry;
             }
@@ -1381,11 +1408,12 @@ namespace WTF {
                 continue;
             }
 
-            const_iterator it = find(Extractor::extract(*entry));
+            auto& key = Extractor::extract(*entry);
+            const_iterator it = find(key);
             ASSERT(entry == it.m_position);
             ++count;
 
-            ValueCheck<Key>::checkConsistency(it->key);
+            ValueCheck<Key>::checkConsistency(key);
         }
 
         ASSERT(count == m_keyCount);
index 89b91f4..00e457f 100644 (file)
@@ -39,12 +39,15 @@ template<bool isInteger, typename T> struct GenericHashTraitsBase;
 template<typename T> struct GenericHashTraitsBase<false, T> {
     // The emptyValueIsZero flag is used to optimize allocation of empty hash tables with zeroed memory.
     static const bool emptyValueIsZero = false;
-    
+
     // The hasIsEmptyValueFunction flag allows the hash table to automatically generate code to check
     // for the empty value when it can be done with the equality operator, but allows custom functions
     // for cases like String that need them.
     static const bool hasIsEmptyValueFunction = false;
 
+    // Used by WeakPtr to indicate that the value may become deleted without being explicitly removed.
+    static const bool hasIsReleasedWeakValueFunction = false;
+
     // The starting table size. Can be overridden when we know beforehand that
     // a hash table will have at least N entries.
     static const unsigned minimumTableSize = 8;
@@ -192,7 +195,7 @@ template<typename P> struct HashTraits<RefPtr<P>> : SimpleClassHashTraits<RefPtr
     }
 };
 
-template<typename P> struct HashTraits<Ref<P>> : SimpleClassHashTraits<Ref<P>> {
+template<typename P> struct RefHashTraits : SimpleClassHashTraits<Ref<P>> {
     static const bool emptyValueIsZero = true;
     static Ref<P> emptyValue() { return HashTableEmptyValue; }
 
@@ -215,6 +218,8 @@ template<typename P> struct HashTraits<Ref<P>> : SimpleClassHashTraits<Ref<P>> {
     static TakeType take(Ref<P>&& value) { return isEmptyValue(value) ? WTF::nullopt : Optional<Ref<P>>(WTFMove(value)); }
 };
 
+template<typename P> struct HashTraits<Ref<P>> : RefHashTraits<P> { };
+
 template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
     static const bool hasIsEmptyValueFunction = true;
     static bool isEmptyValue(const String&);
@@ -236,6 +241,18 @@ template<typename Traits, typename T> inline bool isHashTraitsEmptyValue(const T
     return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFunction>::isEmptyValue(value);
 }
 
+template<typename Traits, bool hasIsReleasedWeakValueFunction> struct HashTraitsReleasedWeakValueChecker;
+template<typename Traits> struct HashTraitsReleasedWeakValueChecker<Traits, true> {
+    template<typename T> static bool isReleasedWeakValue(const T& value) { return Traits::isReleasedWeakValue(value); }
+};
+template<typename Traits> struct HashTraitsReleasedWeakValueChecker<Traits, false> {
+    template<typename T> static bool isReleasedWeakValue(const T&) { return false; }
+};
+template<typename Traits, typename T> inline bool isHashTraitsReleasedWeakValue(const T& value)
+{
+    return HashTraitsReleasedWeakValueChecker<Traits, Traits::hasIsReleasedWeakValueFunction>::isReleasedWeakValue(value);
+}
+
 template<typename Traits, typename T>
 struct HashTraitHasCustomDelete {
     static T& bucketArg;
diff --git a/Source/WTF/wtf/WeakHashSet.h b/Source/WTF/wtf/WeakHashSet.h
new file mode 100644 (file)
index 0000000..8142892
--- /dev/null
@@ -0,0 +1,138 @@
+/*
+ * Copyright (C) 2017, 2019 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <wtf/HashSet.h>
+#include <wtf/HashTraits.h>
+#include <wtf/WeakPtr.h>
+
+namespace WTF {
+
+template <typename T>
+class WeakHashSet {
+public:
+    typedef HashSet<Ref<WeakReference<T>>> WeakReferenceSet;
+
+    class WeakHashSetConstIterator : public std::iterator<std::forward_iterator_tag, T, std::ptrdiff_t, const T*, const T&> {
+    private:
+        WeakHashSetConstIterator(const WeakReferenceSet& set, typename WeakReferenceSet::const_iterator position)
+            : m_position(position), m_endPosition(set.end())
+        {
+            skipEmptyBuckets();
+        }
+
+    public:
+        T* get() const { return m_position->get().get(); }
+        T& operator*() const { return *get(); }
+        T* operator->() const { return get(); }
+
+        WeakHashSetConstIterator& operator++()
+        {
+            ASSERT(m_position != m_endPosition);
+            ++m_position;
+            skipEmptyBuckets();
+            return *this;
+        }
+
+        void skipEmptyBuckets()
+        {
+            while (m_position != m_endPosition && !m_position->get().get())
+                ++m_position;
+        }
+
+        bool operator==(const WeakHashSetConstIterator& other) const
+        {
+            return m_position == other.m_position;
+        }
+
+        bool operator!=(const WeakHashSetConstIterator& other) const
+        {
+            return m_position != other.m_position;
+        }
+
+    private:
+        template <typename U> friend class WeakHashSet;
+
+        typename WeakReferenceSet::const_iterator m_position;
+        typename WeakReferenceSet::const_iterator m_endPosition;
+    };
+    typedef WeakHashSetConstIterator const_iterator;
+
+    WeakHashSet() { }
+
+    const_iterator begin() const { return WeakHashSetConstIterator(m_set, m_set.begin()); }
+    const_iterator end() const { return WeakHashSetConstIterator(m_set, m_set.end()); }
+
+    void add(T& value)
+    {
+        m_set.add(*makeWeakPtr(value).m_ref);
+    }
+
+    void remove(const T& value)
+    {
+        auto* weakReference = value.weakPtrFactory().m_ref.get();
+        if (!weakReference)
+            return;
+        m_set.remove(weakReference);
+    }
+
+    bool contains(const T& value) const
+    {
+        auto* weakReference = value.weakPtrFactory().m_ref.get();
+        if (!weakReference)
+            return false;
+        return m_set.contains(weakReference);
+    }
+
+    unsigned capacity() const { return m_set.capacity(); }
+
+    unsigned computeSize() const
+    {
+        const_cast<WeakReferenceSet&>(m_set).removeIf([] (auto& value) { return !value->get(); });
+        return m_set.size();
+    }
+
+#if ASSERT_DISABLED
+    void checkConsistency() const { }
+#else
+    void checkConsistency() const { m_set.checkConsistency(); }
+#endif
+
+private:
+    WeakReferenceSet m_set;
+};
+
+template<typename T> struct HashTraits<Ref<WeakReference<T>>> : RefHashTraits<WeakReference<T>> {
+    static const bool hasIsReleasedWeakValueFunction = true;
+    static bool isReleasedWeakValue(const Ref<WeakReference<T>>& value)
+    {
+        return !value.isHashTableDeletedValue() && !value.isHashTableEmptyValue() && !value.get().get();
+    }
+};
+
+} // namespace WTF
+
+using WTF::WeakHashSet;
index 9d05182..87d289d 100644 (file)
@@ -42,6 +42,8 @@ class WeakReference : public ThreadSafeRefCounted<WeakReference<T>> {
     WTF_MAKE_NONCOPYABLE(WeakReference<T>);
     WTF_MAKE_FAST_ALLOCATED;
 public:
+    ~WeakReference() { } // So that we can use a template specialization for testing purposes to detect leaks.
+
     T* get() const { return m_ptr; }
 
     void clear() { m_ptr = nullptr; }
@@ -83,6 +85,7 @@ public:
     void clear() { m_ref = nullptr; }
 
 private:
+    template<typename U> friend class WeakHashSet;
     template<typename U> friend class WeakPtr;
     template<typename U> friend WeakPtr<U> makeWeakPtr(U&);
 
@@ -127,6 +130,8 @@ public:
     }
 
 private:
+    template<typename U> friend class WeakHashSet;
+
     mutable RefPtr<WeakReference<T>> m_ref;
 };
 
index e1d0610..f668947 100644 (file)
@@ -1,3 +1,20 @@
+2019-02-28  Ryosuke Niwa  <rniwa@webkit.org>
+
+        Add WeakHashSet
+        https://bugs.webkit.org/show_bug.cgi?id=195152
+
+        Reviewed by Antti Koivisto.
+
+        Added tests for WeakHashSet.
+
+        * TestWebKitAPI/Tests/WTF/WeakPtr.cpp:
+        (TestWebKitAPI::Base::Base): Moved.
+        (TestWebKitAPI::Derived::foo): Moved.
+        (WTF::WeakReference<TestWebKitAPI::Base>): Added to track the number of live WeakReference.
+        (WTF::WeakReference<TestWebKitAPI::Base>::WeakReference):
+        (WTF::WeakReference<TestWebKitAPI::Base>::~WeakReference):
+        (TestWebKitAPI::computeSizeOfWeakHashSet): Added.
+
 2019-03-04  Chris Dumez  <cdumez@apple.com>
 
         Do not share WebProcesses between private and regular sessions
index bc25d22..635309f 100644 (file)
 #include "config.h"
 
 #include "Test.h"
+#include <wtf/HashSet.h>
+#include <wtf/WeakHashSet.h>
 #include <wtf/WeakPtr.h>
 
+static unsigned s_baseWeakReferences = 0;
+
+namespace TestWebKitAPI {
+
+class Base {
+public:
+    Base() { }
+
+    int foo()
+    {
+        return 0;
+    }
+
+    auto& weakPtrFactory() const { return m_weakPtrFactory; }
+
+private:
+    WeakPtrFactory<Base> m_weakPtrFactory;
+};
+
+class Derived : public Base {
+public:
+    Derived() { }
+
+    int foo()
+    {
+        return 1;
+    }
+};
+
+}
+
+namespace WTF {
+
+template<>
+WeakReference<TestWebKitAPI::Base>::WeakReference(TestWebKitAPI::Base* ptr)
+    : m_ptr(ptr)
+{
+    ++s_baseWeakReferences;
+}
+template<>
+WeakReference<TestWebKitAPI::Base>::~WeakReference()
+{
+    --s_baseWeakReferences;
+}
+
+}
+
 namespace TestWebKitAPI {
 
 TEST(WTF_WeakPtr, Basic)
@@ -199,31 +248,6 @@ TEST(WTF_WeakPtr, Forget)
     EXPECT_NULL(weakPtr7.get());
 }
 
-class Base {
-public:
-    Base() { }
-
-    int foo()
-    {
-        return 0;
-    }
-
-    auto& weakPtrFactory() const { return m_weakPtrFactory; }
-
-private:
-    WeakPtrFactory<Base> m_weakPtrFactory;
-};
-
-class Derived : public Base {
-public:
-    Derived() { }
-
-    int foo()
-    {
-        return 1;
-    }
-};
-
 TEST(WTF_WeakPtr, Downcasting)
 {
     int dummy0 = 0;
@@ -322,4 +346,227 @@ TEST(WTF_WeakPtr, DerivedConstructAndAssignConst)
     }
 }
 
+template <typename T>
+unsigned computeSizeOfWeakHashSet(const HashSet<WeakPtr<T>>& set)
+{
+    unsigned size = 0;
+    for (auto& item : set) {
+        UNUSED_PARAM(item);
+        size++;
+    }
+    return size;
+}
+
+template <typename T>
+unsigned computeSizeOfWeakHashSet(const WeakHashSet<T>& set)
+{
+    unsigned size = 0;
+    for (auto& item : set) {
+        UNUSED_PARAM(item);
+        size++;
+    }
+    return size;
+}
+
+TEST(WTF_WeakPtr, WeakHashSetBasic)
+{
+    {
+        WeakHashSet<Base> weakHashSet;
+        Base object;
+        EXPECT_FALSE(weakHashSet.contains(object));
+        EXPECT_EQ(s_baseWeakReferences, 0u);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
+        weakHashSet.add(object);
+        EXPECT_EQ(s_baseWeakReferences, 1u);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
+        EXPECT_TRUE(weakHashSet.contains(object));
+        weakHashSet.add(object);
+        EXPECT_TRUE(weakHashSet.contains(object));
+        EXPECT_EQ(s_baseWeakReferences, 1u);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
+        weakHashSet.checkConsistency();
+    }
+    EXPECT_EQ(s_baseWeakReferences, 0u);
+
+    {
+        WeakHashSet<Base> weakHashSet;
+        Derived object;
+        EXPECT_FALSE(weakHashSet.contains(object));
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
+        EXPECT_EQ(s_baseWeakReferences, 0u);
+        weakHashSet.add(object);
+        EXPECT_TRUE(weakHashSet.contains(object));
+        EXPECT_EQ(s_baseWeakReferences, 1u);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
+        weakHashSet.add(object);
+        EXPECT_TRUE(weakHashSet.contains(object));
+        EXPECT_EQ(s_baseWeakReferences, 1u);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
+        weakHashSet.checkConsistency();
+    }
+    EXPECT_EQ(s_baseWeakReferences, 0u);
+
+    {
+        WeakHashSet<Base> weakHashSet;
+        {
+            Base object;
+            EXPECT_FALSE(weakHashSet.contains(object));
+            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
+            EXPECT_EQ(s_baseWeakReferences, 0u);
+            weakHashSet.add(object);
+            EXPECT_TRUE(weakHashSet.contains(object));
+            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
+            EXPECT_EQ(s_baseWeakReferences, 1u);
+        }
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
+        weakHashSet.checkConsistency();
+    }
+    EXPECT_EQ(s_baseWeakReferences, 0u);
+
+    {
+        WeakHashSet<Base> weakHashSet;
+        {
+            Base object1;
+            Base object2;
+            EXPECT_FALSE(weakHashSet.contains(object1));
+            EXPECT_FALSE(weakHashSet.contains(object2));
+            EXPECT_EQ(s_baseWeakReferences, 0u);
+            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
+            weakHashSet.add(object1);
+            EXPECT_TRUE(weakHashSet.contains(object1));
+            EXPECT_FALSE(weakHashSet.contains(object2));
+            EXPECT_EQ(s_baseWeakReferences, 1u);
+            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
+            weakHashSet.add(object2);
+            EXPECT_TRUE(weakHashSet.contains(object1));
+            EXPECT_TRUE(weakHashSet.contains(object2));
+            EXPECT_EQ(s_baseWeakReferences, 2u);
+            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 2u);
+            weakHashSet.remove(object1);
+            EXPECT_FALSE(weakHashSet.contains(object1));
+            EXPECT_TRUE(weakHashSet.contains(object2));
+            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
+        }
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
+        weakHashSet.checkConsistency();
+    }
+    EXPECT_EQ(s_baseWeakReferences, 0u);
+
+    {
+        WeakHashSet<Base> weakHashSet;
+        Base object1;
+        Base object2;
+        Base object3;
+        EXPECT_FALSE(weakHashSet.contains(object1));
+        EXPECT_FALSE(weakHashSet.contains(object2));
+        EXPECT_FALSE(weakHashSet.contains(object3));
+        EXPECT_EQ(s_baseWeakReferences, 0u);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
+        weakHashSet.add(object1);
+        weakHashSet.add(object2);
+        EXPECT_TRUE(weakHashSet.contains(object1));
+        EXPECT_TRUE(weakHashSet.contains(object2));
+        EXPECT_FALSE(weakHashSet.contains(object3));
+        EXPECT_EQ(s_baseWeakReferences, 2u);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 2u);
+        weakHashSet.remove(object1);
+        EXPECT_FALSE(weakHashSet.contains(object1));
+        EXPECT_TRUE(weakHashSet.contains(object2));
+        EXPECT_FALSE(weakHashSet.contains(object3));
+        EXPECT_EQ(s_baseWeakReferences, 2u); // Because object2 holds onto WeakReference.
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
+        weakHashSet.remove(object3);
+        EXPECT_FALSE(weakHashSet.contains(object1));
+        EXPECT_TRUE(weakHashSet.contains(object2));
+        EXPECT_FALSE(weakHashSet.contains(object3));
+        EXPECT_EQ(s_baseWeakReferences, 2u);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
+        weakHashSet.add(object2);
+        EXPECT_FALSE(weakHashSet.contains(object1));
+        EXPECT_TRUE(weakHashSet.contains(object2));
+        EXPECT_FALSE(weakHashSet.contains(object3));
+        EXPECT_EQ(s_baseWeakReferences, 2u);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
+        weakHashSet.checkConsistency();
+    }
+    EXPECT_EQ(s_baseWeakReferences, 0u);
+}
+
+TEST(WTF_WeakPtr, WeakHashSetExpansion)
+{
+    unsigned initialCapacity;
+    const static unsigned maxLoadCap = 3;
+    {
+        WeakHashSet<Base> weakHashSet;
+        Base object;
+        EXPECT_EQ(s_baseWeakReferences, 0u);
+        weakHashSet.add(object);
+        EXPECT_EQ(s_baseWeakReferences, 1u);
+        initialCapacity = weakHashSet.capacity();
+    }
+    EXPECT_EQ(s_baseWeakReferences, 0u);
+
+    for (unsigned i = 0; i < 1; ++i) {
+        WeakHashSet<Base> weakHashSet;
+        Vector<std::unique_ptr<Base>> objects;
+        Vector<std::unique_ptr<Base>> otherObjects;
+
+        EXPECT_EQ(weakHashSet.capacity(), 0u);
+        EXPECT_TRUE(initialCapacity / maxLoadCap);
+        for (unsigned i = 0; i < initialCapacity / maxLoadCap; ++i) {
+            auto object = std::make_unique<Base>();
+            weakHashSet.add(*object);
+            objects.append(WTFMove(object));
+            otherObjects.append(std::make_unique<Base>());
+            weakHashSet.checkConsistency();
+        }
+        EXPECT_EQ(s_baseWeakReferences, otherObjects.size());
+        EXPECT_EQ(weakHashSet.capacity(), initialCapacity);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), objects.size());
+        for (unsigned i = 0; i < otherObjects.size(); ++i) {
+            EXPECT_TRUE(weakHashSet.contains(*objects[i]));
+            EXPECT_FALSE(weakHashSet.contains(*otherObjects[i]));
+        }
+        objects.clear();
+        weakHashSet.checkConsistency();
+        EXPECT_EQ(s_baseWeakReferences, otherObjects.size());
+        EXPECT_EQ(weakHashSet.capacity(), initialCapacity);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
+        for (auto& object : otherObjects)
+            EXPECT_FALSE(weakHashSet.contains(*object));
+        for (auto& object : otherObjects) {
+            weakHashSet.add(*object);
+            weakHashSet.checkConsistency();
+        }
+        EXPECT_EQ(weakHashSet.capacity(), initialCapacity);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), otherObjects.size());
+        for (auto& object : otherObjects)
+            EXPECT_TRUE(weakHashSet.contains(*object));
+    }
+    EXPECT_EQ(s_baseWeakReferences, 0u);
+
+    for (unsigned i = 0; i < 10; ++i) {
+        WeakHashSet<Base> weakHashSet;
+        Vector<std::unique_ptr<Base>> objects;
+        EXPECT_EQ(weakHashSet.capacity(), 0u);
+        unsigned objectCount = initialCapacity * 2;
+        for (unsigned i = 0; i < objectCount; ++i) {
+            auto object = std::make_unique<Base>();
+            weakHashSet.add(*object);
+            objects.append(WTFMove(object));
+            weakHashSet.checkConsistency();
+        }
+        unsigned originalCapacity = weakHashSet.capacity();
+        EXPECT_EQ(s_baseWeakReferences, objects.size());
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), objects.size());
+        for (auto& object : objects)
+            EXPECT_TRUE(weakHashSet.contains(*object));
+        objects.clear();
+        weakHashSet.checkConsistency();
+        EXPECT_EQ(s_baseWeakReferences, objectCount);
+        EXPECT_EQ(weakHashSet.capacity(), originalCapacity);
+        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
+    }
+}
+
 } // namespace TestWebKitAPI