diff options
Diffstat (limited to 'benchmarks/others/bytell_hash_map.hpp')
| -rw-r--r-- | benchmarks/others/bytell_hash_map.hpp | 1260 |
1 files changed, 1260 insertions, 0 deletions
diff --git a/benchmarks/others/bytell_hash_map.hpp b/benchmarks/others/bytell_hash_map.hpp new file mode 100644 index 00000000..2e348cdb --- /dev/null +++ b/benchmarks/others/bytell_hash_map.hpp @@ -0,0 +1,1260 @@ +// 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
|