Seregon/ShadPKG

A tool for deriving PKG packet encryption keys for ps4 written in c++

C++/47.3 KB/No license
external/tsl/robin_map.h
raw
ShadPKG / external / tsl / robin_map.h
1/**
2 * MIT License
3 *
4 * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24#ifndef TSL_ROBIN_MAP_H
25#define TSL_ROBIN_MAP_H
26 
27#include <cstddef>
28#include <functional>
29#include <initializer_list>
30#include <memory>
31#include <type_traits>
32#include <utility>
33 
34#include "robin_hash.h"
35 
36namespace tsl {
37 
38/**
39 * Implementation of a hash map using open-addressing and the robin hood hashing
40 * algorithm with backward shift deletion.
41 *
42 * For operations modifying the hash map (insert, erase, rehash, ...), the
43 * strong exception guarantee is only guaranteed when the expression
44 * `std::is_nothrow_swappable<std::pair<Key, T>>::value &&
45 * std::is_nothrow_move_constructible<std::pair<Key, T>>::value` is true,
46 * otherwise if an exception is thrown during the swap or the move, the hash map
47 * may end up in a undefined state. Per the standard a `Key` or `T` with a
48 * noexcept copy constructor and no move constructor also satisfies the
49 * `std::is_nothrow_move_constructible<std::pair<Key, T>>::value` criterion (and
50 * will thus guarantee the strong exception for the map).
51 *
52 * When `StoreHash` is true, 32 bits of the hash are stored alongside the
53 * values. It can improve the performance during lookups if the `KeyEqual`
54 * function takes time (if it engenders a cache-miss for example) as we then
55 * compare the stored hashes before comparing the keys. When
56 * `tsl::rh::power_of_two_growth_policy` is used as `GrowthPolicy`, it may also
57 * speed-up the rehash process as we can avoid to recalculate the hash. When it
58 * is detected that storing the hash will not incur any memory penalty due to
59 * alignment (i.e. `sizeof(tsl::detail_robin_hash::bucket_entry<ValueType,
60 * true>) == sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, false>)`)
61 * and `tsl::rh::power_of_two_growth_policy` is used, the hash will be stored
62 * even if `StoreHash` is false so that we can speed-up the rehash (but it will
63 * not be used on lookups unless `StoreHash` is true).
64 *
65 * `GrowthPolicy` defines how the map grows and consequently how a hash value is
66 * mapped to a bucket. By default the map uses
67 * `tsl::rh::power_of_two_growth_policy`. This policy keeps the number of
68 * buckets to a power of two and uses a mask to map the hash to a bucket instead
69 * of the slow modulo. Other growth policies are available and you may define
70 * your own growth policy, check `tsl::rh::power_of_two_growth_policy` for the
71 * interface.
72 *
73 * `std::pair<Key, T>` must be swappable.
74 *
75 * `Key` and `T` must be copy and/or move constructible.
76 *
77 * If the destructor of `Key` or `T` throws an exception, the behaviour of the
78 * class is undefined.
79 *
80 * Iterators invalidation:
81 * - clear, operator=, reserve, rehash: always invalidate the iterators.
82 * - insert, emplace, emplace_hint, operator[]: if there is an effective
83 * insert, invalidate the iterators.
84 * - erase: always invalidate the iterators.
85 */
86template <class Key, class T, class Hash = std::hash<Key>,
87 class KeyEqual = std::equal_to<Key>,
88 class Allocator = std::allocator<std::pair<Key, T>>,
89 bool StoreHash = false,
90 class GrowthPolicy = tsl::rh::power_of_two_growth_policy<2>>
91class robin_map {
92 private:
93 template <typename U>
94 using has_is_transparent = tsl::detail_robin_hash::has_is_transparent<U>;
95 
96 class KeySelect {
97 public:
98 using key_type = Key;
99 
100 const key_type& operator()(
101 const std::pair<Key, T>& key_value) const noexcept {
102 return key_value.first;
103 }
104 
105 key_type& operator()(std::pair<Key, T>& key_value) noexcept {
106 return key_value.first;
107 }
108 };
109 
110 class ValueSelect {
111 public:
112 using value_type = T;
113 
114 const value_type& operator()(
115 const std::pair<Key, T>& key_value) const noexcept {
116 return key_value.second;
117 }
118 
119 value_type& operator()(std::pair<Key, T>& key_value) noexcept {
120 return key_value.second;
121 }
122 };
123 
124 using ht = detail_robin_hash::robin_hash<std::pair<Key, T>, KeySelect,
125 ValueSelect, Hash, KeyEqual,
126 Allocator, StoreHash, GrowthPolicy>;
127 
128 public:
129 using key_type = typename ht::key_type;
130 using mapped_type = T;
131 using value_type = typename ht::value_type;
132 using size_type = typename ht::size_type;
133 using difference_type = typename ht::difference_type;
134 using hasher = typename ht::hasher;
135 using key_equal = typename ht::key_equal;
136 using allocator_type = typename ht::allocator_type;
137 using reference = typename ht::reference;
138 using const_reference = typename ht::const_reference;
139 using pointer = typename ht::pointer;
140 using const_pointer = typename ht::const_pointer;
141 using iterator = typename ht::iterator;
142 using const_iterator = typename ht::const_iterator;
143 
144 public:
145 /*
146 * Constructors
147 */
148 robin_map() : robin_map(ht::DEFAULT_INIT_BUCKETS_SIZE) {}
149 
150 explicit robin_map(size_type bucket_count, const Hash& hash = Hash(),
151 const KeyEqual& equal = KeyEqual(),
152 const Allocator& alloc = Allocator())
153 : m_ht(bucket_count, hash, equal, alloc) {}
154 
155 robin_map(size_type bucket_count, const Allocator& alloc)
156 : robin_map(bucket_count, Hash(), KeyEqual(), alloc) {}
157 
158 robin_map(size_type bucket_count, const Hash& hash, const Allocator& alloc)
159 : robin_map(bucket_count, hash, KeyEqual(), alloc) {}
160 
161 explicit robin_map(const Allocator& alloc)
162 : robin_map(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {}
163 
164 template <class InputIt>
165 robin_map(InputIt first, InputIt last,
166 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
167 const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(),
168 const Allocator& alloc = Allocator())
169 : robin_map(bucket_count, hash, equal, alloc) {
170 insert(first, last);
171 }
172 
173 template <class InputIt>
174 robin_map(InputIt first, InputIt last, size_type bucket_count,
175 const Allocator& alloc)
176 : robin_map(first, last, bucket_count, Hash(), KeyEqual(), alloc) {}
177 
178 template <class InputIt>
179 robin_map(InputIt first, InputIt last, size_type bucket_count,
180 const Hash& hash, const Allocator& alloc)
181 : robin_map(first, last, bucket_count, hash, KeyEqual(), alloc) {}
182 
183 robin_map(std::initializer_list<value_type> init,
184 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
185 const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(),
186 const Allocator& alloc = Allocator())
187 : robin_map(init.begin(), init.end(), bucket_count, hash, equal, alloc) {}
188 
189 robin_map(std::initializer_list<value_type> init, size_type bucket_count,
190 const Allocator& alloc)
191 : robin_map(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(),
192 alloc) {}
193 
194 robin_map(std::initializer_list<value_type> init, size_type bucket_count,
195 const Hash& hash, const Allocator& alloc)
196 : robin_map(init.begin(), init.end(), bucket_count, hash, KeyEqual(),
197 alloc) {}
198 
199 robin_map& operator=(std::initializer_list<value_type> ilist) {
200 m_ht.clear();
201 
202 m_ht.reserve(ilist.size());
203 m_ht.insert(ilist.begin(), ilist.end());
204 
205 return *this;
206 }
207 
208 allocator_type get_allocator() const { return m_ht.get_allocator(); }
209 
210 /*
211 * Iterators
212 */
213 iterator begin() noexcept { return m_ht.begin(); }
214 const_iterator begin() const noexcept { return m_ht.begin(); }
215 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
216 
217 iterator end() noexcept { return m_ht.end(); }
218 const_iterator end() const noexcept { return m_ht.end(); }
219 const_iterator cend() const noexcept { return m_ht.cend(); }
220 
221 /*
222 * Capacity
223 */
224 bool empty() const noexcept { return m_ht.empty(); }
225 size_type size() const noexcept { return m_ht.size(); }
226 size_type max_size() const noexcept { return m_ht.max_size(); }
227 
228 /*
229 * Modifiers
230 */
231 void clear() noexcept { m_ht.clear(); }
232 
233 std::pair<iterator, bool> insert(const value_type& value) {
234 return m_ht.insert(value);
235 }
236 
237 template <class P, typename std::enable_if<std::is_constructible<
238 value_type, P&&>::value>::type* = nullptr>
239 std::pair<iterator, bool> insert(P&& value) {
240 return m_ht.emplace(std::forward<P>(value));
241 }
242 
243 std::pair<iterator, bool> insert(value_type&& value) {
244 return m_ht.insert(std::move(value));
245 }
246 
247 iterator insert(const_iterator hint, const value_type& value) {
248 return m_ht.insert_hint(hint, value);
249 }
250 
251 template <class P, typename std::enable_if<std::is_constructible<
252 value_type, P&&>::value>::type* = nullptr>
253 iterator insert(const_iterator hint, P&& value) {
254 return m_ht.emplace_hint(hint, std::forward<P>(value));
255 }
256 
257 iterator insert(const_iterator hint, value_type&& value) {
258 return m_ht.insert_hint(hint, std::move(value));
259 }
260 
261 template <class InputIt>
262 void insert(InputIt first, InputIt last) {
263 m_ht.insert(first, last);
264 }
265 
266 void insert(std::initializer_list<value_type> ilist) {
267 m_ht.insert(ilist.begin(), ilist.end());
268 }
269 
270 template <class M>
271 std::pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj) {
272 return m_ht.insert_or_assign(k, std::forward<M>(obj));
273 }
274 
275 template <class M>
276 std::pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj) {
277 return m_ht.insert_or_assign(std::move(k), std::forward<M>(obj));
278 }
279 
280 template <class M>
281 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj) {
282 return m_ht.insert_or_assign(hint, k, std::forward<M>(obj));
283 }
284 
285 template <class M>
286 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj) {
287 return m_ht.insert_or_assign(hint, std::move(k), std::forward<M>(obj));
288 }
289 
290 /**
291 * Due to the way elements are stored, emplace will need to move or copy the
292 * key-value once. The method is equivalent to
293 * insert(value_type(std::forward<Args>(args)...));
294 *
295 * Mainly here for compatibility with the std::unordered_map interface.
296 */
297 template <class... Args>
298 std::pair<iterator, bool> emplace(Args&&... args) {
299 return m_ht.emplace(std::forward<Args>(args)...);
300 }
301 
302 /**
303 * Due to the way elements are stored, emplace_hint will need to move or copy
304 * the key-value once. The method is equivalent to insert(hint,
305 * value_type(std::forward<Args>(args)...));
306 *
307 * Mainly here for compatibility with the std::unordered_map interface.
308 */
309 template <class... Args>
310 iterator emplace_hint(const_iterator hint, Args&&... args) {
311 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
312 }
313 
314 template <class... Args>
315 std::pair<iterator, bool> try_emplace(const key_type& k, Args&&... args) {
316 return m_ht.try_emplace(k, std::forward<Args>(args)...);
317 }
318 
319 template <class... Args>
320 std::pair<iterator, bool> try_emplace(key_type&& k, Args&&... args) {
321 return m_ht.try_emplace(std::move(k), std::forward<Args>(args)...);
322 }
323 
324 template <class... Args>
325 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args) {
326 return m_ht.try_emplace_hint(hint, k, std::forward<Args>(args)...);
327 }
328 
329 template <class... Args>
330 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args) {
331 return m_ht.try_emplace_hint(hint, std::move(k),
332 std::forward<Args>(args)...);
333 }
334 
335 iterator erase(iterator pos) { return m_ht.erase(pos); }
336 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
337 iterator erase(const_iterator first, const_iterator last) {
338 return m_ht.erase(first, last);
339 }
340 size_type erase(const key_type& key) { return m_ht.erase(key); }
341 
342 /**
343 * Erase the element at position 'pos'. In contrast to the regular erase()
344 * function, erase_fast() does not return an iterator. This allows it to be
345 * faster especially in hash tables with a low load factor, where finding the
346 * next nonempty bucket would be costly.
347 */
348 void erase_fast(iterator pos) { return m_ht.erase_fast(pos); }
349 
350 /**
351 * Use the hash value 'precalculated_hash' instead of hashing the key. The
352 * hash value should be the same as hash_function()(key). Useful to speed-up
353 * the lookup to the value if you already have the hash.
354 */
355 size_type erase(const key_type& key, std::size_t precalculated_hash) {
356 return m_ht.erase(key, precalculated_hash);
357 }
358 
359 /**
360 * This overload only participates in the overload resolution if the typedef
361 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
362 * to Key.
363 */
364 template <
365 class K, class KE = KeyEqual,
366 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
367 size_type erase(const K& key) {
368 return m_ht.erase(key);
369 }
370 
371 /**
372 * @copydoc erase(const K& key)
373 *
374 * Use the hash value 'precalculated_hash' instead of hashing the key. The
375 * hash value should be the same as hash_function()(key). Useful to speed-up
376 * the lookup to the value if you already have the hash.
377 */
378 template <
379 class K, class KE = KeyEqual,
380 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
381 size_type erase(const K& key, std::size_t precalculated_hash) {
382 return m_ht.erase(key, precalculated_hash);
383 }
384 
385 void swap(robin_map& other) { other.m_ht.swap(m_ht); }
386 
387 /*
388 * Lookup
389 */
390 T& at(const Key& key) { return m_ht.at(key); }
391 
392 /**
393 * Use the hash value 'precalculated_hash' instead of hashing the key. The
394 * hash value should be the same as hash_function()(key). Useful to speed-up
395 * the lookup if you already have the hash.
396 */
397 T& at(const Key& key, std::size_t precalculated_hash) {
398 return m_ht.at(key, precalculated_hash);
399 }
400 
401 const T& at(const Key& key) const { return m_ht.at(key); }
402 
403 /**
404 * @copydoc at(const Key& key, std::size_t precalculated_hash)
405 */
406 const T& at(const Key& key, std::size_t precalculated_hash) const {
407 return m_ht.at(key, precalculated_hash);
408 }
409 
410 /**
411 * This overload only participates in the overload resolution if the typedef
412 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
413 * to Key.
414 */
415 template <
416 class K, class KE = KeyEqual,
417 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
418 T& at(const K& key) {
419 return m_ht.at(key);
420 }
421 
422 /**
423 * @copydoc at(const K& key)
424 *
425 * Use the hash value 'precalculated_hash' instead of hashing the key. The
426 * hash value should be the same as hash_function()(key). Useful to speed-up
427 * the lookup if you already have the hash.
428 */
429 template <
430 class K, class KE = KeyEqual,
431 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
432 T& at(const K& key, std::size_t precalculated_hash) {
433 return m_ht.at(key, precalculated_hash);
434 }
435 
436 /**
437 * @copydoc at(const K& key)
438 */
439 template <
440 class K, class KE = KeyEqual,
441 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
442 const T& at(const K& key) const {
443 return m_ht.at(key);
444 }
445 
446 /**
447 * @copydoc at(const K& key, std::size_t precalculated_hash)
448 */
449 template <
450 class K, class KE = KeyEqual,
451 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
452 const T& at(const K& key, std::size_t precalculated_hash) const {
453 return m_ht.at(key, precalculated_hash);
454 }
455 
456 T& operator[](const Key& key) { return m_ht[key]; }
457 T& operator[](Key&& key) { return m_ht[std::move(key)]; }
458 
459 size_type count(const Key& key) const { return m_ht.count(key); }
460 
461 /**
462 * Use the hash value 'precalculated_hash' instead of hashing the key. The
463 * hash value should be the same as hash_function()(key). Useful to speed-up
464 * the lookup if you already have the hash.
465 */
466 size_type count(const Key& key, std::size_t precalculated_hash) const {
467 return m_ht.count(key, precalculated_hash);
468 }
469 
470 /**
471 * This overload only participates in the overload resolution if the typedef
472 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
473 * to Key.
474 */
475 template <
476 class K, class KE = KeyEqual,
477 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
478 size_type count(const K& key) const {
479 return m_ht.count(key);
480 }
481 
482 /**
483 * @copydoc count(const K& key) const
484 *
485 * Use the hash value 'precalculated_hash' instead of hashing the key. The
486 * hash value should be the same as hash_function()(key). Useful to speed-up
487 * the lookup if you already have the hash.
488 */
489 template <
490 class K, class KE = KeyEqual,
491 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
492 size_type count(const K& key, std::size_t precalculated_hash) const {
493 return m_ht.count(key, precalculated_hash);
494 }
495 
496 iterator find(const Key& key) { return m_ht.find(key); }
497 
498 /**
499 * Use the hash value 'precalculated_hash' instead of hashing the key. The
500 * hash value should be the same as hash_function()(key). Useful to speed-up
501 * the lookup if you already have the hash.
502 */
503 iterator find(const Key& key, std::size_t precalculated_hash) {
504 return m_ht.find(key, precalculated_hash);
505 }
506 
507 const_iterator find(const Key& key) const { return m_ht.find(key); }
508 
509 /**
510 * @copydoc find(const Key& key, std::size_t precalculated_hash)
511 */
512 const_iterator find(const Key& key, std::size_t precalculated_hash) const {
513 return m_ht.find(key, precalculated_hash);
514 }
515 
516 /**
517 * This overload only participates in the overload resolution if the typedef
518 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
519 * to Key.
520 */
521 template <
522 class K, class KE = KeyEqual,
523 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
524 iterator find(const K& key) {
525 return m_ht.find(key);
526 }
527 
528 /**
529 * @copydoc find(const K& key)
530 *
531 * Use the hash value 'precalculated_hash' instead of hashing the key. The
532 * hash value should be the same as hash_function()(key). Useful to speed-up
533 * the lookup if you already have the hash.
534 */
535 template <
536 class K, class KE = KeyEqual,
537 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
538 iterator find(const K& key, std::size_t precalculated_hash) {
539 return m_ht.find(key, precalculated_hash);
540 }
541 
542 /**
543 * @copydoc find(const K& key)
544 */
545 template <
546 class K, class KE = KeyEqual,
547 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
548 const_iterator find(const K& key) const {
549 return m_ht.find(key);
550 }
551 
552 /**
553 * @copydoc find(const K& key)
554 *
555 * Use the hash value 'precalculated_hash' instead of hashing the key. The
556 * hash value should be the same as hash_function()(key). Useful to speed-up
557 * the lookup if you already have the hash.
558 */
559 template <
560 class K, class KE = KeyEqual,
561 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
562 const_iterator find(const K& key, std::size_t precalculated_hash) const {
563 return m_ht.find(key, precalculated_hash);
564 }
565 
566 bool contains(const Key& key) const { return m_ht.contains(key); }
567 
568 /**
569 * Use the hash value 'precalculated_hash' instead of hashing the key. The
570 * hash value should be the same as hash_function()(key). Useful to speed-up
571 * the lookup if you already have the hash.
572 */
573 bool contains(const Key& key, std::size_t precalculated_hash) const {
574 return m_ht.contains(key, precalculated_hash);
575 }
576 
577 /**
578 * This overload only participates in the overload resolution if the typedef
579 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
580 * to Key.
581 */
582 template <
583 class K, class KE = KeyEqual,
584 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
585 bool contains(const K& key) const {
586 return m_ht.contains(key);
587 }
588 
589 /**
590 * @copydoc contains(const K& key) const
591 *
592 * Use the hash value 'precalculated_hash' instead of hashing the key. The
593 * hash value should be the same as hash_function()(key). Useful to speed-up
594 * the lookup if you already have the hash.
595 */
596 template <
597 class K, class KE = KeyEqual,
598 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
599 bool contains(const K& key, std::size_t precalculated_hash) const {
600 return m_ht.contains(key, precalculated_hash);
601 }
602 
603 std::pair<iterator, iterator> equal_range(const Key& key) {
604 return m_ht.equal_range(key);
605 }
606 
607 /**
608 * Use the hash value 'precalculated_hash' instead of hashing the key. The
609 * hash value should be the same as hash_function()(key). Useful to speed-up
610 * the lookup if you already have the hash.
611 */
612 std::pair<iterator, iterator> equal_range(const Key& key,
613 std::size_t precalculated_hash) {
614 return m_ht.equal_range(key, precalculated_hash);
615 }
616 
617 std::pair<const_iterator, const_iterator> equal_range(const Key& key) const {
618 return m_ht.equal_range(key);
619 }
620 
621 /**
622 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
623 */
624 std::pair<const_iterator, const_iterator> equal_range(
625 const Key& key, std::size_t precalculated_hash) const {
626 return m_ht.equal_range(key, precalculated_hash);
627 }
628 
629 /**
630 * This overload only participates in the overload resolution if the typedef
631 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
632 * to Key.
633 */
634 template <
635 class K, class KE = KeyEqual,
636 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
637 std::pair<iterator, iterator> equal_range(const K& key) {
638 return m_ht.equal_range(key);
639 }
640 
641 /**
642 * @copydoc equal_range(const K& key)
643 *
644 * Use the hash value 'precalculated_hash' instead of hashing the key. The
645 * hash value should be the same as hash_function()(key). Useful to speed-up
646 * the lookup if you already have the hash.
647 */
648 template <
649 class K, class KE = KeyEqual,
650 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
651 std::pair<iterator, iterator> equal_range(const K& key,
652 std::size_t precalculated_hash) {
653 return m_ht.equal_range(key, precalculated_hash);
654 }
655 
656 /**
657 * @copydoc equal_range(const K& key)
658 */
659 template <
660 class K, class KE = KeyEqual,
661 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
662 std::pair<const_iterator, const_iterator> equal_range(const K& key) const {
663 return m_ht.equal_range(key);
664 }
665 
666 /**
667 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
668 */
669 template <
670 class K, class KE = KeyEqual,
671 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
672 std::pair<const_iterator, const_iterator> equal_range(
673 const K& key, std::size_t precalculated_hash) const {
674 return m_ht.equal_range(key, precalculated_hash);
675 }
676 
677 /*
678 * Bucket interface
679 */
680 size_type bucket_count() const { return m_ht.bucket_count(); }
681 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
682 
683 /*
684 * Hash policy
685 */
686 float load_factor() const { return m_ht.load_factor(); }
687 
688 float min_load_factor() const { return m_ht.min_load_factor(); }
689 float max_load_factor() const { return m_ht.max_load_factor(); }
690 
691 /**
692 * Set the `min_load_factor` to `ml`. When the `load_factor` of the map goes
693 * below `min_load_factor` after some erase operations, the map will be
694 * shrunk when an insertion occurs. The erase method itself never shrinks
695 * the map.
696 *
697 * The default value of `min_load_factor` is 0.0f, the map never shrinks by
698 * default.
699 */
700 void min_load_factor(float ml) { m_ht.min_load_factor(ml); }
701 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
702 
703 void rehash(size_type count_) { m_ht.rehash(count_); }
704 void reserve(size_type count_) { m_ht.reserve(count_); }
705 
706 /*
707 * Observers
708 */
709 hasher hash_function() const { return m_ht.hash_function(); }
710 key_equal key_eq() const { return m_ht.key_eq(); }
711 
712 /*
713 * Other
714 */
715 
716 /**
717 * Convert a const_iterator to an iterator.
718 */
719 iterator mutable_iterator(const_iterator pos) {
720 return m_ht.mutable_iterator(pos);
721 }
722 
723 /**
724 * Serialize the map through the `serializer` parameter.
725 *
726 * The `serializer` parameter must be a function object that supports the
727 * following call:
728 * - `template<typename U> void operator()(const U& value);` where the types
729 * `std::int16_t`, `std::uint32_t`, `std::uint64_t`, `float` and
730 * `std::pair<Key, T>` must be supported for U.
731 *
732 * The implementation leaves binary compatibility (endianness, IEEE 754 for
733 * floats, ...) of the types it serializes in the hands of the `Serializer`
734 * function object if compatibility is required.
735 */
736 template <class Serializer>
737 void serialize(Serializer& serializer) const {
738 m_ht.serialize(serializer);
739 }
740 
741 /**
742 * Deserialize a previously serialized map through the `deserializer`
743 * parameter.
744 *
745 * The `deserializer` parameter must be a function object that supports the
746 * following call:
747 * - `template<typename U> U operator()();` where the types `std::int16_t`,
748 * `std::uint32_t`, `std::uint64_t`, `float` and `std::pair<Key, T>` must be
749 * supported for U.
750 *
751 * If the deserialized hash map type is hash compatible with the serialized
752 * map, the deserialization process can be sped up by setting
753 * `hash_compatible` to true. To be hash compatible, the Hash, KeyEqual and
754 * GrowthPolicy must behave the same way than the ones used on the serialized
755 * map and the StoreHash must have the same value. The `std::size_t` must also
756 * be of the same size as the one on the platform used to serialize the map.
757 * If these criteria are not met, the behaviour is undefined with
758 * `hash_compatible` sets to true.
759 *
760 * The behaviour is undefined if the type `Key` and `T` of the `robin_map` are
761 * not the same as the types used during serialization.
762 *
763 * The implementation leaves binary compatibility (endianness, IEEE 754 for
764 * floats, size of int, ...) of the types it deserializes in the hands of the
765 * `Deserializer` function object if compatibility is required.
766 */
767 template <class Deserializer>
768 static robin_map deserialize(Deserializer& deserializer,
769 bool hash_compatible = false) {
770 robin_map map(0);
771 map.m_ht.deserialize(deserializer, hash_compatible);
772 
773 return map;
774 }
775 
776 friend bool operator==(const robin_map& lhs, const robin_map& rhs) {
777 if (lhs.size() != rhs.size()) {
778 return false;
779 }
780 
781 for (const auto& element_lhs : lhs) {
782 const auto it_element_rhs = rhs.find(element_lhs.first);
783 if (it_element_rhs == rhs.cend() ||
784 element_lhs.second != it_element_rhs->second) {
785 return false;
786 }
787 }
788 
789 return true;
790 }
791 
792 friend bool operator!=(const robin_map& lhs, const robin_map& rhs) {
793 return !operator==(lhs, rhs);
794 }
795 
796 friend void swap(robin_map& lhs, robin_map& rhs) { lhs.swap(rhs); }
797 
798 private:
799 ht m_ht;
800};
801 
802/**
803 * Same as `tsl::robin_map<Key, T, Hash, KeyEqual, Allocator, StoreHash,
804 * tsl::rh::prime_growth_policy>`.
805 */
806template <class Key, class T, class Hash = std::hash<Key>,
807 class KeyEqual = std::equal_to<Key>,
808 class Allocator = std::allocator<std::pair<Key, T>>,
809 bool StoreHash = false>
810using robin_pg_map = robin_map<Key, T, Hash, KeyEqual, Allocator, StoreHash,
811 tsl::rh::prime_growth_policy>;
812 
813} // end namespace tsl
814 
815#endif
816