375 lines
13 KiB
C++
375 lines
13 KiB
C++
/*
|
|
* 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 *makeWeakPtr<KeyType>(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;
|