Embedded Template Library 1.0
Loading...
Searching...
No Matches
unordered_multimap.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2016 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_UNORDERED_MULTIMAP_INCLUDED
32#define ETL_UNORDERED_MULTIMAP_INCLUDED
33
34#include "platform.h"
35#include "algorithm.h"
36#include "iterator.h"
37#include "functional.h"
38#include "utility.h"
39#include "pool.h"
40#include "vector.h"
42#include "hash.h"
43#include "type_traits.h"
44#include "nth_type.h"
45#include "parameter_type.h"
46#include "nullptr.h"
47#include "pool.h"
48#include "error_handler.h"
49#include "exception.h"
50#include "debug_count.h"
51#include "iterator.h"
52#include "placement_new.h"
53#include "initializer_list.h"
54
56
57#include <stddef.h>
58
59//*****************************************************************************
63//*****************************************************************************
64
65namespace etl
66{
67 //***************************************************************************
70 //***************************************************************************
80
81 //***************************************************************************
84 //***************************************************************************
86 {
87 public:
88
90 : etl::unordered_multimap_exception(ETL_ERROR_TEXT("unordered_multimap:full", ETL_UNORDERED_MULTIMAP_FILE_ID"A"), file_name_, line_number_)
91 {
92 }
93 };
94
95 //***************************************************************************
98 //***************************************************************************
100 {
101 public:
102
104 : etl::unordered_multimap_exception(ETL_ERROR_TEXT("unordered_multimap:range", ETL_UNORDERED_MULTIMAP_FILE_ID"B"), file_name_, line_number_)
105 {}
106 };
107
108 //***************************************************************************
111 //***************************************************************************
113 {
114 public:
115
117 : etl::unordered_multimap_exception(ETL_ERROR_TEXT("unordered_multimap:iterator", ETL_UNORDERED_MULTIMAP_FILE_ID"C"), file_name_, line_number_)
118 {
119 }
120 };
121
122 //***************************************************************************
126 //***************************************************************************
127 template <typename TKey, typename T, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
129 {
130 public:
131
132 typedef ETL_OR_STD::pair<const TKey, T> value_type;
133
134 typedef TKey key_type;
135 typedef T mapped_type;
136 typedef THash hasher;
137 typedef TKeyEqual key_equal;
138 typedef value_type& reference;
139 typedef const value_type& const_reference;
140#if ETL_USING_CPP11
141 typedef value_type&& rvalue_reference;
142#endif
143 typedef value_type* pointer;
144 typedef const value_type* const_pointer;
145 typedef size_t size_type;
146
147 typedef const key_type& const_key_reference;
148#if ETL_USING_CPP11
150#endif
151
152 typedef etl::forward_link<0> link_t; // Default link.
153
154 //*********************************************************************
155 // The nodes that store the elements.
156 struct node_t : public link_t
157 {
158 node_t(const_reference key_value_pair_)
159 : key_value_pair(key_value_pair_)
160 {
161 }
162
163 value_type key_value_pair;
164 };
165
166 friend bool operator ==(const node_t& lhs, const node_t& rhs)
167 {
168 return (lhs.key_value_pair.first == rhs.key_value_pair.first) &&
169 (lhs.key_value_pair.second == rhs.key_value_pair.second);
170 }
171
172 friend bool operator !=(const node_t& lhs, const node_t& rhs)
173 {
174 return !(lhs == rhs);
175 }
176
177 protected:
178
180 typedef etl::ipool pool_t;
181
182 public:
183
184 // Local iterators iterate over one bucket.
185 typedef typename bucket_t::iterator local_iterator;
186 typedef typename bucket_t::const_iterator const_local_iterator;
187
188 //*********************************************************************
189 class iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, T>
190 {
191 public:
192
196 typedef typename iunordered_multimap::hasher hasher;
198 typedef typename iunordered_multimap::reference reference;
199 typedef typename iunordered_multimap::const_reference const_reference;
200 typedef typename iunordered_multimap::pointer pointer;
201 typedef typename iunordered_multimap::const_pointer const_pointer;
203
204 friend class iunordered_multimap;
205 friend class const_iterator;
206
207 //*********************************
208 iterator()
209 {
210 }
211
212 //*********************************
213 iterator(const iterator& other)
214 : pbuckets_end(other.pbuckets_end)
215 , pbucket(other.pbucket)
216 , inode(other.inode)
217 {
218 }
219
220 //*********************************
222 {
223 ++inode;
224
225 // The end of this node list?
226 if (inode == pbucket->end())
227 {
228 // Search for the next non-empty bucket.
229 ++pbucket;
230 while ((pbucket != pbuckets_end) && (pbucket->empty()))
231 {
232 ++pbucket;
233 }
234
235 // If not past the end, get the first node in the bucket.
236 if (pbucket != pbuckets_end)
237 {
238 inode = pbucket->begin();
239 }
240 }
241
242 return *this;
243 }
244
245 //*********************************
247 {
248 iterator temp(*this);
249 operator++();
250 return temp;
251 }
252
253 //*********************************
255 {
256 pbuckets_end = other.pbuckets_end;
257 pbucket = other.pbucket;
258 inode = other.inode;
259 return *this;
260 }
261
262 //*********************************
263 reference operator *() const
264 {
265 return inode->key_value_pair;
266 }
267
268 //*********************************
269 pointer operator &() const
270 {
271 return &(inode->key_value_pair);
272 }
273
274 //*********************************
275 pointer operator ->() const
276 {
277 return &(inode->key_value_pair);
278 }
279
280 //*********************************
281 friend bool operator == (const iterator& lhs, const iterator& rhs)
282 {
283 return lhs.compare(rhs);
284 }
285
286 //*********************************
287 friend bool operator != (const iterator& lhs, const iterator& rhs)
288 {
289 return !(lhs == rhs);
290 }
291
292 private:
293
294 //*********************************
296 : pbuckets_end(pbuckets_end_)
297 , pbucket(pbucket_)
298 , inode(inode_)
299 {
300 }
301
302 //*********************************
303 bool compare(const iterator& rhs) const
304 {
305 return rhs.inode == inode;
306 }
307
308 //*********************************
309 bucket_t& get_bucket()
310 {
311 return *pbucket;
312 }
313
314 //*********************************
315 bucket_t*& get_bucket_list_iterator()
316 {
317 return pbucket;
318 }
319
320 //*********************************
321 local_iterator get_local_iterator()
322 {
323 return inode;
324 }
325
326 bucket_t* pbuckets_end;
327 bucket_t* pbucket;
328 local_iterator inode;
329 };
330
331 //*********************************************************************
332 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const T>
333 {
334 public:
335
339 typedef typename iunordered_multimap::hasher hasher;
341 typedef typename iunordered_multimap::reference reference;
342 typedef typename iunordered_multimap::const_reference const_reference;
343 typedef typename iunordered_multimap::pointer pointer;
344 typedef typename iunordered_multimap::const_pointer const_pointer;
346
347 friend class iunordered_multimap;
348 friend class iterator;
349
350 //*********************************
352 {
353 }
354
355 //*********************************
357 : pbuckets_end(other.pbuckets_end)
358 , pbucket(other.pbucket)
359 , inode(other.inode)
360 {
361 }
362
363 //*********************************
365 : pbuckets_end(other.pbuckets_end)
366 , pbucket(other.pbucket)
367 , inode(other.inode)
368 {
369 }
370
371 //*********************************
373 {
374 ++inode;
375
376 // The end of this node list?
377 if (inode == pbucket->end())
378 {
379 // Search for the next non-empty bucket.
380
381 ++pbucket;
382 while ((pbucket != pbuckets_end) && (pbucket->empty()))
383 {
384 ++pbucket;
385 }
386
387 // If not past the end, get the first node in the bucket.
388 if (pbucket != pbuckets_end)
389 {
390 inode = pbucket->begin();
391 }
392 }
393
394 return *this;
395 }
396
397 //*********************************
399 {
400 const_iterator temp(*this);
401 operator++();
402 return temp;
403 }
404
405 //*********************************
407 {
408 pbuckets_end = other.pbuckets_end;
409 pbucket = other.pbucket;
410 inode = other.inode;
411 return *this;
412 }
413
414 //*********************************
415 const_reference operator *() const
416 {
417 return inode->key_value_pair;
418 }
419
420 //*********************************
421 const_pointer operator &() const
422 {
423 return &(inode->key_value_pair);
424 }
425
426 //*********************************
427 const_pointer operator ->() const
428 {
429 return &(inode->key_value_pair);
430 }
431
432 //*********************************
433 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
434 {
435 return lhs.compare(rhs);
436 }
437
438 //*********************************
439 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
440 {
441 return !(lhs == rhs);
442 }
443
444 private:
445
446 //*********************************
448 : pbuckets_end(pbuckets_end_)
449 , pbucket(pbucket_)
450 , inode(inode_)
451 {
452 }
453
454 //*********************************
455 bool compare(const const_iterator& rhs) const
456 {
457 return rhs.inode == inode;
458 }
459
460 //*********************************
461 bucket_t& get_bucket()
462 {
463 return *pbucket;
464 }
465
466 //*********************************
467 bucket_t*& get_bucket_list_iterator()
468 {
469 return pbucket;
470 }
471
472 //*********************************
473 local_iterator get_local_iterator()
474 {
475 return inode;
476 }
477
478 bucket_t* pbuckets_end;
479 bucket_t* pbucket;
480 local_iterator inode;
481 };
482
483 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
484
485 //*********************************************************************
488 //*********************************************************************
490 {
491 return iterator((pbuckets + number_of_buckets), first, first->begin());
492 }
493
494 //*********************************************************************
497 //*********************************************************************
499 {
500 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
501 }
502
503 //*********************************************************************
506 //*********************************************************************
508 {
509 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
510 }
511
512 //*********************************************************************
515 //*********************************************************************
516 local_iterator begin(size_t i)
517 {
518 return pbuckets[i].begin();
519 }
520
521 //*********************************************************************
524 //*********************************************************************
525 const_local_iterator begin(size_t i) const
526 {
527 return pbuckets[i].cbegin();
528 }
529
530 //*********************************************************************
533 //*********************************************************************
534 const_local_iterator cbegin(size_t i) const
535 {
536 return pbuckets[i].cbegin();
537 }
538
539 //*********************************************************************
542 //*********************************************************************
544 {
545 return iterator((pbuckets + number_of_buckets), last, last->end());
546 }
547
548 //*********************************************************************
551 //*********************************************************************
553 {
554 return const_iterator((pbuckets + number_of_buckets), last, last->end());
555 }
556
557 //*********************************************************************
560 //*********************************************************************
562 {
563 return const_iterator((pbuckets + number_of_buckets), last, last->end());
564 }
565
566 //*********************************************************************
569 //*********************************************************************
570 local_iterator end(size_t i)
571 {
572 return pbuckets[i].end();
573 }
574
575 //*********************************************************************
578 //*********************************************************************
579 const_local_iterator end(size_t i) const
580 {
581 return pbuckets[i].cend();
582 }
583
584 //*********************************************************************
587 //*********************************************************************
588 const_local_iterator cend(size_t i) const
589 {
590 return pbuckets[i].cend();
591 }
592
593 //*********************************************************************
596 //*********************************************************************
598 {
599 return key_hash_function(key) % number_of_buckets;
600 }
601
602#if ETL_USING_CPP11
603 //*********************************************************************
606 //*********************************************************************
608 size_type get_bucket_index(const K& key) const
609 {
610 return key_hash_function(key) % number_of_buckets;
611 }
612#endif
613
614 //*********************************************************************
617 //*********************************************************************
619 {
620 size_t index = bucket(key);
621
622 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
623 }
624
625#if ETL_USING_CPP11
626 //*********************************************************************
629 //*********************************************************************
631 size_type bucket_size(const K& key) const
632 {
633 size_t index = bucket(key);
634
635 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
636 }
637#endif
638
639 //*********************************************************************
642 //*********************************************************************
644 {
645 return number_of_buckets;
646 }
647
648 //*********************************************************************
651 //*********************************************************************
653 {
654 return number_of_buckets;
655 }
656
657 //*********************************************************************
663 //*********************************************************************
664 template <typename TIterator>
666 {
667#if ETL_IS_DEBUG_BUILD
668 difference_type d = etl::distance(first_, last_);
669 ETL_ASSERT(d >= 0, ETL_ERROR(unordered_multimap_iterator));
670 ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_multimap_full));
671#endif
672
673 clear();
674
675 while (first_ != last_)
676 {
677 insert(*first_);
678 ++first_;
679 }
680 }
681
682 //*********************************************************************
686 //*********************************************************************
687 iterator insert(const_reference key_value_pair)
688 {
689 iterator result = end();
690
692
693 const_key_reference key = key_value_pair.first;
694
695 // Get the hash index.
696 size_t index = get_bucket_index(key);
697
698 // Get the bucket & bucket iterator.
699 bucket_t* pbucket = pbuckets + index;
700 bucket_t& bucket = *pbucket;
701
702 // The first one in the bucket?
703 if (bucket.empty())
704 {
705 // Get a new node.
706 node_t* node = allocate_data_node();
707 node->clear();
708 ::new (&node->key_value_pair) value_type(key_value_pair);
709 ETL_INCREMENT_DEBUG_COUNT;
710
711 // Just add the pointer to the bucket;
712 bucket.insert_after(bucket.before_begin(), *node);
713 adjust_first_last_markers_after_insert(pbucket);
714
715 result = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
716 }
717 else
718 {
719 // Step though the bucket looking for a place to insert.
720 local_iterator inode_previous = bucket.before_begin();
721 local_iterator inode = bucket.begin();
722
723 while (inode != bucket.end())
724 {
725 // Do we already have this key?
726 if (key_equal_function(inode->key_value_pair.first, key))
727 {
728 break;
729 }
730
732 ++inode;
733 }
734
735 // Get a new node.
736 node_t* node = allocate_data_node();
737 node->clear();
738 ::new (&node->key_value_pair) value_type(key_value_pair);
739 ETL_INCREMENT_DEBUG_COUNT;
740
741 // Add the node to the end of the bucket;
742 bucket.insert_after(inode_previous, *node);
743 adjust_first_last_markers_after_insert(&bucket);
745
746 result = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
747 }
748
749 return result;
750 }
751
752#if ETL_USING_CPP11
753 //*********************************************************************
757 //*********************************************************************
758 iterator insert(rvalue_reference key_value_pair)
759 {
760 iterator result = end();
761
763
764 const_key_reference key = key_value_pair.first;
765
766 // Get the hash index.
767 size_t index = get_bucket_index(key);
768
769 // Get the bucket & bucket iterator.
770 bucket_t* pbucket = pbuckets + index;
771 bucket_t& bucket = *pbucket;
772
773 // The first one in the bucket?
774 if (bucket.empty())
775 {
776 // Get a new node.
777 node_t* node = allocate_data_node();
778 node->clear();
779 ::new (&node->key_value_pair) value_type(etl::move(key_value_pair));
780 ETL_INCREMENT_DEBUG_COUNT;
781
782 // Just add the pointer to the bucket;
783 bucket.insert_after(bucket.before_begin(), *node);
784 adjust_first_last_markers_after_insert(pbucket);
785
786 result = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
787 }
788 else
789 {
790 // Step though the bucket looking for a place to insert.
791 local_iterator inode_previous = bucket.before_begin();
792 local_iterator inode = bucket.begin();
793
794 while (inode != bucket.end())
795 {
796 // Do we already have this key?
797 if (key_equal_function(inode->key_value_pair.first, key))
798 {
799 break;
800 }
801
802 ++inode_previous;
803 ++inode;
804 }
805
806 // Get a new node.
807 node_t* node = allocate_data_node();
808 node->clear();
809 ::new (&node->key_value_pair) value_type(etl::move(key_value_pair));
810 ETL_INCREMENT_DEBUG_COUNT;
811
812 // Add the node to the end of the bucket;
813 bucket.insert_after(inode_previous, *node);
814 adjust_first_last_markers_after_insert(&bucket);
815 ++inode_previous;
816
817 result = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
818 }
819
820 return result;
821 }
822#endif
823
824 //*********************************************************************
829 //*********************************************************************
830 iterator insert(const_iterator, const_reference key_value_pair)
831 {
832 return insert(key_value_pair);
833 }
834
835#if ETL_USING_CPP11
836 //*********************************************************************
841 //*********************************************************************
842 iterator insert(const_iterator, rvalue_reference key_value_pair)
843 {
844 return insert(etl::move(key_value_pair));
845 }
846#endif
847
848 //*********************************************************************
854 //*********************************************************************
855 template <class TIterator>
857 {
858 while (first_ != last_)
859 {
860 insert(*first_);
861 ++first_;
862 }
863 }
864
865 //*********************************************************************
869 //*********************************************************************
871 {
872 size_t n = 0UL;
873 size_t bucket_id = get_bucket_index(key);
874
875 bucket_t& bucket = pbuckets[bucket_id];
876
877 local_iterator iprevious = bucket.before_begin();
878 local_iterator icurrent = bucket.begin();
879
880 while (icurrent != bucket.end())
881 {
882 if (key_equal_function(icurrent->key_value_pair.first, key))
883 {
884 delete_data_node(iprevious, icurrent, bucket);
885 ++n;
887 }
888 else
889 {
890 ++iprevious;
891 }
892
893 ++icurrent;
894 }
895
896 return n;
897 }
898
899#if ETL_USING_CPP11
900 //*********************************************************************
904 //*********************************************************************
906 size_t erase(const K& key)
907 {
908 size_t n = 0UL;
909 size_t bucket_id = get_bucket_index(key);
910
911 bucket_t& bucket = pbuckets[bucket_id];
912
913 local_iterator iprevious = bucket.before_begin();
914 local_iterator icurrent = bucket.begin();
915
916 while (icurrent != bucket.end())
917 {
918 if (key_equal_function(icurrent->key_value_pair.first, key))
919 {
920 delete_data_node(iprevious, icurrent, bucket);
921 ++n;
923 }
924 else
925 {
926 ++iprevious;
927 }
928
929 ++icurrent;
930 }
931
932 return n;
933 }
934#endif
935
936 //*********************************************************************
939 //*********************************************************************
941 {
942 // Make a note of the next one.
943 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
944 ++inext;
945
946 bucket_t& bucket = ielement.get_bucket();
947 local_iterator iprevious = bucket.before_begin();
948 local_iterator icurrent = ielement.get_local_iterator();
949
950 // Find the node previous to the one we're interested in.
951 while (iprevious->etl_next != &*icurrent)
952 {
953 ++iprevious;
954 }
955
956 delete_data_node(iprevious, icurrent, bucket);
957
958 return inext;
959 }
960
961 //*********************************************************************
967 //*********************************************************************
969 {
970 // Erasing everything?
971 if ((first_ == begin()) && (last_ == end()))
972 {
973 clear();
974 return end();
975 }
976
977 // Get the starting point.
978 bucket_t* pbucket = first_.get_bucket_list_iterator();
979 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
980 local_iterator iprevious = pbucket->before_begin();
981 local_iterator icurrent = first_.get_local_iterator();
982 local_iterator iend = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
983
984 // Find the node previous to the first one.
985 while (iprevious->etl_next != &*icurrent)
986 {
987 ++iprevious;
988 }
989
990 // Remember the item before the first erased one.
991 iterator ibefore_erased = iterator((pbuckets + number_of_buckets), pbucket, iprevious);
992
993 // Until we reach the end.
994 while ((icurrent != iend) || (pbucket != pend_bucket))
995 {
996 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
997
998 // Have we not reached the end?
999 if ((icurrent != iend) || (pbucket != pend_bucket))
1000 {
1001 // At the end of this bucket?
1002 if ((icurrent == pbucket->end()))
1003 {
1004 // Find the next non-empty one.
1005 do
1006 {
1007 ++pbucket;
1008 } while (pbucket->empty());
1009
1010 iprevious = pbucket->before_begin();
1011 icurrent = pbucket->begin();
1012 }
1013 }
1014 }
1015
1016 return ++ibefore_erased;
1017 }
1018
1019 //*************************************************************************
1021 //*************************************************************************
1022 void clear()
1023 {
1024 initialise();
1025 }
1026
1027 //*********************************************************************
1031 //*********************************************************************
1032 size_t count(const_key_reference key) const
1033 {
1034 size_t n = 0UL;
1035 const_iterator f = find(key);
1036 const_iterator l = f;
1037
1038 if (l != end())
1039 {
1040 ++l;
1041 ++n;
1042
1043 while ((l != end()) && key_equal_function(key, l->first))
1044 {
1045 ++l;
1046 ++n;
1047 }
1048 }
1049
1050 return n;
1051 }
1052
1053#if ETL_USING_CPP11
1054 //*********************************************************************
1058 //*********************************************************************
1060 size_t count(const K& key) const
1061 {
1062 size_t n = 0UL;
1063 const_iterator f = find(key);
1064 const_iterator l = f;
1065
1066 if (l != end())
1067 {
1068 ++l;
1069 ++n;
1070
1071 while ((l != end()) && key_equal_function(key, l->first))
1072 {
1073 ++l;
1074 ++n;
1075 }
1076 }
1077
1078 return n;
1079 }
1080#endif
1081
1082 //*********************************************************************
1086 //*********************************************************************
1088 {
1089 size_t index = get_bucket_index(key);
1090
1091 bucket_t* pbucket = pbuckets + index;
1092 bucket_t& bucket = *pbucket;
1093
1094 // Is the bucket not empty?
1095 if (!bucket.empty())
1096 {
1097 // Step though the list until we find the end or an equivalent key.
1098 local_iterator inode = bucket.begin();
1099 local_iterator iend = bucket.end();
1100
1101 while (inode != iend)
1102 {
1103 // Do we have this one?
1104 if (key_equal_function(key, inode->key_value_pair.first))
1105 {
1106 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1107 }
1108
1109 ++inode;
1110 }
1111 }
1112
1113 return end();
1114 }
1115
1116 //*********************************************************************
1120 //*********************************************************************
1122 {
1123 size_t index = get_bucket_index(key);
1124
1125 bucket_t* pbucket = pbuckets + index;
1126 bucket_t& bucket = *pbucket;
1127
1128 // Is the bucket not empty?
1129 if (!bucket.empty())
1130 {
1131 // Step though the list until we find the end or an equivalent key.
1132 local_iterator inode = bucket.begin();
1133 local_iterator iend = bucket.end();
1134
1135 while (inode != iend)
1136 {
1137 // Do we have this one?
1138 if (key_equal_function(key, inode->key_value_pair.first))
1139 {
1140 return const_iterator((pbuckets + number_of_buckets), pbucket, inode);
1141 }
1142
1143 ++inode;
1144 }
1145 }
1146
1147 return end();
1148 }
1149
1150#if ETL_USING_CPP11
1151 //*********************************************************************
1155 //*********************************************************************
1157 iterator find(const K& key)
1158 {
1159 size_t index = get_bucket_index(key);
1160
1161 bucket_t* pbucket = pbuckets + index;
1162 bucket_t& bucket = *pbucket;
1163
1164 // Is the bucket not empty?
1165 if (!bucket.empty())
1166 {
1167 // Step though the list until we find the end or an equivalent key.
1168 local_iterator inode = bucket.begin();
1169 local_iterator iend = bucket.end();
1170
1171 while (inode != iend)
1172 {
1173 // Do we have this one?
1174 if (key_equal_function(key, inode->key_value_pair.first))
1175 {
1176 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1177 }
1178
1179 ++inode;
1180 }
1181 }
1182
1183 return end();
1184 }
1185#endif
1186
1187#if ETL_USING_CPP11
1188 //*********************************************************************
1192 //*********************************************************************
1193 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value, int> = 0>
1194 const_iterator find(const K& key) const
1195 {
1196 size_t index = get_bucket_index(key);
1197
1198 bucket_t* pbucket = pbuckets + index;
1199 bucket_t& bucket = *pbucket;
1200
1201 // Is the bucket not empty?
1202 if (!bucket.empty())
1203 {
1204 // Step though the list until we find the end or an equivalent key.
1205 local_iterator inode = bucket.begin();
1206 local_iterator iend = bucket.end();
1207
1208 while (inode != iend)
1209 {
1210 // Do we have this one?
1211 if (key_equal_function(key, inode->key_value_pair.first))
1212 {
1213 return const_iterator((pbuckets + number_of_buckets), pbucket, inode);
1214 }
1215
1216 ++inode;
1217 }
1218 }
1219
1220 return end();
1221 }
1222#endif
1223
1224 //*********************************************************************
1231 //*********************************************************************
1232 ETL_OR_STD::pair<iterator, iterator> equal_range(const_key_reference key)
1233 {
1234 iterator f = find(key);
1235 iterator l = f;
1236
1237 if (l != end())
1238 {
1239 ++l;
1240
1241 while ((l != end()) && key_equal_function(key, l->first))
1242 {
1243 ++l;
1244 }
1245 }
1246
1247 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1248 }
1249
1250 //*********************************************************************
1257 //*********************************************************************
1258 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const_key_reference key) const
1259 {
1260 const_iterator f = find(key);
1261 const_iterator l = f;
1262
1263 if (l != end())
1264 {
1265 ++l;
1266
1267 while ((l != end()) && key_equal_function(key, l->first))
1268 {
1269 ++l;
1270 }
1271 }
1272
1273 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1274 }
1275
1276#if ETL_USING_CPP11
1277 //*********************************************************************
1284 //*********************************************************************
1286 ETL_OR_STD::pair<iterator, iterator> equal_range(const K& key)
1287 {
1288 iterator f = find(key);
1289 iterator l = f;
1290
1291 if (l != end())
1292 {
1293 ++l;
1294
1295 while ((l != end()) && key_equal_function(key, l->first))
1296 {
1297 ++l;
1298 }
1299 }
1300
1301 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1302 }
1303#endif
1304
1305#if ETL_USING_CPP11
1306 //*********************************************************************
1313 //*********************************************************************
1314 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value, int> = 0>
1315 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const K& key) const
1316 {
1317 const_iterator f = find(key);
1318 const_iterator l = f;
1319
1320 if (l != end())
1321 {
1322 ++l;
1323
1324 while ((l != end()) && key_equal_function(key, l->first))
1325 {
1326 ++l;
1327 }
1328 }
1329
1330 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1331 }
1332#endif
1333
1334 //*************************************************************************
1336 //*************************************************************************
1338 {
1339 return pnodepool->size();
1340 }
1341
1342 //*************************************************************************
1344 //*************************************************************************
1346 {
1347 return pnodepool->max_size();
1348 }
1349
1350 //*************************************************************************
1352 //*************************************************************************
1354 {
1355 return pnodepool->max_size();
1356 }
1357
1358 //*************************************************************************
1360 //*************************************************************************
1361 bool empty() const
1362 {
1363 return pnodepool->empty();
1364 }
1365
1366 //*************************************************************************
1368 //*************************************************************************
1369 bool full() const
1370 {
1371 return pnodepool->full();
1372 }
1373
1374 //*************************************************************************
1377 //*************************************************************************
1378 size_t available() const
1379 {
1380 return pnodepool->available();
1381 }
1382
1383 //*************************************************************************
1386 //*************************************************************************
1387 float load_factor() const
1388 {
1389 return static_cast<float>(size()) / static_cast<float>(bucket_count());
1390 }
1391
1392 //*************************************************************************
1395 //*************************************************************************
1397 {
1398 return key_hash_function;
1399 }
1400
1401 //*************************************************************************
1404 //*************************************************************************
1406 {
1407 return key_equal_function;
1408 }
1409
1410 //*************************************************************************
1412 //*************************************************************************
1414 {
1415 // Skip if doing self assignment
1416 if (this != &rhs)
1417 {
1418 key_hash_function = rhs.hash_function();
1419 key_equal_function = rhs.key_eq();
1420 assign(rhs.cbegin(), rhs.cend());
1421 }
1422
1423 return *this;
1424 }
1425
1426#if ETL_USING_CPP11
1427 //*************************************************************************
1429 //*************************************************************************
1431 {
1432 // Skip if doing self assignment
1433 if (this != &rhs)
1434 {
1435 clear();
1436 key_hash_function = rhs.hash_function();
1437 key_equal_function = rhs.key_eq();
1438 move(rhs.begin(), rhs.end());
1439 }
1440
1441 return *this;
1442 }
1443#endif
1444
1445 //*************************************************************************
1447 //*************************************************************************
1449 {
1450 return find(key) != end();
1451 }
1452
1453#if ETL_USING_CPP11
1454 //*************************************************************************
1456 //*************************************************************************
1458 bool contains(const K& key) const
1459 {
1460 return find(key) != end();
1461 }
1462#endif
1463
1464 protected:
1465
1466 //*********************************************************************
1468 //*********************************************************************
1470 : pnodepool(&node_pool_)
1471 , pbuckets(pbuckets_)
1472 , number_of_buckets(number_of_buckets_)
1473 , first(pbuckets)
1474 , last(pbuckets)
1475 , key_hash_function(key_hash_function_)
1476 , key_equal_function(key_equal_function_)
1477 {
1478 }
1479
1480 //*********************************************************************
1482 //*********************************************************************
1484 {
1485 if (!empty())
1486 {
1487 // For each bucket...
1488 for (size_t i = 0UL; i < number_of_buckets; ++i)
1489 {
1490 bucket_t& bucket = pbuckets[i];
1491
1492 if (!bucket.empty())
1493 {
1494 // For each item in the bucket...
1495 local_iterator it = bucket.begin();
1496
1497 while (it != bucket.end())
1498 {
1499 // Destroy the value contents.
1500 it->key_value_pair.~value_type();
1501 ++it;
1502 ETL_DECREMENT_DEBUG_COUNT;
1503 }
1504
1505 // Now it's safe to clear the bucket.
1506 bucket.clear();
1507 }
1508 }
1509
1510 // Now it's safe to clear the entire pool in one go.
1511 pnodepool->release_all();
1512 }
1513
1514 first = pbuckets;
1515 last = first;
1516 }
1517
1518#if ETL_USING_CPP11
1519 //*************************************************************************
1521 //*************************************************************************
1522 void move(iterator b, iterator e)
1523 {
1524 while (b != e)
1525 {
1526 iterator temp = b;
1527 ++temp;
1528 insert(etl::move(*b));
1529 b = temp;
1530 }
1531 }
1532#endif
1533
1534 private:
1535
1536 //*************************************************************************
1538 //*************************************************************************
1539 node_t* allocate_data_node()
1540 {
1541 node_t* (etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1542 return (pnodepool->*func)();
1543 }
1544
1545 //*********************************************************************
1547 //*********************************************************************
1548 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1549 {
1550 if (size() == 1)
1551 {
1552 first = pbucket;
1553 last = pbucket;
1554 }
1555 else
1556 {
1557 if (pbucket < first)
1558 {
1559 first = pbucket;
1560 }
1561 else if (pbucket > last)
1562 {
1563 last = pbucket;
1564 }
1565 }
1566 }
1567
1568 //*********************************************************************
1570 //*********************************************************************
1571 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1572 {
1573 if (empty())
1574 {
1575 first = pbuckets;
1576 last = pbuckets;
1577 }
1578 else
1579 {
1580 if (pbucket == first)
1581 {
1582 // We erased the first so, we need to search again from where we erased.
1583 while (first->empty())
1584 {
1585 ++first;
1586 }
1587 }
1588 else if (pbucket == last)
1589 {
1590 // We erased the last, so we need to search again. Start from the first, go no further than the current last.
1591 pbucket = first;
1592 bucket_t* pend = last;
1593
1594 last = first;
1595
1596 while (pbucket != pend)
1597 {
1598 if (!pbucket->empty())
1599 {
1600 last = pbucket;
1601 }
1602
1603 ++pbucket;
1604 }
1605 }
1606 }
1607 }
1608
1609 //*********************************************************************
1611 //*********************************************************************
1612 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1613 {
1614 local_iterator inext = bucket.erase_after(iprevious); // Unlink from the bucket.
1615 icurrent->key_value_pair.~value_type(); // Destroy the value.
1616 pnodepool->release(&*icurrent); // Release it back to the pool.
1617 adjust_first_last_markers_after_erase(&bucket);
1618 ETL_DECREMENT_DEBUG_COUNT;
1619
1620 return inext;
1621 }
1622
1623 // Disable copy construction.
1624 iunordered_multimap(const iunordered_multimap&);
1625
1627 pool_t* pnodepool;
1628
1630 bucket_t* pbuckets;
1631
1633 const size_t number_of_buckets;
1634
1636 bucket_t* first;
1637 bucket_t* last;
1638
1640 hasher key_hash_function;
1641
1643 key_equal key_equal_function;
1644
1646 ETL_DECLARE_DEBUG_COUNT;
1647
1648 //*************************************************************************
1650 //*************************************************************************
1651#if defined(ETL_POLYMORPHIC_UNORDERED_MULTIMAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
1652 public:
1653 virtual ~iunordered_multimap()
1654 {
1655 }
1656#else
1657 protected:
1659 {
1660 }
1661#endif
1662 };
1663
1664 //***************************************************************************
1670 //***************************************************************************
1671 template <typename TKey, typename T, typename THash, typename TKeyEqual>
1674 {
1675 const bool sizes_match = (lhs.size() == rhs.size());
1676 bool elements_match = true;
1677
1679
1680 if (sizes_match)
1681 {
1682 itr_t l_begin = lhs.begin();
1683 itr_t l_end = lhs.end();
1684
1685 while ((l_begin != l_end) && elements_match)
1686 {
1687 const TKey key = l_begin->first;
1688 const T l_value = l_begin->second;
1689
1690 // See if the lhs keys exist in the rhs.
1691 ETL_OR_STD::pair<itr_t, itr_t> l_range = lhs.equal_range(key);
1692 ETL_OR_STD::pair<itr_t, itr_t> r_range = rhs.equal_range(key);
1693
1694 if (r_range.first != rhs.end())
1695 {
1696 bool distance_match = (etl::distance(l_range.first, l_range.second) == etl::distance(r_range.first, r_range.second));
1697
1698 if (distance_match)
1699 {
1701 }
1702 else
1703 {
1704 elements_match = false;
1705 }
1706 }
1707 else
1708 {
1709 elements_match = false;
1710 }
1711
1712 ++l_begin;
1713 }
1714 }
1715
1716 return (sizes_match && elements_match);
1717 }
1718
1719 //***************************************************************************
1725 //***************************************************************************
1726 template <typename TKey, typename T, typename THash, typename TKeyEqual>
1732
1733 //*************************************************************************
1735 //*************************************************************************
1736 template <typename TKey, typename TValue, const size_t MAX_SIZE_, const size_t MAX_BUCKETS_ = MAX_SIZE_, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
1737 class unordered_multimap : public etl::iunordered_multimap<TKey, TValue, THash, TKeyEqual>
1738 {
1739 private:
1740
1742
1743 public:
1744
1745 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1746 static ETL_CONSTANT size_t MAX_BUCKETS = MAX_BUCKETS_;
1747
1748 //*************************************************************************
1750 //*************************************************************************
1751 unordered_multimap(const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1752 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1753 {
1754 }
1755
1756 //*************************************************************************
1758 //*************************************************************************
1760 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1761 {
1762 // Skip if doing self assignment
1763 if (this != &other)
1764 {
1765 base::assign(other.cbegin(), other.cend());
1766 }
1767 }
1768
1769#if ETL_USING_CPP11
1770 //*************************************************************************
1772 //*************************************************************************
1774 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1775 {
1776 // Skip if doing self assignment
1777 if (this != &other)
1778 {
1779 base::move(other.begin(), other.end());
1780 }
1781 }
1782#endif
1783
1784 //*************************************************************************
1789 //*************************************************************************
1790 template <typename TIterator>
1792 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1793 {
1794 base::assign(first_, last_);
1795 }
1796
1797#if ETL_HAS_INITIALIZER_LIST
1798 //*************************************************************************
1800 //*************************************************************************
1801 unordered_multimap(std::initializer_list<ETL_OR_STD::pair<TKey, TValue>> init, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1802 : base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
1803 {
1804 base::assign(init.begin(), init.end());
1805 }
1806#endif
1807
1808 //*************************************************************************
1810 //*************************************************************************
1812 {
1813 base::initialise();
1814 }
1815
1816 //*************************************************************************
1818 //*************************************************************************
1820 {
1821 base::operator=(rhs);
1822
1823 return *this;
1824 }
1825
1826#if ETL_USING_CPP11
1827 //*************************************************************************
1829 //*************************************************************************
1831 {
1832 base::operator=(etl::move(rhs));
1833
1834 return *this;
1835 }
1836#endif
1837
1838 private:
1839
1842
1844 typename base::bucket_t buckets[MAX_BUCKETS_];
1845 };
1846
1847 //*************************************************************************
1849 //*************************************************************************
1850#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1851 template <typename... TPairs>
1852 unordered_multimap(TPairs...) -> unordered_multimap<typename etl::nth_type_t<0, TPairs...>::first_type,
1853 typename etl::nth_type_t<0, TPairs...>::second_type,
1854 sizeof...(TPairs)>;
1855#endif
1856
1857 //*************************************************************************
1859 //*************************************************************************
1860#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1861 template <typename TKey, typename T, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey>, typename... TPairs>
1862 constexpr auto make_unordered_multimap(TPairs&&... pairs) -> etl::unordered_multimap<TKey, T, sizeof...(TPairs), sizeof...(TPairs), THash, TKeyEqual>
1863 {
1864 return { etl::forward<TPairs>(pairs)... };
1865 }
1866#endif
1867}
1868
1869#endif
Definition unordered_multimap.h:333
Definition unordered_multimap.h:190
A templated unordered_multimap implementation that uses a fixed size buffer.
Definition unordered_multimap.h:1738
unordered_multimap(const unordered_multimap &other)
Copy constructor.
Definition unordered_multimap.h:1759
unordered_multimap(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_multimap.h:1791
unordered_multimap(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_multimap.h:1751
~unordered_multimap()
Destructor.
Definition unordered_multimap.h:1811
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:968
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition algorithm.h:1739
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
size_t size() const
Returns the number of allocated items in the pool.
Definition ipool.h:301
bool empty() const
Definition ipool.h:310
void release_all()
Release all objects in the pool.
Definition ipool.h:248
bool full() const
Definition ipool.h:319
size_t max_size() const
Returns the maximum number of items in the pool.
Definition ipool.h:269
void release(const void *const p_object)
Definition ipool.h:239
size_t available() const
Returns the number of free items in the pool.
Definition ipool.h:293
Definition ipool.h:102
iterator end()
Definition unordered_multimap.h:543
iunordered_multimap & operator=(const iunordered_multimap &rhs)
Assignment operator.
Definition unordered_multimap.h:1413
const_local_iterator cend(size_t i) const
Definition unordered_multimap.h:588
const_local_iterator cbegin(size_t i) const
Definition unordered_multimap.h:534
float load_factor() const
Definition unordered_multimap.h:1387
void assign(TIterator first_, TIterator last_)
Definition unordered_multimap.h:665
size_t available() const
Definition unordered_multimap.h:1378
const_local_iterator end(size_t i) const
Definition unordered_multimap.h:579
key_equal key_eq() const
Definition unordered_multimap.h:1405
const_iterator find(const_key_reference key) const
Definition unordered_multimap.h:1121
bool contains(const_key_reference key) const
Check if the unordered_multimap contains the key.
Definition unordered_multimap.h:1448
bool empty() const
Checks to see if the unordered_multimap is empty.
Definition unordered_multimap.h:1361
size_type bucket_count() const
Definition unordered_multimap.h:652
iterator insert(const_reference key_value_pair)
Definition unordered_multimap.h:687
iterator erase(const_iterator ielement)
Definition unordered_multimap.h:940
local_iterator end(size_t i)
Definition unordered_multimap.h:570
size_type capacity() const
Gets the maximum possible size of the unordered_multimap.
Definition unordered_multimap.h:1353
const_local_iterator begin(size_t i) const
Definition unordered_multimap.h:525
void initialise()
Initialise the unordered_multimap.
Definition unordered_multimap.h:1483
const_iterator end() const
Definition unordered_multimap.h:552
size_t count(const_key_reference key) const
Definition unordered_multimap.h:1032
iterator find(const_key_reference key)
Definition unordered_multimap.h:1087
size_type size() const
Gets the size of the unordered_multimap.
Definition unordered_multimap.h:1337
void clear()
Clears the unordered_multimap.
Definition unordered_multimap.h:1022
const_iterator begin() const
Definition unordered_multimap.h:498
hasher hash_function() const
Definition unordered_multimap.h:1396
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_multimap.h:968
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition unordered_multimap.h:1258
iterator insert(const_iterator, const_reference key_value_pair)
Definition unordered_multimap.h:830
size_type max_size() const
Gets the maximum possible size of the unordered_multimap.
Definition unordered_multimap.h:1345
const_iterator cbegin() const
Definition unordered_multimap.h:507
local_iterator begin(size_t i)
Definition unordered_multimap.h:516
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition unordered_multimap.h:1232
~iunordered_multimap()
Destructor.
Definition unordered_multimap.h:1658
iunordered_multimap(pool_t &node_pool_, bucket_t *pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
Constructor.
Definition unordered_multimap.h:1469
size_type bucket_size(const_key_reference key) const
Definition unordered_multimap.h:618
size_type max_bucket_count() const
Definition unordered_multimap.h:643
const_iterator cend() const
Definition unordered_multimap.h:561
void insert(TIterator first_, TIterator last_)
Definition unordered_multimap.h:856
bool full() const
Checks to see if the unordered_multimap is full.
Definition unordered_multimap.h:1369
size_t erase(const_key_reference key)
Definition unordered_multimap.h:870
size_type get_bucket_index(const_key_reference key) const
Definition unordered_multimap.h:597
iterator begin()
Definition unordered_multimap.h:489
Definition unordered_multimap.h:129
Definition unordered_multimap.h:72
Definition unordered_multimap.h:86
Definition unordered_multimap.h:113
Definition unordered_multimap.h:100
bitset_ext
Definition absolute.h:38
Definition compare.h:51
iterator
Definition iterator.h:399
Definition unordered_multimap.h:157
pair holds two objects of arbitrary type
Definition utility.h:164
T1 first
first is a copy of the first object
Definition utility.h:168
T2 second
second is a copy of the second object
Definition utility.h:169