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 store 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 hash) const noexcept
182 {
183 return m_hash == truncated_hash_type(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 hash) noexcept { m_hash = 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 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(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 std::size_t max_size() noexcept
372 {
373 if (StoreHash) {
374 return std::numeric_limits<typename bucket_hash::hash_type>::max();
375 }
376 else {
377 return std::numeric_limits<std::size_t>::max();
378 }
379 }
380
381 static truncated_hash_type truncate_hash(std::size_t hash) noexcept
382 {
383 return truncated_hash_type(hash);
384 }
385
386 private:
387 void set_empty(bool is_empty) noexcept
388 {
389 if (is_empty) {
390 m_neighborhood_infos = neighborhood_bitmap(m_neighborhood_infos & ~1);
391 }
392 else {
393 m_neighborhood_infos = neighborhood_bitmap(m_neighborhood_infos | 1);
394 }
395 }
396
397 void destroy_value() noexcept
398 {
399 tsl_hh_assert(!empty());
400 value().~value_type();
401 }
402
403 private:
404 using storage = typename std::aligned_storage<sizeof(value_type), alignof(value_type)>::type;
405
406 neighborhood_bitmap m_neighborhood_infos;
407 storage m_value;
408 };
409
410 /**
411 * Internal common class used by (b)hopscotch_map and (b)hopscotch_set.
412 *
413 * ValueType is what will be stored by hopscotch_hash (usually std::pair<Key, T> for a map and
414 * Key for a set).
415 *
416 * KeySelect should be a FunctionObject which takes a ValueType in parameter and returns a
417 * reference to the key.
418 *
419 * ValueSelect should be a FunctionObject which takes a ValueType in parameter and returns a
420 * reference to the value. ValueSelect should be void if there is no value (in a set for
421 * example).
422 *
423 * OverflowContainer will be used as containers for overflown elements. Usually it should be a
424 * list<ValueType> or a set<Key>/map<Key, T>.
425 */
426 template <class ValueType, class KeySelect, class ValueSelect, class Hash, class KeyEqual,
427 class Allocator, unsigned int NeighborhoodSize, bool StoreHash, class GrowthPolicy,
428 class OverflowContainer>
429 class hopscotch_hash : private Hash, private KeyEqual, private GrowthPolicy
430 {
431 private:
432 template <typename U>
433 using has_mapped_type = typename std::integral_constant<bool, !std::is_same<U, void>::value>;
434
435 static_assert(noexcept(std::declval<GrowthPolicy>().bucket_for_hash(std::size_t(0))),
436 "GrowthPolicy::bucket_for_hash must be noexcept.");
437 static_assert(noexcept(std::declval<GrowthPolicy>().clear()),
438 "GrowthPolicy::clear must be noexcept.");
439
440 public:
441 template <bool IsConst> class hopscotch_iterator;
442
443 using key_type = typename KeySelect::key_type;
444 using value_type = ValueType;
445 using size_type = std::size_t;
446 using difference_type = std::ptrdiff_t;
447 using hasher = Hash;
448 using key_equal = KeyEqual;
449 using allocator_type = Allocator;
450 using reference = value_type &;
451 using const_reference = const value_type &;
452 using pointer = value_type *;
453 using const_pointer = const value_type *;
454 using iterator = hopscotch_iterator<false>;
455 using const_iterator = hopscotch_iterator<true>;
456
457 private:
458 using hopscotch_bucket =
459 tsl::detail_hopscotch_hash::hopscotch_bucket<ValueType, NeighborhoodSize, StoreHash>;
460 using neighborhood_bitmap = typename hopscotch_bucket::neighborhood_bitmap;
461
462 using buckets_allocator =
463 typename std::allocator_traits<allocator_type>::template rebind_alloc<hopscotch_bucket>;
464 using buckets_container_type = std::vector<hopscotch_bucket, buckets_allocator>;
465
466 using overflow_container_type = OverflowContainer;
467
468 static_assert(std::is_same<typename overflow_container_type::value_type, ValueType>::value,
469 "OverflowContainer should have ValueType as type.");
470
471 static_assert(
472 std::is_same<typename overflow_container_type::allocator_type, Allocator>::value,
473 "Invalid allocator, not the same type as the value_type.");
474
475 using iterator_buckets = typename buckets_container_type::iterator;
476 using const_iterator_buckets = typename buckets_container_type::const_iterator;
477
478 using iterator_overflow = typename overflow_container_type::iterator;
479 using const_iterator_overflow = typename overflow_container_type::const_iterator;
480
481 public:
482 /**
483 * The `operator*()` and `operator->()` methods return a const reference and const pointer
484 * respectively to the stored value type.
485 *
486 * In case of a map, to get a modifiable reference to the value associated to a key (the
487 * `.second` in the stored pair), you have to call `value()`.
488 */
489 template <bool IsConst> class hopscotch_iterator
490 {
491 friend class hopscotch_hash;
492
493 private:
494 using iterator_bucket =
495 typename std::conditional<IsConst, typename hopscotch_hash::const_iterator_buckets,
496 typename hopscotch_hash::iterator_buckets>::type;
497 using iterator_overflow =
498 typename std::conditional<IsConst, typename hopscotch_hash::const_iterator_overflow,
499 typename hopscotch_hash::iterator_overflow>::type;
500
501 hopscotch_iterator(iterator_bucket buckets_iterator, iterator_bucket buckets_end_iterator,
502 iterator_overflow overflow_iterator) noexcept
503 : m_buckets_iterator(buckets_iterator), m_buckets_end_iterator(buckets_end_iterator),
504 m_overflow_iterator(overflow_iterator)
505 {
506 }
507
508 public:
509 using iterator_category = std::forward_iterator_tag;
510 using value_type = const typename hopscotch_hash::value_type;
511 using difference_type = std::ptrdiff_t;
512 using reference = value_type &;
513 using pointer = value_type *;
514
515 hopscotch_iterator() noexcept {}
516
517 hopscotch_iterator(const hopscotch_iterator<false> &other) noexcept
518 : m_buckets_iterator(other.m_buckets_iterator),
519 m_buckets_end_iterator(other.m_buckets_end_iterator),
520 m_overflow_iterator(other.m_overflow_iterator)
521 {
522 }
523
524 const typename hopscotch_hash::key_type &key() const
525 {
526 if (m_buckets_iterator != m_buckets_end_iterator) {
527 return KeySelect()(m_buckets_iterator->value());
528 }
529
530 return KeySelect()(*m_overflow_iterator);
531 }
532
533 template <class U = ValueSelect,
534 typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
535 typename std::conditional<IsConst, const typename U::value_type &,
536 typename U::value_type &>::type
537 value() const
538 {
539 if (m_buckets_iterator != m_buckets_end_iterator) {
540 return U()(m_buckets_iterator->value());
541 }
542
543 return U()(*m_overflow_iterator);
544 }
545
546 reference operator*() const
547 {
548 if (m_buckets_iterator != m_buckets_end_iterator) {
549 return m_buckets_iterator->value();
550 }
551
552 return *m_overflow_iterator;
553 }
554
555 pointer operator->() const
556 {
557 if (m_buckets_iterator != m_buckets_end_iterator) {
558 return std::addressof(m_buckets_iterator->value());
559 }
560
561 return std::addressof(*m_overflow_iterator);
562 }
563
564 hopscotch_iterator &operator++()
565 {
566 if (m_buckets_iterator == m_buckets_end_iterator) {
567 ++m_overflow_iterator;
568 return *this;
569 }
570
571 do {
572 ++m_buckets_iterator;
573 } while (m_buckets_iterator != m_buckets_end_iterator && m_buckets_iterator->empty());
574
575 return *this;
576 }
577
578 hopscotch_iterator operator++(int)
579 {
580 hopscotch_iterator tmp(*this);
581 ++*this;
582
583 return tmp;
584 }
585
586 friend bool operator==(const hopscotch_iterator &lhs, const hopscotch_iterator &rhs)
587 {
588 return lhs.m_buckets_iterator == rhs.m_buckets_iterator &&
589 lhs.m_overflow_iterator == rhs.m_overflow_iterator;
590 }
591
592 friend bool operator!=(const hopscotch_iterator &lhs, const hopscotch_iterator &rhs)
593 {
594 return !(lhs == rhs);
595 }
596
597 private:
598 iterator_bucket m_buckets_iterator;
599 iterator_bucket m_buckets_end_iterator;
600 iterator_overflow m_overflow_iterator;
601 };
602
603 public:
604 template <class OC = OverflowContainer,
605 typename std::enable_if<!has_key_compare<OC>::value>::type * = nullptr>
606 hopscotch_hash(size_type bucket_count, const Hash &hash, const KeyEqual &equal,
607 const Allocator &alloc, float max_load_factor)
608 : Hash(hash), KeyEqual(equal), GrowthPolicy(bucket_count), m_buckets(alloc),
609 m_overflow_elements(alloc), m_first_or_empty_bucket(static_empty_bucket_ptr()),
610 m_nb_elements(0)
611 {
612 if (bucket_count > max_bucket_count()) {
613 throw std::length_error("The map exceeds its maxmimum size.");
614 }
615
616 if (bucket_count > 0) {
617 static_assert(NeighborhoodSize - 1 > 0, "");
618
619 // Can't directly construct with the appropriate size in the initializer
620 // as m_buckets(bucket_count, alloc) is not supported by GCC 4.8
621 m_buckets.resize(bucket_count + NeighborhoodSize - 1);
622 m_first_or_empty_bucket = m_buckets.data();
623 }
624
625 this->max_load_factor(max_load_factor);
626
627 // Check in the constructor instead of outside of a function to avoi compilation issues
628 // when value_type is not complete.
629 static_assert(
630 std::is_nothrow_move_constructible<value_type>::value ||
631 std::is_copy_constructible<value_type>::value,
632 "value_type must be either copy constructible or nothrow move constructible.");
633 }
634
635 template <class OC = OverflowContainer,
636 typename std::enable_if<has_key_compare<OC>::value>::type * = nullptr>
637 hopscotch_hash(size_type bucket_count, const Hash &hash, const KeyEqual &equal,
638 const Allocator &alloc, float max_load_factor,
639 const typename OC::key_compare &comp)
640 : Hash(hash), KeyEqual(equal), GrowthPolicy(bucket_count), m_buckets(alloc),
641 m_overflow_elements(comp, alloc), m_first_or_empty_bucket(static_empty_bucket_ptr()),
642 m_nb_elements(0)
643 {
644
645 if (bucket_count > max_bucket_count()) {
646 throw std::length_error("The map exceeds its maxmimum size.");
647 }
648
649 if (bucket_count > 0) {
650 static_assert(NeighborhoodSize - 1 > 0, "");
651
652 // Can't directly construct with the appropriate size in the initializer
653 // as m_buckets(bucket_count, alloc) is not supported by GCC 4.8
654 m_buckets.resize(bucket_count + NeighborhoodSize - 1);
655 m_first_or_empty_bucket = m_buckets.data();
656 }
657
658 this->max_load_factor(max_load_factor);
659
660 // Check in the constructor instead of outside of a function to avoi compilation issues
661 // when value_type is not complete.
662 static_assert(
663 std::is_nothrow_move_constructible<value_type>::value ||
664 std::is_copy_constructible<value_type>::value,
665 "value_type must be either copy constructible or nothrow move constructible.");
666 }
667
668 hopscotch_hash(const hopscotch_hash &other)
669 : Hash(other), KeyEqual(other), GrowthPolicy(other), m_buckets(other.m_buckets),
670 m_overflow_elements(other.m_overflow_elements),
671 m_first_or_empty_bucket(m_buckets.empty() ? static_empty_bucket_ptr()
672 : m_buckets.data()),
673 m_nb_elements(other.m_nb_elements), m_max_load_factor(other.m_max_load_factor),
674 m_max_load_threshold_rehash(other.m_max_load_threshold_rehash),
675 m_min_load_threshold_rehash(other.m_min_load_threshold_rehash)
676 {
677 }
678
679 hopscotch_hash(hopscotch_hash &&other) noexcept(
680 std::is_nothrow_move_constructible<Hash>::value &&std::is_nothrow_move_constructible<
681 KeyEqual>::value &&std::is_nothrow_move_constructible<GrowthPolicy>::value
682 && std::is_nothrow_move_constructible<buckets_container_type>::value
683 && std::is_nothrow_move_constructible<overflow_container_type>::value)
684 : Hash(std::move(static_cast<Hash &>(other))),
685 KeyEqual(std::move(static_cast<KeyEqual &>(other))),
686 GrowthPolicy(std::move(static_cast<GrowthPolicy &>(other))),
687 m_buckets(std::move(other.m_buckets)),
688 m_overflow_elements(std::move(other.m_overflow_elements)),
689 m_first_or_empty_bucket(m_buckets.empty() ? static_empty_bucket_ptr()
690 : m_buckets.data()),
691 m_nb_elements(other.m_nb_elements), m_max_load_factor(other.m_max_load_factor),
692 m_max_load_threshold_rehash(other.m_max_load_threshold_rehash),
693 m_min_load_threshold_rehash(other.m_min_load_threshold_rehash)
694 {
695 other.GrowthPolicy::clear();
696 other.m_buckets.clear();
697 other.m_overflow_elements.clear();
698 other.m_first_or_empty_bucket = static_empty_bucket_ptr();
699 other.m_nb_elements = 0;
700 other.m_max_load_threshold_rehash = 0;
701 other.m_min_load_threshold_rehash = 0;
702 }
703
704 hopscotch_hash &operator=(const hopscotch_hash &other)
705 {
706 if (&other != this) {
707 Hash:: operator=(other);
708 KeyEqual:: operator=(other);
709 GrowthPolicy::operator=(other);
710
711 m_buckets = other.m_buckets;
712 m_overflow_elements = other.m_overflow_elements;
713 m_first_or_empty_bucket =
714 m_buckets.empty() ? static_empty_bucket_ptr() : m_buckets.data();
715 m_nb_elements = other.m_nb_elements;
716 m_max_load_factor = other.m_max_load_factor;
717 m_max_load_threshold_rehash = other.m_max_load_threshold_rehash;
718 m_min_load_threshold_rehash = other.m_min_load_threshold_rehash;
719 }
720
721 return *this;
722 }
723
724 hopscotch_hash &operator=(hopscotch_hash &&other)
725 {
726 other.swap(*this);
727 other.clear();
728
729 return *this;
730 }
731
732 allocator_type get_allocator() const { return m_buckets.get_allocator(); }
733
734 /*
735 * Iterators
736 */
737 iterator begin() noexcept
738 {
739 auto begin = m_buckets.begin();
740 while (begin != m_buckets.end() && begin->empty()) {
741 ++begin;
742 }
743
744 return iterator(begin, m_buckets.end(), m_overflow_elements.begin());
745 }
746
747 const_iterator begin() const noexcept { return cbegin(); }
748
749 const_iterator cbegin() const noexcept
750 {
751 auto begin = m_buckets.cbegin();
752 while (begin != m_buckets.cend() && begin->empty()) {
753 ++begin;
754 }
755
756 return const_iterator(begin, m_buckets.cend(), m_overflow_elements.cbegin());
757 }
758
759 iterator end() noexcept
760 {
761 return iterator(m_buckets.end(), m_buckets.end(), m_overflow_elements.end());
762 }
763
764 const_iterator end() const noexcept { return cend(); }
765
766 const_iterator cend() const noexcept
767 {
768 return const_iterator(m_buckets.cend(), m_buckets.cend(), m_overflow_elements.cend());
769 }
770
771 /*
772 * Capacity
773 */
774 bool empty() const noexcept { return m_nb_elements == 0; }
775
776 size_type size() const noexcept { return m_nb_elements; }
777
778 size_type max_size() const noexcept { return hopscotch_bucket::max_size(); }
779
780 /*
781 * Modifiers
782 */
783 void clear() noexcept
784 {
785 for (auto &bucket : m_buckets) {
786 bucket.clear();
787 }
788
789 m_overflow_elements.clear();
790 m_nb_elements = 0;
791 }
792
793 std::pair<iterator, bool> insert(const value_type &value) { return insert_impl(value); }
794
795 template <class P, typename std::enable_if<
796 std::is_constructible<value_type, P &&>::value>::type * = nullptr>
797 std::pair<iterator, bool> insert(P &&value)
798 {
799 return insert_impl(value_type(std::forward<P>(value)));
800 }
801
802 std::pair<iterator, bool> insert(value_type &&value) { return insert_impl(std::move(value)); }
803
804 iterator insert(const_iterator hint, const value_type &value)
805 {
806 if (hint != cend() && compare_keys(KeySelect()(*hint), KeySelect()(value))) {
807 return mutable_iterator(hint);
808 }
809
810 return insert(value).first;
811 }
812
813 template <class P, typename std::enable_if<
814 std::is_constructible<value_type, P &&>::value>::type * = nullptr>
815 iterator insert(const_iterator hint, P &&value)
816 {
817 return emplace_hint(hint, std::forward<P>(value));
818 }
819
820 iterator insert(const_iterator hint, value_type &&value)
821 {
822 if (hint != cend() && compare_keys(KeySelect()(*hint), KeySelect()(value))) {
823 return mutable_iterator(hint);
824 }
825
826 return insert(std::move(value)).first;
827 }
828
829 template <class InputIt> void insert(InputIt first, InputIt last)
830 {
831 if (std::is_base_of<std::forward_iterator_tag,
832 typename std::iterator_traits<InputIt>::iterator_category>::value) {
833 const auto nb_elements_insert = std::distance(first, last);
834 const std::size_t nb_elements_in_buckets = m_nb_elements - m_overflow_elements.size();
835 const std::size_t nb_free_buckets = m_max_load_threshold_rehash - nb_elements_in_buckets;
836 tsl_hh_assert(m_nb_elements >= m_overflow_elements.size());
837 tsl_hh_assert(m_max_load_threshold_rehash >= nb_elements_in_buckets);
838
839 if (nb_elements_insert > 0 && nb_free_buckets < std::size_t(nb_elements_insert)) {
840 reserve(nb_elements_in_buckets + std::size_t(nb_elements_insert));
841 }
842 }
843
844 for (; first != last; ++first) {
845 insert(*first);
846 }
847 }
848
849 template <class M> std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj)
850 {
851 return insert_or_assign_impl(k, std::forward<M>(obj));
852 }
853
854 template <class M> std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj)
855 {
856 return insert_or_assign_impl(std::move(k), std::forward<M>(obj));
857 }
858
859 template <class M> iterator insert_or_assign(const_iterator hint, const key_type &k, M &&obj)
860 {
861 if (hint != cend() && compare_keys(KeySelect()(*hint), k)) {
862 auto it = mutable_iterator(hint);
863 it.value() = std::forward<M>(obj);
864
865 return it;
866 }
867
868 return insert_or_assign(k, std::forward<M>(obj)).first;
869 }
870
871 template <class M> iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj)
872 {
873 if (hint != cend() && compare_keys(KeySelect()(*hint), k)) {
874 auto it = mutable_iterator(hint);
875 it.value() = std::forward<M>(obj);
876
877 return it;
878 }
879
880 return insert_or_assign(std::move(k), std::forward<M>(obj)).first;
881 }
882
883 template <class... Args> std::pair<iterator, bool> emplace(Args &&... args)
884 {
885 return insert(value_type(std::forward<Args>(args)...));
886 }
887
888 template <class... Args> iterator emplace_hint(const_iterator hint, Args &&... args)
889 {
890 return insert(hint, value_type(std::forward<Args>(args)...));
891 }
892
893 template <class... Args>
894 std::pair<iterator, bool> try_emplace(const key_type &k, Args &&... args)
895 {
896 return try_emplace_impl(k, std::forward<Args>(args)...);
897 }
898
899 template <class... Args> std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args)
900 {
901 return try_emplace_impl(std::move(k), std::forward<Args>(args)...);
902 }
903
904 template <class... Args>
905 iterator try_emplace(const_iterator hint, const key_type &k, Args &&... args)
906 {
907 if (hint != cend() && compare_keys(KeySelect()(*hint), k)) {
908 return mutable_iterator(hint);
909 }
910
911 return try_emplace(k, std::forward<Args>(args)...).first;
912 }
913
914 template <class... Args>
915 iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args)
916 {
917 if (hint != cend() && compare_keys(KeySelect()(*hint), k)) {
918 return mutable_iterator(hint);
919 }
920
921 return try_emplace(std::move(k), std::forward<Args>(args)...).first;
922 }
923
924 /**
925 * Here to avoid `template<class K> size_type erase(const K& key)` being used when
926 * we use an iterator instead of a const_iterator.
927 */
928 iterator erase(iterator pos) { return erase(const_iterator(pos)); }
929
930 iterator erase(const_iterator pos)
931 {
932 const std::size_t ibucket_for_hash = bucket_for_hash(hash_key(pos.key()));
933
934 if (pos.m_buckets_iterator != pos.m_buckets_end_iterator) {
935 auto it_bucket =
936 m_buckets.begin() + std::distance(m_buckets.cbegin(), pos.m_buckets_iterator);
937 erase_from_bucket(*it_bucket, ibucket_for_hash);
938
939 return ++iterator(it_bucket, m_buckets.end(), m_overflow_elements.begin());
940 }
941 else {
942 auto it_next_overflow = erase_from_overflow(pos.m_overflow_iterator, ibucket_for_hash);
943 return iterator(m_buckets.end(), m_buckets.end(), it_next_overflow);
944 }
945 }
946
947 iterator erase(const_iterator first, const_iterator last)
948 {
949 if (first == last) {
950 return mutable_iterator(first);
951 }
952
953 auto to_delete = erase(first);
954 while (to_delete != last) {
955 to_delete = erase(to_delete);
956 }
957
958 return to_delete;
959 }
960
961 template <class K> size_type erase(const K &key) { return erase(key, hash_key(key)); }
962
963 template <class K> size_type erase(const K &key, std::size_t hash)
964 {
965 const std::size_t ibucket_for_hash = bucket_for_hash(hash);
966
967 hopscotch_bucket *bucket_found =
968 find_in_buckets(key, hash, m_first_or_empty_bucket + ibucket_for_hash);
969 if (bucket_found != nullptr) {
970 erase_from_bucket(*bucket_found, ibucket_for_hash);
971
972 return 1;
973 }
974
975 if ((m_first_or_empty_bucket + ibucket_for_hash)->has_overflow()) {
976 auto it_overflow = find_in_overflow(key);
977 if (it_overflow != m_overflow_elements.end()) {
978 erase_from_overflow(it_overflow, ibucket_for_hash);
979
980 return 1;
981 }
982 }
983
984 return 0;
985 }
986
987 void swap(hopscotch_hash &other)
988 {
989 using std::swap;
990
991 swap(static_cast<Hash &>(*this), static_cast<Hash &>(other));
992 swap(static_cast<KeyEqual &>(*this), static_cast<KeyEqual &>(other));
993 swap(static_cast<GrowthPolicy &>(*this), static_cast<GrowthPolicy &>(other));
994 swap(m_buckets, other.m_buckets);
995 swap(m_overflow_elements, other.m_overflow_elements);
996 swap(m_first_or_empty_bucket, other.m_first_or_empty_bucket);
997 swap(m_nb_elements, other.m_nb_elements);
998 swap(m_max_load_factor, other.m_max_load_factor);
999 swap(m_max_load_threshold_rehash, other.m_max_load_threshold_rehash);
1000 swap(m_min_load_threshold_rehash, other.m_min_load_threshold_rehash);
1001 }
1002
1003 /*
1004 * Lookup
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)
1009 {
1010 return at(key, hash_key(key));
1011 }
1012
1013 template <class K, class U = ValueSelect,
1014 typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
1015 typename U::value_type &at(const K &key, std::size_t hash)
1016 {
1017 return const_cast<typename U::value_type &>(
1018 static_cast<const hopscotch_hash *>(this)->at(key, hash));
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) const
1024 {
1025 return at(key, hash_key(key));
1026 }
1027
1028 template <class K, class U = ValueSelect,
1029 typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
1030 const typename U::value_type &at(const K &key, std::size_t hash) const
1031 {
1032 using T = typename U::value_type;
1033
1034 const T *value =
1035 find_value_impl(key, hash, m_first_or_empty_bucket + bucket_for_hash(hash));
1036 if (value == nullptr) {
1037 throw std::out_of_range("Couldn't find key.");
1038 }
1039 else {
1040 return *value;
1041 }
1042 }
1043
1044 template <class K, class U = ValueSelect,
1045 typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
1046 typename U::value_type &operator[](K &&key)
1047 {
1048 using T = typename U::value_type;
1049
1050 const std::size_t hash = hash_key(key);
1051 const std::size_t ibucket_for_hash = bucket_for_hash(hash);
1052
1053 T *value = find_value_impl(key, hash, m_first_or_empty_bucket + ibucket_for_hash);
1054 if (value != nullptr) {
1055 return *value;
1056 }
1057 else {
1058 return insert_impl(ibucket_for_hash, hash, std::piecewise_construct,
1059 std::forward_as_tuple(std::forward<K>(key)), std::forward_as_tuple())
1060 .first.value();
1061 }
1062 }
1063
1064 template <class K> size_type count(const K &key) const { return count(key, hash_key(key)); }
1065
1066 template <class K> size_type count(const K &key, std::size_t hash) const
1067 {
1068 return count_impl(key, hash, m_first_or_empty_bucket + bucket_for_hash(hash));
1069 }
1070
1071 template <class K> iterator find(const K &key) { return find(key, hash_key(key)); }
1072
1073 template <class K> iterator find(const K &key, std::size_t hash)
1074 {
1075 return find_impl(key, hash, m_first_or_empty_bucket + bucket_for_hash(hash));
1076 }
1077
1078 template <class K> const_iterator find(const K &key) const
1079 {
1080 return find(key, hash_key(key));
1081 }
1082
1083 template <class K> const_iterator find(const K &key, std::size_t hash) const
1084 {
1085 return find_impl(key, hash, m_first_or_empty_bucket + bucket_for_hash(hash));
1086 }
1087
1088 template <class K> std::pair<iterator, iterator> equal_range(const K &key)
1089 {
1090 return equal_range(key, hash_key(key));
1091 }
1092
1093 template <class K> std::pair<iterator, iterator> equal_range(const K &key, std::size_t hash)
1094 {
1095 iterator it = find(key, 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 hash) const
1106 {
1107 const_iterator it = find(key, 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.empty()) {
1122 return 0;
1123 }
1124
1125 return m_buckets.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.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.begin() + std::distance(m_buckets.cbegin(), pos.m_buckets_iterator);
1182 return iterator(it, m_buckets.end(), m_overflow_elements.begin());
1183 }
1184 else {
1185 // Get a non-const iterator
1186 auto it = mutable_overflow_iterator(pos.m_overflow_iterator);
1187 return iterator(m_buckets.end(), m_buckets.end(), it);
1188 }
1189 }
1190
1191 size_type overflow_size() const noexcept { return m_overflow_elements.size(); }
1192
1193 template <class U = OverflowContainer,
1194 typename std::enable_if<has_key_compare<U>::value>::type * = nullptr>
1195 typename U::key_compare key_comp() const
1196 {
1197 return m_overflow_elements.key_comp();
1198 }
1199
1200 private:
1201 template <class K> std::size_t hash_key(const K &key) const { return Hash::operator()(key); }
1202
1203 template <class K1, class K2> bool compare_keys(const K1 &key1, const K2 &key2) const
1204 {
1205 return KeyEqual::operator()(key1, key2);
1206 }
1207
1208 std::size_t bucket_for_hash(std::size_t hash) const
1209 {
1210 const std::size_t bucket = GrowthPolicy::bucket_for_hash(hash);
1211 tsl_hh_assert(bucket < m_buckets.size() || (bucket == 0 && m_buckets.empty()));
1212
1213 return bucket;
1214 }
1215
1216 template <
1217 typename U = value_type,
1218 typename std::enable_if<std::is_nothrow_move_constructible<U>::value>::type * = nullptr>
1219 void rehash_impl(size_type count_)
1220 {
1221 hopscotch_hash new_map = new_hopscotch_hash(count_);
1222
1223 if (!m_overflow_elements.empty()) {
1224 new_map.m_overflow_elements.swap(m_overflow_elements);
1225 new_map.m_nb_elements += new_map.m_overflow_elements.size();
1226
1227 for (const value_type &value : new_map.m_overflow_elements) {
1228 const std::size_t ibucket_for_hash =
1229 new_map.bucket_for_hash(new_map.hash_key(KeySelect()(value)));
1230 new_map.m_buckets[ibucket_for_hash].set_overflow(true);
1231 }
1232 }
1233
1234 try {
1235 const bool use_stored_hash = USE_STORED_HASH_ON_REHASH(new_map.bucket_count());
1236 for (auto it_bucket = m_buckets.begin(); it_bucket != m_buckets.end(); ++it_bucket) {
1237 if (it_bucket->empty()) {
1238 continue;
1239 }
1240
1241 const std::size_t hash = use_stored_hash
1242 ? it_bucket->truncated_bucket_hash()
1243 : new_map.hash_key(KeySelect()(it_bucket->value()));
1244 const std::size_t ibucket_for_hash = new_map.bucket_for_hash(hash);
1245
1246 new_map.insert_impl(ibucket_for_hash, hash, std::move(it_bucket->value()));
1247
1248 erase_from_bucket(*it_bucket, bucket_for_hash(hash));
1249 }
1250 }
1251 /*
1252 * The call to insert_impl may throw an exception if an element is added to the overflow
1253 * list. Rollback the elements in this case.
1254 */
1255 catch (...) {
1256 m_overflow_elements.swap(new_map.m_overflow_elements);
1257
1258 const bool use_stored_hash = USE_STORED_HASH_ON_REHASH(new_map.bucket_count());
1259 for (auto it_bucket = new_map.m_buckets.begin(); it_bucket != new_map.m_buckets.end();
1260 ++it_bucket) {
1261 if (it_bucket->empty()) {
1262 continue;
1263 }
1264
1265 const std::size_t hash = use_stored_hash ? it_bucket->truncated_bucket_hash()
1266 : hash_key(KeySelect()(it_bucket->value()));
1267 const std::size_t ibucket_for_hash = bucket_for_hash(hash);
1268
1269 // The elements we insert were not in the overflow list before the switch.
1270 // They will not be go in the overflow list if we rollback the switch.
1271 insert_impl(ibucket_for_hash, hash, std::move(it_bucket->value()));
1272 }
1273
1274 throw;
1275 }
1276
1277 new_map.swap(*this);
1278 }
1279
1280 template <
1281 typename U = value_type,
1282 typename std::enable_if<std::is_copy_constructible<U>::value &&
1283 !std::is_nothrow_move_constructible<U>::value>::type * = nullptr>
1284 void rehash_impl(size_type count_)
1285 {
1286 hopscotch_hash new_map = new_hopscotch_hash(count_);
1287
1288 const bool use_stored_hash = USE_STORED_HASH_ON_REHASH(new_map.bucket_count());
1289 for (const hopscotch_bucket &bucket : m_buckets) {
1290 if (bucket.empty()) {
1291 continue;
1292 }
1293
1294 const std::size_t hash = use_stored_hash ? bucket.truncated_bucket_hash()
1295 : new_map.hash_key(KeySelect()(bucket.value()));
1296 const std::size_t ibucket_for_hash = new_map.bucket_for_hash(hash);
1297
1298 new_map.insert_impl(ibucket_for_hash, hash, bucket.value());
1299 }
1300
1301 for (const value_type &value : m_overflow_elements) {
1302 const std::size_t hash = new_map.hash_key(KeySelect()(value));
1303 const std::size_t ibucket_for_hash = new_map.bucket_for_hash(hash);
1304
1305 new_map.insert_impl(ibucket_for_hash, hash, value);
1306 }
1307
1308 new_map.swap(*this);
1309 }
1310
1311 #ifdef TSL_HH_NO_RANGE_ERASE_WITH_CONST_ITERATOR
1312 iterator_overflow mutable_overflow_iterator(const_iterator_overflow it)
1313 {
1314 return std::next(m_overflow_elements.begin(),
1315 std::distance(m_overflow_elements.cbegin(), it));
1316 }
1317 #else
1318 iterator_overflow mutable_overflow_iterator(const_iterator_overflow it)
1319 {
1320 return m_overflow_elements.erase(it, it);
1321 }
1322 #endif
1323
1324 // iterator is in overflow list
1325 iterator_overflow erase_from_overflow(const_iterator_overflow pos,
1326 std::size_t ibucket_for_hash)
1327 {
1328 #ifdef TSL_HH_NO_RANGE_ERASE_WITH_CONST_ITERATOR
1329 auto it_next = m_overflow_elements.erase(mutable_overflow_iterator(pos));
1330 #else
1331 auto it_next = m_overflow_elements.erase(pos);
1332 #endif
1333 m_nb_elements--;
1334
1335 // Check if we can remove the overflow flag
1336 tsl_hh_assert(m_buckets[ibucket_for_hash].has_overflow());
1337 for (const value_type &value : m_overflow_elements) {
1338 const std::size_t bucket_for_value = bucket_for_hash(hash_key(KeySelect()(value)));
1339 if (bucket_for_value == ibucket_for_hash) {
1340 return it_next;
1341 }
1342 }
1343
1344 m_buckets[ibucket_for_hash].set_overflow(false);
1345 return it_next;
1346 }
1347
1348 /**
1349 * bucket_for_value is the bucket in which the value is.
1350 * ibucket_for_hash is the bucket where the value belongs.
1351 */
1352 void erase_from_bucket(hopscotch_bucket &bucket_for_value,
1353 std::size_t ibucket_for_hash) noexcept
1354 {
1355 const std::size_t ibucket_for_value = std::distance(m_buckets.data(), &bucket_for_value);
1356 tsl_hh_assert(ibucket_for_value >= ibucket_for_hash);
1357
1358 bucket_for_value.remove_value();
1359 m_buckets[ibucket_for_hash].toggle_neighbor_presence(ibucket_for_value - ibucket_for_hash);
1360 m_nb_elements--;
1361 }
1362
1363 template <class K, class M> std::pair<iterator, bool> insert_or_assign_impl(K &&key, M &&obj)
1364 {
1365 auto it = try_emplace_impl(std::forward<K>(key), std::forward<M>(obj));
1366 if (!it.second) {
1367 it.first.value() = std::forward<M>(obj);
1368 }
1369
1370 return it;
1371 }
1372
1373 template <typename P, class... Args>
1374 std::pair<iterator, bool> try_emplace_impl(P &&key, Args &&... args_value)
1375 {
1376 const std::size_t hash = hash_key(key);
1377 const std::size_t ibucket_for_hash = bucket_for_hash(hash);
1378
1379 // Check if already presents
1380 auto it_find = find_impl(key, hash, m_first_or_empty_bucket + ibucket_for_hash);
1381 if (it_find != end()) {
1382 return std::make_pair(it_find, false);
1383 }
1384
1385 return insert_impl(ibucket_for_hash, hash, std::piecewise_construct,
1386 std::forward_as_tuple(std::forward<P>(key)),
1387 std::forward_as_tuple(std::forward<Args>(args_value)...));
1388 }
1389
1390 template <typename P> std::pair<iterator, bool> insert_impl(P &&value)
1391 {
1392 const std::size_t hash = hash_key(KeySelect()(value));
1393 const std::size_t ibucket_for_hash = bucket_for_hash(hash);
1394
1395 // Check if already presents
1396 auto it_find =
1397 find_impl(KeySelect()(value), hash, m_first_or_empty_bucket + ibucket_for_hash);
1398 if (it_find != end()) {
1399 return std::make_pair(it_find, false);
1400 }
1401
1402 return insert_impl(ibucket_for_hash, hash, std::forward<P>(value));
1403 }
1404
1405 template <typename... Args>
1406 std::pair<iterator, bool> insert_impl(std::size_t ibucket_for_hash, std::size_t hash,
1407 Args &&... value_type_args)
1408 {
1409 if ((m_nb_elements - m_overflow_elements.size()) >= m_max_load_threshold_rehash) {
1410 rehash(GrowthPolicy::next_bucket_count());
1411 ibucket_for_hash = bucket_for_hash(hash);
1412 }
1413
1414 std::size_t ibucket_empty = find_empty_bucket(ibucket_for_hash);
1415 if (ibucket_empty < m_buckets.size()) {
1416 do {
1417 tsl_hh_assert(ibucket_empty >= ibucket_for_hash);
1418
1419 // Empty bucket is in range of NeighborhoodSize, use it
1420 if (ibucket_empty - ibucket_for_hash < NeighborhoodSize) {
1421 auto it = insert_in_bucket(ibucket_empty, ibucket_for_hash, hash,
1422 std::forward<Args>(value_type_args)...);
1423 return std::make_pair(iterator(it, m_buckets.end(), m_overflow_elements.begin()),
1424 true);
1425 }
1426 }
1427 // else, try to swap values to get a closer empty bucket
1428 while (swap_empty_bucket_closer(ibucket_empty));
1429 }
1430
1431 // Load factor is too low or a rehash will not change the neighborhood, put the value in
1432 // overflow list
1433 if (size() < m_min_load_threshold_rehash ||
1434 !will_neighborhood_change_on_rehash(ibucket_for_hash)) {
1435 auto it = insert_in_overflow(ibucket_for_hash, std::forward<Args>(value_type_args)...);
1436 return std::make_pair(iterator(m_buckets.end(), m_buckets.end(), it), true);
1437 }
1438
1439 rehash(GrowthPolicy::next_bucket_count());
1440 ibucket_for_hash = bucket_for_hash(hash);
1441
1442 return insert_impl(ibucket_for_hash, hash, std::forward<Args>(value_type_args)...);
1443 }
1444
1445 /*
1446 * Return true if a rehash will change the position of a key-value in the neighborhood of
1447 * ibucket_neighborhood_check. In this case a rehash is needed instead of puting the value in
1448 * overflow list.
1449 */
1450 bool will_neighborhood_change_on_rehash(size_t ibucket_neighborhood_check) const
1451 {
1452 std::size_t expand_bucket_count = GrowthPolicy::next_bucket_count();
1453 GrowthPolicy expand_growth_policy(expand_bucket_count);
1454
1455 const bool use_stored_hash = USE_STORED_HASH_ON_REHASH(expand_bucket_count);
1456 for (size_t ibucket = ibucket_neighborhood_check;
1457 ibucket < m_buckets.size() &&
1458 (ibucket - ibucket_neighborhood_check) < NeighborhoodSize;
1459 ++ibucket) {
1460 tsl_hh_assert(!m_buckets[ibucket].empty());
1461
1462 const size_t hash = use_stored_hash ? m_buckets[ibucket].truncated_bucket_hash()
1463 : hash_key(KeySelect()(m_buckets[ibucket].value()));
1464 if (bucket_for_hash(hash) != expand_growth_policy.bucket_for_hash(hash)) {
1465 return true;
1466 }
1467 }
1468
1469 return false;
1470 }
1471
1472 /*
1473 * Return the index of an empty bucket in m_buckets.
1474 * If none, the returned index equals m_buckets.size()
1475 */
1476 std::size_t find_empty_bucket(std::size_t ibucket_start) const
1477 {
1478 const std::size_t limit =
1479 std::min(ibucket_start + MAX_PROBES_FOR_EMPTY_BUCKET, m_buckets.size());
1480 for (; ibucket_start < limit; ibucket_start++) {
1481 if (m_buckets[ibucket_start].empty()) {
1482 return ibucket_start;
1483 }
1484 }
1485
1486 return m_buckets.size();
1487 }
1488
1489 /*
1490 * Insert value in ibucket_empty where value originally belongs to ibucket_for_hash
1491 *
1492 * Return bucket iterator to ibucket_empty
1493 */
1494 template <typename... Args>
1495 iterator_buckets insert_in_bucket(std::size_t ibucket_empty, std::size_t ibucket_for_hash,
1496 std::size_t hash, Args &&... value_type_args)
1497 {
1498 tsl_hh_assert(ibucket_empty >= ibucket_for_hash);
1499 tsl_hh_assert(m_buckets[ibucket_empty].empty());
1500 m_buckets[ibucket_empty].set_value_of_empty_bucket(hopscotch_bucket::truncate_hash(hash),
1501 std::forward<Args>(value_type_args)...);
1502
1503 tsl_hh_assert(!m_buckets[ibucket_for_hash].empty());
1504 m_buckets[ibucket_for_hash].toggle_neighbor_presence(ibucket_empty - ibucket_for_hash);
1505 m_nb_elements++;
1506
1507 return m_buckets.begin() + ibucket_empty;
1508 }
1509
1510 template <class... Args, class U = OverflowContainer,
1511 typename std::enable_if<!has_key_compare<U>::value>::type * = nullptr>
1512 iterator_overflow insert_in_overflow(std::size_t ibucket_for_hash, Args &&... value_type_args)
1513 {
1514 auto it = m_overflow_elements.emplace(m_overflow_elements.end(),
1515 std::forward<Args>(value_type_args)...);
1516
1517 m_buckets[ibucket_for_hash].set_overflow(true);
1518 m_nb_elements++;
1519
1520 return it;
1521 }
1522
1523 template <class... Args, class U = OverflowContainer,
1524 typename std::enable_if<has_key_compare<U>::value>::type * = nullptr>
1525 iterator_overflow insert_in_overflow(std::size_t ibucket_for_hash, Args &&... value_type_args)
1526 {
1527 auto it = m_overflow_elements.emplace(std::forward<Args>(value_type_args)...).first;
1528
1529 m_buckets[ibucket_for_hash].set_overflow(true);
1530 m_nb_elements++;
1531
1532 return it;
1533 }
1534
1535 /*
1536 * Try to swap the bucket ibucket_empty_in_out with a bucket preceding it while keeping the
1537 * neighborhood conditions correct.
1538 *
1539 * If a swap was possible, the position of ibucket_empty_in_out will be closer to 0 and true
1540 * will re returned.
1541 */
1542 bool swap_empty_bucket_closer(std::size_t &ibucket_empty_in_out)
1543 {
1544 tsl_hh_assert(ibucket_empty_in_out >= NeighborhoodSize);
1545 const std::size_t neighborhood_start = ibucket_empty_in_out - NeighborhoodSize + 1;
1546
1547 for (std::size_t to_check = neighborhood_start; to_check < ibucket_empty_in_out;
1548 to_check++) {
1549 neighborhood_bitmap neighborhood_infos = m_buckets[to_check].neighborhood_infos();
1550 std::size_t to_swap = to_check;
1551
1552 while (neighborhood_infos != 0 && to_swap < ibucket_empty_in_out) {
1553 if ((neighborhood_infos & 1) == 1) {
1554 tsl_hh_assert(m_buckets[ibucket_empty_in_out].empty());
1555 tsl_hh_assert(!m_buckets[to_swap].empty());
1556
1557 m_buckets[to_swap].swap_value_into_empty_bucket(m_buckets[ibucket_empty_in_out]);
1558
1559 tsl_hh_assert(
1560 !m_buckets[to_check].check_neighbor_presence(ibucket_empty_in_out - to_check));
1561 tsl_hh_assert(m_buckets[to_check].check_neighbor_presence(to_swap - to_check));
1562
1563 m_buckets[to_check].toggle_neighbor_presence(ibucket_empty_in_out - to_check);
1564 m_buckets[to_check].toggle_neighbor_presence(to_swap - to_check);
1565
1566 ibucket_empty_in_out = to_swap;
1567
1568 return true;
1569 }
1570
1571 to_swap++;
1572 neighborhood_infos = neighborhood_bitmap(neighborhood_infos >> 1);
1573 }
1574 }
1575
1576 return false;
1577 }
1578
1579 template <class K, class U = ValueSelect,
1580 typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
1581 typename U::value_type *find_value_impl(const K &key, std::size_t hash,
1582 hopscotch_bucket *bucket_for_hash)
1583 {
1584 return const_cast<typename U::value_type *>(
1585 static_cast<const hopscotch_hash *>(this)->find_value_impl(key, hash, bucket_for_hash));
1586 }
1587
1588 /*
1589 * Avoid the creation of an iterator to just get the value for operator[] and at() in maps.
1590 * Faster this way.
1591 *
1592 * Return null if no value for the key (TODO use std::optional when available).
1593 */
1594 template <class K, class U = ValueSelect,
1595 typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
1596 const typename U::value_type *find_value_impl(const K &key, std::size_t hash,
1597 const hopscotch_bucket *bucket_for_hash) const
1598 {
1599 const hopscotch_bucket *bucket_found = find_in_buckets(key, hash, bucket_for_hash);
1600 if (bucket_found != nullptr) {
1601 return std::addressof(ValueSelect()(bucket_found->value()));
1602 }
1603
1604 if (bucket_for_hash->has_overflow()) {
1605 auto it_overflow = find_in_overflow(key);
1606 if (it_overflow != m_overflow_elements.end()) {
1607 return std::addressof(ValueSelect()(*it_overflow));
1608 }
1609 }
1610
1611 return nullptr;
1612 }
1613
1614 template <class K>
1615 size_type count_impl(const K &key, std::size_t hash,
1616 const hopscotch_bucket *bucket_for_hash) const
1617 {
1618 if (find_in_buckets(key, hash, bucket_for_hash) != nullptr) {
1619 return 1;
1620 }
1621 else if (bucket_for_hash->has_overflow() &&
1622 find_in_overflow(key) != m_overflow_elements.cend()) {
1623 return 1;
1624 }
1625 else {
1626 return 0;
1627 }
1628 }
1629
1630 template <class K>
1631 iterator find_impl(const K &key, std::size_t hash, hopscotch_bucket *bucket_for_hash)
1632 {
1633 hopscotch_bucket *bucket_found = find_in_buckets(key, hash, bucket_for_hash);
1634 if (bucket_found != nullptr) {
1635 return iterator(m_buckets.begin() + std::distance(m_buckets.data(), bucket_found),
1636 m_buckets.end(), m_overflow_elements.begin());
1637 }
1638
1639 if (!bucket_for_hash->has_overflow()) {
1640 return end();
1641 }
1642
1643 return iterator(m_buckets.end(), m_buckets.end(), find_in_overflow(key));
1644 }
1645
1646 template <class K>
1647 const_iterator find_impl(const K &key, std::size_t hash,
1648 const hopscotch_bucket *bucket_for_hash) const
1649 {
1650 const hopscotch_bucket *bucket_found = find_in_buckets(key, hash, bucket_for_hash);
1651 if (bucket_found != nullptr) {
1652 return const_iterator(m_buckets.cbegin() + std::distance(m_buckets.data(), bucket_found),
1653 m_buckets.cend(), m_overflow_elements.cbegin());
1654 }
1655
1656 if (!bucket_for_hash->has_overflow()) {
1657 return cend();
1658 }
1659
1660 return const_iterator(m_buckets.cend(), m_buckets.cend(), find_in_overflow(key));
1661 }
1662
1663 template <class K>
1664 hopscotch_bucket *find_in_buckets(const K &key, std::size_t hash,
1665 hopscotch_bucket *bucket_for_hash)
1666 {
1667 const hopscotch_bucket *bucket_found =
1668 static_cast<const hopscotch_hash *>(this)->find_in_buckets(key, hash, bucket_for_hash);
1669 return const_cast<hopscotch_bucket *>(bucket_found);
1670 }
1671
1672 /**
1673 * Return a pointer to the bucket which has the value, nullptr otherwise.
1674 */
1675 template <class K>
1676 const hopscotch_bucket *find_in_buckets(const K &key, std::size_t hash,
1677 const hopscotch_bucket *bucket_for_hash) const
1678 {
1679 (void)hash; // Avoid warning of unused variable when StoreHash is false;
1680
1681 // TODO Try to optimize the function.
1682 // I tried to use ffs and __builtin_ffs functions but I could not reduce the time the
1683 // function takes with -march=native
1684
1685 neighborhood_bitmap neighborhood_infos = bucket_for_hash->neighborhood_infos();
1686 while (neighborhood_infos != 0) {
1687 if ((neighborhood_infos & 1) == 1) {
1688 // Check StoreHash before calling bucket_hash_equal. Functionally it doesn't change
1689 // anythin. If StoreHash is false, bucket_hash_equal is a no-op. Avoiding the call is
1690 // there to help GCC optimizes `hash` parameter away, it seems to not be able to do
1691 // without this hint.
1692 if ((!StoreHash || bucket_for_hash->bucket_hash_equal(hash)) &&
1693 compare_keys(KeySelect()(bucket_for_hash->value()), key)) {
1694 return bucket_for_hash;
1695 }
1696 }
1697
1698 ++bucket_for_hash;
1699 neighborhood_infos = neighborhood_bitmap(neighborhood_infos >> 1);
1700 }
1701
1702 return nullptr;
1703 }
1704
1705 template <class K, class U = OverflowContainer,
1706 typename std::enable_if<!has_key_compare<U>::value>::type * = nullptr>
1707 iterator_overflow find_in_overflow(const K &key)
1708 {
1709 return std::find_if(
1710 m_overflow_elements.begin(), m_overflow_elements.end(),
1711 [&](const value_type &value) { return compare_keys(key, KeySelect()(value)); });
1712 }
1713
1714 template <class K, class U = OverflowContainer,
1715 typename std::enable_if<!has_key_compare<U>::value>::type * = nullptr>
1716 const_iterator_overflow find_in_overflow(const K &key) const
1717 {
1718 return std::find_if(
1719 m_overflow_elements.cbegin(), m_overflow_elements.cend(),
1720 [&](const value_type &value) { return compare_keys(key, KeySelect()(value)); });
1721 }
1722
1723 template <class K, class U = OverflowContainer,
1724 typename std::enable_if<has_key_compare<U>::value>::type * = nullptr>
1725 iterator_overflow find_in_overflow(const K &key)
1726 {
1727 return m_overflow_elements.find(key);
1728 }
1729
1730 template <class K, class U = OverflowContainer,
1731 typename std::enable_if<has_key_compare<U>::value>::type * = nullptr>
1732 const_iterator_overflow find_in_overflow(const K &key) const
1733 {
1734 return m_overflow_elements.find(key);
1735 }
1736
1737 template <class U = OverflowContainer,
1738 typename std::enable_if<!has_key_compare<U>::value>::type * = nullptr>
1739 hopscotch_hash new_hopscotch_hash(size_type bucket_count)
1740 {
1741 return hopscotch_hash(bucket_count, static_cast<Hash &>(*this),
1742 static_cast<KeyEqual &>(*this), get_allocator(), m_max_load_factor);
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 m_overflow_elements.key_comp());
1752 }
1753
1754 public:
1755 static const size_type DEFAULT_INIT_BUCKETS_SIZE = 16;
1756 static constexpr float DEFAULT_MAX_LOAD_FACTOR = (NeighborhoodSize <= 30) ? 0.8f : 0.9f;
1757
1758 private:
1759 static const std::size_t MAX_PROBES_FOR_EMPTY_BUCKET = 12 * NeighborhoodSize;
1760 static constexpr float MIN_LOAD_FACTOR_FOR_REHASH = 0.1f;
1761
1762 static bool USE_STORED_HASH_ON_REHASH(size_type bucket_count)
1763 {
1764 (void)bucket_count;
1765 if (StoreHash && is_power_of_two_policy<GrowthPolicy>::value) {
1766 tsl_hh_assert(bucket_count > 0);
1767 return (bucket_count - 1) <= std::numeric_limits<truncated_hash_type>::max();
1768 }
1769 else {
1770 return false;
1771 }
1772 }
1773
1774 /**
1775 * Return an always valid pointer to an static empty hopscotch_bucket.
1776 */
1777 hopscotch_bucket *static_empty_bucket_ptr()
1778 {
1779 static hopscotch_bucket empty_bucket;
1780 return &empty_bucket;
1781 }
1782
1783 private:
1784 buckets_container_type m_buckets;
1785 overflow_container_type m_overflow_elements;
1786
1787 /**
1788 * Points to m_buckets.data() if !m_buckets.empty() otherwise points to
1789 * static_empty_bucket_ptr. This variable is useful to avoid the cost of checking if m_buckets
1790 * is empty when trying to find an element.
1791 */
1792 hopscotch_bucket *m_first_or_empty_bucket;
1793
1794 size_type m_nb_elements;
1795
1796 float m_max_load_factor;
1797
1798 /**
1799 * Max size of the hash table before a rehash occurs automatically to grow the table.
1800 */
1801 size_type m_max_load_threshold_rehash;
1802
1803 /**
1804 * Min size of the hash table before a rehash can occurs automatically (except if
1805 * m_max_load_threshold_rehash os reached). If the neighborhood of a bucket is full before the
1806 * min is reacher, the elements are put into m_overflow_elements.
1807 */
1808 size_type m_min_load_threshold_rehash;
1809 };
1810
1811 } // end namespace detail_hopscotch_hash
1812
1813 } // end namespace tsl
1814
1815 #endif
tsl::detail_hopscotch_hash::hopscotch_hash::erase
iterator erase(const_iterator pos)
Definition: hopscotch_hash.h:930
tsl::detail_hopscotch_hash::has_is_transparent
Definition: hopscotch_hash.h:69
tsl::detail_hopscotch_hash::hopscotch_hash::count_impl
size_type count_impl(const K &key, std::size_t hash, const hopscotch_bucket *bucket_for_hash) const
Definition: hopscotch_hash.h:1615
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:1762
tsl::detail_hopscotch_hash::hopscotch_hash::MIN_LOAD_FACTOR_FOR_REHASH
static constexpr float MIN_LOAD_FACTOR_FOR_REHASH
Definition: hopscotch_hash.h:1760
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_hash
hopscotch_hash(const hopscotch_hash &other)
Definition: hopscotch_hash.h:668
tsl::detail_hopscotch_hash::hopscotch_hash::reserve
void reserve(size_type count_)
Definition: hopscotch_hash.h:1162
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::size_type
std::size_t size_type
Definition: hopscotch_hash.h:445
tsl::detail_hopscotch_hash::hopscotch_hash::hash_key
std::size_t hash_key(const K &key) const
Definition: hopscotch_hash.h:1201
tsl::detail_hopscotch_hash::hopscotch_hash::find
iterator find(const K &key)
Definition: hopscotch_hash.h:1071
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::operator==
friend bool operator==(const hopscotch_iterator &lhs, const hopscotch_iterator &rhs)
Definition: hopscotch_hash.h:586
tsl::detail_hopscotch_hash::hopscotch_hash::bucket_count
size_type bucket_count() const
Definition: hopscotch_hash.h:1114
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::const_reference
const value_type & const_reference
Definition: hopscotch_hash.h:451
tsl::detail_hopscotch_hash::hopscotch_hash::rehash_impl
void rehash_impl(size_type count_)
Definition: hopscotch_hash.h:1219
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:854
tsl::detail_hopscotch_hash::hopscotch_bucket
Definition: hopscotch_hash.h:198
tsl::detail_hopscotch_hash::hopscotch_hash::end
const_iterator end() const noexcept
Definition: hopscotch_hash.h:764
tsl::detail_hopscotch_hash::hopscotch_hash::find_in_buckets
hopscotch_bucket * find_in_buckets(const K &key, std::size_t hash, hopscotch_bucket *bucket_for_hash)
Definition: hopscotch_hash.h:1664
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::allocator_type
Allocator allocator_type
Definition: hopscotch_hash.h:449
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:1325
tsl::detail_hopscotch_hash::make_void::type
void type
Definition: hopscotch_hash.h:66
tsl::detail_hopscotch_hash::hopscotch_hash::static_empty_bucket_ptr
hopscotch_bucket * static_empty_bucket_ptr()
Definition: hopscotch_hash.h:1777
tsl::detail_hopscotch_hash::hopscotch_bucket::set_value_of_empty_bucket
void set_value_of_empty_bucket(truncated_hash_type hash, Args &&... value_type_args)
Definition: hopscotch_hash.h:329
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::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< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::difference_type
std::ptrdiff_t difference_type
Definition: hopscotch_hash.h:446
tsl::detail_hopscotch_hash::hopscotch_hash
Definition: hopscotch_hash.h:429
tsl::detail_hopscotch_hash::hopscotch_hash::cbegin
const_iterator cbegin() const noexcept
Definition: hopscotch_hash.h:749
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::operator->
pointer operator->() const
Definition: hopscotch_hash.h:555
tsl::detail_hopscotch_hash::hopscotch_hash::find_impl
const_iterator find_impl(const K &key, std::size_t hash, const hopscotch_bucket *bucket_for_hash) const
Definition: hopscotch_hash.h:1647
tsl::detail_hopscotch_hash::hopscotch_hash::insert
std::pair< iterator, bool > insert(const value_type &value)
Definition: hopscotch_hash.h:793
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_bucket::value_type
ValueType value_type
Definition: hopscotch_hash.h:221
tsl::detail_hopscotch_hash::hopscotch_hash::DEFAULT_INIT_BUCKETS_SIZE
static const size_type DEFAULT_INIT_BUCKETS_SIZE
Definition: hopscotch_hash.h:1755
tsl::detail_hopscotch_hash::hopscotch_hash::insert
iterator insert(const_iterator hint, const value_type &value)
Definition: hopscotch_hash.h:804
tsl::detail_hopscotch_hash::hopscotch_hash::end
iterator end() noexcept
Definition: hopscotch_hash.h:759
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::m_overflow_iterator
iterator_overflow m_overflow_iterator
Definition: hopscotch_hash.h:600
tsl
Definition: hopscotch_growth_policy.h:37
tsl::detail_hopscotch_hash::hopscotch_hash::insert
iterator insert(const_iterator hint, value_type &&value)
Definition: hopscotch_hash.h:820
tsl::detail_hopscotch_hash::make_void
Definition: hopscotch_hash.h:64
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::value_type
Key value_type
Definition: hopscotch_hash.h:444
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:871
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, 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:433
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:849
tsl::detail_hopscotch_hash::hopscotch_bucket::value
value_type & value() noexcept
Definition: hopscotch_hash.h:316
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::iterator_overflow
typename overflow_container_type::iterator iterator_overflow
Definition: hopscotch_hash.h:478
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::m_buckets_iterator
iterator_bucket m_buckets_iterator
Definition: hopscotch_hash.h:598
tsl::detail_hopscotch_hash::hopscotch_hash::begin
iterator begin() noexcept
Definition: hopscotch_hash.h:737
tsl::detail_hopscotch_hash::hopscotch_bucket_hash< true >::bucket_hash_equal
bool bucket_hash_equal(std::size_t hash) const noexcept
Definition: hopscotch_hash.h:181
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:915
tsl::detail_hopscotch_hash::hopscotch_hash::max_load_factor
float max_load_factor() const
Definition: hopscotch_hash.h:1147
tsl::detail_hopscotch_hash::truncated_hash_type
std::uint_least32_t truncated_hash_type
Definition: hopscotch_hash.h:160
tsl::detail_hopscotch_hash::hopscotch_hash::m_first_or_empty_bucket
hopscotch_bucket * m_first_or_empty_bucket
Definition: hopscotch_hash.h:1792
tsl::detail_hopscotch_hash::hopscotch_hash::insert_impl
std::pair< iterator, bool > insert_impl(std::size_t ibucket_for_hash, std::size_t hash, Args &&... value_type_args)
Definition: hopscotch_hash.h:1406
tsl::detail_hopscotch_hash::hopscotch_bucket::~hopscotch_bucket
~hopscotch_bucket() noexcept
Definition: hopscotch_hash.h:273
tsl::detail_hopscotch_hash::hopscotch_bucket::truncate_hash
static truncated_hash_type truncate_hash(std::size_t hash) noexcept
Definition: hopscotch_hash.h:381
tsl::detail_hopscotch_hash::hopscotch_hash::at
U::value_type & at(const K &key, std::size_t hash)
Definition: hopscotch_hash.h:1015
tsl::detail_hopscotch_hash::hopscotch_hash::try_emplace
std::pair< iterator, bool > try_emplace(const key_type &k, Args &&... args)
Definition: hopscotch_hash.h:894
tsl::detail_hopscotch_hash::hopscotch_bucket::set_empty
void set_empty(bool is_empty) noexcept
Definition: hopscotch_hash.h:387
tsl_hh_assert
#define tsl_hh_assert(expr)
Definition: hopscotch_hash.h:57
tsl::detail_hopscotch_hash::hopscotch_hash::find
const_iterator find(const K &key) const
Definition: hopscotch_hash.h:1078
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::hasher
Hash hasher
Definition: hopscotch_hash.h:447
tsl::detail_hopscotch_hash::hopscotch_hash::find_value_impl
const U::value_type * find_value_impl(const K &key, std::size_t hash, const hopscotch_bucket *bucket_for_hash) const
Definition: hopscotch_hash.h:1596
tsl::detail_hopscotch_hash::hopscotch_bucket::value
const value_type & value() const noexcept
Definition: hopscotch_hash.h:322
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::empty
bool empty() const noexcept
Definition: hopscotch_hash.h:774
tsl::detail_hopscotch_hash::hopscotch_hash::m_buckets
buckets_container_type m_buckets
Definition: hopscotch_hash.h:1784
tsl::detail_hopscotch_hash::hopscotch_hash::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: hopscotch_hash.h:888
tsl::detail_hopscotch_hash::hopscotch_hash::compare_keys
bool compare_keys(const K1 &key1, const K2 &key2) const
Definition: hopscotch_hash.h:1203
tsl::detail_hopscotch_hash::hopscotch_hash::insert
std::pair< iterator, bool > insert(P &&value)
Definition: hopscotch_hash.h:797
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::const_iterator
hopscotch_iterator< true > const_iterator
Definition: hopscotch_hash.h:455
tsl::detail_hopscotch_hash::hopscotch_hash::m_overflow_elements
overflow_container_type m_overflow_elements
Definition: hopscotch_hash.h:1785
tsl::detail_hopscotch_hash::hopscotch_hash::insert
std::pair< iterator, bool > insert(value_type &&value)
Definition: hopscotch_hash.h:802
tsl::detail_hopscotch_hash::hopscotch_hash::size
size_type size() const noexcept
Definition: hopscotch_hash.h:776
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:1759
tsl::detail_hopscotch_hash::hopscotch_hash::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: hopscotch_hash.h:1088
tsl::detail_hopscotch_hash::hopscotch_hash::erase
iterator erase(const_iterator first, const_iterator last)
Definition: hopscotch_hash.h:947
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:679
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::hopscotch_iterator
hopscotch_iterator() noexcept
Definition: hopscotch_hash.h:515
tsl::detail_hopscotch_hash::hopscotch_hash::find_in_overflow
iterator_overflow find_in_overflow(const K &key)
Definition: hopscotch_hash.h:1707
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 hash, Args &&... value_type_args)
Definition: hopscotch_hash.h:1495
tsl::detail_hopscotch_hash::hopscotch_hash::try_emplace
std::pair< iterator, bool > try_emplace(key_type &&k, Args &&... args)
Definition: hopscotch_hash.h:899
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< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::key_type
typename KeySelect::key_type key_type
Definition: hopscotch_hash.h:443
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::max_load_factor
void max_load_factor(float ml)
Definition: hopscotch_hash.h:1149
tsl::detail_hopscotch_hash::hopscotch_hash::at
const U::value_type & at(const K &key, std::size_t hash) const
Definition: hopscotch_hash.h:1030
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::pointer
value_type * pointer
Definition: hopscotch_hash.h:513
hopscotch_growth_policy.h
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::iterator_buckets
typename buckets_container_type::iterator iterator_buckets
Definition: hopscotch_hash.h:475
tsl::detail_hopscotch_hash::hopscotch_hash::m_max_load_factor
float m_max_load_factor
Definition: hopscotch_hash.h:1796
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::value_type
const typename hopscotch_hash::value_type value_type
Definition: hopscotch_hash.h:510
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_bucket::has_overflow
bool has_overflow() const noexcept
Definition: hopscotch_hash.h:295
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::hopscotch_bucket::destroy_value
void destroy_value() noexcept
Definition: hopscotch_hash.h:397
tsl::detail_hopscotch_hash::has_key_compare
Definition: hopscotch_hash.h:79
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:496
tsl::detail_hopscotch_hash::hopscotch_hash::at
U::value_type & at(const K &key)
Definition: hopscotch_hash.h:1008
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::difference_type
std::ptrdiff_t difference_type
Definition: hopscotch_hash.h:511
tsl::detail_hopscotch_hash::hopscotch_hash::erase
size_type erase(const K &key, std::size_t hash)
Definition: hopscotch_hash.h:963
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:499
tsl::detail_hopscotch_hash::hopscotch_hash::DEFAULT_MAX_LOAD_FACTOR
static constexpr float DEFAULT_MAX_LOAD_FACTOR
Definition: hopscotch_hash.h:1756
tsl::detail_hopscotch_hash::hopscotch_hash::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: hopscotch_hash.h:883
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::key_equal
KeyEqual key_equal
Definition: hopscotch_hash.h:448
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::swap
void swap(hopscotch_hash &other)
Definition: hopscotch_hash.h:987
tsl::detail_hopscotch_hash::hopscotch_hash::try_emplace
iterator try_emplace(const_iterator hint, const key_type &k, Args &&... args)
Definition: hopscotch_hash.h:905
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::insert_or_assign_impl
std::pair< iterator, bool > insert_or_assign_impl(K &&key, M &&obj)
Definition: hopscotch_hash.h:1363
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:501
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::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t hash) const
Definition: hopscotch_hash.h:1105
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< Key, KeySelect, void, 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:463
tsl::detail_hopscotch_hash::hopscotch_bucket::max_size
static std::size_t max_size() noexcept
Definition: hopscotch_hash.h:371
tsl::detail_hopscotch_hash::hopscotch_bucket::storage
typename std::aligned_storage< sizeof(value_type), alignof(value_type)>::type storage
Definition: hopscotch_hash.h:404
tsl::detail_hopscotch_hash::hopscotch_hash::insert
void insert(InputIt first, InputIt last)
Definition: hopscotch_hash.h:829
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:1374
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::swap_empty_bucket_closer
bool swap_empty_bucket_closer(std::size_t &ibucket_empty_in_out)
Definition: hopscotch_hash.h:1542
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, 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:479
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_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::m_min_load_threshold_rehash
size_type m_min_load_threshold_rehash
Definition: hopscotch_hash.h:1808
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::iterator
hopscotch_iterator< false > iterator
Definition: hopscotch_hash.h:454
tsl::detail_hopscotch_hash::hopscotch_hash::key_comp
U::key_compare key_comp() const
Definition: hopscotch_hash.h:1195
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::operator *
reference operator *() const
Definition: hopscotch_hash.h:546
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:1476
tsl::detail_hopscotch_hash::hopscotch_hash::key_eq
key_equal key_eq() const
Definition: hopscotch_hash.h:1172
tsl::hh::power_of_two_growth_policy
Definition: hopscotch_growth_policy.h:47
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:1352
tsl::detail_hopscotch_hash::hopscotch_hash::find_in_overflow
const_iterator_overflow find_in_overflow(const K &key) const
Definition: hopscotch_hash.h:1716
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: hopscotch_hash.h:509
tsl::detail_hopscotch_hash::hopscotch_hash::m_nb_elements
size_type m_nb_elements
Definition: hopscotch_hash.h:1794
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::m_buckets_end_iterator
iterator_bucket m_buckets_end_iterator
Definition: hopscotch_hash.h:599
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:537
tsl::detail_hopscotch_hash::hopscotch_hash::m_max_load_threshold_rehash
size_type m_max_load_threshold_rehash
Definition: hopscotch_hash.h:1801
tsl::detail_hopscotch_hash::hopscotch_hash::insert_impl
std::pair< iterator, bool > insert_impl(P &&value)
Definition: hopscotch_hash.h:1390
tsl::detail_hopscotch_hash::hopscotch_hash::mutable_overflow_iterator
iterator_overflow mutable_overflow_iterator(const_iterator_overflow it)
Definition: hopscotch_hash.h:1318
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_hash
hopscotch_hash(size_type bucket_count, const Hash &hash, const KeyEqual &equal, const Allocator &alloc, float max_load_factor, const typename OC::key_compare &comp)
Definition: hopscotch_hash.h:637
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_hash< true >::copy_hash
void copy_hash(const hopscotch_bucket_hash &bucket) noexcept
Definition: hopscotch_hash.h:189
tsl::detail_hopscotch_hash::hopscotch_hash::find_value_impl
U::value_type * find_value_impl(const K &key, std::size_t hash, hopscotch_bucket *bucket_for_hash)
Definition: hopscotch_hash.h:1581
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
tsl::detail_hopscotch_hash::hopscotch_bucket::clear
void clear() noexcept
Definition: hopscotch_hash.h:361
tsl::detail_hopscotch_hash::hopscotch_bucket::empty
bool empty() const noexcept
Definition: hopscotch_hash.h:297
tsl::detail_hopscotch_hash::hopscotch_bucket::hopscotch_bucket
hopscotch_bucket() noexcept
Definition: hopscotch_hash.h:226
tsl::detail_hopscotch_hash::hopscotch_hash::count
size_type count(const K &key, std::size_t hash) const
Definition: hopscotch_hash.h:1066
tsl::detail_hopscotch_hash::hopscotch_bucket::remove_value
void remove_value() noexcept
Definition: hopscotch_hash.h:353
tsl::detail_hopscotch_hash::hopscotch_hash::count
size_type count(const K &key) const
Definition: hopscotch_hash.h:1064
tsl::detail_hopscotch_hash::hopscotch_hash::find
iterator find(const K &key, std::size_t hash)
Definition: hopscotch_hash.h:1073
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::operator!=
friend bool operator!=(const hopscotch_iterator &lhs, const hopscotch_iterator &rhs)
Definition: hopscotch_hash.h:592
tsl::detail_hopscotch_hash::hopscotch_bucket_hash
Definition: hopscotch_hash.h:165
anonymous_namespace{cth_pressure_map.C}::data
std::vector< char > data
Definition: cth_pressure_map.C:73
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::reference
value_type & reference
Definition: hopscotch_hash.h:450
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::operator++
hopscotch_iterator operator++(int)
Definition: hopscotch_hash.h:578
tsl::detail_hopscotch_hash::hopscotch_hash::equal_range
std::pair< iterator, iterator > equal_range(const K &key, std::size_t hash)
Definition: hopscotch_hash.h:1093
tsl::detail_hopscotch_hash::smallest_type_for_min_bits
Definition: hopscotch_hash.h:102
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::operator++
hopscotch_iterator & operator++()
Definition: hopscotch_hash.h:564
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::neighborhood_bitmap
typename hopscotch_bucket::neighborhood_bitmap neighborhood_bitmap
Definition: hopscotch_hash.h:460
tsl::detail_hopscotch_hash::hopscotch_bucket_hash< true >::set_hash
void set_hash(truncated_hash_type hash) noexcept
Definition: hopscotch_hash.h:191
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< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::const_pointer
const value_type * const_pointer
Definition: hopscotch_hash.h:453
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< Key, KeySelect, void, 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:464
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::load_factor
float load_factor() const
Definition: hopscotch_hash.h:1138
tsl::detail_hopscotch_hash::hopscotch_hash::overflow_size
size_type overflow_size() const noexcept
Definition: hopscotch_hash.h:1191
tsl::detail_hopscotch_hash::hopscotch_hash::at
const U::value_type & at(const K &key) const
Definition: hopscotch_hash.h:1023
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::key
const hopscotch_hash::key_type & key() const
Definition: hopscotch_hash.h:524
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:859
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:1512
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::rehash
void rehash(size_type count_)
Definition: hopscotch_hash.h:1156
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::overflow_container_type
overflow_container_type overflow_container_type
Definition: hopscotch_hash.h:466
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator
Definition: hopscotch_hash.h:441
tsl::detail_hopscotch_hash::hopscotch_bucket::m_neighborhood_infos
neighborhood_bitmap m_neighborhood_infos
Definition: hopscotch_hash.h:406
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_hash::truncated_bucket_hash
truncated_hash_type truncated_bucket_hash() const noexcept
Definition: hopscotch_hash.h:170
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::is_power_of_two_policy
Definition: hopscotch_hash.h:88
tsl::detail_hopscotch_hash::hopscotch_hash::operator=
hopscotch_hash & operator=(hopscotch_hash &&other)
Definition: hopscotch_hash.h:724
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::max_size
size_type max_size() const noexcept
Definition: hopscotch_hash.h:778
tsl::detail_hopscotch_hash::hopscotch_hash::operator[]
U::value_type & operator[](K &&key)
Definition: hopscotch_hash.h:1046
tsl::detail_hopscotch_hash::hopscotch_hash::clear
void clear() noexcept
Definition: hopscotch_hash.h:783
tsl::detail_hopscotch_hash::hopscotch_hash::cend
const_iterator cend() const noexcept
Definition: hopscotch_hash.h:766
tsl::detail_hopscotch_hash::hopscotch_bucket::m_value
storage m_value
Definition: hopscotch_hash.h:407
tsl::detail_hopscotch_hash::hopscotch_hash::find
const_iterator find(const K &key, std::size_t hash) const
Definition: hopscotch_hash.h:1083
tsl::detail_hopscotch_hash::hopscotch_hash::erase
size_type erase(const K &key)
Definition: hopscotch_hash.h:961
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_hash
hopscotch_hash(size_type bucket_count, const Hash &hash, const KeyEqual &equal, const Allocator &alloc, float max_load_factor)
Definition: hopscotch_hash.h:606
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::hopscotch_hash::hopscotch_iterator::reference
value_type & reference
Definition: hopscotch_hash.h:512
tsl::detail_hopscotch_hash::hopscotch_hash::find_impl
iterator find_impl(const K &key, std::size_t hash, hopscotch_bucket *bucket_for_hash)
Definition: hopscotch_hash.h:1631
tsl::detail_hopscotch_hash::hopscotch_hash::get_allocator
allocator_type get_allocator() const
Definition: hopscotch_hash.h:732
tsl::detail_hopscotch_hash::hopscotch_hash::new_hopscotch_hash
hopscotch_hash new_hopscotch_hash(size_type bucket_count)
Definition: hopscotch_hash.h:1739
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, 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:476
tsl::detail_hopscotch_hash::hopscotch_hash::find_in_buckets
const hopscotch_bucket * find_in_buckets(const K &key, std::size_t hash, const hopscotch_bucket *bucket_for_hash) const
Definition: hopscotch_hash.h:1676
tsl::detail_hopscotch_hash::hopscotch_hash::bucket_for_hash
std::size_t bucket_for_hash(std::size_t hash) const
Definition: hopscotch_hash.h:1208
tsl::detail_hopscotch_hash::hopscotch_hash::erase
iterator erase(iterator pos)
Definition: hopscotch_hash.h:928
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:1450
tsl::detail_hopscotch_hash::hopscotch_hash::hopscotch_iterator::hopscotch_iterator
hopscotch_iterator(const hopscotch_iterator< false > &other) noexcept
Definition: hopscotch_hash.h:517
tsl::detail_hopscotch_hash::hopscotch_hash::operator=
hopscotch_hash & operator=(const hopscotch_hash &other)
Definition: hopscotch_hash.h:704
tsl::detail_hopscotch_hash::hopscotch_hash::insert
iterator insert(const_iterator hint, P &&value)
Definition: hopscotch_hash.h:815
tsl::detail_hopscotch_hash::hopscotch_hash< Key, KeySelect, void, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::pointer
value_type * pointer
Definition: hopscotch_hash.h:452
tsl::detail_hopscotch_hash::hopscotch_hash::begin
const_iterator begin() const noexcept
Definition: hopscotch_hash.h:747