Source/WTF/wtf/RobinHoodHashTable.h

/*
 * 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>
#include <wtf/text/StringHash.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