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