⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 242387 in webkit


Ignore:
Timestamp:
Mar 4, 2019, 1:52:32 PM (7 years ago)
Author:
rniwa@webkit.org
Message:

Add WeakHashSet
​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.

Location:
trunk
Files:
1 added
10 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WTF/ChangeLog

    r242360 r242387  
     12019-02-28  Ryosuke Niwa  <rniwa@webkit.org>
     2
     3        Add WeakHashSet
     4        https://bugs.webkit.org/show_bug.cgi?id=195152
     5
     6        Reviewed by Antti Koivisto.
     7
     8        Added WeakHashSet which is a HashSet of WeakPtr. When the object pointed by WeakPtr is deleted,
     9        WeakHashSet treats the key to be no longer in the set. That is, WeakHashSet::contains returns false
     10        and const_iterator skips such a WeakPtr in the set.
     11
     12        We decided not to make HashSet<WeahPtr<T>> work because it involves weird semantics such as making
     13        find(X) delete the table entry as remove(find(X)) would be a no-op otherwise as find(X) would return
     14        necessarily need to return HashSet<WeakPtr<T>>::end().
     15
     16        Furthermore, we cannot determine the true size of this set in O(1) because the objected pointed by
     17        some of WeakPtr in the set may have already been deleted. This has implications that we can't have
     18        size(), isEmpty(), random(), etc... as O(1) operation.
     19
     20        WeakHashSet is implemented as HashSet<WeakReference<T>>. HashTable::rehash has been updated to delete
     21        WeakReference<T>'s whose m_ptr has become null, and HashTable::expand first deletes any such entry
     22        before deciding an actual expansion is needed. This is accomplished via newly added hash trait,
     23        hasIsReleasedWeakValueFunction, and HashTraits<Ref<WeakReference<T>>>::isReleasedWeakValue which
     24        returns true for when WeakReference<T> pointed by Ref<WeakReference<T>> has null m_ptr, not to be
     25        confused with Ref<WeakReference<T>> itself pointing to a null WeakReference<T>.
     26
     27        * WTF.xcodeproj/project.pbxproj:
     28        * wtf/CMakeLists.txt:
     29        * wtf/Forward.h:
     30        * wtf/HashSet.h:
     31        (WTF::HashSet<T, U, V>::checkConsistency const): Added.
     32        * wtf/HashTable.h:
     33        (WTF::HashTable::isReleasedWeakBucket): Added.
     34        (WTF::HashTable::expand): Delete WeakReference<T> with null m_ptr first. This updates m_keyCount
     35        and may make mustRehashInPlace() return true.
     36        (WTF::HashTable::deleteReleasedWeakBuckets): Added.
     37        (WTF::HashTable::rehash): Delete WeakReference<T> with null m_ptr. Also refactored the code a bit
     38        to avoid keep repeating oldTable[i].
     39        * wtf/HashTraits.h:
     40        (WTF::HashTraits<T>::isHashTraitsReleasedWeakValue): Added.
     41        (WTF::RefHashTraits<T>): Extracted from HashTraits<Ref<P>> to share code with
     42        HashTraits<Ref<WeakReference<T>>>.
     43        (WTF::HashTraitsReleasedWeakValueChecker<Traits, hasIsReleasedWeakValueFunction>): Added.
     44        (WTF::isHashTraitsReleasedWeakValue<Traits, hasIsReleasedWeakValueFunction>): Added.
     45        * wtf/WeakHashSet.h: Added.
     46        (WTF::WeakHashSet): Added.
     47        (WTF::WeakHashSet::WeakHashSetConstIterator::WeakHashSetConstIterator):
     48        (WTF::WeakHashSet::WeakHashSetConstIterator::get const):
     49        (WTF::WeakHashSet::WeakHashSetConstIterator::operator* const):
     50        (WTF::WeakHashSet::WeakHashSetConstIterator::operator-> const):
     51        (WTF::WeakHashSet::WeakHashSetConstIterator::operator++):
     52        (WTF::WeakHashSet::WeakHashSetConstIterator::skipEmptyBuckets):
     53        (WTF::WeakHashSet::WeakHashSetConstIterator::operator== const):
     54        (WTF::WeakHashSet::WeakHashSetConstIterator::operator!= const):
     55        (WTF::WeakHashSet::WeakHashSet):
     56        (WTF::WeakHashSet::begin const):
     57        (WTF::WeakHashSet::end const):
     58        (WTF::WeakHashSet::add):
     59        (WTF::WeakHashSet::remove):
     60        (WTF::WeakHashSet::contains const):
     61        (WTF::WeakHashSet::capacity const):
     62        (WTF::WeakHashSet::computeSize const): Deletes any WeakReference<T> with null m_ptr first.
     63        (WTF::WeakHashSet::checkConsistency const):
     64        (WTF::HashTraits<Ref<WeakReference<T>>>): Added. This hash traits triggers the new code in HashTable's
     65        expand and rehash methods to delete WeakReference<T> with null m_ptr.
     66        (WTF::HashTraits<Ref<WeakReference<T>>>::isReleasedWeakValue):
     67        * wtf/WeakPtr.h:
     68        (WTF::WeakReference::~WeakReference): Added so that we can keep track the number of live WeakReference
     69        in API tests by template specializations.
     70
    1712019-03-03  Darin Adler  <darin@apple.com>
    272

  • trunk/Source/WTF/WTF.xcodeproj/project.pbxproj

    r242330 r242387  
    440440                974CFC8D16A4F327006D5404 /* WeakPtr.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakPtr.h; sourceTree = "<group>"; };
    441441                996B17841EBA441C007E10EB /* DebugUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DebugUtilities.h; sourceTree = "<group>"; };
     442                9B67F3F12228D5310030DE9C /* WeakHashSet.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = WeakHashSet.h; sourceTree = "<group>"; };
    442443                9BC70F04176C379D00101DEC /* AtomicStringTable.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AtomicStringTable.cpp; sourceTree = "<group>"; };
    443444                9BD8F40A176C2AD80002D865 /* AtomicStringTable.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = AtomicStringTable.h; sourceTree = "<group>"; };
    … …  
    11841185                                0F66B2881DC97BAB004A1D3F /* WallTime.cpp */,
    11851186                                0F66B2891DC97BAB004A1D3F /* WallTime.h */,
     1187                                9B67F3F12228D5310030DE9C /* WeakHashSet.h */,
    11861188                                83ABB3C020B3823200BA3306 /* WeakObjCPtr.h */,
    11871189                                974CFC8D16A4F327006D5404 /* WeakPtr.h */,

  • trunk/Source/WTF/wtf/CMakeLists.txt

    r242330 r242387  
    259259    WTFSemaphore.h
    260260    WallTime.h
     261    WeakHashSet.h
    261262    WeakPtr.h
    262263    WeakRandom.h

  • trunk/Source/WTF/wtf/Forward.h

    r238771 r242387  
    6060template<typename> class StringBuffer;
    6161template<typename, typename = void> class StringTypeAdapter;
     62template<typename T> class WeakPtr;
    6263
    6364template<typename> struct DefaultHash { using Hash = void; };

  • trunk/Source/WTF/wtf/HashSet.h

    r237461 r242387  
    128128    bool operator!=(const OtherCollection&) const;
    129129
     130    void checkConsistency() const;
     131
    130132private:
    131133    HashTableType m_impl;
    … …  
    383385}
    384386
     387template<typename T, typename U, typename V>
     388inline void HashSet<T, U, V>::checkConsistency() const
     389{
     390    m_impl.checkTableConsistency();
     391}
     392
    385393} // namespace WTF
    386394

  • trunk/Source/WTF/wtf/HashTable.h

    r237522 r242387  
    425425
    426426        static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
     427        static bool isReleasedWeakBucket(const ValueType& value) { return isHashTraitsReleasedWeakValue<KeyTraits>(Extractor::extract(value)); }
    427428        static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
    428429        static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
    … …  
    469470        ValueType* expand(ValueType* entry = nullptr);
    470471        void shrink() { rehash(m_tableSize / 2, nullptr); }
     472
     473        void deleteReleasedWeakBuckets();
    471474
    472475        ValueType* rehash(unsigned newTableSize, ValueType* entry);
    … …  
    11791182    auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand(ValueType* entry) -> ValueType*
    11801183    {
     1184        if (KeyTraits::hasIsReleasedWeakValueFunction)
     1185            deleteReleasedWeakBuckets();
     1186
    11811187        unsigned newSize;
    11821188        if (m_tableSize == 0)
    … …  
    11911197
    11921198    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     1199    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deleteReleasedWeakBuckets()
     1200    {
     1201        for (unsigned i = 0; i < m_tableSize; ++i) {
     1202            auto& entry = m_table[i];
     1203            if (isReleasedWeakBucket(entry)) {
     1204                deleteBucket(entry);
     1205                ++m_deletedCount;
     1206                --m_keyCount;
     1207            }
     1208        }
     1209    }
     1210
     1211    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    11931212    auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(unsigned newTableSize, ValueType* entry) -> ValueType*
    11941213    {
    … …  
    12141233        Value* newEntry = nullptr;
    12151234        for (unsigned i = 0; i != oldTableSize; ++i) {
    1216             if (isDeletedBucket(oldTable[i])) {
    1217                 ASSERT(std::addressof(oldTable[i]) != entry);
     1235            auto& oldEntry = oldTable[i];
     1236            if (isDeletedBucket(oldEntry)) {
     1237                ASSERT(std::addressof(oldEntry) != entry);
    12181238                continue;
    12191239            }
    12201240
    1221             if (isEmptyBucket(oldTable[i])) {
    1222                 ASSERT(std::addressof(oldTable[i]) != entry);
     1241            if (isEmptyBucket(oldEntry)) {
     1242                ASSERT(std::addressof(oldEntry) != entry);
    12231243                oldTable[i].~ValueType();
    12241244                continue;
    12251245            }
    12261246
    1227             Value* reinsertedEntry = reinsert(WTFMove(oldTable[i]));
    1228             oldTable[i].~ValueType();
    1229             if (std::addressof(oldTable[i]) == entry) {
     1247            if (isReleasedWeakBucket(oldEntry)) {
     1248                ASSERT(std::addressof(oldEntry) != entry);
     1249                oldEntry.~ValueType();
     1250                --m_keyCount;
     1251                continue;
     1252            }
     1253
     1254            Value* reinsertedEntry = reinsert(WTFMove(oldEntry));
     1255            oldEntry.~ValueType();
     1256            if (std::addressof(oldEntry) == entry) {
    12301257                ASSERT(!newEntry);
    12311258                newEntry = reinsertedEntry;
    … …  
    13821409            }
    13831410
    1384             const_iterator it = find(Extractor::extract(*entry));
     1411            auto& key = Extractor::extract(*entry);
     1412            const_iterator it = find(key);
    13851413            ASSERT(entry == it.m_position);
    13861414            ++count;
    13871415
    1388             ValueCheck<Key>::checkConsistency(it->key);
     1416            ValueCheck<Key>::checkConsistency(key);
    13891417        }
    13901418

  • trunk/Source/WTF/wtf/HashTraits.h

    r239427 r242387  
    4040    // The emptyValueIsZero flag is used to optimize allocation of empty hash tables with zeroed memory.
    4141    static const bool emptyValueIsZero = false;
    42    
     42
    4343    // The hasIsEmptyValueFunction flag allows the hash table to automatically generate code to check
    4444    // for the empty value when it can be done with the equality operator, but allows custom functions
    4545    // for cases like String that need them.
    4646    static const bool hasIsEmptyValueFunction = false;
     47
     48    // Used by WeakPtr to indicate that the value may become deleted without being explicitly removed.
     49    static const bool hasIsReleasedWeakValueFunction = false;
    4750
    4851    // The starting table size. Can be overridden when we know beforehand that
    … …  
    193196};
    194197
    195 template<typename P> struct HashTraits<Ref<P>> : SimpleClassHashTraits<Ref<P>> {
     198template<typename P> struct RefHashTraits : SimpleClassHashTraits<Ref<P>> {
    196199    static const bool emptyValueIsZero = true;
    197200    static Ref<P> emptyValue() { return HashTableEmptyValue; }
    … …  
    215218    static TakeType take(Ref<P>&& value) { return isEmptyValue(value) ? WTF::nullopt : Optional<Ref<P>>(WTFMove(value)); }
    216219};
     220
     221template<typename P> struct HashTraits<Ref<P>> : RefHashTraits<P> { };
    217222
    218223template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
    … …  
    235240{
    236241    return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFunction>::isEmptyValue(value);
     242}
     243
     244template<typename Traits, bool hasIsReleasedWeakValueFunction> struct HashTraitsReleasedWeakValueChecker;
     245template<typename Traits> struct HashTraitsReleasedWeakValueChecker<Traits, true> {
     246    template<typename T> static bool isReleasedWeakValue(const T& value) { return Traits::isReleasedWeakValue(value); }
     247};
     248template<typename Traits> struct HashTraitsReleasedWeakValueChecker<Traits, false> {
     249    template<typename T> static bool isReleasedWeakValue(const T&) { return false; }
     250};
     251template<typename Traits, typename T> inline bool isHashTraitsReleasedWeakValue(const T& value)
     252{
     253    return HashTraitsReleasedWeakValueChecker<Traits, Traits::hasIsReleasedWeakValueFunction>::isReleasedWeakValue(value);
    237254}
    238255

  • trunk/Source/WTF/wtf/WeakPtr.h

    r237099 r242387  
    4343    WTF_MAKE_FAST_ALLOCATED;
    4444public:
     45    ~WeakReference() { } // So that we can use a template specialization for testing purposes to detect leaks.
     46
    4547    T* get() const { return m_ptr; }
    4648
    … …  
    8486
    8587private:
     88    template<typename U> friend class WeakHashSet;
    8689    template<typename U> friend class WeakPtr;
    8790    template<typename U> friend WeakPtr<U> makeWeakPtr(U&);
    … …  
    128131
    129132private:
     133    template<typename U> friend class WeakHashSet;
     134
    130135    mutable RefPtr<WeakReference<T>> m_ref;
    131136};

  • trunk/Tools/ChangeLog

    r242371 r242387  
     12019-02-28  Ryosuke Niwa  <rniwa@webkit.org>
     2
     3        Add WeakHashSet
     4        https://bugs.webkit.org/show_bug.cgi?id=195152
     5
     6        Reviewed by Antti Koivisto.
     7
     8        Added tests for WeakHashSet.
     9
     10        * TestWebKitAPI/Tests/WTF/WeakPtr.cpp:
     11        (TestWebKitAPI::Base::Base): Moved.
     12        (TestWebKitAPI::Derived::foo): Moved.
     13        (WTF::WeakReference<TestWebKitAPI::Base>): Added to track the number of live WeakReference.
     14        (WTF::WeakReference<TestWebKitAPI::Base>::WeakReference):
     15        (WTF::WeakReference<TestWebKitAPI::Base>::~WeakReference):
     16        (TestWebKitAPI::computeSizeOfWeakHashSet): Added.
     17
    1182019-03-04  Chris Dumez  <cdumez@apple.com>
    219

  • trunk/Tools/TestWebKitAPI/Tests/WTF/WeakPtr.cpp

    r235315 r242387  
    2727
    2828#include "Test.h"
     29#include <wtf/HashSet.h>
     30#include <wtf/WeakHashSet.h>
    2931#include <wtf/WeakPtr.h>
     32
     33static unsigned s_baseWeakReferences = 0;
     34
     35namespace TestWebKitAPI {
     36
     37class Base {
     38public:
     39    Base() { }
     40
     41    int foo()
     42    {
     43        return 0;
     44    }
     45
     46    auto& weakPtrFactory() const { return m_weakPtrFactory; }
     47
     48private:
     49    WeakPtrFactory<Base> m_weakPtrFactory;
     50};
     51
     52class Derived : public Base {
     53public:
     54    Derived() { }
     55
     56    int foo()
     57    {
     58        return 1;
     59    }
     60};
     61
     62}
     63
     64namespace WTF {
     65
     66template<>
     67WeakReference<TestWebKitAPI::Base>::WeakReference(TestWebKitAPI::Base* ptr)
     68    : m_ptr(ptr)
     69{
     70    ++s_baseWeakReferences;
     71}
     72template<>
     73WeakReference<TestWebKitAPI::Base>::~WeakReference()
     74{
     75    --s_baseWeakReferences;
     76}
     77
     78}
    3079
    3180namespace TestWebKitAPI {
    … …  
    200249}
    201250
    202 class Base {
    203 public:
    204     Base() { }
    205 
    206     int foo()
    207     {
    208         return 0;
    209     }
    210 
    211     auto& weakPtrFactory() const { return m_weakPtrFactory; }
    212 
    213 private:
    214     WeakPtrFactory<Base> m_weakPtrFactory;
    215 };
    216 
    217 class Derived : public Base {
    218 public:
    219     Derived() { }
    220 
    221     int foo()
    222     {
    223         return 1;
    224     }
    225 };
    226 
    227251TEST(WTF_WeakPtr, Downcasting)
    228252{
    … …  
    323347}
    324348
     349template <typename T>
     350unsigned computeSizeOfWeakHashSet(const HashSet<WeakPtr<T>>& set)
     351{
     352    unsigned size = 0;
     353    for (auto& item : set) {
     354        UNUSED_PARAM(item);
     355        size++;
     356    }
     357    return size;
     358}
     359
     360template <typename T>
     361unsigned computeSizeOfWeakHashSet(const WeakHashSet<T>& set)
     362{
     363    unsigned size = 0;
     364    for (auto& item : set) {
     365        UNUSED_PARAM(item);
     366        size++;
     367    }
     368    return size;
     369}
     370
     371TEST(WTF_WeakPtr, WeakHashSetBasic)
     372{
     373    {
     374        WeakHashSet<Base> weakHashSet;
     375        Base object;
     376        EXPECT_FALSE(weakHashSet.contains(object));
     377        EXPECT_EQ(s_baseWeakReferences, 0u);
     378        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
     379        weakHashSet.add(object);
     380        EXPECT_EQ(s_baseWeakReferences, 1u);
     381        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
     382        EXPECT_TRUE(weakHashSet.contains(object));
     383        weakHashSet.add(object);
     384        EXPECT_TRUE(weakHashSet.contains(object));
     385        EXPECT_EQ(s_baseWeakReferences, 1u);
     386        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
     387        weakHashSet.checkConsistency();
     388    }
     389    EXPECT_EQ(s_baseWeakReferences, 0u);
     390
     391    {
     392        WeakHashSet<Base> weakHashSet;
     393        Derived object;
     394        EXPECT_FALSE(weakHashSet.contains(object));
     395        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
     396        EXPECT_EQ(s_baseWeakReferences, 0u);
     397        weakHashSet.add(object);
     398        EXPECT_TRUE(weakHashSet.contains(object));
     399        EXPECT_EQ(s_baseWeakReferences, 1u);
     400        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
     401        weakHashSet.add(object);
     402        EXPECT_TRUE(weakHashSet.contains(object));
     403        EXPECT_EQ(s_baseWeakReferences, 1u);
     404        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
     405        weakHashSet.checkConsistency();
     406    }
     407    EXPECT_EQ(s_baseWeakReferences, 0u);
     408
     409    {
     410        WeakHashSet<Base> weakHashSet;
     411        {
     412            Base object;
     413            EXPECT_FALSE(weakHashSet.contains(object));
     414            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
     415            EXPECT_EQ(s_baseWeakReferences, 0u);
     416            weakHashSet.add(object);
     417            EXPECT_TRUE(weakHashSet.contains(object));
     418            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
     419            EXPECT_EQ(s_baseWeakReferences, 1u);
     420        }
     421        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
     422        weakHashSet.checkConsistency();
     423    }
     424    EXPECT_EQ(s_baseWeakReferences, 0u);
     425
     426    {
     427        WeakHashSet<Base> weakHashSet;
     428        {
     429            Base object1;
     430            Base object2;
     431            EXPECT_FALSE(weakHashSet.contains(object1));
     432            EXPECT_FALSE(weakHashSet.contains(object2));
     433            EXPECT_EQ(s_baseWeakReferences, 0u);
     434            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
     435            weakHashSet.add(object1);
     436            EXPECT_TRUE(weakHashSet.contains(object1));
     437            EXPECT_FALSE(weakHashSet.contains(object2));
     438            EXPECT_EQ(s_baseWeakReferences, 1u);
     439            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
     440            weakHashSet.add(object2);
     441            EXPECT_TRUE(weakHashSet.contains(object1));
     442            EXPECT_TRUE(weakHashSet.contains(object2));
     443            EXPECT_EQ(s_baseWeakReferences, 2u);
     444            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 2u);
     445            weakHashSet.remove(object1);
     446            EXPECT_FALSE(weakHashSet.contains(object1));
     447            EXPECT_TRUE(weakHashSet.contains(object2));
     448            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
     449        }
     450        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
     451        weakHashSet.checkConsistency();
     452    }
     453    EXPECT_EQ(s_baseWeakReferences, 0u);
     454
     455    {
     456        WeakHashSet<Base> weakHashSet;
     457        Base object1;
     458        Base object2;
     459        Base object3;
     460        EXPECT_FALSE(weakHashSet.contains(object1));
     461        EXPECT_FALSE(weakHashSet.contains(object2));
     462        EXPECT_FALSE(weakHashSet.contains(object3));
     463        EXPECT_EQ(s_baseWeakReferences, 0u);
     464        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
     465        weakHashSet.add(object1);
     466        weakHashSet.add(object2);
     467        EXPECT_TRUE(weakHashSet.contains(object1));
     468        EXPECT_TRUE(weakHashSet.contains(object2));
     469        EXPECT_FALSE(weakHashSet.contains(object3));
     470        EXPECT_EQ(s_baseWeakReferences, 2u);
     471        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 2u);
     472        weakHashSet.remove(object1);
     473        EXPECT_FALSE(weakHashSet.contains(object1));
     474        EXPECT_TRUE(weakHashSet.contains(object2));
     475        EXPECT_FALSE(weakHashSet.contains(object3));
     476        EXPECT_EQ(s_baseWeakReferences, 2u); // Because object2 holds onto WeakReference.
     477        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
     478        weakHashSet.remove(object3);
     479        EXPECT_FALSE(weakHashSet.contains(object1));
     480        EXPECT_TRUE(weakHashSet.contains(object2));
     481        EXPECT_FALSE(weakHashSet.contains(object3));
     482        EXPECT_EQ(s_baseWeakReferences, 2u);
     483        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
     484        weakHashSet.add(object2);
     485        EXPECT_FALSE(weakHashSet.contains(object1));
     486        EXPECT_TRUE(weakHashSet.contains(object2));
     487        EXPECT_FALSE(weakHashSet.contains(object3));
     488        EXPECT_EQ(s_baseWeakReferences, 2u);
     489        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
     490        weakHashSet.checkConsistency();
     491    }
     492    EXPECT_EQ(s_baseWeakReferences, 0u);
     493}
     494
     495TEST(WTF_WeakPtr, WeakHashSetExpansion)
     496{
     497    unsigned initialCapacity;
     498    const static unsigned maxLoadCap = 3;
     499    {
     500        WeakHashSet<Base> weakHashSet;
     501        Base object;
     502        EXPECT_EQ(s_baseWeakReferences, 0u);
     503        weakHashSet.add(object);
     504        EXPECT_EQ(s_baseWeakReferences, 1u);
     505        initialCapacity = weakHashSet.capacity();
     506    }
     507    EXPECT_EQ(s_baseWeakReferences, 0u);
     508
     509    for (unsigned i = 0; i < 1; ++i) {
     510        WeakHashSet<Base> weakHashSet;
     511        Vector<std::unique_ptr<Base>> objects;
     512        Vector<std::unique_ptr<Base>> otherObjects;
     513
     514        EXPECT_EQ(weakHashSet.capacity(), 0u);
     515        EXPECT_TRUE(initialCapacity / maxLoadCap);
     516        for (unsigned i = 0; i < initialCapacity / maxLoadCap; ++i) {
     517            auto object = std::make_unique<Base>();
     518            weakHashSet.add(*object);
     519            objects.append(WTFMove(object));
     520            otherObjects.append(std::make_unique<Base>());
     521            weakHashSet.checkConsistency();
     522        }
     523        EXPECT_EQ(s_baseWeakReferences, otherObjects.size());
     524        EXPECT_EQ(weakHashSet.capacity(), initialCapacity);
     525        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), objects.size());
     526        for (unsigned i = 0; i < otherObjects.size(); ++i) {
     527            EXPECT_TRUE(weakHashSet.contains(*objects[i]));
     528            EXPECT_FALSE(weakHashSet.contains(*otherObjects[i]));
     529        }
     530        objects.clear();
     531        weakHashSet.checkConsistency();
     532        EXPECT_EQ(s_baseWeakReferences, otherObjects.size());
     533        EXPECT_EQ(weakHashSet.capacity(), initialCapacity);
     534        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
     535        for (auto& object : otherObjects)
     536            EXPECT_FALSE(weakHashSet.contains(*object));
     537        for (auto& object : otherObjects) {
     538            weakHashSet.add(*object);
     539            weakHashSet.checkConsistency();
     540        }
     541        EXPECT_EQ(weakHashSet.capacity(), initialCapacity);
     542        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), otherObjects.size());
     543        for (auto& object : otherObjects)
     544            EXPECT_TRUE(weakHashSet.contains(*object));
     545    }
     546    EXPECT_EQ(s_baseWeakReferences, 0u);
     547
     548    for (unsigned i = 0; i < 10; ++i) {
     549        WeakHashSet<Base> weakHashSet;
     550        Vector<std::unique_ptr<Base>> objects;
     551        EXPECT_EQ(weakHashSet.capacity(), 0u);
     552        unsigned objectCount = initialCapacity * 2;
     553        for (unsigned i = 0; i < objectCount; ++i) {
     554            auto object = std::make_unique<Base>();
     555            weakHashSet.add(*object);
     556            objects.append(WTFMove(object));
     557            weakHashSet.checkConsistency();
     558        }
     559        unsigned originalCapacity = weakHashSet.capacity();
     560        EXPECT_EQ(s_baseWeakReferences, objects.size());
     561        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), objects.size());
     562        for (auto& object : objects)
     563            EXPECT_TRUE(weakHashSet.contains(*object));
     564        objects.clear();
     565        weakHashSet.checkConsistency();
     566        EXPECT_EQ(s_baseWeakReferences, objectCount);
     567        EXPECT_EQ(weakHashSet.capacity(), originalCapacity);
     568        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
     569    }
     570}
     571
    325572} // namespace TestWebKitAPI
Note: See TracChangeset for help on using the changeset viewer.