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
55#include <stddef.h>
56
57//*****************************************************************************
61//*****************************************************************************
62
63namespace etl
64{
65 //***************************************************************************
68 //***************************************************************************
78
79 //***************************************************************************
82 //***************************************************************************
84 {
85 public:
86
88 : etl::unordered_multimap_exception(ETL_ERROR_TEXT("unordered_multimap:full", ETL_UNORDERED_MULTIMAP_FILE_ID"A"), file_name_, line_number_)
89 {
90 }
91 };
92
93 //***************************************************************************
96 //***************************************************************************
98 {
99 public:
100
102 : etl::unordered_multimap_exception(ETL_ERROR_TEXT("unordered_multimap:range", ETL_UNORDERED_MULTIMAP_FILE_ID"B"), file_name_, line_number_)
103 {}
104 };
105
106 //***************************************************************************
109 //***************************************************************************
111 {
112 public:
113
115 : etl::unordered_multimap_exception(ETL_ERROR_TEXT("unordered_multimap:iterator", ETL_UNORDERED_MULTIMAP_FILE_ID"C"), file_name_, line_number_)
116 {
117 }
118 };
119
120 //***************************************************************************
124 //***************************************************************************
125 template <typename TKey, typename T, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
127 {
128 public:
129
130 typedef ETL_OR_STD::pair<const TKey, T> value_type;
131
132 typedef TKey key_type;
133 typedef T mapped_type;
134 typedef THash hasher;
135 typedef TKeyEqual key_equal;
136 typedef value_type& reference;
137 typedef const value_type& const_reference;
138#if ETL_USING_CPP11
139 typedef value_type&& rvalue_reference;
140#endif
141 typedef value_type* pointer;
142 typedef const value_type* const_pointer;
143 typedef size_t size_type;
144
145 typedef const key_type& const_key_reference;
146#if ETL_USING_CPP11
148#endif
149
150 typedef etl::forward_link<0> link_t; // Default link.
151
152 //*********************************************************************
153 // The nodes that store the elements.
154 struct node_t : public link_t
155 {
156 node_t(const_reference key_value_pair_)
157 : key_value_pair(key_value_pair_)
158 {
159 }
160
161 value_type key_value_pair;
162 };
163
164 friend bool operator ==(const node_t& lhs, const node_t& rhs)
165 {
166 return (lhs.key_value_pair.first == rhs.key_value_pair.first) &&
167 (lhs.key_value_pair.second == rhs.key_value_pair.second);
168 }
169
170 friend bool operator !=(const node_t& lhs, const node_t& rhs)
171 {
172 return !(lhs == rhs);
173 }
174
175 protected:
176
178 typedef etl::ipool pool_t;
179
180 public:
181
182 // Local iterators iterate over one bucket.
183 typedef typename bucket_t::iterator local_iterator;
184 typedef typename bucket_t::const_iterator const_local_iterator;
185
186 //*********************************************************************
187 class iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, T>
188 {
189 public:
190
194 typedef typename iunordered_multimap::hasher hasher;
196 typedef typename iunordered_multimap::reference reference;
197 typedef typename iunordered_multimap::const_reference const_reference;
198 typedef typename iunordered_multimap::pointer pointer;
199 typedef typename iunordered_multimap::const_pointer const_pointer;
201
202 friend class iunordered_multimap;
203 friend class const_iterator;
204
205 //*********************************
206 iterator()
207 {
208 }
209
210 //*********************************
211 iterator(const iterator& other)
212 : pbuckets_end(other.pbuckets_end)
213 , pbucket(other.pbucket)
214 , inode(other.inode)
215 {
216 }
217
218 //*********************************
220 {
221 ++inode;
222
223 // The end of this node list?
224 if (inode == pbucket->end())
225 {
226 // Search for the next non-empty bucket.
227 ++pbucket;
228 while ((pbucket != pbuckets_end) && (pbucket->empty()))
229 {
230 ++pbucket;
231 }
232
233 // If not past the end, get the first node in the bucket.
234 if (pbucket != pbuckets_end)
235 {
236 inode = pbucket->begin();
237 }
238 }
239
240 return *this;
241 }
242
243 //*********************************
245 {
246 iterator temp(*this);
247 operator++();
248 return temp;
249 }
250
251 //*********************************
253 {
254 pbuckets_end = other.pbuckets_end;
255 pbucket = other.pbucket;
256 inode = other.inode;
257 return *this;
258 }
259
260 //*********************************
261 reference operator *() const
262 {
263 return inode->key_value_pair;
264 }
265
266 //*********************************
267 pointer operator &() const
268 {
269 return &(inode->key_value_pair);
270 }
271
272 //*********************************
273 pointer operator ->() const
274 {
275 return &(inode->key_value_pair);
276 }
277
278 //*********************************
279 friend bool operator == (const iterator& lhs, const iterator& rhs)
280 {
281 return lhs.compare(rhs);
282 }
283
284 //*********************************
285 friend bool operator != (const iterator& lhs, const iterator& rhs)
286 {
287 return !(lhs == rhs);
288 }
289
290 private:
291
292 //*********************************
294 : pbuckets_end(pbuckets_end_)
295 , pbucket(pbucket_)
296 , inode(inode_)
297 {
298 }
299
300 //*********************************
301 bool compare(const iterator& rhs) const
302 {
303 return rhs.inode == inode;
304 }
305
306 //*********************************
307 bucket_t& get_bucket()
308 {
309 return *pbucket;
310 }
311
312 //*********************************
313 bucket_t*& get_bucket_list_iterator()
314 {
315 return pbucket;
316 }
317
318 //*********************************
319 local_iterator get_local_iterator()
320 {
321 return inode;
322 }
323
324 bucket_t* pbuckets_end;
325 bucket_t* pbucket;
326 local_iterator inode;
327 };
328
329 //*********************************************************************
330 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const T>
331 {
332 public:
333
337 typedef typename iunordered_multimap::hasher hasher;
339 typedef typename iunordered_multimap::reference reference;
340 typedef typename iunordered_multimap::const_reference const_reference;
341 typedef typename iunordered_multimap::pointer pointer;
342 typedef typename iunordered_multimap::const_pointer const_pointer;
344
345 friend class iunordered_multimap;
346 friend class iterator;
347
348 //*********************************
350 {
351 }
352
353 //*********************************
355 : pbuckets_end(other.pbuckets_end)
356 , pbucket(other.pbucket)
357 , inode(other.inode)
358 {
359 }
360
361 //*********************************
363 : pbuckets_end(other.pbuckets_end)
364 , pbucket(other.pbucket)
365 , inode(other.inode)
366 {
367 }
368
369 //*********************************
371 {
372 ++inode;
373
374 // The end of this node list?
375 if (inode == pbucket->end())
376 {
377 // Search for the next non-empty bucket.
378
379 ++pbucket;
380 while ((pbucket != pbuckets_end) && (pbucket->empty()))
381 {
382 ++pbucket;
383 }
384
385 // If not past the end, get the first node in the bucket.
386 if (pbucket != pbuckets_end)
387 {
388 inode = pbucket->begin();
389 }
390 }
391
392 return *this;
393 }
394
395 //*********************************
397 {
398 const_iterator temp(*this);
399 operator++();
400 return temp;
401 }
402
403 //*********************************
405 {
406 pbuckets_end = other.pbuckets_end;
407 pbucket = other.pbucket;
408 inode = other.inode;
409 return *this;
410 }
411
412 //*********************************
413 const_reference operator *() const
414 {
415 return inode->key_value_pair;
416 }
417
418 //*********************************
419 const_pointer operator &() const
420 {
421 return &(inode->key_value_pair);
422 }
423
424 //*********************************
425 const_pointer operator ->() const
426 {
427 return &(inode->key_value_pair);
428 }
429
430 //*********************************
431 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
432 {
433 return lhs.compare(rhs);
434 }
435
436 //*********************************
437 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
438 {
439 return !(lhs == rhs);
440 }
441
442 private:
443
444 //*********************************
446 : pbuckets_end(pbuckets_end_)
447 , pbucket(pbucket_)
448 , inode(inode_)
449 {
450 }
451
452 //*********************************
453 bool compare(const const_iterator& rhs) const
454 {
455 return rhs.inode == inode;
456 }
457
458 //*********************************
459 bucket_t& get_bucket()
460 {
461 return *pbucket;
462 }
463
464 //*********************************
465 bucket_t*& get_bucket_list_iterator()
466 {
467 return pbucket;
468 }
469
470 //*********************************
471 local_iterator get_local_iterator()
472 {
473 return inode;
474 }
475
476 bucket_t* pbuckets_end;
477 bucket_t* pbucket;
478 local_iterator inode;
479 };
480
481 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
482
483 //*********************************************************************
486 //*********************************************************************
488 {
489 return iterator((pbuckets + number_of_buckets), first, first->begin());
490 }
491
492 //*********************************************************************
495 //*********************************************************************
497 {
498 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
499 }
500
501 //*********************************************************************
504 //*********************************************************************
506 {
507 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
508 }
509
510 //*********************************************************************
513 //*********************************************************************
514 local_iterator begin(size_t i)
515 {
516 return pbuckets[i].begin();
517 }
518
519 //*********************************************************************
522 //*********************************************************************
523 const_local_iterator begin(size_t i) const
524 {
525 return pbuckets[i].cbegin();
526 }
527
528 //*********************************************************************
531 //*********************************************************************
532 const_local_iterator cbegin(size_t i) const
533 {
534 return pbuckets[i].cbegin();
535 }
536
537 //*********************************************************************
540 //*********************************************************************
542 {
543 return iterator((pbuckets + number_of_buckets), last, last->end());
544 }
545
546 //*********************************************************************
549 //*********************************************************************
551 {
552 return const_iterator((pbuckets + number_of_buckets), last, last->end());
553 }
554
555 //*********************************************************************
558 //*********************************************************************
560 {
561 return const_iterator((pbuckets + number_of_buckets), last, last->end());
562 }
563
564 //*********************************************************************
567 //*********************************************************************
568 local_iterator end(size_t i)
569 {
570 return pbuckets[i].end();
571 }
572
573 //*********************************************************************
576 //*********************************************************************
577 const_local_iterator end(size_t i) const
578 {
579 return pbuckets[i].cend();
580 }
581
582 //*********************************************************************
585 //*********************************************************************
586 const_local_iterator cend(size_t i) const
587 {
588 return pbuckets[i].cend();
589 }
590
591 //*********************************************************************
594 //*********************************************************************
596 {
597 return key_hash_function(key) % number_of_buckets;
598 }
599
600 //*********************************************************************
603 //*********************************************************************
605 {
606 size_t index = bucket(key);
607
608 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
609 }
610
611 //*********************************************************************
614 //*********************************************************************
616 {
617 return number_of_buckets;
618 }
619
620 //*********************************************************************
623 //*********************************************************************
625 {
626 return number_of_buckets;
627 }
628
629 //*********************************************************************
635 //*********************************************************************
636 template <typename TIterator>
638 {
639#if ETL_IS_DEBUG_BUILD
640 difference_type d = etl::distance(first_, last_);
641 ETL_ASSERT(d >= 0, ETL_ERROR(unordered_multimap_iterator));
642 ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_multimap_full));
643#endif
644
645 clear();
646
647 while (first_ != last_)
648 {
649 insert(*first_);
650 ++first_;
651 }
652 }
653
654 //*********************************************************************
658 //*********************************************************************
659 iterator insert(const_reference key_value_pair)
660 {
661 iterator result = end();
662
664
665 const_key_reference key = key_value_pair.first;
666
667 // Get the hash index.
668 size_t index = get_bucket_index(key);
669
670 // Get the bucket & bucket iterator.
671 bucket_t* pbucket = pbuckets + index;
672 bucket_t& bucket = *pbucket;
673
674 // The first one in the bucket?
675 if (bucket.empty())
676 {
677 // Get a new node.
678 node_t* node = allocate_data_node();
679 node->clear();
680 ::new (&node->key_value_pair) value_type(key_value_pair);
681 ETL_INCREMENT_DEBUG_COUNT;
682
683 // Just add the pointer to the bucket;
684 bucket.insert_after(bucket.before_begin(), *node);
685 adjust_first_last_markers_after_insert(pbucket);
686
687 result = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
688 }
689 else
690 {
691 // Step though the bucket looking for a place to insert.
692 local_iterator inode_previous = bucket.before_begin();
693 local_iterator inode = bucket.begin();
694
695 while (inode != bucket.end())
696 {
697 // Do we already have this key?
698 if (key_equal_function(inode->key_value_pair.first, key))
699 {
700 break;
701 }
702
704 ++inode;
705 }
706
707 // Get a new node.
708 node_t* node = allocate_data_node();
709 node->clear();
710 ::new (&node->key_value_pair) value_type(key_value_pair);
711 ETL_INCREMENT_DEBUG_COUNT;
712
713 // Add the node to the end of the bucket;
714 bucket.insert_after(inode_previous, *node);
715 adjust_first_last_markers_after_insert(&bucket);
717
718 result = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
719 }
720
721 return result;
722 }
723
724#if ETL_USING_CPP11
725 //*********************************************************************
729 //*********************************************************************
730 iterator insert(rvalue_reference key_value_pair)
731 {
732 iterator result = end();
733
735
736 const_key_reference key = key_value_pair.first;
737
738 // Get the hash index.
739 size_t index = get_bucket_index(key);
740
741 // Get the bucket & bucket iterator.
742 bucket_t* pbucket = pbuckets + index;
743 bucket_t& bucket = *pbucket;
744
745 // The first one in the bucket?
746 if (bucket.empty())
747 {
748 // Get a new node.
749 node_t* node = allocate_data_node();
750 node->clear();
751 ::new (&node->key_value_pair) value_type(etl::move(key_value_pair));
752 ETL_INCREMENT_DEBUG_COUNT;
753
754 // Just add the pointer to the bucket;
755 bucket.insert_after(bucket.before_begin(), *node);
756 adjust_first_last_markers_after_insert(pbucket);
757
758 result = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
759 }
760 else
761 {
762 // Step though the bucket looking for a place to insert.
763 local_iterator inode_previous = bucket.before_begin();
764 local_iterator inode = bucket.begin();
765
766 while (inode != bucket.end())
767 {
768 // Do we already have this key?
769 if (key_equal_function(inode->key_value_pair.first, key))
770 {
771 break;
772 }
773
774 ++inode_previous;
775 ++inode;
776 }
777
778 // Get a new node.
779 node_t* node = allocate_data_node();
780 node->clear();
781 ::new (&node->key_value_pair) value_type(etl::move(key_value_pair));
782 ETL_INCREMENT_DEBUG_COUNT;
783
784 // Add the node to the end of the bucket;
785 bucket.insert_after(inode_previous, *node);
786 adjust_first_last_markers_after_insert(&bucket);
787 ++inode_previous;
788
789 result = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
790 }
791
792 return result;
793 }
794#endif
795
796 //*********************************************************************
801 //*********************************************************************
802 iterator insert(const_iterator, const_reference key_value_pair)
803 {
804 return insert(key_value_pair);
805 }
806
807#if ETL_USING_CPP11
808 //*********************************************************************
813 //*********************************************************************
814 iterator insert(const_iterator, rvalue_reference key_value_pair)
815 {
816 return insert(etl::move(key_value_pair));
817 }
818#endif
819
820 //*********************************************************************
826 //*********************************************************************
827 template <class TIterator>
829 {
830 while (first_ != last_)
831 {
832 insert(*first_);
833 ++first_;
834 }
835 }
836
837 //*********************************************************************
841 //*********************************************************************
843 {
844 size_t n = 0UL;
845 size_t bucket_id = get_bucket_index(key);
846
847 bucket_t& bucket = pbuckets[bucket_id];
848
849 local_iterator iprevious = bucket.before_begin();
850 local_iterator icurrent = bucket.begin();
851
852 while (icurrent != bucket.end())
853 {
854 if (key_equal_function(icurrent->key_value_pair.first, key))
855 {
856 delete_data_node(iprevious, icurrent, bucket);
857 ++n;
859 }
860 else
861 {
862 ++iprevious;
863 }
864
865 ++icurrent;
866 }
867
868 return n;
869 }
870
871 //*********************************************************************
874 //*********************************************************************
876 {
877 // Make a note of the next one.
878 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
879 ++inext;
880
881 bucket_t& bucket = ielement.get_bucket();
882 local_iterator iprevious = bucket.before_begin();
883 local_iterator icurrent = ielement.get_local_iterator();
884
885 // Find the node previous to the one we're interested in.
886 while (iprevious->etl_next != &*icurrent)
887 {
888 ++iprevious;
889 }
890
891 delete_data_node(iprevious, icurrent, bucket);
892
893 return inext;
894 }
895
896 //*********************************************************************
902 //*********************************************************************
904 {
905 // Erasing everything?
906 if ((first_ == begin()) && (last_ == end()))
907 {
908 clear();
909 return end();
910 }
911
912 // Get the starting point.
913 bucket_t* pbucket = first_.get_bucket_list_iterator();
914 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
915 local_iterator iprevious = pbucket->before_begin();
916 local_iterator icurrent = first_.get_local_iterator();
917 local_iterator iend = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
918
919 // Find the node previous to the first one.
920 while (iprevious->etl_next != &*icurrent)
921 {
922 ++iprevious;
923 }
924
925 // Remember the item before the first erased one.
926 iterator ibefore_erased = iterator((pbuckets + number_of_buckets), pbucket, iprevious);
927
928 // Until we reach the end.
929 while ((icurrent != iend) || (pbucket != pend_bucket))
930 {
931 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
932
933 // Have we not reached the end?
934 if ((icurrent != iend) || (pbucket != pend_bucket))
935 {
936 // At the end of this bucket?
937 if ((icurrent == pbucket->end()))
938 {
939 // Find the next non-empty one.
940 do
941 {
942 ++pbucket;
943 } while (pbucket->empty());
944
945 iprevious = pbucket->before_begin();
946 icurrent = pbucket->begin();
947 }
948 }
949 }
950
951 return ++ibefore_erased;
952 }
953
954 //*************************************************************************
956 //*************************************************************************
957 void clear()
958 {
959 initialise();
960 }
961
962 //*********************************************************************
966 //*********************************************************************
967 size_t count(const_key_reference key) const
968 {
969 size_t n = 0UL;
970 const_iterator f = find(key);
972
973 if (l != end())
974 {
975 ++l;
976 ++n;
977
978 while ((l != end()) && key_equal_function(key, l->first))
979 {
980 ++l;
981 ++n;
982 }
983 }
984
985 return n;
986 }
987
988 //*********************************************************************
992 //*********************************************************************
994 {
995 size_t index = get_bucket_index(key);
996
997 bucket_t* pbucket = pbuckets + index;
998 bucket_t& bucket = *pbucket;
999
1000 // Is the bucket not empty?
1001 if (!bucket.empty())
1002 {
1003 // Step though the list until we find the end or an equivalent key.
1004 local_iterator inode = bucket.begin();
1005 local_iterator iend = bucket.end();
1006
1007 while (inode != iend)
1008 {
1009 // Do we have this one?
1010 if (key_equal_function(key, inode->key_value_pair.first))
1011 {
1012 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1013 }
1014
1015 ++inode;
1016 }
1017 }
1018
1019 return end();
1020 }
1021
1022 //*********************************************************************
1026 //*********************************************************************
1028 {
1029 size_t index = get_bucket_index(key);
1030
1031 bucket_t* pbucket = pbuckets + index;
1032 bucket_t& bucket = *pbucket;
1033
1034 // Is the bucket not empty?
1035 if (!bucket.empty())
1036 {
1037 // Step though the list until we find the end or an equivalent key.
1038 local_iterator inode = bucket.begin();
1039 local_iterator iend = bucket.end();
1040
1041 while (inode != iend)
1042 {
1043 // Do we have this one?
1044 if (key_equal_function(key, inode->key_value_pair.first))
1045 {
1046 return const_iterator((pbuckets + number_of_buckets), pbucket, inode);
1047 }
1048
1049 ++inode;
1050 }
1051 }
1052
1053 return end();
1054 }
1055
1056 //*********************************************************************
1063 //*********************************************************************
1064 ETL_OR_STD::pair<iterator, iterator> equal_range(const_key_reference key)
1065 {
1066 iterator f = find(key);
1067 iterator l = f;
1068
1069 if (l != end())
1070 {
1071 ++l;
1072
1073 while ((l != end()) && key_equal_function(key, l->first))
1074 {
1075 ++l;
1076 }
1077 }
1078
1079 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1080 }
1081
1082 //*********************************************************************
1089 //*********************************************************************
1090 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const_key_reference key) const
1091 {
1092 const_iterator f = find(key);
1093 const_iterator l = f;
1094
1095 if (l != end())
1096 {
1097 ++l;
1098
1099 while ((l != end()) && key_equal_function(key, l->first))
1100 {
1101 ++l;
1102 }
1103 }
1104
1105 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1106 }
1107
1108 //*************************************************************************
1110 //*************************************************************************
1112 {
1113 return pnodepool->size();
1114 }
1115
1116 //*************************************************************************
1118 //*************************************************************************
1120 {
1121 return pnodepool->max_size();
1122 }
1123
1124 //*************************************************************************
1126 //*************************************************************************
1128 {
1129 return pnodepool->max_size();
1130 }
1131
1132 //*************************************************************************
1134 //*************************************************************************
1135 bool empty() const
1136 {
1137 return pnodepool->empty();
1138 }
1139
1140 //*************************************************************************
1142 //*************************************************************************
1143 bool full() const
1144 {
1145 return pnodepool->full();
1146 }
1147
1148 //*************************************************************************
1151 //*************************************************************************
1152 size_t available() const
1153 {
1154 return pnodepool->available();
1155 }
1156
1157 //*************************************************************************
1160 //*************************************************************************
1161 float load_factor() const
1162 {
1163 return static_cast<float>(size()) / static_cast<float>(bucket_count());
1164 }
1165
1166 //*************************************************************************
1169 //*************************************************************************
1171 {
1172 return key_hash_function;
1173 }
1174
1175 //*************************************************************************
1178 //*************************************************************************
1180 {
1181 return key_equal_function;
1182 }
1183
1184 //*************************************************************************
1186 //*************************************************************************
1188 {
1189 // Skip if doing self assignment
1190 if (this != &rhs)
1191 {
1192 key_hash_function = rhs.hash_function();
1193 key_equal_function = rhs.key_eq();
1194 assign(rhs.cbegin(), rhs.cend());
1195 }
1196
1197 return *this;
1198 }
1199
1200#if ETL_USING_CPP11
1201 //*************************************************************************
1203 //*************************************************************************
1205 {
1206 // Skip if doing self assignment
1207 if (this != &rhs)
1208 {
1209 clear();
1210 key_hash_function = rhs.hash_function();
1211 key_equal_function = rhs.key_eq();
1212 move(rhs.begin(), rhs.end());
1213 }
1214
1215 return *this;
1216 }
1217#endif
1218
1219 protected:
1220
1221 //*********************************************************************
1223 //*********************************************************************
1225 : pnodepool(&node_pool_)
1226 , pbuckets(pbuckets_)
1227 , number_of_buckets(number_of_buckets_)
1228 , first(pbuckets)
1229 , last(pbuckets)
1230 , key_hash_function(key_hash_function_)
1231 , key_equal_function(key_equal_function_)
1232 {
1233 }
1234
1235 //*********************************************************************
1237 //*********************************************************************
1239 {
1240 if (!empty())
1241 {
1242 // For each bucket...
1243 for (size_t i = 0UL; i < number_of_buckets; ++i)
1244 {
1245 bucket_t& bucket = pbuckets[i];
1246
1247 if (!bucket.empty())
1248 {
1249 // For each item in the bucket...
1250 local_iterator it = bucket.begin();
1251
1252 while (it != bucket.end())
1253 {
1254 // Destroy the value contents.
1255 it->key_value_pair.~value_type();
1256 ++it;
1257 ETL_DECREMENT_DEBUG_COUNT;
1258 }
1259
1260 // Now it's safe to clear the bucket.
1261 bucket.clear();
1262 }
1263 }
1264
1265 // Now it's safe to clear the entire pool in one go.
1266 pnodepool->release_all();
1267 }
1268
1269 first = pbuckets;
1270 last = first;
1271 }
1272
1273#if ETL_USING_CPP11
1274 //*************************************************************************
1276 //*************************************************************************
1277 void move(iterator b, iterator e)
1278 {
1279 while (b != e)
1280 {
1281 iterator temp = b;
1282 ++temp;
1283 insert(etl::move(*b));
1284 b = temp;
1285 }
1286 }
1287#endif
1288
1289 private:
1290
1291 //*************************************************************************
1293 //*************************************************************************
1294 node_t* allocate_data_node()
1295 {
1296 node_t* (etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1297 return (pnodepool->*func)();
1298 }
1299
1300 //*********************************************************************
1302 //*********************************************************************
1303 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1304 {
1305 if (size() == 1)
1306 {
1307 first = pbucket;
1308 last = pbucket;
1309 }
1310 else
1311 {
1312 if (pbucket < first)
1313 {
1314 first = pbucket;
1315 }
1316 else if (pbucket > last)
1317 {
1318 last = pbucket;
1319 }
1320 }
1321 }
1322
1323 //*********************************************************************
1325 //*********************************************************************
1326 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1327 {
1328 if (empty())
1329 {
1330 first = pbuckets;
1331 last = pbuckets;
1332 }
1333 else
1334 {
1335 if (pbucket == first)
1336 {
1337 // We erased the first so, we need to search again from where we erased.
1338 while (first->empty())
1339 {
1340 ++first;
1341 }
1342 }
1343 else if (pbucket == last)
1344 {
1345 // We erased the last, so we need to search again. Start from the first, go no further than the current last.
1346 pbucket = first;
1347 bucket_t* pend = last;
1348
1349 last = first;
1350
1351 while (pbucket != pend)
1352 {
1353 if (!pbucket->empty())
1354 {
1355 last = pbucket;
1356 }
1357
1358 ++pbucket;
1359 }
1360 }
1361 }
1362 }
1363
1364 //*********************************************************************
1366 //*********************************************************************
1367 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1368 {
1369 local_iterator inext = bucket.erase_after(iprevious); // Unlink from the bucket.
1370 icurrent->key_value_pair.~value_type(); // Destroy the value.
1371 pnodepool->release(&*icurrent); // Release it back to the pool.
1372 adjust_first_last_markers_after_erase(&bucket);
1373 ETL_DECREMENT_DEBUG_COUNT;
1374
1375 return inext;
1376 }
1377
1378 // Disable copy construction.
1379 iunordered_multimap(const iunordered_multimap&);
1380
1382 pool_t* pnodepool;
1383
1385 bucket_t* pbuckets;
1386
1388 const size_t number_of_buckets;
1389
1391 bucket_t* first;
1392 bucket_t* last;
1393
1395 hasher key_hash_function;
1396
1398 key_equal key_equal_function;
1399
1401 ETL_DECLARE_DEBUG_COUNT;
1402
1403 //*************************************************************************
1405 //*************************************************************************
1406#if defined(ETL_POLYMORPHIC_UNORDERED_MULTIMAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
1407 public:
1408 virtual ~iunordered_multimap()
1409 {
1410 }
1411#else
1412 protected:
1414 {
1415 }
1416#endif
1417 };
1418
1419 //***************************************************************************
1425 //***************************************************************************
1426 template <typename TKey, typename T, typename THash, typename TKeyEqual>
1429 {
1430 const bool sizes_match = (lhs.size() == rhs.size());
1431 bool elements_match = true;
1432
1434
1435 if (sizes_match)
1436 {
1437 itr_t l_begin = lhs.begin();
1438 itr_t l_end = lhs.end();
1439
1440 while ((l_begin != l_end) && elements_match)
1441 {
1442 const TKey key = l_begin->first;
1443 const T l_value = l_begin->second;
1444
1445 // See if the lhs keys exist in the rhs.
1446 ETL_OR_STD::pair<itr_t, itr_t> l_range = lhs.equal_range(key);
1447 ETL_OR_STD::pair<itr_t, itr_t> r_range = rhs.equal_range(key);
1448
1449 if (r_range.first != rhs.end())
1450 {
1451 bool distance_match = (etl::distance(l_range.first, l_range.second) == etl::distance(r_range.first, r_range.second));
1452
1453 if (distance_match)
1454 {
1456 }
1457 else
1458 {
1459 elements_match = false;
1460 }
1461 }
1462 else
1463 {
1464 elements_match = false;
1465 }
1466
1467 ++l_begin;
1468 }
1469 }
1470
1471 return (sizes_match && elements_match);
1472 }
1473
1474 //***************************************************************************
1480 //***************************************************************************
1481 template <typename TKey, typename T, typename THash, typename TKeyEqual>
1487
1488 //*************************************************************************
1490 //*************************************************************************
1491 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> >
1492 class unordered_multimap : public etl::iunordered_multimap<TKey, TValue, THash, TKeyEqual>
1493 {
1494 private:
1495
1497
1498 public:
1499
1500 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1501 static ETL_CONSTANT size_t MAX_BUCKETS = MAX_BUCKETS_;
1502
1503 //*************************************************************************
1505 //*************************************************************************
1506 unordered_multimap(const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1507 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1508 {
1509 }
1510
1511 //*************************************************************************
1513 //*************************************************************************
1515 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1516 {
1517 // Skip if doing self assignment
1518 if (this != &other)
1519 {
1520 base::assign(other.cbegin(), other.cend());
1521 }
1522 }
1523
1524#if ETL_USING_CPP11
1525 //*************************************************************************
1527 //*************************************************************************
1529 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1530 {
1531 // Skip if doing self assignment
1532 if (this != &other)
1533 {
1534 base::move(other.begin(), other.end());
1535 }
1536 }
1537#endif
1538
1539 //*************************************************************************
1544 //*************************************************************************
1545 template <typename TIterator>
1547 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1548 {
1549 base::assign(first_, last_);
1550 }
1551
1552#if ETL_HAS_INITIALIZER_LIST
1553 //*************************************************************************
1555 //*************************************************************************
1556 unordered_multimap(std::initializer_list<ETL_OR_STD::pair<TKey, TValue>> init, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1557 : base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
1558 {
1559 base::assign(init.begin(), init.end());
1560 }
1561#endif
1562
1563 //*************************************************************************
1565 //*************************************************************************
1567 {
1568 base::initialise();
1569 }
1570
1571 //*************************************************************************
1573 //*************************************************************************
1575 {
1576 base::operator=(rhs);
1577
1578 return *this;
1579 }
1580
1581#if ETL_USING_CPP11
1582 //*************************************************************************
1584 //*************************************************************************
1586 {
1587 base::operator=(etl::move(rhs));
1588
1589 return *this;
1590 }
1591#endif
1592
1593 private:
1594
1597
1599 typename base::bucket_t buckets[MAX_BUCKETS_];
1600 };
1601
1602 //*************************************************************************
1604 //*************************************************************************
1605#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1606 template <typename... TPairs>
1607 unordered_multimap(TPairs...) -> unordered_multimap<typename etl::nth_type_t<0, TPairs...>::first_type,
1608 typename etl::nth_type_t<0, TPairs...>::second_type,
1609 sizeof...(TPairs)>;
1610#endif
1611
1612 //*************************************************************************
1614 //*************************************************************************
1615#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1616 template <typename TKey, typename T, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey>, typename... TPairs>
1617 constexpr auto make_unordered_multimap(TPairs&&... pairs) -> etl::unordered_multimap<TKey, T, sizeof...(TPairs), sizeof...(TPairs), THash, TKeyEqual>
1618 {
1619 return { etl::forward<TPairs>(pairs)... };
1620 }
1621#endif
1622}
1623
1624#endif
Definition unordered_multimap.h:331
Definition unordered_multimap.h:188
A templated unordered_multimap implementation that uses a fixed size buffer.
Definition unordered_multimap.h:1493
unordered_multimap(const unordered_multimap &other)
Copy constructor.
Definition unordered_multimap.h:1514
unordered_multimap(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_multimap.h:1546
unordered_multimap(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_multimap.h:1506
~unordered_multimap()
Destructor.
Definition unordered_multimap.h:1566
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:966
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition algorithm.h:1727
#define ETL_ASSERT(b, e)
Definition error_handler.h:316
Definition exception.h:47
size_t size() const
Returns the number of allocated items in the pool.
Definition ipool.h:293
bool empty() const
Definition ipool.h:302
void release_all()
Release all objects in the pool.
Definition ipool.h:248
bool full() const
Definition ipool.h:311
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:285
Definition ipool.h:102
iterator end()
Definition unordered_multimap.h:541
iunordered_multimap & operator=(const iunordered_multimap &rhs)
Assignment operator.
Definition unordered_multimap.h:1187
const_local_iterator cend(size_t i) const
Definition unordered_multimap.h:586
const_local_iterator cbegin(size_t i) const
Definition unordered_multimap.h:532
float load_factor() const
Definition unordered_multimap.h:1161
void assign(TIterator first_, TIterator last_)
Definition unordered_multimap.h:637
size_t available() const
Definition unordered_multimap.h:1152
const_local_iterator end(size_t i) const
Definition unordered_multimap.h:577
key_equal key_eq() const
Definition unordered_multimap.h:1179
const_iterator find(const_key_reference key) const
Definition unordered_multimap.h:1027
bool empty() const
Checks to see if the unordered_multimap is empty.
Definition unordered_multimap.h:1135
size_type bucket_count() const
Definition unordered_multimap.h:624
iterator insert(const_reference key_value_pair)
Definition unordered_multimap.h:659
iterator erase(const_iterator ielement)
Definition unordered_multimap.h:875
local_iterator end(size_t i)
Definition unordered_multimap.h:568
size_type capacity() const
Gets the maximum possible size of the unordered_multimap.
Definition unordered_multimap.h:1127
const_local_iterator begin(size_t i) const
Definition unordered_multimap.h:523
void initialise()
Initialise the unordered_multimap.
Definition unordered_multimap.h:1238
const_iterator end() const
Definition unordered_multimap.h:550
size_t count(const_key_reference key) const
Definition unordered_multimap.h:967
iterator find(const_key_reference key)
Definition unordered_multimap.h:993
size_type size() const
Gets the size of the unordered_multimap.
Definition unordered_multimap.h:1111
void clear()
Clears the unordered_multimap.
Definition unordered_multimap.h:957
const_iterator begin() const
Definition unordered_multimap.h:496
hasher hash_function() const
Definition unordered_multimap.h:1170
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_multimap.h:903
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition unordered_multimap.h:1090
iterator insert(const_iterator, const_reference key_value_pair)
Definition unordered_multimap.h:802
size_type max_size() const
Gets the maximum possible size of the unordered_multimap.
Definition unordered_multimap.h:1119
const_iterator cbegin() const
Definition unordered_multimap.h:505
local_iterator begin(size_t i)
Definition unordered_multimap.h:514
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition unordered_multimap.h:1064
~iunordered_multimap()
Destructor.
Definition unordered_multimap.h:1413
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:1224
size_type bucket_size(const_key_reference key) const
Definition unordered_multimap.h:604
size_type max_bucket_count() const
Definition unordered_multimap.h:615
const_iterator cend() const
Definition unordered_multimap.h:559
void insert(TIterator first_, TIterator last_)
Definition unordered_multimap.h:828
bool full() const
Checks to see if the unordered_multimap is full.
Definition unordered_multimap.h:1143
size_t erase(const_key_reference key)
Definition unordered_multimap.h:842
size_type get_bucket_index(const_key_reference key) const
Definition unordered_multimap.h:595
iterator begin()
Definition unordered_multimap.h:487
Definition unordered_multimap.h:127
Definition unordered_multimap.h:70
Definition unordered_multimap.h:84
Definition unordered_multimap.h:111
Definition unordered_multimap.h:98
bitset_ext
Definition absolute.h:38
Definition compare.h:51
iterator
Definition iterator.h:399
Definition unordered_multimap.h:155
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