1 |
root |
1.1 |
// Copyright Malte Skarupke 2017. |
2 |
|
|
// Distributed under the Boost Software License, Version 1.0. |
3 |
|
|
// (See http://www.boost.org/LICENSE_1_0.txt) |
4 |
|
|
|
5 |
|
|
#pragma once |
6 |
|
|
|
7 |
|
|
#include <cstdint> |
8 |
|
|
#include <cstddef> |
9 |
|
|
#include <functional> |
10 |
|
|
#include <cmath> |
11 |
|
|
#include <algorithm> |
12 |
|
|
#include <iterator> |
13 |
|
|
#include <utility> |
14 |
|
|
#include <type_traits> |
15 |
|
|
|
16 |
|
|
#ifdef _MSC_VER |
17 |
|
|
#define SKA_NOINLINE(...) __declspec(noinline) __VA_ARGS__ |
18 |
|
|
#else |
19 |
|
|
#define SKA_NOINLINE(...) __VA_ARGS__ __attribute__((noinline)) |
20 |
|
|
#endif |
21 |
|
|
|
22 |
|
|
namespace ska |
23 |
|
|
{ |
24 |
|
|
struct prime_number_hash_policy; |
25 |
|
|
struct power_of_two_hash_policy; |
26 |
|
|
struct fibonacci_hash_policy; |
27 |
|
|
|
28 |
|
|
namespace detailv3 |
29 |
|
|
{ |
30 |
|
|
template<typename Result, typename Functor> |
31 |
|
|
struct functor_storage : Functor |
32 |
|
|
{ |
33 |
|
|
functor_storage() = default; |
34 |
|
|
functor_storage(const Functor & functor) |
35 |
|
|
: Functor(functor) |
36 |
|
|
{ |
37 |
|
|
} |
38 |
|
|
template<typename... Args> |
39 |
|
|
Result operator()(Args &&... args) |
40 |
|
|
{ |
41 |
|
|
return static_cast<Functor &>(*this)(std::forward<Args>(args)...); |
42 |
|
|
} |
43 |
|
|
template<typename... Args> |
44 |
|
|
Result operator()(Args &&... args) const |
45 |
|
|
{ |
46 |
|
|
return static_cast<const Functor &>(*this)(std::forward<Args>(args)...); |
47 |
|
|
} |
48 |
|
|
}; |
49 |
|
|
template<typename Result, typename... Args> |
50 |
|
|
struct functor_storage<Result, Result (*)(Args...)> |
51 |
|
|
{ |
52 |
|
|
typedef Result (*function_ptr)(Args...); |
53 |
|
|
function_ptr function; |
54 |
|
|
functor_storage(function_ptr function) |
55 |
|
|
: function(function) |
56 |
|
|
{ |
57 |
|
|
} |
58 |
|
|
Result operator()(Args... args) const |
59 |
|
|
{ |
60 |
|
|
return function(std::forward<Args>(args)...); |
61 |
|
|
} |
62 |
|
|
operator function_ptr &() |
63 |
|
|
{ |
64 |
|
|
return function; |
65 |
|
|
} |
66 |
|
|
operator const function_ptr &() |
67 |
|
|
{ |
68 |
|
|
return function; |
69 |
|
|
} |
70 |
|
|
}; |
71 |
|
|
template<typename key_type, typename value_type, typename hasher> |
72 |
|
|
struct KeyOrValueHasher : functor_storage<size_t, hasher> |
73 |
|
|
{ |
74 |
|
|
typedef functor_storage<size_t, hasher> hasher_storage; |
75 |
|
|
KeyOrValueHasher() = default; |
76 |
|
|
KeyOrValueHasher(const hasher & hash) |
77 |
|
|
: hasher_storage(hash) |
78 |
|
|
{ |
79 |
|
|
} |
80 |
|
|
size_t operator()(const key_type & key) |
81 |
|
|
{ |
82 |
|
|
return static_cast<hasher_storage &>(*this)(key); |
83 |
|
|
} |
84 |
|
|
size_t operator()(const key_type & key) const |
85 |
|
|
{ |
86 |
|
|
return static_cast<const hasher_storage &>(*this)(key); |
87 |
|
|
} |
88 |
|
|
size_t operator()(const value_type & value) |
89 |
|
|
{ |
90 |
|
|
return static_cast<hasher_storage &>(*this)(value.first); |
91 |
|
|
} |
92 |
|
|
size_t operator()(const value_type & value) const |
93 |
|
|
{ |
94 |
|
|
return static_cast<const hasher_storage &>(*this)(value.first); |
95 |
|
|
} |
96 |
|
|
template<typename F, typename S> |
97 |
|
|
size_t operator()(const std::pair<F, S> & value) |
98 |
|
|
{ |
99 |
|
|
return static_cast<hasher_storage &>(*this)(value.first); |
100 |
|
|
} |
101 |
|
|
template<typename F, typename S> |
102 |
|
|
size_t operator()(const std::pair<F, S> & value) const |
103 |
|
|
{ |
104 |
|
|
return static_cast<const hasher_storage &>(*this)(value.first); |
105 |
|
|
} |
106 |
|
|
}; |
107 |
|
|
template<typename key_type, typename value_type, typename key_equal> |
108 |
|
|
struct KeyOrValueEquality : functor_storage<bool, key_equal> |
109 |
|
|
{ |
110 |
|
|
typedef functor_storage<bool, key_equal> equality_storage; |
111 |
|
|
KeyOrValueEquality() = default; |
112 |
|
|
KeyOrValueEquality(const key_equal & equality) |
113 |
|
|
: equality_storage(equality) |
114 |
|
|
{ |
115 |
|
|
} |
116 |
|
|
bool operator()(const key_type & lhs, const key_type & rhs) |
117 |
|
|
{ |
118 |
|
|
return static_cast<equality_storage &>(*this)(lhs, rhs); |
119 |
|
|
} |
120 |
|
|
bool operator()(const key_type & lhs, const value_type & rhs) |
121 |
|
|
{ |
122 |
|
|
return static_cast<equality_storage &>(*this)(lhs, rhs.first); |
123 |
|
|
} |
124 |
|
|
bool operator()(const value_type & lhs, const key_type & rhs) |
125 |
|
|
{ |
126 |
|
|
return static_cast<equality_storage &>(*this)(lhs.first, rhs); |
127 |
|
|
} |
128 |
|
|
bool operator()(const value_type & lhs, const value_type & rhs) |
129 |
|
|
{ |
130 |
|
|
return static_cast<equality_storage &>(*this)(lhs.first, rhs.first); |
131 |
|
|
} |
132 |
|
|
template<typename F, typename S> |
133 |
|
|
bool operator()(const key_type & lhs, const std::pair<F, S> & rhs) |
134 |
|
|
{ |
135 |
|
|
return static_cast<equality_storage &>(*this)(lhs, rhs.first); |
136 |
|
|
} |
137 |
|
|
template<typename F, typename S> |
138 |
|
|
bool operator()(const std::pair<F, S> & lhs, const key_type & rhs) |
139 |
|
|
{ |
140 |
|
|
return static_cast<equality_storage &>(*this)(lhs.first, rhs); |
141 |
|
|
} |
142 |
|
|
template<typename F, typename S> |
143 |
|
|
bool operator()(const value_type & lhs, const std::pair<F, S> & rhs) |
144 |
|
|
{ |
145 |
|
|
return static_cast<equality_storage &>(*this)(lhs.first, rhs.first); |
146 |
|
|
} |
147 |
|
|
template<typename F, typename S> |
148 |
|
|
bool operator()(const std::pair<F, S> & lhs, const value_type & rhs) |
149 |
|
|
{ |
150 |
|
|
return static_cast<equality_storage &>(*this)(lhs.first, rhs.first); |
151 |
|
|
} |
152 |
|
|
template<typename FL, typename SL, typename FR, typename SR> |
153 |
|
|
bool operator()(const std::pair<FL, SL> & lhs, const std::pair<FR, SR> & rhs) |
154 |
|
|
{ |
155 |
|
|
return static_cast<equality_storage &>(*this)(lhs.first, rhs.first); |
156 |
|
|
} |
157 |
|
|
}; |
158 |
|
|
static constexpr int8_t min_lookups = 4; |
159 |
|
|
template<typename T> |
160 |
|
|
struct sherwood_v3_entry |
161 |
|
|
{ |
162 |
|
|
sherwood_v3_entry() |
163 |
|
|
{ |
164 |
|
|
} |
165 |
|
|
sherwood_v3_entry(int8_t distance_from_desired) |
166 |
|
|
: distance_from_desired(distance_from_desired) |
167 |
|
|
{ |
168 |
|
|
} |
169 |
|
|
~sherwood_v3_entry() |
170 |
|
|
{ |
171 |
|
|
} |
172 |
|
|
static sherwood_v3_entry * empty_default_table() |
173 |
|
|
{ |
174 |
|
|
static sherwood_v3_entry result[min_lookups] = { {}, {}, {}, {special_end_value} }; |
175 |
|
|
return result; |
176 |
|
|
} |
177 |
|
|
|
178 |
|
|
bool has_value() const |
179 |
|
|
{ |
180 |
|
|
return distance_from_desired >= 0; |
181 |
|
|
} |
182 |
|
|
bool is_empty() const |
183 |
|
|
{ |
184 |
|
|
return distance_from_desired < 0; |
185 |
|
|
} |
186 |
|
|
bool is_at_desired_position() const |
187 |
|
|
{ |
188 |
|
|
return distance_from_desired <= 0; |
189 |
|
|
} |
190 |
|
|
template<typename... Args> |
191 |
|
|
void emplace(int8_t distance, Args &&... args) |
192 |
|
|
{ |
193 |
|
|
new (std::addressof(value)) T(std::forward<Args>(args)...); |
194 |
|
|
distance_from_desired = distance; |
195 |
|
|
} |
196 |
|
|
|
197 |
|
|
void destroy_value() |
198 |
|
|
{ |
199 |
|
|
value.~T(); |
200 |
|
|
distance_from_desired = -1; |
201 |
|
|
} |
202 |
|
|
|
203 |
|
|
int8_t distance_from_desired = -1; |
204 |
|
|
static constexpr int8_t special_end_value = 0; |
205 |
|
|
union { T value; }; |
206 |
|
|
}; |
207 |
|
|
|
208 |
|
|
inline int8_t log2(size_t value) |
209 |
|
|
{ |
210 |
|
|
static constexpr int8_t table[64] = |
211 |
|
|
{ |
212 |
|
|
63, 0, 58, 1, 59, 47, 53, 2, |
213 |
|
|
60, 39, 48, 27, 54, 33, 42, 3, |
214 |
|
|
61, 51, 37, 40, 49, 18, 28, 20, |
215 |
|
|
55, 30, 34, 11, 43, 14, 22, 4, |
216 |
|
|
62, 57, 46, 52, 38, 26, 32, 41, |
217 |
|
|
50, 36, 17, 19, 29, 10, 13, 21, |
218 |
|
|
56, 45, 25, 31, 35, 16, 9, 12, |
219 |
|
|
44, 24, 15, 8, 23, 7, 6, 5 |
220 |
|
|
}; |
221 |
|
|
value |= value >> 1; |
222 |
|
|
value |= value >> 2; |
223 |
|
|
value |= value >> 4; |
224 |
|
|
value |= value >> 8; |
225 |
|
|
value |= value >> 16; |
226 |
|
|
value |= value >> 32; |
227 |
|
|
return table[((value - (value >> 1)) * 0x07EDD5E59A4E28C2) >> 58]; |
228 |
|
|
} |
229 |
|
|
|
230 |
|
|
template<typename T, bool> |
231 |
|
|
struct AssignIfTrue |
232 |
|
|
{ |
233 |
|
|
void operator()(T & lhs, const T & rhs) |
234 |
|
|
{ |
235 |
|
|
lhs = rhs; |
236 |
|
|
} |
237 |
|
|
void operator()(T & lhs, T && rhs) |
238 |
|
|
{ |
239 |
|
|
lhs = std::move(rhs); |
240 |
|
|
} |
241 |
|
|
}; |
242 |
|
|
template<typename T> |
243 |
|
|
struct AssignIfTrue<T, false> |
244 |
|
|
{ |
245 |
|
|
void operator()(T &, const T &) |
246 |
|
|
{ |
247 |
|
|
} |
248 |
|
|
void operator()(T &, T &&) |
249 |
|
|
{ |
250 |
|
|
} |
251 |
|
|
}; |
252 |
|
|
|
253 |
|
|
inline size_t next_power_of_two(size_t i) |
254 |
|
|
{ |
255 |
|
|
--i; |
256 |
|
|
i |= i >> 1; |
257 |
|
|
i |= i >> 2; |
258 |
|
|
i |= i >> 4; |
259 |
|
|
i |= i >> 8; |
260 |
|
|
i |= i >> 16; |
261 |
|
|
i |= i >> 32; |
262 |
|
|
++i; |
263 |
|
|
return i; |
264 |
|
|
} |
265 |
|
|
|
266 |
|
|
template<typename...> using void_t = void; |
267 |
|
|
|
268 |
|
|
template<typename T, typename = void> |
269 |
|
|
struct HashPolicySelector |
270 |
|
|
{ |
271 |
|
|
typedef fibonacci_hash_policy type; |
272 |
|
|
}; |
273 |
|
|
template<typename T> |
274 |
|
|
struct HashPolicySelector<T, void_t<typename T::hash_policy>> |
275 |
|
|
{ |
276 |
|
|
typedef typename T::hash_policy type; |
277 |
|
|
}; |
278 |
|
|
|
279 |
|
|
template<typename T, typename FindKey, typename ArgumentHash, typename Hasher, typename ArgumentEqual, typename Equal, typename ArgumentAlloc, typename EntryAlloc> |
280 |
|
|
class sherwood_v3_table : private EntryAlloc, private Hasher, private Equal |
281 |
|
|
{ |
282 |
|
|
using Entry = detailv3::sherwood_v3_entry<T>; |
283 |
|
|
using AllocatorTraits = std::allocator_traits<EntryAlloc>; |
284 |
|
|
using EntryPointer = typename AllocatorTraits::pointer; |
285 |
|
|
struct convertible_to_iterator; |
286 |
|
|
|
287 |
|
|
public: |
288 |
|
|
|
289 |
|
|
using value_type = T; |
290 |
|
|
using size_type = size_t; |
291 |
|
|
using difference_type = std::ptrdiff_t; |
292 |
|
|
using hasher = ArgumentHash; |
293 |
|
|
using key_equal = ArgumentEqual; |
294 |
|
|
using allocator_type = EntryAlloc; |
295 |
|
|
using reference = value_type &; |
296 |
|
|
using const_reference = const value_type &; |
297 |
|
|
using pointer = value_type *; |
298 |
|
|
using const_pointer = const value_type *; |
299 |
|
|
|
300 |
|
|
sherwood_v3_table() |
301 |
|
|
{ |
302 |
|
|
} |
303 |
|
|
explicit sherwood_v3_table(size_type bucket_count, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc()) |
304 |
|
|
: EntryAlloc(alloc), Hasher(hash), Equal(equal) |
305 |
|
|
{ |
306 |
|
|
rehash(bucket_count); |
307 |
|
|
} |
308 |
|
|
sherwood_v3_table(size_type bucket_count, const ArgumentAlloc & alloc) |
309 |
|
|
: sherwood_v3_table(bucket_count, ArgumentHash(), ArgumentEqual(), alloc) |
310 |
|
|
{ |
311 |
|
|
} |
312 |
|
|
sherwood_v3_table(size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc) |
313 |
|
|
: sherwood_v3_table(bucket_count, hash, ArgumentEqual(), alloc) |
314 |
|
|
{ |
315 |
|
|
} |
316 |
|
|
explicit sherwood_v3_table(const ArgumentAlloc & alloc) |
317 |
|
|
: EntryAlloc(alloc) |
318 |
|
|
{ |
319 |
|
|
} |
320 |
|
|
template<typename It> |
321 |
|
|
sherwood_v3_table(It first, It last, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc()) |
322 |
|
|
: sherwood_v3_table(bucket_count, hash, equal, alloc) |
323 |
|
|
{ |
324 |
|
|
insert(first, last); |
325 |
|
|
} |
326 |
|
|
template<typename It> |
327 |
|
|
sherwood_v3_table(It first, It last, size_type bucket_count, const ArgumentAlloc & alloc) |
328 |
|
|
: sherwood_v3_table(first, last, bucket_count, ArgumentHash(), ArgumentEqual(), alloc) |
329 |
|
|
{ |
330 |
|
|
} |
331 |
|
|
template<typename It> |
332 |
|
|
sherwood_v3_table(It first, It last, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc) |
333 |
|
|
: sherwood_v3_table(first, last, bucket_count, hash, ArgumentEqual(), alloc) |
334 |
|
|
{ |
335 |
|
|
} |
336 |
|
|
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()) |
337 |
|
|
: sherwood_v3_table(bucket_count, hash, equal, alloc) |
338 |
|
|
{ |
339 |
|
|
if (bucket_count == 0) |
340 |
|
|
rehash(il.size()); |
341 |
|
|
insert(il.begin(), il.end()); |
342 |
|
|
} |
343 |
|
|
sherwood_v3_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentAlloc & alloc) |
344 |
|
|
: sherwood_v3_table(il, bucket_count, ArgumentHash(), ArgumentEqual(), alloc) |
345 |
|
|
{ |
346 |
|
|
} |
347 |
|
|
sherwood_v3_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc) |
348 |
|
|
: sherwood_v3_table(il, bucket_count, hash, ArgumentEqual(), alloc) |
349 |
|
|
{ |
350 |
|
|
} |
351 |
|
|
sherwood_v3_table(const sherwood_v3_table & other) |
352 |
|
|
: sherwood_v3_table(other, AllocatorTraits::select_on_container_copy_construction(other.get_allocator())) |
353 |
|
|
{ |
354 |
|
|
} |
355 |
|
|
sherwood_v3_table(const sherwood_v3_table & other, const ArgumentAlloc & alloc) |
356 |
|
|
: EntryAlloc(alloc), Hasher(other), Equal(other), _max_load_factor(other._max_load_factor) |
357 |
|
|
{ |
358 |
|
|
rehash_for_other_container(other); |
359 |
|
|
try |
360 |
|
|
{ |
361 |
|
|
insert(other.begin(), other.end()); |
362 |
|
|
} |
363 |
|
|
catch(...) |
364 |
|
|
{ |
365 |
|
|
clear(); |
366 |
|
|
deallocate_data(entries, num_slots_minus_one, max_lookups); |
367 |
|
|
throw; |
368 |
|
|
} |
369 |
|
|
} |
370 |
|
|
sherwood_v3_table(sherwood_v3_table && other) noexcept |
371 |
|
|
: EntryAlloc(std::move(other)), Hasher(std::move(other)), Equal(std::move(other)) |
372 |
|
|
{ |
373 |
|
|
swap_pointers(other); |
374 |
|
|
} |
375 |
|
|
sherwood_v3_table(sherwood_v3_table && other, const ArgumentAlloc & alloc) noexcept |
376 |
|
|
: EntryAlloc(alloc), Hasher(std::move(other)), Equal(std::move(other)) |
377 |
|
|
{ |
378 |
|
|
swap_pointers(other); |
379 |
|
|
} |
380 |
|
|
sherwood_v3_table & operator=(const sherwood_v3_table & other) |
381 |
|
|
{ |
382 |
|
|
if (this == std::addressof(other)) |
383 |
|
|
return *this; |
384 |
|
|
|
385 |
|
|
clear(); |
386 |
|
|
if (AllocatorTraits::propagate_on_container_copy_assignment::value) |
387 |
|
|
{ |
388 |
|
|
if (static_cast<EntryAlloc &>(*this) != static_cast<const EntryAlloc &>(other)) |
389 |
|
|
{ |
390 |
|
|
reset_to_empty_state(); |
391 |
|
|
} |
392 |
|
|
AssignIfTrue<EntryAlloc, AllocatorTraits::propagate_on_container_copy_assignment::value>()(*this, other); |
393 |
|
|
} |
394 |
|
|
_max_load_factor = other._max_load_factor; |
395 |
|
|
static_cast<Hasher &>(*this) = other; |
396 |
|
|
static_cast<Equal &>(*this) = other; |
397 |
|
|
rehash_for_other_container(other); |
398 |
|
|
insert(other.begin(), other.end()); |
399 |
|
|
return *this; |
400 |
|
|
} |
401 |
|
|
sherwood_v3_table & operator=(sherwood_v3_table && other) noexcept |
402 |
|
|
{ |
403 |
|
|
if (this == std::addressof(other)) |
404 |
|
|
return *this; |
405 |
|
|
else if (AllocatorTraits::propagate_on_container_move_assignment::value) |
406 |
|
|
{ |
407 |
|
|
clear(); |
408 |
|
|
reset_to_empty_state(); |
409 |
|
|
AssignIfTrue<EntryAlloc, AllocatorTraits::propagate_on_container_move_assignment::value>()(*this, std::move(other)); |
410 |
|
|
swap_pointers(other); |
411 |
|
|
} |
412 |
|
|
else if (static_cast<EntryAlloc &>(*this) == static_cast<EntryAlloc &>(other)) |
413 |
|
|
{ |
414 |
|
|
swap_pointers(other); |
415 |
|
|
} |
416 |
|
|
else |
417 |
|
|
{ |
418 |
|
|
clear(); |
419 |
|
|
_max_load_factor = other._max_load_factor; |
420 |
|
|
rehash_for_other_container(other); |
421 |
|
|
for (T & elem : other) |
422 |
|
|
emplace(std::move(elem)); |
423 |
|
|
other.clear(); |
424 |
|
|
} |
425 |
|
|
static_cast<Hasher &>(*this) = std::move(other); |
426 |
|
|
static_cast<Equal &>(*this) = std::move(other); |
427 |
|
|
return *this; |
428 |
|
|
} |
429 |
|
|
~sherwood_v3_table() |
430 |
|
|
{ |
431 |
|
|
clear(); |
432 |
|
|
deallocate_data(entries, num_slots_minus_one, max_lookups); |
433 |
|
|
} |
434 |
|
|
|
435 |
|
|
const allocator_type & get_allocator() const |
436 |
|
|
{ |
437 |
|
|
return static_cast<const allocator_type &>(*this); |
438 |
|
|
} |
439 |
|
|
const ArgumentEqual & key_eq() const |
440 |
|
|
{ |
441 |
|
|
return static_cast<const ArgumentEqual &>(*this); |
442 |
|
|
} |
443 |
|
|
const ArgumentHash & hash_function() const |
444 |
|
|
{ |
445 |
|
|
return static_cast<const ArgumentHash &>(*this); |
446 |
|
|
} |
447 |
|
|
|
448 |
|
|
template<typename ValueType> |
449 |
|
|
struct templated_iterator |
450 |
|
|
{ |
451 |
|
|
templated_iterator() = default; |
452 |
|
|
templated_iterator(EntryPointer current) |
453 |
|
|
: current(current) |
454 |
|
|
{ |
455 |
|
|
} |
456 |
|
|
EntryPointer current = EntryPointer(); |
457 |
|
|
|
458 |
|
|
using iterator_category = std::forward_iterator_tag; |
459 |
|
|
using value_type = ValueType; |
460 |
|
|
using difference_type = ptrdiff_t; |
461 |
|
|
using pointer = ValueType *; |
462 |
|
|
using reference = ValueType &; |
463 |
|
|
|
464 |
|
|
friend bool operator==(const templated_iterator & lhs, const templated_iterator & rhs) |
465 |
|
|
{ |
466 |
|
|
return lhs.current == rhs.current; |
467 |
|
|
} |
468 |
|
|
friend bool operator!=(const templated_iterator & lhs, const templated_iterator & rhs) |
469 |
|
|
{ |
470 |
|
|
return !(lhs == rhs); |
471 |
|
|
} |
472 |
|
|
|
473 |
|
|
templated_iterator & operator++() |
474 |
|
|
{ |
475 |
|
|
do |
476 |
|
|
{ |
477 |
|
|
++current; |
478 |
|
|
} |
479 |
|
|
while(current->is_empty()); |
480 |
|
|
return *this; |
481 |
|
|
} |
482 |
|
|
templated_iterator operator++(int) |
483 |
|
|
{ |
484 |
|
|
templated_iterator copy(*this); |
485 |
|
|
++*this; |
486 |
|
|
return copy; |
487 |
|
|
} |
488 |
|
|
|
489 |
|
|
ValueType & operator*() const |
490 |
|
|
{ |
491 |
|
|
return current->value; |
492 |
|
|
} |
493 |
|
|
ValueType * operator->() const |
494 |
|
|
{ |
495 |
|
|
return std::addressof(current->value); |
496 |
|
|
} |
497 |
|
|
|
498 |
|
|
operator templated_iterator<const value_type>() const |
499 |
|
|
{ |
500 |
|
|
return { current }; |
501 |
|
|
} |
502 |
|
|
}; |
503 |
|
|
using iterator = templated_iterator<value_type>; |
504 |
|
|
using const_iterator = templated_iterator<const value_type>; |
505 |
|
|
|
506 |
|
|
iterator begin() |
507 |
|
|
{ |
508 |
|
|
for (EntryPointer it = entries;; ++it) |
509 |
|
|
{ |
510 |
|
|
if (it->has_value()) |
511 |
|
|
return { it }; |
512 |
|
|
} |
513 |
|
|
} |
514 |
|
|
const_iterator begin() const |
515 |
|
|
{ |
516 |
|
|
for (EntryPointer it = entries;; ++it) |
517 |
|
|
{ |
518 |
|
|
if (it->has_value()) |
519 |
|
|
return { it }; |
520 |
|
|
} |
521 |
|
|
} |
522 |
|
|
const_iterator cbegin() const |
523 |
|
|
{ |
524 |
|
|
return begin(); |
525 |
|
|
} |
526 |
|
|
iterator end() |
527 |
|
|
{ |
528 |
|
|
return { entries + static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups) }; |
529 |
|
|
} |
530 |
|
|
const_iterator end() const |
531 |
|
|
{ |
532 |
|
|
return { entries + static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups) }; |
533 |
|
|
} |
534 |
|
|
const_iterator cend() const |
535 |
|
|
{ |
536 |
|
|
return end(); |
537 |
|
|
} |
538 |
|
|
|
539 |
|
|
iterator find(const FindKey & key) |
540 |
|
|
{ |
541 |
|
|
size_t index = hash_policy.index_for_hash(hash_object(key), num_slots_minus_one); |
542 |
|
|
EntryPointer it = entries + ptrdiff_t(index); |
543 |
|
|
for (int8_t distance = 0; it->distance_from_desired >= distance; ++distance, ++it) |
544 |
|
|
{ |
545 |
|
|
if (compares_equal(key, it->value)) |
546 |
|
|
return { it }; |
547 |
|
|
} |
548 |
|
|
return end(); |
549 |
|
|
} |
550 |
|
|
const_iterator find(const FindKey & key) const |
551 |
|
|
{ |
552 |
|
|
return const_cast<sherwood_v3_table *>(this)->find(key); |
553 |
|
|
} |
554 |
|
|
size_t count(const FindKey & key) const |
555 |
|
|
{ |
556 |
|
|
return find(key) == end() ? 0 : 1; |
557 |
|
|
} |
558 |
|
|
std::pair<iterator, iterator> equal_range(const FindKey & key) |
559 |
|
|
{ |
560 |
|
|
iterator found = find(key); |
561 |
|
|
if (found == end()) |
562 |
|
|
return { found, found }; |
563 |
|
|
else |
564 |
|
|
return { found, std::next(found) }; |
565 |
|
|
} |
566 |
|
|
std::pair<const_iterator, const_iterator> equal_range(const FindKey & key) const |
567 |
|
|
{ |
568 |
|
|
const_iterator found = find(key); |
569 |
|
|
if (found == end()) |
570 |
|
|
return { found, found }; |
571 |
|
|
else |
572 |
|
|
return { found, std::next(found) }; |
573 |
|
|
} |
574 |
|
|
|
575 |
|
|
template<typename Key, typename... Args> |
576 |
|
|
std::pair<iterator, bool> emplace(Key && key, Args &&... args) |
577 |
|
|
{ |
578 |
|
|
size_t index = hash_policy.index_for_hash(hash_object(key), num_slots_minus_one); |
579 |
|
|
EntryPointer current_entry = entries + ptrdiff_t(index); |
580 |
|
|
int8_t distance_from_desired = 0; |
581 |
|
|
for (; current_entry->distance_from_desired >= distance_from_desired; ++current_entry, ++distance_from_desired) |
582 |
|
|
{ |
583 |
|
|
if (compares_equal(key, current_entry->value)) |
584 |
|
|
return { { current_entry }, false }; |
585 |
|
|
} |
586 |
|
|
return emplace_new_key(distance_from_desired, current_entry, std::forward<Key>(key), std::forward<Args>(args)...); |
587 |
|
|
} |
588 |
|
|
|
589 |
|
|
std::pair<iterator, bool> insert(const value_type & value) |
590 |
|
|
{ |
591 |
|
|
return emplace(value); |
592 |
|
|
} |
593 |
|
|
std::pair<iterator, bool> insert(value_type && value) |
594 |
|
|
{ |
595 |
|
|
return emplace(std::move(value)); |
596 |
|
|
} |
597 |
|
|
template<typename... Args> |
598 |
|
|
iterator emplace_hint(const_iterator, Args &&... args) |
599 |
|
|
{ |
600 |
|
|
return emplace(std::forward<Args>(args)...).first; |
601 |
|
|
} |
602 |
|
|
iterator insert(const_iterator, const value_type & value) |
603 |
|
|
{ |
604 |
|
|
return emplace(value).first; |
605 |
|
|
} |
606 |
|
|
iterator insert(const_iterator, value_type && value) |
607 |
|
|
{ |
608 |
|
|
return emplace(std::move(value)).first; |
609 |
|
|
} |
610 |
|
|
|
611 |
|
|
template<typename It> |
612 |
|
|
void insert(It begin, It end) |
613 |
|
|
{ |
614 |
|
|
for (; begin != end; ++begin) |
615 |
|
|
{ |
616 |
|
|
emplace(*begin); |
617 |
|
|
} |
618 |
|
|
} |
619 |
|
|
void insert(std::initializer_list<value_type> il) |
620 |
|
|
{ |
621 |
|
|
insert(il.begin(), il.end()); |
622 |
|
|
} |
623 |
|
|
|
624 |
|
|
void rehash(size_t num_buckets) |
625 |
|
|
{ |
626 |
|
|
num_buckets = std::max(num_buckets, static_cast<size_t>(std::ceil(num_elements / static_cast<double>(_max_load_factor)))); |
627 |
|
|
if (num_buckets == 0) |
628 |
|
|
{ |
629 |
|
|
reset_to_empty_state(); |
630 |
|
|
return; |
631 |
|
|
} |
632 |
|
|
auto new_prime_index = hash_policy.next_size_over(num_buckets); |
633 |
|
|
if (num_buckets == bucket_count()) |
634 |
|
|
return; |
635 |
|
|
int8_t new_max_lookups = compute_max_lookups(num_buckets); |
636 |
|
|
EntryPointer new_buckets(AllocatorTraits::allocate(*this, num_buckets + new_max_lookups)); |
637 |
|
|
EntryPointer special_end_item = new_buckets + static_cast<ptrdiff_t>(num_buckets + new_max_lookups - 1); |
638 |
|
|
for (EntryPointer it = new_buckets; it != special_end_item; ++it) |
639 |
|
|
it->distance_from_desired = -1; |
640 |
|
|
special_end_item->distance_from_desired = Entry::special_end_value; |
641 |
|
|
std::swap(entries, new_buckets); |
642 |
|
|
std::swap(num_slots_minus_one, num_buckets); |
643 |
|
|
--num_slots_minus_one; |
644 |
|
|
hash_policy.commit(new_prime_index); |
645 |
|
|
int8_t old_max_lookups = max_lookups; |
646 |
|
|
max_lookups = new_max_lookups; |
647 |
|
|
num_elements = 0; |
648 |
|
|
for (EntryPointer it = new_buckets, end = it + static_cast<ptrdiff_t>(num_buckets + old_max_lookups); it != end; ++it) |
649 |
|
|
{ |
650 |
|
|
if (it->has_value()) |
651 |
|
|
{ |
652 |
|
|
emplace(std::move(it->value)); |
653 |
|
|
it->destroy_value(); |
654 |
|
|
} |
655 |
|
|
} |
656 |
|
|
deallocate_data(new_buckets, num_buckets, old_max_lookups); |
657 |
|
|
} |
658 |
|
|
|
659 |
|
|
void reserve(size_t num_elements) |
660 |
|
|
{ |
661 |
|
|
size_t required_buckets = num_buckets_for_reserve(num_elements); |
662 |
|
|
if (required_buckets > bucket_count()) |
663 |
|
|
rehash(required_buckets); |
664 |
|
|
} |
665 |
|
|
|
666 |
|
|
// the return value is a type that can be converted to an iterator |
667 |
|
|
// the reason for doing this is that it's not free to find the |
668 |
|
|
// iterator pointing at the next element. if you care about the |
669 |
|
|
// next iterator, turn the return value into an iterator |
670 |
|
|
convertible_to_iterator erase(const_iterator to_erase) |
671 |
|
|
{ |
672 |
|
|
EntryPointer current = to_erase.current; |
673 |
|
|
current->destroy_value(); |
674 |
|
|
--num_elements; |
675 |
|
|
for (EntryPointer next = current + ptrdiff_t(1); !next->is_at_desired_position(); ++current, ++next) |
676 |
|
|
{ |
677 |
|
|
current->emplace(next->distance_from_desired - 1, std::move(next->value)); |
678 |
|
|
next->destroy_value(); |
679 |
|
|
} |
680 |
|
|
return { to_erase.current }; |
681 |
|
|
} |
682 |
|
|
|
683 |
|
|
iterator erase(const_iterator begin_it, const_iterator end_it) |
684 |
|
|
{ |
685 |
|
|
if (begin_it == end_it) |
686 |
|
|
return { begin_it.current }; |
687 |
|
|
for (EntryPointer it = begin_it.current, end = end_it.current; it != end; ++it) |
688 |
|
|
{ |
689 |
|
|
if (it->has_value()) |
690 |
|
|
{ |
691 |
|
|
it->destroy_value(); |
692 |
|
|
--num_elements; |
693 |
|
|
} |
694 |
|
|
} |
695 |
|
|
if (end_it == this->end()) |
696 |
|
|
return this->end(); |
697 |
|
|
ptrdiff_t num_to_move = std::min(static_cast<ptrdiff_t>(end_it.current->distance_from_desired), end_it.current - begin_it.current); |
698 |
|
|
EntryPointer to_return = end_it.current - num_to_move; |
699 |
|
|
for (EntryPointer it = end_it.current; !it->is_at_desired_position();) |
700 |
|
|
{ |
701 |
|
|
EntryPointer target = it - num_to_move; |
702 |
|
|
target->emplace(it->distance_from_desired - num_to_move, std::move(it->value)); |
703 |
|
|
it->destroy_value(); |
704 |
|
|
++it; |
705 |
|
|
num_to_move = std::min(static_cast<ptrdiff_t>(it->distance_from_desired), num_to_move); |
706 |
|
|
} |
707 |
|
|
return { to_return }; |
708 |
|
|
} |
709 |
|
|
|
710 |
|
|
size_t erase(const FindKey & key) |
711 |
|
|
{ |
712 |
|
|
auto found = find(key); |
713 |
|
|
if (found == end()) |
714 |
|
|
return 0; |
715 |
|
|
else |
716 |
|
|
{ |
717 |
|
|
erase(found); |
718 |
|
|
return 1; |
719 |
|
|
} |
720 |
|
|
} |
721 |
|
|
|
722 |
|
|
void clear() |
723 |
|
|
{ |
724 |
|
|
for (EntryPointer it = entries, end = it + static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups); it != end; ++it) |
725 |
|
|
{ |
726 |
|
|
if (it->has_value()) |
727 |
|
|
it->destroy_value(); |
728 |
|
|
} |
729 |
|
|
num_elements = 0; |
730 |
|
|
} |
731 |
|
|
|
732 |
|
|
void shrink_to_fit() |
733 |
|
|
{ |
734 |
|
|
rehash_for_other_container(*this); |
735 |
|
|
} |
736 |
|
|
|
737 |
|
|
void swap(sherwood_v3_table & other) |
738 |
|
|
{ |
739 |
|
|
using std::swap; |
740 |
|
|
swap_pointers(other); |
741 |
|
|
swap(static_cast<ArgumentHash &>(*this), static_cast<ArgumentHash &>(other)); |
742 |
|
|
swap(static_cast<ArgumentEqual &>(*this), static_cast<ArgumentEqual &>(other)); |
743 |
|
|
if (AllocatorTraits::propagate_on_container_swap::value) |
744 |
|
|
swap(static_cast<EntryAlloc &>(*this), static_cast<EntryAlloc &>(other)); |
745 |
|
|
} |
746 |
|
|
|
747 |
|
|
size_t size() const |
748 |
|
|
{ |
749 |
|
|
return num_elements; |
750 |
|
|
} |
751 |
|
|
size_t max_size() const |
752 |
|
|
{ |
753 |
|
|
return (AllocatorTraits::max_size(*this)) / sizeof(Entry); |
754 |
|
|
} |
755 |
|
|
size_t bucket_count() const |
756 |
|
|
{ |
757 |
|
|
return num_slots_minus_one ? num_slots_minus_one + 1 : 0; |
758 |
|
|
} |
759 |
|
|
size_type max_bucket_count() const |
760 |
|
|
{ |
761 |
|
|
return (AllocatorTraits::max_size(*this) - min_lookups) / sizeof(Entry); |
762 |
|
|
} |
763 |
|
|
size_t bucket(const FindKey & key) const |
764 |
|
|
{ |
765 |
|
|
return hash_policy.index_for_hash(hash_object(key), num_slots_minus_one); |
766 |
|
|
} |
767 |
|
|
float load_factor() const |
768 |
|
|
{ |
769 |
|
|
size_t buckets = bucket_count(); |
770 |
|
|
if (buckets) |
771 |
|
|
return static_cast<float>(num_elements) / bucket_count(); |
772 |
|
|
else |
773 |
|
|
return 0; |
774 |
|
|
} |
775 |
|
|
void max_load_factor(float value) |
776 |
|
|
{ |
777 |
|
|
_max_load_factor = value; |
778 |
|
|
} |
779 |
|
|
float max_load_factor() const |
780 |
|
|
{ |
781 |
|
|
return _max_load_factor; |
782 |
|
|
} |
783 |
|
|
|
784 |
|
|
bool empty() const |
785 |
|
|
{ |
786 |
|
|
return num_elements == 0; |
787 |
|
|
} |
788 |
|
|
|
789 |
|
|
private: |
790 |
|
|
EntryPointer entries = Entry::empty_default_table(); |
791 |
|
|
size_t num_slots_minus_one = 0; |
792 |
|
|
typename HashPolicySelector<ArgumentHash>::type hash_policy; |
793 |
|
|
int8_t max_lookups = detailv3::min_lookups - 1; |
794 |
|
|
float _max_load_factor = 0.5f; |
795 |
|
|
size_t num_elements = 0; |
796 |
|
|
|
797 |
|
|
static int8_t compute_max_lookups(size_t num_buckets) |
798 |
|
|
{ |
799 |
|
|
int8_t desired = detailv3::log2(num_buckets); |
800 |
|
|
return std::max(detailv3::min_lookups, desired); |
801 |
|
|
} |
802 |
|
|
|
803 |
|
|
size_t num_buckets_for_reserve(size_t num_elements) const |
804 |
|
|
{ |
805 |
|
|
return static_cast<size_t>(std::ceil(num_elements / std::min(0.5, static_cast<double>(_max_load_factor)))); |
806 |
|
|
} |
807 |
|
|
void rehash_for_other_container(const sherwood_v3_table & other) |
808 |
|
|
{ |
809 |
|
|
rehash(std::min(num_buckets_for_reserve(other.size()), other.bucket_count())); |
810 |
|
|
} |
811 |
|
|
|
812 |
|
|
void swap_pointers(sherwood_v3_table & other) |
813 |
|
|
{ |
814 |
|
|
using std::swap; |
815 |
|
|
swap(hash_policy, other.hash_policy); |
816 |
|
|
swap(entries, other.entries); |
817 |
|
|
swap(num_slots_minus_one, other.num_slots_minus_one); |
818 |
|
|
swap(num_elements, other.num_elements); |
819 |
|
|
swap(max_lookups, other.max_lookups); |
820 |
|
|
swap(_max_load_factor, other._max_load_factor); |
821 |
|
|
} |
822 |
|
|
|
823 |
|
|
template<typename Key, typename... Args> |
824 |
|
|
SKA_NOINLINE(std::pair<iterator, bool>) emplace_new_key(int8_t distance_from_desired, EntryPointer current_entry, Key && key, Args &&... args) |
825 |
|
|
{ |
826 |
|
|
using std::swap; |
827 |
|
|
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)) |
828 |
|
|
{ |
829 |
|
|
grow(); |
830 |
|
|
return emplace(std::forward<Key>(key), std::forward<Args>(args)...); |
831 |
|
|
} |
832 |
|
|
else if (current_entry->is_empty()) |
833 |
|
|
{ |
834 |
|
|
current_entry->emplace(distance_from_desired, std::forward<Key>(key), std::forward<Args>(args)...); |
835 |
|
|
++num_elements; |
836 |
|
|
return { { current_entry }, true }; |
837 |
|
|
} |
838 |
|
|
value_type to_insert(std::forward<Key>(key), std::forward<Args>(args)...); |
839 |
|
|
swap(distance_from_desired, current_entry->distance_from_desired); |
840 |
|
|
swap(to_insert, current_entry->value); |
841 |
|
|
iterator result = { current_entry }; |
842 |
|
|
for (++distance_from_desired, ++current_entry;; ++current_entry) |
843 |
|
|
{ |
844 |
|
|
if (current_entry->is_empty()) |
845 |
|
|
{ |
846 |
|
|
current_entry->emplace(distance_from_desired, std::move(to_insert)); |
847 |
|
|
++num_elements; |
848 |
|
|
return { result, true }; |
849 |
|
|
} |
850 |
|
|
else if (current_entry->distance_from_desired < distance_from_desired) |
851 |
|
|
{ |
852 |
|
|
swap(distance_from_desired, current_entry->distance_from_desired); |
853 |
|
|
swap(to_insert, current_entry->value); |
854 |
|
|
++distance_from_desired; |
855 |
|
|
} |
856 |
|
|
else |
857 |
|
|
{ |
858 |
|
|
++distance_from_desired; |
859 |
|
|
if (distance_from_desired == max_lookups) |
860 |
|
|
{ |
861 |
|
|
swap(to_insert, result.current->value); |
862 |
|
|
grow(); |
863 |
|
|
return emplace(std::move(to_insert)); |
864 |
|
|
} |
865 |
|
|
} |
866 |
|
|
} |
867 |
|
|
} |
868 |
|
|
|
869 |
|
|
void grow() |
870 |
|
|
{ |
871 |
|
|
rehash(std::max(size_t(4), 2 * bucket_count())); |
872 |
|
|
} |
873 |
|
|
|
874 |
|
|
void deallocate_data(EntryPointer begin, size_t num_slots_minus_one, int8_t max_lookups) |
875 |
|
|
{ |
876 |
|
|
if (begin != Entry::empty_default_table()) |
877 |
|
|
{ |
878 |
|
|
AllocatorTraits::deallocate(*this, begin, num_slots_minus_one + max_lookups + 1); |
879 |
|
|
} |
880 |
|
|
} |
881 |
|
|
|
882 |
|
|
void reset_to_empty_state() |
883 |
|
|
{ |
884 |
|
|
deallocate_data(entries, num_slots_minus_one, max_lookups); |
885 |
|
|
entries = Entry::empty_default_table(); |
886 |
|
|
num_slots_minus_one = 0; |
887 |
|
|
hash_policy.reset(); |
888 |
|
|
max_lookups = detailv3::min_lookups - 1; |
889 |
|
|
} |
890 |
|
|
|
891 |
|
|
template<typename U> |
892 |
|
|
size_t hash_object(const U & key) |
893 |
|
|
{ |
894 |
|
|
return static_cast<Hasher &>(*this)(key); |
895 |
|
|
} |
896 |
|
|
template<typename U> |
897 |
|
|
size_t hash_object(const U & key) const |
898 |
|
|
{ |
899 |
|
|
return static_cast<const Hasher &>(*this)(key); |
900 |
|
|
} |
901 |
|
|
template<typename L, typename R> |
902 |
|
|
bool compares_equal(const L & lhs, const R & rhs) |
903 |
|
|
{ |
904 |
|
|
return static_cast<Equal &>(*this)(lhs, rhs); |
905 |
|
|
} |
906 |
|
|
|
907 |
|
|
struct convertible_to_iterator |
908 |
|
|
{ |
909 |
|
|
EntryPointer it; |
910 |
|
|
|
911 |
|
|
operator iterator() |
912 |
|
|
{ |
913 |
|
|
if (it->has_value()) |
914 |
|
|
return { it }; |
915 |
|
|
else |
916 |
|
|
return ++iterator{it}; |
917 |
|
|
} |
918 |
|
|
operator const_iterator() |
919 |
|
|
{ |
920 |
|
|
if (it->has_value()) |
921 |
|
|
return { it }; |
922 |
|
|
else |
923 |
|
|
return ++const_iterator{it}; |
924 |
|
|
} |
925 |
|
|
}; |
926 |
|
|
|
927 |
|
|
}; |
928 |
|
|
} |
929 |
|
|
|
930 |
|
|
struct prime_number_hash_policy |
931 |
|
|
{ |
932 |
|
|
static size_t mod0(size_t) { return 0llu; } |
933 |
|
|
static size_t mod2(size_t hash) { return hash % 2llu; } |
934 |
|
|
static size_t mod3(size_t hash) { return hash % 3llu; } |
935 |
|
|
static size_t mod5(size_t hash) { return hash % 5llu; } |
936 |
|
|
static size_t mod7(size_t hash) { return hash % 7llu; } |
937 |
|
|
static size_t mod11(size_t hash) { return hash % 11llu; } |
938 |
|
|
static size_t mod13(size_t hash) { return hash % 13llu; } |
939 |
|
|
static size_t mod17(size_t hash) { return hash % 17llu; } |
940 |
|
|
static size_t mod23(size_t hash) { return hash % 23llu; } |
941 |
|
|
static size_t mod29(size_t hash) { return hash % 29llu; } |
942 |
|
|
static size_t mod37(size_t hash) { return hash % 37llu; } |
943 |
|
|
static size_t mod47(size_t hash) { return hash % 47llu; } |
944 |
|
|
static size_t mod59(size_t hash) { return hash % 59llu; } |
945 |
|
|
static size_t mod73(size_t hash) { return hash % 73llu; } |
946 |
|
|
static size_t mod97(size_t hash) { return hash % 97llu; } |
947 |
|
|
static size_t mod127(size_t hash) { return hash % 127llu; } |
948 |
|
|
static size_t mod151(size_t hash) { return hash % 151llu; } |
949 |
|
|
static size_t mod197(size_t hash) { return hash % 197llu; } |
950 |
|
|
static size_t mod251(size_t hash) { return hash % 251llu; } |
951 |
|
|
static size_t mod313(size_t hash) { return hash % 313llu; } |
952 |
|
|
static size_t mod397(size_t hash) { return hash % 397llu; } |
953 |
|
|
static size_t mod499(size_t hash) { return hash % 499llu; } |
954 |
|
|
static size_t mod631(size_t hash) { return hash % 631llu; } |
955 |
|
|
static size_t mod797(size_t hash) { return hash % 797llu; } |
956 |
|
|
static size_t mod1009(size_t hash) { return hash % 1009llu; } |
957 |
|
|
static size_t mod1259(size_t hash) { return hash % 1259llu; } |
958 |
|
|
static size_t mod1597(size_t hash) { return hash % 1597llu; } |
959 |
|
|
static size_t mod2011(size_t hash) { return hash % 2011llu; } |
960 |
|
|
static size_t mod2539(size_t hash) { return hash % 2539llu; } |
961 |
|
|
static size_t mod3203(size_t hash) { return hash % 3203llu; } |
962 |
|
|
static size_t mod4027(size_t hash) { return hash % 4027llu; } |
963 |
|
|
static size_t mod5087(size_t hash) { return hash % 5087llu; } |
964 |
|
|
static size_t mod6421(size_t hash) { return hash % 6421llu; } |
965 |
|
|
static size_t mod8089(size_t hash) { return hash % 8089llu; } |
966 |
|
|
static size_t mod10193(size_t hash) { return hash % 10193llu; } |
967 |
|
|
static size_t mod12853(size_t hash) { return hash % 12853llu; } |
968 |
|
|
static size_t mod16193(size_t hash) { return hash % 16193llu; } |
969 |
|
|
static size_t mod20399(size_t hash) { return hash % 20399llu; } |
970 |
|
|
static size_t mod25717(size_t hash) { return hash % 25717llu; } |
971 |
|
|
static size_t mod32401(size_t hash) { return hash % 32401llu; } |
972 |
|
|
static size_t mod40823(size_t hash) { return hash % 40823llu; } |
973 |
|
|
static size_t mod51437(size_t hash) { return hash % 51437llu; } |
974 |
|
|
static size_t mod64811(size_t hash) { return hash % 64811llu; } |
975 |
|
|
static size_t mod81649(size_t hash) { return hash % 81649llu; } |
976 |
|
|
static size_t mod102877(size_t hash) { return hash % 102877llu; } |
977 |
|
|
static size_t mod129607(size_t hash) { return hash % 129607llu; } |
978 |
|
|
static size_t mod163307(size_t hash) { return hash % 163307llu; } |
979 |
|
|
static size_t mod205759(size_t hash) { return hash % 205759llu; } |
980 |
|
|
static size_t mod259229(size_t hash) { return hash % 259229llu; } |
981 |
|
|
static size_t mod326617(size_t hash) { return hash % 326617llu; } |
982 |
|
|
static size_t mod411527(size_t hash) { return hash % 411527llu; } |
983 |
|
|
static size_t mod518509(size_t hash) { return hash % 518509llu; } |
984 |
|
|
static size_t mod653267(size_t hash) { return hash % 653267llu; } |
985 |
|
|
static size_t mod823117(size_t hash) { return hash % 823117llu; } |
986 |
|
|
static size_t mod1037059(size_t hash) { return hash % 1037059llu; } |
987 |
|
|
static size_t mod1306601(size_t hash) { return hash % 1306601llu; } |
988 |
|
|
static size_t mod1646237(size_t hash) { return hash % 1646237llu; } |
989 |
|
|
static size_t mod2074129(size_t hash) { return hash % 2074129llu; } |
990 |
|
|
static size_t mod2613229(size_t hash) { return hash % 2613229llu; } |
991 |
|
|
static size_t mod3292489(size_t hash) { return hash % 3292489llu; } |
992 |
|
|
static size_t mod4148279(size_t hash) { return hash % 4148279llu; } |
993 |
|
|
static size_t mod5226491(size_t hash) { return hash % 5226491llu; } |
994 |
|
|
static size_t mod6584983(size_t hash) { return hash % 6584983llu; } |
995 |
|
|
static size_t mod8296553(size_t hash) { return hash % 8296553llu; } |
996 |
|
|
static size_t mod10453007(size_t hash) { return hash % 10453007llu; } |
997 |
|
|
static size_t mod13169977(size_t hash) { return hash % 13169977llu; } |
998 |
|
|
static size_t mod16593127(size_t hash) { return hash % 16593127llu; } |
999 |
|
|
static size_t mod20906033(size_t hash) { return hash % 20906033llu; } |
1000 |
|
|
static size_t mod26339969(size_t hash) { return hash % 26339969llu; } |
1001 |
|
|
static size_t mod33186281(size_t hash) { return hash % 33186281llu; } |
1002 |
|
|
static size_t mod41812097(size_t hash) { return hash % 41812097llu; } |
1003 |
|
|
static size_t mod52679969(size_t hash) { return hash % 52679969llu; } |
1004 |
|
|
static size_t mod66372617(size_t hash) { return hash % 66372617llu; } |
1005 |
|
|
static size_t mod83624237(size_t hash) { return hash % 83624237llu; } |
1006 |
|
|
static size_t mod105359939(size_t hash) { return hash % 105359939llu; } |
1007 |
|
|
static size_t mod132745199(size_t hash) { return hash % 132745199llu; } |
1008 |
|
|
static size_t mod167248483(size_t hash) { return hash % 167248483llu; } |
1009 |
|
|
static size_t mod210719881(size_t hash) { return hash % 210719881llu; } |
1010 |
|
|
static size_t mod265490441(size_t hash) { return hash % 265490441llu; } |
1011 |
|
|
static size_t mod334496971(size_t hash) { return hash % 334496971llu; } |
1012 |
|
|
static size_t mod421439783(size_t hash) { return hash % 421439783llu; } |
1013 |
|
|
static size_t mod530980861(size_t hash) { return hash % 530980861llu; } |
1014 |
|
|
static size_t mod668993977(size_t hash) { return hash % 668993977llu; } |
1015 |
|
|
static size_t mod842879579(size_t hash) { return hash % 842879579llu; } |
1016 |
|
|
static size_t mod1061961721(size_t hash) { return hash % 1061961721llu; } |
1017 |
|
|
static size_t mod1337987929(size_t hash) { return hash % 1337987929llu; } |
1018 |
|
|
static size_t mod1685759167(size_t hash) { return hash % 1685759167llu; } |
1019 |
|
|
static size_t mod2123923447(size_t hash) { return hash % 2123923447llu; } |
1020 |
|
|
static size_t mod2675975881(size_t hash) { return hash % 2675975881llu; } |
1021 |
|
|
static size_t mod3371518343(size_t hash) { return hash % 3371518343llu; } |
1022 |
|
|
static size_t mod4247846927(size_t hash) { return hash % 4247846927llu; } |
1023 |
|
|
static size_t mod5351951779(size_t hash) { return hash % 5351951779llu; } |
1024 |
|
|
static size_t mod6743036717(size_t hash) { return hash % 6743036717llu; } |
1025 |
|
|
static size_t mod8495693897(size_t hash) { return hash % 8495693897llu; } |
1026 |
|
|
static size_t mod10703903591(size_t hash) { return hash % 10703903591llu; } |
1027 |
|
|
static size_t mod13486073473(size_t hash) { return hash % 13486073473llu; } |
1028 |
|
|
static size_t mod16991387857(size_t hash) { return hash % 16991387857llu; } |
1029 |
|
|
static size_t mod21407807219(size_t hash) { return hash % 21407807219llu; } |
1030 |
|
|
static size_t mod26972146961(size_t hash) { return hash % 26972146961llu; } |
1031 |
|
|
static size_t mod33982775741(size_t hash) { return hash % 33982775741llu; } |
1032 |
|
|
static size_t mod42815614441(size_t hash) { return hash % 42815614441llu; } |
1033 |
|
|
static size_t mod53944293929(size_t hash) { return hash % 53944293929llu; } |
1034 |
|
|
static size_t mod67965551447(size_t hash) { return hash % 67965551447llu; } |
1035 |
|
|
static size_t mod85631228929(size_t hash) { return hash % 85631228929llu; } |
1036 |
|
|
static size_t mod107888587883(size_t hash) { return hash % 107888587883llu; } |
1037 |
|
|
static size_t mod135931102921(size_t hash) { return hash % 135931102921llu; } |
1038 |
|
|
static size_t mod171262457903(size_t hash) { return hash % 171262457903llu; } |
1039 |
|
|
static size_t mod215777175787(size_t hash) { return hash % 215777175787llu; } |
1040 |
|
|
static size_t mod271862205833(size_t hash) { return hash % 271862205833llu; } |
1041 |
|
|
static size_t mod342524915839(size_t hash) { return hash % 342524915839llu; } |
1042 |
|
|
static size_t mod431554351609(size_t hash) { return hash % 431554351609llu; } |
1043 |
|
|
static size_t mod543724411781(size_t hash) { return hash % 543724411781llu; } |
1044 |
|
|
static size_t mod685049831731(size_t hash) { return hash % 685049831731llu; } |
1045 |
|
|
static size_t mod863108703229(size_t hash) { return hash % 863108703229llu; } |
1046 |
|
|
static size_t mod1087448823553(size_t hash) { return hash % 1087448823553llu; } |
1047 |
|
|
static size_t mod1370099663459(size_t hash) { return hash % 1370099663459llu; } |
1048 |
|
|
static size_t mod1726217406467(size_t hash) { return hash % 1726217406467llu; } |
1049 |
|
|
static size_t mod2174897647073(size_t hash) { return hash % 2174897647073llu; } |
1050 |
|
|
static size_t mod2740199326961(size_t hash) { return hash % 2740199326961llu; } |
1051 |
|
|
static size_t mod3452434812973(size_t hash) { return hash % 3452434812973llu; } |
1052 |
|
|
static size_t mod4349795294267(size_t hash) { return hash % 4349795294267llu; } |
1053 |
|
|
static size_t mod5480398654009(size_t hash) { return hash % 5480398654009llu; } |
1054 |
|
|
static size_t mod6904869625999(size_t hash) { return hash % 6904869625999llu; } |
1055 |
|
|
static size_t mod8699590588571(size_t hash) { return hash % 8699590588571llu; } |
1056 |
|
|
static size_t mod10960797308051(size_t hash) { return hash % 10960797308051llu; } |
1057 |
|
|
static size_t mod13809739252051(size_t hash) { return hash % 13809739252051llu; } |
1058 |
|
|
static size_t mod17399181177241(size_t hash) { return hash % 17399181177241llu; } |
1059 |
|
|
static size_t mod21921594616111(size_t hash) { return hash % 21921594616111llu; } |
1060 |
|
|
static size_t mod27619478504183(size_t hash) { return hash % 27619478504183llu; } |
1061 |
|
|
static size_t mod34798362354533(size_t hash) { return hash % 34798362354533llu; } |
1062 |
|
|
static size_t mod43843189232363(size_t hash) { return hash % 43843189232363llu; } |
1063 |
|
|
static size_t mod55238957008387(size_t hash) { return hash % 55238957008387llu; } |
1064 |
|
|
static size_t mod69596724709081(size_t hash) { return hash % 69596724709081llu; } |
1065 |
|
|
static size_t mod87686378464759(size_t hash) { return hash % 87686378464759llu; } |
1066 |
|
|
static size_t mod110477914016779(size_t hash) { return hash % 110477914016779llu; } |
1067 |
|
|
static size_t mod139193449418173(size_t hash) { return hash % 139193449418173llu; } |
1068 |
|
|
static size_t mod175372756929481(size_t hash) { return hash % 175372756929481llu; } |
1069 |
|
|
static size_t mod220955828033581(size_t hash) { return hash % 220955828033581llu; } |
1070 |
|
|
static size_t mod278386898836457(size_t hash) { return hash % 278386898836457llu; } |
1071 |
|
|
static size_t mod350745513859007(size_t hash) { return hash % 350745513859007llu; } |
1072 |
|
|
static size_t mod441911656067171(size_t hash) { return hash % 441911656067171llu; } |
1073 |
|
|
static size_t mod556773797672909(size_t hash) { return hash % 556773797672909llu; } |
1074 |
|
|
static size_t mod701491027718027(size_t hash) { return hash % 701491027718027llu; } |
1075 |
|
|
static size_t mod883823312134381(size_t hash) { return hash % 883823312134381llu; } |
1076 |
|
|
static size_t mod1113547595345903(size_t hash) { return hash % 1113547595345903llu; } |
1077 |
|
|
static size_t mod1402982055436147(size_t hash) { return hash % 1402982055436147llu; } |
1078 |
|
|
static size_t mod1767646624268779(size_t hash) { return hash % 1767646624268779llu; } |
1079 |
|
|
static size_t mod2227095190691797(size_t hash) { return hash % 2227095190691797llu; } |
1080 |
|
|
static size_t mod2805964110872297(size_t hash) { return hash % 2805964110872297llu; } |
1081 |
|
|
static size_t mod3535293248537579(size_t hash) { return hash % 3535293248537579llu; } |
1082 |
|
|
static size_t mod4454190381383713(size_t hash) { return hash % 4454190381383713llu; } |
1083 |
|
|
static size_t mod5611928221744609(size_t hash) { return hash % 5611928221744609llu; } |
1084 |
|
|
static size_t mod7070586497075177(size_t hash) { return hash % 7070586497075177llu; } |
1085 |
|
|
static size_t mod8908380762767489(size_t hash) { return hash % 8908380762767489llu; } |
1086 |
|
|
static size_t mod11223856443489329(size_t hash) { return hash % 11223856443489329llu; } |
1087 |
|
|
static size_t mod14141172994150357(size_t hash) { return hash % 14141172994150357llu; } |
1088 |
|
|
static size_t mod17816761525534927(size_t hash) { return hash % 17816761525534927llu; } |
1089 |
|
|
static size_t mod22447712886978529(size_t hash) { return hash % 22447712886978529llu; } |
1090 |
|
|
static size_t mod28282345988300791(size_t hash) { return hash % 28282345988300791llu; } |
1091 |
|
|
static size_t mod35633523051069991(size_t hash) { return hash % 35633523051069991llu; } |
1092 |
|
|
static size_t mod44895425773957261(size_t hash) { return hash % 44895425773957261llu; } |
1093 |
|
|
static size_t mod56564691976601587(size_t hash) { return hash % 56564691976601587llu; } |
1094 |
|
|
static size_t mod71267046102139967(size_t hash) { return hash % 71267046102139967llu; } |
1095 |
|
|
static size_t mod89790851547914507(size_t hash) { return hash % 89790851547914507llu; } |
1096 |
|
|
static size_t mod113129383953203213(size_t hash) { return hash % 113129383953203213llu; } |
1097 |
|
|
static size_t mod142534092204280003(size_t hash) { return hash % 142534092204280003llu; } |
1098 |
|
|
static size_t mod179581703095829107(size_t hash) { return hash % 179581703095829107llu; } |
1099 |
|
|
static size_t mod226258767906406483(size_t hash) { return hash % 226258767906406483llu; } |
1100 |
|
|
static size_t mod285068184408560057(size_t hash) { return hash % 285068184408560057llu; } |
1101 |
|
|
static size_t mod359163406191658253(size_t hash) { return hash % 359163406191658253llu; } |
1102 |
|
|
static size_t mod452517535812813007(size_t hash) { return hash % 452517535812813007llu; } |
1103 |
|
|
static size_t mod570136368817120201(size_t hash) { return hash % 570136368817120201llu; } |
1104 |
|
|
static size_t mod718326812383316683(size_t hash) { return hash % 718326812383316683llu; } |
1105 |
|
|
static size_t mod905035071625626043(size_t hash) { return hash % 905035071625626043llu; } |
1106 |
|
|
static size_t mod1140272737634240411(size_t hash) { return hash % 1140272737634240411llu; } |
1107 |
|
|
static size_t mod1436653624766633509(size_t hash) { return hash % 1436653624766633509llu; } |
1108 |
|
|
static size_t mod1810070143251252131(size_t hash) { return hash % 1810070143251252131llu; } |
1109 |
|
|
static size_t mod2280545475268481167(size_t hash) { return hash % 2280545475268481167llu; } |
1110 |
|
|
static size_t mod2873307249533267101(size_t hash) { return hash % 2873307249533267101llu; } |
1111 |
|
|
static size_t mod3620140286502504283(size_t hash) { return hash % 3620140286502504283llu; } |
1112 |
|
|
static size_t mod4561090950536962147(size_t hash) { return hash % 4561090950536962147llu; } |
1113 |
|
|
static size_t mod5746614499066534157(size_t hash) { return hash % 5746614499066534157llu; } |
1114 |
|
|
static size_t mod7240280573005008577(size_t hash) { return hash % 7240280573005008577llu; } |
1115 |
|
|
static size_t mod9122181901073924329(size_t hash) { return hash % 9122181901073924329llu; } |
1116 |
|
|
static size_t mod11493228998133068689(size_t hash) { return hash % 11493228998133068689llu; } |
1117 |
|
|
static size_t mod14480561146010017169(size_t hash) { return hash % 14480561146010017169llu; } |
1118 |
|
|
static size_t mod18446744073709551557(size_t hash) { return hash % 18446744073709551557llu; } |
1119 |
|
|
|
1120 |
|
|
using mod_function = size_t (*)(size_t); |
1121 |
|
|
|
1122 |
|
|
mod_function next_size_over(size_t & size) const |
1123 |
|
|
{ |
1124 |
|
|
// prime numbers generated by the following method: |
1125 |
|
|
// 1. start with a prime p = 2 |
1126 |
|
|
// 2. go to wolfram alpha and get p = NextPrime(2 * p) |
1127 |
|
|
// 3. repeat 2. until you overflow 64 bits |
1128 |
|
|
// you now have large gaps which you would hit if somebody called reserve() with an unlucky number. |
1129 |
|
|
// 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 |
1130 |
|
|
// 5. get PrevPrime(2^64) and put it at the end |
1131 |
|
|
static constexpr const size_t prime_list[] = |
1132 |
|
|
{ |
1133 |
|
|
2llu, 3llu, 5llu, 7llu, 11llu, 13llu, 17llu, 23llu, 29llu, 37llu, 47llu, |
1134 |
|
|
59llu, 73llu, 97llu, 127llu, 151llu, 197llu, 251llu, 313llu, 397llu, |
1135 |
|
|
499llu, 631llu, 797llu, 1009llu, 1259llu, 1597llu, 2011llu, 2539llu, |
1136 |
|
|
3203llu, 4027llu, 5087llu, 6421llu, 8089llu, 10193llu, 12853llu, 16193llu, |
1137 |
|
|
20399llu, 25717llu, 32401llu, 40823llu, 51437llu, 64811llu, 81649llu, |
1138 |
|
|
102877llu, 129607llu, 163307llu, 205759llu, 259229llu, 326617llu, |
1139 |
|
|
411527llu, 518509llu, 653267llu, 823117llu, 1037059llu, 1306601llu, |
1140 |
|
|
1646237llu, 2074129llu, 2613229llu, 3292489llu, 4148279llu, 5226491llu, |
1141 |
|
|
6584983llu, 8296553llu, 10453007llu, 13169977llu, 16593127llu, 20906033llu, |
1142 |
|
|
26339969llu, 33186281llu, 41812097llu, 52679969llu, 66372617llu, |
1143 |
|
|
83624237llu, 105359939llu, 132745199llu, 167248483llu, 210719881llu, |
1144 |
|
|
265490441llu, 334496971llu, 421439783llu, 530980861llu, 668993977llu, |
1145 |
|
|
842879579llu, 1061961721llu, 1337987929llu, 1685759167llu, 2123923447llu, |
1146 |
|
|
2675975881llu, 3371518343llu, 4247846927llu, 5351951779llu, 6743036717llu, |
1147 |
|
|
8495693897llu, 10703903591llu, 13486073473llu, 16991387857llu, |
1148 |
|
|
21407807219llu, 26972146961llu, 33982775741llu, 42815614441llu, |
1149 |
|
|
53944293929llu, 67965551447llu, 85631228929llu, 107888587883llu, |
1150 |
|
|
135931102921llu, 171262457903llu, 215777175787llu, 271862205833llu, |
1151 |
|
|
342524915839llu, 431554351609llu, 543724411781llu, 685049831731llu, |
1152 |
|
|
863108703229llu, 1087448823553llu, 1370099663459llu, 1726217406467llu, |
1153 |
|
|
2174897647073llu, 2740199326961llu, 3452434812973llu, 4349795294267llu, |
1154 |
|
|
5480398654009llu, 6904869625999llu, 8699590588571llu, 10960797308051llu, |
1155 |
|
|
13809739252051llu, 17399181177241llu, 21921594616111llu, 27619478504183llu, |
1156 |
|
|
34798362354533llu, 43843189232363llu, 55238957008387llu, 69596724709081llu, |
1157 |
|
|
87686378464759llu, 110477914016779llu, 139193449418173llu, |
1158 |
|
|
175372756929481llu, 220955828033581llu, 278386898836457llu, |
1159 |
|
|
350745513859007llu, 441911656067171llu, 556773797672909llu, |
1160 |
|
|
701491027718027llu, 883823312134381llu, 1113547595345903llu, |
1161 |
|
|
1402982055436147llu, 1767646624268779llu, 2227095190691797llu, |
1162 |
|
|
2805964110872297llu, 3535293248537579llu, 4454190381383713llu, |
1163 |
|
|
5611928221744609llu, 7070586497075177llu, 8908380762767489llu, |
1164 |
|
|
11223856443489329llu, 14141172994150357llu, 17816761525534927llu, |
1165 |
|
|
22447712886978529llu, 28282345988300791llu, 35633523051069991llu, |
1166 |
|
|
44895425773957261llu, 56564691976601587llu, 71267046102139967llu, |
1167 |
|
|
89790851547914507llu, 113129383953203213llu, 142534092204280003llu, |
1168 |
|
|
179581703095829107llu, 226258767906406483llu, 285068184408560057llu, |
1169 |
|
|
359163406191658253llu, 452517535812813007llu, 570136368817120201llu, |
1170 |
|
|
718326812383316683llu, 905035071625626043llu, 1140272737634240411llu, |
1171 |
|
|
1436653624766633509llu, 1810070143251252131llu, 2280545475268481167llu, |
1172 |
|
|
2873307249533267101llu, 3620140286502504283llu, 4561090950536962147llu, |
1173 |
|
|
5746614499066534157llu, 7240280573005008577llu, 9122181901073924329llu, |
1174 |
|
|
11493228998133068689llu, 14480561146010017169llu, 18446744073709551557llu |
1175 |
|
|
}; |
1176 |
|
|
static constexpr size_t (* const mod_functions[])(size_t) = |
1177 |
|
|
{ |
1178 |
|
|
&mod0, &mod2, &mod3, &mod5, &mod7, &mod11, &mod13, &mod17, &mod23, &mod29, &mod37, |
1179 |
|
|
&mod47, &mod59, &mod73, &mod97, &mod127, &mod151, &mod197, &mod251, &mod313, &mod397, |
1180 |
|
|
&mod499, &mod631, &mod797, &mod1009, &mod1259, &mod1597, &mod2011, &mod2539, &mod3203, |
1181 |
|
|
&mod4027, &mod5087, &mod6421, &mod8089, &mod10193, &mod12853, &mod16193, &mod20399, |
1182 |
|
|
&mod25717, &mod32401, &mod40823, &mod51437, &mod64811, &mod81649, &mod102877, |
1183 |
|
|
&mod129607, &mod163307, &mod205759, &mod259229, &mod326617, &mod411527, &mod518509, |
1184 |
|
|
&mod653267, &mod823117, &mod1037059, &mod1306601, &mod1646237, &mod2074129, |
1185 |
|
|
&mod2613229, &mod3292489, &mod4148279, &mod5226491, &mod6584983, &mod8296553, |
1186 |
|
|
&mod10453007, &mod13169977, &mod16593127, &mod20906033, &mod26339969, &mod33186281, |
1187 |
|
|
&mod41812097, &mod52679969, &mod66372617, &mod83624237, &mod105359939, &mod132745199, |
1188 |
|
|
&mod167248483, &mod210719881, &mod265490441, &mod334496971, &mod421439783, |
1189 |
|
|
&mod530980861, &mod668993977, &mod842879579, &mod1061961721, &mod1337987929, |
1190 |
|
|
&mod1685759167, &mod2123923447, &mod2675975881, &mod3371518343, &mod4247846927, |
1191 |
|
|
&mod5351951779, &mod6743036717, &mod8495693897, &mod10703903591, &mod13486073473, |
1192 |
|
|
&mod16991387857, &mod21407807219, &mod26972146961, &mod33982775741, &mod42815614441, |
1193 |
|
|
&mod53944293929, &mod67965551447, &mod85631228929, &mod107888587883, &mod135931102921, |
1194 |
|
|
&mod171262457903, &mod215777175787, &mod271862205833, &mod342524915839, |
1195 |
|
|
&mod431554351609, &mod543724411781, &mod685049831731, &mod863108703229, |
1196 |
|
|
&mod1087448823553, &mod1370099663459, &mod1726217406467, &mod2174897647073, |
1197 |
|
|
&mod2740199326961, &mod3452434812973, &mod4349795294267, &mod5480398654009, |
1198 |
|
|
&mod6904869625999, &mod8699590588571, &mod10960797308051, &mod13809739252051, |
1199 |
|
|
&mod17399181177241, &mod21921594616111, &mod27619478504183, &mod34798362354533, |
1200 |
|
|
&mod43843189232363, &mod55238957008387, &mod69596724709081, &mod87686378464759, |
1201 |
|
|
&mod110477914016779, &mod139193449418173, &mod175372756929481, &mod220955828033581, |
1202 |
|
|
&mod278386898836457, &mod350745513859007, &mod441911656067171, &mod556773797672909, |
1203 |
|
|
&mod701491027718027, &mod883823312134381, &mod1113547595345903, &mod1402982055436147, |
1204 |
|
|
&mod1767646624268779, &mod2227095190691797, &mod2805964110872297, &mod3535293248537579, |
1205 |
|
|
&mod4454190381383713, &mod5611928221744609, &mod7070586497075177, &mod8908380762767489, |
1206 |
|
|
&mod11223856443489329, &mod14141172994150357, &mod17816761525534927, |
1207 |
|
|
&mod22447712886978529, &mod28282345988300791, &mod35633523051069991, |
1208 |
|
|
&mod44895425773957261, &mod56564691976601587, &mod71267046102139967, |
1209 |
|
|
&mod89790851547914507, &mod113129383953203213, &mod142534092204280003, |
1210 |
|
|
&mod179581703095829107, &mod226258767906406483, &mod285068184408560057, |
1211 |
|
|
&mod359163406191658253, &mod452517535812813007, &mod570136368817120201, |
1212 |
|
|
&mod718326812383316683, &mod905035071625626043, &mod1140272737634240411, |
1213 |
|
|
&mod1436653624766633509, &mod1810070143251252131, &mod2280545475268481167, |
1214 |
|
|
&mod2873307249533267101, &mod3620140286502504283, &mod4561090950536962147, |
1215 |
|
|
&mod5746614499066534157, &mod7240280573005008577, &mod9122181901073924329, |
1216 |
|
|
&mod11493228998133068689, &mod14480561146010017169, &mod18446744073709551557 |
1217 |
|
|
}; |
1218 |
|
|
const size_t * found = std::lower_bound(std::begin(prime_list), std::end(prime_list) - 1, size); |
1219 |
|
|
size = *found; |
1220 |
|
|
return mod_functions[1 + found - prime_list]; |
1221 |
|
|
} |
1222 |
|
|
void commit(mod_function new_mod_function) |
1223 |
|
|
{ |
1224 |
|
|
current_mod_function = new_mod_function; |
1225 |
|
|
} |
1226 |
|
|
void reset() |
1227 |
|
|
{ |
1228 |
|
|
current_mod_function = &mod0; |
1229 |
|
|
} |
1230 |
|
|
|
1231 |
|
|
size_t index_for_hash(size_t hash, size_t /*num_slots_minus_one*/) const |
1232 |
|
|
{ |
1233 |
|
|
return current_mod_function(hash); |
1234 |
|
|
} |
1235 |
|
|
size_t keep_in_range(size_t index, size_t num_slots_minus_one) const |
1236 |
|
|
{ |
1237 |
|
|
return index > num_slots_minus_one ? current_mod_function(index) : index; |
1238 |
|
|
} |
1239 |
|
|
|
1240 |
|
|
private: |
1241 |
|
|
mod_function current_mod_function = &mod0; |
1242 |
|
|
}; |
1243 |
|
|
|
1244 |
|
|
struct power_of_two_hash_policy |
1245 |
|
|
{ |
1246 |
|
|
size_t index_for_hash(size_t hash, size_t num_slots_minus_one) const |
1247 |
|
|
{ |
1248 |
|
|
return hash & num_slots_minus_one; |
1249 |
|
|
} |
1250 |
|
|
size_t keep_in_range(size_t index, size_t num_slots_minus_one) const |
1251 |
|
|
{ |
1252 |
|
|
return index_for_hash(index, num_slots_minus_one); |
1253 |
|
|
} |
1254 |
|
|
int8_t next_size_over(size_t & size) const |
1255 |
|
|
{ |
1256 |
|
|
size = detailv3::next_power_of_two(size); |
1257 |
|
|
return 0; |
1258 |
|
|
} |
1259 |
|
|
void commit(int8_t) |
1260 |
|
|
{ |
1261 |
|
|
} |
1262 |
|
|
void reset() |
1263 |
|
|
{ |
1264 |
|
|
} |
1265 |
|
|
|
1266 |
|
|
}; |
1267 |
|
|
|
1268 |
|
|
struct fibonacci_hash_policy |
1269 |
|
|
{ |
1270 |
|
|
size_t index_for_hash(size_t hash, size_t /*num_slots_minus_one*/) const |
1271 |
|
|
{ |
1272 |
|
|
return (11400714819323198485ull * hash) >> shift; |
1273 |
|
|
} |
1274 |
|
|
size_t keep_in_range(size_t index, size_t num_slots_minus_one) const |
1275 |
|
|
{ |
1276 |
|
|
return index & num_slots_minus_one; |
1277 |
|
|
} |
1278 |
|
|
|
1279 |
|
|
int8_t next_size_over(size_t & size) const |
1280 |
|
|
{ |
1281 |
|
|
size = std::max(size_t(2), detailv3::next_power_of_two(size)); |
1282 |
|
|
return 64 - detailv3::log2(size); |
1283 |
|
|
} |
1284 |
|
|
void commit(int8_t shift) |
1285 |
|
|
{ |
1286 |
|
|
this->shift = shift; |
1287 |
|
|
} |
1288 |
|
|
void reset() |
1289 |
|
|
{ |
1290 |
|
|
shift = 63; |
1291 |
|
|
} |
1292 |
|
|
|
1293 |
|
|
private: |
1294 |
|
|
int8_t shift = 63; |
1295 |
|
|
}; |
1296 |
|
|
|
1297 |
|
|
template<typename K, typename V, typename H = std::hash<K>, typename E = std::equal_to<K>, typename A = std::allocator<std::pair<K, V> > > |
1298 |
|
|
class flat_hash_map |
1299 |
|
|
: public detailv3::sherwood_v3_table |
1300 |
|
|
< |
1301 |
|
|
std::pair<K, V>, |
1302 |
|
|
K, |
1303 |
|
|
H, |
1304 |
|
|
detailv3::KeyOrValueHasher<K, std::pair<K, V>, H>, |
1305 |
|
|
E, |
1306 |
|
|
detailv3::KeyOrValueEquality<K, std::pair<K, V>, E>, |
1307 |
|
|
A, |
1308 |
|
|
typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<std::pair<K, V>>> |
1309 |
|
|
> |
1310 |
|
|
{ |
1311 |
|
|
using Table = detailv3::sherwood_v3_table |
1312 |
|
|
< |
1313 |
|
|
std::pair<K, V>, |
1314 |
|
|
K, |
1315 |
|
|
H, |
1316 |
|
|
detailv3::KeyOrValueHasher<K, std::pair<K, V>, H>, |
1317 |
|
|
E, |
1318 |
|
|
detailv3::KeyOrValueEquality<K, std::pair<K, V>, E>, |
1319 |
|
|
A, |
1320 |
|
|
typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<std::pair<K, V>>> |
1321 |
|
|
>; |
1322 |
|
|
public: |
1323 |
|
|
|
1324 |
|
|
using key_type = K; |
1325 |
|
|
using mapped_type = V; |
1326 |
|
|
|
1327 |
|
|
using Table::Table; |
1328 |
|
|
flat_hash_map() |
1329 |
|
|
{ |
1330 |
|
|
} |
1331 |
|
|
|
1332 |
|
|
inline V & operator[](const K & key) |
1333 |
|
|
{ |
1334 |
|
|
return emplace(key, convertible_to_value()).first->second; |
1335 |
|
|
} |
1336 |
|
|
inline V & operator[](K && key) |
1337 |
|
|
{ |
1338 |
|
|
return emplace(std::move(key), convertible_to_value()).first->second; |
1339 |
|
|
} |
1340 |
|
|
V & at(const K & key) |
1341 |
|
|
{ |
1342 |
|
|
auto found = this->find(key); |
1343 |
|
|
if (found == this->end()) |
1344 |
|
|
throw std::out_of_range("Argument passed to at() was not in the map."); |
1345 |
|
|
return found->second; |
1346 |
|
|
} |
1347 |
|
|
const V & at(const K & key) const |
1348 |
|
|
{ |
1349 |
|
|
auto found = this->find(key); |
1350 |
|
|
if (found == this->end()) |
1351 |
|
|
throw std::out_of_range("Argument passed to at() was not in the map."); |
1352 |
|
|
return found->second; |
1353 |
|
|
} |
1354 |
|
|
|
1355 |
|
|
using Table::emplace; |
1356 |
|
|
std::pair<typename Table::iterator, bool> emplace() |
1357 |
|
|
{ |
1358 |
|
|
return emplace(key_type(), convertible_to_value()); |
1359 |
|
|
} |
1360 |
|
|
template<typename M> |
1361 |
|
|
std::pair<typename Table::iterator, bool> insert_or_assign(const key_type & key, M && m) |
1362 |
|
|
{ |
1363 |
|
|
auto emplace_result = emplace(key, std::forward<M>(m)); |
1364 |
|
|
if (!emplace_result.second) |
1365 |
|
|
emplace_result.first->second = std::forward<M>(m); |
1366 |
|
|
return emplace_result; |
1367 |
|
|
} |
1368 |
|
|
template<typename M> |
1369 |
|
|
std::pair<typename Table::iterator, bool> insert_or_assign(key_type && key, M && m) |
1370 |
|
|
{ |
1371 |
|
|
auto emplace_result = emplace(std::move(key), std::forward<M>(m)); |
1372 |
|
|
if (!emplace_result.second) |
1373 |
|
|
emplace_result.first->second = std::forward<M>(m); |
1374 |
|
|
return emplace_result; |
1375 |
|
|
} |
1376 |
|
|
template<typename M> |
1377 |
|
|
typename Table::iterator insert_or_assign(typename Table::const_iterator, const key_type & key, M && m) |
1378 |
|
|
{ |
1379 |
|
|
return insert_or_assign(key, std::forward<M>(m)).first; |
1380 |
|
|
} |
1381 |
|
|
template<typename M> |
1382 |
|
|
typename Table::iterator insert_or_assign(typename Table::const_iterator, key_type && key, M && m) |
1383 |
|
|
{ |
1384 |
|
|
return insert_or_assign(std::move(key), std::forward<M>(m)).first; |
1385 |
|
|
} |
1386 |
|
|
|
1387 |
|
|
friend bool operator==(const flat_hash_map & lhs, const flat_hash_map & rhs) |
1388 |
|
|
{ |
1389 |
|
|
if (lhs.size() != rhs.size()) |
1390 |
|
|
return false; |
1391 |
|
|
for (const typename Table::value_type & value : lhs) |
1392 |
|
|
{ |
1393 |
|
|
auto found = rhs.find(value.first); |
1394 |
|
|
if (found == rhs.end()) |
1395 |
|
|
return false; |
1396 |
|
|
else if (value.second != found->second) |
1397 |
|
|
return false; |
1398 |
|
|
} |
1399 |
|
|
return true; |
1400 |
|
|
} |
1401 |
|
|
friend bool operator!=(const flat_hash_map & lhs, const flat_hash_map & rhs) |
1402 |
|
|
{ |
1403 |
|
|
return !(lhs == rhs); |
1404 |
|
|
} |
1405 |
|
|
|
1406 |
|
|
private: |
1407 |
|
|
struct convertible_to_value |
1408 |
|
|
{ |
1409 |
|
|
operator V() const |
1410 |
|
|
{ |
1411 |
|
|
return V(); |
1412 |
|
|
} |
1413 |
|
|
}; |
1414 |
|
|
}; |
1415 |
|
|
|
1416 |
|
|
template<typename T, typename H = std::hash<T>, typename E = std::equal_to<T>, typename A = std::allocator<T> > |
1417 |
|
|
class flat_hash_set |
1418 |
|
|
: public detailv3::sherwood_v3_table |
1419 |
|
|
< |
1420 |
|
|
T, |
1421 |
|
|
T, |
1422 |
|
|
H, |
1423 |
|
|
detailv3::functor_storage<size_t, H>, |
1424 |
|
|
E, |
1425 |
|
|
detailv3::functor_storage<bool, E>, |
1426 |
|
|
A, |
1427 |
|
|
typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<T>> |
1428 |
|
|
> |
1429 |
|
|
{ |
1430 |
|
|
using Table = detailv3::sherwood_v3_table |
1431 |
|
|
< |
1432 |
|
|
T, |
1433 |
|
|
T, |
1434 |
|
|
H, |
1435 |
|
|
detailv3::functor_storage<size_t, H>, |
1436 |
|
|
E, |
1437 |
|
|
detailv3::functor_storage<bool, E>, |
1438 |
|
|
A, |
1439 |
|
|
typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<T>> |
1440 |
|
|
>; |
1441 |
|
|
public: |
1442 |
|
|
|
1443 |
|
|
using key_type = T; |
1444 |
|
|
|
1445 |
|
|
using Table::Table; |
1446 |
|
|
flat_hash_set() |
1447 |
|
|
{ |
1448 |
|
|
} |
1449 |
|
|
|
1450 |
|
|
template<typename... Args> |
1451 |
|
|
std::pair<typename Table::iterator, bool> emplace(Args &&... args) |
1452 |
|
|
{ |
1453 |
|
|
return Table::emplace(T(std::forward<Args>(args)...)); |
1454 |
|
|
} |
1455 |
|
|
std::pair<typename Table::iterator, bool> emplace(const key_type & arg) |
1456 |
|
|
{ |
1457 |
|
|
return Table::emplace(arg); |
1458 |
|
|
} |
1459 |
|
|
std::pair<typename Table::iterator, bool> emplace(key_type & arg) |
1460 |
|
|
{ |
1461 |
|
|
return Table::emplace(arg); |
1462 |
|
|
} |
1463 |
|
|
std::pair<typename Table::iterator, bool> emplace(const key_type && arg) |
1464 |
|
|
{ |
1465 |
|
|
return Table::emplace(std::move(arg)); |
1466 |
|
|
} |
1467 |
|
|
std::pair<typename Table::iterator, bool> emplace(key_type && arg) |
1468 |
|
|
{ |
1469 |
|
|
return Table::emplace(std::move(arg)); |
1470 |
|
|
} |
1471 |
|
|
|
1472 |
|
|
friend bool operator==(const flat_hash_set & lhs, const flat_hash_set & rhs) |
1473 |
|
|
{ |
1474 |
|
|
if (lhs.size() != rhs.size()) |
1475 |
|
|
return false; |
1476 |
|
|
for (const T & value : lhs) |
1477 |
|
|
{ |
1478 |
|
|
if (rhs.find(value) == rhs.end()) |
1479 |
|
|
return false; |
1480 |
|
|
} |
1481 |
|
|
return true; |
1482 |
|
|
} |
1483 |
|
|
friend bool operator!=(const flat_hash_set & lhs, const flat_hash_set & rhs) |
1484 |
|
|
{ |
1485 |
|
|
return !(lhs == rhs); |
1486 |
|
|
} |
1487 |
|
|
}; |
1488 |
|
|
|
1489 |
|
|
|
1490 |
|
|
template<typename T> |
1491 |
|
|
struct power_of_two_std_hash : std::hash<T> |
1492 |
|
|
{ |
1493 |
|
|
typedef ska::power_of_two_hash_policy hash_policy; |
1494 |
|
|
}; |
1495 |
|
|
|
1496 |
|
|
} // end namespace ska |