Website Summary Files Commits Branches @commit @diff @stats
path: root / gctest / flat_hash_map
diff options
context:
space:
mode:
Commit728886e38902d3133f2d94e59387d87fe800ace6 (patch)
Author
 Dimitar Trendafilov <trendafilov.dn@gmail.com>
2021-09-20 21:48:02 +0300
Committer
 Dimitar Trendafilov <trendafilov.dn@gmail.com>
2021-09-20 21:48:02 +0300
Files1589603eab06bf9aab3ceb3145f51347e056d175 /gctest/flat_hash_map
IPL-728886e38902d3133f2d94e59387d87fe800ace6.tar
IPL-728886e38902d3133f2d94e59387d87fe800ace6.tar.gz
IPL-728886e38902d3133f2d94e59387d87fe800ace6.zip
Parent8f14aeac7728e6b0efc9a9f7e849c784538dcb07 (diff)
Move files to match other projects
3 files changed, 0 insertions, 3641 deletions
-rw-r--r--gctest/flat_hash_map/bytell_hash_map.hpp1260
-rw-r--r--gctest/flat_hash_map/flat_hash_map.hpp1496
-rw-r--r--gctest/flat_hash_map/unordered_map.hpp885
diff --git a/gctest/flat_hash_map/bytell_hash_map.hpp b/gctest/flat_hash_map/bytell_hash_map.hpp
deleted file mode 100644
index 9c9a246..0000000
--- a/gctest/flat_hash_map/bytell_hash_map.hpp
+++ /dev/null
@@ -1,1260 +0,0 @@
-// Copyright Malte Skarupke 2017.
-// Distributed under the Boost Software License, Version 1.0.
-// (See http://www.boost.org/LICENSE_1_0.txt)
-
-#pragma once
-
-#include <cstdint>
-#include <cstddef>
-#include <cmath>
-#include <algorithm>
-#include <iterator>
-#include <utility>
-#include <type_traits>
-#include "flat_hash_map.hpp"
-#include <vector>
-#include <array>
-
-namespace ska
-{
-
-namespace detailv8
-{
-using ska::detailv3::functor_storage;
-using ska::detailv3::KeyOrValueHasher;
-using ska::detailv3::KeyOrValueEquality;
-using ska::detailv3::AssignIfTrue;
-using ska::detailv3::HashPolicySelector;
-
-template<typename = void>
-struct sherwood_v8_constants
-{
- static constexpr int8_t magic_for_empty = int8_t(0b11111111);
- static constexpr int8_t magic_for_reserved = int8_t(0b11111110);
- static constexpr int8_t bits_for_direct_hit = int8_t(0b10000000);
- static constexpr int8_t magic_for_direct_hit = int8_t(0b00000000);
- static constexpr int8_t magic_for_list_entry = int8_t(0b10000000);
-
- static constexpr int8_t bits_for_distance = int8_t(0b01111111);
- inline static int distance_from_metadata(int8_t metadata)
- {
- return metadata & bits_for_distance;
- }
-
- static constexpr int num_jump_distances = 126;
- // jump distances chosen like this:
- // 1. pick the first 16 integers to promote staying in the same block
- // 2. add the next 66 triangular numbers to get even jumps when
- // the hash table is a power of two
- // 3. add 44 more triangular numbers at a much steeper growth rate
- // to get a sequence that allows large jumps so that a table
- // with 10000 sequential numbers doesn't endlessly re-allocate
- static constexpr size_t jump_distances[num_jump_distances]
- {
- 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
-
- 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231,
- 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630,
- 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176,
- 1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830,
- 1891, 1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556,
-
- 3741, 8385, 18915, 42486, 95703, 215496, 485605, 1091503, 2456436,
- 5529475, 12437578, 27986421, 62972253, 141700195, 318819126, 717314626,
- 1614000520, 3631437253, 8170829695, 18384318876, 41364501751,
- 93070021080, 209407709220, 471167588430, 1060127437995, 2385287281530,
- 5366895564381, 12075513791265, 27169907873235, 61132301007778,
- 137547673121001, 309482258302503, 696335090510256, 1566753939653640,
- 3525196427195653, 7931691866727775, 17846306747368716,
- 40154190394120111, 90346928493040500, 203280588949935750,
- 457381324898247375, 1029107980662394500, 2315492957028380766,
- 5209859150892887590,
- };
-};
-template<typename T>
-constexpr int8_t sherwood_v8_constants<T>::magic_for_empty;
-template<typename T>
-constexpr int8_t sherwood_v8_constants<T>::magic_for_reserved;
-template<typename T>
-constexpr int8_t sherwood_v8_constants<T>::bits_for_direct_hit;
-template<typename T>
-constexpr int8_t sherwood_v8_constants<T>::magic_for_direct_hit;
-template<typename T>
-constexpr int8_t sherwood_v8_constants<T>::magic_for_list_entry;
-
-template<typename T>
-constexpr int8_t sherwood_v8_constants<T>::bits_for_distance;
-
-template<typename T>
-constexpr int sherwood_v8_constants<T>::num_jump_distances;
-template<typename T>
-constexpr size_t sherwood_v8_constants<T>::jump_distances[num_jump_distances];
-
-template<typename T, uint8_t BlockSize>
-struct sherwood_v8_block
-{
- sherwood_v8_block()
- {
- }
- ~sherwood_v8_block()
- {
- }
- int8_t control_bytes[BlockSize];
- union
- {
- T data[BlockSize];
- };
-
- static sherwood_v8_block * empty_block()
- {
- static std::array<int8_t, BlockSize> empty_bytes = []
- {
- std::array<int8_t, BlockSize> result;
- result.fill(sherwood_v8_constants<>::magic_for_empty);
- return result;
- }();
- return reinterpret_cast<sherwood_v8_block *>(&empty_bytes);
- }
-
- int first_empty_index() const
- {
- for (int i = 0; i < BlockSize; ++i)
- {
- if (control_bytes[i] == sherwood_v8_constants<>::magic_for_empty)
- return i;
- }
- return -1;
- }
-
- void fill_control_bytes(int8_t value)
- {
- std::fill(std::begin(control_bytes), std::end(control_bytes), value);
- }
-};
-
-template<typename T, typename FindKey, typename ArgumentHash, typename Hasher, typename ArgumentEqual, typename Equal, typename ArgumentAlloc, typename ByteAlloc, uint8_t BlockSize>
-class sherwood_v8_table : private ByteAlloc, private Hasher, private Equal
-{
- using AllocatorTraits = std::allocator_traits<ByteAlloc>;
- using BlockType = sherwood_v8_block<T, BlockSize>;
- using BlockPointer = BlockType *;
- using BytePointer = typename AllocatorTraits::pointer;
- struct convertible_to_iterator;
- using Constants = sherwood_v8_constants<>;
-
-public:
-
- using value_type = T;
- using size_type = size_t;
- using difference_type = std::ptrdiff_t;
- using hasher = ArgumentHash;
- using key_equal = ArgumentEqual;
- using allocator_type = ByteAlloc;
- using reference = value_type &;
- using const_reference = const value_type &;
- using pointer = value_type *;
- using const_pointer = const value_type *;
-
- sherwood_v8_table()
- {
- }
- explicit sherwood_v8_table(size_type bucket_count, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
- : ByteAlloc(alloc), Hasher(hash), Equal(equal)
- {
- if (bucket_count)
- rehash(bucket_count);
- }
- sherwood_v8_table(size_type bucket_count, const ArgumentAlloc & alloc)
- : sherwood_v8_table(bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
- {
- }
- sherwood_v8_table(size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
- : sherwood_v8_table(bucket_count, hash, ArgumentEqual(), alloc)
- {
- }
- explicit sherwood_v8_table(const ArgumentAlloc & alloc)
- : ByteAlloc(alloc)
- {
- }
- template<typename It>
- sherwood_v8_table(It first, It last, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
- : sherwood_v8_table(bucket_count, hash, equal, alloc)
- {
- insert(first, last);
- }
- template<typename It>
- sherwood_v8_table(It first, It last, size_type bucket_count, const ArgumentAlloc & alloc)
- : sherwood_v8_table(first, last, bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
- {
- }
- template<typename It>
- sherwood_v8_table(It first, It last, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
- : sherwood_v8_table(first, last, bucket_count, hash, ArgumentEqual(), alloc)
- {
- }
- sherwood_v8_table(std::initializer_list<T> il, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
- : sherwood_v8_table(bucket_count, hash, equal, alloc)
- {
- if (bucket_count == 0)
- rehash(il.size());
- insert(il.begin(), il.end());
- }
- sherwood_v8_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentAlloc & alloc)
- : sherwood_v8_table(il, bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
- {
- }
- sherwood_v8_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
- : sherwood_v8_table(il, bucket_count, hash, ArgumentEqual(), alloc)
- {
- }
- sherwood_v8_table(const sherwood_v8_table & other)
- : sherwood_v8_table(other, AllocatorTraits::select_on_container_copy_construction(other.get_allocator()))
- {
- }
- sherwood_v8_table(const sherwood_v8_table & other, const ArgumentAlloc & alloc)
- : ByteAlloc(alloc), Hasher(other), Equal(other), _max_load_factor(other._max_load_factor)
- {
- rehash_for_other_container(other);
- try
- {
- insert(other.begin(), other.end());
- }
- catch(...)
- {
- clear();
- deallocate_data(entries, num_slots_minus_one);
- throw;
- }
- }
- sherwood_v8_table(sherwood_v8_table && other) noexcept
- : ByteAlloc(std::move(other)), Hasher(std::move(other)), Equal(std::move(other))
- , _max_load_factor(other._max_load_factor)
- {
- swap_pointers(other);
- }
- sherwood_v8_table(sherwood_v8_table && other, const ArgumentAlloc & alloc) noexcept
- : ByteAlloc(alloc), Hasher(std::move(other)), Equal(std::move(other))
- , _max_load_factor(other._max_load_factor)
- {
- swap_pointers(other);
- }
- sherwood_v8_table & operator=(const sherwood_v8_table & other)
- {
- if (this == std::addressof(other))
- return *this;
-
- clear();
- if (AllocatorTraits::propagate_on_container_copy_assignment::value)
- {
- if (static_cast<ByteAlloc &>(*this) != static_cast<const ByteAlloc &>(other))
- {
- reset_to_empty_state();
- }
- AssignIfTrue<ByteAlloc, AllocatorTraits::propagate_on_container_copy_assignment::value>()(*this, other);
- }
- _max_load_factor = other._max_load_factor;
- static_cast<Hasher &>(*this) = other;
- static_cast<Equal &>(*this) = other;
- rehash_for_other_container(other);
- insert(other.begin(), other.end());
- return *this;
- }
- sherwood_v8_table & operator=(sherwood_v8_table && other) noexcept
- {
- if (this == std::addressof(other))
- return *this;
- else if (AllocatorTraits::propagate_on_container_move_assignment::value)
- {
- clear();
- reset_to_empty_state();
- AssignIfTrue<ByteAlloc, AllocatorTraits::propagate_on_container_move_assignment::value>()(*this, std::move(other));
- swap_pointers(other);
- }
- else if (static_cast<ByteAlloc &>(*this) == static_cast<ByteAlloc &>(other))
- {
- swap_pointers(other);
- }
- else
- {
- clear();
- _max_load_factor = other._max_load_factor;
- rehash_for_other_container(other);
- for (T & elem : other)
- emplace(std::move(elem));
- other.clear();
- }
- static_cast<Hasher &>(*this) = std::move(other);
- static_cast<Equal &>(*this) = std::move(other);
- return *this;
- }
- ~sherwood_v8_table()
- {
- clear();
- deallocate_data(entries, num_slots_minus_one);
- }
-
- const allocator_type & get_allocator() const
- {
- return static_cast<const allocator_type &>(*this);
- }
- const ArgumentEqual & key_eq() const
- {
- return static_cast<const ArgumentEqual &>(*this);
- }
- const ArgumentHash & hash_function() const
- {
- return static_cast<const ArgumentHash &>(*this);
- }
-
- template<typename ValueType>
- struct templated_iterator
- {
- private:
- friend class sherwood_v8_table;
- BlockPointer current = BlockPointer();
- size_t index = 0;
-
- public:
- templated_iterator()
- {
- }
- templated_iterator(BlockPointer entries, size_t index)
- : current(entries)
- , index(index)
- {
- }
-
- using iterator_category = std::forward_iterator_tag;
- using value_type = ValueType;
- using difference_type = ptrdiff_t;
- using pointer = ValueType *;
- using reference = ValueType &;
-
- friend bool operator==(const templated_iterator & lhs, const templated_iterator & rhs)
- {
- return lhs.index == rhs.index;
- }
- friend bool operator!=(const templated_iterator & lhs, const templated_iterator & rhs)
- {
- return !(lhs == rhs);
- }
-
- templated_iterator & operator++()
- {
- do
- {
- if (index % BlockSize == 0)
- --current;
- if (index-- == 0)
- break;
- }
- while(current->control_bytes[index % BlockSize] == Constants::magic_for_empty);
- return *this;
- }
- templated_iterator operator++(int)
- {
- templated_iterator copy(*this);
- ++*this;
- return copy;
- }
-
- ValueType & operator*() const
- {
- return current->data[index % BlockSize];
- }
- ValueType * operator->() const
- {
- return current->data + index % BlockSize;
- }
-
- operator templated_iterator<const value_type>() const
- {
- return { current, index };
- }
- };
- using iterator = templated_iterator<value_type>;
- using const_iterator = templated_iterator<const value_type>;
-
- iterator begin()
- {
- size_t num_slots = num_slots_minus_one ? num_slots_minus_one + 1 : 0;
- return ++iterator{ entries + num_slots / BlockSize, num_slots };
- }
- const_iterator begin() const
- {
- size_t num_slots = num_slots_minus_one ? num_slots_minus_one + 1 : 0;
- return ++iterator{ entries + num_slots / BlockSize, num_slots };
- }
- const_iterator cbegin() const
- {
- return begin();
- }
- iterator end()
- {
- return { entries - 1, std::numeric_limits<size_t>::max() };
- }
- const_iterator end() const
- {
- return { entries - 1, std::numeric_limits<size_t>::max() };
- }
- const_iterator cend() const
- {
- return end();
- }
-
- inline iterator find(const FindKey & key)
- {
- size_t index = hash_object(key);
- size_t num_slots_minus_one = this->num_slots_minus_one;
- BlockPointer entries = this->entries;
- index = hash_policy.index_for_hash(index, num_slots_minus_one);
- bool first = true;
- for (;;)
- {
- size_t block_index = index / BlockSize;
- int index_in_block = index % BlockSize;
- BlockPointer block = entries + block_index;
- int8_t metadata = block->control_bytes[index_in_block];
- if (first)
- {
- if ((metadata & Constants::bits_for_direct_hit) != Constants::magic_for_direct_hit)
- return end();
- first = false;
- }
- if (compares_equal(key, block->data[index_in_block]))
- return { block, index };
- int8_t to_next_index = metadata & Constants::bits_for_distance;
- if (to_next_index == 0)
- return end();
- index += Constants::jump_distances[to_next_index];
- index = hash_policy.keep_in_range(index, num_slots_minus_one);
- }
- }
- inline const_iterator find(const FindKey & key) const
- {
- return const_cast<sherwood_v8_table *>(this)->find(key);
- }
- size_t count(const FindKey & key) const
- {
- return find(key) == end() ? 0 : 1;
- }
- std::pair<iterator, iterator> equal_range(const FindKey & key)
- {
- iterator found = find(key);
- if (found == end())
- return { found, found };
- else
- return { found, std::next(found) };
- }
- std::pair<const_iterator, const_iterator> equal_range(const FindKey & key) const
- {
- const_iterator found = find(key);
- if (found == end())
- return { found, found };
- else
- return { found, std::next(found) };
- }
-
-
- template<typename Key, typename... Args>
- inline std::pair<iterator, bool> emplace(Key && key, Args &&... args)
- {
- size_t index = hash_object(key);
- size_t num_slots_minus_one = this->num_slots_minus_one;
- BlockPointer entries = this->entries;
- index = hash_policy.index_for_hash(index, num_slots_minus_one);
- bool first = true;
- for (;;)
- {
- size_t block_index = index / BlockSize;
- int index_in_block = index % BlockSize;
- BlockPointer block = entries + block_index;
- int8_t metadata = block->control_bytes[index_in_block];
- if (first)
- {
- if ((metadata & Constants::bits_for_direct_hit) != Constants::magic_for_direct_hit)
- return emplace_direct_hit({ index, block }, std::forward<Key>(key), std::forward<Args>(args)...);
- first = false;
- }
- if (compares_equal(key, block->data[index_in_block]))
- return { { block, index }, false };
- int8_t to_next_index = metadata & Constants::bits_for_distance;
- if (to_next_index == 0)
- return emplace_new_key({ index, block }, std::forward<Key>(key), std::forward<Args>(args)...);
- index += Constants::jump_distances[to_next_index];
- index = hash_policy.keep_in_range(index, num_slots_minus_one);
- }
- }
-
- std::pair<iterator, bool> insert(const value_type & value)
- {
- return emplace(value);
- }
- std::pair<iterator, bool> insert(value_type && value)
- {
- return emplace(std::move(value));
- }
- template<typename... Args>
- iterator emplace_hint(const_iterator, Args &&... args)
- {
- return emplace(std::forward<Args>(args)...).first;
- }
- iterator insert(const_iterator, const value_type & value)
- {
- return emplace(value).first;
- }
- iterator insert(const_iterator, value_type && value)
- {
- return emplace(std::move(value)).first;
- }
-
- template<typename It>
- void insert(It begin, It end)
- {
- for (; begin != end; ++begin)
- {
- emplace(*begin);
- }
- }
- void insert(std::initializer_list<value_type> il)
- {
- insert(il.begin(), il.end());
- }
-
- void rehash(size_t num_items)
- {
- num_items = std::max(num_items, static_cast<size_t>(std::ceil(num_elements / static_cast<double>(_max_load_factor))));
- if (num_items == 0)
- {
- reset_to_empty_state();
- return;
- }
- auto new_prime_index = hash_policy.next_size_over(num_items);
- if (num_items == num_slots_minus_one + 1)
- return;
- size_t num_blocks = num_items / BlockSize;
- if (num_items % BlockSize)
- ++num_blocks;
- size_t memory_requirement = calculate_memory_requirement(num_blocks);
- unsigned char * new_memory = &*AllocatorTraits::allocate(*this, memory_requirement);
-
- BlockPointer new_buckets = reinterpret_cast<BlockPointer>(new_memory);
-
- BlockPointer special_end_item = new_buckets + num_blocks;
- for (BlockPointer it = new_buckets; it <= special_end_item; ++it)
- it->fill_control_bytes(Constants::magic_for_empty);
- using std::swap;
- swap(entries, new_buckets);
- swap(num_slots_minus_one, num_items);
- --num_slots_minus_one;
- hash_policy.commit(new_prime_index);
- num_elements = 0;
- if (num_items)
- ++num_items;
- size_t old_num_blocks = num_items / BlockSize;
- if (num_items % BlockSize)
- ++old_num_blocks;
- for (BlockPointer it = new_buckets, end = new_buckets + old_num_blocks; it != end; ++it)
- {
- for (int i = 0; i < BlockSize; ++i)
- {
- int8_t metadata = it->control_bytes[i];
- if (metadata != Constants::magic_for_empty && metadata != Constants::magic_for_reserved)
- {
- emplace(std::move(it->data[i]));
- AllocatorTraits::destroy(*this, it->data + i);
- }
- }
- }
- deallocate_data(new_buckets, num_items - 1);
- }
-
- void reserve(size_t num_elements)
- {
- size_t required_buckets = num_buckets_for_reserve(num_elements);
- if (required_buckets > bucket_count())
- rehash(required_buckets);
- }
-
- // the return value is a type that can be converted to an iterator
- // the reason for doing this is that it's not free to find the
- // iterator pointing at the next element. if you care about the
- // next iterator, turn the return value into an iterator
- convertible_to_iterator erase(const_iterator to_erase)
- {
- LinkedListIt current = { to_erase.index, to_erase.current };
- if (current.has_next())
- {
- LinkedListIt previous = current;
- LinkedListIt next = current.next(*this);
- while (next.has_next())
- {
- previous = next;
- next = next.next(*this);
- }
- AllocatorTraits::destroy(*this, std::addressof(*current));
- AllocatorTraits::construct(*this, std::addressof(*current), std::move(*next));
- AllocatorTraits::destroy(*this, std::addressof(*next));
- next.set_metadata(Constants::magic_for_empty);
- previous.clear_next();
- }
- else
- {
- if (!current.is_direct_hit())
- find_parent_block(current).clear_next();
- AllocatorTraits::destroy(*this, std::addressof(*current));
- current.set_metadata(Constants::magic_for_empty);
- }
- --num_elements;
- return { to_erase.current, to_erase.index };
- }
-
- iterator erase(const_iterator begin_it, const_iterator end_it)
- {
- if (begin_it == end_it)
- return { begin_it.current, begin_it.index };
- if (std::next(begin_it) == end_it)
- return erase(begin_it);
- if (begin_it == begin() && end_it == end())
- {
- clear();
- return { end_it.current, end_it.index };
- }
- std::vector<std::pair<int, LinkedListIt>> depth_in_chain;
- for (const_iterator it = begin_it; it != end_it; ++it)
- {
- LinkedListIt list_it(it.index, it.current);
- if (list_it.is_direct_hit())
- depth_in_chain.emplace_back(0, list_it);
- else
- {
- LinkedListIt root = find_direct_hit(list_it);
- int distance = 1;
- for (;;)
- {
- LinkedListIt next = root.next(*this);
- if (next == list_it)
- break;
- ++distance;
- root = next;
- }
- depth_in_chain.emplace_back(distance, list_it);
- }
- }
- std::sort(depth_in_chain.begin(), depth_in_chain.end(), [](const auto & a, const auto & b) { return a.first < b.first; });
- for (auto it = depth_in_chain.rbegin(), end = depth_in_chain.rend(); it != end; ++it)
- {
- erase(it->second.it());
- }
-
- if (begin_it.current->control_bytes[begin_it.index % BlockSize] == Constants::magic_for_empty)
- return ++iterator{ begin_it.current, begin_it.index };
- else
- return { begin_it.current, begin_it.index };
- }
-
- size_t erase(const FindKey & key)
- {
- auto found = find(key);
- if (found == end())
- return 0;
- else
- {
- erase(found);
- return 1;
- }
- }
-
- void clear()
- {
- if (!num_slots_minus_one)
- return;
- size_t num_slots = num_slots_minus_one + 1;
- size_t num_blocks = num_slots / BlockSize;
- if (num_slots % BlockSize)
- ++num_blocks;
- for (BlockPointer it = entries, end = it + num_blocks; it != end; ++it)
- {
- for (int i = 0; i < BlockSize; ++i)
- {
- if (it->control_bytes[i] != Constants::magic_for_empty)
- {
- AllocatorTraits::destroy(*this, std::addressof(it->data[i]));
- it->control_bytes[i] = Constants::magic_for_empty;
- }
- }
- }
- num_elements = 0;
- }
-
- void shrink_to_fit()
- {
- rehash_for_other_container(*this);
- }
-
- void swap(sherwood_v8_table & other)
- {
- using std::swap;
- swap_pointers(other);
- swap(static_cast<ArgumentHash &>(*this), static_cast<ArgumentHash &>(other));
- swap(static_cast<ArgumentEqual &>(*this), static_cast<ArgumentEqual &>(other));
- if (AllocatorTraits::propagate_on_container_swap::value)
- swap(static_cast<ByteAlloc &>(*this), static_cast<ByteAlloc &>(other));
- }
-
- size_t size() const
- {
- return num_elements;
- }
- size_t max_size() const
- {
- return (AllocatorTraits::max_size(*this)) / sizeof(T);
- }
- size_t bucket_count() const
- {
- return num_slots_minus_one ? num_slots_minus_one + 1 : 0;
- }
- size_type max_bucket_count() const
- {
- return (AllocatorTraits::max_size(*this)) / sizeof(T);
- }
- size_t bucket(const FindKey & key) const
- {
- return hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
- }
- float load_factor() const
- {
- return static_cast<double>(num_elements) / (num_slots_minus_one + 1);
- }
- void max_load_factor(float value)
- {
- _max_load_factor = value;
- }
- float max_load_factor() const
- {
- return _max_load_factor;
- }
-
- bool empty() const
- {
- return num_elements == 0;
- }
-
-private:
- BlockPointer entries = BlockType::empty_block();
- size_t num_slots_minus_one = 0;
- typename HashPolicySelector<ArgumentHash>::type hash_policy;
- float _max_load_factor = 0.9375f;
- size_t num_elements = 0;
-
- size_t num_buckets_for_reserve(size_t num_elements) const
- {
- return static_cast<size_t>(std::ceil(num_elements / static_cast<double>(_max_load_factor)));
- }
- void rehash_for_other_container(const sherwood_v8_table & other)
- {
- rehash(std::min(num_buckets_for_reserve(other.size()), other.bucket_count()));
- }
- bool is_full() const
- {
- if (!num_slots_minus_one)
- return true;
- else
- return num_elements + 1 > (num_slots_minus_one + 1) * static_cast<double>(_max_load_factor);
- }
-
- void swap_pointers(sherwood_v8_table & other)
- {
- using std::swap;
- swap(hash_policy, other.hash_policy);
- swap(entries, other.entries);
- swap(num_slots_minus_one, other.num_slots_minus_one);
- swap(num_elements, other.num_elements);
- swap(_max_load_factor, other._max_load_factor);
- }
-
- struct LinkedListIt
- {
- size_t index = 0;
- BlockPointer block = nullptr;
-
- LinkedListIt()
- {
- }
- LinkedListIt(size_t index, BlockPointer block)
- : index(index), block(block)
- {
- }
-
- iterator it() const
- {
- return { block, index };
- }
- int index_in_block() const
- {
- return index % BlockSize;
- }
- bool is_direct_hit() const
- {
- return (metadata() & Constants::bits_for_direct_hit) == Constants::magic_for_direct_hit;
- }
- bool is_empty() const
- {
- return metadata() == Constants::magic_for_empty;
- }
- bool has_next() const
- {
- return jump_index() != 0;
- }
- int8_t jump_index() const
- {
- return Constants::distance_from_metadata(metadata());
- }
- int8_t metadata() const
- {
- return block->control_bytes[index_in_block()];
- }
- void set_metadata(int8_t metadata)
- {
- block->control_bytes[index_in_block()] = metadata;
- }
-
- LinkedListIt next(sherwood_v8_table & table) const
- {
- int8_t distance = jump_index();
- size_t next_index = table.hash_policy.keep_in_range(index + Constants::jump_distances[distance], table.num_slots_minus_one);
- return { next_index, table.entries + next_index / BlockSize };
- }
- void set_next(int8_t jump_index)
- {
- int8_t & metadata = block->control_bytes[index_in_block()];
- metadata = (metadata & ~Constants::bits_for_distance) | jump_index;
- }
- void clear_next()
- {
- set_next(0);
- }
-
- value_type & operator*() const
- {
- return block->data[index_in_block()];
- }
- bool operator!() const
- {
- return !block;
- }
- explicit operator bool() const
- {
- return block != nullptr;
- }
- bool operator==(const LinkedListIt & other) const
- {
- return index == other.index;
- }
- bool operator!=(const LinkedListIt & other) const
- {
- return !(*this == other);
- }
- };
-
- template<typename... Args>
- SKA_NOINLINE(std::pair<iterator, bool>) emplace_direct_hit(LinkedListIt block, Args &&... args)
- {
- using std::swap;
- if (is_full())
- {
- grow();
- return emplace(std::forward<Args>(args)...);
- }
- if (block.metadata() == Constants::magic_for_empty)
- {
- AllocatorTraits::construct(*this, std::addressof(*block), std::forward<Args>(args)...);
- block.set_metadata(Constants::magic_for_direct_hit);
- ++num_elements;
- return { block.it(), true };
- }
- else
- {
- LinkedListIt parent_block = find_parent_block(block);
- std::pair<int8_t, LinkedListIt> free_block = find_free_index(parent_block);
- if (!free_block.first)
- {
- grow();
- return emplace(std::forward<Args>(args)...);
- }
- value_type new_value(std::forward<Args>(args)...);
- for (LinkedListIt it = block;;)
- {
- AllocatorTraits::construct(*this, std::addressof(*free_block.second), std::move(*it));
- AllocatorTraits::destroy(*this, std::addressof(*it));
- parent_block.set_next(free_block.first);
- free_block.second.set_metadata(Constants::magic_for_list_entry);
- if (!it.has_next())
- {
- it.set_metadata(Constants::magic_for_empty);
- break;
- }
- LinkedListIt next = it.next(*this);
- it.set_metadata(Constants::magic_for_empty);
- block.set_metadata(Constants::magic_for_reserved);
- it = next;
- parent_block = free_block.second;
- free_block = find_free_index(free_block.second);
- if (!free_block.first)
- {
- grow();
- return emplace(std::move(new_value));
- }
- }
- AllocatorTraits::construct(*this, std::addressof(*block), std::move(new_value));
- block.set_metadata(Constants::magic_for_direct_hit);
- ++num_elements;
- return { block.it(), true };
- }
- }
-
- template<typename... Args>
- SKA_NOINLINE(std::pair<iterator, bool>) emplace_new_key(LinkedListIt parent, Args &&... args)
- {
- if (is_full())
- {
- grow();
- return emplace(std::forward<Args>(args)...);
- }
- std::pair<int8_t, LinkedListIt> free_block = find_free_index(parent);
- if (!free_block.first)
- {
- grow();
- return emplace(std::forward<Args>(args)...);
- }
- AllocatorTraits::construct(*this, std::addressof(*free_block.second), std::forward<Args>(args)...);
- free_block.second.set_metadata(Constants::magic_for_list_entry);
- parent.set_next(free_block.first);
- ++num_elements;
- return { free_block.second.it(), true };
- }
-
- LinkedListIt find_direct_hit(LinkedListIt child) const
- {
- size_t to_move_hash = hash_object(*child);
- size_t to_move_index = hash_policy.index_for_hash(to_move_hash, num_slots_minus_one);
- return { to_move_index, entries + to_move_index / BlockSize };
- }
- LinkedListIt find_parent_block(LinkedListIt child)
- {
- LinkedListIt parent_block = find_direct_hit(child);
- for (;;)
- {
- LinkedListIt next = parent_block.next(*this);
- if (next == child)
- return parent_block;
- parent_block = next;
- }
- }
-
- std::pair<int8_t, LinkedListIt> find_free_index(LinkedListIt parent) const
- {
- for (int8_t jump_index = 1; jump_index < Constants::num_jump_distances; ++jump_index)
- {
- size_t index = hash_policy.keep_in_range(parent.index + Constants::jump_distances[jump_index], num_slots_minus_one);
- BlockPointer block = entries + index / BlockSize;
- if (block->control_bytes[index % BlockSize] == Constants::magic_for_empty)
- return { jump_index, { index, block } };
- }
- return { 0, {} };
- }
-
- void grow()
- {
- rehash(std::max(size_t(10), 2 * bucket_count()));
- }
-
- size_t calculate_memory_requirement(size_t num_blocks)
- {
- size_t memory_required = sizeof(BlockType) * num_blocks;
- memory_required += BlockSize; // for metadata of past-the-end pointer
- return memory_required;
- }
-
- void deallocate_data(BlockPointer begin, size_t num_slots_minus_one)
- {
- if (begin == BlockType::empty_block())
- return;
-
- ++num_slots_minus_one;
- size_t num_blocks = num_slots_minus_one / BlockSize;
- if (num_slots_minus_one % BlockSize)
- ++num_blocks;
- size_t memory = calculate_memory_requirement(num_blocks);
- unsigned char * as_byte_pointer = reinterpret_cast<unsigned char *>(begin);
- AllocatorTraits::deallocate(*this, typename AllocatorTraits::pointer(as_byte_pointer), memory);
- }
-
- void reset_to_empty_state()
- {
- deallocate_data(entries, num_slots_minus_one);
- entries = BlockType::empty_block();
- num_slots_minus_one = 0;
- hash_policy.reset();
- }
-
- template<typename U>
- size_t hash_object(const U & key)
- {
- return static_cast<Hasher &>(*this)(key);
- }
- template<typename U>
- size_t hash_object(const U & key) const
- {
- return static_cast<const Hasher &>(*this)(key);
- }
- template<typename L, typename R>
- bool compares_equal(const L & lhs, const R & rhs)
- {
- return static_cast<Equal &>(*this)(lhs, rhs);
- }
-
- struct convertible_to_iterator
- {
- BlockPointer it;
- size_t index;
-
- operator iterator()
- {
- if (it->control_bytes[index % BlockSize] == Constants::magic_for_empty)
- return ++iterator{it, index};
- else
- return { it, index };
- }
- operator const_iterator()
- {
- if (it->control_bytes[index % BlockSize] == Constants::magic_for_empty)
- return ++iterator{it, index};
- else
- return { it, index };
- }
- };
-};
-template<typename T, typename Enable = void>
-struct AlignmentOr8Bytes
-{
- static constexpr size_t value = 8;
-};
-template<typename T>
-struct AlignmentOr8Bytes<T, typename std::enable_if<alignof(T) >= 1>::type>
-{
- static constexpr size_t value = alignof(T);
-};
-template<typename... Args>
-struct CalculateBytellBlockSize;
-template<typename First, typename... More>
-struct CalculateBytellBlockSize<First, More...>
-{
- static constexpr size_t this_value = AlignmentOr8Bytes<First>::value;
- static constexpr size_t base_value = CalculateBytellBlockSize<More...>::value;
- static constexpr size_t value = this_value > base_value ? this_value : base_value;
-};
-template<>
-struct CalculateBytellBlockSize<>
-{
- static constexpr size_t value = 8;
-};
-}
-
-template<typename K, typename V, typename H = std::hash<K>, typename E = std::equal_to<K>, typename A = std::allocator<std::pair<K, V> > >
-class bytell_hash_map
- : public detailv8::sherwood_v8_table
- <
- std::pair<K, V>,
- K,
- H,
- detailv8::KeyOrValueHasher<K, std::pair<K, V>, H>,
- E,
- detailv8::KeyOrValueEquality<K, std::pair<K, V>, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<unsigned char>,
- detailv8::CalculateBytellBlockSize<K, V>::value
- >
-{
- using Table = detailv8::sherwood_v8_table
- <
- std::pair<K, V>,
- K,
- H,
- detailv8::KeyOrValueHasher<K, std::pair<K, V>, H>,
- E,
- detailv8::KeyOrValueEquality<K, std::pair<K, V>, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<unsigned char>,
- detailv8::CalculateBytellBlockSize<K, V>::value
- >;
-public:
-
- using key_type = K;
- using mapped_type = V;
-
- using Table::Table;
- bytell_hash_map()
- {
- }
-
- inline V & operator[](const K & key)
- {
- return emplace(key, convertible_to_value()).first->second;
- }
- inline V & operator[](K && key)
- {
- return emplace(std::move(key), convertible_to_value()).first->second;
- }
- V & at(const K & key)
- {
- auto found = this->find(key);
- if (found == this->end())
- throw std::out_of_range("Argument passed to at() was not in the map.");
- return found->second;
- }
- const V & at(const K & key) const
- {
- auto found = this->find(key);
- if (found == this->end())
- throw std::out_of_range("Argument passed to at() was not in the map.");
- return found->second;
- }
-
- using Table::emplace;
- std::pair<typename Table::iterator, bool> emplace()
- {
- return emplace(key_type(), convertible_to_value());
- }
- template<typename M>
- std::pair<typename Table::iterator, bool> insert_or_assign(const key_type & key, M && m)
- {
- auto emplace_result = emplace(key, std::forward<M>(m));
- if (!emplace_result.second)
- emplace_result.first->second = std::forward<M>(m);
- return emplace_result;
- }
- template<typename M>
- std::pair<typename Table::iterator, bool> insert_or_assign(key_type && key, M && m)
- {
- auto emplace_result = emplace(std::move(key), std::forward<M>(m));
- if (!emplace_result.second)
- emplace_result.first->second = std::forward<M>(m);
- return emplace_result;
- }
- template<typename M>
- typename Table::iterator insert_or_assign(typename Table::const_iterator, const key_type & key, M && m)
- {
- return insert_or_assign(key, std::forward<M>(m)).first;
- }
- template<typename M>
- typename Table::iterator insert_or_assign(typename Table::const_iterator, key_type && key, M && m)
- {
- return insert_or_assign(std::move(key), std::forward<M>(m)).first;
- }
-
- friend bool operator==(const bytell_hash_map & lhs, const bytell_hash_map & rhs)
- {
- if (lhs.size() != rhs.size())
- return false;
- for (const typename Table::value_type & value : lhs)
- {
- auto found = rhs.find(value.first);
- if (found == rhs.end())
- return false;
- else if (value.second != found->second)
- return false;
- }
- return true;
- }
- friend bool operator!=(const bytell_hash_map & lhs, const bytell_hash_map & rhs)
- {
- return !(lhs == rhs);
- }
-
-private:
- struct convertible_to_value
- {
- operator V() const
- {
- return V();
- }
- };
-};
-
-template<typename T, typename H = std::hash<T>, typename E = std::equal_to<T>, typename A = std::allocator<T> >
-class bytell_hash_set
- : public detailv8::sherwood_v8_table
- <
- T,
- T,
- H,
- detailv8::functor_storage<size_t, H>,
- E,
- detailv8::functor_storage<bool, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<unsigned char>,
- detailv8::CalculateBytellBlockSize<T>::value
- >
-{
- using Table = detailv8::sherwood_v8_table
- <
- T,
- T,
- H,
- detailv8::functor_storage<size_t, H>,
- E,
- detailv8::functor_storage<bool, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<unsigned char>,
- detailv8::CalculateBytellBlockSize<T>::value
- >;
-public:
-
- using key_type = T;
-
- using Table::Table;
- bytell_hash_set()
- {
- }
-
- template<typename... Args>
- std::pair<typename Table::iterator, bool> emplace(Args &&... args)
- {
- return Table::emplace(T(std::forward<Args>(args)...));
- }
- std::pair<typename Table::iterator, bool> emplace(const key_type & arg)
- {
- return Table::emplace(arg);
- }
- std::pair<typename Table::iterator, bool> emplace(key_type & arg)
- {
- return Table::emplace(arg);
- }
- std::pair<typename Table::iterator, bool> emplace(const key_type && arg)
- {
- return Table::emplace(std::move(arg));
- }
- std::pair<typename Table::iterator, bool> emplace(key_type && arg)
- {
- return Table::emplace(std::move(arg));
- }
-
- friend bool operator==(const bytell_hash_set & lhs, const bytell_hash_set & rhs)
- {
- if (lhs.size() != rhs.size())
- return false;
- for (const T & value : lhs)
- {
- if (rhs.find(value) == rhs.end())
- return false;
- }
- return true;
- }
- friend bool operator!=(const bytell_hash_set & lhs, const bytell_hash_set & rhs)
- {
- return !(lhs == rhs);
- }
-};
-
-} // end namespace ska
diff --git a/gctest/flat_hash_map/flat_hash_map.hpp b/gctest/flat_hash_map/flat_hash_map.hpp
deleted file mode 100644
index a8723ee..0000000
--- a/gctest/flat_hash_map/flat_hash_map.hpp
+++ /dev/null
@@ -1,1496 +0,0 @@
-// Copyright Malte Skarupke 2017.
-// Distributed under the Boost Software License, Version 1.0.
-// (See http://www.boost.org/LICENSE_1_0.txt)
-
-#pragma once
-
-#include <cstdint>
-#include <cstddef>
-#include <functional>
-#include <cmath>
-#include <algorithm>
-#include <iterator>
-#include <utility>
-#include <type_traits>
-
-#ifdef _MSC_VER
-#define SKA_NOINLINE(...) __declspec(noinline) __VA_ARGS__
-#else
-#define SKA_NOINLINE(...) __VA_ARGS__ __attribute__((noinline))
-#endif
-
-namespace ska
-{
-struct prime_number_hash_policy;
-struct power_of_two_hash_policy;
-struct fibonacci_hash_policy;
-
-namespace detailv3
-{
-template<typename Result, typename Functor>
-struct functor_storage : Functor
-{
- functor_storage() = default;
- functor_storage(const Functor & functor)
- : Functor(functor)
- {
- }
- template<typename... Args>
- Result operator()(Args &&... args)
- {
- return static_cast<Functor &>(*this)(std::forward<Args>(args)...);
- }
- template<typename... Args>
- Result operator()(Args &&... args) const
- {
- return static_cast<const Functor &>(*this)(std::forward<Args>(args)...);
- }
-};
-template<typename Result, typename... Args>
-struct functor_storage<Result, Result (*)(Args...)>
-{
- typedef Result (*function_ptr)(Args...);
- function_ptr function;
- functor_storage(function_ptr function)
- : function(function)
- {
- }
- Result operator()(Args... args) const
- {
- return function(std::forward<Args>(args)...);
- }
- operator function_ptr &()
- {
- return function;
- }
- operator const function_ptr &()
- {
- return function;
- }
-};
-template<typename key_type, typename value_type, typename hasher>
-struct KeyOrValueHasher : functor_storage<size_t, hasher>
-{
- typedef functor_storage<size_t, hasher> hasher_storage;
- KeyOrValueHasher() = default;
- KeyOrValueHasher(const hasher & hash)
- : hasher_storage(hash)
- {
- }
- size_t operator()(const key_type & key)
- {
- return static_cast<hasher_storage &>(*this)(key);
- }
- size_t operator()(const key_type & key) const
- {
- return static_cast<const hasher_storage &>(*this)(key);
- }
- size_t operator()(const value_type & value)
- {
- return static_cast<hasher_storage &>(*this)(value.first);
- }
- size_t operator()(const value_type & value) const
- {
- return static_cast<const hasher_storage &>(*this)(value.first);
- }
- template<typename F, typename S>
- size_t operator()(const std::pair<F, S> & value)
- {
- return static_cast<hasher_storage &>(*this)(value.first);
- }
- template<typename F, typename S>
- size_t operator()(const std::pair<F, S> & value) const
- {
- return static_cast<const hasher_storage &>(*this)(value.first);
- }
-};
-template<typename key_type, typename value_type, typename key_equal>
-struct KeyOrValueEquality : functor_storage<bool, key_equal>
-{
- typedef functor_storage<bool, key_equal> equality_storage;
- KeyOrValueEquality() = default;
- KeyOrValueEquality(const key_equal & equality)
- : equality_storage(equality)
- {
- }
- bool operator()(const key_type & lhs, const key_type & rhs)
- {
- return static_cast<equality_storage &>(*this)(lhs, rhs);
- }
- bool operator()(const key_type & lhs, const value_type & rhs)
- {
- return static_cast<equality_storage &>(*this)(lhs, rhs.first);
- }
- bool operator()(const value_type & lhs, const key_type & rhs)
- {
- return static_cast<equality_storage &>(*this)(lhs.first, rhs);
- }
- bool operator()(const value_type & lhs, const value_type & rhs)
- {
- return static_cast<equality_storage &>(*this)(lhs.first, rhs.first);
- }
- template<typename F, typename S>
- bool operator()(const key_type & lhs, const std::pair<F, S> & rhs)
- {
- return static_cast<equality_storage &>(*this)(lhs, rhs.first);
- }
- template<typename F, typename S>
- bool operator()(const std::pair<F, S> & lhs, const key_type & rhs)
- {
- return static_cast<equality_storage &>(*this)(lhs.first, rhs);
- }
- template<typename F, typename S>
- bool operator()(const value_type & lhs, const std::pair<F, S> & rhs)
- {
- return static_cast<equality_storage &>(*this)(lhs.first, rhs.first);
- }
- template<typename F, typename S>
- bool operator()(const std::pair<F, S> & lhs, const value_type & rhs)
- {
- return static_cast<equality_storage &>(*this)(lhs.first, rhs.first);
- }
- template<typename FL, typename SL, typename FR, typename SR>
- bool operator()(const std::pair<FL, SL> & lhs, const std::pair<FR, SR> & rhs)
- {
- return static_cast<equality_storage &>(*this)(lhs.first, rhs.first);
- }
-};
-static constexpr int8_t min_lookups = 4;
-template<typename T>
-struct sherwood_v3_entry
-{
- sherwood_v3_entry()
- {
- }
- sherwood_v3_entry(int8_t distance_from_desired)
- : distance_from_desired(distance_from_desired)
- {
- }
- ~sherwood_v3_entry()
- {
- }
- static sherwood_v3_entry * empty_default_table()
- {
- static sherwood_v3_entry result[min_lookups] = { {}, {}, {}, {special_end_value} };
- return result;
- }
-
- bool has_value() const
- {
- return distance_from_desired >= 0;
- }
- bool is_empty() const
- {
- return distance_from_desired < 0;
- }
- bool is_at_desired_position() const
- {
- return distance_from_desired <= 0;
- }
- template<typename... Args>
- void emplace(int8_t distance, Args &&... args)
- {
- new (std::addressof(value)) T(std::forward<Args>(args)...);
- distance_from_desired = distance;
- }
-
- void destroy_value()
- {
- value.~T();
- distance_from_desired = -1;
- }
-
- int8_t distance_from_desired = -1;
- static constexpr int8_t special_end_value = 0;
- union { T value; };
-};
-
-inline int8_t log2(size_t value)
-{
- static constexpr int8_t table[64] =
- {
- 63, 0, 58, 1, 59, 47, 53, 2,
- 60, 39, 48, 27, 54, 33, 42, 3,
- 61, 51, 37, 40, 49, 18, 28, 20,
- 55, 30, 34, 11, 43, 14, 22, 4,
- 62, 57, 46, 52, 38, 26, 32, 41,
- 50, 36, 17, 19, 29, 10, 13, 21,
- 56, 45, 25, 31, 35, 16, 9, 12,
- 44, 24, 15, 8, 23, 7, 6, 5
- };
- value |= value >> 1;
- value |= value >> 2;
- value |= value >> 4;
- value |= value >> 8;
- value |= value >> 16;
- value |= value >> 32;
- return table[((value - (value >> 1)) * 0x07EDD5E59A4E28C2) >> 58];
-}
-
-template<typename T, bool>
-struct AssignIfTrue
-{
- void operator()(T & lhs, const T & rhs)
- {
- lhs = rhs;
- }
- void operator()(T & lhs, T && rhs)
- {
- lhs = std::move(rhs);
- }
-};
-template<typename T>
-struct AssignIfTrue<T, false>
-{
- void operator()(T &, const T &)
- {
- }
- void operator()(T &, T &&)
- {
- }
-};
-
-inline size_t next_power_of_two(size_t i)
-{
- --i;
- i |= i >> 1;
- i |= i >> 2;
- i |= i >> 4;
- i |= i >> 8;
- i |= i >> 16;
- i |= i >> 32;
- ++i;
- return i;
-}
-
-template<typename...> using void_t = void;
-
-template<typename T, typename = void>
-struct HashPolicySelector
-{
- typedef fibonacci_hash_policy type;
-};
-template<typename T>
-struct HashPolicySelector<T, void_t<typename T::hash_policy>>
-{
- typedef typename T::hash_policy type;
-};
-
-template<typename T, typename FindKey, typename ArgumentHash, typename Hasher, typename ArgumentEqual, typename Equal, typename ArgumentAlloc, typename EntryAlloc>
-class sherwood_v3_table : private EntryAlloc, private Hasher, private Equal
-{
- using Entry = detailv3::sherwood_v3_entry<T>;
- using AllocatorTraits = std::allocator_traits<EntryAlloc>;
- using EntryPointer = typename AllocatorTraits::pointer;
- struct convertible_to_iterator;
-
-public:
-
- using value_type = T;
- using size_type = size_t;
- using difference_type = std::ptrdiff_t;
- using hasher = ArgumentHash;
- using key_equal = ArgumentEqual;
- using allocator_type = EntryAlloc;
- using reference = value_type &;
- using const_reference = const value_type &;
- using pointer = value_type *;
- using const_pointer = const value_type *;
-
- sherwood_v3_table()
- {
- }
- explicit sherwood_v3_table(size_type bucket_count, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
- : EntryAlloc(alloc), Hasher(hash), Equal(equal)
- {
- rehash(bucket_count);
- }
- sherwood_v3_table(size_type bucket_count, const ArgumentAlloc & alloc)
- : sherwood_v3_table(bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
- {
- }
- sherwood_v3_table(size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
- : sherwood_v3_table(bucket_count, hash, ArgumentEqual(), alloc)
- {
- }
- explicit sherwood_v3_table(const ArgumentAlloc & alloc)
- : EntryAlloc(alloc)
- {
- }
- template<typename It>
- sherwood_v3_table(It first, It last, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
- : sherwood_v3_table(bucket_count, hash, equal, alloc)
- {
- insert(first, last);
- }
- template<typename It>
- sherwood_v3_table(It first, It last, size_type bucket_count, const ArgumentAlloc & alloc)
- : sherwood_v3_table(first, last, bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
- {
- }
- template<typename It>
- sherwood_v3_table(It first, It last, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
- : sherwood_v3_table(first, last, bucket_count, hash, ArgumentEqual(), alloc)
- {
- }
- sherwood_v3_table(std::initializer_list<T> il, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
- : sherwood_v3_table(bucket_count, hash, equal, alloc)
- {
- if (bucket_count == 0)
- rehash(il.size());
- insert(il.begin(), il.end());
- }
- sherwood_v3_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentAlloc & alloc)
- : sherwood_v3_table(il, bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
- {
- }
- sherwood_v3_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
- : sherwood_v3_table(il, bucket_count, hash, ArgumentEqual(), alloc)
- {
- }
- sherwood_v3_table(const sherwood_v3_table & other)
- : sherwood_v3_table(other, AllocatorTraits::select_on_container_copy_construction(other.get_allocator()))
- {
- }
- sherwood_v3_table(const sherwood_v3_table & other, const ArgumentAlloc & alloc)
- : EntryAlloc(alloc), Hasher(other), Equal(other), _max_load_factor(other._max_load_factor)
- {
- rehash_for_other_container(other);
- try
- {
- insert(other.begin(), other.end());
- }
- catch(...)
- {
- clear();
- deallocate_data(entries, num_slots_minus_one, max_lookups);
- throw;
- }
- }
- sherwood_v3_table(sherwood_v3_table && other) noexcept
- : EntryAlloc(std::move(other)), Hasher(std::move(other)), Equal(std::move(other))
- {
- swap_pointers(other);
- }
- sherwood_v3_table(sherwood_v3_table && other, const ArgumentAlloc & alloc) noexcept
- : EntryAlloc(alloc), Hasher(std::move(other)), Equal(std::move(other))
- {
- swap_pointers(other);
- }
- sherwood_v3_table & operator=(const sherwood_v3_table & other)
- {
- if (this == std::addressof(other))
- return *this;
-
- clear();
- if (AllocatorTraits::propagate_on_container_copy_assignment::value)
- {
- if (static_cast<EntryAlloc &>(*this) != static_cast<const EntryAlloc &>(other))
- {
- reset_to_empty_state();
- }
- AssignIfTrue<EntryAlloc, AllocatorTraits::propagate_on_container_copy_assignment::value>()(*this, other);
- }
- _max_load_factor = other._max_load_factor;
- static_cast<Hasher &>(*this) = other;
- static_cast<Equal &>(*this) = other;
- rehash_for_other_container(other);
- insert(other.begin(), other.end());
- return *this;
- }
- sherwood_v3_table & operator=(sherwood_v3_table && other) noexcept
- {
- if (this == std::addressof(other))
- return *this;
- else if (AllocatorTraits::propagate_on_container_move_assignment::value)
- {
- clear();
- reset_to_empty_state();
- AssignIfTrue<EntryAlloc, AllocatorTraits::propagate_on_container_move_assignment::value>()(*this, std::move(other));
- swap_pointers(other);
- }
- else if (static_cast<EntryAlloc &>(*this) == static_cast<EntryAlloc &>(other))
- {
- swap_pointers(other);
- }
- else
- {
- clear();
- _max_load_factor = other._max_load_factor;
- rehash_for_other_container(other);
- for (T & elem : other)
- emplace(std::move(elem));
- other.clear();
- }
- static_cast<Hasher &>(*this) = std::move(other);
- static_cast<Equal &>(*this) = std::move(other);
- return *this;
- }
- ~sherwood_v3_table()
- {
- clear();
- deallocate_data(entries, num_slots_minus_one, max_lookups);
- }
-
- const allocator_type & get_allocator() const
- {
- return static_cast<const allocator_type &>(*this);
- }
- const ArgumentEqual & key_eq() const
- {
- return static_cast<const ArgumentEqual &>(*this);
- }
- const ArgumentHash & hash_function() const
- {
- return static_cast<const ArgumentHash &>(*this);
- }
-
- template<typename ValueType>
- struct templated_iterator
- {
- templated_iterator() = default;
- templated_iterator(EntryPointer current)
- : current(current)
- {
- }
- EntryPointer current = EntryPointer();
-
- using iterator_category = std::forward_iterator_tag;
- using value_type = ValueType;
- using difference_type = ptrdiff_t;
- using pointer = ValueType *;
- using reference = ValueType &;
-
- friend bool operator==(const templated_iterator & lhs, const templated_iterator & rhs)
- {
- return lhs.current == rhs.current;
- }
- friend bool operator!=(const templated_iterator & lhs, const templated_iterator & rhs)
- {
- return !(lhs == rhs);
- }
-
- templated_iterator & operator++()
- {
- do
- {
- ++current;
- }
- while(current->is_empty());
- return *this;
- }
- templated_iterator operator++(int)
- {
- templated_iterator copy(*this);
- ++*this;
- return copy;
- }
-
- ValueType & operator*() const
- {
- return current->value;
- }
- ValueType * operator->() const
- {
- return std::addressof(current->value);
- }
-
- operator templated_iterator<const value_type>() const
- {
- return { current };
- }
- };
- using iterator = templated_iterator<value_type>;
- using const_iterator = templated_iterator<const value_type>;
-
- iterator begin()
- {
- for (EntryPointer it = entries;; ++it)
- {
- if (it->has_value())
- return { it };
- }
- }
- const_iterator begin() const
- {
- for (EntryPointer it = entries;; ++it)
- {
- if (it->has_value())
- return { it };
- }
- }
- const_iterator cbegin() const
- {
- return begin();
- }
- iterator end()
- {
- return { entries + static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups) };
- }
- const_iterator end() const
- {
- return { entries + static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups) };
- }
- const_iterator cend() const
- {
- return end();
- }
-
- iterator find(const FindKey & key)
- {
- size_t index = hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
- EntryPointer it = entries + ptrdiff_t(index);
- for (int8_t distance = 0; it->distance_from_desired >= distance; ++distance, ++it)
- {
- if (compares_equal(key, it->value))
- return { it };
- }
- return end();
- }
- const_iterator find(const FindKey & key) const
- {
- return const_cast<sherwood_v3_table *>(this)->find(key);
- }
- size_t count(const FindKey & key) const
- {
- return find(key) == end() ? 0 : 1;
- }
- std::pair<iterator, iterator> equal_range(const FindKey & key)
- {
- iterator found = find(key);
- if (found == end())
- return { found, found };
- else
- return { found, std::next(found) };
- }
- std::pair<const_iterator, const_iterator> equal_range(const FindKey & key) const
- {
- const_iterator found = find(key);
- if (found == end())
- return { found, found };
- else
- return { found, std::next(found) };
- }
-
- template<typename Key, typename... Args>
- std::pair<iterator, bool> emplace(Key && key, Args &&... args)
- {
- size_t index = hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
- EntryPointer current_entry = entries + ptrdiff_t(index);
- int8_t distance_from_desired = 0;
- for (; current_entry->distance_from_desired >= distance_from_desired; ++current_entry, ++distance_from_desired)
- {
- if (compares_equal(key, current_entry->value))
- return { { current_entry }, false };
- }
- return emplace_new_key(distance_from_desired, current_entry, std::forward<Key>(key), std::forward<Args>(args)...);
- }
-
- std::pair<iterator, bool> insert(const value_type & value)
- {
- return emplace(value);
- }
- std::pair<iterator, bool> insert(value_type && value)
- {
- return emplace(std::move(value));
- }
- template<typename... Args>
- iterator emplace_hint(const_iterator, Args &&... args)
- {
- return emplace(std::forward<Args>(args)...).first;
- }
- iterator insert(const_iterator, const value_type & value)
- {
- return emplace(value).first;
- }
- iterator insert(const_iterator, value_type && value)
- {
- return emplace(std::move(value)).first;
- }
-
- template<typename It>
- void insert(It begin, It end)
- {
- for (; begin != end; ++begin)
- {
- emplace(*begin);
- }
- }
- void insert(std::initializer_list<value_type> il)
- {
- insert(il.begin(), il.end());
- }
-
- void rehash(size_t num_buckets)
- {
- num_buckets = std::max(num_buckets, static_cast<size_t>(std::ceil(num_elements / static_cast<double>(_max_load_factor))));
- if (num_buckets == 0)
- {
- reset_to_empty_state();
- return;
- }
- auto new_prime_index = hash_policy.next_size_over(num_buckets);
- if (num_buckets == bucket_count())
- return;
- int8_t new_max_lookups = compute_max_lookups(num_buckets);
- EntryPointer new_buckets(AllocatorTraits::allocate(*this, num_buckets + new_max_lookups));
- EntryPointer special_end_item = new_buckets + static_cast<ptrdiff_t>(num_buckets + new_max_lookups - 1);
- for (EntryPointer it = new_buckets; it != special_end_item; ++it)
- it->distance_from_desired = -1;
- special_end_item->distance_from_desired = Entry::special_end_value;
- std::swap(entries, new_buckets);
- std::swap(num_slots_minus_one, num_buckets);
- --num_slots_minus_one;
- hash_policy.commit(new_prime_index);
- int8_t old_max_lookups = max_lookups;
- max_lookups = new_max_lookups;
- num_elements = 0;
- for (EntryPointer it = new_buckets, end = it + static_cast<ptrdiff_t>(num_buckets + old_max_lookups); it != end; ++it)
- {
- if (it->has_value())
- {
- emplace(std::move(it->value));
- it->destroy_value();
- }
- }
- deallocate_data(new_buckets, num_buckets, old_max_lookups);
- }
-
- void reserve(size_t num_elements)
- {
- size_t required_buckets = num_buckets_for_reserve(num_elements);
- if (required_buckets > bucket_count())
- rehash(required_buckets);
- }
-
- // the return value is a type that can be converted to an iterator
- // the reason for doing this is that it's not free to find the
- // iterator pointing at the next element. if you care about the
- // next iterator, turn the return value into an iterator
- convertible_to_iterator erase(const_iterator to_erase)
- {
- EntryPointer current = to_erase.current;
- current->destroy_value();
- --num_elements;
- for (EntryPointer next = current + ptrdiff_t(1); !next->is_at_desired_position(); ++current, ++next)
- {
- current->emplace(next->distance_from_desired - 1, std::move(next->value));
- next->destroy_value();
- }
- return { to_erase.current };
- }
-
- iterator erase(const_iterator begin_it, const_iterator end_it)
- {
- if (begin_it == end_it)
- return { begin_it.current };
- for (EntryPointer it = begin_it.current, end = end_it.current; it != end; ++it)
- {
- if (it->has_value())
- {
- it->destroy_value();
- --num_elements;
- }
- }
- if (end_it == this->end())
- return this->end();
- ptrdiff_t num_to_move = std::min(static_cast<ptrdiff_t>(end_it.current->distance_from_desired), end_it.current - begin_it.current);
- EntryPointer to_return = end_it.current - num_to_move;
- for (EntryPointer it = end_it.current; !it->is_at_desired_position();)
- {
- EntryPointer target = it - num_to_move;
- target->emplace(it->distance_from_desired - num_to_move, std::move(it->value));
- it->destroy_value();
- ++it;
- num_to_move = std::min(static_cast<ptrdiff_t>(it->distance_from_desired), num_to_move);
- }
- return { to_return };
- }
-
- size_t erase(const FindKey & key)
- {
- auto found = find(key);
- if (found == end())
- return 0;
- else
- {
- erase(found);
- return 1;
- }
- }
-
- void clear()
- {
- for (EntryPointer it = entries, end = it + static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups); it != end; ++it)
- {
- if (it->has_value())
- it->destroy_value();
- }
- num_elements = 0;
- }
-
- void shrink_to_fit()
- {
- rehash_for_other_container(*this);
- }
-
- void swap(sherwood_v3_table & other)
- {
- using std::swap;
- swap_pointers(other);
- swap(static_cast<ArgumentHash &>(*this), static_cast<ArgumentHash &>(other));
- swap(static_cast<ArgumentEqual &>(*this), static_cast<ArgumentEqual &>(other));
- if (AllocatorTraits::propagate_on_container_swap::value)
- swap(static_cast<EntryAlloc &>(*this), static_cast<EntryAlloc &>(other));
- }
-
- size_t size() const
- {
- return num_elements;
- }
- size_t max_size() const
- {
- return (AllocatorTraits::max_size(*this)) / sizeof(Entry);
- }
- size_t bucket_count() const
- {
- return num_slots_minus_one ? num_slots_minus_one + 1 : 0;
- }
- size_type max_bucket_count() const
- {
- return (AllocatorTraits::max_size(*this) - min_lookups) / sizeof(Entry);
- }
- size_t bucket(const FindKey & key) const
- {
- return hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
- }
- float load_factor() const
- {
- size_t buckets = bucket_count();
- if (buckets)
- return static_cast<float>(num_elements) / bucket_count();
- else
- return 0;
- }
- void max_load_factor(float value)
- {
- _max_load_factor = value;
- }
- float max_load_factor() const
- {
- return _max_load_factor;
- }
-
- bool empty() const
- {
- return num_elements == 0;
- }
-
-private:
- EntryPointer entries = Entry::empty_default_table();
- size_t num_slots_minus_one = 0;
- typename HashPolicySelector<ArgumentHash>::type hash_policy;
- int8_t max_lookups = detailv3::min_lookups - 1;
- float _max_load_factor = 0.5f;
- size_t num_elements = 0;
-
- static int8_t compute_max_lookups(size_t num_buckets)
- {
- int8_t desired = detailv3::log2(num_buckets);
- return std::max(detailv3::min_lookups, desired);
- }
-
- size_t num_buckets_for_reserve(size_t num_elements) const
- {
- return static_cast<size_t>(std::ceil(num_elements / std::min(0.5, static_cast<double>(_max_load_factor))));
- }
- void rehash_for_other_container(const sherwood_v3_table & other)
- {
- rehash(std::min(num_buckets_for_reserve(other.size()), other.bucket_count()));
- }
-
- void swap_pointers(sherwood_v3_table & other)
- {
- using std::swap;
- swap(hash_policy, other.hash_policy);
- swap(entries, other.entries);
- swap(num_slots_minus_one, other.num_slots_minus_one);
- swap(num_elements, other.num_elements);
- swap(max_lookups, other.max_lookups);
- swap(_max_load_factor, other._max_load_factor);
- }
-
- template<typename Key, typename... Args>
- SKA_NOINLINE(std::pair<iterator, bool>) emplace_new_key(int8_t distance_from_desired, EntryPointer current_entry, Key && key, Args &&... args)
- {
- using std::swap;
- if (num_slots_minus_one == 0 || distance_from_desired == max_lookups || num_elements + 1 > (num_slots_minus_one + 1) * static_cast<double>(_max_load_factor))
- {
- grow();
- return emplace(std::forward<Key>(key), std::forward<Args>(args)...);
- }
- else if (current_entry->is_empty())
- {
- current_entry->emplace(distance_from_desired, std::forward<Key>(key), std::forward<Args>(args)...);
- ++num_elements;
- return { { current_entry }, true };
- }
- value_type to_insert(std::forward<Key>(key), std::forward<Args>(args)...);
- swap(distance_from_desired, current_entry->distance_from_desired);
- swap(to_insert, current_entry->value);
- iterator result = { current_entry };
- for (++distance_from_desired, ++current_entry;; ++current_entry)
- {
- if (current_entry->is_empty())
- {
- current_entry->emplace(distance_from_desired, std::move(to_insert));
- ++num_elements;
- return { result, true };
- }
- else if (current_entry->distance_from_desired < distance_from_desired)
- {
- swap(distance_from_desired, current_entry->distance_from_desired);
- swap(to_insert, current_entry->value);
- ++distance_from_desired;
- }
- else
- {
- ++distance_from_desired;
- if (distance_from_desired == max_lookups)
- {
- swap(to_insert, result.current->value);
- grow();
- return emplace(std::move(to_insert));
- }
- }
- }
- }
-
- void grow()
- {
- rehash(std::max(size_t(4), 2 * bucket_count()));
- }
-
- void deallocate_data(EntryPointer begin, size_t num_slots_minus_one, int8_t max_lookups)
- {
- if (begin != Entry::empty_default_table())
- {
- AllocatorTraits::deallocate(*this, begin, num_slots_minus_one + max_lookups + 1);
- }
- }
-
- void reset_to_empty_state()
- {
- deallocate_data(entries, num_slots_minus_one, max_lookups);
- entries = Entry::empty_default_table();
- num_slots_minus_one = 0;
- hash_policy.reset();
- max_lookups = detailv3::min_lookups - 1;
- }
-
- template<typename U>
- size_t hash_object(const U & key)
- {
- return static_cast<Hasher &>(*this)(key);
- }
- template<typename U>
- size_t hash_object(const U & key) const
- {
- return static_cast<const Hasher &>(*this)(key);
- }
- template<typename L, typename R>
- bool compares_equal(const L & lhs, const R & rhs)
- {
- return static_cast<Equal &>(*this)(lhs, rhs);
- }
-
- struct convertible_to_iterator
- {
- EntryPointer it;
-
- operator iterator()
- {
- if (it->has_value())
- return { it };
- else
- return ++iterator{it};
- }
- operator const_iterator()
- {
- if (it->has_value())
- return { it };
- else
- return ++const_iterator{it};
- }
- };
-
-};
-}
-
-struct prime_number_hash_policy
-{
- static size_t mod0(size_t) { return 0llu; }
- static size_t mod2(size_t hash) { return hash % 2llu; }
- static size_t mod3(size_t hash) { return hash % 3llu; }
- static size_t mod5(size_t hash) { return hash % 5llu; }
- static size_t mod7(size_t hash) { return hash % 7llu; }
- static size_t mod11(size_t hash) { return hash % 11llu; }
- static size_t mod13(size_t hash) { return hash % 13llu; }
- static size_t mod17(size_t hash) { return hash % 17llu; }
- static size_t mod23(size_t hash) { return hash % 23llu; }
- static size_t mod29(size_t hash) { return hash % 29llu; }
- static size_t mod37(size_t hash) { return hash % 37llu; }
- static size_t mod47(size_t hash) { return hash % 47llu; }
- static size_t mod59(size_t hash) { return hash % 59llu; }
- static size_t mod73(size_t hash) { return hash % 73llu; }
- static size_t mod97(size_t hash) { return hash % 97llu; }
- static size_t mod127(size_t hash) { return hash % 127llu; }
- static size_t mod151(size_t hash) { return hash % 151llu; }
- static size_t mod197(size_t hash) { return hash % 197llu; }
- static size_t mod251(size_t hash) { return hash % 251llu; }
- static size_t mod313(size_t hash) { return hash % 313llu; }
- static size_t mod397(size_t hash) { return hash % 397llu; }
- static size_t mod499(size_t hash) { return hash % 499llu; }
- static size_t mod631(size_t hash) { return hash % 631llu; }
- static size_t mod797(size_t hash) { return hash % 797llu; }
- static size_t mod1009(size_t hash) { return hash % 1009llu; }
- static size_t mod1259(size_t hash) { return hash % 1259llu; }
- static size_t mod1597(size_t hash) { return hash % 1597llu; }
- static size_t mod2011(size_t hash) { return hash % 2011llu; }
- static size_t mod2539(size_t hash) { return hash % 2539llu; }
- static size_t mod3203(size_t hash) { return hash % 3203llu; }
- static size_t mod4027(size_t hash) { return hash % 4027llu; }
- static size_t mod5087(size_t hash) { return hash % 5087llu; }
- static size_t mod6421(size_t hash) { return hash % 6421llu; }
- static size_t mod8089(size_t hash) { return hash % 8089llu; }
- static size_t mod10193(size_t hash) { return hash % 10193llu; }
- static size_t mod12853(size_t hash) { return hash % 12853llu; }
- static size_t mod16193(size_t hash) { return hash % 16193llu; }
- static size_t mod20399(size_t hash) { return hash % 20399llu; }
- static size_t mod25717(size_t hash) { return hash % 25717llu; }
- static size_t mod32401(size_t hash) { return hash % 32401llu; }
- static size_t mod40823(size_t hash) { return hash % 40823llu; }
- static size_t mod51437(size_t hash) { return hash % 51437llu; }
- static size_t mod64811(size_t hash) { return hash % 64811llu; }
- static size_t mod81649(size_t hash) { return hash % 81649llu; }
- static size_t mod102877(size_t hash) { return hash % 102877llu; }
- static size_t mod129607(size_t hash) { return hash % 129607llu; }
- static size_t mod163307(size_t hash) { return hash % 163307llu; }
- static size_t mod205759(size_t hash) { return hash % 205759llu; }
- static size_t mod259229(size_t hash) { return hash % 259229llu; }
- static size_t mod326617(size_t hash) { return hash % 326617llu; }
- static size_t mod411527(size_t hash) { return hash % 411527llu; }
- static size_t mod518509(size_t hash) { return hash % 518509llu; }
- static size_t mod653267(size_t hash) { return hash % 653267llu; }
- static size_t mod823117(size_t hash) { return hash % 823117llu; }
- static size_t mod1037059(size_t hash) { return hash % 1037059llu; }
- static size_t mod1306601(size_t hash) { return hash % 1306601llu; }
- static size_t mod1646237(size_t hash) { return hash % 1646237llu; }
- static size_t mod2074129(size_t hash) { return hash % 2074129llu; }
- static size_t mod2613229(size_t hash) { return hash % 2613229llu; }
- static size_t mod3292489(size_t hash) { return hash % 3292489llu; }
- static size_t mod4148279(size_t hash) { return hash % 4148279llu; }
- static size_t mod5226491(size_t hash) { return hash % 5226491llu; }
- static size_t mod6584983(size_t hash) { return hash % 6584983llu; }
- static size_t mod8296553(size_t hash) { return hash % 8296553llu; }
- static size_t mod10453007(size_t hash) { return hash % 10453007llu; }
- static size_t mod13169977(size_t hash) { return hash % 13169977llu; }
- static size_t mod16593127(size_t hash) { return hash % 16593127llu; }
- static size_t mod20906033(size_t hash) { return hash % 20906033llu; }
- static size_t mod26339969(size_t hash) { return hash % 26339969llu; }
- static size_t mod33186281(size_t hash) { return hash % 33186281llu; }
- static size_t mod41812097(size_t hash) { return hash % 41812097llu; }
- static size_t mod52679969(size_t hash) { return hash % 52679969llu; }
- static size_t mod66372617(size_t hash) { return hash % 66372617llu; }
- static size_t mod83624237(size_t hash) { return hash % 83624237llu; }
- static size_t mod105359939(size_t hash) { return hash % 105359939llu; }
- static size_t mod132745199(size_t hash) { return hash % 132745199llu; }
- static size_t mod167248483(size_t hash) { return hash % 167248483llu; }
- static size_t mod210719881(size_t hash) { return hash % 210719881llu; }
- static size_t mod265490441(size_t hash) { return hash % 265490441llu; }
- static size_t mod334496971(size_t hash) { return hash % 334496971llu; }
- static size_t mod421439783(size_t hash) { return hash % 421439783llu; }
- static size_t mod530980861(size_t hash) { return hash % 530980861llu; }
- static size_t mod668993977(size_t hash) { return hash % 668993977llu; }
- static size_t mod842879579(size_t hash) { return hash % 842879579llu; }
- static size_t mod1061961721(size_t hash) { return hash % 1061961721llu; }
- static size_t mod1337987929(size_t hash) { return hash % 1337987929llu; }
- static size_t mod1685759167(size_t hash) { return hash % 1685759167llu; }
- static size_t mod2123923447(size_t hash) { return hash % 2123923447llu; }
- static size_t mod2675975881(size_t hash) { return hash % 2675975881llu; }
- static size_t mod3371518343(size_t hash) { return hash % 3371518343llu; }
- static size_t mod4247846927(size_t hash) { return hash % 4247846927llu; }
- static size_t mod5351951779(size_t hash) { return hash % 5351951779llu; }
- static size_t mod6743036717(size_t hash) { return hash % 6743036717llu; }
- static size_t mod8495693897(size_t hash) { return hash % 8495693897llu; }
- static size_t mod10703903591(size_t hash) { return hash % 10703903591llu; }
- static size_t mod13486073473(size_t hash) { return hash % 13486073473llu; }
- static size_t mod16991387857(size_t hash) { return hash % 16991387857llu; }
- static size_t mod21407807219(size_t hash) { return hash % 21407807219llu; }
- static size_t mod26972146961(size_t hash) { return hash % 26972146961llu; }
- static size_t mod33982775741(size_t hash) { return hash % 33982775741llu; }
- static size_t mod42815614441(size_t hash) { return hash % 42815614441llu; }
- static size_t mod53944293929(size_t hash) { return hash % 53944293929llu; }
- static size_t mod67965551447(size_t hash) { return hash % 67965551447llu; }
- static size_t mod85631228929(size_t hash) { return hash % 85631228929llu; }
- static size_t mod107888587883(size_t hash) { return hash % 107888587883llu; }
- static size_t mod135931102921(size_t hash) { return hash % 135931102921llu; }
- static size_t mod171262457903(size_t hash) { return hash % 171262457903llu; }
- static size_t mod215777175787(size_t hash) { return hash % 215777175787llu; }
- static size_t mod271862205833(size_t hash) { return hash % 271862205833llu; }
- static size_t mod342524915839(size_t hash) { return hash % 342524915839llu; }
- static size_t mod431554351609(size_t hash) { return hash % 431554351609llu; }
- static size_t mod543724411781(size_t hash) { return hash % 543724411781llu; }
- static size_t mod685049831731(size_t hash) { return hash % 685049831731llu; }
- static size_t mod863108703229(size_t hash) { return hash % 863108703229llu; }
- static size_t mod1087448823553(size_t hash) { return hash % 1087448823553llu; }
- static size_t mod1370099663459(size_t hash) { return hash % 1370099663459llu; }
- static size_t mod1726217406467(size_t hash) { return hash % 1726217406467llu; }
- static size_t mod2174897647073(size_t hash) { return hash % 2174897647073llu; }
- static size_t mod2740199326961(size_t hash) { return hash % 2740199326961llu; }
- static size_t mod3452434812973(size_t hash) { return hash % 3452434812973llu; }
- static size_t mod4349795294267(size_t hash) { return hash % 4349795294267llu; }
- static size_t mod5480398654009(size_t hash) { return hash % 5480398654009llu; }
- static size_t mod6904869625999(size_t hash) { return hash % 6904869625999llu; }
- static size_t mod8699590588571(size_t hash) { return hash % 8699590588571llu; }
- static size_t mod10960797308051(size_t hash) { return hash % 10960797308051llu; }
- static size_t mod13809739252051(size_t hash) { return hash % 13809739252051llu; }
- static size_t mod17399181177241(size_t hash) { return hash % 17399181177241llu; }
- static size_t mod21921594616111(size_t hash) { return hash % 21921594616111llu; }
- static size_t mod27619478504183(size_t hash) { return hash % 27619478504183llu; }
- static size_t mod34798362354533(size_t hash) { return hash % 34798362354533llu; }
- static size_t mod43843189232363(size_t hash) { return hash % 43843189232363llu; }
- static size_t mod55238957008387(size_t hash) { return hash % 55238957008387llu; }
- static size_t mod69596724709081(size_t hash) { return hash % 69596724709081llu; }
- static size_t mod87686378464759(size_t hash) { return hash % 87686378464759llu; }
- static size_t mod110477914016779(size_t hash) { return hash % 110477914016779llu; }
- static size_t mod139193449418173(size_t hash) { return hash % 139193449418173llu; }
- static size_t mod175372756929481(size_t hash) { return hash % 175372756929481llu; }
- static size_t mod220955828033581(size_t hash) { return hash % 220955828033581llu; }
- static size_t mod278386898836457(size_t hash) { return hash % 278386898836457llu; }
- static size_t mod350745513859007(size_t hash) { return hash % 350745513859007llu; }
- static size_t mod441911656067171(size_t hash) { return hash % 441911656067171llu; }
- static size_t mod556773797672909(size_t hash) { return hash % 556773797672909llu; }
- static size_t mod701491027718027(size_t hash) { return hash % 701491027718027llu; }
- static size_t mod883823312134381(size_t hash) { return hash % 883823312134381llu; }
- static size_t mod1113547595345903(size_t hash) { return hash % 1113547595345903llu; }
- static size_t mod1402982055436147(size_t hash) { return hash % 1402982055436147llu; }
- static size_t mod1767646624268779(size_t hash) { return hash % 1767646624268779llu; }
- static size_t mod2227095190691797(size_t hash) { return hash % 2227095190691797llu; }
- static size_t mod2805964110872297(size_t hash) { return hash % 2805964110872297llu; }
- static size_t mod3535293248537579(size_t hash) { return hash % 3535293248537579llu; }
- static size_t mod4454190381383713(size_t hash) { return hash % 4454190381383713llu; }
- static size_t mod5611928221744609(size_t hash) { return hash % 5611928221744609llu; }
- static size_t mod7070586497075177(size_t hash) { return hash % 7070586497075177llu; }
- static size_t mod8908380762767489(size_t hash) { return hash % 8908380762767489llu; }
- static size_t mod11223856443489329(size_t hash) { return hash % 11223856443489329llu; }
- static size_t mod14141172994150357(size_t hash) { return hash % 14141172994150357llu; }
- static size_t mod17816761525534927(size_t hash) { return hash % 17816761525534927llu; }
- static size_t mod22447712886978529(size_t hash) { return hash % 22447712886978529llu; }
- static size_t mod28282345988300791(size_t hash) { return hash % 28282345988300791llu; }
- static size_t mod35633523051069991(size_t hash) { return hash % 35633523051069991llu; }
- static size_t mod44895425773957261(size_t hash) { return hash % 44895425773957261llu; }
- static size_t mod56564691976601587(size_t hash) { return hash % 56564691976601587llu; }
- static size_t mod71267046102139967(size_t hash) { return hash % 71267046102139967llu; }
- static size_t mod89790851547914507(size_t hash) { return hash % 89790851547914507llu; }
- static size_t mod113129383953203213(size_t hash) { return hash % 113129383953203213llu; }
- static size_t mod142534092204280003(size_t hash) { return hash % 142534092204280003llu; }
- static size_t mod179581703095829107(size_t hash) { return hash % 179581703095829107llu; }
- static size_t mod226258767906406483(size_t hash) { return hash % 226258767906406483llu; }
- static size_t mod285068184408560057(size_t hash) { return hash % 285068184408560057llu; }
- static size_t mod359163406191658253(size_t hash) { return hash % 359163406191658253llu; }
- static size_t mod452517535812813007(size_t hash) { return hash % 452517535812813007llu; }
- static size_t mod570136368817120201(size_t hash) { return hash % 570136368817120201llu; }
- static size_t mod718326812383316683(size_t hash) { return hash % 718326812383316683llu; }
- static size_t mod905035071625626043(size_t hash) { return hash % 905035071625626043llu; }
- static size_t mod1140272737634240411(size_t hash) { return hash % 1140272737634240411llu; }
- static size_t mod1436653624766633509(size_t hash) { return hash % 1436653624766633509llu; }
- static size_t mod1810070143251252131(size_t hash) { return hash % 1810070143251252131llu; }
- static size_t mod2280545475268481167(size_t hash) { return hash % 2280545475268481167llu; }
- static size_t mod2873307249533267101(size_t hash) { return hash % 2873307249533267101llu; }
- static size_t mod3620140286502504283(size_t hash) { return hash % 3620140286502504283llu; }
- static size_t mod4561090950536962147(size_t hash) { return hash % 4561090950536962147llu; }
- static size_t mod5746614499066534157(size_t hash) { return hash % 5746614499066534157llu; }
- static size_t mod7240280573005008577(size_t hash) { return hash % 7240280573005008577llu; }
- static size_t mod9122181901073924329(size_t hash) { return hash % 9122181901073924329llu; }
- static size_t mod11493228998133068689(size_t hash) { return hash % 11493228998133068689llu; }
- static size_t mod14480561146010017169(size_t hash) { return hash % 14480561146010017169llu; }
- static size_t mod18446744073709551557(size_t hash) { return hash % 18446744073709551557llu; }
-
- using mod_function = size_t (*)(size_t);
-
- mod_function next_size_over(size_t & size) const
- {
- // prime numbers generated by the following method:
- // 1. start with a prime p = 2
- // 2. go to wolfram alpha and get p = NextPrime(2 * p)
- // 3. repeat 2. until you overflow 64 bits
- // you now have large gaps which you would hit if somebody called reserve() with an unlucky number.
- // 4. to fill the gaps for every prime p go to wolfram alpha and get ClosestPrime(p * 2^(1/3)) and ClosestPrime(p * 2^(2/3)) and put those in the gaps
- // 5. get PrevPrime(2^64) and put it at the end
- static constexpr const size_t prime_list[] =
- {
- 2llu, 3llu, 5llu, 7llu, 11llu, 13llu, 17llu, 23llu, 29llu, 37llu, 47llu,
- 59llu, 73llu, 97llu, 127llu, 151llu, 197llu, 251llu, 313llu, 397llu,
- 499llu, 631llu, 797llu, 1009llu, 1259llu, 1597llu, 2011llu, 2539llu,
- 3203llu, 4027llu, 5087llu, 6421llu, 8089llu, 10193llu, 12853llu, 16193llu,
- 20399llu, 25717llu, 32401llu, 40823llu, 51437llu, 64811llu, 81649llu,
- 102877llu, 129607llu, 163307llu, 205759llu, 259229llu, 326617llu,
- 411527llu, 518509llu, 653267llu, 823117llu, 1037059llu, 1306601llu,
- 1646237llu, 2074129llu, 2613229llu, 3292489llu, 4148279llu, 5226491llu,
- 6584983llu, 8296553llu, 10453007llu, 13169977llu, 16593127llu, 20906033llu,
- 26339969llu, 33186281llu, 41812097llu, 52679969llu, 66372617llu,
- 83624237llu, 105359939llu, 132745199llu, 167248483llu, 210719881llu,
- 265490441llu, 334496971llu, 421439783llu, 530980861llu, 668993977llu,
- 842879579llu, 1061961721llu, 1337987929llu, 1685759167llu, 2123923447llu,
- 2675975881llu, 3371518343llu, 4247846927llu, 5351951779llu, 6743036717llu,
- 8495693897llu, 10703903591llu, 13486073473llu, 16991387857llu,
- 21407807219llu, 26972146961llu, 33982775741llu, 42815614441llu,
- 53944293929llu, 67965551447llu, 85631228929llu, 107888587883llu,
- 135931102921llu, 171262457903llu, 215777175787llu, 271862205833llu,
- 342524915839llu, 431554351609llu, 543724411781llu, 685049831731llu,
- 863108703229llu, 1087448823553llu, 1370099663459llu, 1726217406467llu,
- 2174897647073llu, 2740199326961llu, 3452434812973llu, 4349795294267llu,
- 5480398654009llu, 6904869625999llu, 8699590588571llu, 10960797308051llu,
- 13809739252051llu, 17399181177241llu, 21921594616111llu, 27619478504183llu,
- 34798362354533llu, 43843189232363llu, 55238957008387llu, 69596724709081llu,
- 87686378464759llu, 110477914016779llu, 139193449418173llu,
- 175372756929481llu, 220955828033581llu, 278386898836457llu,
- 350745513859007llu, 441911656067171llu, 556773797672909llu,
- 701491027718027llu, 883823312134381llu, 1113547595345903llu,
- 1402982055436147llu, 1767646624268779llu, 2227095190691797llu,
- 2805964110872297llu, 3535293248537579llu, 4454190381383713llu,
- 5611928221744609llu, 7070586497075177llu, 8908380762767489llu,
- 11223856443489329llu, 14141172994150357llu, 17816761525534927llu,
- 22447712886978529llu, 28282345988300791llu, 35633523051069991llu,
- 44895425773957261llu, 56564691976601587llu, 71267046102139967llu,
- 89790851547914507llu, 113129383953203213llu, 142534092204280003llu,
- 179581703095829107llu, 226258767906406483llu, 285068184408560057llu,
- 359163406191658253llu, 452517535812813007llu, 570136368817120201llu,
- 718326812383316683llu, 905035071625626043llu, 1140272737634240411llu,
- 1436653624766633509llu, 1810070143251252131llu, 2280545475268481167llu,
- 2873307249533267101llu, 3620140286502504283llu, 4561090950536962147llu,
- 5746614499066534157llu, 7240280573005008577llu, 9122181901073924329llu,
- 11493228998133068689llu, 14480561146010017169llu, 18446744073709551557llu
- };
- static constexpr size_t (* const mod_functions[])(size_t) =
- {
- &mod0, &mod2, &mod3, &mod5, &mod7, &mod11, &mod13, &mod17, &mod23, &mod29, &mod37,
- &mod47, &mod59, &mod73, &mod97, &mod127, &mod151, &mod197, &mod251, &mod313, &mod397,
- &mod499, &mod631, &mod797, &mod1009, &mod1259, &mod1597, &mod2011, &mod2539, &mod3203,
- &mod4027, &mod5087, &mod6421, &mod8089, &mod10193, &mod12853, &mod16193, &mod20399,
- &mod25717, &mod32401, &mod40823, &mod51437, &mod64811, &mod81649, &mod102877,
- &mod129607, &mod163307, &mod205759, &mod259229, &mod326617, &mod411527, &mod518509,
- &mod653267, &mod823117, &mod1037059, &mod1306601, &mod1646237, &mod2074129,
- &mod2613229, &mod3292489, &mod4148279, &mod5226491, &mod6584983, &mod8296553,
- &mod10453007, &mod13169977, &mod16593127, &mod20906033, &mod26339969, &mod33186281,
- &mod41812097, &mod52679969, &mod66372617, &mod83624237, &mod105359939, &mod132745199,
- &mod167248483, &mod210719881, &mod265490441, &mod334496971, &mod421439783,
- &mod530980861, &mod668993977, &mod842879579, &mod1061961721, &mod1337987929,
- &mod1685759167, &mod2123923447, &mod2675975881, &mod3371518343, &mod4247846927,
- &mod5351951779, &mod6743036717, &mod8495693897, &mod10703903591, &mod13486073473,
- &mod16991387857, &mod21407807219, &mod26972146961, &mod33982775741, &mod42815614441,
- &mod53944293929, &mod67965551447, &mod85631228929, &mod107888587883, &mod135931102921,
- &mod171262457903, &mod215777175787, &mod271862205833, &mod342524915839,
- &mod431554351609, &mod543724411781, &mod685049831731, &mod863108703229,
- &mod1087448823553, &mod1370099663459, &mod1726217406467, &mod2174897647073,
- &mod2740199326961, &mod3452434812973, &mod4349795294267, &mod5480398654009,
- &mod6904869625999, &mod8699590588571, &mod10960797308051, &mod13809739252051,
- &mod17399181177241, &mod21921594616111, &mod27619478504183, &mod34798362354533,
- &mod43843189232363, &mod55238957008387, &mod69596724709081, &mod87686378464759,
- &mod110477914016779, &mod139193449418173, &mod175372756929481, &mod220955828033581,
- &mod278386898836457, &mod350745513859007, &mod441911656067171, &mod556773797672909,
- &mod701491027718027, &mod883823312134381, &mod1113547595345903, &mod1402982055436147,
- &mod1767646624268779, &mod2227095190691797, &mod2805964110872297, &mod3535293248537579,
- &mod4454190381383713, &mod5611928221744609, &mod7070586497075177, &mod8908380762767489,
- &mod11223856443489329, &mod14141172994150357, &mod17816761525534927,
- &mod22447712886978529, &mod28282345988300791, &mod35633523051069991,
- &mod44895425773957261, &mod56564691976601587, &mod71267046102139967,
- &mod89790851547914507, &mod113129383953203213, &mod142534092204280003,
- &mod179581703095829107, &mod226258767906406483, &mod285068184408560057,
- &mod359163406191658253, &mod452517535812813007, &mod570136368817120201,
- &mod718326812383316683, &mod905035071625626043, &mod1140272737634240411,
- &mod1436653624766633509, &mod1810070143251252131, &mod2280545475268481167,
- &mod2873307249533267101, &mod3620140286502504283, &mod4561090950536962147,
- &mod5746614499066534157, &mod7240280573005008577, &mod9122181901073924329,
- &mod11493228998133068689, &mod14480561146010017169, &mod18446744073709551557
- };
- const size_t * found = std::lower_bound(std::begin(prime_list), std::end(prime_list) - 1, size);
- size = *found;
- return mod_functions[1 + found - prime_list];
- }
- void commit(mod_function new_mod_function)
- {
- current_mod_function = new_mod_function;
- }
- void reset()
- {
- current_mod_function = &mod0;
- }
-
- size_t index_for_hash(size_t hash, size_t /*num_slots_minus_one*/) const
- {
- return current_mod_function(hash);
- }
- size_t keep_in_range(size_t index, size_t num_slots_minus_one) const
- {
- return index > num_slots_minus_one ? current_mod_function(index) : index;
- }
-
-private:
- mod_function current_mod_function = &mod0;
-};
-
-struct power_of_two_hash_policy
-{
- size_t index_for_hash(size_t hash, size_t num_slots_minus_one) const
- {
- return hash & num_slots_minus_one;
- }
- size_t keep_in_range(size_t index, size_t num_slots_minus_one) const
- {
- return index_for_hash(index, num_slots_minus_one);
- }
- int8_t next_size_over(size_t & size) const
- {
- size = detailv3::next_power_of_two(size);
- return 0;
- }
- void commit(int8_t)
- {
- }
- void reset()
- {
- }
-
-};
-
-struct fibonacci_hash_policy
-{
- size_t index_for_hash(size_t hash, size_t /*num_slots_minus_one*/) const
- {
- return (11400714819323198485ull * hash) >> shift;
- }
- size_t keep_in_range(size_t index, size_t num_slots_minus_one) const
- {
- return index & num_slots_minus_one;
- }
-
- int8_t next_size_over(size_t & size) const
- {
- size = std::max(size_t(2), detailv3::next_power_of_two(size));
- return 64 - detailv3::log2(size);
- }
- void commit(int8_t shift)
- {
- this->shift = shift;
- }
- void reset()
- {
- shift = 63;
- }
-
-private:
- int8_t shift = 63;
-};
-
-template<typename K, typename V, typename H = std::hash<K>, typename E = std::equal_to<K>, typename A = std::allocator<std::pair<K, V> > >
-class flat_hash_map
- : public detailv3::sherwood_v3_table
- <
- std::pair<K, V>,
- K,
- H,
- detailv3::KeyOrValueHasher<K, std::pair<K, V>, H>,
- E,
- detailv3::KeyOrValueEquality<K, std::pair<K, V>, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<std::pair<K, V>>>
- >
-{
- using Table = detailv3::sherwood_v3_table
- <
- std::pair<K, V>,
- K,
- H,
- detailv3::KeyOrValueHasher<K, std::pair<K, V>, H>,
- E,
- detailv3::KeyOrValueEquality<K, std::pair<K, V>, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<std::pair<K, V>>>
- >;
-public:
-
- using key_type = K;
- using mapped_type = V;
-
- using Table::Table;
- flat_hash_map()
- {
- }
-
- inline V & operator[](const K & key)
- {
- return emplace(key, convertible_to_value()).first->second;
- }
- inline V & operator[](K && key)
- {
- return emplace(std::move(key), convertible_to_value()).first->second;
- }
- V & at(const K & key)
- {
- auto found = this->find(key);
- if (found == this->end())
- throw std::out_of_range("Argument passed to at() was not in the map.");
- return found->second;
- }
- const V & at(const K & key) const
- {
- auto found = this->find(key);
- if (found == this->end())
- throw std::out_of_range("Argument passed to at() was not in the map.");
- return found->second;
- }
-
- using Table::emplace;
- std::pair<typename Table::iterator, bool> emplace()
- {
- return emplace(key_type(), convertible_to_value());
- }
- template<typename M>
- std::pair<typename Table::iterator, bool> insert_or_assign(const key_type & key, M && m)
- {
- auto emplace_result = emplace(key, std::forward<M>(m));
- if (!emplace_result.second)
- emplace_result.first->second = std::forward<M>(m);
- return emplace_result;
- }
- template<typename M>
- std::pair<typename Table::iterator, bool> insert_or_assign(key_type && key, M && m)
- {
- auto emplace_result = emplace(std::move(key), std::forward<M>(m));
- if (!emplace_result.second)
- emplace_result.first->second = std::forward<M>(m);
- return emplace_result;
- }
- template<typename M>
- typename Table::iterator insert_or_assign(typename Table::const_iterator, const key_type & key, M && m)
- {
- return insert_or_assign(key, std::forward<M>(m)).first;
- }
- template<typename M>
- typename Table::iterator insert_or_assign(typename Table::const_iterator, key_type && key, M && m)
- {
- return insert_or_assign(std::move(key), std::forward<M>(m)).first;
- }
-
- friend bool operator==(const flat_hash_map & lhs, const flat_hash_map & rhs)
- {
- if (lhs.size() != rhs.size())
- return false;
- for (const typename Table::value_type & value : lhs)
- {
- auto found = rhs.find(value.first);
- if (found == rhs.end())
- return false;
- else if (value.second != found->second)
- return false;
- }
- return true;
- }
- friend bool operator!=(const flat_hash_map & lhs, const flat_hash_map & rhs)
- {
- return !(lhs == rhs);
- }
-
-private:
- struct convertible_to_value
- {
- operator V() const
- {
- return V();
- }
- };
-};
-
-template<typename T, typename H = std::hash<T>, typename E = std::equal_to<T>, typename A = std::allocator<T> >
-class flat_hash_set
- : public detailv3::sherwood_v3_table
- <
- T,
- T,
- H,
- detailv3::functor_storage<size_t, H>,
- E,
- detailv3::functor_storage<bool, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<T>>
- >
-{
- using Table = detailv3::sherwood_v3_table
- <
- T,
- T,
- H,
- detailv3::functor_storage<size_t, H>,
- E,
- detailv3::functor_storage<bool, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<T>>
- >;
-public:
-
- using key_type = T;
-
- using Table::Table;
- flat_hash_set()
- {
- }
-
- template<typename... Args>
- std::pair<typename Table::iterator, bool> emplace(Args &&... args)
- {
- return Table::emplace(T(std::forward<Args>(args)...));
- }
- std::pair<typename Table::iterator, bool> emplace(const key_type & arg)
- {
- return Table::emplace(arg);
- }
- std::pair<typename Table::iterator, bool> emplace(key_type & arg)
- {
- return Table::emplace(arg);
- }
- std::pair<typename Table::iterator, bool> emplace(const key_type && arg)
- {
- return Table::emplace(std::move(arg));
- }
- std::pair<typename Table::iterator, bool> emplace(key_type && arg)
- {
- return Table::emplace(std::move(arg));
- }
-
- friend bool operator==(const flat_hash_set & lhs, const flat_hash_set & rhs)
- {
- if (lhs.size() != rhs.size())
- return false;
- for (const T & value : lhs)
- {
- if (rhs.find(value) == rhs.end())
- return false;
- }
- return true;
- }
- friend bool operator!=(const flat_hash_set & lhs, const flat_hash_set & rhs)
- {
- return !(lhs == rhs);
- }
-};
-
-
-template<typename T>
-struct power_of_two_std_hash : std::hash<T>
-{
- typedef ska::power_of_two_hash_policy hash_policy;
-};
-
-} // end namespace ska
diff --git a/gctest/flat_hash_map/unordered_map.hpp b/gctest/flat_hash_map/unordered_map.hpp
deleted file mode 100644
index 5e6e876..0000000
--- a/gctest/flat_hash_map/unordered_map.hpp
+++ /dev/null
@@ -1,885 +0,0 @@
-// Copyright Malte Skarupke 2017.
-// Distributed under the Boost Software License, Version 1.0.
-// (See http://www.boost.org/LICENSE_1_0.txt)
-
-#pragma once
-
-#include <cstdint>
-#include <cstddef>
-#include <cmath>
-#include <array>
-#include <algorithm>
-#include <iterator>
-#include <utility>
-#include <type_traits>
-#include "flat_hash_map.hpp"
-
-namespace ska
-{
-
-namespace detailv10
-{
-template<typename T, typename Allocator>
-struct sherwood_v10_entry
-{
- sherwood_v10_entry()
- {
- }
- ~sherwood_v10_entry()
- {
- }
-
- using EntryPointer = typename std::allocator_traits<typename std::allocator_traits<Allocator>::template rebind_alloc<sherwood_v10_entry>>::pointer;
-
- EntryPointer next = nullptr;
- union
- {
- T value;
- };
-
- static EntryPointer * empty_pointer()
- {
- static EntryPointer result[3] = { EntryPointer(nullptr) + ptrdiff_t(1), nullptr, nullptr };
- return result + 1;
- }
-};
-
-using ska::detailv3::functor_storage;
-using ska::detailv3::KeyOrValueHasher;
-using ska::detailv3::KeyOrValueEquality;
-using ska::detailv3::AssignIfTrue;
-using ska::detailv3::HashPolicySelector;
-
-template<typename T, typename FindKey, typename ArgumentHash, typename Hasher, typename ArgumentEqual, typename Equal, typename ArgumentAlloc, typename EntryAlloc, typename BucketAllocator>
-class sherwood_v10_table : private EntryAlloc, private Hasher, private Equal, private BucketAllocator
-{
- using Entry = detailv10::sherwood_v10_entry<T, ArgumentAlloc>;
- using AllocatorTraits = std::allocator_traits<EntryAlloc>;
- using BucketAllocatorTraits = std::allocator_traits<BucketAllocator>;
- using EntryPointer = typename AllocatorTraits::pointer;
- struct convertible_to_iterator;
-
-public:
-
- using value_type = T;
- using size_type = size_t;
- using difference_type = std::ptrdiff_t;
- using hasher = ArgumentHash;
- using key_equal = ArgumentEqual;
- using allocator_type = EntryAlloc;
- using reference = value_type &;
- using const_reference = const value_type &;
- using pointer = value_type *;
- using const_pointer = const value_type *;
-
- sherwood_v10_table()
- {
- }
- explicit sherwood_v10_table(size_type bucket_count, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
- : EntryAlloc(alloc), Hasher(hash), Equal(equal), BucketAllocator(alloc)
- {
- rehash(bucket_count);
- }
- sherwood_v10_table(size_type bucket_count, const ArgumentAlloc & alloc)
- : sherwood_v10_table(bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
- {
- }
- sherwood_v10_table(size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
- : sherwood_v10_table(bucket_count, hash, ArgumentEqual(), alloc)
- {
- }
- explicit sherwood_v10_table(const ArgumentAlloc & alloc)
- : EntryAlloc(alloc), BucketAllocator(alloc)
- {
- }
- template<typename It>
- sherwood_v10_table(It first, It last, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
- : sherwood_v10_table(bucket_count, hash, equal, alloc)
- {
- insert(first, last);
- }
- template<typename It>
- sherwood_v10_table(It first, It last, size_type bucket_count, const ArgumentAlloc & alloc)
- : sherwood_v10_table(first, last, bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
- {
- }
- template<typename It>
- sherwood_v10_table(It first, It last, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
- : sherwood_v10_table(first, last, bucket_count, hash, ArgumentEqual(), alloc)
- {
- }
- sherwood_v10_table(std::initializer_list<T> il, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
- : sherwood_v10_table(bucket_count, hash, equal, alloc)
- {
- if (bucket_count == 0)
- reserve(il.size());
- insert(il.begin(), il.end());
- }
- sherwood_v10_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentAlloc & alloc)
- : sherwood_v10_table(il, bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
- {
- }
- sherwood_v10_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
- : sherwood_v10_table(il, bucket_count, hash, ArgumentEqual(), alloc)
- {
- }
- sherwood_v10_table(const sherwood_v10_table & other)
- : sherwood_v10_table(other, AllocatorTraits::select_on_container_copy_construction(other.get_allocator()))
- {
- }
- sherwood_v10_table(const sherwood_v10_table & other, const ArgumentAlloc & alloc)
- : EntryAlloc(alloc), Hasher(other), Equal(other), BucketAllocator(alloc), _max_load_factor(other._max_load_factor)
- {
- try
- {
- rehash_for_other_container(other);
- insert(other.begin(), other.end());
- }
- catch(...)
- {
- clear();
- deallocate_data();
- throw;
- }
- }
- sherwood_v10_table(sherwood_v10_table && other) noexcept
- : EntryAlloc(std::move(other)), Hasher(std::move(other)), Equal(std::move(other)), BucketAllocator(std::move(other)), _max_load_factor(other._max_load_factor)
- {
- swap_pointers(other);
- }
- sherwood_v10_table(sherwood_v10_table && other, const ArgumentAlloc & alloc) noexcept
- : EntryAlloc(alloc), Hasher(std::move(other)), Equal(std::move(other)), BucketAllocator(alloc), _max_load_factor(other._max_load_factor)
- {
- swap_pointers(other);
- }
- sherwood_v10_table & operator=(const sherwood_v10_table & other)
- {
- if (this == std::addressof(other))
- return *this;
-
- clear();
- static_assert(AllocatorTraits::propagate_on_container_copy_assignment::value == BucketAllocatorTraits::propagate_on_container_copy_assignment::value, "The allocators have to behave the same way");
- if (AllocatorTraits::propagate_on_container_copy_assignment::value)
- {
- if (static_cast<EntryAlloc &>(*this) != static_cast<const EntryAlloc &>(other) || static_cast<BucketAllocator &>(*this) != static_cast<const BucketAllocator &>(other))
- {
- reset_to_empty_state();
- }
- AssignIfTrue<EntryAlloc, AllocatorTraits::propagate_on_container_copy_assignment::value>()(*this, other);
- AssignIfTrue<BucketAllocator, BucketAllocatorTraits::propagate_on_container_copy_assignment::value>()(*this, other);
- }
- _max_load_factor = other._max_load_factor;
- static_cast<Hasher &>(*this) = other;
- static_cast<Equal &>(*this) = other;
- rehash_for_other_container(other);
- insert(other.begin(), other.end());
- return *this;
- }
- sherwood_v10_table & operator=(sherwood_v10_table && other) noexcept
- {
- static_assert(AllocatorTraits::propagate_on_container_move_assignment::value == BucketAllocatorTraits::propagate_on_container_move_assignment::value, "The allocators have to behave the same way");
- if (this == std::addressof(other))
- return *this;
- else if (AllocatorTraits::propagate_on_container_move_assignment::value)
- {
- clear();
- reset_to_empty_state();
- AssignIfTrue<EntryAlloc, AllocatorTraits::propagate_on_container_move_assignment::value>()(*this, std::move(other));
- AssignIfTrue<BucketAllocator, BucketAllocatorTraits::propagate_on_container_move_assignment::value>()(*this, std::move(other));
- swap_pointers(other);
- }
- else if (static_cast<EntryAlloc &>(*this) == static_cast<EntryAlloc &>(other) && static_cast<BucketAllocator &>(*this) == static_cast<BucketAllocator &>(other))
- {
- swap_pointers(other);
- }
- else
- {
- clear();
- _max_load_factor = other._max_load_factor;
- rehash_for_other_container(other);
- for (T & elem : other)
- emplace(std::move(elem));
- other.clear();
- }
- static_cast<Hasher &>(*this) = std::move(other);
- static_cast<Equal &>(*this) = std::move(other);
- return *this;
- }
- ~sherwood_v10_table()
- {
- clear();
- deallocate_data();
- }
-
- const allocator_type & get_allocator() const
- {
- return static_cast<const allocator_type &>(*this);
- }
- const ArgumentEqual & key_eq() const
- {
- return static_cast<const ArgumentEqual &>(*this);
- }
- const ArgumentHash & hash_function() const
- {
- return static_cast<const ArgumentHash &>(*this);
- }
-
- template<typename ValueType>
- struct templated_iterator
- {
- templated_iterator()
- {
- }
- templated_iterator(EntryPointer element, EntryPointer * bucket)
- : current_element(element), current_bucket(bucket)
- {
- }
-
- EntryPointer current_element = nullptr;
- EntryPointer * current_bucket = nullptr;
-
- using iterator_category = std::forward_iterator_tag;
- using value_type = ValueType;
- using difference_type = ptrdiff_t;
- using pointer = ValueType *;
- using reference = ValueType &;
-
- friend bool operator==(const templated_iterator & lhs, const templated_iterator & rhs)
- {
- return lhs.current_element == rhs.current_element;
- }
- friend bool operator!=(const templated_iterator & lhs, const templated_iterator & rhs)
- {
- return !(lhs == rhs);
- }
-
- templated_iterator & operator++()
- {
- if (!current_element->next)
- {
- do
- {
- --current_bucket;
- }
- while (!*current_bucket);
- current_element = *current_bucket;
- }
- else
- current_element = current_element->next;
- return *this;
- }
- templated_iterator operator++(int)
- {
- templated_iterator copy(*this);
- ++*this;
- return copy;
- }
-
- ValueType & operator*() const
- {
- return current_element->value;
- }
- ValueType * operator->() const
- {
- return std::addressof(current_element->value);
- }
-
- operator templated_iterator<const value_type>() const
- {
- return { current_element, current_bucket };
- }
- };
- using iterator = templated_iterator<value_type>;
- using const_iterator = templated_iterator<const value_type>;
-
- iterator begin()
- {
- EntryPointer * end = entries - 1;
- for (EntryPointer * it = entries + num_slots_minus_one; it != end; --it)
- {
- if (*it)
- return { *it, it };
- }
- return { *end, end };
- }
- const_iterator begin() const
- {
- return const_cast<sherwood_v10_table *>(this)->begin();
- }
- const_iterator cbegin() const
- {
- return begin();
- }
- iterator end()
- {
- EntryPointer * end = entries - 1;
- return { *end, end };
- }
- const_iterator end() const
- {
- EntryPointer * end = entries - 1;
- return { *end, end };
- }
- const_iterator cend() const
- {
- return end();
- }
-
- iterator find(const FindKey & key)
- {
- size_t index = hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
- EntryPointer * bucket = entries + ptrdiff_t(index);
- for (EntryPointer it = *bucket; it; it = it->next)
- {
- if (compares_equal(key, it->value))
- return { it, bucket };
- }
- return end();
- }
- const_iterator find(const FindKey & key) const
- {
- return const_cast<sherwood_v10_table *>(this)->find(key);
- }
- size_t count(const FindKey & key) const
- {
- return find(key) == end() ? 0 : 1;
- }
- std::pair<iterator, iterator> equal_range(const FindKey & key)
- {
- iterator found = find(key);
- if (found == end())
- return { found, found };
- else
- return { found, std::next(found) };
- }
- std::pair<const_iterator, const_iterator> equal_range(const FindKey & key) const
- {
- const_iterator found = find(key);
- if (found == end())
- return { found, found };
- else
- return { found, std::next(found) };
- }
-
- template<typename Key, typename... Args>
- std::pair<iterator, bool> emplace(Key && key, Args &&... args)
- {
- size_t index = hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
- EntryPointer * bucket = entries + ptrdiff_t(index);
- for (EntryPointer it = *bucket; it; it = it->next)
- {
- if (compares_equal(key, it->value))
- return { { it, bucket }, false };
- }
- return emplace_new_key(bucket, std::forward<Key>(key), std::forward<Args>(args)...);
- }
-
- std::pair<iterator, bool> insert(const value_type & value)
- {
- return emplace(value);
- }
- std::pair<iterator, bool> insert(value_type && value)
- {
- return emplace(std::move(value));
- }
- template<typename... Args>
- iterator emplace_hint(const_iterator, Args &&... args)
- {
- return emplace(std::forward<Args>(args)...).first;
- }
- iterator insert(const_iterator, const value_type & value)
- {
- return emplace(value).first;
- }
- iterator insert(const_iterator, value_type && value)
- {
- return emplace(std::move(value)).first;
- }
-
- template<typename It>
- void insert(It begin, It end)
- {
- for (; begin != end; ++begin)
- {
- emplace(*begin);
- }
- }
- void insert(std::initializer_list<value_type> il)
- {
- insert(il.begin(), il.end());
- }
-
- void rehash(size_t num_buckets)
- {
- num_buckets = std::max(num_buckets, static_cast<size_t>(std::ceil(num_elements / static_cast<double>(_max_load_factor))));
- if (num_buckets == 0)
- {
- reset_to_empty_state();
- return;
- }
- auto new_prime_index = hash_policy.next_size_over(num_buckets);
- if (num_buckets == bucket_count())
- return;
- EntryPointer * new_buckets(&*BucketAllocatorTraits::allocate(*this, num_buckets + 1));
- EntryPointer * end_it = new_buckets + static_cast<ptrdiff_t>(num_buckets + 1);
- *new_buckets = EntryPointer(nullptr) + ptrdiff_t(1);
- ++new_buckets;
- std::fill(new_buckets, end_it, nullptr);
- std::swap(entries, new_buckets);
- std::swap(num_slots_minus_one, num_buckets);
- --num_slots_minus_one;
- hash_policy.commit(new_prime_index);
- if (!num_buckets)
- return;
-
- for (EntryPointer * it = new_buckets, * end = it + static_cast<ptrdiff_t>(num_buckets + 1); it != end; ++it)
- {
- for (EntryPointer e = *it; e;)
- {
- EntryPointer next = e->next;
- size_t index = hash_policy.index_for_hash(hash_object(e->value), num_slots_minus_one);
- EntryPointer & new_slot = entries[index];
- e->next = new_slot;
- new_slot = e;
- e = next;
- }
- }
- BucketAllocatorTraits::deallocate(*this, new_buckets - 1, num_buckets + 2);
- }
-
- void reserve(size_t num_elements)
- {
- if (!num_elements)
- return;
- num_elements = static_cast<size_t>(std::ceil(num_elements / static_cast<double>(_max_load_factor)));
- if (num_elements > bucket_count())
- rehash(num_elements);
- }
-
- // the return value is a type that can be converted to an iterator
- // the reason for doing this is that it's not free to find the
- // iterator pointing at the next element. if you care about the
- // next iterator, turn the return value into an iterator
- convertible_to_iterator erase(const_iterator to_erase)
- {
- --num_elements;
- AllocatorTraits::destroy(*this, std::addressof(to_erase.current_element->value));
- EntryPointer * previous = to_erase.current_bucket;
- while (*previous != to_erase.current_element)
- {
- previous = &(*previous)->next;
- }
- *previous = to_erase.current_element->next;
- AllocatorTraits::deallocate(*this, to_erase.current_element, 1);
- return { *previous, to_erase.current_bucket };
- }
-
- convertible_to_iterator erase(const_iterator begin_it, const_iterator end_it)
- {
- while (begin_it.current_bucket != end_it.current_bucket)
- {
- begin_it = erase(begin_it);
- }
- EntryPointer * bucket = begin_it.current_bucket;
- EntryPointer * previous = bucket;
- while (*previous != begin_it.current_element)
- previous = &(*previous)->next;
- while (*previous != end_it.current_element)
- {
- --num_elements;
- EntryPointer entry = *previous;
- AllocatorTraits::destroy(*this, std::addressof(entry->value));
- *previous = entry->next;
- AllocatorTraits::deallocate(*this, entry, 1);
- }
- return { *previous, bucket };
- }
-
- size_t erase(const FindKey & key)
- {
- auto found = find(key);
- if (found == end())
- return 0;
- else
- {
- erase(found);
- return 1;
- }
- }
-
- void clear()
- {
- if (!num_slots_minus_one)
- return;
- for (EntryPointer * it = entries, * end = it + static_cast<ptrdiff_t>(num_slots_minus_one + 1); it != end; ++it)
- {
- for (EntryPointer e = *it; e;)
- {
- EntryPointer next = e->next;
- AllocatorTraits::destroy(*this, std::addressof(e->value));
- AllocatorTraits::deallocate(*this, e, 1);
- e = next;
- }
- *it = nullptr;
- }
- num_elements = 0;
- }
-
- void swap(sherwood_v10_table & other)
- {
- using std::swap;
- swap_pointers(other);
- swap(static_cast<ArgumentHash &>(*this), static_cast<ArgumentHash &>(other));
- swap(static_cast<ArgumentEqual &>(*this), static_cast<ArgumentEqual &>(other));
- if (AllocatorTraits::propagate_on_container_swap::value)
- swap(static_cast<EntryAlloc &>(*this), static_cast<EntryAlloc &>(other));
- if (BucketAllocatorTraits::propagate_on_container_swap::value)
- swap(static_cast<BucketAllocator &>(*this), static_cast<BucketAllocator &>(other));
- }
-
- size_t size() const
- {
- return num_elements;
- }
- size_t max_size() const
- {
- return (AllocatorTraits::max_size(*this)) / sizeof(Entry);
- }
- size_t bucket_count() const
- {
- return num_slots_minus_one + 1;
- }
- size_type max_bucket_count() const
- {
- return (AllocatorTraits::max_size(*this) - 1) / sizeof(Entry);
- }
- size_t bucket(const FindKey & key) const
- {
- return hash_policy.template index_for_hash<0>(hash_object(key), num_slots_minus_one);
- }
- float load_factor() const
- {
- size_t buckets = bucket_count();
- if (buckets)
- return static_cast<float>(num_elements) / bucket_count();
- else
- return 0;
- }
- void max_load_factor(float value)
- {
- _max_load_factor = value;
- }
- float max_load_factor() const
- {
- return _max_load_factor;
- }
-
- bool empty() const
- {
- return num_elements == 0;
- }
-
-private:
- EntryPointer * entries = Entry::empty_pointer();
- size_t num_slots_minus_one = 0;
- typename HashPolicySelector<ArgumentHash>::type hash_policy;
- float _max_load_factor = 1.0f;
- size_t num_elements = 0;
-
- void rehash_for_other_container(const sherwood_v10_table & other)
- {
- reserve(other.size());
- }
-
- void swap_pointers(sherwood_v10_table & other)
- {
- using std::swap;
- swap(hash_policy, other.hash_policy);
- swap(entries, other.entries);
- swap(num_slots_minus_one, other.num_slots_minus_one);
- swap(num_elements, other.num_elements);
- swap(_max_load_factor, other._max_load_factor);
- }
-
- template<typename... Args>
- SKA_NOINLINE(std::pair<iterator, bool>) emplace_new_key(EntryPointer * bucket, Args &&... args)
- {
- using std::swap;
- if (is_full())
- {
- grow();
- return emplace(std::forward<Args>(args)...);
- }
- else
- {
- EntryPointer new_entry = AllocatorTraits::allocate(*this, 1);
- try
- {
- AllocatorTraits::construct(*this, std::addressof(new_entry->value), std::forward<Args>(args)...);
- }
- catch(...)
- {
- AllocatorTraits::deallocate(*this, new_entry, 1);
- throw;
- }
- ++num_elements;
- new_entry->next = *bucket;
- *bucket = new_entry;
- return { { new_entry, bucket }, true };
- }
- }
-
- bool is_full() const
- {
- if (!num_slots_minus_one)
- return true;
- else
- return num_elements + 1 > (num_slots_minus_one + 1) * static_cast<double>(_max_load_factor);
- }
-
- void grow()
- {
- rehash(std::max(size_t(4), 2 * bucket_count()));
- }
-
- void deallocate_data()
- {
- if (entries != Entry::empty_pointer())
- {
- BucketAllocatorTraits::deallocate(*this, entries - 1, num_slots_minus_one + 2);
- }
- }
-
- void reset_to_empty_state()
- {
- deallocate_data();
- entries = Entry::empty_pointer();
- num_slots_minus_one = 0;
- hash_policy.reset();
- }
-
- template<typename U>
- size_t hash_object(const U & key)
- {
- return static_cast<Hasher &>(*this)(key);
- }
- template<typename U>
- size_t hash_object(const U & key) const
- {
- return static_cast<const Hasher &>(*this)(key);
- }
- template<typename L, typename R>
- bool compares_equal(const L & lhs, const R & rhs)
- {
- return static_cast<Equal &>(*this)(lhs, rhs);
- }
-
- struct convertible_to_iterator
- {
- EntryPointer element;
- EntryPointer * bucket;
-
- operator iterator()
- {
- if (element)
- return { element, bucket };
- else
- {
- do
- {
- --bucket;
- }
- while (!*bucket);
- return { *bucket, bucket };
- }
- }
- operator const_iterator()
- {
- if (element)
- return { element, bucket };
- else
- {
- do
- {
- --bucket;
- }
- while (!*bucket);
- return { *bucket, bucket };
- }
- }
- };
-};
-}
-
-
-template<typename K, typename V, typename H = std::hash<K>, typename E = std::equal_to<K>, typename A = std::allocator<std::pair<K, V> > >
-class unordered_map
- : public detailv10::sherwood_v10_table
- <
- std::pair<K, V>,
- K,
- H,
- detailv10::KeyOrValueHasher<K, std::pair<K, V>, H>,
- E,
- detailv10::KeyOrValueEquality<K, std::pair<K, V>, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<detailv10::sherwood_v10_entry<std::pair<K, V>, A>>,
- typename std::allocator_traits<A>::template rebind_alloc<typename std::allocator_traits<A>::template rebind_traits<detailv10::sherwood_v10_entry<std::pair<K, V>, A>>::pointer>
- >
-{
- using Table = detailv10::sherwood_v10_table
- <
- std::pair<K, V>,
- K,
- H,
- detailv10::KeyOrValueHasher<K, std::pair<K, V>, H>,
- E,
- detailv10::KeyOrValueEquality<K, std::pair<K, V>, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<detailv10::sherwood_v10_entry<std::pair<K, V>, A>>,
- typename std::allocator_traits<A>::template rebind_alloc<typename std::allocator_traits<A>::template rebind_traits<detailv10::sherwood_v10_entry<std::pair<K, V>, A>>::pointer>
- >;
-public:
-
- using key_type = K;
- using mapped_type = V;
-
- using Table::Table;
- unordered_map()
- {
- }
-
- V & operator[](const K & key)
- {
- return emplace(key, convertible_to_value()).first->second;
- }
- V & operator[](K && key)
- {
- return emplace(std::move(key), convertible_to_value()).first->second;
- }
- V & at(const K & key)
- {
- auto found = this->find(key);
- if (found == this->end())
- throw std::out_of_range("Argument passed to at() was not in the map.");
- return found->second;
- }
- const V & at(const K & key) const
- {
- auto found = this->find(key);
- if (found == this->end())
- throw std::out_of_range("Argument passed to at() was not in the map.");
- return found->second;
- }
-
- using Table::emplace;
- std::pair<typename Table::iterator, bool> emplace()
- {
- return emplace(key_type(), convertible_to_value());
- }
-
- friend bool operator==(const unordered_map & lhs, const unordered_map & rhs)
- {
- if (lhs.size() != rhs.size())
- return false;
- for (const typename Table::value_type & value : lhs)
- {
- auto found = rhs.find(value.first);
- if (found == rhs.end())
- return false;
- else if (value.second != found->second)
- return false;
- }
- return true;
- }
- friend bool operator!=(const unordered_map & lhs, const unordered_map & rhs)
- {
- return !(lhs == rhs);
- }
-
-private:
- struct convertible_to_value
- {
- operator V() const
- {
- return V();
- }
- };
-};
-
-template<typename T, typename H = std::hash<T>, typename E = std::equal_to<T>, typename A = std::allocator<T> >
-class unordered_set
- : public detailv10::sherwood_v10_table
- <
- T,
- T,
- H,
- detailv10::functor_storage<size_t, H>,
- E,
- detailv10::functor_storage<bool, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<detailv10::sherwood_v10_entry<T, A>>,
- typename std::allocator_traits<A>::template rebind_alloc<typename std::allocator_traits<A>::template rebind_traits<detailv10::sherwood_v10_entry<T, A>>::pointer>
- >
-{
- using Table = detailv10::sherwood_v10_table
- <
- T,
- T,
- H,
- detailv10::functor_storage<size_t, H>,
- E,
- detailv10::functor_storage<bool, E>,
- A,
- typename std::allocator_traits<A>::template rebind_alloc<detailv10::sherwood_v10_entry<T, A>>,
- typename std::allocator_traits<A>::template rebind_alloc<typename std::allocator_traits<A>::template rebind_traits<detailv10::sherwood_v10_entry<T, A>>::pointer>
- >;
-public:
-
- using key_type = T;
-
- using Table::Table;
- unordered_set()
- {
- }
-
- template<typename... Args>
- std::pair<typename Table::iterator, bool> emplace(Args &&... args)
- {
- return Table::emplace(T(std::forward<Args>(args)...));
- }
- std::pair<typename Table::iterator, bool> emplace(const key_type & arg)
- {
- return Table::emplace(arg);
- }
- std::pair<typename Table::iterator, bool> emplace(key_type & arg)
- {
- return Table::emplace(arg);
- }
- std::pair<typename Table::iterator, bool> emplace(const key_type && arg)
- {
- return Table::emplace(std::move(arg));
- }
- std::pair<typename Table::iterator, bool> emplace(key_type && arg)
- {
- return Table::emplace(std::move(arg));
- }
-
- friend bool operator==(const unordered_set & lhs, const unordered_set & rhs)
- {
- if (lhs.size() != rhs.size())
- return false;
- for (const T & value : lhs)
- {
- if (rhs.find(value) == rhs.end())
- return false;
- }
- return true;
- }
- friend bool operator!=(const unordered_set & lhs, const unordered_set & rhs)
- {
- return !(lhs == rhs);
- }
-};
-
-} // end namespace ska