Source/WTF/wtf/WeakHashMap.h - WebKit - Git at Google

 /*
  * Copyright (C) 2021 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/Algorithms.h>
 #include <wtf/HashTable.h>
 #include <wtf/WeakPtr.h>

 namespace WTF {

 // Value will be deleted lazily upon rehash or amortized over time. For manual cleanup, call removeNullReferences().
 template<typename KeyType, typename ValueType, typename Counter = EmptyCounter>
 class WeakHashMap final {
     WTF_MAKE_FAST_ALLOCATED;
 public:

     using RefType = Ref<WeakPtrImpl<Counter>>;
     using KeyTraits = HashTraits<KeyType>;
     using ValueTraits = HashTraits<ValueType>;
     using WeakHashImplMap = HashMap<RefType, ValueType>;

     struct PeekKeyValuePairTraits : KeyValuePairHashTraits<HashTraits<KeyType&>, HashTraits<ValueType&>> {
         static constexpr bool hasIsEmptyValueFunction = true;
         static bool isEmptyValue(const typename KeyValuePairHashTraits<HashTraits<KeyType&>, HashTraits<ValueType&>>::TraitType& value)
         {
             return isHashTraitsEmptyValue<KeyTraits>(value.key);
         }
     };
     using PeekKeyValuePairType = typename PeekKeyValuePairTraits::TraitType;

     struct PeekType {
         KeyType& key;
         ValueType& value;
     };

     struct PeekPtrType {
         PeekPtrType(const PeekType& peek)
             : m_peek(peek)
         { }

         const PeekType& operator*() const { return m_peek; }
         PeekType& operator*() { return m_peek; }

         const PeekType* operator->() const { return &m_peek; }
         PeekType* operator->() { return &m_peek; }

     private:
         PeekType m_peek;
     };

     template <typename MapType, typename IteratorType, typename IteratorPeekPtrType, typename IteratorPeekType>
     class WeakHashMapIteratorBase : public std::iterator<std::forward_iterator_tag, IteratorPeekType, std::ptrdiff_t, IteratorPeekPtrType, IteratorPeekType> {
     protected:
         WeakHashMapIteratorBase(MapType& weakHashMap, IteratorType position)
             : m_weakHashMap { weakHashMap }
             , m_position { position }
             , m_endPosition { weakHashMap.m_map.end() }
         {
             skipEmptyBuckets();
         }

         ~WeakHashMapIteratorBase()
         {
             if (m_emptyBucketCount > m_weakHashMap.m_map.size() / 8)
                 const_cast<WeakHashMap&>(m_weakHashMap).removeNullReferences();
             else
                 m_weakHashMap.amortizedCleanupIfNeeded(m_advanceCount + m_emptyBucketCount);
         }

         ALWAYS_INLINE IteratorPeekType makePeek()
         {
             auto* entry = m_position.get();
             auto* key = static_cast<KeyType*>(entry->key->template get<KeyType>());
             return IteratorPeekType { *key, entry->value };
         }

         ALWAYS_INLINE IteratorPeekType makePeek() const
         {
             auto* entry = m_position.get();
             auto* key = static_cast<KeyType*>(entry->key->template get<KeyType>());
             return IteratorPeekType { *key, const_cast<ValueType&>(entry->value) };
         }

         void advance()
         {
             ASSERT(m_position != m_endPosition);
             ++m_position;
             ++m_advanceCount;
             skipEmptyBuckets();
         }

         void skipEmptyBuckets()
         {
             while (m_position != m_endPosition && !m_position->key.get()) {
                 ++m_position;
                 ++m_emptyBucketCount;
             }
         }

         const MapType& m_weakHashMap;
         IteratorType m_position;
         IteratorType m_endPosition;
         unsigned m_advanceCount { 0 };
         unsigned m_emptyBucketCount { 0 };
     };

     class WeakHashMapIterator : public WeakHashMapIteratorBase<WeakHashMap, typename WeakHashImplMap::iterator, PeekPtrType, PeekType> {
     public:
         using Base = WeakHashMapIteratorBase<WeakHashMap, typename WeakHashImplMap::iterator, PeekPtrType, PeekType>;

         bool operator==(const WeakHashMapIterator& other) const { return Base::m_position == other.Base::m_position; }
         bool operator!=(const WeakHashMapIterator& other) const { return Base::m_position != other.Base::m_position; }

         PeekPtrType get() { return Base::makePeek(); }
         PeekType operator*() { return Base::makePeek(); }
         PeekPtrType operator->() { return Base::makePeek(); }

         WeakHashMapIterator& operator++()
         {
             Base::advance();
             return *this;
         }

     private:
         WeakHashMapIterator(WeakHashMap& map, typename WeakHashImplMap::iterator position)
             : Base { map, position }
         { }

         template <typename, typename, typename> friend class WeakHashMap;
     };

     class WeakHashMapConstIterator : public WeakHashMapIteratorBase<const WeakHashMap, typename WeakHashImplMap::const_iterator, const PeekPtrType, const PeekType> {
     public:
         using Base = WeakHashMapIteratorBase<const WeakHashMap, typename WeakHashImplMap::const_iterator, const PeekPtrType, const PeekType>;

         bool operator==(const WeakHashMapConstIterator& other) const { return Base::m_position == other.Base::m_position; }
         bool operator!=(const WeakHashMapConstIterator& other) const { return Base::m_position != other.Base::m_position; }

         const PeekPtrType get() const { return Base::makePeek(); }
         const PeekType operator*() const { return Base::makePeek(); }
         const PeekPtrType operator->() const { return Base::makePeek(); }

         WeakHashMapConstIterator& operator++()
         {
             Base::advance();
             return *this;
         }

     private:
         WeakHashMapConstIterator(const WeakHashMap& map, typename WeakHashImplMap::const_iterator position)
             : Base { map, position }
         { }

         template <typename, typename, typename> friend class WeakHashMap;
     };

     struct AddResult {
         AddResult() : isNewEntry(false) { }
         AddResult(WeakHashMapIterator it, bool isNewEntry) : iterator(it), isNewEntry(isNewEntry) { }
         WeakHashMapIterator iterator;
         bool isNewEntry;

         explicit operator bool() const { return isNewEntry; }
     };

     using iterator = WeakHashMapIterator;
     using const_iterator = WeakHashMapConstIterator;

     iterator begin() { return WeakHashMapIterator(*this, m_map.begin()); }
     iterator end() { return WeakHashMapIterator(*this, m_map.end()); }
     const_iterator begin() const { return WeakHashMapConstIterator(*this, m_map.begin()); }
     const_iterator end() const { return WeakHashMapConstIterator(*this, m_map.end()); }

     template <typename Functor>
     AddResult ensure(const KeyType& key, Functor&& functor)
     {
         amortizedCleanupIfNeeded();
         auto result = m_map.ensure(makeKeyImpl(key), functor);
         return AddResult { WeakHashMapIterator(*this, result.iterator), result.isNewEntry };
     }

     template<typename T>
     AddResult add(const KeyType& key, T&& value)
     {
         amortizedCleanupIfNeeded();
         auto addResult = m_map.add(makeKeyImpl(key), std::forward<T>(value));
         return AddResult { WeakHashMapIterator(*this, addResult.iterator), addResult.isNewEntry };
     }

     template<typename T, typename V>
     void set(const T& key, V&& value)
     {
         amortizedCleanupIfNeeded();
         m_map.set(makeKeyImpl(key), WTFMove(value));
     }

     iterator find(const KeyType& key)
     {
         amortizedCleanupIfNeeded();
         auto* keyImpl = keyImplIfExists(key);
         if (!keyImpl)
             return end();
         return WeakHashMapIterator(*this, m_map.find(*keyImpl));
     }

     const_iterator find(const KeyType& key) const
     {
         amortizedCleanupIfNeeded();
         auto* keyImpl = keyImplIfExists(key);
         if (!keyImpl)
             return end();
         return WeakHashMapConstIterator(*this, m_map.find(*keyImpl));
     }

     bool contains(const KeyType& key) const
     {
         amortizedCleanupIfNeeded();
         auto* keyImpl = keyImplIfExists(key);
         if (!keyImpl)
             return false;
         return m_map.contains(*keyImpl);
     }

     typename ValueTraits::TakeType take(const KeyType& key)
     {
         amortizedCleanupIfNeeded();
         auto* keyImpl = keyImplIfExists(key);
         if (!keyImpl)
             return ValueTraits::take(ValueTraits::emptyValue());
         return m_map.take(*keyImpl);
     }

     typename ValueTraits::PeekType get(const KeyType& key)
     {
         amortizedCleanupIfNeeded();
         auto* keyImpl = keyImplIfExists(key);
         if (!keyImpl)
             return ValueTraits::peek(ValueTraits::emptyValue());
         return m_map.get(*keyImpl);
     }

     bool remove(iterator it)
     {
         amortizedCleanupIfNeeded();
         return m_map.remove(it.m_position);
     }

     bool remove(const KeyType& key)
     {
         amortizedCleanupIfNeeded();
         auto* keyImpl = keyImplIfExists(key);
         if (!keyImpl)
             return false;
         return m_map.remove(keyImpl);
     }

     template<typename Functor>
     bool removeIf(Functor&& functor)
     {
         m_operationCountSinceLastCleanup = 0;
         return m_map.removeIf([&](auto& entry) {
             auto* key = static_cast<KeyType*>(entry.key->template get<KeyType>());
             bool isReleasedWeakKey = !key;
             if (isReleasedWeakKey)
                 return true;
             PeekType peek { *key, entry.value };
             return functor(peek);
         });
     }

     void clear()
     {
         m_operationCountSinceLastCleanup = 0;
         m_map.clear();
     }

     unsigned capacity() const { return m_map.capacity(); }

     bool isEmptyIgnoringNullReferences() const
     {
         auto result = begin() == end();
         if (UNLIKELY(result && m_map.size()))
             const_cast<WeakHashMap&>(*this).clear();
         return result;
     }

     bool hasNullReferences() const
     {
         unsigned count = 0;
         auto result = WTF::anyOf(m_map, [&] (auto& iterator) {
             ++count;
             return !iterator.key.get();
         });
         if (result)
             amortizedCleanupIfNeeded(count);
         else
             m_operationCountSinceLastCleanup = 0;
         return result;
     }

     unsigned computeSize() const
     {
         const_cast<WeakHashMap&>(*this).removeNullReferences();
         return m_map.size();
     }

     NEVER_INLINE bool removeNullReferences()
     {
         m_operationCountSinceLastCleanup = 0;
         return m_map.removeIf([](auto& iterator) { return !iterator.key.get(); });
     }

 #if ASSERT_ENABLED
     void checkConsistency() const { m_map.checkConsistency(); }
 #else
     void checkConsistency() const { }
 #endif

 private:
     ALWAYS_INLINE void amortizedCleanupIfNeeded(unsigned operationsPerformed = 1) const
     {
         unsigned currentCount = m_operationCountSinceLastCleanup;
         m_operationCountSinceLastCleanup = currentCount + operationsPerformed;
         if (currentCount / 2 > m_map.size())
             const_cast<WeakHashMap&>(*this).removeNullReferences();
     }

     template <typename T>
     static RefType makeKeyImpl(const T& key)
     {
         return *key.weakPtrFactory().template createWeakPtr<T>(const_cast<T&>(key)).m_impl;
     }

     template <typename T>
     static WeakPtrImpl<Counter>* keyImplIfExists(const T& key)
     {
         auto& weakPtrImpl = key.weakPtrFactory().m_impl;
         if (!weakPtrImpl || !*weakPtrImpl)
             return nullptr;
         return weakPtrImpl.get();
     }

     WeakHashImplMap m_map;
     mutable unsigned m_operationCountSinceLastCleanup { 0 }; // FIXME: Store this as a HashTable meta data.

     template <typename, typename, typename, typename> friend class WeakHashMapIteratorBase;
 };

 } // namespace WTF

 using WTF::WeakHashMap;
	/*
	* Copyright (C) 2021 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/Algorithms.h>
	#include <wtf/HashTable.h>
	#include <wtf/WeakPtr.h>

	namespace WTF {

	// Value will be deleted lazily upon rehash or amortized over time. For manual cleanup, call removeNullReferences().
	template<typename KeyType, typename ValueType, typename Counter = EmptyCounter>
	class WeakHashMap final {
	WTF_MAKE_FAST_ALLOCATED;
	public:

	using RefType = Ref<WeakPtrImpl<Counter>>;
	using KeyTraits = HashTraits<KeyType>;
	using ValueTraits = HashTraits<ValueType>;
	using WeakHashImplMap = HashMap<RefType, ValueType>;

	struct PeekKeyValuePairTraits : KeyValuePairHashTraits<HashTraits<KeyType&>, HashTraits<ValueType&>> {
	static constexpr bool hasIsEmptyValueFunction = true;
	static bool isEmptyValue(const typename KeyValuePairHashTraits<HashTraits<KeyType&>, HashTraits<ValueType&>>::TraitType& value)
	{
	return isHashTraitsEmptyValue<KeyTraits>(value.key);
	}
	};
	using PeekKeyValuePairType = typename PeekKeyValuePairTraits::TraitType;

	struct PeekType {
	KeyType& key;
	ValueType& value;
	};

	struct PeekPtrType {
	PeekPtrType(const PeekType& peek)
	: m_peek(peek)
	{ }

	const PeekType& operator*() const { return m_peek; }
	PeekType& operator*() { return m_peek; }

	const PeekType* operator->() const { return &m_peek; }
	PeekType* operator->() { return &m_peek; }

	private:
	PeekType m_peek;
	};

	template <typename MapType, typename IteratorType, typename IteratorPeekPtrType, typename IteratorPeekType>
	class WeakHashMapIteratorBase : public std::iterator<std::forward_iterator_tag, IteratorPeekType, std::ptrdiff_t, IteratorPeekPtrType, IteratorPeekType> {
	protected:
	WeakHashMapIteratorBase(MapType& weakHashMap, IteratorType position)
	: m_weakHashMap { weakHashMap }
	, m_position { position }
	, m_endPosition { weakHashMap.m_map.end() }
	{
	skipEmptyBuckets();
	}

	~WeakHashMapIteratorBase()
	{
	if (m_emptyBucketCount > m_weakHashMap.m_map.size() / 8)
	const_cast<WeakHashMap&>(m_weakHashMap).removeNullReferences();
	else
	m_weakHashMap.amortizedCleanupIfNeeded(m_advanceCount + m_emptyBucketCount);
	}

	ALWAYS_INLINE IteratorPeekType makePeek()
	{
	auto* entry = m_position.get();
	auto* key = static_cast<KeyType*>(entry->key->template get<KeyType>());
	return IteratorPeekType { *key, entry->value };
	}

	ALWAYS_INLINE IteratorPeekType makePeek() const
	{
	auto* entry = m_position.get();
	auto* key = static_cast<KeyType*>(entry->key->template get<KeyType>());
	return IteratorPeekType { *key, const_cast<ValueType&>(entry->value) };
	}

	void advance()
	{
	ASSERT(m_position != m_endPosition);
	++m_position;
	++m_advanceCount;
	skipEmptyBuckets();
	}

	void skipEmptyBuckets()
	{
	while (m_position != m_endPosition && !m_position->key.get()) {
	++m_position;
	++m_emptyBucketCount;
	}
	}

	const MapType& m_weakHashMap;
	IteratorType m_position;
	IteratorType m_endPosition;
	unsigned m_advanceCount { 0 };
	unsigned m_emptyBucketCount { 0 };
	};

	class WeakHashMapIterator : public WeakHashMapIteratorBase<WeakHashMap, typename WeakHashImplMap::iterator, PeekPtrType, PeekType> {
	public:
	using Base = WeakHashMapIteratorBase<WeakHashMap, typename WeakHashImplMap::iterator, PeekPtrType, PeekType>;

	bool operator==(const WeakHashMapIterator& other) const { return Base::m_position == other.Base::m_position; }
	bool operator!=(const WeakHashMapIterator& other) const { return Base::m_position != other.Base::m_position; }

	PeekPtrType get() { return Base::makePeek(); }
	PeekType operator*() { return Base::makePeek(); }
	PeekPtrType operator->() { return Base::makePeek(); }

	WeakHashMapIterator& operator++()
	{
	Base::advance();
	return *this;
	}

	private:
	WeakHashMapIterator(WeakHashMap& map, typename WeakHashImplMap::iterator position)
	: Base { map, position }
	{ }

	template <typename, typename, typename> friend class WeakHashMap;
	};

	class WeakHashMapConstIterator : public WeakHashMapIteratorBase<const WeakHashMap, typename WeakHashImplMap::const_iterator, const PeekPtrType, const PeekType> {
	public:
	using Base = WeakHashMapIteratorBase<const WeakHashMap, typename WeakHashImplMap::const_iterator, const PeekPtrType, const PeekType>;

	bool operator==(const WeakHashMapConstIterator& other) const { return Base::m_position == other.Base::m_position; }
	bool operator!=(const WeakHashMapConstIterator& other) const { return Base::m_position != other.Base::m_position; }

	const PeekPtrType get() const { return Base::makePeek(); }
	const PeekType operator*() const { return Base::makePeek(); }
	const PeekPtrType operator->() const { return Base::makePeek(); }

	WeakHashMapConstIterator& operator++()
	{
	Base::advance();
	return *this;
	}

	private:
	WeakHashMapConstIterator(const WeakHashMap& map, typename WeakHashImplMap::const_iterator position)
	: Base { map, position }
	{ }

	template <typename, typename, typename> friend class WeakHashMap;
	};

	struct AddResult {
	AddResult() : isNewEntry(false) { }
	AddResult(WeakHashMapIterator it, bool isNewEntry) : iterator(it), isNewEntry(isNewEntry) { }
	WeakHashMapIterator iterator;
	bool isNewEntry;

	explicit operator bool() const { return isNewEntry; }
	};

	using iterator = WeakHashMapIterator;
	using const_iterator = WeakHashMapConstIterator;

	iterator begin() { return WeakHashMapIterator(*this, m_map.begin()); }
	iterator end() { return WeakHashMapIterator(*this, m_map.end()); }
	const_iterator begin() const { return WeakHashMapConstIterator(*this, m_map.begin()); }
	const_iterator end() const { return WeakHashMapConstIterator(*this, m_map.end()); }

	template <typename Functor>
	AddResult ensure(const KeyType& key, Functor&& functor)
	{
	amortizedCleanupIfNeeded();
	auto result = m_map.ensure(makeKeyImpl(key), functor);
	return AddResult { WeakHashMapIterator(*this, result.iterator), result.isNewEntry };
	}

	template<typename T>
	AddResult add(const KeyType& key, T&& value)
	{
	amortizedCleanupIfNeeded();
	auto addResult = m_map.add(makeKeyImpl(key), std::forward<T>(value));
	return AddResult { WeakHashMapIterator(*this, addResult.iterator), addResult.isNewEntry };
	}

	template<typename T, typename V>
	void set(const T& key, V&& value)
	{
	amortizedCleanupIfNeeded();
	m_map.set(makeKeyImpl(key), WTFMove(value));
	}

	iterator find(const KeyType& key)
	{
	amortizedCleanupIfNeeded();
	auto* keyImpl = keyImplIfExists(key);
	if (!keyImpl)
	return end();
	return WeakHashMapIterator(this, m_map.find(keyImpl));
	}

	const_iterator find(const KeyType& key) const
	{
	amortizedCleanupIfNeeded();
	auto* keyImpl = keyImplIfExists(key);
	if (!keyImpl)
	return end();
	return WeakHashMapConstIterator(this, m_map.find(keyImpl));
	}

	bool contains(const KeyType& key) const
	{
	amortizedCleanupIfNeeded();
	auto* keyImpl = keyImplIfExists(key);
	if (!keyImpl)
	return false;
	return m_map.contains(*keyImpl);
	}

	typename ValueTraits::TakeType take(const KeyType& key)
	{
	amortizedCleanupIfNeeded();
	auto* keyImpl = keyImplIfExists(key);
	if (!keyImpl)
	return ValueTraits::take(ValueTraits::emptyValue());
	return m_map.take(*keyImpl);
	}

	typename ValueTraits::PeekType get(const KeyType& key)
	{
	amortizedCleanupIfNeeded();
	auto* keyImpl = keyImplIfExists(key);
	if (!keyImpl)
	return ValueTraits::peek(ValueTraits::emptyValue());
	return m_map.get(*keyImpl);
	}

	bool remove(iterator it)
	{
	amortizedCleanupIfNeeded();
	return m_map.remove(it.m_position);
	}

	bool remove(const KeyType& key)
	{
	amortizedCleanupIfNeeded();
	auto* keyImpl = keyImplIfExists(key);
	if (!keyImpl)
	return false;
	return m_map.remove(keyImpl);
	}

	template<typename Functor>
	bool removeIf(Functor&& functor)
	{
	m_operationCountSinceLastCleanup = 0;
	return m_map.removeIf([&](auto& entry) {
	auto* key = static_cast<KeyType*>(entry.key->template get<KeyType>());
	bool isReleasedWeakKey = !key;
	if (isReleasedWeakKey)
	return true;
	PeekType peek { *key, entry.value };
	return functor(peek);
	});
	}

	void clear()
	{
	m_operationCountSinceLastCleanup = 0;
	m_map.clear();
	}

	unsigned capacity() const { return m_map.capacity(); }

	bool isEmptyIgnoringNullReferences() const
	{
	auto result = begin() == end();
	if (UNLIKELY(result && m_map.size()))
	const_cast<WeakHashMap&>(*this).clear();
	return result;
	}

	bool hasNullReferences() const
	{
	unsigned count = 0;
	auto result = WTF::anyOf(m_map, [&] (auto& iterator) {
	++count;
	return !iterator.key.get();
	});
	if (result)
	amortizedCleanupIfNeeded(count);
	else
	m_operationCountSinceLastCleanup = 0;
	return result;
	}

	unsigned computeSize() const
	{
	const_cast<WeakHashMap&>(*this).removeNullReferences();
	return m_map.size();
	}

	NEVER_INLINE bool removeNullReferences()
	{
	m_operationCountSinceLastCleanup = 0;
	return m_map.removeIf([](auto& iterator) { return !iterator.key.get(); });
	}

	#if ASSERT_ENABLED
	void checkConsistency() const { m_map.checkConsistency(); }
	#else
	void checkConsistency() const { }
	#endif

	private:
	ALWAYS_INLINE void amortizedCleanupIfNeeded(unsigned operationsPerformed = 1) const
	{
	unsigned currentCount = m_operationCountSinceLastCleanup;
	m_operationCountSinceLastCleanup = currentCount + operationsPerformed;
	if (currentCount / 2 > m_map.size())
	const_cast<WeakHashMap&>(*this).removeNullReferences();
	}

	template <typename T>
	static RefType makeKeyImpl(const T& key)
	{
	return *key.weakPtrFactory().template createWeakPtr<T>(const_cast<T&>(key)).m_impl;
	}

	template <typename T>
	static WeakPtrImpl<Counter>* keyImplIfExists(const T& key)
	{
	auto& weakPtrImpl = key.weakPtrFactory().m_impl;
	if (!weakPtrImpl \|\| !*weakPtrImpl)
	return nullptr;
	return weakPtrImpl.get();
	}

	WeakHashImplMap m_map;
	mutable unsigned m_operationCountSinceLastCleanup { 0 }; // FIXME: Store this as a HashTable meta data.

	template <typename, typename, typename, typename> friend class WeakHashMapIteratorBase;
	};

	} // namespace WTF

	using WTF::WeakHashMap;