934 lines
39 KiB
C++
934 lines
39 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.
|
|
*/
|
|
/*
|
|
* Copyright 2018 The Rust Project Developers.
|
|
*
|
|
* Permission is hereby granted, free of charge, to any
|
|
* person obtaining a copy of this software and associated
|
|
* documentation files (the "Software"), to deal in the
|
|
* Software without restriction, including without
|
|
* limitation the rights to use, copy, modify, merge,
|
|
* publish, distribute, sublicense, and/or sell copies of
|
|
* the Software, and to permit persons to whom the Software
|
|
* is furnished to do so, subject to the following
|
|
* conditions:
|
|
*
|
|
* The above copyright notice and this permission notice
|
|
* shall be included in all copies or substantial portions
|
|
* of the Software.
|
|
*
|
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
|
|
* ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
|
|
* TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
|
|
* PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
|
|
* SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
|
|
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
|
|
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
|
|
* IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
|
|
* DEALINGS IN THE SOFTWARE.
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
#include <wtf/HashTable.h>
|
|
|
|
namespace WTF {
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
class RobinHoodHashTable;
|
|
|
|
// 95% load factor. This a bit regress "insertion" performance, while it keeps lookup performance sane.
|
|
// RobinHoodHashTable can work with 95% load factor because of maintained probe distance.
|
|
struct MemoryCompactLookupOnlyRobinHoodHashTableSizePolicy {
|
|
static constexpr unsigned maxLoadNumerator = 19;
|
|
static constexpr unsigned maxLoadDenominator = 20;
|
|
static constexpr unsigned minLoad = 6;
|
|
};
|
|
|
|
// 90% load factor. RobinHoodHashTable can work with such a high load-factor.
|
|
// Observed performance is slightly worse than HashTable (75% for small table, 50% for large table).
|
|
struct MemoryCompactRobinHoodHashTableSizePolicy {
|
|
static constexpr unsigned maxLoadNumerator = 9;
|
|
static constexpr unsigned maxLoadDenominator = 10;
|
|
static constexpr unsigned minLoad = 6;
|
|
};
|
|
|
|
// 75% load factor, this maintains the performance same to HashTable, still the load factor
|
|
// is higher (HashTable uses 75% for small table, 50 for large table).
|
|
struct FastRobinHoodHashTableSizePolicy {
|
|
static constexpr unsigned maxLoadNumerator = 3;
|
|
static constexpr unsigned maxLoadDenominator = 4;
|
|
static constexpr unsigned minLoad = 6;
|
|
};
|
|
|
|
// RobinHood HashTable has several limitations compared to usual HashTable, that's why this is not a default one.
|
|
// RobinHood HashTable computes hash much more frequently. This means that the Key should cache computed hash.
|
|
// But our default HashTable does not cache hash value because of memory usage. This design means that Key type
|
|
// should have hash value intrusively (e.g. WTF::String holds hash value internally).
|
|
//
|
|
// If the above requirements meet your use case, then you can try RobinHood HashTable.
|
|
// The largest benefit is that we can use significantly high load-factor (90% - 95%)!
|
|
//
|
|
// The algorithm is RobinHood-Hashing + backward shift deletion, described in [1,2].
|
|
//
|
|
// Naive RobinHoodHashTable has some cases which cause O(N^2) when iterating it and inserting it to some new RobinHoodHashTable
|
|
// without reserving capacity and this is because of high load-factor and exposed hash-ordering at iteration[3]. To mitigate it,
|
|
// we calculate hash for each table, and do XOR with the hash value to make hash-ordering different for each table.
|
|
//
|
|
// [1]: https://codecapsule.com/2013/11/11/robin-hood-hashing/
|
|
// [2]: https://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
|
|
// [3]: https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
class RobinHoodHashTable {
|
|
public:
|
|
using HashTableType = RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>;
|
|
using iterator = HashTableIterator<HashTableType, Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
|
|
using const_iterator = HashTableConstIterator<HashTableType, Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
|
|
using ValueTraits = Traits;
|
|
using KeyType = Key;
|
|
using ValueType = Value;
|
|
using IdentityTranslatorType = IdentityHashTranslator<ValueTraits, HashFunctions>;
|
|
using AddResult = HashTableAddResult<iterator>;
|
|
|
|
static constexpr unsigned probeDistanceThreshold = 128;
|
|
|
|
static_assert(!KeyTraits::hasIsReleasedWeakValueFunction);
|
|
static_assert(HashFunctions::hasHashInValue);
|
|
|
|
RobinHoodHashTable() = default;
|
|
|
|
~RobinHoodHashTable()
|
|
{
|
|
invalidateIterators(this);
|
|
if (m_table)
|
|
deallocateTable(m_table, tableSize());
|
|
}
|
|
|
|
RobinHoodHashTable(const RobinHoodHashTable&);
|
|
void swap(RobinHoodHashTable&);
|
|
RobinHoodHashTable& operator=(const RobinHoodHashTable&);
|
|
|
|
RobinHoodHashTable(RobinHoodHashTable&&);
|
|
RobinHoodHashTable& operator=(RobinHoodHashTable&&);
|
|
|
|
// When the hash table is empty, just return the same iterator for end as for begin.
|
|
// This is more efficient because we don't have to skip all the empty and deleted
|
|
// buckets, and iterating an empty table is a common case that's worth optimizing.
|
|
iterator begin() { return isEmpty() ? end() : makeIterator(m_table); }
|
|
iterator end() { return makeKnownGoodIterator(m_table + tableSize()); }
|
|
const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); }
|
|
const_iterator end() const { return makeKnownGoodConstIterator(m_table + tableSize()); }
|
|
|
|
iterator random()
|
|
{
|
|
if (isEmpty())
|
|
return end();
|
|
|
|
while (true) {
|
|
auto& bucket = m_table[weakRandomUint32() & tableSizeMask()];
|
|
if (!isEmptyBucket(bucket))
|
|
return makeKnownGoodIterator(&bucket);
|
|
}
|
|
}
|
|
|
|
const_iterator random() const { return static_cast<const_iterator>(const_cast<RobinHoodHashTable*>(this)->random()); }
|
|
|
|
unsigned size() const { return keyCount(); }
|
|
unsigned capacity() const { return tableSize(); }
|
|
bool isEmpty() const { return !keyCount(); }
|
|
|
|
void reserveInitialCapacity(unsigned keyCount)
|
|
{
|
|
ASSERT(!m_table);
|
|
ASSERT(!tableSize());
|
|
|
|
unsigned minimumTableSize = KeyTraits::minimumTableSize;
|
|
unsigned newTableSize = std::max(minimumTableSize, computeBestTableSize(keyCount));
|
|
|
|
m_table = allocateTable(newTableSize);
|
|
m_tableSize = newTableSize;
|
|
m_keyCount = 0;
|
|
m_tableHash = computeTableHash(m_table);
|
|
m_willExpand = false;
|
|
internalCheckTableConsistency();
|
|
}
|
|
|
|
AddResult add(const ValueType& value) { return add<IdentityTranslatorType>(Extractor::extract(value), value); }
|
|
AddResult add(ValueType&& value) { return add<IdentityTranslatorType>(Extractor::extract(value), WTFMove(value)); }
|
|
|
|
// A special version of add() that finds the object by hashing and comparing
|
|
// with some other type, to avoid the cost of type conversion if the object is already
|
|
// in the table.
|
|
template<typename HashTranslator, typename T, typename Extra> AddResult add(T&& key, Extra&&);
|
|
template<typename HashTranslator, typename T, typename Extra> AddResult addPassingHashCode(T&& key, Extra&&);
|
|
|
|
iterator find(const KeyType& key) { return find<IdentityTranslatorType>(key); }
|
|
const_iterator find(const KeyType& key) const { return find<IdentityTranslatorType>(key); }
|
|
bool contains(const KeyType& key) const { return contains<IdentityTranslatorType>(key); }
|
|
|
|
template<typename HashTranslator, typename T> iterator find(const T&);
|
|
template<typename HashTranslator, typename T> const_iterator find(const T&) const;
|
|
template<typename HashTranslator, typename T> bool contains(const T&) const;
|
|
|
|
void remove(const KeyType&);
|
|
void remove(iterator);
|
|
void removeWithoutEntryConsistencyCheck(iterator);
|
|
void removeWithoutEntryConsistencyCheck(const_iterator);
|
|
void clear();
|
|
|
|
static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
|
|
static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value); }
|
|
|
|
ValueType* lookup(const Key& key) { return lookup<IdentityTranslatorType>(key); }
|
|
template<typename HashTranslator, typename T> ValueType* lookup(const T&);
|
|
template<typename HashTranslator, typename T> ValueType* inlineLookup(const T&);
|
|
|
|
#if ASSERT_ENABLED
|
|
void checkTableConsistency() const;
|
|
#else
|
|
static void checkTableConsistency() { }
|
|
#endif
|
|
|
|
#if CHECK_HASHTABLE_CONSISTENCY
|
|
void internalCheckTableConsistency() const { checkTableConsistency(); }
|
|
void internalCheckTableConsistencyExceptSize() const { checkTableConsistencyExceptSize(); }
|
|
#else
|
|
static void internalCheckTableConsistencyExceptSize() { }
|
|
static void internalCheckTableConsistency() { }
|
|
#endif
|
|
|
|
static constexpr bool shouldExpand(uint64_t keyCount, uint64_t tableSize)
|
|
{
|
|
return keyCount * maxLoadDenominator >= tableSize * maxLoadNumerator;
|
|
}
|
|
|
|
private:
|
|
static ValueType* allocateTable(unsigned size);
|
|
static void deallocateTable(ValueType* table, unsigned size);
|
|
|
|
using LookupType = std::pair<ValueType*, bool>;
|
|
|
|
template<typename HashTranslator, typename T> void checkKey(const T&);
|
|
|
|
void maintainProbeDistanceForAdd(ValueType&&, unsigned index, unsigned distance, unsigned size, unsigned sizeMask, unsigned tableHash);
|
|
|
|
void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
|
|
void removeAndInvalidate(ValueType*);
|
|
void remove(ValueType*);
|
|
|
|
static unsigned computeTableHash(ValueType* table) { return DefaultHash<ValueType*>::hash(table); }
|
|
|
|
static constexpr unsigned computeBestTableSize(unsigned keyCount);
|
|
bool shouldExpand() const
|
|
{
|
|
unsigned keyCount = this->keyCount();
|
|
unsigned tableSize = this->tableSize();
|
|
if (shouldExpand(keyCount, tableSize))
|
|
return true;
|
|
// If probe-length exceeds probeDistanceThreshold, and 50%~ is filled, expand the table.
|
|
return m_willExpand && keyCount * 2 >= tableSize;
|
|
}
|
|
bool shouldShrink() const { return keyCount() * minLoad < tableSize() && tableSize() > KeyTraits::minimumTableSize; }
|
|
void expand();
|
|
void shrink() { rehash(tableSize() / 2); }
|
|
void shrinkToBestSize();
|
|
|
|
void rehash(unsigned newTableSize);
|
|
void reinsert(ValueType&&);
|
|
|
|
static void initializeBucket(ValueType& bucket);
|
|
static void deleteBucket(ValueType& bucket) { hashTraitsDeleteBucket<Traits>(bucket); }
|
|
|
|
static constexpr unsigned desiredIndex(unsigned hash, unsigned sizeMask)
|
|
{
|
|
return hash & sizeMask;
|
|
}
|
|
|
|
static constexpr unsigned probeDistance(unsigned hash, unsigned index, unsigned size, unsigned sizeMask)
|
|
{
|
|
return (index + size - desiredIndex(hash, sizeMask)) & sizeMask;
|
|
}
|
|
|
|
iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + tableSize()); }
|
|
const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + tableSize()); }
|
|
iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + tableSize(), HashItemKnownGood); }
|
|
const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + tableSize(), HashItemKnownGood); }
|
|
|
|
#if ASSERT_ENABLED
|
|
void checkTableConsistencyExceptSize() const;
|
|
#else
|
|
static void checkTableConsistencyExceptSize() { }
|
|
#endif
|
|
|
|
static constexpr unsigned maxLoadNumerator = SizePolicy::maxLoadNumerator;
|
|
static constexpr unsigned maxLoadDenominator = SizePolicy::maxLoadDenominator;
|
|
static constexpr unsigned minLoad = SizePolicy::minLoad;
|
|
|
|
unsigned tableSize() const { return m_tableSize; }
|
|
unsigned tableSizeMask() const { return m_tableSize - 1; }
|
|
unsigned keyCount() const { return m_keyCount; }
|
|
unsigned tableHash() const { return m_tableHash; }
|
|
|
|
ValueType* m_table { nullptr };
|
|
unsigned m_tableSize { 0 };
|
|
unsigned m_keyCount { 0 };
|
|
unsigned m_tableHash { 0 };
|
|
bool m_willExpand { false };
|
|
|
|
#if CHECK_HASHTABLE_ITERATORS
|
|
public:
|
|
// All access to m_iterators should be guarded with m_mutex.
|
|
mutable const_iterator* m_iterators { nullptr };
|
|
// Use std::unique_ptr so HashTable can still be memmove'd or memcpy'ed.
|
|
mutable std::unique_ptr<Lock> m_mutex { makeUnique<Lock>() };
|
|
#endif
|
|
};
|
|
|
|
#if !ASSERT_ENABLED
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
template<typename HashTranslator, typename T>
|
|
inline void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::checkKey(const T&)
|
|
{
|
|
}
|
|
|
|
#else // ASSERT_ENABLED
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
template<typename HashTranslator, typename T>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::checkKey(const T& key)
|
|
{
|
|
if (!HashFunctions::safeToCompareToEmptyOrDeleted)
|
|
return;
|
|
ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
|
|
typename std::aligned_storage<sizeof(ValueType), std::alignment_of<ValueType>::value>::type deletedValueBuffer;
|
|
ValueType* deletedValuePtr = reinterpret_cast_ptr<ValueType*>(&deletedValueBuffer);
|
|
ValueType& deletedValue = *deletedValuePtr;
|
|
Traits::constructDeletedValue(deletedValue);
|
|
ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
|
|
}
|
|
|
|
#endif // ASSERT_ENABLED
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
template<typename HashTranslator, typename T>
|
|
inline auto RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::lookup(const T& key) -> ValueType*
|
|
{
|
|
return inlineLookup<HashTranslator>(key);
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
template<typename HashTranslator, typename T>
|
|
ALWAYS_INLINE auto RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::inlineLookup(const T& key) -> ValueType*
|
|
{
|
|
checkKey<HashTranslator>(key);
|
|
|
|
ValueType* table = m_table;
|
|
if (!table)
|
|
return nullptr;
|
|
|
|
unsigned size = tableSize();
|
|
unsigned sizeMask = tableSizeMask();
|
|
unsigned tableHash = this->tableHash();
|
|
unsigned hash = HashTranslator::hash(key) ^ tableHash;
|
|
unsigned index = desiredIndex(hash, sizeMask);
|
|
unsigned distance = 0;
|
|
|
|
while (true) {
|
|
ValueType* entry = m_table + index;
|
|
if (isEmptyBucket(*entry))
|
|
return nullptr;
|
|
|
|
// RobinHoodHashTable maintains this invariant so that we can stop
|
|
// probing when distance exceeds probing distance of the existing entry.
|
|
auto& entryKey = Extractor::extract(*entry);
|
|
unsigned entryHash = IdentityTranslatorType::hash(entryKey) ^ tableHash;
|
|
if (distance > probeDistance(entryHash, index, size, sizeMask))
|
|
return nullptr;
|
|
|
|
if (entryHash == hash && HashTranslator::equal(entryKey, key))
|
|
return entry;
|
|
|
|
index = (index + 1) & sizeMask;
|
|
++distance;
|
|
}
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
inline void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::initializeBucket(ValueType& bucket)
|
|
{
|
|
HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket);
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
template<typename HashTranslator, typename T, typename Extra>
|
|
ALWAYS_INLINE auto RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::add(T&& key, Extra&& extra) -> AddResult
|
|
{
|
|
checkKey<HashTranslator>(key);
|
|
|
|
invalidateIterators(this);
|
|
|
|
// We should expand before potentially inserting an entry. If we expand a table after inserting an entry,
|
|
// we need to re-look up entry from the table since the inserted entry position is not stable during rehasing.
|
|
if (shouldExpand())
|
|
expand();
|
|
|
|
internalCheckTableConsistency();
|
|
|
|
ASSERT(m_table);
|
|
|
|
unsigned size = tableSize();
|
|
unsigned sizeMask = tableSizeMask();
|
|
unsigned tableHash = this->tableHash();
|
|
unsigned hash = HashTranslator::hash(key) ^ tableHash;
|
|
unsigned index = desiredIndex(hash, sizeMask);
|
|
unsigned distance = 0;
|
|
|
|
ValueType* entry = nullptr;
|
|
while (true) {
|
|
entry = m_table + index;
|
|
if (isEmptyBucket(*entry)) {
|
|
if (distance >= probeDistanceThreshold)
|
|
m_willExpand = true;
|
|
HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
|
|
break;
|
|
}
|
|
|
|
auto& entryKey = Extractor::extract(*entry);
|
|
unsigned entryHash = IdentityTranslatorType::hash(entryKey) ^ tableHash;
|
|
unsigned entryDistance = probeDistance(entryHash, index, size, sizeMask);
|
|
if (distance > entryDistance) {
|
|
if (distance >= probeDistanceThreshold)
|
|
m_willExpand = true;
|
|
// Start swapping existing entry to maintain probe-distance invariant.
|
|
ValueType existingEntry = WTFMove(*entry);
|
|
entry->~ValueType();
|
|
initializeBucket(*entry);
|
|
HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
|
|
maintainProbeDistanceForAdd(WTFMove(existingEntry), index, entryDistance, size, sizeMask, tableHash);
|
|
break;
|
|
}
|
|
|
|
if (entryHash == hash && HashTranslator::equal(entryKey, key))
|
|
return AddResult(makeKnownGoodIterator(entry), false);
|
|
|
|
index = (index + 1) & sizeMask;
|
|
++distance;
|
|
}
|
|
|
|
m_keyCount += 1;
|
|
|
|
internalCheckTableConsistency();
|
|
|
|
return AddResult(makeKnownGoodIterator(entry), true);
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
ALWAYS_INLINE void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::maintainProbeDistanceForAdd(ValueType&& value, unsigned index, unsigned distance, unsigned size, unsigned sizeMask, unsigned tableHash)
|
|
{
|
|
using std::swap; // For C++ ADL.
|
|
index = (index + 1) & sizeMask;
|
|
++distance;
|
|
|
|
while (true) {
|
|
ValueType* entry = m_table + index;
|
|
if (isEmptyBucket(*entry)) {
|
|
ValueTraits::assignToEmpty(*entry, WTFMove(value));
|
|
return;
|
|
}
|
|
|
|
unsigned entryHash = IdentityTranslatorType::hash(Extractor::extract(*entry)) ^ tableHash;
|
|
unsigned entryDistance = probeDistance(entryHash, index, size, sizeMask);
|
|
if (distance > entryDistance) {
|
|
swap(value, *entry);
|
|
distance = entryDistance;
|
|
}
|
|
|
|
index = (index + 1) & sizeMask;
|
|
++distance;
|
|
}
|
|
}
|
|
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
template<typename HashTranslator, typename T, typename Extra>
|
|
inline auto RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::addPassingHashCode(T&& key, Extra&& extra) -> AddResult
|
|
{
|
|
checkKey<HashTranslator>(key);
|
|
|
|
invalidateIterators(this);
|
|
|
|
// We should expand before potentially inserting an entry. If we expand a table after inserting an entry,
|
|
// we need to re-look up entry from the table since the inserted entry position is not stable during rehasing.
|
|
if (shouldExpand())
|
|
expand();
|
|
|
|
internalCheckTableConsistency();
|
|
|
|
ASSERT(m_table);
|
|
|
|
unsigned size = tableSize();
|
|
unsigned sizeMask = tableSizeMask();
|
|
unsigned tableHash = this->tableHash();
|
|
unsigned originalHash = HashTranslator::hash(key);
|
|
unsigned hash = originalHash ^ tableHash;
|
|
unsigned index = desiredIndex(hash, sizeMask);
|
|
unsigned distance = 0;
|
|
|
|
ValueType* entry = nullptr;
|
|
while (true) {
|
|
entry = m_table + index;
|
|
if (isEmptyBucket(*entry)) {
|
|
if (distance >= probeDistanceThreshold)
|
|
m_willExpand = true;
|
|
HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra), originalHash);
|
|
break;
|
|
}
|
|
|
|
auto& entryKey = Extractor::extract(*entry);
|
|
unsigned entryHash = IdentityTranslatorType::hash(entryKey) ^ tableHash;
|
|
unsigned entryDistance = probeDistance(entryHash, index, size, sizeMask);
|
|
if (distance > entryDistance) {
|
|
if (distance >= probeDistanceThreshold)
|
|
m_willExpand = true;
|
|
// Start swapping existing entry to maintain probe-distance invariant.
|
|
ValueType existingEntry = WTFMove(*entry);
|
|
entry->~ValueType();
|
|
initializeBucket(*entry);
|
|
HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra), originalHash);
|
|
maintainProbeDistanceForAdd(WTFMove(existingEntry), index, entryDistance, size, sizeMask, tableHash);
|
|
break;
|
|
}
|
|
|
|
if (entryHash == hash && HashTranslator::equal(entryKey, key))
|
|
return AddResult(makeKnownGoodIterator(entry), false);
|
|
|
|
index = (index + 1) & sizeMask;
|
|
++distance;
|
|
}
|
|
|
|
m_keyCount += 1;
|
|
|
|
internalCheckTableConsistency();
|
|
|
|
return AddResult(makeKnownGoodIterator(entry), true);
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
inline void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::reinsert(ValueType&& value)
|
|
{
|
|
using std::swap; // For C++ ADL.
|
|
unsigned size = tableSize();
|
|
unsigned sizeMask = tableSizeMask();
|
|
unsigned tableHash = this->tableHash();
|
|
unsigned hash = IdentityTranslatorType::hash(Extractor::extract(value)) ^ tableHash;
|
|
unsigned index = desiredIndex(hash, sizeMask);
|
|
unsigned distance = 0;
|
|
|
|
while (true) {
|
|
ValueType* entry = m_table + index;
|
|
if (isEmptyBucket(*entry)) {
|
|
ValueTraits::assignToEmpty(*entry, WTFMove(value));
|
|
return;
|
|
}
|
|
|
|
unsigned entryHash = IdentityTranslatorType::hash(Extractor::extract(*entry)) ^ tableHash;
|
|
unsigned entryDistance = probeDistance(entryHash, index, size, sizeMask);
|
|
if (distance > entryDistance) {
|
|
swap(value, *entry);
|
|
distance = entryDistance;
|
|
}
|
|
|
|
index = (index + 1) & sizeMask;
|
|
++distance;
|
|
}
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
template <typename HashTranslator, typename T>
|
|
auto RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::find(const T& key) -> iterator
|
|
{
|
|
if (!m_table)
|
|
return end();
|
|
|
|
ValueType* entry = lookup<HashTranslator>(key);
|
|
if (!entry)
|
|
return end();
|
|
|
|
return makeKnownGoodIterator(entry);
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
template <typename HashTranslator, typename T>
|
|
auto RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::find(const T& key) const -> const_iterator
|
|
{
|
|
if (!m_table)
|
|
return end();
|
|
|
|
ValueType* entry = const_cast<RobinHoodHashTable*>(this)->lookup<HashTranslator>(key);
|
|
if (!entry)
|
|
return end();
|
|
|
|
return makeKnownGoodConstIterator(entry);
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
template <typename HashTranslator, typename T>
|
|
bool RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::contains(const T& key) const
|
|
{
|
|
if (!m_table)
|
|
return false;
|
|
|
|
return const_cast<RobinHoodHashTable*>(this)->lookup<HashTranslator>(key);
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos)
|
|
{
|
|
invalidateIterators(this);
|
|
remove(pos);
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::removeAndInvalidate(ValueType* pos)
|
|
{
|
|
invalidateIterators(this);
|
|
internalCheckTableConsistency();
|
|
remove(pos);
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::remove(ValueType* pos)
|
|
{
|
|
// This is removal via "backward-shift-deletion". This basically shift existing entries to removed empty entry place so that we make
|
|
// the table as if no removal happened so far. This decreases distance-to-initial-bucket (DIB) of the subsequent entries by 1. This maintains
|
|
// DIB of the table low and relatively constant even if we have many removals, compared to using tombstones.
|
|
// https://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
|
|
deleteBucket(*pos);
|
|
initializeBucket(*pos);
|
|
m_keyCount -= 1;
|
|
|
|
unsigned size = tableSize();
|
|
unsigned sizeMask = tableSizeMask();
|
|
unsigned tableHash = this->tableHash();
|
|
unsigned indexPrevious = pos - m_table;
|
|
unsigned index = (indexPrevious + 1) & sizeMask;
|
|
|
|
while (true) {
|
|
Value* previousEntry = m_table + indexPrevious;
|
|
Value* entry = m_table + index;
|
|
if (isEmptyBucket(*entry))
|
|
break;
|
|
|
|
ASSERT(isEmptyBucket(*previousEntry));
|
|
auto& entryKey = Extractor::extract(*entry);
|
|
unsigned entryHash = IdentityTranslatorType::hash(entryKey) ^ tableHash;
|
|
if (!probeDistance(entryHash, index, size, sizeMask))
|
|
break;
|
|
|
|
ValueTraits::assignToEmpty(*previousEntry, WTFMove(*entry));
|
|
entry->~ValueType();
|
|
initializeBucket(*entry);
|
|
|
|
indexPrevious = index;
|
|
index = (index + 1) & sizeMask;
|
|
}
|
|
|
|
if (shouldShrink())
|
|
shrink();
|
|
|
|
internalCheckTableConsistency();
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
inline void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::remove(iterator it)
|
|
{
|
|
if (it == end())
|
|
return;
|
|
|
|
removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position));
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
inline void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::removeWithoutEntryConsistencyCheck(iterator it)
|
|
{
|
|
if (it == end())
|
|
return;
|
|
|
|
removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position));
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
inline void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::removeWithoutEntryConsistencyCheck(const_iterator it)
|
|
{
|
|
if (it == end())
|
|
return;
|
|
|
|
removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_position));
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
inline void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::remove(const KeyType& key)
|
|
{
|
|
remove(find(key));
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
auto RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::allocateTable(unsigned size) -> ValueType*
|
|
{
|
|
// would use a template member function with explicit specializations here, but
|
|
// gcc doesn't appear to support that
|
|
if constexpr (Traits::emptyValueIsZero)
|
|
return reinterpret_cast_ptr<ValueType*>(static_cast<char*>(HashTableMalloc::zeroedMalloc(size * sizeof(ValueType))));
|
|
|
|
ValueType* result = reinterpret_cast_ptr<ValueType*>(static_cast<char*>(HashTableMalloc::malloc(size * sizeof(ValueType))));
|
|
for (unsigned i = 0; i < size; i++)
|
|
initializeBucket(result[i]);
|
|
return result;
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::deallocateTable(ValueType* table, unsigned size)
|
|
{
|
|
for (unsigned i = 0; i < size; ++i)
|
|
table[i].~ValueType();
|
|
HashTableMalloc::free(reinterpret_cast<char*>(table));
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::expand()
|
|
{
|
|
unsigned newSize;
|
|
unsigned oldSize = tableSize();
|
|
if (!oldSize)
|
|
newSize = KeyTraits::minimumTableSize;
|
|
else
|
|
newSize = oldSize * 2;
|
|
|
|
rehash(newSize);
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
constexpr unsigned RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::computeBestTableSize(unsigned keyCount)
|
|
{
|
|
unsigned bestTableSize = WTF::roundUpToPowerOfTwo(keyCount);
|
|
|
|
if (shouldExpand(keyCount, bestTableSize))
|
|
bestTableSize *= 2;
|
|
|
|
auto aboveThresholdForEagerExpansion = [](double loadFactor, unsigned keyCount, unsigned tableSize)
|
|
{
|
|
// Here is the rationale behind this calculation, using 3/4 load-factor.
|
|
// With maxLoad at 3/4 and minLoad at 1/6, our average load is 11/24.
|
|
// If we are getting half-way between 11/24 and 3/4, we double the size
|
|
// to avoid being too close to loadMax and bring the ratio close to 11/24. This
|
|
// give us a load in the bounds [9/24, 15/24).
|
|
double maxLoadRatio = loadFactor;
|
|
double minLoadRatio = 1.0 / minLoad;
|
|
double averageLoadRatio = (maxLoadRatio + minLoadRatio) / 2;
|
|
double halfWayBetweenAverageAndMaxLoadRatio = (averageLoadRatio + maxLoadRatio) / 2;
|
|
return keyCount >= tableSize * halfWayBetweenAverageAndMaxLoadRatio;
|
|
};
|
|
|
|
constexpr double loadFactor = static_cast<double>(maxLoadNumerator) / maxLoadDenominator;
|
|
if (aboveThresholdForEagerExpansion(loadFactor, keyCount, bestTableSize))
|
|
bestTableSize *= 2;
|
|
unsigned minimumTableSize = KeyTraits::minimumTableSize;
|
|
return std::max(bestTableSize, minimumTableSize);
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::shrinkToBestSize()
|
|
{
|
|
unsigned minimumTableSize = KeyTraits::minimumTableSize;
|
|
rehash(std::max(minimumTableSize, computeBestTableSize(keyCount())));
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::rehash(unsigned newTableSize)
|
|
{
|
|
internalCheckTableConsistencyExceptSize();
|
|
|
|
unsigned oldTableSize = tableSize();
|
|
ValueType* oldTable = m_table;
|
|
|
|
m_table = allocateTable(newTableSize);
|
|
m_tableSize = newTableSize;
|
|
m_tableHash = computeTableHash(m_table);
|
|
m_willExpand = false;
|
|
|
|
for (unsigned i = 0; i < oldTableSize; ++i) {
|
|
auto* oldEntry = oldTable + i;
|
|
if (!isEmptyBucket(*oldEntry))
|
|
reinsert(WTFMove(*oldEntry));
|
|
oldEntry->~ValueType();
|
|
}
|
|
|
|
if (oldTable)
|
|
HashTableMalloc::free(reinterpret_cast<char*>(oldTable));
|
|
|
|
internalCheckTableConsistency();
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::clear()
|
|
{
|
|
invalidateIterators(this);
|
|
if (!m_table)
|
|
return;
|
|
|
|
unsigned oldTableSize = tableSize();
|
|
m_tableSize = 0;
|
|
m_keyCount = 0;
|
|
m_tableHash = 0;
|
|
m_willExpand = false;
|
|
deallocateTable(std::exchange(m_table, nullptr), oldTableSize);
|
|
internalCheckTableConsistency();
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::RobinHoodHashTable(const RobinHoodHashTable& other)
|
|
{
|
|
if (!other.m_tableSize || !other.m_keyCount)
|
|
return;
|
|
|
|
m_table = allocateTable(other.m_tableSize);
|
|
m_tableSize = other.m_tableSize;
|
|
m_keyCount = other.m_keyCount;
|
|
m_tableHash = computeTableHash(m_table);
|
|
m_willExpand = other.m_willExpand;
|
|
|
|
for (unsigned index = 0; index < other.m_tableSize; ++index) {
|
|
ValueType& otherEntry = other.m_table[index];
|
|
if (!isEmptyBucket(otherEntry)) {
|
|
ValueType entry(otherEntry);
|
|
reinsert(WTFMove(entry));
|
|
}
|
|
}
|
|
internalCheckTableConsistency();
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::swap(RobinHoodHashTable& other)
|
|
{
|
|
using std::swap; // For C++ ADL.
|
|
invalidateIterators(this);
|
|
invalidateIterators(&other);
|
|
|
|
swap(m_table, other.m_table);
|
|
swap(m_tableSize, other.m_tableSize);
|
|
swap(m_keyCount, other.m_keyCount);
|
|
swap(m_tableHash, other.m_tableHash);
|
|
swap(m_willExpand, other.m_willExpand);
|
|
|
|
internalCheckTableConsistency();
|
|
other.internalCheckTableConsistency();
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
auto RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::operator=(const RobinHoodHashTable& other) -> RobinHoodHashTable&
|
|
{
|
|
RobinHoodHashTable tmp(other);
|
|
swap(tmp);
|
|
return *this;
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
inline RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::RobinHoodHashTable(RobinHoodHashTable&& other)
|
|
{
|
|
invalidateIterators(&other);
|
|
|
|
m_table = std::exchange(other.m_table, nullptr);
|
|
m_tableSize = std::exchange(other.m_tableSize, 0);
|
|
m_keyCount = std::exchange(other.m_keyCount, 0);
|
|
m_tableHash = std::exchange(other.m_tableHash, 0);
|
|
m_willExpand = std::exchange(other.m_willExpand, false);
|
|
|
|
internalCheckTableConsistency();
|
|
other.internalCheckTableConsistency();
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
inline auto RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::operator=(RobinHoodHashTable&& other) -> RobinHoodHashTable&
|
|
{
|
|
RobinHoodHashTable temp(WTFMove(other));
|
|
swap(temp);
|
|
return *this;
|
|
}
|
|
|
|
|
|
#if ASSERT_ENABLED
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::checkTableConsistency() const
|
|
{
|
|
checkTableConsistencyExceptSize();
|
|
}
|
|
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename SizePolicy>
|
|
void RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, SizePolicy>::checkTableConsistencyExceptSize() const
|
|
{
|
|
if (!m_table)
|
|
return;
|
|
|
|
unsigned count = 0;
|
|
unsigned tableSize = this->tableSize();
|
|
for (unsigned i = 0; i < tableSize; ++i) {
|
|
ValueType* entry = m_table + i;
|
|
if (isEmptyBucket(*entry))
|
|
continue;
|
|
|
|
auto& key = Extractor::extract(*entry);
|
|
const_iterator it = find(key);
|
|
ASSERT(entry == it.m_position);
|
|
++count;
|
|
|
|
ValueCheck<Key>::checkConsistency(key);
|
|
}
|
|
|
|
ASSERT(count == keyCount());
|
|
ASSERT(this->tableSize() >= KeyTraits::minimumTableSize);
|
|
ASSERT(tableSizeMask());
|
|
ASSERT(this->tableSize() == tableSizeMask() + 1);
|
|
}
|
|
|
|
#endif // ASSERT_ENABLED
|
|
|
|
struct MemoryCompactLookupOnlyRobinHoodHashTableTraits {
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
|
|
using TableType = RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, MemoryCompactLookupOnlyRobinHoodHashTableSizePolicy>;
|
|
};
|
|
|
|
struct MemoryCompactRobinHoodHashTableTraits {
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
|
|
using TableType = RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, MemoryCompactRobinHoodHashTableSizePolicy>;
|
|
};
|
|
|
|
struct FastRobinHoodHashTableTraits {
|
|
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
|
|
using TableType = RobinHoodHashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, FastRobinHoodHashTableSizePolicy>;
|
|
};
|
|
|
|
} // namespace WTF
|