ydb/util/generic/hash_table.h

#pragma once

#include "fwd.h"
#include "mapfindptr.h"

#include <util/memory/alloc.h>
#include <util/system/compiler.h>
#include <util/system/type_name.h>
#include <util/system/yassert.h>
#include <util/str_stl.h>
#include "yexception.h"
#include "typetraits.h"
#include "utility.h"

#include <algorithm>
#include <initializer_list>
#include <memory>
#include <tuple>
#include <utility>

#include <cstdlib>

#include "hash_primes.h"

struct TSelect1st {
    template <class TPair>
    inline const typename TPair::first_type& operator()(const TPair& x) const {
        return x.first;
    }
};

template <class Value>
struct __yhashtable_node {
    /** If the first bit is not set, then this is a pointer to the next node in
     * the list of nodes for the current bucket. Otherwise this is a pointer of
     * type __yhashtable_node**, pointing back into the buckets array.
     *
     * This trick makes it possible to use only one node pointer in a hash table
     * iterator. */
    __yhashtable_node* next;

    /** Value stored in a node. */
    Value val;

    __yhashtable_node& operator=(const __yhashtable_node&) = delete;
};

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

template <class Key, class T, class HashFcn,
          class EqualKey, typename size_type_f>
class sthash;

template <class Value>
struct __yhashtable_iterator;

template <class Value>
struct __yhashtable_const_iterator;

template <class Value>
struct __yhashtable_iterator {
    using iterator = __yhashtable_iterator<Value>;
    using const_iterator = __yhashtable_const_iterator<Value>;
    using node = __yhashtable_node<Value>;

    using iterator_category = std::forward_iterator_tag;
    using value_type = Value;
    using difference_type = ptrdiff_t;
    using size_type = size_t;
    using reference = Value&;
    using pointer = Value*;

    node* cur;

    explicit __yhashtable_iterator(node* n)
        : cur(n)
    {
    } /*y*/
    __yhashtable_iterator() = default;

    reference operator*() const {
        return cur->val;
    }
    pointer operator->() const {
        return &(operator*());
    }
    iterator& operator++();
    iterator operator++(int);
    friend bool operator==(const iterator& l, const iterator& r) {
        return l.cur == r.cur;
    }
    friend bool operator!=(const iterator& l, const iterator& r) {
        return l.cur != r.cur;
    }
    bool IsEnd() const {
        return !cur;
    }
    Y_FORCE_INLINE explicit operator bool() const noexcept {
        return cur != nullptr;
    }
};

template <class Value>
struct __yhashtable_const_iterator {
    using iterator = __yhashtable_iterator<Value>;
    using const_iterator = __yhashtable_const_iterator<Value>;
    using node = __yhashtable_node<Value>;

    using iterator_category = std::forward_iterator_tag;
    using value_type = Value;
    using difference_type = ptrdiff_t;
    using size_type = size_t;
    using reference = const Value&;
    using pointer = const Value*;

    const node* cur;

    explicit __yhashtable_const_iterator(const node* n)
        : cur(n)
    {
    }
    __yhashtable_const_iterator() {
    }
    __yhashtable_const_iterator(const iterator& it)
        : cur(it.cur)
    {
    }
    reference operator*() const {
        return cur->val;
    }
    pointer operator->() const {
        return &(operator*());
    }
    const_iterator& operator++();
    const_iterator operator++(int);
    friend bool operator==(const const_iterator& l, const const_iterator& r) {
        return l.cur == r.cur;
    }
    friend bool operator!=(const const_iterator& l, const const_iterator& r) {
        return l.cur != r.cur;
    }
    bool IsEnd() const {
        return !cur;
    }
    Y_FORCE_INLINE explicit operator bool() const noexcept {
        return cur != nullptr;
    }
};

/**
 * This class saves some space in allocator-based containers for the most common
 * use case of empty allocators. This is achieved thanks to the application of
 * empty base class optimization (aka EBCO).
 */
template <class Alloc>
class _allocator_base: private Alloc {
public:
    _allocator_base(const Alloc& other)
        : Alloc(other)
    {
    }

    Alloc& _get_alloc() {
        return static_cast<Alloc&>(*this);
    }
    const Alloc& _get_alloc() const {
        return static_cast<const Alloc&>(*this);
    }
    void _set_alloc(const Alloc& allocator) {
        _get_alloc() = allocator;
    }

    void swap(_allocator_base& other) {
        DoSwap(_get_alloc(), other._get_alloc());
    }
};

/**
 * Wrapper for an array of THashTable buckets.
 *
 * Is better than vector for this particular use case. Main differences:
 *   - Occupies one less word on stack.
 *   - Doesn't even try to initialize its elements. It is THashTable's responsibility.
 *   - Presents a better interface in relation to THashTable's marker element trick.
 *
 * Internally this class is just a pointer-size pair, and the data on the heap
 * has the following structure:
 *
 *     +----------+----------------------+----------+-------------------------+
 *     | raw_size | elements ...         | marker   | unused space [optional] |
 *     +----------+----------------------+----------+-------------------------+
 *                 ^                      ^
 *                 |                      |
 *                Data points here       end() points here
 *
 * `raw_size` stores the size of the allocated memory block. It is used to
 * support resizing without reallocation.
 *
 * `marker` is a special marker element that is set by the THashTable that is
 * then used in iterator implementation to know when the end is reached.
 *
 * Unused space at the end of the memory block may not be present.
 */
template <class T, class Alloc>
class _yhashtable_buckets: private _allocator_base<Alloc> {
    using base_type = _allocator_base<Alloc>;

    static_assert(sizeof(T) == sizeof(size_t), "T is expected to be the same size as size_t.");

public:
    using allocator_type = Alloc;
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using iterator = pointer;
    using const_iterator = const_pointer;
    using size_type = size_t;
    using difference_type = ptrdiff_t;
    using TBucketDivisor = ::NPrivate::THashDivisor;

    _yhashtable_buckets(const Alloc& other)
        : base_type(other)
        , Data(nullptr)
        , Size()
    {
    }

    ~_yhashtable_buckets() {
        Y_ASSERT(!Data);
    }

    void initialize_dynamic(TBucketDivisor size) {
        Y_ASSERT(!Data);

        Data = this->_get_alloc().allocate(size() + 2) + 1;
        Size = size;

        *reinterpret_cast<size_type*>(Data - 1) = size() + 2;
    }

    void deinitialize_dynamic() {
        Y_ASSERT(Data);

        this->_get_alloc().deallocate(Data - 1, *reinterpret_cast<size_type*>(Data - 1));
        Data = pointer();
        Size = TBucketDivisor();
    }

    void initialize_static(pointer data, TBucketDivisor size) {
        Y_ASSERT(!Data && data && size() >= 1);

        Data = data;
        Size = size;
    }

    void deinitialize_static() {
        Y_ASSERT(Data);

        Data = pointer();
        Size = TBucketDivisor();
    }

    void resize_noallocate(TBucketDivisor size) {
        Y_ASSERT(size() <= capacity());

        Size = size;
    }

    iterator begin() {
        return Data;
    }
    const_iterator begin() const {
        return Data;
    }
    iterator end() {
        return Data + Size();
    }
    const_iterator end() const {
        return Data + Size();
    }

    pointer data() {
        return Data;
    }
    const_pointer data() const {
        return Data;
    }

    size_type size() const {
        return Size();
    }
    size_type capacity() const {
        return *reinterpret_cast<size_type*>(Data - 1);
    }
    TBucketDivisor ExtSize() const {
        return Size;
    }
    int BucketDivisorHint() const {
        return +Size.Hint;
    }

    allocator_type get_allocator() const {
        return this->_get_alloc();
    }

    const_reference operator[](size_type index) const {
        Y_ASSERT(index <= Size());

        return *(Data + index);
    }

    reference operator[](size_type index) {
        Y_ASSERT(index <= Size());

        return *(Data + index);
    }

    void swap(_yhashtable_buckets& other) {
        base_type::swap(other);
        DoSwap(Data, other.Data);
        DoSwap(Size, other.Size);
    }

private:
    /** Pointer to the first element of the buckets array. */
    pointer Data;

    /** Size of the buckets array. Doesn't take the marker element at the end into account. */
    TBucketDivisor Size;
};

/**
 * This class saves one word in THashTable for the most common use case of empty
 * functors. The exact implementation picks a specialization with storage allocated
 * for the functors if those are non-empty, and another specialization that creates
 * functors on the fly if they are empty. It is expected that empty functors have
 * trivial constructors.
 *
 * Note that this is basically the only way to do it portably. Another option is
 * multiple inheritance from empty functors, but MSVC's empty base class
 * optimization chokes up on multiple empty bases, and we're already using
 * EBCO in _allocator_base.
 *
 * Note that there are no specializations for the case when only one or two
 * of the functors are empty as this is a case that's just way too rare.
 */
template <class HashFcn, class ExtractKey, class EqualKey, class Alloc, bool IsEmpty = std::is_empty<HashFcn>::value && std::is_empty<ExtractKey>::value && std::is_empty<EqualKey>::value>
class _yhashtable_base: public _allocator_base<Alloc> {
    using base_type = _allocator_base<Alloc>;

public:
    _yhashtable_base(const HashFcn& hash, const ExtractKey& extract, const EqualKey& equals, const Alloc& alloc)
        : base_type(alloc)
        , hash_(hash)
        , extract_(extract)
        , equals_(equals)
    {
    }

    const EqualKey& _get_key_eq() const {
        return equals_;
    }
    EqualKey& _get_key_eq() {
        return equals_;
    }
    void _set_key_eq(const EqualKey& equals) {
        this->equals_ = equals;
    }

    const ExtractKey& _get_key_extract() const {
        return extract_;
    }
    ExtractKey& _get_key_extract() {
        return extract_;
    }
    void _set_key_extract(const ExtractKey& extract) {
        this->extract_ = extract;
    }

    const HashFcn& _get_hash_fun() const {
        return hash_;
    }
    HashFcn& _get_hash_fun() {
        return hash_;
    }
    void _set_hash_fun(const HashFcn& hash) {
        this->hash_ = hash;
    }

    void swap(_yhashtable_base& other) {
        base_type::swap(other);
        DoSwap(equals_, other.equals_);
        DoSwap(extract_, other.extract_);
        DoSwap(hash_, other.hash_);
    }

private:
    HashFcn hash_;
    ExtractKey extract_;
    EqualKey equals_;
};

template <class HashFcn, class ExtractKey, class EqualKey, class Alloc>
class _yhashtable_base<HashFcn, ExtractKey, EqualKey, Alloc, true>: public _allocator_base<Alloc> {
    using base_type = _allocator_base<Alloc>;

public:
    _yhashtable_base(const HashFcn&, const ExtractKey&, const EqualKey&, const Alloc& alloc)
        : base_type(alloc)
    {
    }

    EqualKey _get_key_eq() const {
        return EqualKey();
    }
    void _set_key_eq(const EqualKey&) {
    }

    ExtractKey _get_key_extract() const {
        return ExtractKey();
    }
    void _set_key_extract(const ExtractKey&) {
    }

    HashFcn _get_hash_fun() const {
        return HashFcn();
    }
    void _set_hash_fun(const HashFcn&) {
    }

    void swap(_yhashtable_base& other) {
        base_type::swap(other);
    }
};

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct _yhashtable_traits {
    using node = __yhashtable_node<Value>;

    using node_allocator_type = TReboundAllocator<Alloc, node>;
    using nodep_allocator_type = TReboundAllocator<Alloc, node*>;

    using base_type = _yhashtable_base<HashFcn, ExtractKey, EqualKey, node_allocator_type>;
};

extern const void* const _yhashtable_empty_data[];

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
class THashTable: private _yhashtable_traits<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::base_type {
    using traits_type = _yhashtable_traits<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
    using base_type = typename traits_type::base_type;
    using node = typename traits_type::node;
    using nodep_allocator_type = typename traits_type::nodep_allocator_type;
    using buckets_type = _yhashtable_buckets<node*, nodep_allocator_type>;
    using TBucketDivisor = ::NPrivate::THashDivisor;

public:
    using key_type = Key;
    using value_type = Value;
    using hasher = HashFcn;
    using key_equal = EqualKey;
    using key_extract = ExtractKey;
    using allocator_type = Alloc;
    using node_allocator_type = typename traits_type::node_allocator_type;

    using size_type = size_t;
    using difference_type = ptrdiff_t;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using reference = value_type&;
    using const_reference = const value_type&;

    node_allocator_type& GetNodeAllocator() {
        return this->_get_alloc();
    }
    const node_allocator_type& GetNodeAllocator() const {
        return this->_get_alloc();
    }
    key_equal key_eq() const {
        return this->_get_key_eq();
    }
    hasher hash_function() const {
        return this->_get_hash_fun();
    }

private:
    template <class KeyL, class KeyR>
    bool equals(const KeyL& l, const KeyR& r) const {
        return this->_get_key_eq()(l, r);
    }

    /* This method is templated to postpone instantiation of key extraction functor. */
    template <class ValueL>
    auto get_key(const ValueL& value) const -> decltype(ExtractKey()(value)) {
        return this->_get_key_extract()(value);
    }

    node* get_node() {
        node* result = this->_get_alloc().allocate(1);
        Y_ASSERT((reinterpret_cast<uintptr_t>(result) & 1) == 0); /* We're using the last bit of the node pointer. */
        return result;
    }
    void put_node(node* p) {
        this->_get_alloc().deallocate(p, 1);
    }

    buckets_type buckets;
    size_type num_elements;

public:
    using iterator = __yhashtable_iterator<Value>;
    using const_iterator = __yhashtable_const_iterator<Value>;
    using insert_ctx = node**;

    friend struct __yhashtable_iterator<Value>;
    friend struct __yhashtable_const_iterator<Value>;

public:
    THashTable()
        : base_type(HashFcn(), ExtractKey(), EqualKey(), node_allocator_type())
        , buckets(nodep_allocator_type())
        , num_elements(0)
    {
        initialize_buckets(buckets, 0);
    }

    THashTable(size_type n, const HashFcn& hf, const EqualKey& eql, const ExtractKey& ext)
        : base_type(hf, ext, eql, node_allocator_type())
        , buckets(nodep_allocator_type())
        , num_elements(0)
    {
        initialize_buckets(buckets, n);
    }

    THashTable(size_type n, const HashFcn& hf, const EqualKey& eql)
        : base_type(hf, ExtractKey(), eql, node_allocator_type())
        , buckets(nodep_allocator_type())
        , num_elements(0)
    {
        initialize_buckets(buckets, n);
    }

    template <class TAllocParam>
    THashTable(size_type n, const HashFcn& hf, const EqualKey& eql, TAllocParam* allocParam)
        : base_type(hf, ExtractKey(), eql, allocParam)
        , buckets(allocParam)
        , num_elements(0)
    {
        initialize_buckets(buckets, n);
    }

    THashTable(const THashTable& ht)
        : base_type(ht._get_hash_fun(), ht._get_key_extract(), ht._get_key_eq(), ht._get_alloc())
        , buckets(ht.buckets.get_allocator())
        , num_elements(0)
    {
        if (ht.empty()) {
            initialize_buckets(buckets, 0);
        } else {
            initialize_buckets_dynamic(buckets, ht.buckets.ExtSize());
            copy_from_dynamic(ht);
        }
    }

    THashTable(THashTable&& ht) noexcept
        : base_type(ht._get_hash_fun(), ht._get_key_extract(), ht._get_key_eq(), ht._get_alloc())
        , buckets(ht.buckets.get_allocator())
        , num_elements(0)
    {
        initialize_buckets(buckets, 0);
        this->swap(ht);
    }

    THashTable& operator=(const THashTable& ht) {
        if (&ht != this) {
            basic_clear();
            this->_set_hash_fun(ht._get_hash_fun());
            this->_set_key_eq(ht._get_key_eq());
            this->_set_key_extract(ht._get_key_extract());
            /* We don't copy allocator for a reason. */

            if (ht.empty()) {
                /* Some of the old code in Arcadia works around the behavior in
                 * clear() by invoking operator= with empty hash as an argument.
                 * It's expected that this will deallocate the buckets array, so
                 * this is what we have to do here. */
                deinitialize_buckets(buckets);
                initialize_buckets(buckets, 0);
            } else {
                if (buckets.capacity() > ht.buckets.size()) {
                    buckets.resize_noallocate(ht.buckets.ExtSize());
                } else {
                    deinitialize_buckets(buckets);
                    initialize_buckets_dynamic(buckets, ht.buckets.ExtSize());
                }

                copy_from_dynamic(ht);
            }
        }
        return *this;
    }

    THashTable& operator=(THashTable&& ht) noexcept {
        basic_clear();
        swap(ht);

        return *this;
    }

    ~THashTable() {
        basic_clear();
        deinitialize_buckets(buckets);
    }

    size_type size() const noexcept {
        return num_elements;
    }
    size_type max_size() const noexcept {
        return size_type(-1);
    }

    Y_PURE_FUNCTION bool empty() const noexcept {
        return size() == 0;
    }

    void swap(THashTable& ht) {
        base_type::swap(ht);
        buckets.swap(ht.buckets);
        DoSwap(num_elements, ht.num_elements);
    }

    iterator begin() {
        for (size_type n = 0; n < buckets.size(); ++n) { /*y*/
            if (buckets[n]) {
                return iterator(buckets[n]); /*y*/
            }
        }
        return end();
    }

    iterator end() {
        return iterator(nullptr);
    } /*y*/

    const_iterator begin() const {
        for (size_type n = 0; n < buckets.size(); ++n) { /*y*/
            if (buckets[n]) {
                return const_iterator(buckets[n]); /*y*/
            }
        }
        return end();
    }

    const_iterator end() const {
        return const_iterator(nullptr);
    } /*y*/

public:
    size_type bucket_count() const {
        return buckets.size();
    } /*y*/

    size_type bucket_size(size_type bucket) const {
        size_type result = 0;
        if (const node* cur = buckets[bucket]) {
            for (; !((uintptr_t)cur & 1); cur = cur->next) {
                result += 1;
            }
        }
        return result;
    }

    template <class OtherValue>
    std::pair<iterator, bool> insert_unique(const OtherValue& obj) {
        reserve(num_elements + 1);
        return insert_unique_noresize(obj);
    }

    template <class OtherValue>
    iterator insert_equal(const OtherValue& obj) {
        reserve(num_elements + 1);
        return emplace_equal_noresize(obj);
    }

    template <typename... Args>
    iterator emplace_equal(Args&&... args) {
        reserve(num_elements + 1);
        return emplace_equal_noresize(std::forward<Args>(args)...);
    }

    template <class OtherValue>
    iterator insert_direct(const OtherValue& obj, insert_ctx ins) {
        return emplace_direct(ins, obj);
    }

    template <typename... Args>
    iterator emplace_direct(insert_ctx ins, Args&&... args) {
        bool resized = reserve(num_elements + 1);
        node* tmp = new_node(std::forward<Args>(args)...);
        if (resized) {
            find_i(get_key(tmp->val), ins);
        }
        tmp->next = *ins ? *ins : (node*)((uintptr_t)(ins + 1) | 1);
        *ins = tmp;
        ++num_elements;
        return iterator(tmp);
    }

    template <typename... Args>
    std::pair<iterator, bool> emplace_unique(Args&&... args) {
        reserve(num_elements + 1);
        return emplace_unique_noresize(std::forward<Args>(args)...);
    }

    template <typename... Args>
    std::pair<iterator, bool> emplace_unique_noresize(Args&&... args);

    template <class OtherValue>
    std::pair<iterator, bool> insert_unique_noresize(const OtherValue& obj);

    template <typename... Args>
    iterator emplace_equal_noresize(Args&&... args);

    template <class InputIterator>
    void insert_unique(InputIterator f, InputIterator l) {
        insert_unique(f, l, typename std::iterator_traits<InputIterator>::iterator_category());
    }

    template <class InputIterator>
    void insert_equal(InputIterator f, InputIterator l) {
        insert_equal(f, l, typename std::iterator_traits<InputIterator>::iterator_category());
    }

    template <class InputIterator>
    void insert_unique(InputIterator f, InputIterator l, std::input_iterator_tag) {
        for (; f != l; ++f) {
            insert_unique(*f);
        }
    }

    template <class InputIterator>
    void insert_equal(InputIterator f, InputIterator l, std::input_iterator_tag) {
        for (; f != l; ++f) {
            insert_equal(*f);
        }
    }

    template <class ForwardIterator>
    void insert_unique(ForwardIterator f, ForwardIterator l, std::forward_iterator_tag) {
        difference_type n = std::distance(f, l);

        reserve(num_elements + n);
        for (; n > 0; --n, ++f) {
            insert_unique_noresize(*f);
        }
    }

    template <class ForwardIterator>
    void insert_equal(ForwardIterator f, ForwardIterator l, std::forward_iterator_tag) {
        difference_type n = std::distance(f, l);

        reserve(num_elements + n);
        for (; n > 0; --n, ++f) {
            emplace_equal_noresize(*f);
        }
    }

    template <class OtherValue>
    reference find_or_insert(const OtherValue& v);

    template <class OtherKey>
    iterator find(const OtherKey& key) {
        size_type n = bkt_num_key(key);
        node* first;
        for (first = buckets[n];
             first && !equals(get_key(first->val), key);
             first = ((uintptr_t)first->next & 1) ? nullptr : first->next) /*y*/
        {
        }
        return iterator(first); /*y*/
    }

    template <class OtherKey>
    const_iterator find(const OtherKey& key) const {
        size_type n = bkt_num_key(key);
        const node* first;
        for (first = buckets[n];
             first && !equals(get_key(first->val), key);
             first = ((uintptr_t)first->next & 1) ? nullptr : first->next) /*y*/
        {
        }
        return const_iterator(first); /*y*/
    }

    template <class OtherKey>
    iterator find_i(const OtherKey& key, insert_ctx& ins);

    template <class OtherKey>
    size_type count(const OtherKey& key) const {
        const size_type n = bkt_num_key(key);
        size_type result = 0;

        if (const node* cur = buckets[n]) {
            for (; !((uintptr_t)cur & 1); cur = cur->next) {
                if (equals(get_key(cur->val), key)) {
                    ++result;
                }
            }
        }
        return result;
    }

    template <class OtherKey>
    std::pair<iterator, iterator> equal_range(const OtherKey& key);

    template <class OtherKey>
    std::pair<const_iterator, const_iterator> equal_range(const OtherKey& key) const;

    template <class OtherKey>
    std::pair<iterator, iterator> equal_range_i(const OtherKey& key, insert_ctx& ins);

    template <class OtherKey>
    size_type erase(const OtherKey& key);

    template <class OtherKey>
    size_type erase_one(const OtherKey& key);

    // void (instead of iterator) is intended, see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf
    void erase(const iterator& it);
    void erase(iterator first, iterator last);

    void erase(const const_iterator& it);
    void erase(const_iterator first, const_iterator last);

    bool reserve(size_type num_elements_hint);
    Y_REINITIALIZES_OBJECT void basic_clear();

    /**
     * Clears the hashtable without deallocating the nodes.
     *
     * This might come in handy with non-standard allocators, e.g. a pool
     * allocator with a pool that is then cleared manually, thus releasing all
     * the nodes at once.
     */
    void release_nodes() {
        if (empty()) {
            return; /* Need this check because empty buckets may reside in read-only memory. */
        }

        clear_buckets(buckets);
        num_elements = 0;
    }

    // implemented in save_stl.h
    template <class KeySaver>
    int save_for_st(IOutputStream* stream, KeySaver& ks, sthash<int, int, THash<int>, TEqualTo<int>, typename KeySaver::TSizeType>* stHash = nullptr) const;

    Y_REINITIALIZES_OBJECT void clear(size_type downsize) {
        basic_clear();

        if (downsize < buckets.size()) {
            const TBucketDivisor newSize = HashBucketCountExt(downsize);
            if (newSize() < buckets.size()) {
                Y_ASSERT(newSize() >= 7); /* We cannot downsize static buckets. */
                buckets.resize_noallocate(newSize);
            }
        }
    }

    /**
     * Clears the hashtable and tries to reasonably downsize it. Note that
     * downsizing is mainly for the following use case:
     *
     *     THashTable hash;
     *     for(...) {
     *         if (someCond())
     *             hash.clear();
     *         hash.insert(...);
     *     }
     *
     * Here if at some point `hash` gets really big, then all the following calls
     * to `clear` become really slow as they have to iterate through all the the
     * empty buckets. This is worked around by squeezing the buckets array a little
     * bit with every `clear` call.
     *
     * Alternatively, the user can call `basic_clear`, which doesn't do the
     * downsizing.
     */
    Y_REINITIALIZES_OBJECT void clear() {
        if (num_elements) {
            clear((num_elements * 2 + buckets.size()) / 3);
        }
    }

private:
    static void initialize_buckets(buckets_type& buckets, size_type sizeHint) {
        if (sizeHint == 0) {
            buckets.initialize_static(reinterpret_cast<node**>(const_cast<void**>(_yhashtable_empty_data)) + 1, TBucketDivisor::One());
        } else {
            TBucketDivisor size = HashBucketCountExt(sizeHint);
            Y_ASSERT(size() >= 7);

            initialize_buckets_dynamic(buckets, size);
        }
    }

    static void initialize_buckets_dynamic(buckets_type& buckets, TBucketDivisor size) {
        buckets.initialize_dynamic(size);
        memset(buckets.data(), 0, size() * sizeof(*buckets.data()));
        buckets[size()] = (node*)1;
    }

    static void deinitialize_buckets(buckets_type& buckets) {
        if (buckets.size() == 1) {
            buckets.deinitialize_static();
        } else {
            buckets.deinitialize_dynamic();
        }
    }

    static void clear_buckets(buckets_type& buckets) {
        memset(buckets.data(), 0, buckets.size() * sizeof(*buckets.data()));
    }

    template <class OtherKey>
    size_type bkt_num_key(const OtherKey& key) const {
        return bkt_num_key(key, buckets.ExtSize());
    }

    template <class OtherValue>
    size_type bkt_num(const OtherValue& obj) const {
        return bkt_num_key(get_key(obj));
    }

    template <class OtherKey>
    size_type bkt_num_key(const OtherKey& key, TBucketDivisor n) const {
        const size_type bucket = n.Remainder(this->_get_hash_fun()(key));
        Y_ASSERT((0 <= bucket) && (bucket < n()));
        return bucket;
    }

    template <class OtherValue>
    size_type bkt_num(const OtherValue& obj, TBucketDivisor n) const {
        return bkt_num_key(get_key(obj), n);
    }

    template <typename... Args>
    node* new_node(Args&&... val) {
        node* n = get_node();
        n->next = (node*)1; /*y*/ // just for a case
        try {
            new (static_cast<void*>(&n->val)) Value(std::forward<Args>(val)...);
        } catch (...) {
            put_node(n);
            throw;
        }
        return n;
    }

    void delete_node(node* n) {
        n->val.~Value();
        // n->next = (node*) 0xDeadBeeful;
        put_node(n);
    }

    void erase_bucket(const size_type n, node* first, node* last);
    void erase_bucket(const size_type n, node* last);

    void copy_from_dynamic(const THashTable& ht);
};

template <class V>
__yhashtable_iterator<V>& __yhashtable_iterator<V>::operator++() {
    Y_ASSERT(cur);
    cur = cur->next;
    if ((uintptr_t)cur & 1) {
        node** bucket = (node**)((uintptr_t)cur & ~1);
        while (*bucket == nullptr) {
            ++bucket;
        }
        Y_ASSERT(*bucket != nullptr);
        cur = (node*)((uintptr_t)*bucket & ~1);
    }
    return *this;
}

template <class V>
inline __yhashtable_iterator<V> __yhashtable_iterator<V>::operator++(int) {
    iterator tmp = *this;
    ++*this;
    return tmp;
}

template <class V>
__yhashtable_const_iterator<V>& __yhashtable_const_iterator<V>::operator++() {
    Y_ASSERT(cur);
    cur = cur->next;
    if ((uintptr_t)cur & 1) {
        node** bucket = (node**)((uintptr_t)cur & ~1);
        while (*bucket == nullptr) {
            ++bucket;
        }
        Y_ASSERT(*bucket != nullptr);
        cur = (node*)((uintptr_t)*bucket & ~1);
    }
    return *this;
}

template <class V>
inline __yhashtable_const_iterator<V> __yhashtable_const_iterator<V>::operator++(int) {
    const_iterator tmp = *this;
    ++*this;
    return tmp;
}

template <class V, class K, class HF, class Ex, class Eq, class A>
template <typename... Args>
std::pair<typename THashTable<V, K, HF, Ex, Eq, A>::iterator, bool> THashTable<V, K, HF, Ex, Eq, A>::emplace_unique_noresize(Args&&... args) {
    auto deleter = [&](node* tmp) { delete_node(tmp); };
    node* tmp = new_node(std::forward<Args>(args)...);
    std::unique_ptr<node, decltype(deleter)> guard(tmp, deleter);

    const size_type n = bkt_num(tmp->val);
    node* first = buckets[n];

    if (first) {                                                          /*y*/
        for (node* cur = first; !((uintptr_t)cur & 1); cur = cur->next) { /*y*/
            if (equals(get_key(cur->val), get_key(tmp->val))) {
                return std::pair<iterator, bool>(iterator(cur), false); /*y*/
            }
        }
    }

    guard.release();
    tmp->next = first ? first : (node*)((uintptr_t)&buckets[n + 1] | 1); /*y*/
    buckets[n] = tmp;
    ++num_elements;
    return std::pair<iterator, bool>(iterator(tmp), true); /*y*/
}

template <class V, class K, class HF, class Ex, class Eq, class A>
template <class OtherValue>
std::pair<typename THashTable<V, K, HF, Ex, Eq, A>::iterator, bool> THashTable<V, K, HF, Ex, Eq, A>::insert_unique_noresize(const OtherValue& obj) {
    const size_type n = bkt_num(obj);
    node* first = buckets[n];

    if (first) {                                                          /*y*/
        for (node* cur = first; !((uintptr_t)cur & 1); cur = cur->next) { /*y*/
            if (equals(get_key(cur->val), get_key(obj))) {
                return std::pair<iterator, bool>(iterator(cur), false); /*y*/
            }
        }
    }

    node* tmp = new_node(obj);
    tmp->next = first ? first : (node*)((uintptr_t)&buckets[n + 1] | 1); /*y*/
    buckets[n] = tmp;
    ++num_elements;
    return std::pair<iterator, bool>(iterator(tmp), true); /*y*/
}

template <class V, class K, class HF, class Ex, class Eq, class A>
template <typename... Args>
__yhashtable_iterator<V> THashTable<V, K, HF, Ex, Eq, A>::emplace_equal_noresize(Args&&... args) {
    auto deleter = [&](node* tmp) { delete_node(tmp); };
    node* tmp = new_node(std::forward<Args>(args)...);
    std::unique_ptr<node, decltype(deleter)> guard(tmp, deleter);
    const size_type n = bkt_num(tmp->val);
    node* first = buckets[n];

    if (first) {                                                          /*y*/
        for (node* cur = first; !((uintptr_t)cur & 1); cur = cur->next) { /*y*/
            if (equals(get_key(cur->val), get_key(tmp->val))) {
                guard.release();
                tmp->next = cur->next;
                cur->next = tmp;
                ++num_elements;
                return iterator(tmp); /*y*/
            }
        }
    }

    guard.release();
    tmp->next = first ? first : (node*)((uintptr_t)&buckets[n + 1] | 1); /*y*/
    buckets[n] = tmp;
    ++num_elements;
    return iterator(tmp); /*y*/
}

template <class V, class K, class HF, class Ex, class Eq, class A>
template <class OtherValue>
typename THashTable<V, K, HF, Ex, Eq, A>::reference THashTable<V, K, HF, Ex, Eq, A>::find_or_insert(const OtherValue& v) {
    reserve(num_elements + 1);

    size_type n = bkt_num_key(get_key(v));
    node* first = buckets[n];

    if (first) {                                                          /*y*/
        for (node* cur = first; !((uintptr_t)cur & 1); cur = cur->next) { /*y*/
            if (equals(get_key(cur->val), get_key(v))) {
                return cur->val;
            }
        }
    }

    node* tmp = new_node(v);
    tmp->next = first ? first : (node*)((uintptr_t)&buckets[n + 1] | 1); /*y*/
    buckets[n] = tmp;
    ++num_elements;
    return tmp->val;
}

template <class V, class K, class HF, class Ex, class Eq, class A>
template <class OtherKey>
__yhashtable_iterator<V> THashTable<V, K, HF, Ex, Eq, A>::find_i(const OtherKey& key, insert_ctx& ins) {
    size_type n = bkt_num_key(key);
    ins = &buckets[n];
    node* first = buckets[n];

    if (first) {                                                          /*y*/
        for (node* cur = first; !((uintptr_t)cur & 1); cur = cur->next) { /*y*/
            if (equals(get_key(cur->val), key)) {
                return iterator(cur); /*y*/
            }
        }
    }
    return end();
}

template <class V, class K, class HF, class Ex, class Eq, class A>
template <class OtherKey>
std::pair<__yhashtable_iterator<V>, __yhashtable_iterator<V>> THashTable<V, K, HF, Ex, Eq, A>::equal_range(const OtherKey& key) {
    insert_ctx ctx;
    return equal_range_i(key, ctx);
}

template <class V, class K, class HF, class Ex, class Eq, class A>
template <class OtherKey>
std::pair<__yhashtable_iterator<V>, __yhashtable_iterator<V>> THashTable<V, K, HF, Ex, Eq, A>::equal_range_i(const OtherKey& key, insert_ctx& ins) {
    using pii = std::pair<iterator, iterator>;
    const size_type n = bkt_num_key(key);
    ins = &buckets[n];
    node* first = buckets[n];

    if (first) {                                               /*y*/
        for (; !((uintptr_t)first & 1); first = first->next) { /*y*/
            if (equals(get_key(first->val), key)) {
                for (node* cur = first->next; !((uintptr_t)cur & 1); cur = cur->next) {
                    if (!equals(get_key(cur->val), key)) {
                        return pii(iterator(first), iterator(cur)); /*y*/
                    }
                }
                for (size_type m = n + 1; m < buckets.size(); ++m) { /*y*/
                    if (buckets[m]) {
                        return pii(iterator(first),       /*y*/
                                   iterator(buckets[m])); /*y*/
                    }
                }
                return pii(iterator(first), end()); /*y*/
            }
        }
    }
    return pii(end(), end());
}

template <class V, class K, class HF, class Ex, class Eq, class A>
template <class OtherKey>
std::pair<__yhashtable_const_iterator<V>, __yhashtable_const_iterator<V>> THashTable<V, K, HF, Ex, Eq, A>::equal_range(const OtherKey& key) const {
    using pii = std::pair<const_iterator, const_iterator>;
    const size_type n = bkt_num_key(key);
    const node* first = buckets[n];

    if (first) {                                               /*y*/
        for (; !((uintptr_t)first & 1); first = first->next) { /*y*/
            if (equals(get_key(first->val), key)) {
                for (const node* cur = first->next; !((uintptr_t)cur & 1); cur = cur->next) {
                    if (!equals(get_key(cur->val), key)) {
                        return pii(const_iterator(first), /*y*/
                                   const_iterator(cur));  /*y*/
                    }
                }
                for (size_type m = n + 1; m < buckets.size(); ++m) { /*y*/
                    if (buckets[m]) {
                        return pii(const_iterator(first /*y*/),
                                   const_iterator(buckets[m] /*y*/));
                    }
                }
                return pii(const_iterator(first /*y*/), end());
            }
        }
    }
    return pii(end(), end());
}

template <class V, class K, class HF, class Ex, class Eq, class A>
template <class OtherKey>
typename THashTable<V, K, HF, Ex, Eq, A>::size_type THashTable<V, K, HF, Ex, Eq, A>::erase(const OtherKey& key) {
    const size_type n = bkt_num_key(key);
    node* first = buckets[n];
    size_type erased = 0;

    if (first) {
        node* cur = first;
        node* next = cur->next;
        while (!((uintptr_t)next & 1)) { /*y*/
            if (equals(get_key(next->val), key)) {
                cur->next = next->next;
                ++erased;
                --num_elements;
                delete_node(next);
                next = cur->next;
            } else {
                cur = next;
                next = cur->next;
            }
        }
        if (equals(get_key(first->val), key)) {
            buckets[n] = ((uintptr_t)first->next & 1) ? nullptr : first->next; /*y*/
            ++erased;
            --num_elements;
            delete_node(first);
        }
    }
    return erased;
}

template <class V, class K, class HF, class Ex, class Eq, class A>
template <class OtherKey>
typename THashTable<V, K, HF, Ex, Eq, A>::size_type THashTable<V, K, HF, Ex, Eq, A>::erase_one(const OtherKey& key) {
    const size_type n = bkt_num_key(key);
    node* first = buckets[n];

    if (first) {
        node* cur = first;
        node* next = cur->next;
        while (!((uintptr_t)next & 1)) { /*y*/
            if (equals(get_key(next->val), key)) {
                cur->next = next->next;
                --num_elements;
                delete_node(next);
                return 1;
            } else {
                cur = next;
                next = cur->next;
            }
        }
        if (equals(get_key(first->val), key)) {
            buckets[n] = ((uintptr_t)first->next & 1) ? nullptr : first->next; /*y*/
            --num_elements;
            delete_node(first);
            return 1;
        }
    }
    return 0;
}

template <class V, class K, class HF, class Ex, class Eq, class A>
void THashTable<V, K, HF, Ex, Eq, A>::erase(const iterator& it) {
    if (node* const p = it.cur) {
        const size_type n = bkt_num(p->val);
        node* cur = buckets[n];

        if (cur == p) {
            buckets[n] = ((uintptr_t)cur->next & 1) ? nullptr : cur->next; /*y*/
            delete_node(cur);
            --num_elements;
        } else {
            node* next = cur->next;
            while (!((uintptr_t)next & 1)) {
                if (next == p) {
                    cur->next = next->next;
                    delete_node(next);
                    --num_elements;
                    break;
                } else {
                    cur = next;
                    next = cur->next;
                }
            }
        }
    }
}

template <class V, class K, class HF, class Ex, class Eq, class A>
void THashTable<V, K, HF, Ex, Eq, A>::erase(iterator first, iterator last) {
    size_type f_bucket = first.cur ? bkt_num(first.cur->val) : buckets.size(); /*y*/
    size_type l_bucket = last.cur ? bkt_num(last.cur->val) : buckets.size();   /*y*/

    if (first.cur == last.cur) {
        return;
    } else if (f_bucket == l_bucket) {
        erase_bucket(f_bucket, first.cur, last.cur);
    } else {
        erase_bucket(f_bucket, first.cur, nullptr);
        for (size_type n = f_bucket + 1; n < l_bucket; ++n) {
            erase_bucket(n, nullptr);
        }
        if (l_bucket != buckets.size()) { /*y*/
            erase_bucket(l_bucket, last.cur);
        }
    }
}

template <class V, class K, class HF, class Ex, class Eq, class A>
inline void
THashTable<V, K, HF, Ex, Eq, A>::erase(const_iterator first, const_iterator last) {
    erase(iterator(const_cast<node*>(first.cur)), iterator(const_cast<node*>(last.cur)));
}

template <class V, class K, class HF, class Ex, class Eq, class A>
inline void THashTable<V, K, HF, Ex, Eq, A>::erase(const const_iterator& it) {
    erase(iterator(const_cast<node*>(it.cur)));
}

template <class V, class K, class HF, class Ex, class Eq, class A>
bool THashTable<V, K, HF, Ex, Eq, A>::reserve(size_type num_elements_hint) {
    const size_type old_n = buckets.size(); /*y*/
    if (num_elements_hint + 1 > old_n) {
        if (old_n != 1 && num_elements_hint <= old_n) { // TODO: this if is for backwards compatibility down to order-in-buckets level. Can be safely removed.
            return false;
        }

        const TBucketDivisor n = HashBucketCountExt(num_elements_hint + 1, buckets.BucketDivisorHint() + 1);
        if (n() > old_n) {
            buckets_type tmp(buckets.get_allocator());
            initialize_buckets_dynamic(tmp, n);
#ifdef __STL_USE_EXCEPTIONS
            try {
#endif /* __STL_USE_EXCEPTIONS */
                for (size_type bucket = 0; bucket < old_n; ++bucket) {
                    node* first = buckets[bucket];
                    while (first) {
                        size_type new_bucket = bkt_num(first->val, n);
                        node* next = first->next;
                        buckets[bucket] = ((uintptr_t)next & 1) ? nullptr : next; /*y*/
                        next = tmp[new_bucket];
                        first->next = next ? next : (node*)((uintptr_t) & (tmp[new_bucket + 1]) | 1); /*y*/
                        tmp[new_bucket] = first;
                        first = buckets[bucket];
                    }
                }

                buckets.swap(tmp);
                deinitialize_buckets(tmp);

                return true;
#ifdef __STL_USE_EXCEPTIONS
            } catch (...) {
                for (size_type bucket = 0; bucket < tmp.size() - 1; ++bucket) {
                    while (tmp[bucket]) {
                        node* next = tmp[bucket]->next;
                        delete_node(tmp[bucket]);
                        tmp[bucket] = ((uintptr_t)next & 1) ? nullptr : next /*y*/;
                    }
                }
                throw;
            }
#endif /* __STL_USE_EXCEPTIONS */
        }
    }

    return false;
}

template <class V, class K, class HF, class Ex, class Eq, class A>
void THashTable<V, K, HF, Ex, Eq, A>::erase_bucket(const size_type n, node* first, node* last) {
    node* cur = buckets[n];
    if (cur == first) {
        erase_bucket(n, last);
    } else {
        node* next;
        for (next = cur->next; next != first; cur = next, next = cur->next)
            ;
        while (next != last) { /*y; 3.1*/
            cur->next = next->next;
            delete_node(next);
            next = ((uintptr_t)cur->next & 1) ? nullptr : cur->next; /*y*/
            --num_elements;
        }
    }
}

template <class V, class K, class HF, class Ex, class Eq, class A>
void THashTable<V, K, HF, Ex, Eq, A>::erase_bucket(const size_type n, node* last) {
    node* cur = buckets[n];
    while (cur != last) {
        node* next = cur->next;
        delete_node(cur);
        cur = ((uintptr_t)next & 1) ? nullptr : next; /*y*/
        buckets[n] = cur;
        --num_elements;
    }
}

template <class V, class K, class HF, class Ex, class Eq, class A>
void THashTable<V, K, HF, Ex, Eq, A>::basic_clear() {
    if (!num_elements) {
        return;
    }

    node** first = buckets.begin();
    node** last = buckets.end();
    for (; first < last; ++first) {
        node* cur = *first;
        if (cur) {                          /*y*/
            while (!((uintptr_t)cur & 1)) { /*y*/
                node* next = cur->next;
                delete_node(cur);
                cur = next;
            }
            *first = nullptr;
        }
    }
    num_elements = 0;
}

template <class V, class K, class HF, class Ex, class Eq, class A>
void THashTable<V, K, HF, Ex, Eq, A>::copy_from_dynamic(const THashTable& ht) {
    Y_ASSERT(buckets.size() == ht.buckets.size() && !ht.empty());

#ifdef __STL_USE_EXCEPTIONS
    try {
#endif                                                      /* __STL_USE_EXCEPTIONS */
        for (size_type i = 0; i < ht.buckets.size(); ++i) { /*y*/
            if (const node* cur = ht.buckets[i]) {
                node* copy = new_node(cur->val);
                buckets[i] = copy;

                for (node* next = cur->next; !((uintptr_t)next & 1); cur = next, next = cur->next) {
                    copy->next = new_node(next->val);
                    copy = copy->next;
                }
                copy->next = (node*)((uintptr_t)&buckets[i + 1] | 1); /*y*/
            }
        }
        num_elements = ht.num_elements;
#ifdef __STL_USE_EXCEPTIONS
    } catch (...) {
        basic_clear();
        throw;
    }
#endif /* __STL_USE_EXCEPTIONS */
}

namespace NPrivate {
    template <class Key>
    inline TString MapKeyToString(const Key&) {
        return TypeName<Key>();
    }

    TString MapKeyToString(TStringBuf key);
    TString MapKeyToString(unsigned short key);
    TString MapKeyToString(short key);
    TString MapKeyToString(unsigned int key);
    TString MapKeyToString(int key);
    TString MapKeyToString(unsigned long key);
    TString MapKeyToString(long key);
    TString MapKeyToString(unsigned long long key);
    TString MapKeyToString(long long key);

    inline TString MapKeyToString(const TString& key) {
        return MapKeyToString(TStringBuf(key));
    }

    inline TString MapKeyToString(const char* key) {
        return MapKeyToString(TStringBuf(key));
    }

    inline TString MapKeyToString(char* key) {
        return MapKeyToString(TStringBuf(key));
    }

    [[noreturn]] void ThrowKeyNotFoundInHashTableException(const TStringBuf keyRepresentation);
} // namespace NPrivate

// Cannot name it just 'Hash' because it clashes with too many class members in the code.
template <class T>
size_t ComputeHash(const T& value) {
    return THash<T>{}(value);
}