24 #ifndef TSL_ARRAY_GROWTH_POLICY_H 25 #define TSL_ARRAY_GROWTH_POLICY_H 48 template<std::size_t GrowthFactor>
60 throw std::length_error(
"The hash table exceeds its maxmimum size.");
63 if(min_bucket_count_in_out > 0) {
64 min_bucket_count_in_out = round_up_to_power_of_two(min_bucket_count_in_out);
65 m_mask = min_bucket_count_in_out - 1;
85 throw std::length_error(
"The hash table exceeds its maxmimum size.");
88 return (
m_mask + 1) * GrowthFactor;
96 return (std::numeric_limits<std::size_t>::max() / 2) + 1;
108 static std::size_t round_up_to_power_of_two(std::size_t value) {
109 if(is_power_of_two(value)) {
118 for(std::size_t i = 1; i <
sizeof(std::size_t) * CHAR_BIT; i *= 2) {
125 static constexpr bool is_power_of_two(std::size_t value) {
126 return value != 0 && (value & (value - 1)) == 0;
130 static_assert(is_power_of_two(GrowthFactor) && GrowthFactor >= 2,
"GrowthFactor must be a power of two >= 2.");
140 template<
class GrowthFactor = std::ratio<3, 2>>
145 throw std::length_error(
"The hash table exceeds its maxmimum size.");
148 if(min_bucket_count_in_out > 0) {
149 m_mod = min_bucket_count_in_out;
162 throw std::length_error(
"The hash table exceeds its maxmimum size.");
165 const double next_bucket_count = std::ceil(
double(m_mod) * REHASH_SIZE_MULTIPLICATION_FACTOR);
166 if(!std::isnormal(next_bucket_count)) {
167 throw std::length_error(
"The hash table exceeds its maxmimum size.");
174 return std::size_t(next_bucket_count);
179 return MAX_BUCKET_COUNT;
187 static constexpr double REHASH_SIZE_MULTIPLICATION_FACTOR = 1.0 * GrowthFactor::num / GrowthFactor::den;
188 static const std::size_t MAX_BUCKET_COUNT =
190 std::numeric_limits<std::size_t>::max() / REHASH_SIZE_MULTIPLICATION_FACTOR
193 static_assert(REHASH_SIZE_MULTIPLICATION_FACTOR >= 1.1,
"Growth factor should be >= 1.1.");
202 static constexpr const std::array<std::size_t, 40> PRIMES = {{
203 1ul, 5ul, 17ul, 29ul, 37ul, 53ul, 67ul, 79ul, 97ul, 131ul, 193ul, 257ul, 389ul, 521ul, 769ul, 1031ul,
204 1543ul, 2053ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
205 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul,
206 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
209 template<
unsigned int IPrime>
210 static constexpr std::size_t mod(std::size_t hash) {
return hash % PRIMES[IPrime]; }
214 static constexpr const std::array<std::size_t(*)(std::size_t), 40> MOD_PRIME = {{
215 &mod<0>, &mod<1>, &mod<2>, &mod<3>, &mod<4>, &mod<5>, &mod<6>, &mod<7>, &mod<8>, &mod<9>, &mod<10>,
216 &mod<11>, &mod<12>, &mod<13>, &mod<14>, &mod<15>, &mod<16>, &mod<17>, &mod<18>, &mod<19>, &mod<20>,
217 &mod<21>, &mod<22>, &mod<23>, &mod<24>, &mod<25>, &mod<26>, &mod<27>, &mod<28>, &mod<29>, &mod<30>,
218 &mod<31>, &mod<32>, &mod<33>, &mod<34>, &mod<35>, &mod<36>, &mod<37> , &mod<38>, &mod<39>
250 auto it_prime = std::lower_bound(
detail::PRIMES.begin(),
251 detail::PRIMES.end(), min_bucket_count_in_out);
252 if(it_prime ==
detail::PRIMES.end()) {
253 throw std::length_error(
"The hash table exceeds its maxmimum size.");
256 m_iprime =
static_cast<
unsigned int>(std::distance(
detail::PRIMES.begin(), it_prime));
257 if(min_bucket_count_in_out > 0) {
258 min_bucket_count_in_out = *it_prime;
261 min_bucket_count_in_out = 0;
266 return detail::MOD_PRIME[m_iprime](hash);
270 if(m_iprime + 1 >=
detail::PRIMES.size()) {
271 throw std::length_error(
"The hash table exceeds its maxmimum size.");
274 return detail::PRIMES[m_iprime + 1];
278 return detail::PRIMES.back();
286 unsigned int m_iprime;
288 static_assert(std::numeric_limits<
decltype(m_iprime)>::max() >=
detail::PRIMES.size(),
289 "The type of m_iprime is not big enough.");
Definition: array_growth_policy.h:40
Definition: array_growth_policy.h:39
std::size_t m_mask
Definition: array_growth_policy.h:130
prime_growth_policy(std::size_t &min_bucket_count_in_out)
Definition: array_growth_policy.h:249
mod_growth_policy(std::size_t &min_bucket_count_in_out)
Definition: array_growth_policy.h:143
power_of_two_growth_policy(std::size_t &min_bucket_count_in_out)
Definition: array_growth_policy.h:58
std::size_t max_bucket_count() const
Definition: array_growth_policy.h:277
std::size_t max_bucket_count() const
Definition: array_growth_policy.h:178
void clear() noexcept
Definition: array_growth_policy.h:182
std::size_t bucket_for_hash(std::size_t hash) const noexcept
Definition: array_growth_policy.h:265
std::size_t max_bucket_count() const
Definition: array_growth_policy.h:94
void clear() noexcept
Definition: array_growth_policy.h:103
std::size_t next_bucket_count() const
Definition: array_growth_policy.h:83
Definition: array_growth_policy.h:200
Definition: array_growth_policy.h:141
std::size_t bucket_for_hash(std::size_t hash) const noexcept
Definition: array_growth_policy.h:156
void clear() noexcept
Definition: array_growth_policy.h:281
std::size_t bucket_for_hash(std::size_t hash) const noexcept
Definition: array_growth_policy.h:76
Definition: array_growth_policy.h:49
Definition: array_growth_policy.h:247
std::size_t next_bucket_count() const
Definition: array_growth_policy.h:269
std::size_t next_bucket_count() const
Definition: array_growth_policy.h:160