flat_hashtable.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_CONTAINER_FLAT_HASHTABLE_HPP__
#define NEFORCE_CORE_CONTAINER_FLAT_HASHTABLE_HPP__

 
#include "NeForce/core/algorithm/sort.hpp"
#include "NeForce/core/container/vector.hpp"
#include "NeForce/core/interface/icollector.hpp"
#include "NeForce/core/interface/iiterator.hpp"
#include "NeForce/core/memory/construct.hpp"
#include "NeForce/core/memory/bit.hpp"
#include "NeForce/core/simd/bytes.hpp"
NEFORCE_BEGIN_NAMESPACE__

 
template <typename Value, typename Key, typename HashFcn, typename ExtractKey, typename EqualKey, typename Alloc>
class flat_hashtable;

template <bool IsConst, typename FlatHT>
struct flat_hashtable_iterator : iiterator<flat_hashtable_iterator<IsConst, FlatHT>> {
public:
    using container_type = FlatHT;                                    
    using value_type = typename container_type::value_type;           
    using size_type = typename container_type::size_type;             
    using difference_type = typename container_type::difference_type; 
    using iterator_category = forward_iterator_tag;                   
    using reference = conditional_t<IsConst, typename container_type::const_reference,
                                    typename container_type::reference>; 
    using pointer = conditional_t<IsConst, typename container_type::const_pointer,
                                  typename container_type::pointer>; 
 
private:
    size_type index_ = 0;                       
    const container_type* container_ = nullptr; 
 
    template <typename, typename, typename, typename, typename, typename>
    friend class flat_hashtable;
 
public:
    flat_hashtable_iterator() noexcept = default;
    ~flat_hashtable_iterator() = default;
 
    flat_hashtable_iterator(const flat_hashtable_iterator&) noexcept = default;
    flat_hashtable_iterator& operator=(const flat_hashtable_iterator&) noexcept = default;
    flat_hashtable_iterator(flat_hashtable_iterator&&) noexcept = default;
    flat_hashtable_iterator& operator=(flat_hashtable_iterator&&) noexcept = default;

    flat_hashtable_iterator(const size_type index, const container_type* container) noexcept :
    index_(index),
    container_(container) {}

    NEFORCE_NODISCARD reference dereference() const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ != nullptr, "null container in flat_hashtable_iterator");
        NEFORCE_DEBUG_VERIFY(index_ < container_->capacity_, "index out of range in flat_hashtable_iterator");
        return container_->data_[index_];
    }

    void increment() noexcept {
        NEFORCE_DEBUG_VERIFY(container_ != nullptr, "null container in flat_hashtable_iterator");
        ++index_;
        while (index_ < container_->capacity_) {
            const byte_t meta = container_->metadata_[index_];
            if (meta != container_type::FLAT_HT_EMPTY && meta != container_type::FLAT_HT_DELETED) {
                return;
            }
            ++index_;
        }
    }

    NEFORCE_NODISCARD bool equal_to(const flat_hashtable_iterator& rhs) const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ == rhs.container_, "comparing iterators from different containers");
        return index_ == rhs.index_;
    }

    NEFORCE_NODISCARD size_type index() const noexcept { return index_; }

    NEFORCE_NODISCARD const container_type* container() const noexcept { return container_; }
};

template <typename Value, typename Key, typename HashFcn, typename ExtractKey, typename EqualKey, typename Alloc>
class flat_hashtable : public icollector<flat_hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>> {
public:
    using key_type = Key;       
    using hasher = HashFcn;     
    using key_equal = EqualKey; 
    using value_type = Value;   
 
    using pointer = Value*;               
    using reference = Value&;             
    using const_pointer = const Value*;   
    using const_reference = const Value&; 
    using size_type = size_t;             
    using difference_type = ptrdiff_t;    
 
    using iterator = flat_hashtable_iterator<false, flat_hashtable>;      
    using const_iterator = flat_hashtable_iterator<true, flat_hashtable>; 
 
    using allocator_type = Alloc; 
 
    static constexpr byte_t FLAT_HT_EMPTY = 0x80;   
    static constexpr byte_t FLAT_HT_DELETED = 0xFE; 
    static constexpr byte_t FLAT_HT_H2_MASK = 0x7F; 
    static constexpr size_t npos = static_cast<size_t>(-1);
 
private:
    Value* data_ = nullptr;      
    byte_t* metadata_ = nullptr; 
    size_t capacity_ = 0;        
    size_t size_ = 0;            
    size_t growth_left_ = 0;     
    hasher hasher_{};            
    key_equal equals_{};         
    ExtractKey extracter_{};     
 
    compressed_pair<allocator_type, float> alloc_lf_{default_construct_tag{}, 0.875F}; 
 
    template <bool, typename>
    friend struct flat_hashtable_iterator;
 
private:
    static size_t next_power_of_2(const size_t n) noexcept {
        if (n <= 16) {
            return 16;
        }
        size_t result = 1;
        while (result < n) {
            result <<= 1;
        }
        return result;
    }

    NEFORCE_NODISCARD size_t hash_to_index(const size_t hash) const noexcept { return (hash >> 7) & (capacity_ - 1); }

    static byte_t hash_to_h2(const size_t hash) noexcept { return static_cast<byte_t>(hash & FLAT_HT_H2_MASK); }

    allocator_type& get_allocator() noexcept { return alloc_lf_.get_base(); }

    void alloc_arrays(const size_t cap) {
        if (cap == 0) {
            return;
        }
        allocator_type& alloc = get_allocator();
        data_ = alloc.allocate(cap);
        metadata_ = static_cast<byte_t*>(::operator new(cap * sizeof(byte_t), std::nothrow));
        if (metadata_ == nullptr) {
            alloc.deallocate(data_, cap);
            data_ = nullptr;
            NEFORCE_THROW_EXCEPTION(memory_exception("flat_hashtable metadata allocation failed"));
        }
        for (size_t i = 0; i < cap; ++i) {
            metadata_[i] = FLAT_HT_EMPTY;
        }
    }

    void free_arrays() noexcept {
        if (data_ && capacity_ > 0) {
            for (size_t i = 0; i < capacity_; ++i) {
                if (metadata_[i] != FLAT_HT_EMPTY && metadata_[i] != FLAT_HT_DELETED) {
                    _NEFORCE destroy(&data_[i]);
                }
            }
            allocator_type& alloc = get_allocator();
            alloc.deallocate(data_, capacity_);
            data_ = nullptr;
        }
        if (metadata_ != nullptr) {
            ::operator delete(metadata_, std::nothrow);
            metadata_ = nullptr;
        }
    }

    pair<size_t, bool> probe_find_or_insert(const key_type& key, const byte_t h2) const noexcept {
        const size_t h1 = hash_to_index(hasher_(key));
        size_t idx = h1;
        size_t first_deleted = npos;
 
        for (size_t i = 0; i < capacity_; ++i) {
            const byte_t meta = metadata_[idx];
            if (meta == FLAT_HT_EMPTY) {
                return {first_deleted != npos ? first_deleted : idx, false};
            }
            if (meta == FLAT_HT_DELETED) {
                if (first_deleted == npos) {
                    first_deleted = idx;
                }
            } else if (meta == h2 && equals_(extracter_(data_[idx]), key)) {
                return {idx, true};
            }
            idx = (idx + 1) & (capacity_ - 1);
        }
        return {first_deleted, false};
    }

    pair<size_t, bool> probe_find_or_insert_simd(const key_type& key, const byte_t h2) const noexcept {
        const size_t h1 = hash_to_index(hasher_(key));
        size_t idx = h1;
        size_t first_deleted = npos;
 
        const simd::vec128_t h2_vec = simd::fill_byte(h2);
        const simd::vec128_t empty_vec = simd::fill_byte(FLAT_HT_EMPTY);
        const simd::vec128_t deleted_vec = simd::fill_byte(FLAT_HT_DELETED);
 
        for (size_t round = 0; round < capacity_; round += 16) {
            // wrap-around safe load: metadata array is exactly capacity_ bytes,
            // a 16-byte load from idx may cross the array boundary
            simd::vec128_t meta_vec;
            const size_t remaining = capacity_ - idx;
            if (remaining >= 16) {
                meta_vec = simd::load_unaligned(metadata_ + idx);
            } else {
                byte_t buf[16];
                for (size_t k = 0; k < remaining; ++k) {
                    buf[k] = metadata_[idx + k];
                }
                for (size_t k = 0; k < 16 - remaining; ++k) {
                    buf[remaining + k] = metadata_[k];
                }
                meta_vec = simd::load_unaligned(buf);
            }
 
            const int h2_mask = simd::to_bitmask(simd::match_bytes(meta_vec, h2_vec));
            const int empty_mask = simd::to_bitmask(simd::match_bytes(meta_vec, empty_vec));
            const int deleted_mask = simd::to_bitmask(simd::match_bytes(meta_vec, deleted_vec));
 
            int match = h2_mask;
            while (match != 0) {
                const int bit = countr_zero(static_cast<uintptr_t>(match));
                const size_t slot = (idx + bit) & (capacity_ - 1);
                if (equals_(extracter_(data_[slot]), key)) {
                    return {slot, true};
                }
                match &= (match - 1);
            }
 
            if (empty_mask != 0) {
                const int empty_bit = countr_zero(static_cast<uintptr_t>(empty_mask));
                const size_t empty_slot = (idx + empty_bit) & (capacity_ - 1);
                if (first_deleted != npos) {
                    const size_t probe_dist_empty =
                            (empty_slot >= h1) ? (empty_slot - h1) : (capacity_ - h1 + empty_slot);
                    const size_t probe_dist_del =
                            (first_deleted >= h1) ? (first_deleted - h1) : (capacity_ - h1 + first_deleted);
                    if (probe_dist_del < probe_dist_empty) {
                        return {first_deleted, false};
                    }
                }
                return {empty_slot, false};
            }
 
            const int del = deleted_mask;
            if ((del != 0) && first_deleted == npos) {
                const int del_bit = countr_zero(static_cast<uintptr_t>(del));
                first_deleted = (idx + del_bit) & (capacity_ - 1);
            }
 
            idx = (idx + 16) & (capacity_ - 1);
        }
        return {first_deleted, false};
    }

    NEFORCE_NODISCARD bool should_rehash() const noexcept { return growth_left_ == 0; }

    void rehash_impl(const size_t min_capacity) {
        const size_t needed = max(min_capacity, static_cast<size_t>(static_cast<double>(size_) / max_load_factor()));
        const size_t new_capacity = next_power_of_2(needed);
        if (new_capacity <= capacity_) {
            return;
        }
 
        allocator_type& alloc = get_allocator();
        Value* new_data = alloc.allocate(new_capacity);
        auto* new_metadata = static_cast<byte_t*>(::operator new(new_capacity * sizeof(byte_t), std::nothrow));
        if (new_metadata == nullptr) {
            alloc.deallocate(new_data, new_capacity);
            NEFORCE_THROW_EXCEPTION(memory_exception("flat_hashtable rehash metadata allocation failed"));
        }
        for (size_t i = 0; i < new_capacity; ++i) {
            new_metadata[i] = FLAT_HT_EMPTY;
        }
 
        const size_t old_capacity = capacity_;
        Value* const old_data = data_;
        byte_t* const old_metadata = metadata_;
 
        try {
            for (size_t i = 0; i < old_capacity; ++i) {
                if (old_metadata[i] != FLAT_HT_EMPTY && old_metadata[i] != FLAT_HT_DELETED) {
                    const key_type& key = extracter_(old_data[i]);
                    const size_t hash = hasher_(key);
                    const byte_t h2 = hash_to_h2(hash);
                    const size_t h1 = (hash >> 7) & (new_capacity - 1);
 
                    size_t new_idx = h1;
                    bool placed = false;
                    for (size_t j = 0; j < new_capacity; ++j) {
                        const byte_t nm = new_metadata[new_idx];
                        if (nm == FLAT_HT_EMPTY) {
                            break;
                        }
                        if (nm == h2 && equals_(extracter_(new_data[new_idx]), key)) {
                            size_t run_end = new_idx;
                            for (size_t k = j + 1; k < new_capacity; ++k) {
                                run_end = (run_end + 1) & (new_capacity - 1);
                                const byte_t rmn = new_metadata[run_end];
                                if (rmn == FLAT_HT_EMPTY) {
                                    new_idx = run_end;
                                    placed = true;
                                    break;
                                }
                                if (rmn == h2 && equals_(extracter_(new_data[run_end]), key)) {
                                    continue;
                                }
                                size_t shift_end = run_end;
                                for (size_t m = 0; m < new_capacity; ++m) {
                                    shift_end = (shift_end + 1) & (new_capacity - 1);
                                    if (new_metadata[shift_end] == FLAT_HT_EMPTY) {
                                        break;
                                    }
                                }
                                while (shift_end != run_end) {
                                    const size_t prev = (shift_end - 1) & (new_capacity - 1);
                                    _NEFORCE construct(&new_data[shift_end], _NEFORCE move(new_data[prev]));
                                    _NEFORCE destroy(&new_data[prev]);
                                    new_metadata[shift_end] = new_metadata[prev];
                                    shift_end = prev;
                                }
                                new_idx = run_end;
                                placed = true;
                                break;
                            }
                            if (!placed) {
                                new_idx = run_end;
                            }
                            break;
                        }
                        new_idx = (new_idx + 1) & (new_capacity - 1);
                    }
                    _NEFORCE construct(&new_data[new_idx], _NEFORCE move(old_data[i]));
                    new_metadata[new_idx] = h2;
                }
            }
        } catch (...) {
            for (size_t i = 0; i < new_capacity; ++i) {
                if (new_metadata[i] != FLAT_HT_EMPTY && new_metadata[i] != FLAT_HT_DELETED) {
                    _NEFORCE destroy(&new_data[i]);
                }
            }
            alloc.deallocate(new_data, new_capacity);
            ::operator delete(new_metadata, std::nothrow);
            throw;
        }
 
        if (old_data) {
            alloc.deallocate(old_data, old_capacity);
        }
        if (old_metadata != nullptr) {
            ::operator delete(old_metadata, std::nothrow);
        }
 
        data_ = new_data;
        metadata_ = new_metadata;
        capacity_ = new_capacity;
        growth_left_ = static_cast<size_t>(static_cast<double>(capacity_) * max_load_factor()) - size_;
    }

    template <typename... Args>
    void construct_at(const size_t idx, const byte_t h2, Args&&... args) {
        _NEFORCE construct(&data_[idx], _NEFORCE forward<Args>(args)...);
        metadata_[idx] = h2;
        ++size_;
        --growth_left_;
    }

    void shift_make_room(const size_t pos) noexcept {
        size_t end = pos;
        for (size_t i = 0; i < capacity_; ++i) {
            end = (end + 1) & (capacity_ - 1);
            const byte_t m = metadata_[end];
            if (m == FLAT_HT_EMPTY || m == FLAT_HT_DELETED) {
                break;
            }
        }
        while (end != pos) {
            const size_t prev = (end - 1) & (capacity_ - 1);
            _NEFORCE construct(&data_[end], _NEFORCE move(data_[prev]));
            _NEFORCE destroy(&data_[prev]);
            metadata_[end] = metadata_[prev];
            end = prev;
        }
    }

    void copy_from(const flat_hashtable& other) {
        if (other.capacity_ == 0) {
            return;
        }
        alloc_arrays(other.capacity_);
        capacity_ = other.capacity_;
        growth_left_ = other.growth_left_;
        try {
            for (size_t i = 0; i < other.capacity_; ++i) {
                metadata_[i] = other.metadata_[i];
                if (other.metadata_[i] != FLAT_HT_EMPTY && other.metadata_[i] != FLAT_HT_DELETED) {
                    _NEFORCE construct(&data_[i], other.data_[i]);
                }
            }
            size_ = other.size_;
        } catch (...) {
            clear();
            throw;
        }
    }
 
    bool equal_small(const flat_hashtable& rhs) const {
        for (const_iterator iter = begin(); iter != end(); ++iter) {
            const key_type& key = extracter_(*iter);
            const size_t count_lhs = _NEFORCE count_if(
                    begin(), end(), [this, &key](const value_type& val) { return equals_(extracter_(val), key); });
            const size_t count_rhs = _NEFORCE count_if(rhs.begin(), rhs.end(), [&rhs, &key](const value_type& val) {
                return rhs.equals_(rhs.extracter_(val), key);
            });
            if (count_lhs != count_rhs) {
                return false;
            }
        }
        return true;
    }
 
    bool equal_large(const flat_hashtable& rhs) const {
        if (size_ != rhs.size_) {
            return false;
        }
        vector<const value_type*> ptrs_lhs, ptrs_rhs;
        ptrs_lhs.reserve(size_);
        ptrs_rhs.reserve(size_);
        for (const_iterator it = begin(); it != end(); ++it) {
            ptrs_lhs.push_back(&(*it));
        }
        for (const_iterator it = rhs.begin(); it != rhs.end(); ++it) {
            ptrs_rhs.push_back(&(*it));
        }
 
        auto key_less = [this](const value_type* a, const value_type* b) { return extracter_(*a) < extracter_(*b); };
        auto rhs_key_less = [&rhs](const value_type* a, const value_type* b) {
            return rhs.extracter_(*a) < rhs.extracter_(*b);
        };
        _NEFORCE sort(ptrs_lhs.begin(), ptrs_lhs.end(), key_less);
        _NEFORCE sort(ptrs_rhs.begin(), ptrs_rhs.end(), rhs_key_less);
 
        size_type i = 0, j = 0;
        const size_type n = ptrs_lhs.size();
        while (i < n && j < n) {
            const key_type& key_l = extracter_(*ptrs_lhs[i]);
            const key_type& key_r = rhs.extracter_(*ptrs_rhs[j]);
            if (!equals_(key_l, key_r)) {
                return false;
            }
            const size_type i_start = i;
            const size_type j_start = j;
            while (i < n && equals_(extracter_(*ptrs_lhs[i]), key_l)) {
                ++i;
            }
            while (j < n && rhs.equals_(rhs.extracter_(*ptrs_rhs[j]), key_l)) {
                ++j;
            }
            const size_type count_l = i - i_start;
            const size_type count_r = j - j_start;
            if (count_l != count_r) {
                return false;
            }
            for (size_type k = i_start; k < i; ++k) {
                const value_type& val = *ptrs_lhs[k];
                bool found = false;
                for (size_type l = j_start; l < j; ++l) {
                    if (ptrs_rhs[l] && *ptrs_rhs[l] == val) {
                        ptrs_rhs[l] = nullptr;
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    return false;
                }
            }
            for (size_type l = j_start; l < j; ++l) {
                if (ptrs_rhs[l] != nullptr) {
                    return false;
                }
            }
        }
        return true;
    }
 
    static iterator to_iterator(const const_iterator& iter) noexcept {
        return iterator(iter.index(), const_cast<flat_hashtable*>(iter.container()));
    }
    static const_iterator to_const_iterator(const iterator& iter) noexcept {
        return const_iterator(iter.index(), iter.container());
    }
 
public:
    explicit flat_hashtable(const size_type n = 0) {
        if (n > 0) {
            const size_t cap = next_power_of_2(static_cast<size_t>(static_cast<double>(n) / max_load_factor()));
            alloc_arrays(cap);
            capacity_ = cap;
            growth_left_ = static_cast<size_t>(static_cast<double>(cap) * max_load_factor());
        }
    }

    flat_hashtable(const size_type n, const HashFcn& hf) :
    hasher_(hf) {
        if (n > 0) {
            const size_t cap = next_power_of_2(static_cast<size_t>(static_cast<double>(n) / max_load_factor()));
            alloc_arrays(cap);
            capacity_ = cap;
            growth_left_ = static_cast<size_t>(static_cast<double>(cap) * max_load_factor());
        }
    }

    flat_hashtable(const size_type n, const HashFcn& hf, const EqualKey& eql) :
    hasher_(hf),
    equals_(eql) {
        if (n > 0) {
            const size_t cap = next_power_of_2(static_cast<size_t>(static_cast<double>(n) / max_load_factor()));
            alloc_arrays(cap);
            capacity_ = cap;
            growth_left_ = static_cast<size_t>(static_cast<double>(cap) * max_load_factor());
        }
    }

    flat_hashtable(const size_type n, const HashFcn& hf, const EqualKey& eql, const ExtractKey& ext) :
    hasher_(hf),
    equals_(eql),
    extracter_(ext) {
        if (n > 0) {
            const size_t cap = next_power_of_2(static_cast<size_t>(static_cast<double>(n) / max_load_factor()));
            alloc_arrays(cap);
            capacity_ = cap;
            growth_left_ = static_cast<size_t>(static_cast<double>(cap) * max_load_factor());
        }
    }

    flat_hashtable(const flat_hashtable& other) :
    hasher_(other.hasher_),
    equals_(other.equals_),
    extracter_(other.extracter_),
    alloc_lf_(other.alloc_lf_) {
        copy_from(other);
    }

    flat_hashtable& operator=(const flat_hashtable& other) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        clear();
        hasher_ = other.hasher_;
        equals_ = other.equals_;
        extracter_ = other.extracter_;
        alloc_lf_ = other.alloc_lf_;
        copy_from(other);
        return *this;
    }

    flat_hashtable(flat_hashtable&& other) noexcept :
    data_(other.data_),
    metadata_(other.metadata_),
    capacity_(other.capacity_),
    size_(other.size_),
    growth_left_(other.growth_left_),
    hasher_(_NEFORCE move(other.hasher_)),
    equals_(_NEFORCE move(other.equals_)),
    extracter_(_NEFORCE move(other.extracter_)),
    alloc_lf_(_NEFORCE move(other.alloc_lf_)) {
        other.data_ = nullptr;
        other.metadata_ = nullptr;
        other.capacity_ = 0;
        other.size_ = 0;
        other.growth_left_ = 0;
    }

    flat_hashtable& operator=(flat_hashtable&& other) noexcept {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        clear();
        swap(other);
        return *this;
    }

    ~flat_hashtable() { free_arrays(); }

    NEFORCE_NODISCARD iterator begin() noexcept {
        for (size_t n = 0; n < capacity_; ++n) {
            const byte_t meta = metadata_[n];
            if (meta != FLAT_HT_EMPTY && meta != FLAT_HT_DELETED) {
                return iterator(n, this);
            }
        }
        return end();
    }

    NEFORCE_NODISCARD iterator end() noexcept { return iterator(capacity_, this); }

    NEFORCE_NODISCARD const_iterator begin() const noexcept { return cbegin(); }

    NEFORCE_NODISCARD const_iterator end() const noexcept { return cend(); }

    NEFORCE_NODISCARD const_iterator cbegin() const noexcept {
        for (size_t n = 0; n < capacity_; ++n) {
            const byte_t meta = metadata_[n];
            if (meta != FLAT_HT_EMPTY && meta != FLAT_HT_DELETED) {
                return const_iterator(n, this);
            }
        }
        return cend();
    }

    NEFORCE_NODISCARD const_iterator cend() const noexcept { return const_iterator(capacity_, this); }

    NEFORCE_NODISCARD size_type size() const noexcept { return size_; }

    NEFORCE_NODISCARD size_type max_size() const noexcept { return static_cast<size_type>(-1); }

    NEFORCE_NODISCARD bool empty() const noexcept { return size_ == 0; }

    NEFORCE_NODISCARD size_type capacity() const noexcept { return capacity_; }

    NEFORCE_NODISCARD hasher hash_function() const noexcept(is_nothrow_copy_constructible_v<hasher>) { return hasher_; }

    NEFORCE_NODISCARD key_equal key_eql() const noexcept(is_nothrow_copy_constructible_v<key_equal>) { return equals_; }

    NEFORCE_NODISCARD float load_factor() const noexcept {
        return capacity_ == 0 ? 0.0F : static_cast<float>(size_) / static_cast<float>(capacity_);
    }

    NEFORCE_NODISCARD float max_load_factor() const noexcept { return alloc_lf_.value; }

    void max_load_factor(const float lf) noexcept {
        NEFORCE_DEBUG_VERIFY(lf > 0, "flat_hashtable load factor invalid.");
        alloc_lf_.value = lf;
        growth_left_ = static_cast<size_t>(static_cast<double>(capacity_) * lf) - size_;
    }

    void rehash(const size_type new_size) { rehash_impl(new_size); }

    void reserve(const size_type n) {
        if (n <= size_) {
            return;
        }
        rehash(static_cast<size_t>(static_cast<double>(n) / max_load_factor()));
    }

    template <typename... Args>
    pair<iterator, bool> emplace_unique(Args&&... args) {
        if (should_rehash()) {
            const size_type new_cap = capacity_ == 0 ? 16 : capacity_ * 2;
            rehash(max(new_cap, static_cast<size_t>(static_cast<double>(size_ + 1) / max_load_factor())));
        }
 
        value_type tmp(_NEFORCE forward<Args>(args)...);
        const key_type& key = extracter_(tmp);
        const size_t hash = hasher_(key);
        const byte_t h2 = hash_to_h2(hash);
 
#ifdef NEFORCE_SIMD_SSE2
        pair<size_t, bool> probe_result = probe_find_or_insert_simd(key, h2);
#else
        pair<size_t, bool> probe_result = probe_find_or_insert(key, h2);
#endif
 
        if (probe_result.second) {
            return {iterator(probe_result.first, this), false};
        }
 
        const size_t insert_idx = probe_result.first;
        _NEFORCE construct(&data_[insert_idx], _NEFORCE move(tmp));
        metadata_[insert_idx] = h2;
        ++size_;
        --growth_left_;
        return {iterator(insert_idx, this), true};
    }

    template <typename... Args>
    iterator emplace_equal(Args&&... args) {
        if (should_rehash()) {
            const size_type new_cap = capacity_ == 0 ? 16 : capacity_ * 2;
            rehash(max(new_cap, static_cast<size_t>(static_cast<double>(size_ + 1) / max_load_factor())));
        }
 
        value_type tmp(_NEFORCE forward<Args>(args)...);
        const key_type& key = extracter_(tmp);
        const size_t hash = hasher_(key);
        const byte_t h2 = hash_to_h2(hash);
        const size_t h1 = hash_to_index(hash);
 
        size_t idx = h1;
        size_t first_deleted = npos;
        for (size_t i = 0; i < capacity_; ++i) {
            const byte_t meta = metadata_[idx];
            if (meta == FLAT_HT_EMPTY) {
                const size_t insert_idx = (first_deleted != npos) ? first_deleted : idx;
                construct_at(insert_idx, h2, _NEFORCE move(tmp));
                return iterator(insert_idx, this);
            }
            if (meta == FLAT_HT_DELETED && first_deleted == npos) {
                first_deleted = idx;
            } else if (meta == h2 && equals_(extracter_(data_[idx]), key)) {
                size_t run_end = idx;
                for (size_t j = i + 1; j < capacity_; ++j) {
                    run_end = (run_end + 1) & (capacity_ - 1);
                    if (run_end == 0) {
                        const size_type new_cap = capacity_ * 2;
                        rehash(max(new_cap, static_cast<size_t>(static_cast<double>(size_ + 1) / max_load_factor())));
                        return emplace_equal(_NEFORCE move(tmp));
                    }
                    const byte_t rm = metadata_[run_end];
                    if (rm == FLAT_HT_EMPTY || rm == FLAT_HT_DELETED) {
                        construct_at(run_end, h2, _NEFORCE move(tmp));
                        return iterator(run_end, this);
                    }
                    if (rm == h2 && equals_(extracter_(data_[run_end]), key)) {
                        continue;
                    }
                    shift_make_room(run_end);
                    construct_at(run_end, h2, _NEFORCE move(tmp));
                    return iterator(run_end, this);
                }
                NEFORCE_THROW_EXCEPTION(value_exception("flat_hashtable: no available slot for insert_equal"));
            }
            idx = (idx + 1) & (capacity_ - 1);
        }
 
        const size_t insert_idx = first_deleted;
        if (insert_idx == npos) {
            NEFORCE_THROW_EXCEPTION(value_exception("flat_hashtable: no available slot for insert_equal"));
        }
        construct_at(insert_idx, h2, _NEFORCE move(tmp));
        return iterator(insert_idx, this);
    }

    pair<iterator, bool> insert_unique(const value_type& value) { return emplace_unique(value); }

    pair<iterator, bool> insert_unique(value_type&& value) { return emplace_unique(_NEFORCE move(value)); }

    iterator insert_equal(const value_type& value) { return emplace_equal(value); }

    iterator insert_equal(value_type&& value) { return emplace_equal(_NEFORCE move(value)); }

    template <typename Iterator>
    enable_if_t<is_ranges_fwd_iter_v<Iterator>> insert_unique(Iterator first, Iterator last) {
        size_type n = _NEFORCE distance(first, last);
        if (n > 0) {
            rehash(static_cast<size_t>(static_cast<double>(size_ + n) / max_load_factor()));
        }
        for (; n > 0; --n, ++first) {
            insert_unique(*first);
        }
    }

    template <typename Iterator>
    enable_if_t<!is_ranges_fwd_iter_v<Iterator>> insert_unique(Iterator first, Iterator last) {
        for (; first != last; ++first) {
            insert_unique(*first);
        }
    }

    void insert_unique(std::initializer_list<value_type> ilist) { insert_unique(ilist.begin(), ilist.end()); }

    template <typename Iterator>
    enable_if_t<is_ranges_fwd_iter_v<Iterator>> insert_equal(Iterator first, Iterator last) {
        size_type n = _NEFORCE distance(first, last);
        if (n > 0) {
            rehash(static_cast<size_t>(static_cast<double>(size_ + n) / max_load_factor()));
        }
        for (; n > 0; --n, ++first) {
            insert_equal(*first);
        }
    }

    template <typename Iterator>
    enable_if_t<!is_ranges_fwd_iter_v<Iterator>> insert_equal(Iterator first, Iterator last) {
        for (; first != last; ++first) {
            insert_equal(*first);
        }
    }

    void insert_equal(std::initializer_list<value_type> ilist) { insert_equal(ilist.begin(), ilist.end()); }

    size_type erase(const key_type& key) noexcept {
        if (capacity_ == 0) {
            return 0;
        }
 
        const size_t hash = hasher_(key);
        const byte_t h2 = hash_to_h2(hash);
        size_t idx = hash_to_index(hash);
        size_type erased = 0;
 
        for (size_t i = 0; i < capacity_; ++i) {
            const byte_t meta = metadata_[idx];
            if (meta == FLAT_HT_EMPTY) {
                break;
            }
            if (meta == h2 && equals_(extracter_(data_[idx]), key)) {
                _NEFORCE destroy(&data_[idx]);
                metadata_[idx] = FLAT_HT_DELETED;
                ++erased;
                --size_;
            }
            idx = (idx + 1) & (capacity_ - 1);
        }
        return erased;
    }

    iterator erase(const iterator& position) noexcept {
        if (position.container() != this || position.index() >= capacity_) {
            return end();
        }
        const byte_t meta = metadata_[position.index()];
        if (meta == FLAT_HT_EMPTY || meta == FLAT_HT_DELETED) {
            return end();
        }
 
        _NEFORCE destroy(&data_[position.index()]);
        metadata_[position.index()] = FLAT_HT_DELETED;
        --size_;
 
        size_t next = position.index() + 1;
        while (next < capacity_) {
            const byte_t next_meta = metadata_[next];
            if (next_meta != FLAT_HT_EMPTY && next_meta != FLAT_HT_DELETED) {
                return iterator(next, this);
            }
            ++next;
        }
        return end();
    }

    iterator erase(iterator first, iterator last) noexcept {
        if (first == last) {
            return last;
        }
        if (first.container() != this || (last.container() != this && last != end())) {
            return end();
        }
 
        for (size_t idx = first.index(); idx < last.index() && idx < capacity_; ++idx) {
            const byte_t meta = metadata_[idx];
            if (meta != FLAT_HT_EMPTY && meta != FLAT_HT_DELETED) {
                _NEFORCE destroy(&data_[idx]);
                metadata_[idx] = FLAT_HT_DELETED;
                --size_;
            }
        }
        return last;
    }

    const_iterator erase(const const_iterator& position) noexcept {
        return to_const_iterator(erase(to_iterator(position)));
    }

    const_iterator erase(const_iterator first, const_iterator last) noexcept {
        return to_const_iterator(erase(to_iterator(first), to_iterator(last)));
    }

    void clear() noexcept {
        for (size_t i = 0; i < capacity_; ++i) {
            if (metadata_[i] != FLAT_HT_EMPTY && metadata_[i] != FLAT_HT_DELETED) {
                _NEFORCE destroy(&data_[i]);
            }
            metadata_[i] = FLAT_HT_EMPTY;
        }
        size_ = 0;
        growth_left_ = static_cast<size_t>(static_cast<double>(capacity_) * max_load_factor());
    }

    NEFORCE_NODISCARD iterator find(const key_type& key) noexcept {
        if (capacity_ == 0) {
            return end();
        }
        const size_t hash = hasher_(key);
        const byte_t h2 = hash_to_h2(hash);
        size_t idx = hash_to_index(hash);
 
        for (size_t i = 0; i < capacity_; ++i) {
            const byte_t meta = metadata_[idx];
            if (meta == FLAT_HT_EMPTY) {
                return end();
            }
            if (meta == h2 && equals_(extracter_(data_[idx]), key)) {
                return iterator(idx, this);
            }
            idx = (idx + 1) & (capacity_ - 1);
        }
        return end();
    }

    NEFORCE_NODISCARD const_iterator find(const key_type& key) const noexcept {
        if (capacity_ == 0) {
            return cend();
        }
        const size_t hash = hasher_(key);
        const byte_t h2 = hash_to_h2(hash);
        size_t idx = hash_to_index(hash);
 
        for (size_t i = 0; i < capacity_; ++i) {
            const byte_t meta = metadata_[idx];
            if (meta == FLAT_HT_EMPTY) {
                return cend();
            }
            if (meta == h2 && equals_(extracter_(data_[idx]), key)) {
                return const_iterator(idx, this);
            }
            idx = (idx + 1) & (capacity_ - 1);
        }
        return cend();
    }

    NEFORCE_NODISCARD size_type count(const key_type& key) const noexcept {
        if (capacity_ == 0) {
            return 0;
        }
        const size_t hash = hasher_(key);
        const byte_t h2 = hash_to_h2(hash);
        size_t idx = hash_to_index(hash);
        size_type result = 0;
 
        for (size_t i = 0; i < capacity_; ++i) {
            const byte_t meta = metadata_[idx];
            if (meta == FLAT_HT_EMPTY) {
                break;
            }
            if (meta == h2 && equals_(extracter_(data_[idx]), key)) {
                ++result;
            }
            idx = (idx + 1) & (capacity_ - 1);
        }
        return result;
    }

    NEFORCE_NODISCARD bool contains(const key_type& key) const noexcept { return find(key) != cend(); }

    NEFORCE_NODISCARD pair<iterator, iterator> equal_range(const key_type& key) {
        if (capacity_ == 0) {
            return {end(), end()};
        }
        const size_t hash = hasher_(key);
        const byte_t h2 = hash_to_h2(hash);
        size_t idx = hash_to_index(hash);
 
        size_t first_idx = npos;
        for (size_t i = 0; i < capacity_; ++i) {
            const byte_t meta = metadata_[idx];
            if (meta == FLAT_HT_EMPTY) {
                return {end(), end()};
            }
            if (meta == h2 && equals_(extracter_(data_[idx]), key)) {
                first_idx = idx;
                break;
            }
            idx = (idx + 1) & (capacity_ - 1);
        }
        if (first_idx == npos) {
            return {end(), end()};
        }
 
        size_t last_idx = first_idx;
        do {
            last_idx = (last_idx + 1) & (capacity_ - 1);
            if (last_idx == first_idx) {
                return {iterator(first_idx, this), end()};
            }
        } while (metadata_[last_idx] != FLAT_HT_EMPTY && equals_(extracter_(data_[last_idx]), key));
 
        while (last_idx != first_idx &&
               (metadata_[last_idx] == FLAT_HT_EMPTY || metadata_[last_idx] == FLAT_HT_DELETED)) {
            last_idx = (last_idx + 1) & (capacity_ - 1);
        }
        if (last_idx == first_idx || last_idx < first_idx) {
            // wraparound: the range extends past the end of the array,
            // second iterator points to end() since forward iteration
            // cannot jump from the end back to the beginning
            return {iterator(first_idx, this), end()};
        }
        return {iterator(first_idx, this), iterator(last_idx, this)};
    }

    NEFORCE_NODISCARD pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        if (capacity_ == 0) {
            return {cend(), cend()};
        }
        const size_t hash = hasher_(key);
        const byte_t h2 = hash_to_h2(hash);
        size_t idx = hash_to_index(hash);
 
        size_t first_idx = npos;
        for (size_t i = 0; i < capacity_; ++i) {
            const byte_t meta = metadata_[idx];
            if (meta == FLAT_HT_EMPTY) {
                return {cend(), cend()};
            }
            if (meta == h2 && equals_(extracter_(data_[idx]), key)) {
                first_idx = idx;
                break;
            }
            idx = (idx + 1) & (capacity_ - 1);
        }
        if (first_idx == npos) {
            return {cend(), cend()};
        }
 
        size_t last_idx = first_idx;
        do {
            last_idx = (last_idx + 1) & (capacity_ - 1);
            if (last_idx == first_idx) {
                return {const_iterator(first_idx, this), cend()};
            }
        } while (metadata_[last_idx] != FLAT_HT_EMPTY && equals_(extracter_(data_[last_idx]), key));
 
        while (last_idx != first_idx &&
               (metadata_[last_idx] == FLAT_HT_EMPTY || metadata_[last_idx] == FLAT_HT_DELETED)) {
            last_idx = (last_idx + 1) & (capacity_ - 1);
        }
        if (last_idx == first_idx || last_idx < first_idx) {
            // wraparound: the range extends past the end of the array
            return {const_iterator(first_idx, this), cend()};
        }
        return {const_iterator(first_idx, this), const_iterator(last_idx, this)};
    }

    void swap(flat_hashtable& other) noexcept {
        if (_NEFORCE addressof(other) == this) {
            return;
        }
        _NEFORCE swap(data_, other.data_);
        _NEFORCE swap(metadata_, other.metadata_);
        _NEFORCE swap(capacity_, other.capacity_);
        _NEFORCE swap(size_, other.size_);
        _NEFORCE swap(growth_left_, other.growth_left_);
        _NEFORCE swap(hasher_, other.hasher_);
        _NEFORCE swap(equals_, other.equals_);
        _NEFORCE swap(extracter_, other.extracter_);
        alloc_lf_.swap(other.alloc_lf_);
    }

    NEFORCE_NODISCARD bool equal_to(const flat_hashtable& rhs) const {
        if (size_ != rhs.size_) {
            return false;
        }
        if (size_ == 0) {
            return true;
        }
        if (this == &rhs) {
            return true;
        }
        if (size_ < 100) {
            return equal_small(rhs);
        }
        return equal_large(rhs);
    }

    NEFORCE_NODISCARD bool less_than(const flat_hashtable& rhs) const
            noexcept(noexcept(_NEFORCE lexicographical_compare(cbegin(), cend(), rhs.cbegin(), rhs.cend()))) {
        return _NEFORCE lexicographical_compare(cbegin(), cend(), rhs.cbegin(), rhs.cend());
    }
};
 // FlatHashTable
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_CONTAINER_FLAT_HASHTABLE_HPP__