High performance txt file parsing
// START include/flat_hash_map/flat_hash_map.hpp | |
// Copyright Malte Skarupke 2017. | |
// Distributed under the Boost Software License, Version 1.0. | |
// (See http://www.boost.org/LICENSE_1_0.txt) | |
#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 | |
// START include/flat_hash_map/bytell_hash_map.hpp | |
// Copyright Malte Skarupke 2017. | |
// Distributed under the Boost Software License, Version 1.0. | |
// (See http://www.boost.org/LICENSE_1_0.txt) | |
#include <cstdint> | |
#include <cstddef> | |
#include <cmath> | |
#include <algorithm> | |
#include <iterator> | |
#include <utility> | |
#include <type_traits> | |
#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 | |
// START include/toolbelt/os/fs.hpp | |
// for mmap: | |
#include <fcntl.h> | |
#include <iostream> | |
#include <stdexcept> | |
#include <string_view> | |
#include <sys/mman.h> | |
#include <sys/stat.h> | |
namespace os::fs { | |
class MemoryMappedFile { | |
public: | |
explicit MemoryMappedFile(const std::string& filename) { | |
int fd = open(filename.c_str(), O_RDONLY); // NOLINT | |
if (fd == -1) throw std::logic_error("MemoryMappedFile: couldn't open file."); | |
// obtain file size | |
struct stat sbuf {}; | |
if (fstat(fd, &sbuf) == -1) throw std::logic_error("MemoryMappedFile: cannot stat file size"); | |
_filesize = sbuf.st_size; | |
_map = static_cast<const char*>(mmap(nullptr, _filesize, PROT_READ, MAP_PRIVATE, fd, 0U)); | |
if (_map == MAP_FAILED) // NOLINT : doesn't work somehow? | |
throw std::logic_error("MemoryMappedFile: cannot map file"); | |
} | |
~MemoryMappedFile() { | |
if (munmap(static_cast<void*>(const_cast<char*>(_map)), _filesize) == -1) // NOLINT | |
std::cerr << "Warnng: MemoryMappedFile: error in destructor during `munmap()`\n"; | |
} | |
// no copies | |
MemoryMappedFile(const MemoryMappedFile& other) = delete; | |
MemoryMappedFile& operator=(MemoryMappedFile other) = delete; | |
// default moves | |
MemoryMappedFile(MemoryMappedFile&& other) = default; | |
MemoryMappedFile& operator=(MemoryMappedFile&& other) = default; | |
// char* pointers. up to callee to make string_views or strings | |
[[nodiscard]] const char* begin() const { return _map; } | |
[[nodiscard]] const char* end() const { return _map + _filesize; } // NOLINT | |
[[nodiscard]] std::string_view get_buffer() const { | |
return std::string_view{begin(), static_cast<std::size_t>(end() - begin())} ; | |
} | |
private: | |
size_t _filesize = 0; | |
const char* _map = nullptr; | |
}; | |
} // namespace os::fs | |
// START include/toolbelt/os/str.hpp | |
#include <algorithm> | |
#include <cctype> | |
#include <charconv> | |
#include <functional> | |
#include <iostream> | |
#include <list> | |
#include <set> | |
#include <sstream> | |
#include <string> | |
#include <string_view> | |
#include <vector> | |
namespace os::str { | |
namespace ascii { | |
inline constexpr bool isalpha(char c) { return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); } | |
inline constexpr bool isnumeric(char c) { | |
return (c >= '0' && c <= '9') || c == '+' || c == '-' || c == '.' || c == ',' || c == '^' || | |
c == '*' || c == 'e' || c == 'E'; | |
} | |
inline constexpr bool isspace(char c) { | |
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == '\v' || c == '\f'; | |
} | |
inline constexpr std::string_view spacechars() { return " \t\n\r\v\f"; } | |
inline constexpr bool isalphanum(char c) { return isalpha(c) || isnumeric(c) || isspace(c); } | |
inline constexpr char tolower(char c) { | |
constexpr auto offset = 'a' - 'A'; | |
static_assert(offset % 2 == 0); // it's 32 == 0x20 == 1 << 5 in ASCII | |
return c | offset; // NOLINT - ignore warnings because < 128 | |
} | |
inline constexpr char toupper(char c) { return c & ~('a' - 'A'); } // NOLINT - ignore warnings | |
} // namespace ascii | |
inline void ltrim(std::string& s) { | |
s.erase(s.begin(), std::find_if(s.begin(), s.end(), [](char c) { return std::isspace(c) == 0; })); | |
} | |
inline void rtrim(std::string& s) { | |
s.erase(std::find_if(s.rbegin(), s.rend(), [](char c) { return std::isspace(c) == 0; }).base(), | |
s.end()); | |
} | |
inline std::string lpad(const std::string& s, size_t size) { | |
return (s.size() < size) ? std::string(size - s.size(), ' ') + s : s; | |
} | |
inline std::string rpad(const std::string& s, size_t size) { | |
return (s.size() < size) ? s + std::string(size - s.size(), ' ') : s; | |
} | |
inline void tolower(std::string& s) { | |
std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c) { return std::tolower(c); }); | |
} | |
inline void toupper(std::string& s) { | |
std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c) { return std::toupper(c); }); | |
} | |
// clang-format off | |
inline void trim(std::string& s) { ltrim(s); rtrim(s); } | |
inline std::string ltrim_copy(std::string s) { ltrim(s); return s; } | |
inline std::string rtrim_copy(std::string s) { rtrim(s); return s; } | |
inline std::string trim_copy(std::string s) { trim(s); return s; } | |
inline std::string tolower_copy(std::string s) { tolower(s); return s; } | |
inline std::string toupper_copy(std::string s) { toupper(s); return s; } | |
// clang-format on | |
// std::string_view equivalents. different implementation, and "_copy" only because cheap | |
inline std::string_view ltrim(std::string_view sv, | |
std::string_view ignore_chars = ascii::spacechars()) { | |
sv.remove_prefix(std::min(sv.find_first_not_of(ignore_chars), sv.size())); | |
return sv; | |
} | |
inline std::string_view rtrim(std::string_view sv, | |
std::string_view ignore_chars = ascii::spacechars()) { | |
auto last = sv.find_last_not_of(ignore_chars); | |
if (last != std::string_view::npos) sv.remove_suffix(sv.size() - last - 1); | |
return sv; | |
} | |
inline std::string_view trim(std::string_view sv, | |
std::string_view ignore_chars = ascii::spacechars()) { | |
return ltrim(rtrim(sv, ignore_chars), ignore_chars); | |
} | |
// std::string_view equivalents. different implementation, and "_copy" only because cheap | |
template <typename UnaryPredicate> | |
std::string_view ltrim_if(std::string_view sv, UnaryPredicate ischar) { | |
auto first = std::find_if(sv.begin(), sv.end(), ischar); | |
if (first != sv.end()) sv.remove_prefix(first - sv.begin()); | |
return sv; | |
} | |
template <typename UnaryPredicate> | |
std::string_view rtrim_if(std::string_view sv, UnaryPredicate ischar) { | |
auto last = find_if(sv.rbegin(), sv.rend(), ischar); | |
if (last != sv.rend()) sv.remove_suffix(sv.end() - last.base()); | |
return sv; | |
} | |
template <typename UnaryPredicate> | |
std::string_view trim_if(std::string_view sv, UnaryPredicate ischar) { | |
return ltrim_if(rtrim_if(sv, ischar), ischar); | |
} | |
inline std::optional<std::string> trim_lower(std::string_view word) { | |
word = trim_if(word, ascii::isalpha); | |
if (!word.empty()) { | |
std::string output{word}; | |
std::transform(output.begin(), output.end(), output.begin(), | |
[](auto c) { return ascii::tolower(c); }); | |
return std::optional<std::string>{output}; | |
} | |
return std::nullopt; | |
} | |
template <typename ActionFunction, typename Predicate = decltype(ascii::isalpha)> | |
void proc_words(std::string_view buffer, const ActionFunction& action, | |
const Predicate& pred = ascii::isalpha) { | |
const char* begin = buffer.begin(); | |
const char* curr = begin; | |
const char* const end = buffer.end(); | |
while (curr != end) { | |
if (!pred(*curr)) { | |
auto maybe_word = | |
trim_lower(std::string_view{&*begin, static_cast<std::size_t>(curr - begin)}); | |
if (maybe_word) action(*maybe_word); | |
begin = std::next(curr); | |
} | |
std::advance(curr, 1); | |
} | |
} | |
template <typename T> | |
T from_chars(std::string_view sv) { | |
T val; | |
std::from_chars(sv.data(), sv.data() + sv.size(), val); | |
return val; | |
} | |
inline std::vector<std::string> split(const std::string& str, const std::string& delim) { | |
std::vector<std::string> result; | |
size_t pos = str.find(delim); | |
size_t start = 0; | |
while (pos != std::string::npos) { | |
result.emplace_back(str.begin() + start, str.begin() + pos); | |
start = pos + delim.size(); | |
pos = str.find(delim, start); | |
} | |
if (start != str.size()) result.emplace_back(str.begin() + start, str.end()); | |
return result; | |
} | |
template <typename InputIt> | |
std::ostream& join(std::ostream& stream, InputIt begin, InputIt end, const std::string& glue = ", ", | |
const std::string& term = "") { | |
if (begin == end) return stream << term; | |
stream << *begin; | |
++begin; | |
while (begin != end) { | |
stream << glue; | |
stream << *begin; | |
++begin; | |
} | |
return stream << term; | |
} | |
template <typename InputIt> | |
std::string join(InputIt begin, InputIt end, const std::string& glue = ", ", | |
const std::string& term = "") { | |
std::ostringstream ss; | |
join(ss, begin, end, glue, term); | |
return ss.str(); | |
} | |
template <typename Container> | |
std::ostream& join(std::ostream& stream, Container cont, const std::string& glue = ", ", | |
const std::string& term = "") { | |
return join(stream, std::begin(cont), std::end(cont), glue, term); | |
} | |
template <typename Container> | |
std::string join(Container cont, const std::string& glue = ", ", const std::string& term = "") { | |
std::ostringstream ss; | |
join(ss, std::begin(cont), std::end(cont), glue, term); | |
return ss.str(); // can't call this on the rvalue above LWG#1203 | |
} | |
} // namespace os::str | |
// START main code | |
#include <cstdint> | |
#include <iostream> | |
#include <string> | |
#include <string_view> | |
std::uint64_t yahtzee_upper(const std::string& filename) { | |
auto mfile = os::fs::MemoryMappedFile{filename}; | |
auto max_total = std::uint64_t{0}; | |
auto accum = ska::bytell_hash_map<std::uint64_t, std::uint64_t>{}; | |
os::str::proc_words( | |
mfile.get_buffer(), | |
[&](std::string_view word) { | |
auto die = os::str::from_chars<std::uint64_t>(word); | |
auto total = accum[die] += die; | |
if (total > max_total) max_total = total; | |
}, | |
os::str::ascii::isnumeric); | |
return max_total; | |
} | |
int main(int argc, char* argv[]) { | |
if (argc < 2) return 1; | |
std::cout << yahtzee_upper(argv[1]) << std::endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment