IOSS 2.0

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