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_ORDERED_HASH_H
25#define TSL_ORDERED_HASH_H
26
27
28#include <algorithm>
29#include <cassert>
30#include <climits>
31#include <cmath>
32#include <cstddef>
33#include <cstdint>
34#include <functional>
35#include <iterator>
36#include <limits>
37#include <memory>
38#include <stdexcept>
39#include <tuple>
40#include <type_traits>
41#include <utility>
42#include <vector>
43
44
45/**
46 * Macros for compatibility with GCC 4.8
47 */
48#ifndef TSL_NO_CONTAINER_ERASE_CONST_ITERATOR
49 #if (defined(__GNUC__) && (__GNUC__ == 4) && (__GNUC_MINOR__ < 9))
50 #define TSL_NO_CONTAINER_ERASE_CONST_ITERATOR
51 #endif
52#endif
53
54#ifndef TSL_NO_CONTAINER_EMPLACE_CONST_ITERATOR
55 #if (defined(__GNUC__) && (__GNUC__ == 4) && (__GNUC_MINOR__ < 9))
56 #define TSL_NO_CONTAINER_EMPLACE_CONST_ITERATOR
57 #endif
58#endif
59
60
61/*
62 * Only activate tsl_assert if TSL_DEBUG is defined.
63 * This way we avoid the performance hit when NDEBUG is not defined with assert as tsl_assert is used a lot
64 * (people usually compile with "-O3" and not "-O3 -DNDEBUG").
65 */
66#ifndef tsl_assert
67 #ifdef TSL_DEBUG
68 #define tsl_assert(expr) assert(expr)
69 #else
70 #define tsl_assert(expr) (static_cast<void>(0))
71 #endif
72#endif
73
74
75namespace tsl {
76
77namespace detail_ordered_hash {
78
79template<typename T>
80struct make_void {
81 using type = void;
82};
83
84template<typename T, typename = void>
85struct has_is_transparent: std::false_type {
86};
87
88template<typename T>
89struct has_is_transparent<T, typename make_void<typename T::is_transparent>::type>: std::true_type {
90};
91
92
93template<typename T, typename = void>
94struct is_vector: std::false_type {
95};
96
97template<typename T>
98struct is_vector<T, typename std::enable_if<
99 std::is_same<T, std::vector<typename T::value_type, typename T::allocator_type>>::value
100 >::type>: std::true_type {
101};
102
103
104/**
105 * Each bucket entry stores a 32-bits index which is the index in m_values corresponding to the bucket's value
106 * and a 32 bits hash (truncated if the original was 64-bits) corresponding to the hash of the value.
107 *
108 * The 32-bit index limits the size of the map to 2^32 - 1 elements (-1 due to a reserved value used to mark a
109 * bucket as empty).
110 */
111class bucket_entry {
112public:
113 using index_type = std::uint_least32_t;
114 using truncated_hash_type = std::uint_least32_t;
115
116
117 bucket_entry() noexcept: m_index(EMPTY_MARKER_INDEX), m_hash(0) {
118 }
119
120 bool empty() const noexcept {
121 return m_index == EMPTY_MARKER_INDEX;
122 }
123
124 void clear() noexcept {
125 m_index = EMPTY_MARKER_INDEX;
126 }
127
128 index_type index() const noexcept {
129 tsl_assert(!empty());
130 return m_index;
131 }
132
133 index_type& index_ref() noexcept {
134 tsl_assert(!empty());
135 return m_index;
136 }
137
138 void set_index(index_type index) noexcept {
139 tsl_assert(index <= max_size());
140
141 m_index = index;
142 }
143
144 truncated_hash_type truncated_hash() const noexcept {
145 tsl_assert(!empty());
146 return m_hash;
147 }
148
149 truncated_hash_type& truncated_hash_ref() noexcept {
150 tsl_assert(!empty());
151 return m_hash;
152 }
153
154 void set_hash(std::size_t hash) noexcept {
155 m_hash = truncate_hash(hash);
156 }
157
158
159
160 static truncated_hash_type truncate_hash(std::size_t hash) noexcept {
161 return truncated_hash_type(hash);
162 }
163
164 static std::size_t max_size() noexcept {
165 return std::numeric_limits<index_type>::max() - NB_RESERVED_INDEXES;
166 }
167
168private:
169 static const index_type EMPTY_MARKER_INDEX = std::numeric_limits<index_type>::max();
170 static const std::size_t NB_RESERVED_INDEXES = 1;
171
172 index_type m_index;
173 truncated_hash_type m_hash;
174};
175
176
177
178/**
179 * Internal common class used by ordered_map and ordered_set.
180 *
181 * ValueType is what will be stored by ordered_hash (usually std::pair<Key, T> for map and Key for set).
182 *
183 * KeySelect should be a FunctionObject which takes a ValueType in parameter and return a reference to the key.
184 *
185 * ValueSelect should be a FunctionObject which takes a ValueType in parameter and return a reference to the value.
186 * ValueSelect should be void if there is no value (in set for example).
187 *
188 * ValueTypeContainer is the container which will be used to store ValueType values.
189 * Usually a std::deque<ValueType, Allocator> or std::vector<ValueType, Allocator>.
190 *
191 *
192 *
193 * The orderd_hash structure is a hash table which preserves the order of insertion of the elements.
194 * To do so, it stores the values in the ValueTypeContainer (m_values) using emplace_back at each
195 * insertion of a new element. Another structure (m_buckets of type std::vector<bucket_entry>) will
196 * serve as buckets array for the hash table part. Each bucket stores an index which corresponds to
197 * the index in m_values where the bucket's value is and the (truncated) hash of this value. An index
198 * is used instead of a pointer to the value to reduce the size of each bucket entry.
199 *
200 * To resolve collisions in the buckets array, the structures use robin hood linear probing with
201 * backward shift deletion.
202 */
203template<class ValueType,
204 class KeySelect,
205 class ValueSelect,
206 class Hash,
207 class KeyEqual,
208 class Allocator,
209 class ValueTypeContainer>
210class ordered_hash: private Hash, private KeyEqual {
211private:
212 template<typename U>
213 using has_mapped_type = typename std::integral_constant<bool, !std::is_same<U, void>::value>;
214
215 static_assert(std::is_same<typename ValueTypeContainer::value_type, ValueType>::value,
216 "ValueTypeContainer::value_type != ValueType.");
217 static_assert(std::is_same<typename ValueTypeContainer::allocator_type, Allocator>::value,
218 "ValueTypeContainer::allocator_type != Allocator.");
219
220
221public:
222 template<bool IsConst>
223 class ordered_iterator;
224
225 using key_type = typename KeySelect::key_type;
226 using value_type = ValueType;
227 using size_type = std::size_t;
228 using difference_type = std::ptrdiff_t;
229 using hasher = Hash;
230 using key_equal = KeyEqual;
231 using allocator_type = Allocator;
232 using reference = value_type&;
233 using const_reference = const value_type&;
234 using pointer = value_type*;
235 using const_pointer = const value_type*;
236 using iterator = ordered_iterator<false>;
237 using const_iterator = ordered_iterator<true>;
238 using reverse_iterator = std::reverse_iterator<iterator>;
239 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
240
241 using values_container_type = ValueTypeContainer;
242
243public:
244 template<bool IsConst>
245 class ordered_iterator {
246 friend class ordered_hash;
247
248 private:
249 using iterator = typename std::conditional<IsConst,
250 typename values_container_type::const_iterator,
251 typename values_container_type::iterator>::type;
252
253
254 ordered_iterator(iterator it) noexcept: m_iterator(it) {
255 }
256
257 public:
258 using iterator_category = std::random_access_iterator_tag;
259 using value_type = const typename ordered_hash::value_type;
260 using difference_type = typename iterator::difference_type;
261 using reference = value_type&;
262 using pointer = value_type*;
263
264
265 ordered_iterator() noexcept {
266 }
267
268 ordered_iterator(const ordered_iterator<false>& other) noexcept: m_iterator(other.m_iterator) {
269 }
270
271 const typename ordered_hash::key_type& key() const {
272 return KeySelect()(*m_iterator);
273 }
274
275 template<class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value && IsConst>::type* = nullptr>
276 const typename U::value_type& value() const {
277 return U()(*m_iterator);
278 }
279
280 template<class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value && !IsConst>::type* = nullptr>
281 typename U::value_type& value() {
282 return U()(*m_iterator);
283 }
284
285 reference operator*() const { return *m_iterator; }
286 pointer operator->() const { return m_iterator.operator->(); }
287
288 ordered_iterator& operator++() { ++m_iterator; return *this; }
289 ordered_iterator& operator--() { --m_iterator; return *this; }
290
291 ordered_iterator operator++(int) { ordered_iterator tmp(*this); ++(*this); return tmp; }
292 ordered_iterator operator--(int) { ordered_iterator tmp(*this); --(*this); return tmp; }
293
294 reference operator[](difference_type n) const { return m_iterator[n]; }
295
296 ordered_iterator& operator+=(difference_type n) { m_iterator += n; return *this; }
297 ordered_iterator& operator-=(difference_type n) { m_iterator -= n; return *this; }
298
299 ordered_iterator operator+(difference_type n) { ordered_iterator tmp(*this); tmp += n; return tmp; }
300 ordered_iterator operator-(difference_type n) { ordered_iterator tmp(*this); tmp -= n; return tmp; }
301
302 friend bool operator==(const ordered_iterator& lhs, const ordered_iterator& rhs) {
303 return lhs.m_iterator == rhs.m_iterator;
304 }
305
306 friend bool operator!=(const ordered_iterator& lhs, const ordered_iterator& rhs) {
307 return lhs.m_iterator != rhs.m_iterator;
308 }
309
310 friend bool operator<(const ordered_iterator& lhs, const ordered_iterator& rhs) {
311 return lhs.m_iterator < rhs.m_iterator;
312 }
313
314 friend bool operator>(const ordered_iterator& lhs, const ordered_iterator& rhs) {
315 return lhs.m_iterator > rhs.m_iterator;
316 }
317
318 friend bool operator<=(const ordered_iterator& lhs, const ordered_iterator& rhs) {
319 return lhs.m_iterator <= rhs.m_iterator;
320 }
321
322 friend bool operator>=(const ordered_iterator& lhs, const ordered_iterator& rhs) {
323 return lhs.m_iterator >= rhs.m_iterator;
324 }
325
326 friend ordered_iterator operator+(difference_type n, const ordered_iterator& it) {
327 return n + it.m_iterator;
328 }
329
330 friend difference_type operator-(const ordered_iterator& lhs, const ordered_iterator& rhs) {
331 return lhs.m_iterator - rhs.m_iterator;
332 }
333
334 private:
335 iterator m_iterator;
336 };
337
338
339private:
340 using buckets_container_allocator = typename
341 std::allocator_traits<allocator_type>::template rebind_alloc<bucket_entry>;
342
343 using buckets_container_type = std::vector<bucket_entry, buckets_container_allocator>;
344
345
346 using truncated_hash_type = typename bucket_entry::truncated_hash_type;
347 using index_type = typename bucket_entry::index_type;
348
349public:
350 ordered_hash(size_type bucket_count,
351 const Hash& hash,
352 const KeyEqual& equal,
353 const Allocator& alloc,
354 float max_load_factor): Hash(hash), KeyEqual(equal), m_buckets(alloc),
355 m_values(alloc), m_grow_on_next_insert(false)
356 {
357 bucket_count = round_up_to_power_of_two(bucket_count);
358 if(bucket_count > max_bucket_count()) {
359 throw std::length_error("The map exceeds its maxmimum size.");
360 }
361 tsl_assert(bucket_count > 0);
362
363 m_buckets.resize(bucket_count);
364 m_mask = bucket_count - 1;
365
366 this->max_load_factor(max_load_factor);
367 }
368
369 allocator_type get_allocator() const {
370 return m_values.get_allocator();
371 }
372
373
374 /*
375 * Iterators
376 */
377 iterator begin() noexcept {
378 return iterator(m_values.begin());
379 }
380
381 const_iterator begin() const noexcept {
382 return cbegin();
383 }
384
385 const_iterator cbegin() const noexcept {
386 return const_iterator(m_values.cbegin());
387 }
388
389 iterator end() noexcept {
390 return iterator(m_values.end());
391 }
392
393 const_iterator end() const noexcept {
394 return cend();
395 }
396
397 const_iterator cend() const noexcept {
398 return const_iterator(m_values.cend());
399 }
400
401
402 reverse_iterator rbegin() noexcept {
403 return reverse_iterator(m_values.end());
404 }
405
406 const_reverse_iterator rbegin() const noexcept {
407 return rcbegin();
408 }
409
410 const_reverse_iterator rcbegin() const noexcept {
411 return const_reverse_iterator(m_values.cend());
412 }
413
414 reverse_iterator rend() noexcept {
415 return reverse_iterator(m_values.begin());
416 }
417
418 const_reverse_iterator rend() const noexcept {
419 return rcend();
420 }
421
422 const_reverse_iterator rcend() const noexcept {
423 return const_reverse_iterator(m_values.cbegin());
424 }
425
426
427 /*
428 * Capacity
429 */
430 bool empty() const noexcept {
431 return m_values.empty();
432 }
433
434 size_type size() const noexcept {
435 return m_values.size();
436 }
437
438 size_type max_size() const noexcept {
439 return std::min(bucket_entry::max_size(), m_values.max_size());
440 }
441
442
443 /*
444 * Modifiers
445 */
446 void clear() noexcept {
447 for(auto& bucket: m_buckets) {
448 bucket.clear();
449 }
450
451 m_values.clear();
452 m_grow_on_next_insert = false;
453 }
454
455 template<typename P>
456 std::pair<iterator, bool> insert(P&& value) {
457 return insert_impl(KeySelect()(value), std::forward<P>(value));
458 }
459
460 template<typename P>
461 iterator insert(const_iterator hint, P&& value) {
462 if(hint != cend() && compare_keys(KeySelect()(*hint), KeySelect()(value))) {
463 return mutable_iterator(hint);
464 }
465
466 return insert(std::forward<P>(value)).first;
467 }
468
469 template<class InputIt>
470 void insert(InputIt first, InputIt last) {
471 if(std::is_base_of<std::forward_iterator_tag,
472 typename std::iterator_traits<InputIt>::iterator_category>::value)
473 {
474 const auto nb_elements_insert = std::distance(first, last);
475 const size_type nb_free_buckets = m_load_threshold - size();
476 tsl_assert(m_load_threshold >= size());
477
478 if(nb_elements_insert > 0 && nb_free_buckets < size_type(nb_elements_insert)) {
479 reserve(size() + size_type(nb_elements_insert));
480 }
481 }
482
483 for(; first != last; ++first) {
484 insert(*first);
485 }
486 }
487
488
489
490 template<class K, class M>
491 std::pair<iterator, bool> insert_or_assign(K&& key, M&& value) {
492 auto it = try_emplace(std::forward<K>(key), std::forward<M>(value));
493 if(!it.second) {
494 it.first.value() = std::forward<M>(value);
495 }
496
497 return it;
498 }
499
500 template<class K, class M>
501 iterator insert_or_assign(const_iterator hint, K&& key, M&& obj) {
502 if(hint != cend() && compare_keys(KeySelect()(*hint), key)) {
503 auto it = mutable_iterator(hint);
504 it.value() = std::forward<M>(obj);
505
506 return it;
507 }
508
509 return insert_or_assign(std::forward<K>(key), std::forward<M>(obj)).first;
510 }
511
512
513
514 template<class... Args>
515 std::pair<iterator, bool> emplace(Args&&... args) {
516 return insert(value_type(std::forward<Args>(args)...));
517 }
518
519 template<class... Args>
520 iterator emplace_hint(const_iterator hint, Args&&... args) {
521 return insert(hint, value_type(std::forward<Args>(args)...));
522 }
523
524
525
526 template<class K, class... Args>
527 std::pair<iterator, bool> try_emplace(K&& key, Args&&... value_args) {
528 return insert_impl(key, std::piecewise_construct,
529 std::forward_as_tuple(std::forward<K>(key)),
530 std::forward_as_tuple(std::forward<Args>(value_args)...));
531 }
532
533 template<class K, class... Args>
534 iterator try_emplace(const_iterator hint, K&& key, Args&&... args) {
535 if(hint != cend() && compare_keys(KeySelect()(*hint), key)) {
536 return mutable_iterator(hint);
537 }
538
539 return try_emplace(std::forward<K>(key), std::forward<Args>(args)...).first;
540 }
541
542
543
544 /**
545 * Here to avoid `template<class K> size_type erase(const K& key)` being used when
546 * we use a iterator instead of a const_iterator.
547 */
548 iterator erase(iterator pos) {
549 return erase(const_iterator(pos));
550 }
551
552 iterator erase(const_iterator pos) {
553 tsl_assert(pos != cend());
554
555 const std::size_t index_erase = iterator_to_index(pos);
556
557 auto it_bucket = find_key(pos.key(), hash_key(pos.key()));
558 tsl_assert(it_bucket != m_buckets.end());
559
560 erase_value_from_bucket(it_bucket);
561
562 /*
563 * One element was removed from m_values, due to the left shift the next element
564 * is now at the position of the previous element (or end if none).
565 */
566 return begin() + index_erase;
567 }
568
569 iterator erase(const_iterator first, const_iterator last) {
570 if(first == last) {
571 return mutable_iterator(first);
572 }
573
574 tsl_assert(std::distance(first, last) > 0);
575 const std::size_t start_index = iterator_to_index(first);
576 const std::size_t nb_values = std::size_t(std::distance(first, last));
577 const std::size_t end_index = start_index + nb_values;
578
579 // Delete all values
580#ifdef TSL_NO_CONTAINER_ERASE_CONST_ITERATOR
581 auto next_it = m_values.erase(mutable_iterator(first).m_iterator, mutable_iterator(last).m_iterator);
582#else
583 auto next_it = m_values.erase(first.m_iterator, last.m_iterator);
584#endif
585
586 /*
587 * Mark the buckets corresponding to the values as empty and do a backward shift.
588 *
589 * Also, the erase operation on m_values has shifted all the values on the right of last.m_iterator.
590 * Adapt the indexes for these values.
591 */
592 std::size_t ibucket = 0;
593 while(ibucket < m_buckets.size()) {
594 if(m_buckets[ibucket].empty()) {
595 ibucket++;
596 }
597 else if(m_buckets[ibucket].index() >= start_index && m_buckets[ibucket].index() < end_index) {
598 m_buckets[ibucket].clear();
599 backward_shift(ibucket);
600 // Don't increment ibucket, backward_shift may have replaced current bucket.
601 }
602 else if(m_buckets[ibucket].index() >= end_index) {
603 m_buckets[ibucket].set_index(index_type(m_buckets[ibucket].index() - nb_values));
604 ibucket++;
605 }
606 else {
607 ibucket++;
608 }
609 }
610
611 return iterator(next_it);
612 }
613
614
615 template<class K>
616 size_type erase(const K& key) {
617 return erase(key, hash_key(key));
618 }
619
620 template<class K>
621 size_type erase(const K& key, std::size_t hash) {
622 return erase_impl(key, hash);
623 }
624
625 void swap(ordered_hash& other) {
626 using std::swap;
627
628 swap(static_cast<Hash&>(*this), static_cast<Hash&>(other));
629 swap(static_cast<KeyEqual&>(*this), static_cast<KeyEqual&>(other));
630 swap(m_buckets, other.m_buckets);
631 swap(m_mask, other.m_mask);
632 swap(m_values, other.m_values);
633 swap(m_grow_on_next_insert, other.m_grow_on_next_insert);
634 swap(m_max_load_factor, other.m_max_load_factor);
635 swap(m_load_threshold, other.m_load_threshold);
636 }
637
638
639
640
641 /*
642 * Lookup
643 */
644 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
645 typename U::value_type& at(const K& key) {
646 return at(key, hash_key(key));
647 }
648
649 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
650 typename U::value_type& at(const K& key, std::size_t hash) {
651 return const_cast<typename U::value_type&>(static_cast<const ordered_hash*>(this)->at(key, hash));
652 }
653
654 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
655 const typename U::value_type& at(const K& key) const {
656 return at(key, hash_key(key));
657 }
658
659 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
660 const typename U::value_type& at(const K& key, std::size_t hash) const {
661 auto it = find(key, hash);
662 if(it != end()) {
663 return it.value();
664 }
665 else {
666 throw std::out_of_range("Couldn't find the key.");
667 }
668 }
669
670
671 template<class K, class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
672 typename U::value_type& operator[](K&& key) {
673 return try_emplace(std::forward<K>(key)).first.value();
674 }
675
676
677 template<class K>
678 size_type count(const K& key) const {
679 return count(key, hash_key(key));
680 }
681
682 template<class K>
683 size_type count(const K& key, std::size_t hash) const {
684 if(find(key, hash) == cend()) {
685 return 0;
686 }
687 else {
688 return 1;
689 }
690 }
691
692 template<class K>
693 iterator find(const K& key) {
694 return find(key, hash_key(key));
695 }
696
697 template<class K>
698 iterator find(const K& key, std::size_t hash) {
699 auto it_bucket = find_key(key, hash);
700 return (it_bucket != m_buckets.end())?iterator(m_values.begin() + it_bucket->index()):end();
701 }
702
703 template<class K>
704 const_iterator find(const K& key) const {
705 return find(key, hash_key(key));
706 }
707
708 template<class K>
709 const_iterator find(const K& key, std::size_t hash) const {
710 auto it_bucket = find_key(key, hash);
711 return (it_bucket != m_buckets.cend())?const_iterator(m_values.begin() + it_bucket->index()):end();
712 }
713
714
715 template<class K>
716 std::pair<iterator, iterator> equal_range(const K& key) {
717 return equal_range(key, hash_key(key));
718 }
719
720 template<class K>
721 std::pair<iterator, iterator> equal_range(const K& key, std::size_t hash) {
722 iterator it = find(key, hash);
723 return std::make_pair(it, (it == end())?it:std::next(it));
724 }
725
726 template<class K>
727 std::pair<const_iterator, const_iterator> equal_range(const K& key) const {
728 return equal_range(key, hash_key(key));
729 }
730
731 template<class K>
732 std::pair<const_iterator, const_iterator> equal_range(const K& key, std::size_t hash) const {
733 const_iterator it = find(key, hash);
734 return std::make_pair(it, (it == cend())?it:std::next(it));
735 }
736
737
738 /*
739 * Bucket interface
740 */
741 size_type bucket_count() const {
742 return m_buckets.size();
743 }
744
745 size_type max_bucket_count() const {
746 return m_buckets.max_size();
747 }
748
749 /*
750 * Hash policy
751 */
752 float load_factor() const {
753 return float(size())/float(bucket_count());
754 }
755
756 float max_load_factor() const {
757 return m_max_load_factor;
758 }
759
760 void max_load_factor(float ml) {
761 m_max_load_factor = std::max(0.1f, std::min(ml, 0.95f));
762 m_load_threshold = size_type(float(bucket_count())*m_max_load_factor);
763 }
764
765 void rehash(size_type count) {
766 count = std::max(count, size_type(std::ceil(float(size())/max_load_factor())));
767 rehash_impl(count);
768 }
769
770 void reserve(size_type count) {
771 reserve_space_for_values(count);
772
773 count = size_type(std::ceil(float(count)/max_load_factor()));
774 rehash(count);
775 }
776
777
778 /*
779 * Observers
780 */
781 hasher hash_function() const {
782 return static_cast<const Hash&>(*this);
783 }
784
785 key_equal key_eq() const {
786 return static_cast<const KeyEqual&>(*this);
787 }
788
789
790 /*
791 * Other
792 */
793 iterator mutable_iterator(const_iterator pos) {
794 return iterator(m_values.begin() + iterator_to_index(pos));
795 }
796
797 iterator nth(size_type index) {
798 return iterator(m_values.begin() + index);
799 }
800
801 const_iterator nth(size_type index) const {
802 return const_iterator(m_values.cbegin() + index);
803 }
804
805 const_reference front() const {
806 return m_values.front();
807 }
808
809 const_reference back() const {
810 return m_values.back();
811 }
812
813 const values_container_type& values_container() const noexcept {
814 return m_values;
815 }
816
817 template<class U = values_container_type, typename std::enable_if<is_vector<U>::value>::type* = nullptr>
818 const typename values_container_type::value_type* data() const noexcept {
819 return m_values.data();
820 }
821
822 template<class U = values_container_type, typename std::enable_if<is_vector<U>::value>::type* = nullptr>
823 size_type capacity() const noexcept {
824 return m_values.capacity();
825 }
826
827 void shrink_to_fit() {
828 m_values.shrink_to_fit();
829 }
830
831
832 template<typename P>
833 std::pair<iterator, bool> insert_at_position(const_iterator pos, P&& value) {
834 return insert_at_position_impl(pos.m_iterator, KeySelect()(value), std::forward<P>(value));
835 }
836
837 template<class... Args>
838 std::pair<iterator, bool> emplace_at_position(const_iterator pos, Args&&... args) {
839 return insert_at_position(pos, value_type(std::forward<Args>(args)...));
840 }
841
842 template<class K, class... Args>
843 std::pair<iterator, bool> try_emplace_at_position(const_iterator pos, K&& key, Args&&... value_args) {
844 return insert_at_position_impl(pos.m_iterator, key,
845 std::piecewise_construct,
846 std::forward_as_tuple(std::forward<K>(key)),
847 std::forward_as_tuple(std::forward<Args>(value_args)...));
848 }
849
850
851 void pop_back() {
852 tsl_assert(!empty());
853 erase(std::prev(end()));
854 }
855
856
857 /**
858 * Here to avoid `template<class K> size_type unordered_erase(const K& key)` being used when
859 * we use a iterator instead of a const_iterator.
860 */
861 iterator unordered_erase(iterator pos) {
862 return unordered_erase(const_iterator(pos));
863 }
864
865 iterator unordered_erase(const_iterator pos) {
866 const std::size_t index_erase = iterator_to_index(pos);
867 unordered_erase(pos.key());
868
869 /*
870 * One element was deleted, index_erase now points to the next element as the elements after
871 * the deleted value were shifted to the left in m_values (will be end() if we deleted the last element).
872 */
873 return begin() + index_erase;
874 }
875
876 template<class K>
877 size_type unordered_erase(const K& key) {
878 return unordered_erase(key, hash_key(key));
879 }
880
881 template<class K>
882 size_type unordered_erase(const K& key, std::size_t hash) {
883 auto it_bucket_key = find_key(key, hash);
884 if(it_bucket_key == m_buckets.end()) {
885 return 0;
886 }
887
888 /**
889 * If we are not erasing the last element in m_values, we swap
890 * the element we are erasing with the last element. We then would
891 * just have to do a pop_back() in m_values.
892 */
893 if(!compare_keys(key, KeySelect()(back()))) {
894 auto it_bucket_last_elem = find_key(KeySelect()(back()), hash_key(KeySelect()(back())));
895 tsl_assert(it_bucket_last_elem != m_buckets.end());
896 tsl_assert(it_bucket_last_elem->index() == m_values.size() - 1);
897
898 using std::swap;
899 swap(m_values[it_bucket_key->index()], m_values[it_bucket_last_elem->index()]);
900 swap(it_bucket_key->index_ref(), it_bucket_last_elem->index_ref());
901 }
902
903 erase_value_from_bucket(it_bucket_key);
904
905 return 1;
906 }
907
908 friend bool operator==(const ordered_hash& lhs, const ordered_hash& rhs) {
909 return lhs.m_values == rhs.m_values;
910 }
911
912 friend bool operator!=(const ordered_hash& lhs, const ordered_hash& rhs) {
913 return lhs.m_values != rhs.m_values;
914 }
915
916 friend bool operator<(const ordered_hash& lhs, const ordered_hash& rhs) {
917 return lhs.m_values < rhs.m_values;
918 }
919
920 friend bool operator<=(const ordered_hash& lhs, const ordered_hash& rhs) {
921 return lhs.m_values <= rhs.m_values;
922 }
923
924 friend bool operator>(const ordered_hash& lhs, const ordered_hash& rhs) {
925 return lhs.m_values > rhs.m_values;
926 }
927
928 friend bool operator>=(const ordered_hash& lhs, const ordered_hash& rhs) {
929 return lhs.m_values >= rhs.m_values;
930 }
931
932
933private:
934 template<class K>
935 std::size_t hash_key(const K& key) const {
936 return Hash::operator()(key);
937 }
938
939 template<class K1, class K2>
940 bool compare_keys(const K1& key1, const K2& key2) const {
941 return KeyEqual::operator()(key1, key2);
942 }
943
944 template<class K>
945 typename buckets_container_type::iterator find_key(const K& key, std::size_t hash) {
946 auto it = static_cast<const ordered_hash*>(this)->find_key(key, hash);
947 return m_buckets.begin() + std::distance(m_buckets.cbegin(), it);
948 }
949
950 /**
951 * Return bucket which has the key 'key' or m_buckets.end() if none.
952 *
953 * From the bucket_for_hash, search for the value until we either find an empty bucket
954 * or a bucket which has a value with a distance from its ideal bucket longer
955 * than the probe length for the value we are looking for.
956 */
957 template<class K>
958 typename buckets_container_type::const_iterator find_key(const K& key, std::size_t hash) const {
959 for(std::size_t ibucket = bucket_for_hash(hash), dist_from_ideal_bucket = 0; ;
960 ibucket = next_bucket(ibucket), dist_from_ideal_bucket++)
961 {
962 if(m_buckets[ibucket].empty()) {
963 return m_buckets.end();
964 }
965 else if(m_buckets[ibucket].truncated_hash() == bucket_entry::truncate_hash(hash) &&
966 compare_keys(key, KeySelect()(m_values[m_buckets[ibucket].index()])))
967 {
968 return m_buckets.begin() + ibucket;
969 }
970 else if(dist_from_ideal_bucket > distance_from_ideal_bucket(ibucket)) {
971 return m_buckets.end();
972 }
973 }
974 }
975
976 void rehash_impl(size_type bucket_count) {
977 bucket_count = round_up_to_power_of_two(bucket_count);
978 tsl_assert(bucket_count > 0);
979
980 if(bucket_count == this->bucket_count()) {
981 return;
982 }
983
984 if(bucket_count > max_bucket_count()) {
985 throw std::length_error("The map exceeds its maxmimum size.");
986 }
987
988
989 buckets_container_type old_buckets(bucket_count);
990 m_buckets.swap(old_buckets);
991 // Everything should be noexcept from here.
992
993 m_mask = bucket_count - 1;
994 this->max_load_factor(m_max_load_factor);
995 m_grow_on_next_insert = false;
996
997
998
999 for(const bucket_entry& old_bucket: old_buckets) {
1000 if(old_bucket.empty()) {
1001 continue;
1002 }
1003
1004 truncated_hash_type insert_hash = old_bucket.truncated_hash();
1005 index_type insert_index = old_bucket.index();
1006
1007 for(std::size_t ibucket = bucket_for_hash(insert_hash), dist_from_ideal_bucket = 0; ;
1008 ibucket = next_bucket(ibucket), dist_from_ideal_bucket++)
1009 {
1010 if(m_buckets[ibucket].empty()) {
1011 m_buckets[ibucket].set_index(insert_index);
1012 m_buckets[ibucket].set_hash(insert_hash);
1013 break;
1014 }
1015
1016 const std::size_t distance = distance_from_ideal_bucket(ibucket);
1017 if(dist_from_ideal_bucket > distance) {
1018 std::swap(insert_index, m_buckets[ibucket].index_ref());
1019 std::swap(insert_hash, m_buckets[ibucket].truncated_hash_ref());
1020 dist_from_ideal_bucket = distance;
1021 }
1022 }
1023 }
1024 }
1025
1026 template<class T = values_container_type, typename std::enable_if<is_vector<T>::value>::type* = nullptr>
1027 void reserve_space_for_values(size_type count) {
1028 m_values.reserve(count);
1029 }
1030
1031 template<class T = values_container_type, typename std::enable_if<!is_vector<T>::value>::type* = nullptr>
1032 void reserve_space_for_values(size_type /*count*/) {
1033 }
1034
1035 /**
1036 * Swap the empty bucket with the values on its right until we cross another empty bucket
1037 * or if the other bucket has a distance_from_ideal_bucket == 0.
1038 */
1039 void backward_shift(std::size_t empty_ibucket) noexcept {
1040 tsl_assert(m_buckets[empty_ibucket].empty());
1041
1042 std::size_t previous_ibucket = empty_ibucket;
1043 for(std::size_t current_ibucket = next_bucket(previous_ibucket);
1044 !m_buckets[current_ibucket].empty() && distance_from_ideal_bucket(current_ibucket) > 0;
1045 previous_ibucket = current_ibucket, current_ibucket = next_bucket(current_ibucket))
1046 {
1047 std::swap(m_buckets[current_ibucket], m_buckets[previous_ibucket]);
1048 }
1049 }
1050
1051 void erase_value_from_bucket(typename buckets_container_type::iterator it_bucket) {
1052 tsl_assert(it_bucket != m_buckets.end() && !it_bucket->empty());
1053
1054 m_values.erase(m_values.begin() + it_bucket->index());
1055
1056 /*
1057 * m_values.erase shifted all the values on the right of the erased value,
1058 * shift the indexes by 1 in the buckets array for these values.
1059 */
1060 if(it_bucket->index() != m_values.size()) {
1061 shift_indexes_in_buckets(it_bucket->index(), short(1));
1062 }
1063
1064 // Mark the bucket as empty and do a backward shift of the values on the right
1065 it_bucket->clear();
1066 backward_shift(std::size_t(std::distance(m_buckets.begin(), it_bucket)));
1067 }
1068
1069 /**
1070 * Go through each value from [from_ivalue, m_values.size()) in m_values and for each
1071 * bucket corresponding to the value, shift the indexes to the left by delta.
1072 */
1073 void shift_indexes_in_buckets(index_type from_ivalue, short delta) noexcept {
1074 static_assert(std::is_unsigned<index_type>::value && sizeof(index_type) >= sizeof(short),
1075 "index_type should be unsigned and sizeof(index_type) >= sizeof(short)");
1076
1077 for(std::size_t ivalue = from_ivalue; ivalue < m_values.size(); ivalue++) {
1078 std::size_t ibucket = bucket_for_hash(hash_key(KeySelect()(m_values[ivalue])));
1079
1080 // Modulo arithmetic, we should be alright for index_type(ivalue + delta). TODO further checks
1081 while(m_buckets[ibucket].index() != index_type(ivalue + delta)) {
1082 ibucket = next_bucket(ibucket);
1083 }
1084
1085 m_buckets[ibucket].set_index(index_type(m_buckets[ibucket].index() - delta));
1086 }
1087 }
1088
1089 template<class K>
1090 size_type erase_impl(const K& key, std::size_t hash) {
1091 auto it_bucket = find_key(key, hash);
1092 if(it_bucket != m_buckets.end()) {
1093 erase_value_from_bucket(it_bucket);
1094
1095 return 1;
1096 }
1097 else {
1098 return 0;
1099 }
1100 }
1101
1102 template<class K, class... Args>
1103 std::pair<iterator, bool> insert_impl(const K& key, Args&&... value_type_args) {
1104 return insert_at_position_impl(m_values.cend(), key, std::forward<Args>(value_type_args)...);
1105 }
1106
1107 /**
1108 * Insert the element before insert_position.
1109 */
1110 template<class K, class... Args>
1111 std::pair<iterator, bool> insert_at_position_impl(typename values_container_type::const_iterator insert_position,
1112 const K& key, Args&&... value_type_args)
1113 {
1114 const std::size_t hash = hash_key(key);
1115
1116 std::size_t ibucket = bucket_for_hash(hash);
1117 std::size_t dist_from_ideal_bucket = 0;
1118
1119 while(!m_buckets[ibucket].empty() && dist_from_ideal_bucket <= distance_from_ideal_bucket(ibucket)) {
1120 if(m_buckets[ibucket].truncated_hash() == bucket_entry::truncate_hash(hash) &&
1121 compare_keys(key, KeySelect()(m_values[m_buckets[ibucket].index()])))
1122 {
1123 return std::make_pair(begin() + m_buckets[ibucket].index(), false);
1124 }
1125
1126 ibucket = next_bucket(ibucket);
1127 dist_from_ideal_bucket++;
1128 }
1129
1130 if(size() >= max_size()) {
1131 throw std::length_error("We reached the maximum size for the hash table.");
1132 }
1133
1134
1135 if(grow_on_high_load()) {
1136 ibucket = bucket_for_hash(hash);
1137 dist_from_ideal_bucket = 0;
1138 }
1139
1140
1141 const index_type index_insert_position = index_type(std::distance(m_values.cbegin(), insert_position));
1142
1143#ifdef TSL_NO_CONTAINER_EMPLACE_CONST_ITERATOR
1144 m_values.emplace(m_values.begin() + std::distance(m_values.cbegin(), insert_position), std::forward<Args>(value_type_args)...);
1145#else
1146 m_values.emplace(insert_position, std::forward<Args>(value_type_args)...);
1147#endif
1148
1149 insert_index(ibucket, dist_from_ideal_bucket,
1150 index_insert_position, bucket_entry::truncate_hash(hash));
1151
1152 /*
1153 * The insertion didn't happend at the end of the m_values container,
1154 * we need to shift the indexes in m_buckets.
1155 */
1156 if(index_insert_position != m_values.size() - 1) {
1157 shift_indexes_in_buckets(index_insert_position + 1, short(-1));
1158 }
1159
1160 return std::make_pair(iterator(m_values.begin() + index_insert_position), true);
1161 }
1162
1163 void insert_index(std::size_t ibucket, std::size_t dist_from_ideal_bucket,
1164 index_type index_insert, truncated_hash_type hash_insert) noexcept
1165 {
1166 while(!m_buckets[ibucket].empty()) {
1167 const std::size_t distance = distance_from_ideal_bucket(ibucket);
1168 if(dist_from_ideal_bucket > distance) {
1169 std::swap(index_insert, m_buckets[ibucket].index_ref());
1170 std::swap(hash_insert, m_buckets[ibucket].truncated_hash_ref());
1171
1172 dist_from_ideal_bucket = distance;
1173 }
1174
1175
1176 ibucket = next_bucket(ibucket);
1177 dist_from_ideal_bucket++;
1178
1179
1180 if(dist_from_ideal_bucket > REHASH_ON_HIGH_NB_PROBES__NPROBES && !m_grow_on_next_insert &&
1181 load_factor() >= REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR)
1182 {
1183 // We don't want to grow the map now as we need this method to be noexcept.
1184 // Do it on next insert.
1185 m_grow_on_next_insert = true;
1186 }
1187 }
1188
1189
1190 m_buckets[ibucket].set_index(index_insert);
1191 m_buckets[ibucket].set_hash(hash_insert);
1192 }
1193
1194 std::size_t distance_from_ideal_bucket(std::size_t ibucket) const noexcept {
1195 const std::size_t ideal_bucket = bucket_for_hash(m_buckets[ibucket].truncated_hash());
1196
1197 if(ibucket >= ideal_bucket) {
1198 return ibucket - ideal_bucket;
1199 }
1200 // If the bucket is smaller than the ideal bucket for the value, there was a wrapping at the end of the
1201 // bucket array due to the modulo.
1202 else {
1203 return (bucket_count() + ibucket) - ideal_bucket;
1204 }
1205 }
1206
1207 std::size_t next_bucket(std::size_t index) const noexcept {
1208 tsl_assert(index < m_buckets.size());
1209
1210 index++;
1211 return (index < m_buckets.size())?index:0;
1212 }
1213
1214 std::size_t bucket_for_hash(std::size_t hash) const noexcept {
1215 return hash & m_mask;
1216 }
1217
1218 std::size_t iterator_to_index(const_iterator it) const noexcept {
1219 const auto dist = std::distance(cbegin(), it);
1220 tsl_assert(dist >= 0);
1221
1222 return std::size_t(dist);
1223 }
1224
1225 /**
1226 * Return true if the map has been rehashed.
1227 */
1228 bool grow_on_high_load() {
1229 if(m_grow_on_next_insert || size() >= m_load_threshold) {
1230 rehash_impl(bucket_count() * 2);
1231 m_grow_on_next_insert = false;
1232
1233 return true;
1234 }
1235 else {
1236 return false;
1237 }
1238 }
1239
1240 static std::size_t round_up_to_power_of_two(std::size_t value) {
1241 if(is_power_of_two(value)) {
1242 return value;
1243 }
1244
1245 if(value == 0) {
1246 return 1;
1247 }
1248
1249 --value;
1250 for(std::size_t i = 1; i < sizeof(std::size_t) * CHAR_BIT; i *= 2) {
1251 value |= value >> i;
1252 }
1253
1254 return value + 1;
1255 }
1256
1257 static constexpr bool is_power_of_two(std::size_t value) {
1258 return value != 0 && (value & (value - 1)) == 0;
1259 }
1260
1261
1262public:
1263 static const size_type DEFAULT_INIT_BUCKETS_SIZE = 16;
1264 static constexpr float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
1265
1266private:
1267 static const size_type REHASH_ON_HIGH_NB_PROBES__NPROBES = 128;
1268 static constexpr float REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR = 0.15f;
1269
1270private:
1271 buckets_container_type m_buckets;
1272 size_type m_mask;
1273
1274 values_container_type m_values;
1275
1276 bool m_grow_on_next_insert;
1277 float m_max_load_factor;
1278 size_type m_load_threshold;
1279};
1280
1281
1282} // end namespace detail_ordered_hash
1283
1284} // end namespace tsl
1285
1286#endif
1287