#pragma once
#include "fwd.h"
#include "mapfindptr.h"
#include <util/memory/alloc.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);
bool operator==(const iterator& it) const {
return cur == it.cur;
}
bool operator!=(const iterator& it) const {
return cur != it.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);
bool operator==(const const_iterator& it) const {
return cur == it.cur;
}
bool operator!=(const const_iterator& it) const {
return cur != it.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>
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);
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;
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.
*/
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) {
using pii = std::pair<iterator, iterator>;
const size_type n = bkt_num_key(key);
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);
}
template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
class THashMap: public TMapOps<THashMap<Key, T, HashFcn, EqualKey, Alloc>> {
private:
using ht = THashTable<std::pair<const Key, T>, Key, HashFcn, TSelect1st, EqualKey, Alloc>;
ht rep;
public:
using key_type = typename ht::key_type;
using value_type = typename ht::value_type;
using hasher = typename ht::hasher;
using key_equal = typename ht::key_equal;
using allocator_type = typename ht::allocator_type;
using node_allocator_type = typename ht::node_allocator_type;
using mapped_type = T;
using size_type = typename ht::size_type;
using difference_type = typename ht::difference_type;
using pointer = typename ht::pointer;
using const_pointer = typename ht::const_pointer;
using reference = typename ht::reference;
using const_reference = typename ht::const_reference;
using iterator = typename ht::iterator;
using const_iterator = typename ht::const_iterator;
using insert_ctx = typename ht::insert_ctx;
hasher hash_function() const {
return rep.hash_function();
}
key_equal key_eq() const {
return rep.key_eq();
}
public:
THashMap()
: rep(0, hasher(), key_equal())
{
}
template <class TAllocParam>
explicit THashMap(TAllocParam* allocParam, size_type n = 0)
: rep(n, hasher(), key_equal(), allocParam)
{
}
explicit THashMap(size_type n)
: rep(n, hasher(), key_equal())
{
}
THashMap(size_type n, const hasher& hf)
: rep(n, hf, key_equal())
{
}
THashMap(size_type n, const hasher& hf, const key_equal& eql)
: rep(n, hf, eql)
{
}
template <class TAllocParam>
explicit THashMap(size_type n, TAllocParam* allocParam)
: rep(n, hasher(), key_equal(), allocParam)
{
}
template <class InputIterator>
THashMap(InputIterator f, InputIterator l)
: rep(0, hasher(), key_equal())
{
rep.insert_unique(f, l);
}
template <class InputIterator>
THashMap(InputIterator f, InputIterator l, size_type n)
: rep(n, hasher(), key_equal())
{
rep.insert_unique(f, l);
}
template <class InputIterator>
THashMap(InputIterator f, InputIterator l, size_type n,
const hasher& hf)
: rep(n, hf, key_equal())
{
rep.insert_unique(f, l);
}
template <class InputIterator>
THashMap(InputIterator f, InputIterator l, size_type n,
const hasher& hf, const key_equal& eql)
: rep(n, hf, eql)
{
rep.insert_unique(f, l);
}
THashMap(const std::initializer_list<std::pair<Key, T>>& list)
: rep(list.size(), hasher(), key_equal())
{
for (const auto& v : list) {
rep.insert_unique_noresize(v);
}
}
// THashMap has implicit copy/move constructors and copy-/move-assignment operators
// because its implementation is backed by THashTable.
// See hash_ut.cpp
public:
size_type size() const noexcept {
return rep.size();
}
yssize_t ysize() const noexcept {
return (yssize_t)rep.size();
}
size_type max_size() const noexcept {
return rep.max_size();
}
Y_PURE_FUNCTION bool empty() const noexcept {
return rep.empty();
}
explicit operator bool() const noexcept {
return !empty();
}
void swap(THashMap& hs) {
rep.swap(hs.rep);
}
iterator begin() {
return rep.begin();
}
iterator end() {
return rep.end();
}
const_iterator begin() const {
return rep.begin();
}
const_iterator end() const {
return rep.end();
}
const_iterator cbegin() const {
return rep.begin();
}
const_iterator cend() const {
return rep.end();
}
public:
template <class InputIterator>
void insert(InputIterator f, InputIterator l) {
rep.insert_unique(f, l);
}
std::pair<iterator, bool> insert(const value_type& obj) {
return rep.insert_unique(obj);
}
template <typename... Args>
std::pair<iterator, bool> emplace(Args&&... args) {
return rep.emplace_unique(std::forward<Args>(args)...);
}
std::pair<iterator, bool> insert_noresize(const value_type& obj) {
return rep.insert_unique_noresize(obj);
}
template <typename... Args>
std::pair<iterator, bool> emplace_noresize(Args&&... args) {
return rep.emplace_unique_noresize(std::forward<Args>(args)...);
}
template <class TheObj>
iterator insert_direct(const TheObj& obj, const insert_ctx& ins) {
return rep.insert_direct(obj, ins);
}
template <typename... Args>
iterator emplace_direct(const insert_ctx& ins, Args&&... args) {
return rep.emplace_direct(ins, std::forward<Args>(args)...);
}
template <typename TKey, typename... Args>
std::pair<iterator, bool> try_emplace(TKey&& key, Args&&... args) {
insert_ctx ctx = nullptr;
iterator it = find(key, ctx);
if (it == end()) {
it = rep.emplace_direct(ctx, std::piecewise_construct,
std::forward_as_tuple(std::forward<TKey>(key)),
std::forward_as_tuple(std::forward<Args>(args)...));
return {it, true};
}
return {it, false};
}
template <class TheKey>
iterator find(const TheKey& key) {
return rep.find(key);
}
template <class TheKey>
const_iterator find(const TheKey& key) const {
return rep.find(key);
}
template <class TheKey>
iterator find(const TheKey& key, insert_ctx& ins) {
return rep.find_i(key, ins);
}
template <class TheKey>
bool contains(const TheKey& key) const {
return rep.find(key) != rep.end();
}
bool contains(const key_type& key) const {
return rep.find(key) != rep.end();
}
template <class TheKey>
bool contains(const TheKey& key, insert_ctx& ins) {
return rep.find_i(key, ins) != rep.end();
}
template <class TKey>
T& operator[](const TKey& key) {
insert_ctx ctx = nullptr;
iterator it = find(key, ctx);
if (it != end()) {
return it->second;
}
return rep.emplace_direct(ctx, std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple())->second;
}
template <class TheKey>
const T& at(const TheKey& key) const {
using namespace ::NPrivate;
const_iterator it = find(key);
if (Y_UNLIKELY(it == end())) {
::NPrivate::ThrowKeyNotFoundInHashTableException(MapKeyToString(key));
}
return it->second;
}
template <class TheKey>
T& at(const TheKey& key) {
using namespace ::NPrivate;
iterator it = find(key);
if (Y_UNLIKELY(it == end())) {
::NPrivate::ThrowKeyNotFoundInHashTableException(MapKeyToString(key));
}
return it->second;
}
template <class TKey>
size_type count(const TKey& key) const {
return rep.count(key);
}
template <class TKey>
std::pair<iterator, iterator> equal_range(const TKey& key) {
return rep.equal_range(key);
}
template <class TKey>
std::pair<const_iterator, const_iterator> equal_range(const TKey& key) const {
return rep.equal_range(key);
}
template <class TKey>
size_type erase(const TKey& key) {
return rep.erase_one(key);
}
void erase(iterator it) {
rep.erase(it);
}
void erase(iterator f, iterator l) {
rep.erase(f, l);
}
void clear() {
rep.clear();
}
void clear(size_t downsize_hint) {
rep.clear(downsize_hint);
}
void basic_clear() {
rep.basic_clear();
}
void release_nodes() {
rep.release_nodes();
}
// if (stHash != NULL) bucket_count() must be equal to stHash->bucket_count()
template <class KeySaver>
int save_for_st(IOutputStream* stream, KeySaver& ks, sthash<int, int, THash<int>, TEqualTo<int>, typename KeySaver::TSizeType>* stHash = nullptr) const {
return rep.template save_for_st<KeySaver>(stream, ks, stHash);
}
public:
void reserve(size_type hint) {
rep.reserve(hint);
}
size_type bucket_count() const {
return rep.bucket_count();
}
size_type bucket_size(size_type n) const {
return rep.bucket_size(n);
}
node_allocator_type& GetNodeAllocator() {
return rep.GetNodeAllocator();
}
const node_allocator_type& GetNodeAllocator() const {
return rep.GetNodeAllocator();
}
};
template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
inline bool operator==(const THashMap<Key, T, HashFcn, EqualKey, Alloc>& hm1, const THashMap<Key, T, HashFcn, EqualKey, Alloc>& hm2) {
if (hm1.size() != hm2.size()) {
return false;
}
for (const auto& it1 : hm1) {
auto it2 = hm2.find(it1.first);
if ((it2 == hm2.end()) || !(it1 == *it2)) {
return false;
}
}
return true;
}
template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
inline bool operator!=(const THashMap<Key, T, HashFcn, EqualKey, Alloc>& hm1, const THashMap<Key, T, HashFcn, EqualKey, Alloc>& hm2) {
return !(hm1 == hm2);
}
template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
class THashMultiMap {
private:
using ht = THashTable<std::pair<const Key, T>, Key, HashFcn, TSelect1st, EqualKey, Alloc>;
ht rep;
public:
using key_type = typename ht::key_type;
using value_type = typename ht::value_type;
using hasher = typename ht::hasher;
using key_equal = typename ht::key_equal;
using mapped_type = T;
using allocator_type = typename ht::allocator_type;
using size_type = typename ht::size_type;
using difference_type = typename ht::difference_type;
using pointer = typename ht::pointer;
using const_pointer = typename ht::const_pointer;
using reference = typename ht::reference;
using const_reference = typename ht::const_reference;
using iterator = typename ht::iterator;
using const_iterator = typename ht::const_iterator;
using insert_ctx = typename ht::insert_ctx;
hasher hash_function() const {
return rep.hash_function();
}
key_equal key_eq() const {
return rep.key_eq();
}
public:
THashMultiMap()
: rep(0, hasher(), key_equal())
{
}
template <typename TAllocParam>
explicit THashMultiMap(TAllocParam* allocParam)
: rep(0, hasher(), key_equal(), allocParam)
{
}
explicit THashMultiMap(size_type n)
: rep(n, hasher(), key_equal())
{
}
THashMultiMap(size_type n, const hasher& hf)
: rep(n, hf, key_equal())
{
}
THashMultiMap(size_type n, const hasher& hf, const key_equal& eql)
: rep(n, hf, eql)
{
}
template <class InputIterator>
THashMultiMap(InputIterator f, InputIterator l)
: rep(0, hasher(), key_equal())
{
rep.insert_equal(f, l);
}
template <class InputIterator>
THashMultiMap(InputIterator f, InputIterator l, size_type n)
: rep(n, hasher(), key_equal())
{
rep.insert_equal(f, l);
}
template <class InputIterator>
THashMultiMap(InputIterator f, InputIterator l, size_type n, const hasher& hf)
: rep(n, hf, key_equal())
{
rep.insert_equal(f, l);
}
template <class InputIterator>
THashMultiMap(InputIterator f, InputIterator l, size_type n, const hasher& hf, const key_equal& eql)
: rep(n, hf, eql)
{
rep.insert_equal(f, l);
}
THashMultiMap(std::initializer_list<std::pair<Key, T>> list)
: rep(list.size(), hasher(), key_equal())
{
for (const auto& v : list) {
rep.emplace_equal_noresize(v);
}
}
// THashMultiMap has implicit copy/move constructors and copy-/move-assignment operators
// because its implementation is backed by THashTable.
// See hash_ut.cpp
public:
size_type size() const {
return rep.size();
}
yssize_t ysize() const {
return (yssize_t)rep.size();
}
size_type max_size() const {
return rep.max_size();
}
Y_PURE_FUNCTION bool empty() const {
return rep.empty();
}
explicit operator bool() const noexcept {
return !empty();
}
void swap(THashMultiMap& hs) {
rep.swap(hs.rep);
}
iterator begin() {
return rep.begin();
}
iterator end() {
return rep.end();
}
const_iterator begin() const {
return rep.begin();
}
const_iterator end() const {
return rep.end();
}
const_iterator cbegin() const {
return rep.begin();
}
const_iterator cend() const {
return rep.end();
}
public:
template <class InputIterator>
void insert(InputIterator f, InputIterator l) {
rep.insert_equal(f, l);
}
iterator insert(const value_type& obj) {
return rep.insert_equal(obj);
}
template <typename... Args>
iterator emplace(Args&&... args) {
return rep.emplace_equal(std::forward<Args>(args)...);
}
iterator insert_noresize(const value_type& obj) {
return rep.emplace_equal_noresize(obj);
}
template <typename... Args>
iterator emplace_noresize(Args&&... args) {
return rep.emplace_equal_noresize(std::forward<Args>(args)...);
}
template <class TheObj>
iterator insert_direct(const TheObj& obj, const insert_ctx& ins) {
return rep.insert_direct(obj, ins);
}
template <typename... Args>
iterator emplace_direct(const insert_ctx& ins, Args&&... args) {
return rep.emplace_direct(ins, std::forward<Args>(args)...);
}
template <class TKey>
const_iterator find(const TKey& key) const {
return rep.find(key);
}
template <class TKey>
iterator find(const TKey& key) {
return rep.find(key);
}
template <class TheKey>
iterator find(const TheKey& key, insert_ctx& ins) {
return rep.find_i(key, ins);
}
template <class TheKey>
bool contains(const TheKey& key) const {
return rep.find(key) != rep.end();
}
template <class TKey>
size_type count(const TKey& key) const {
return rep.count(key);
}
template <class TKey>
std::pair<iterator, iterator> equal_range(const TKey& key) {
return rep.equal_range(key);
}
template <class TKey>
std::pair<const_iterator, const_iterator> equal_range(const TKey& key) const {
return rep.equal_range(key);
}
size_type erase(const key_type& key) {
return rep.erase(key);
}
void erase(iterator it) {
rep.erase(it);
}
void erase(iterator f, iterator l) {
rep.erase(f, l);
}
void clear() {
rep.clear();
}
void clear(size_t downsize_hint) {
rep.clear(downsize_hint);
}
void basic_clear() {
rep.basic_clear();
}
void release_nodes() {
rep.release_nodes();
}
// if (stHash != NULL) bucket_count() must be equal to stHash->bucket_count()
template <class KeySaver>
int save_for_st(IOutputStream* stream, KeySaver& ks, sthash<int, int, THash<int>, TEqualTo<int>, typename KeySaver::TSizeType>* stHash = nullptr) const {
return rep.template save_for_st<KeySaver>(stream, ks, stHash);
}
public:
void reserve(size_type hint) {
rep.reserve(hint);
}
size_type bucket_count() const {
return rep.bucket_count();
}
size_type bucket_size(size_type n) const {
return rep.bucket_size(n);
}
};
template <class Key, class T, class HF, class EqKey, class Alloc>
inline bool operator==(const THashMultiMap<Key, T, HF, EqKey, Alloc>& hm1, const THashMultiMap<Key, T, HF, EqKey, Alloc>& hm2) {
// NOTE: copy-pasted from
// contrib/libs/cxxsupp/libcxx/include/unordered_map
// and adapted to THashMultiMap
if (hm1.size() != hm2.size()) {
return false;
}
using const_iterator = typename THashMultiMap<Key, T, HF, EqKey, Alloc>::const_iterator;
using TEqualRange = std::pair<const_iterator, const_iterator>;
for (const_iterator it = hm1.begin(), end = hm1.end(); it != end;) {
TEqualRange eq1 = hm1.equal_range(it->first);
TEqualRange eq2 = hm2.equal_range(it->first);
if (std::distance(eq1.first, eq1.second) != std::distance(eq2.first, eq2.second) ||
!std::is_permutation(eq1.first, eq1.second, eq2.first))
{
return false;
}
it = eq1.second;
}
return true;
}
template <class Key, class T, class HF, class EqKey, class Alloc>
inline bool operator!=(const THashMultiMap<Key, T, HF, EqKey, Alloc>& hm1, const THashMultiMap<Key, T, HF, EqKey, Alloc>& hm2) {
return !(hm1 == hm2);
}
// 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);
}