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)
commitace55a00e091ca0ad457e178e5a0df6b597545bd
tree5371e96c7ef5c42affa2f7c8e0ce2baac3130a22
parent8d98d8f6c0785256118ca6e56a908499e045598e
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.

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