1/**
2 * MIT License
3 *
4 * Copyright (c) 2017 Tessil
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 all
14 * 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_HOPSCOTCH_HASH_H
25#define TSL_HOPSCOTCH_HASH_H
26
27
28#include <algorithm>
29#include <array>
30#include <cassert>
31#include <cmath>
32#include <climits>
33#include <cstddef>
34#include <cstdint>
35#include <exception>
36#include <functional>
37#include <initializer_list>
38#include <iterator>
39#include <limits>
40#include <memory>
41#include <ratio>
42#include <stdexcept>
43#include <tuple>
44#include <type_traits>
45#include <utility>
46#include <vector>
47
48#if (defined(__GNUC__) && (__GNUC__ == 4) && (__GNUC_MINOR__ < 9))
49#define TSL_NO_RANGE_ERASE_WITH_CONST_ITERATOR
50#endif
51
52
53
54/*
55 * Only activate tsl_assert if TSL_DEBUG is defined.
56 * This way we avoid the performance hit when NDEBUG is not defined with assert as tsl_assert is used a lot
57 * (people usually compile with "-O3" and not "-O3 -DNDEBUG").
58 */
59#ifndef tsl_assert
60 #ifdef TSL_DEBUG
61 #define tsl_assert(expr) assert(expr)
62 #else
63 #define tsl_assert(expr) (static_cast<void>(0))
64 #endif
65#endif
66
67namespace tsl {
68
69/**
70 * Grow the map by a factor of two keeping bucket_count to a power of two. It allows
71 * the map to use a mask operation instead of a modulo operation to map a hash to a bucket.
72 */
73class power_of_two_growth_policy {
74public:
75 /**
76 * Called on map creation and rehash. The number of buckets requested is passed by parameter.
77 * This number is a minimum, the policy may update this value with a higher value if needed.
78 */
79 power_of_two_growth_policy(std::size_t& min_bucket_count_in_out) {
80 if(min_bucket_count_in_out > max_bucket_count()) {
81 throw std::length_error("The map exceeds its maxmimum size.");
82 }
83
84 static_assert(MIN_BUCKETS_SIZE > 0, "");
85 const std::size_t min_bucket_count = MIN_BUCKETS_SIZE;
86
87 min_bucket_count_in_out = std::max(min_bucket_count, min_bucket_count_in_out);
88 min_bucket_count_in_out = round_up_to_power_of_two(min_bucket_count_in_out);
89 m_mask = min_bucket_count_in_out - 1;
90 }
91
92 /**
93 * Return the bucket [0, bucket_count()) to which the hash belongs.
94 */
95 std::size_t bucket_for_hash(std::size_t hash) const {
96 return hash & m_mask;
97 }
98
99 /**
100 * Return the bucket count to uses when the bucket array grows on rehash.
101 */
102 std::size_t next_bucket_count() const {
103 if((m_mask + 1) > max_bucket_count()/2) {
104 throw std::length_error("The map exceeds its maxmimum size.");
105 }
106
107 return (m_mask + 1) * 2;
108 }
109
110 /**
111 * Return the maximum number of buckets supported by the policy.
112 */
113 std::size_t max_bucket_count() const {
114 return std::numeric_limits<std::size_t>::max()/2 + 1;
115 }
116
117private:
118 static std::size_t round_up_to_power_of_two(std::size_t value) {
119 if(value == 0) {
120 return 1;
121 }
122
123 if(is_power_of_two(value)) {
124 return value;
125 }
126
127 --value;
128 for(std::size_t i = 1; i < sizeof(std::size_t) * CHAR_BIT; i *= 2) {
129 value |= value >> i;
130 }
131
132 return value + 1;
133 }
134
135 static constexpr bool is_power_of_two(std::size_t value) {
136 return value != 0 && (value & (value - 1)) == 0;
137 }
138
139private:
140 static const std::size_t MIN_BUCKETS_SIZE = 2;
141
142 std::size_t m_mask;
143};
144
145/**
146 * Grow the map by GrowthFactor::num/GrowthFactor::den and use a modulo to map a hash
147 * to a bucket. Slower but it can be usefull if you want a slower growth.
148 */
149template<class GrowthFactor = std::ratio<3, 2>>
150class mod_growth_policy {
151public:
152 mod_growth_policy(std::size_t& min_bucket_count_in_out) {
153 if(min_bucket_count_in_out > max_bucket_count()) {
154 throw std::length_error("The map exceeds its maxmimum size.");
155 }
156
157 static_assert(MIN_BUCKETS_SIZE > 0, "");
158 const std::size_t min_bucket_count = MIN_BUCKETS_SIZE;
159
160 min_bucket_count_in_out = std::max(min_bucket_count, min_bucket_count_in_out);
161 m_bucket_count = min_bucket_count_in_out;
162 }
163
164 std::size_t bucket_for_hash(std::size_t hash) const {
165 tsl_assert(m_bucket_count != 0);
166 return hash % m_bucket_count;
167 }
168
169 std::size_t next_bucket_count() const {
170 if(m_bucket_count == max_bucket_count()) {
171 throw std::length_error("The map exceeds its maxmimum size.");
172 }
173
174 const double next_bucket_count = std::ceil(double(m_bucket_count) * REHASH_SIZE_MULTIPLICATION_FACTOR);
175 if(!std::isnormal(next_bucket_count)) {
176 throw std::length_error("The map exceeds its maxmimum size.");
177 }
178
179 if(next_bucket_count > double(max_bucket_count())) {
180 return max_bucket_count();
181 }
182 else {
183 return std::size_t(next_bucket_count);
184 }
185 }
186
187 std::size_t max_bucket_count() const {
188 return MAX_BUCKET_COUNT;
189 }
190
191private:
192 static const std::size_t MIN_BUCKETS_SIZE = 2;
193 static constexpr double REHASH_SIZE_MULTIPLICATION_FACTOR = 1.0*GrowthFactor::num/GrowthFactor::den;
194 static const std::size_t MAX_BUCKET_COUNT =
195 std::size_t(double(
196 std::numeric_limits<std::size_t>::max()/REHASH_SIZE_MULTIPLICATION_FACTOR
197 ));
198
199 static_assert(REHASH_SIZE_MULTIPLICATION_FACTOR >= 1.1, "Grow factor should be >= 1.1.");
200
201 std::size_t m_bucket_count;
202};
203
204
205
206namespace detail_hopscotch_hash {
207
208static constexpr const std::array<std::size_t, 39> PRIMES = {{
209 5ul, 17ul, 29ul, 37ul, 53ul, 67ul, 79ul, 97ul, 131ul, 193ul, 257ul, 389ul, 521ul, 769ul, 1031ul, 1543ul, 2053ul,
210 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul,
211 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
212 1610612741ul, 3221225473ul, 4294967291ul
213}};
214
215template<unsigned int IPrime>
216static std::size_t mod(std::size_t hash) { return hash % PRIMES[IPrime]; }
217
218// MOD_PRIME[iprime](hash) returns hash % PRIMES[iprime]. This table allows for faster modulo as the
219// compiler can optimize the modulo code better with a constant known at the compilation.
220static constexpr const std::array<std::size_t(*)(std::size_t), 39> MOD_PRIME = {{
221 &mod<0>, &mod<1>, &mod<2>, &mod<3>, &mod<4>, &mod<5>, &mod<6>, &mod<7>, &mod<8>, &mod<9>, &mod<10>,
222 &mod<11>, &mod<12>, &mod<13>, &mod<14>, &mod<15>, &mod<16>, &mod<17>, &mod<18>, &mod<19>, &mod<20>,
223 &mod<21>, &mod<22>, &mod<23>, &mod<24>, &mod<25>, &mod<26>, &mod<27>, &mod<28>, &mod<29>, &mod<30>,
224 &mod<31>, &mod<32>, &mod<33>, &mod<34>, &mod<35>, &mod<36>, &mod<37> , &mod<38>
225}};
226
227}
228
229/**
230 * Grow the map by using prime numbers as size. Slower than tsl::power_of_two_growth_policy in general
231 * but will probably distribute the values around better in the buckets with a poor hash function.
232 */
233class prime_growth_policy {
234public:
235 prime_growth_policy(std::size_t& min_bucket_count_in_out) {
236 auto it_prime = std::lower_bound(tsl::detail_hopscotch_hash::PRIMES.begin(),
237 tsl::detail_hopscotch_hash::PRIMES.end(), min_bucket_count_in_out);
238 if(it_prime == tsl::detail_hopscotch_hash::PRIMES.end()) {
239 throw std::length_error("The map exceeds its maxmimum size.");
240 }
241
242 m_iprime = static_cast<unsigned int>(std::distance(tsl::detail_hopscotch_hash::PRIMES.begin(), it_prime));
243 min_bucket_count_in_out = *it_prime;
244 }
245
246 std::size_t bucket_for_hash(std::size_t hash) const {
247 return bucket_for_hash_iprime(hash, m_iprime);
248 }
249
250 std::size_t next_bucket_count() const {
251 if(m_iprime + 1 >= tsl::detail_hopscotch_hash::PRIMES.size()) {
252 throw std::length_error("The map exceeds its maxmimum size.");
253 }
254
255 return tsl::detail_hopscotch_hash::PRIMES[m_iprime + 1];
256 }
257
258 std::size_t max_bucket_count() const {
259 return tsl::detail_hopscotch_hash::PRIMES.back();
260 }
261
262private:
263 std::size_t bucket_for_hash_iprime(std::size_t hash, unsigned int iprime) const {
264 tsl_assert(iprime < tsl::detail_hopscotch_hash::MOD_PRIME.size());
265 return tsl::detail_hopscotch_hash::MOD_PRIME[iprime](hash);
266 }
267
268private:
269 unsigned int m_iprime;
270};
271
272
273namespace detail_hopscotch_hash {
274
275
276
277template<typename T>
278struct make_void {
279 using type = void;
280};
281
282
283template<typename T, typename = void>
284struct has_is_transparent : std::false_type {
285};
286
287template<typename T>
288struct has_is_transparent<T, typename make_void<typename T::is_transparent>::type> : std::true_type {
289};
290
291
292template<typename T, typename = void>
293struct has_key_compare : std::false_type {
294};
295
296template<typename T>
297struct has_key_compare<T, typename make_void<typename T::key_compare>::type> : std::true_type {
298};
299
300
301
302
303
304/*
305 * smallest_type_for_min_bits::type returns the smallest type that can fit MinBits.
306 */
307static const size_t SMALLEST_TYPE_MAX_BITS_SUPPORTED = 64;
308template<unsigned int MinBits, typename Enable = void>
309class smallest_type_for_min_bits {
310};
311
312template<unsigned int MinBits>
313class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 0) && (MinBits <= 8)>::type> {
314public:
315 using type = std::uint_least8_t;
316};
317
318template<unsigned int MinBits>
319class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 8) && (MinBits <= 16)>::type> {
320public:
321 using type = std::uint_least16_t;
322};
323
324template<unsigned int MinBits>
325class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 16) && (MinBits <= 32)>::type> {
326public:
327 using type = std::uint_least32_t;
328};
329
330template<unsigned int MinBits>
331class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 32) && (MinBits <= 64)>::type> {
332public:
333 using type = std::uint_least64_t;
334};
335
336
337
338/*
339 * Each bucket may store up to three elements:
340 * - An aligned storage to store a value_type object with placement-new.
341 * - An (optional) hash of the value in the bucket.
342 * - An unsigned integer of type neighborhood_bitmap used to tell us which buckets in the neighborhood of the
343 * current bucket contain a value with a hash belonging to the current bucket.
344 *
345 * For a bucket 'b' a bit 'i' (counting from 0 and from the least significant bit to the most significant)
346 * set to 1 means that the bucket 'b+i' contains a value with a hash belonging to bucket 'b'.
347 * The bits used for that, start from the third least significant bit.
348 *
349 * The least significant bit is set to 1 if there is a value in the bucket storage.
350 * The second least significant bit is set to 1 if there is an overflow. More than NeighborhoodSize values
351 * give the same hash, all overflow values are stored in the m_overflow_elements list of the map.
352 */
353static const std::size_t NB_RESERVED_BITS_IN_NEIGHBORHOOD = 2;
354
355
356template<bool StoreHash>
357class hopscotch_bucket_hash {
358public:
359 using hash_type = std::false_type;
360
361 bool bucket_hash_equal(std::size_t /*hash*/) const noexcept {
362 return true;
363 }
364
365 std::size_t truncated_bucket_hash() const noexcept {
366 assert(false);
367 return 0;
368 }
369
370protected:
371 void copy_hash(const hopscotch_bucket_hash& ) noexcept {
372 }
373
374 void set_hash(std::size_t /*hash*/) noexcept {
375 }
376};
377
378template<>
379class hopscotch_bucket_hash<true> {
380public:
381 using hash_type = std::uint_least32_t;
382 static_assert(sizeof(hash_type) <= sizeof(std::size_t), "");
383
384 bool bucket_hash_equal(std::size_t hash) const noexcept {
385 return m_hash == hash_type(hash);
386 }
387
388 std::size_t truncated_bucket_hash() const noexcept {
389 return m_hash;
390 }
391
392protected:
393 void copy_hash(const hopscotch_bucket_hash& bucket) noexcept {
394 m_hash = bucket.m_hash;
395 }
396
397 void set_hash(std::size_t hash) noexcept {
398 m_hash = hash_type(hash);
399 }
400
401private:
402 hash_type m_hash;
403};
404
405template<typename ValueType, unsigned int NeighborhoodSize, bool StoreHash>
406class hopscotch_bucket: public hopscotch_bucket_hash<StoreHash> {
407private:
408 static const size_t MIN_NEIGHBORHOOD_SIZE = 4;
409 static const size_t MAX_NEIGHBORHOOD_SIZE = SMALLEST_TYPE_MAX_BITS_SUPPORTED - NB_RESERVED_BITS_IN_NEIGHBORHOOD;
410
411
412 static_assert(NeighborhoodSize >= 4, "NeighborhoodSize should be >= 4.");
413 // We can't put a variable in the message, ensure coherence
414 static_assert(MIN_NEIGHBORHOOD_SIZE == 4, "");
415
416 static_assert(NeighborhoodSize <= 62, "NeighborhoodSize should be <= 62.");
417 // We can't put a variable in the message, ensure coherence
418 static_assert(MAX_NEIGHBORHOOD_SIZE == 62, "");
419
420
421 static_assert(!StoreHash || NeighborhoodSize <= 30,
422 "NeighborhoodSize should be <= 30 if StoreHash is true.");
423 // We can't put a variable in the message, ensure coherence
424 static_assert(MAX_NEIGHBORHOOD_SIZE - 32 == 30, "");
425
426 using bucket_hash = hopscotch_bucket_hash<StoreHash>;
427
428public:
429 using value_type = ValueType;
430 using neighborhood_bitmap =
431 typename smallest_type_for_min_bits<NeighborhoodSize + NB_RESERVED_BITS_IN_NEIGHBORHOOD>::type;
432
433
434 hopscotch_bucket() noexcept: bucket_hash(), m_neighborhood_infos(0) {
435 tsl_assert(empty());
436 }
437
438
439 hopscotch_bucket(const hopscotch_bucket& bucket)
440 noexcept(std::is_nothrow_copy_constructible<value_type>::value): bucket_hash(bucket),
441 m_neighborhood_infos(0)
442 {
443 if(!bucket.empty()) {
444 ::new (static_cast<void*>(std::addressof(m_value))) value_type(bucket.value());
445 }
446
447 m_neighborhood_infos = bucket.m_neighborhood_infos;
448 }
449
450 hopscotch_bucket(hopscotch_bucket&& bucket)
451 noexcept(std::is_nothrow_move_constructible<value_type>::value) : bucket_hash(std::move(bucket)),
452 m_neighborhood_infos(0)
453 {
454 if(!bucket.empty()) {
455 ::new (static_cast<void*>(std::addressof(m_value))) value_type(std::move(bucket.value()));
456 }
457
458 m_neighborhood_infos = bucket.m_neighborhood_infos;
459 }
460
461 hopscotch_bucket& operator=(const hopscotch_bucket& bucket)
462 noexcept(std::is_nothrow_copy_constructible<value_type>::value)
463 {
464 if(this != &bucket) {
465 bucket_hash::operator=(bucket);
466
467 if(!empty()) {
468 destroy_value();
469 set_empty(true);
470 }
471
472 if(!bucket.empty()) {
473 ::new (static_cast<void*>(std::addressof(m_value))) value_type(bucket.value());
474 }
475
476 m_neighborhood_infos = bucket.m_neighborhood_infos;
477 }
478
479 return *this;
480 }
481
482 hopscotch_bucket& operator=(hopscotch_bucket&& ) = delete;
483
484 ~hopscotch_bucket() noexcept {
485 if(!empty()) {
486 destroy_value();
487 }
488 }
489
490 neighborhood_bitmap neighborhood_infos() const noexcept {
491 return neighborhood_bitmap(m_neighborhood_infos >> NB_RESERVED_BITS_IN_NEIGHBORHOOD);
492 }
493
494 void set_overflow(bool has_overflow) noexcept {
495 if(has_overflow) {
496 m_neighborhood_infos = neighborhood_bitmap(m_neighborhood_infos | 2);
497 }
498 else {
499 m_neighborhood_infos = neighborhood_bitmap(m_neighborhood_infos & ~2);
500 }
501 }
502
503 bool has_overflow() const noexcept {
504 return (m_neighborhood_infos & 2) != 0;
505 }
506
507 bool empty() const noexcept {
508 return (m_neighborhood_infos & 1) == 0;
509 }
510
511 void toggle_neighbor_presence(std::size_t ineighbor) noexcept {
512 tsl_assert(ineighbor <= NeighborhoodSize);
513 m_neighborhood_infos = neighborhood_bitmap(
514 m_neighborhood_infos ^ (1ull << (ineighbor + NB_RESERVED_BITS_IN_NEIGHBORHOOD)));
515 }
516
517 bool check_neighbor_presence(std::size_t ineighbor) const noexcept {
518 tsl_assert(ineighbor <= NeighborhoodSize);
519 if(((m_neighborhood_infos >> (ineighbor + NB_RESERVED_BITS_IN_NEIGHBORHOOD)) & 1) == 1) {
520 return true;
521 }
522
523 return false;
524 }
525
526 value_type& value() noexcept {
527 tsl_assert(!empty());
528 return *reinterpret_cast<value_type*>(std::addressof(m_value));
529 }
530
531 const value_type& value() const noexcept {
532 tsl_assert(!empty());
533 return *reinterpret_cast<const value_type*>(std::addressof(m_value));
534 }
535
536 template<typename P>
537 void set_value_of_empty_bucket(P&& value, std::size_t hash) {
538 tsl_assert(empty());
539
540 ::new (static_cast<void*>(std::addressof(m_value))) value_type(std::forward<P>(value));
541 set_empty(false);
542 this->set_hash(hash);
543 }
544
545 void swap_value_into_empty_bucket(hopscotch_bucket& empty_bucket) {
546 tsl_assert(empty_bucket.empty());
547 if(!empty()) {
548 ::new (static_cast<void*>(std::addressof(empty_bucket.m_value))) value_type(std::move(value()));
549 empty_bucket.copy_hash(*this);
550 empty_bucket.set_empty(false);
551
552 destroy_value();
553 set_empty(true);
554 }
555 }
556
557 void remove_value() noexcept {
558 if(!empty()) {
559 destroy_value();
560 set_empty(true);
561 }
562 }
563
564 void clear() noexcept {
565 if(!empty()) {
566 destroy_value();
567 }
568
569 m_neighborhood_infos = 0;
570 tsl_assert(empty());
571 }
572
573 static std::size_t max_size() noexcept {
574 if(StoreHash) {
575 return std::numeric_limits<typename bucket_hash::hash_type>::max();
576 }
577 else {
578 return std::numeric_limits<std::size_t>::max();
579 }
580 }
581
582private:
583 void set_empty(bool is_empty) noexcept {
584 if(is_empty) {
585 m_neighborhood_infos = neighborhood_bitmap(m_neighborhood_infos & ~1);
586 }
587 else {
588 m_neighborhood_infos = neighborhood_bitmap(m_neighborhood_infos | 1);
589 }
590 }
591
592 void destroy_value() noexcept {
593 try {
594 tsl_assert(!empty());
595
596 value().~value_type();
597 }
598 catch(...) {
599 std::terminate();
600 }
601 }
602
603private:
604 using storage = typename std::aligned_storage<sizeof(value_type), alignof(value_type)>::type;
605
606 neighborhood_bitmap m_neighborhood_infos;
607 storage m_value;
608};
609
610
611/**
612 * Internal common class used by hopscotch_(sc)_map and hopscotch_(sc)_set.
613 *
614 * ValueType is what will be stored by hopscotch_hash (usually std::pair<Key, T> for map and Key for set).
615 *
616 * KeySelect should be a FunctionObject which takes a ValueType in parameter and returns a reference to the key.
617 *
618 * ValueSelect should be a FunctionObject which takes a ValueType in parameter and returns a reference to the value.
619 * ValueSelect should be void if there is no value (in set for example).
620 *
621 * OverflowContainer will be used as containers for overflown elements. Usually it should be a list<ValueType>
622 * or a set<Key>/map<Key, T>.
623 */
624template<class ValueType,
625 class KeySelect,
626 class ValueSelect,
627 class Hash,
628 class KeyEqual,
629 class Allocator,
630 unsigned int NeighborhoodSize,
631 bool StoreHash,
632 class GrowthPolicy,
633 class OverflowContainer>
634class hopscotch_hash: private Hash, private KeyEqual, private GrowthPolicy {
635private:
636 template<typename U>
637 using has_mapped_type = typename std::integral_constant<bool, !std::is_same<U, void>::value>;
638
639public:
640 template<bool is_const>
641 class hopscotch_iterator;
642
643 using key_type = typename KeySelect::key_type;
644 using value_type = ValueType;
645 using size_type = std::size_t;
646 using difference_type = std::ptrdiff_t;
647 using hasher = Hash;
648 using key_equal = KeyEqual;
649 using allocator_type = Allocator;
650 using reference = value_type&;
651 using const_reference = const value_type&;
652 using pointer = value_type*;
653 using const_pointer = const value_type*;
654 using iterator = hopscotch_iterator<false>;
655 using const_iterator = hopscotch_iterator<true>;
656
657private:
658 using hopscotch_bucket = tsl::detail_hopscotch_hash::hopscotch_bucket<ValueType, NeighborhoodSize, StoreHash>;
659 using neighborhood_bitmap = typename hopscotch_bucket::neighborhood_bitmap;
660
661 using buckets_allocator = typename std::allocator_traits<allocator_type>::template rebind_alloc<hopscotch_bucket>;
662 using buckets_container_type = std::vector<hopscotch_bucket, buckets_allocator>;
663
664 using overflow_container_type = OverflowContainer;
665
666 static_assert(std::is_same<typename overflow_container_type::value_type, ValueType>::value,
667 "OverflowContainer should have ValueType as type.");
668
669 static_assert(std::is_same<typename overflow_container_type::allocator_type, Allocator>::value,
670 "Invalid allocator, not the same type as the value_type.");
671
672
673 using iterator_buckets = typename buckets_container_type::iterator;
674 using const_iterator_buckets = typename buckets_container_type::const_iterator;
675
676 using iterator_overflow = typename overflow_container_type::iterator;
677 using const_iterator_overflow = typename overflow_container_type::const_iterator;
678
679public:
680 /**
681 * The 'operator*()' and 'operator->()' methods return a const reference and const pointer respectively to the
682 * stored value type.
683 *
684 * In case of a map, to get a modifiable reference to the value associated to a key (the '.second' in the
685 * stored pair), you have to call 'value()'.
686 */
687 template<bool is_const>
688 class hopscotch_iterator {
689 friend class hopscotch_hash;
690 private:
691 using iterator_bucket = typename std::conditional<is_const,
692 typename hopscotch_hash::const_iterator_buckets,
693 typename hopscotch_hash::iterator_buckets>::type;
694 using iterator_overflow = typename std::conditional<is_const,
695 typename hopscotch_hash::const_iterator_overflow,
696 typename hopscotch_hash::iterator_overflow>::type;
697
698
699 hopscotch_iterator(iterator_bucket buckets_iterator, iterator_bucket buckets_end_iterator,
700 iterator_overflow overflow_iterator) noexcept :
701 m_buckets_iterator(buckets_iterator), m_buckets_end_iterator(buckets_end_iterator),
702 m_overflow_iterator(overflow_iterator)
703 {
704 }
705
706 public:
707 using iterator_category = std::forward_iterator_tag;
708 using value_type = const typename hopscotch_hash::value_type;
709 using difference_type = std::ptrdiff_t;
710 using reference = value_type&;
711 using pointer = value_type*;
712
713
714 hopscotch_iterator() noexcept {
715 }
716
717 hopscotch_iterator(const hopscotch_iterator<false>& other) noexcept :
718 m_buckets_iterator(other.m_buckets_iterator), m_buckets_end_iterator(other.m_buckets_end_iterator),
719 m_overflow_iterator(other.m_overflow_iterator)
720 {
721 }
722
723 const typename hopscotch_hash::key_type& key() const {
724 if(m_buckets_iterator != m_buckets_end_iterator) {
725 return KeySelect()(m_buckets_iterator->value());
726 }
727
728 return KeySelect()(*m_overflow_iterator);
729 }
730
731 template<class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
732 typename std::conditional<
733 is_const,
734 const typename U::value_type&,
735 typename U::value_type&>::type value() const
736 {
737 if(m_buckets_iterator != m_buckets_end_iterator) {
738 return U()(m_buckets_iterator->value());
739 }
740
741 return U()(*m_overflow_iterator);
742 }
743
744 reference operator*() const {
745 if(m_buckets_iterator != m_buckets_end_iterator) {
746 return m_buckets_iterator->value();
747 }
748
749 return *m_overflow_iterator;
750 }
751
752 pointer operator->() const {
753 if(m_buckets_iterator != m_buckets_end_iterator) {
754 return std::addressof(m_buckets_iterator->value());
755 }
756
757 return std::addressof(*m_overflow_iterator);
758 }
759
760 hopscotch_iterator& operator++() {
761 if(m_buckets_iterator == m_buckets_end_iterator) {
762 ++m_overflow_iterator;
763 return *this;
764 }
765
766 do {
767 ++m_buckets_iterator;
768 } while(m_buckets_iterator != m_buckets_end_iterator && m_buckets_iterator->empty());
769
770 return *this;
771 }
772
773 hopscotch_iterator operator++(int) {
774 hopscotch_iterator tmp(*this);
775 ++*this;
776
777 return tmp;
778 }
779
780 friend bool operator==(const hopscotch_iterator& lhs, const hopscotch_iterator& rhs) {
781 return lhs.m_buckets_iterator == rhs.m_buckets_iterator &&
782 lhs.m_overflow_iterator == rhs.m_overflow_iterator;
783 }
784
785 friend bool operator!=(const hopscotch_iterator& lhs, const hopscotch_iterator& rhs) {
786 return !(lhs == rhs);
787 }
788
789 private:
790 iterator_bucket m_buckets_iterator;
791 iterator_bucket m_buckets_end_iterator;
792 iterator_overflow m_overflow_iterator;
793 };
794
795
796
797public:
798 template<class OC = OverflowContainer, typename std::enable_if<!has_key_compare<OC>::value>::type* = nullptr>
799 hopscotch_hash(size_type bucket_count,
800 const Hash& hash,
801 const KeyEqual& equal,
802 const Allocator& alloc,
803 float max_load_factor) : Hash(hash),
804 KeyEqual(equal),
805 GrowthPolicy(bucket_count),
806 m_buckets(alloc),
807 m_overflow_elements(alloc),
808 m_nb_elements(0)
809 {
810 if(bucket_count > max_bucket_count()) {
811 throw std::length_error("The map exceeds its maxmimum size.");
812 }
813
814 static_assert(NeighborhoodSize - 1 > 0, "");
815 m_buckets.resize(bucket_count + NeighborhoodSize - 1);
816
817
818 this->max_load_factor(max_load_factor);
819 }
820
821 template<class OC = OverflowContainer, typename std::enable_if<has_key_compare<OC>::value>::type* = nullptr>
822 hopscotch_hash(size_type bucket_count,
823 const Hash& hash,
824 const KeyEqual& equal,
825 const Allocator& alloc,
826 float max_load_factor,
827 const typename OC::key_compare& comp) : Hash(hash),
828 KeyEqual(equal),
829 GrowthPolicy(bucket_count),
830 m_buckets(alloc),
831 m_overflow_elements(comp, alloc),
832 m_nb_elements(0)
833 {
834
835 if(bucket_count > max_bucket_count()) {
836 throw std::length_error("The map exceeds its maxmimum size.");
837 }
838
839 static_assert(NeighborhoodSize - 1 > 0, "");
840 m_buckets.resize(bucket_count + NeighborhoodSize - 1);
841
842
843 this->max_load_factor(max_load_factor);
844 }
845
846 hopscotch_hash(const hopscotch_hash& other) = default;
847
848 hopscotch_hash(hopscotch_hash&& other)
849 noexcept(
850 std::is_nothrow_move_constructible<Hash>::value &&
851 std::is_nothrow_move_constructible<KeyEqual>::value &&
852 std::is_nothrow_move_constructible<GrowthPolicy>::value &&
853 std::is_nothrow_move_constructible<buckets_container_type>::value &&
854 std::is_nothrow_move_constructible<overflow_container_type>::value
855 )
856 : Hash(std::move(static_cast<Hash&>(other))),
857 KeyEqual(std::move(static_cast<KeyEqual&>(other))),
858 GrowthPolicy(std::move(static_cast<GrowthPolicy&>(other))),
859 m_buckets(std::move(other.m_buckets)),
860 m_overflow_elements(std::move(other.m_overflow_elements)),
861 m_nb_elements(other.m_nb_elements),
862 m_max_load_factor(other.m_max_load_factor),
863 m_load_threshold(other.m_load_threshold),
864 m_min_load_factor_rehash_threshold(other.m_min_load_factor_rehash_threshold)
865 {
866 other.clear();
867 }
868
869 hopscotch_hash& operator=(const hopscotch_hash& other) = default;
870
871 hopscotch_hash& operator=(hopscotch_hash&& other) {
872 other.swap(*this);
873 other.clear();
874
875 return *this;
876 }
877
878 allocator_type get_allocator() const {
879 return m_buckets.get_allocator();
880 }
881
882
883 /*
884 * Iterators
885 */
886 iterator begin() noexcept {
887 auto begin = m_buckets.begin();
888 while(begin != m_buckets.end() && begin->empty()) {
889 ++begin;
890 }
891
892 return iterator(begin, m_buckets.end(), m_overflow_elements.begin());
893 }
894
895 const_iterator begin() const noexcept {
896 return cbegin();
897 }
898
899 const_iterator cbegin() const noexcept {
900 auto begin = m_buckets.cbegin();
901 while(begin != m_buckets.cend() && begin->empty()) {
902 ++begin;
903 }
904
905 return const_iterator(begin, m_buckets.cend(), m_overflow_elements.cbegin());
906 }
907
908 iterator end() noexcept {
909 return iterator(m_buckets.end(), m_buckets.end(), m_overflow_elements.end());
910 }
911
912 const_iterator end() const noexcept {
913 return cend();
914 }
915
916 const_iterator cend() const noexcept {
917 return const_iterator(m_buckets.cend(), m_buckets.cend(), m_overflow_elements.cend());
918 }
919
920
921 /*
922 * Capacity
923 */
924 bool empty() const noexcept {
925 return m_nb_elements == 0;
926 }
927
928 size_type size() const noexcept {
929 return m_nb_elements;
930 }
931
932 size_type max_size() const noexcept {
933 return hopscotch_bucket::max_size();
934 }
935
936 /*
937 * Modifiers
938 */
939 void clear() noexcept {
940 for(auto& bucket : m_buckets) {
941 bucket.clear();
942 }
943
944 m_overflow_elements.clear();
945 m_nb_elements = 0;
946 }
947
948
949 std::pair<iterator, bool> insert(const value_type& value) {
950 return insert_impl(value);
951 }
952
953 template<class P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type* = nullptr>
954 std::pair<iterator, bool> insert(P&& value) {
955 return emplace(std::forward<P>(value));
956 }
957
958 std::pair<iterator, bool> insert(value_type&& value) {
959 return insert_impl(std::move(value));
960 }
961
962
963 iterator insert(const_iterator hint, const value_type& value) {
964 if(hint != cend() && compare_keys(KeySelect()(*hint), KeySelect()(value))) {
965 return mutable_iterator(hint);
966 }
967
968 return insert(value).first;
969 }
970
971 template<class P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type* = nullptr>
972 iterator insert(const_iterator hint, P&& value) {
973 return emplace_hint(hint, std::forward<P>(value));
974 }
975
976 iterator insert(const_iterator hint, value_type&& value) {
977 if(hint != cend() && compare_keys(KeySelect()(*hint), KeySelect()(value))) {
978 return mutable_iterator(hint);
979 }
980
981 return insert(std::move(value)).first;
982 }
983
984
985 template<class InputIt>
986 void insert(InputIt first, InputIt last) {
987 if(std::is_base_of<std::forward_iterator_tag,
988 typename std::iterator_traits<InputIt>::iterator_category>::value)
989 {
990 const auto nb_elements_insert = std::distance(first, last);
991 const std::size_t nb_elements_in_buckets = m_nb_elements - m_overflow_elements.size();
992 const std::size_t nb_free_buckets = m_load_threshold - nb_elements_in_buckets;
993 tsl_assert(m_nb_elements >= m_overflow_elements.size());
994 tsl_assert(m_load_threshold >= nb_elements_in_buckets);
995
996 if(nb_elements_insert > 0 && nb_free_buckets < std::size_t(nb_elements_insert)) {
997 reserve(nb_elements_in_buckets + std::size_t(nb_elements_insert));
998 }
999 }
1000
1001 for(; first != last; ++first) {
1002 insert(*first);
1003 }
1004 }
1005
1006
1007 template<class M>
1008 std::pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj) {
1009 return insert_or_assign_impl(k, std::forward<M>(obj));
1010 }
1011
1012 template<class M>
1013 std::pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj) {
1014 return insert_or_assign_impl(std::move(k), std::forward<M>(obj));
1015 }
1016
1017
1018 template<class M>
1019 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj) {
1020 if(hint != cend() && compare_keys(KeySelect()(*hint), k)) {
1021 auto it = mutable_iterator(hint);
1022 it.value() = std::forward<M>(obj);
1023
1024 return it;
1025 }
1026
1027 return insert_or_assign(k, std::forward<M>(obj)).first;
1028 }
1029
1030 template<class M>
1031 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj) {
1032 if(hint != cend() && compare_keys(KeySelect()(*hint), k)) {
1033 auto it = mutable_iterator(hint);
1034 it.value() = std::forward<M>(obj);
1035
1036 return it;
1037 }
1038
1039 return insert_or_assign(std::move(k), std::forward<M>(obj)).first;
1040 }
1041
1042
1043 template<class... Args>
1044 std::pair<iterator, bool> emplace(Args&&... args) {
1045 return insert(value_type(std::forward<Args>(args)...));
1046 }
1047
1048 template<class... Args>
1049 iterator emplace_hint(const_iterator hint, Args&&... args) {
1050 return insert(hint, value_type(std::forward<Args>(args)...));
1051 }
1052
1053 template<class... Args>
1054 std::pair<iterator, bool> try_emplace(const key_type& k, Args&&... args) {
1055 return try_emplace_impl(k, std::forward<Args>(args)...);
1056 }
1057
1058 template<class... Args>
1059 std::pair<iterator, bool> try_emplace(key_type&& k, Args&&... args) {
1060 return try_emplace_impl(std::move(k), std::forward<Args>(args)...);
1061 }
1062
1063 template<class... Args>
1064 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args) {
1065 if(hint != cend() && compare_keys(KeySelect()(*hint), k)) {
1066 return mutable_iterator(hint);
1067 }
1068
1069 return try_emplace(k, std::forward<Args>(args)...).first;
1070 }
1071
1072 template<class... Args>
1073 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args) {
1074 if(hint != cend() && compare_keys(KeySelect()(*hint), k)) {
1075 return mutable_iterator(hint);
1076 }
1077
1078 return try_emplace(std::move(k), std::forward<Args>(args)...).first;
1079 }
1080
1081
1082
1083 iterator erase(iterator pos) {
1084 return erase(const_iterator(pos));
1085 }
1086
1087 iterator erase(const_iterator pos) {
1088 const std::size_t ibucket_for_hash = bucket_for_hash(hash_key(pos.key()));
1089
1090 if(pos.m_buckets_iterator != pos.m_buckets_end_iterator) {
1091 auto it_bucket = m_buckets.begin() + std::distance(m_buckets.cbegin(), pos.m_buckets_iterator);
1092 erase_from_bucket(it_bucket, ibucket_for_hash);
1093
1094 return ++iterator(it_bucket, m_buckets.end(), m_overflow_elements.begin());
1095 }
1096 else {
1097 auto it_next_overflow = erase_from_overflow(pos.m_overflow_iterator, ibucket_for_hash);
1098 return iterator(m_buckets.end(), m_buckets.end(), it_next_overflow);
1099 }
1100 }
1101
1102 iterator erase(const_iterator first, const_iterator last) {
1103 if(first == last) {
1104 return mutable_iterator(first);
1105 }
1106
1107 auto to_delete = erase(first);
1108 while(to_delete != last) {
1109 to_delete = erase(to_delete);
1110 }
1111
1112 return to_delete;
1113 }
1114
1115 template<class K>
1116 size_type erase(const K& key) {
1117 return erase(key, hash_key(key));
1118 }
1119
1120 template<class K>
1121 size_type erase(const K& key, std::size_t hash) {
1122 const std::size_t ibucket_for_hash = bucket_for_hash(hash);
1123
1124 auto it_find = find_in_buckets(key, hash, m_buckets.begin() + ibucket_for_hash);
1125 if(it_find != m_buckets.end()) {
1126 erase_from_bucket(it_find, ibucket_for_hash);
1127
1128 return 1;
1129 }
1130
1131 if(m_buckets[ibucket_for_hash].has_overflow()) {
1132 auto it_overflow = find_in_overflow(key);
1133 if(it_overflow != m_overflow_elements.end()) {
1134 erase_from_overflow(it_overflow, ibucket_for_hash);
1135
1136 return 1;
1137 }
1138 }
1139
1140 return 0;
1141 }
1142
1143 void swap(hopscotch_hash& other) {
1144 using std::swap;
1145
1146 swap(static_cast<Hash&>(*this), static_cast<Hash&>(other));
1147 swap(static_cast<KeyEqual&>(*this), static_cast<KeyEqual&>(other));
1148 swap(static_cast<GrowthPolicy&>(*this), static_cast<GrowthPolicy&>(other));
1149 swap(m_buckets, other.m_buckets);
1150 swap(m_overflow_elements, other.m_overflow_elements);
1151 swap(m_nb_elements, other.m_nb_elements);
1152 swap(m_max_load_factor, other.m_max_load_factor);
1153 swap(m_load_threshold, other.m_load_threshold);
1154 swap(m_min_load_factor_rehash_threshold, other.m_min_load_factor_rehash_threshold);
1155 }
1156
1157
1158 /*
1159 * Lookup
1160 */
1161 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1162 typename U::value_type& at(const K& key) {
1163 return at(key, hash_key(key));
1164 }
1165
1166 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1167 typename U::value_type& at(const K& key, std::size_t hash) {
1168 return const_cast<typename U::value_type&>(static_cast<const hopscotch_hash*>(this)->at(key, hash));
1169 }
1170
1171
1172 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1173 const typename U::value_type& at(const K& key) const {
1174 return at(key, hash_key(key));
1175 }
1176
1177 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1178 const typename U::value_type& at(const K& key, std::size_t hash) const {
1179 using T = typename U::value_type;
1180
1181 const T* value = find_value_impl(key, hash, m_buckets.begin() + bucket_for_hash(hash));
1182 if(value == nullptr) {
1183 throw std::out_of_range("Couldn't find key.");
1184 }
1185 else {
1186 return *value;
1187 }
1188 }
1189
1190
1191 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1192 typename U::value_type& operator[](K&& key) {
1193 using T = typename U::value_type;
1194
1195 const std::size_t hash = hash_key(key);
1196 const std::size_t ibucket_for_hash = bucket_for_hash(hash);
1197
1198 T* value = find_value_impl(key, hash, m_buckets.begin() + ibucket_for_hash);
1199 if(value != nullptr) {
1200 return *value;
1201 }
1202 else {
1203 return insert_impl(std::make_pair(std::forward<K>(key), T()), hash, ibucket_for_hash).first.value();
1204 }
1205 }
1206
1207
1208 template<class K>
1209 size_type count(const K& key) const {
1210 return count(key, hash_key(key));
1211 }
1212
1213 template<class K>
1214 size_type count(const K& key, std::size_t hash) const {
1215 return count_impl(key, hash, m_buckets.cbegin() + bucket_for_hash(hash));
1216 }
1217
1218
1219 template<class K>
1220 iterator find(const K& key) {
1221 return find(key, hash_key(key));
1222 }
1223
1224 template<class K>
1225 iterator find(const K& key, std::size_t hash) {
1226 return find_impl(key, hash, m_buckets.begin() + bucket_for_hash(hash));
1227 }
1228
1229
1230 template<class K>
1231 const_iterator find(const K& key) const {
1232 return find(key, hash_key(key));
1233 }
1234
1235 template<class K>
1236 const_iterator find(const K& key, std::size_t hash) const {
1237 return find_impl(key, hash, m_buckets.begin() + bucket_for_hash(hash));
1238 }
1239
1240
1241 template<class K>
1242 std::pair<iterator, iterator> equal_range(const K& key) {
1243 return equal_range(key, hash_key(key));
1244 }
1245
1246 template<class K>
1247 std::pair<iterator, iterator> equal_range(const K& key, std::size_t hash) {
1248 iterator it = find(key, hash);
1249 return std::make_pair(it, (it == end())?it:std::next(it));
1250 }
1251
1252
1253 template<class K>
1254 std::pair<const_iterator, const_iterator> equal_range(const K& key) const {
1255 return equal_range(key, hash_key(key));
1256 }
1257
1258 template<class K>
1259 std::pair<const_iterator, const_iterator> equal_range(const K& key, std::size_t hash) const {
1260 const_iterator it = find(key, hash);
1261 return std::make_pair(it, (it == cend())?it:std::next(it));
1262 }
1263
1264 /*
1265 * Bucket interface
1266 */
1267 size_type bucket_count() const {
1268 /*
1269 * So that the last bucket can have NeighborhoodSize neighbors, the size of the bucket array is a little
1270 * bigger than the real number of buckets. We could use some of the buckets at the beginning, but
1271 * it is easier this way and we avoid weird behaviour with iterators.
1272 */
1273 return m_buckets.size() - NeighborhoodSize + 1;
1274 }
1275
1276 size_type max_bucket_count() const {
1277 const std::size_t max_bucket_count = std::min(GrowthPolicy::max_bucket_count(), m_buckets.max_size());
1278 return max_bucket_count - NeighborhoodSize + 1;
1279 }
1280
1281
1282 /*
1283 * Hash policy
1284 */
1285 float load_factor() const {
1286 return float(m_nb_elements)/float(bucket_count());
1287 }
1288
1289 float max_load_factor() const {
1290 return m_max_load_factor;
1291 }
1292
1293 void max_load_factor(float ml) {
1294 m_max_load_factor = ml;
1295 m_load_threshold = size_type(float(bucket_count())*m_max_load_factor);
1296 m_min_load_factor_rehash_threshold = size_type(bucket_count()*MIN_LOAD_FACTOR_FOR_REHASH);
1297 }
1298
1299 void rehash(size_type count) {
1300 count = std::max(count, size_type(std::ceil(float(size())/max_load_factor())));
1301 rehash_impl(count);
1302 }
1303
1304 void reserve(size_type count) {
1305 rehash(size_type(std::ceil(float(count)/max_load_factor())));
1306 }
1307
1308
1309 /*
1310 * Observers
1311 */
1312 hasher hash_function() const {
1313 return static_cast<Hash>(*this);
1314 }
1315
1316 key_equal key_eq() const {
1317 return static_cast<KeyEqual>(*this);
1318 }
1319
1320 /*
1321 * Other
1322 */
1323 size_type overflow_size() const noexcept {
1324 return m_overflow_elements.size();
1325 }
1326
1327 template<class U = OverflowContainer, typename std::enable_if<has_key_compare<U>::value>::type* = nullptr>
1328 typename U::key_compare key_comp() const {
1329 return m_overflow_elements.key_comp();
1330 }
1331
1332private:
1333 template<class K>
1334 std::size_t hash_key(const K& key) const {
1335 return Hash::operator()(key);
1336 }
1337
1338 template<class K1, class K2>
1339 bool compare_keys(const K1& key1, const K2& key2) const {
1340 return KeyEqual::operator()(key1, key2);
1341 }
1342
1343 std::size_t bucket_for_hash(std::size_t hash) const {
1344 return GrowthPolicy::bucket_for_hash(hash);
1345 }
1346
1347 iterator mutable_iterator(const_iterator pos) {
1348 if(pos.m_buckets_iterator != pos.m_buckets_end_iterator) {
1349 // Get a non-const iterator
1350 auto it = m_buckets.begin() + std::distance(m_buckets.cbegin(), pos.m_buckets_iterator);
1351 return iterator(it, m_buckets.end(), m_overflow_elements.begin());
1352 }
1353 else {
1354 // Get a non-const iterator
1355 auto it = mutable_overflow_iterator(pos.m_overflow_iterator);
1356
1357 return iterator(m_buckets.end(), m_buckets.end(), it);
1358 }
1359 }
1360
1361
1362 static_assert(std::is_nothrow_move_constructible<value_type>::value ||
1363 std::is_copy_constructible<value_type>::value,
1364 "value_type must be either copy constructible or nothrow move constructible.");
1365
1366 template<typename U = value_type,
1367 typename std::enable_if<std::is_nothrow_move_constructible<U>::value>::type* = nullptr>
1368 void rehash_impl(size_type count) {
1369 hopscotch_hash new_map = new_hopscotch_hash(count);
1370
1371 if(!m_overflow_elements.empty()) {
1372 new_map.m_overflow_elements.swap(m_overflow_elements);
1373 new_map.m_nb_elements += new_map.m_overflow_elements.size();
1374
1375 for(const value_type& value : new_map.m_overflow_elements) {
1376 const std::size_t ibucket_for_hash = new_map.bucket_for_hash(new_map.hash_key(KeySelect()(value)));
1377 new_map.m_buckets[ibucket_for_hash].set_overflow(true);
1378 }
1379 }
1380
1381 try {
1382 for(auto it_bucket = m_buckets.begin(); it_bucket != m_buckets.end(); ++it_bucket) {
1383 if(it_bucket->empty()) {
1384 continue;
1385 }
1386
1387 const std::size_t hash = USE_STORED_HASH_ON_REHASH?
1388 it_bucket->truncated_bucket_hash():
1389 new_map.hash_key(KeySelect()(it_bucket->value()));
1390 const std::size_t ibucket_for_hash = new_map.bucket_for_hash(hash);
1391
1392 new_map.insert_impl(std::move(it_bucket->value()), hash, ibucket_for_hash);
1393
1394
1395 erase_from_bucket(it_bucket, bucket_for_hash(hash));
1396 }
1397 }
1398 /*
1399 * The call to insert_impl may throw an exception if an element is added to the overflow
1400 * list. Rollback the elements in this case.
1401 */
1402 catch(...) {
1403 m_overflow_elements.swap(new_map.m_overflow_elements);
1404
1405 for(auto it_bucket = new_map.m_buckets.begin(); it_bucket != new_map.m_buckets.end(); ++it_bucket) {
1406 if(it_bucket->empty()) {
1407 continue;
1408 }
1409
1410 const std::size_t hash = USE_STORED_HASH_ON_REHASH?
1411 it_bucket->truncated_bucket_hash():
1412 hash_key(KeySelect()(it_bucket->value()));
1413 const std::size_t ibucket_for_hash = bucket_for_hash(hash);
1414
1415 // The elements we insert were not in the overflow list before the switch.
1416 // They will not be go in the overflow list if we rollback the switch.
1417 insert_impl(std::move(it_bucket->value()), hash, ibucket_for_hash);
1418 }
1419
1420 throw;
1421 }
1422
1423 new_map.swap(*this);
1424 }
1425
1426 template<typename U = value_type,
1427 typename std::enable_if<std::is_copy_constructible<U>::value &&
1428 !std::is_nothrow_move_constructible<U>::value>::type* = nullptr>
1429 void rehash_impl(size_type count) {
1430 hopscotch_hash new_map = new_hopscotch_hash(count);
1431
1432 for(const hopscotch_bucket& bucket: m_buckets) {
1433 if(bucket.empty()) {
1434 continue;
1435 }
1436
1437 const std::size_t hash = USE_STORED_HASH_ON_REHASH?
1438 bucket.truncated_bucket_hash():
1439 new_map.hash_key(KeySelect()(bucket.value()));
1440 const std::size_t ibucket_for_hash = new_map.bucket_for_hash(hash);
1441
1442 new_map.insert_impl(bucket.value(), hash, ibucket_for_hash);
1443 }
1444
1445 for(const value_type& value: m_overflow_elements) {
1446 const std::size_t hash = new_map.hash_key(KeySelect()(value));
1447 const std::size_t ibucket_for_hash = new_map.bucket_for_hash(hash);
1448
1449 new_map.insert_impl(value, hash, ibucket_for_hash);
1450 }
1451
1452 new_map.swap(*this);
1453 }
1454
1455#ifdef TSL_NO_RANGE_ERASE_WITH_CONST_ITERATOR
1456 iterator_overflow mutable_overflow_iterator(const_iterator_overflow it) {
1457 return std::next(m_overflow_elements.begin(), std::distance(m_overflow_elements.cbegin(), it));
1458 }
1459#else
1460 iterator_overflow mutable_overflow_iterator(const_iterator_overflow it) {
1461 return m_overflow_elements.erase(it, it);
1462 }
1463#endif
1464
1465 // iterator is in overflow list
1466 iterator_overflow erase_from_overflow(const_iterator_overflow pos, std::size_t ibucket_for_hash) {
1467#ifdef TSL_NO_RANGE_ERASE_WITH_CONST_ITERATOR
1468 auto it_next = m_overflow_elements.erase(mutable_overflow_iterator(pos));
1469#else
1470 auto it_next = m_overflow_elements.erase(pos);
1471#endif
1472 m_nb_elements--;
1473
1474
1475 // Check if we can remove the overflow flag
1476 tsl_assert(m_buckets[ibucket_for_hash].has_overflow());
1477 for(const value_type& value: m_overflow_elements) {
1478 const std::size_t bucket_for_value = bucket_for_hash(hash_key(KeySelect()(value)));
1479 if(bucket_for_value == ibucket_for_hash) {
1480 return it_next;
1481 }
1482 }
1483
1484 m_buckets[ibucket_for_hash].set_overflow(false);
1485 return it_next;
1486 }
1487
1488 // iterator is in bucket
1489 void erase_from_bucket(iterator_buckets pos, std::size_t ibucket_for_hash) noexcept {
1490 const std::size_t ibucket_for_pos = std::distance(m_buckets.begin(), pos);
1491 tsl_assert(ibucket_for_pos >= ibucket_for_hash);
1492
1493 m_buckets[ibucket_for_pos].remove_value();
1494 m_buckets[ibucket_for_hash].toggle_neighbor_presence(ibucket_for_pos - ibucket_for_hash);
1495 m_nb_elements--;
1496 }
1497
1498
1499
1500 template<class K, class M>
1501 std::pair<iterator, bool> insert_or_assign_impl(K&& key, M&& obj) {
1502 const std::size_t hash = hash_key(key);
1503 const std::size_t ibucket_for_hash = bucket_for_hash(hash);
1504
1505 // Check if already presents
1506 auto it_find = find_impl(key, hash, m_buckets.begin() + ibucket_for_hash);
1507 if(it_find != end()) {
1508 it_find.value() = std::forward<M>(obj);
1509 return std::make_pair(it_find, false);
1510 }
1511
1512
1513 return insert_impl(value_type(std::forward<K>(key), std::forward<M>(obj)), hash, ibucket_for_hash);
1514 }
1515
1516 template<typename P, class... Args>
1517 std::pair<iterator, bool> try_emplace_impl(P&& key, Args&&... args_value) {
1518 const std::size_t hash = hash_key(key);
1519 const std::size_t ibucket_for_hash = bucket_for_hash(hash);
1520
1521 // Check if already presents
1522 auto it_find = find_impl(key, hash, m_buckets.begin() + ibucket_for_hash);
1523 if(it_find != end()) {
1524 return std::make_pair(it_find, false);
1525 }
1526
1527
1528 return insert_impl(value_type(std::piecewise_construct,
1529 std::forward_as_tuple(std::forward<P>(key)),
1530 std::forward_as_tuple(std::forward<Args>(args_value)...)),
1531 hash, ibucket_for_hash);
1532 }
1533
1534 template<typename P>
1535 std::pair<iterator, bool> insert_impl(P&& value) {
1536 const std::size_t hash = hash_key(KeySelect()(value));
1537 const std::size_t ibucket_for_hash = bucket_for_hash(hash);
1538
1539 // Check if already presents
1540 auto it_find = find_impl(KeySelect()(value), hash, m_buckets.begin() + ibucket_for_hash);
1541 if(it_find != end()) {
1542 return std::make_pair(it_find, false);
1543 }
1544
1545
1546 return insert_impl(std::forward<P>(value), hash, ibucket_for_hash);
1547 }
1548
1549 template<typename P>
1550 std::pair<iterator, bool> insert_impl(P&& value, std::size_t hash, std::size_t ibucket_for_hash) {
1551 if((m_nb_elements - m_overflow_elements.size()) >= m_load_threshold) {
1552 rehash(GrowthPolicy::next_bucket_count());
1553 ibucket_for_hash = bucket_for_hash(hash);
1554 }
1555
1556 std::size_t ibucket_empty = find_empty_bucket(ibucket_for_hash);
1557 if(ibucket_empty < m_buckets.size()) {
1558 do {
1559 tsl_assert(ibucket_empty >= ibucket_for_hash);
1560
1561 // Empty bucket is in range of NeighborhoodSize, use it
1562 if(ibucket_empty - ibucket_for_hash < NeighborhoodSize) {
1563 auto it = insert_in_bucket(std::forward<P>(value), hash, ibucket_empty, ibucket_for_hash);
1564 return std::make_pair(iterator(it, m_buckets.end(), m_overflow_elements.begin()), true);
1565 }
1566 }
1567 // else, try to swap values to get a closer empty bucket
1568 while(swap_empty_bucket_closer(ibucket_empty));
1569 }
1570
1571 // Load factor is too low or a rehash will not change the neighborhood, put the value in overflow list
1572 if(size() < m_min_load_factor_rehash_threshold || !will_neighborhood_change_on_rehash(ibucket_for_hash)) {
1573 auto it_insert = m_overflow_elements.insert(m_overflow_elements.end(), std::forward<P>(value));
1574 m_buckets[ibucket_for_hash].set_overflow(true);
1575 m_nb_elements++;
1576
1577 return std::make_pair(iterator(m_buckets.end(), m_buckets.end(), it_insert), true);
1578 }
1579
1580 rehash(GrowthPolicy::next_bucket_count());
1581
1582 ibucket_for_hash = bucket_for_hash(hash);
1583 return insert_impl(std::forward<P>(value), hash, ibucket_for_hash);
1584 }
1585
1586 /*
1587 * Return true if a rehash will change the position of a key-value in the neighborhood of
1588 * ibucket_neighborhood_check. In this case a rehash is needed instead of puting the value in overflow list.
1589 */
1590 bool will_neighborhood_change_on_rehash(size_t ibucket_neighborhood_check) const {
1591 std::size_t expand_bucket_count = GrowthPolicy::next_bucket_count();
1592 GrowthPolicy expand_growth_policy(expand_bucket_count);
1593
1594 for(size_t ibucket = ibucket_neighborhood_check;
1595 ibucket < m_buckets.size() && (ibucket - ibucket_neighborhood_check) < NeighborhoodSize;
1596 ++ibucket)
1597 {
1598 tsl_assert(!m_buckets[ibucket].empty());
1599
1600 const size_t hash = USE_STORED_HASH_ON_REHASH?
1601 m_buckets[ibucket].truncated_bucket_hash():
1602 hash_key(KeySelect()(m_buckets[ibucket].value()));
1603 if(bucket_for_hash(hash) != expand_growth_policy.bucket_for_hash(hash)) {
1604 return true;
1605 }
1606 }
1607
1608 return false;
1609 }
1610
1611 /*
1612 * Return the index of an empty bucket in m_buckets.
1613 * If none, the returned index equals m_buckets.size()
1614 */
1615 std::size_t find_empty_bucket(std::size_t ibucket_start) const {
1616 const std::size_t limit = std::min(ibucket_start + MAX_PROBES_FOR_EMPTY_BUCKET, m_buckets.size());
1617 for(; ibucket_start < limit; ibucket_start++) {
1618 if(m_buckets[ibucket_start].empty()) {
1619 return ibucket_start;
1620 }
1621 }
1622
1623 return m_buckets.size();
1624 }
1625
1626 /*
1627 * Insert value in ibucket_empty where value originally belongs to ibucket_for_hash
1628 *
1629 * Return bucket iterator to ibucket_empty
1630 */
1631 template<typename P>
1632 iterator_buckets insert_in_bucket(P&& value, std::size_t hash,
1633 std::size_t ibucket_empty, std::size_t ibucket_for_hash)
1634 {
1635 tsl_assert(ibucket_empty >= ibucket_for_hash );
1636 tsl_assert(m_buckets[ibucket_empty].empty());
1637 m_buckets[ibucket_empty].set_value_of_empty_bucket(std::forward<P>(value), hash);
1638
1639 tsl_assert(!m_buckets[ibucket_for_hash].empty());
1640 m_buckets[ibucket_for_hash].toggle_neighbor_presence(ibucket_empty - ibucket_for_hash);
1641 m_nb_elements++;
1642
1643 return m_buckets.begin() + ibucket_empty;
1644 }
1645
1646 /*
1647 * Try to swap the bucket ibucket_empty_in_out with a bucket preceding it while keeping the neighborhood
1648 * conditions correct.
1649 *
1650 * If a swap was possible, the position of ibucket_empty_in_out will be closer to 0 and true will re returned.
1651 */
1652 bool swap_empty_bucket_closer(std::size_t& ibucket_empty_in_out) {
1653 tsl_assert(ibucket_empty_in_out >= NeighborhoodSize);
1654 const std::size_t neighborhood_start = ibucket_empty_in_out - NeighborhoodSize + 1;
1655
1656 for(std::size_t to_check = neighborhood_start; to_check < ibucket_empty_in_out; to_check++) {
1657 neighborhood_bitmap neighborhood_infos = m_buckets[to_check].neighborhood_infos();
1658 std::size_t to_swap = to_check;
1659
1660 while(neighborhood_infos != 0 && to_swap < ibucket_empty_in_out) {
1661 if((neighborhood_infos & 1) == 1) {
1662 tsl_assert(m_buckets[ibucket_empty_in_out].empty());
1663 tsl_assert(!m_buckets[to_swap].empty());
1664
1665 m_buckets[to_swap].swap_value_into_empty_bucket(m_buckets[ibucket_empty_in_out]);
1666
1667 tsl_assert(!m_buckets[to_check].check_neighbor_presence(ibucket_empty_in_out - to_check));
1668 tsl_assert(m_buckets[to_check].check_neighbor_presence(to_swap - to_check));
1669
1670 m_buckets[to_check].toggle_neighbor_presence(ibucket_empty_in_out - to_check);
1671 m_buckets[to_check].toggle_neighbor_presence(to_swap - to_check);
1672
1673
1674 ibucket_empty_in_out = to_swap;
1675
1676 return true;
1677 }
1678
1679 to_swap++;
1680 neighborhood_infos = neighborhood_bitmap(neighborhood_infos >> 1);
1681 }
1682 }
1683
1684 return false;
1685 }
1686
1687
1688
1689 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1690 typename U::value_type* find_value_impl(const K& key, std::size_t hash, iterator_buckets it_bucket) {
1691 return const_cast<typename U::value_type*>(
1692 static_cast<const hopscotch_hash*>(this)->find_value_impl(key, hash, it_bucket));
1693 }
1694
1695 /*
1696 * Avoid the creation of an iterator to just get the value for operator[] and at() in maps. Faster this way.
1697 *
1698 * Return null if no value for key (TODO use std::optional when available).
1699 */
1700 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1701 const typename U::value_type* find_value_impl(const K& key, std::size_t hash,
1702 const_iterator_buckets it_bucket) const
1703 {
1704 auto it_find = find_in_buckets(key, hash, it_bucket);
1705 if(it_find != m_buckets.cend()) {
1706 return std::addressof(ValueSelect()(it_find->value()));
1707 }
1708
1709 if(it_bucket->has_overflow()) {
1710 auto it_overflow = find_in_overflow(key);
1711 if(it_overflow != m_overflow_elements.end()) {
1712 return std::addressof(ValueSelect()(*it_overflow));
1713 }
1714 }
1715
1716 return nullptr;
1717 }
1718
1719 template<class K>
1720 size_type count_impl(const K& key, std::size_t hash, const_iterator_buckets it_bucket) const {
1721 if(find_in_buckets(key, hash, it_bucket) != m_buckets.cend()) {
1722 return 1;
1723 }
1724 else if(it_bucket->has_overflow() && find_in_overflow(key) != m_overflow_elements.cend()) {
1725 return 1;
1726 }
1727 else {
1728 return 0;
1729 }
1730 }
1731
1732 template<class K>
1733 iterator find_impl(const K& key, std::size_t hash, iterator_buckets it_bucket) {
1734 auto it = find_in_buckets(key, hash, it_bucket);
1735 if(it != m_buckets.end()) {
1736 return iterator(it, m_buckets.end(), m_overflow_elements.begin());
1737 }
1738
1739 if(!it_bucket->has_overflow()) {
1740 return end();
1741 }
1742
1743 return iterator(m_buckets.end(), m_buckets.end(), find_in_overflow(key));
1744 }
1745
1746 template<class K>
1747 const_iterator find_impl(const K& key, std::size_t hash, const_iterator_buckets it_bucket) const {
1748 auto it = find_in_buckets(key, hash, it_bucket);
1749 if(it != m_buckets.cend()) {
1750 return const_iterator(it, m_buckets.cend(), m_overflow_elements.cbegin());
1751 }
1752
1753 if(!it_bucket->has_overflow()) {
1754 return cend();
1755 }
1756
1757
1758 return const_iterator(m_buckets.cend(), m_buckets.cend(), find_in_overflow(key));
1759 }
1760
1761 template<class K>
1762 iterator_buckets find_in_buckets(const K& key, std::size_t hash, iterator_buckets it_bucket) {
1763 auto it_find = static_cast<const hopscotch_hash*>(this)->find_in_buckets(key, hash, it_bucket);
1764 return m_buckets.begin() + std::distance(m_buckets.cbegin(), it_find);
1765 }
1766
1767
1768 template<class K>
1769 const_iterator_buckets find_in_buckets(const K& key, std::size_t hash, const_iterator_buckets it_bucket) const {
1770 (void) hash; // Avoid warning of unused variable when StoreHash is false;
1771
1772 // TODO Try to optimize the function.
1773 // I tried to use ffs and __builtin_ffs functions but I could not reduce the time the function
1774 // takes with -march=native
1775
1776 neighborhood_bitmap neighborhood_infos = it_bucket->neighborhood_infos();
1777 while(neighborhood_infos != 0) {
1778 if((neighborhood_infos & 1) == 1) {
1779 // Check StoreHash before calling bucket_hash_equal. Functionally it doesn't change anythin.
1780 // If StoreHash is false, bucket_hash_equal is a no-op. Avoiding the call is there to help
1781 // GCC optimizes `hash` parameter away, it seems to not be able to do without this hint.
1782 if((!StoreHash || it_bucket->bucket_hash_equal(hash)) &&
1783 compare_keys(KeySelect()(it_bucket->value()), key))
1784 {
1785 return it_bucket;
1786 }
1787 }
1788
1789 ++it_bucket;
1790 neighborhood_infos = neighborhood_bitmap(neighborhood_infos >> 1);
1791 }
1792
1793 return m_buckets.end();
1794 }
1795
1796
1797 // TODO Use a better way to check if we should use
1798 // std::find_if(m_overflow_elements.begin(), m_overflow_elements.end(), ...) or
1799 // m_overflow_elements.find(...)
1800 template<class K, class U = OverflowContainer, typename std::enable_if<!has_key_compare<U>::value>::type* = nullptr>
1801 iterator_overflow find_in_overflow(const K& key) {
1802 return std::find_if(m_overflow_elements.begin(), m_overflow_elements.end(),
1803 [&](const value_type& value) {
1804 return compare_keys(key, KeySelect()(value));
1805 });
1806 }
1807
1808 template<class K, class U = OverflowContainer, typename std::enable_if<!has_key_compare<U>::value>::type* = nullptr>
1809 const_iterator_overflow find_in_overflow(const K& key) const {
1810 return std::find_if(m_overflow_elements.cbegin(), m_overflow_elements.cend(),
1811 [&](const value_type& value) {
1812 return compare_keys(key, KeySelect()(value));
1813 });
1814 }
1815
1816 template<class K, class U = OverflowContainer, typename std::enable_if<has_key_compare<U>::value>::type* = nullptr>
1817 iterator_overflow find_in_overflow(const K& key) {
1818 return m_overflow_elements.find(key);
1819 }
1820
1821 template<class K, class U = OverflowContainer, typename std::enable_if<has_key_compare<U>::value>::type* = nullptr>
1822 const_iterator_overflow find_in_overflow(const K& key) const {
1823 return m_overflow_elements.find(key);
1824 }
1825
1826 template<class U = OverflowContainer, typename std::enable_if<!has_key_compare<U>::value>::type* = nullptr>
1827 hopscotch_hash new_hopscotch_hash(size_type bucket_count) {
1828 return hopscotch_hash(bucket_count, static_cast<Hash&>(*this), static_cast<KeyEqual&>(*this),
1829 get_allocator(), m_max_load_factor);
1830 }
1831
1832 template<class U = OverflowContainer, typename std::enable_if<has_key_compare<U>::value>::type* = nullptr>
1833 hopscotch_hash new_hopscotch_hash(size_type bucket_count) {
1834 return hopscotch_hash(bucket_count, static_cast<Hash&>(*this), static_cast<KeyEqual&>(*this),
1835 get_allocator(), m_max_load_factor, m_overflow_elements.key_comp());
1836 }
1837
1838public:
1839 static const size_type DEFAULT_INIT_BUCKETS_SIZE = 16;
1840 static constexpr float DEFAULT_MAX_LOAD_FACTOR = 0.9f;
1841
1842private:
1843 static const std::size_t MAX_PROBES_FOR_EMPTY_BUCKET = 12*NeighborhoodSize;
1844 static constexpr float MIN_LOAD_FACTOR_FOR_REHASH = 0.1f;
1845
1846 static const bool USE_STORED_HASH_ON_REHASH =
1847 StoreHash && std::is_same<GrowthPolicy, tsl::power_of_two_growth_policy>::value;
1848
1849private:
1850 buckets_container_type m_buckets;
1851 overflow_container_type m_overflow_elements;
1852
1853 size_type m_nb_elements;
1854
1855 float m_max_load_factor;
1856 size_type m_load_threshold;
1857 size_type m_min_load_factor_rehash_threshold;
1858};
1859
1860} // end namespace detail_hopscotch_hash
1861
1862
1863} // end namespace tsl
1864
1865#endif
1866