Embedded Template Library 1.0
Loading...
Searching...
No Matches
unordered_multiset.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_MULTISET_INCLUDED
32#define ETL_UNORDERED_MULTISET_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 "error_handler.h"
48#include "exception.h"
49#include "debug_count.h"
50#include "iterator.h"
51#include "placement_new.h"
52#include "initializer_list.h"
53
54#include <stddef.h>
55
56//*****************************************************************************
60//*****************************************************************************
61
62namespace etl
63{
64 //***************************************************************************
67 //***************************************************************************
77
78 //***************************************************************************
81 //***************************************************************************
83 {
84 public:
85
87 : etl::unordered_multiset_exception(ETL_ERROR_TEXT("unordered_multiset:full", ETL_UNORDERED_MULTISET_FILE_ID"A"), file_name_, line_number_)
88 {
89 }
90 };
91
92 //***************************************************************************
95 //***************************************************************************
97 {
98 public:
99
101 : etl::unordered_multiset_exception(ETL_ERROR_TEXT("unordered_multiset:range", ETL_UNORDERED_MULTISET_FILE_ID"B"), file_name_, line_number_)
102 {}
103 };
104
105 //***************************************************************************
108 //***************************************************************************
110 {
111 public:
112
114 : etl::unordered_multiset_exception(ETL_ERROR_TEXT("unordered_multiset:iterator", ETL_UNORDERED_MULTISET_FILE_ID"C"), file_name_, line_number_)
115 {
116 }
117 };
118
119 //***************************************************************************
123 //***************************************************************************
124 template <typename TKey, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
126 {
127 public:
128
129 typedef TKey value_type;
130 typedef TKey key_type;
131 typedef THash hasher;
132 typedef TKeyEqual key_equal;
133 typedef value_type& reference;
134 typedef const value_type& const_reference;
135#if ETL_USING_CPP11
137#endif
138 typedef value_type* pointer;
139 typedef const value_type* const_pointer;
140 typedef size_t size_type;
141
142 typedef const TKey& key_parameter_t;
143
145
146 //*********************************************************************
147 // The nodes that store the elements.
148 struct node_t : public link_t
149 {
151 : key(key_)
152 {
153 }
154
155 value_type key;
156 };
157
158 friend bool operator ==(const node_t& lhs, const node_t& rhs)
159 {
160 return (lhs.key == rhs.key);
161 }
162
163 friend bool operator !=(const node_t& lhs, const node_t& rhs)
164 {
165 return !(lhs == rhs);
166 }
167
168 protected:
169
171 typedef etl::ipool pool_t;
172
173 public:
174
175 // Local iterators iterate over one bucket.
176 typedef typename bucket_t::iterator local_iterator;
177 typedef typename bucket_t::const_iterator const_local_iterator;
178
179 //*********************************************************************
180 class iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, TKey>
181 {
182 public:
183
186 typedef typename iunordered_multiset::hasher hasher;
190 typedef typename iunordered_multiset::pointer pointer;
193
194 friend class iunordered_multiset;
195 friend class const_iterator;
196
197 //*********************************
198 iterator()
199 {
200 }
201
202 //*********************************
203 iterator(const iterator& other)
204 : pbuckets_end(other.pbuckets_end)
205 , pbucket(other.pbucket)
206 , inode(other.inode)
207 {
208 }
209
210 //*********************************
212 {
213 ++inode;
214
215 // The end of this node list?
216 if (inode == pbucket->end())
217 {
218 // Search for the next non-empty bucket.
219 ++pbucket;
220 while ((pbucket != pbuckets_end) && (pbucket->empty()))
221 {
222 ++pbucket;
223 }
224
225 // If not past the end, get the first node in the bucket.
226 if (pbucket != pbuckets_end)
227 {
228 inode = pbucket->begin();
229 }
230 }
231
232 return *this;
233 }
234
235 //*********************************
237 {
238 iterator temp(*this);
239 operator++();
240 return temp;
241 }
242
243 //*********************************
245 {
246 pbuckets_end = other.pbuckets_end;
247 pbucket = other.pbucket;
248 inode = other.inode;
249 return *this;
250 }
251
252 //*********************************
253 reference operator *() const
254 {
255 return inode->key;
256 }
257
258 //*********************************
259 pointer operator &() const
260 {
261 return &(inode->key);
262 }
263
264 //*********************************
265 pointer operator ->() const
266 {
267 return &(inode->key);
268 }
269
270 //*********************************
271 friend bool operator == (const iterator& lhs, const iterator& rhs)
272 {
273 return lhs.compare(rhs);
274 }
275
276 //*********************************
277 friend bool operator != (const iterator& lhs, const iterator& rhs)
278 {
279 return !(lhs == rhs);
280 }
281
282 private:
283
284 //*********************************
286 : pbuckets_end(pbuckets_end_)
287 , pbucket(pbucket_)
288 , inode(inode_)
289 {
290 }
291
292 //*********************************
293 bool compare(const iterator& rhs) const
294 {
295 return rhs.inode == inode;
296 }
297
298 //*********************************
299 bucket_t& get_bucket()
300 {
301 return *pbucket;
302 }
303
304 //*********************************
305 bucket_t*& get_bucket_list_iterator()
306 {
307 return pbucket;
308 }
309
310 //*********************************
311 local_iterator get_local_iterator()
312 {
313 return inode;
314 }
315
316 bucket_t* pbuckets_end;
317 bucket_t* pbucket;
318 local_iterator inode;
319 };
320
321 //*********************************************************************
322 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const TKey>
323 {
324 public:
325
328 typedef typename iunordered_multiset::hasher hasher;
332 typedef typename iunordered_multiset::pointer pointer;
335
336 friend class iunordered_multiset;
337 friend class iterator;
338
339 //*********************************
341 {
342 }
343
344 //*********************************
346 : pbuckets_end(other.pbuckets_end)
347 , pbucket(other.pbucket)
348 , inode(other.inode)
349 {
350 }
351
352 //*********************************
354 : pbuckets_end(other.pbuckets_end)
355 , pbucket(other.pbucket)
356 , inode(other.inode)
357 {
358 }
359
360 //*********************************
362 {
363 ++inode;
364
365 // The end of this node list?
366 if (inode == pbucket->end())
367 {
368 // Search for the next non-empty bucket.
369
370 ++pbucket;
371 while ((pbucket != pbuckets_end) && (pbucket->empty()))
372 {
373 ++pbucket;
374 }
375
376 // If not past the end, get the first node in the bucket.
377 if (pbucket != pbuckets_end)
378 {
379 inode = pbucket->begin();
380 }
381 }
382
383 return *this;
384 }
385
386 //*********************************
388 {
389 const_iterator temp(*this);
390 operator++();
391 return temp;
392 }
393
394 //*********************************
396 {
397 pbuckets_end = other.pbuckets_end;
398 pbucket = other.pbucket;
399 inode = other.inode;
400 return *this;
401 }
402
403 //*********************************
405 {
406 return inode->key;
407 }
408
409 //*********************************
411 {
412 return &(inode->key);
413 }
414
415 //*********************************
417 {
418 return &(inode->key);
419 }
420
421 //*********************************
422 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
423 {
424 return lhs.compare(rhs);
425 }
426
427 //*********************************
428 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
429 {
430 return !(lhs == rhs);
431 }
432
433 private:
434
435 //*********************************
437 : pbuckets_end(pbuckets_end_)
438 , pbucket(pbucket_)
439 , inode(inode_)
440 {
441 }
442
443 //*********************************
444 bool compare(const const_iterator& rhs) const
445 {
446 return rhs.inode == inode;
447 }
448
449 //*********************************
450 bucket_t& get_bucket()
451 {
452 return *pbucket;
453 }
454
455 //*********************************
456 bucket_t*& get_bucket_list_iterator()
457 {
458 return pbucket;
459 }
460
461 //*********************************
462 local_iterator get_local_iterator()
463 {
464 return inode;
465 }
466
467 bucket_t* pbuckets_end;
468 bucket_t* pbucket;
469 local_iterator inode;
470 };
471
472 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
473
474 //*********************************************************************
477 //*********************************************************************
479 {
480 return iterator((pbuckets + number_of_buckets), first, first->begin());
481 }
482
483 //*********************************************************************
486 //*********************************************************************
488 {
489 return const_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 //*********************************************************************
505 local_iterator begin(size_t i)
506 {
507 return pbuckets[i].begin();
508 }
509
510 //*********************************************************************
513 //*********************************************************************
514 const_local_iterator begin(size_t i) const
515 {
516 return pbuckets[i].cbegin();
517 }
518
519 //*********************************************************************
522 //*********************************************************************
523 const_local_iterator cbegin(size_t i) const
524 {
525 return pbuckets[i].cbegin();
526 }
527
528 //*********************************************************************
531 //*********************************************************************
533 {
534 return iterator((pbuckets + number_of_buckets), last, last->end());
535 }
536
537 //*********************************************************************
540 //*********************************************************************
542 {
543 return const_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 //*********************************************************************
559 local_iterator end(size_t i)
560 {
561 return pbuckets[i].end();
562 }
563
564 //*********************************************************************
567 //*********************************************************************
568 const_local_iterator end(size_t i) const
569 {
570 return pbuckets[i].cend();
571 }
572
573 //*********************************************************************
576 //*********************************************************************
577 const_local_iterator cend(size_t i) const
578 {
579 return pbuckets[i].cend();
580 }
581
582 //*********************************************************************
585 //*********************************************************************
587 {
588 return key_hash_function(key) % number_of_buckets;
589 }
590
591 //*********************************************************************
594 //*********************************************************************
596 {
597 size_t index = bucket(key);
598
599 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
600 }
601
602 //*********************************************************************
605 //*********************************************************************
607 {
608 return number_of_buckets;
609 }
610
611 //*********************************************************************
614 //*********************************************************************
616 {
617 return number_of_buckets;
618 }
619
620 //*********************************************************************
626 //*********************************************************************
627 template <typename TIterator>
629 {
630#if ETL_IS_DEBUG_BUILD
631 difference_type d = etl::distance(first_, last_);
632 ETL_ASSERT(d >= 0, ETL_ERROR(unordered_multiset_iterator));
633 ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_multiset_full));
634#endif
635
636 clear();
637
638 while (first_ != last_)
639 {
640 insert(*first_);
641 ++first_;
642 }
643 }
644
645 //*********************************************************************
649 //*********************************************************************
650 ETL_OR_STD::pair<iterator, bool> insert(const_reference key)
651 {
652 ETL_OR_STD::pair<iterator, bool> result(end(), false);
653
655
656 // Get the hash index.
657 size_t index = get_bucket_index(key);
658
659 // Get the bucket & bucket iterator.
660 bucket_t* pbucket = pbuckets + index;
661 bucket_t& bucket = *pbucket;
662
663 // The first one in the bucket?
664 if (bucket.empty())
665 {
666 // Get a new node.
667 node_t* node = allocate_data_node();
668 node->clear();
669 ::new (&node->key) value_type(key);
670 ETL_INCREMENT_DEBUG_COUNT;
671
672 // Just add the pointer to the bucket;
673 bucket.insert_after(bucket.before_begin(), *node);
674 adjust_first_last_markers_after_insert(&bucket);
675
676 result.first = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
677 result.second = true;
678 }
679 else
680 {
681 // Step though the bucket looking for a place to insert.
682 local_iterator inode_previous = bucket.before_begin();
683 local_iterator inode = bucket.begin();
684
685 while (inode != bucket.end())
686 {
687 // Do we already have this key?
688 if (key_equal_function(inode->key, key))
689 {
690 break;
691 }
692
694 ++inode;
695 }
696
697 // Get a new node.
698 node_t* node = allocate_data_node();
699 node->clear();
700 ::new (&node->key) value_type(key);
701 ETL_INCREMENT_DEBUG_COUNT;
702
703 // Add the node to the end of the bucket;
704 bucket.insert_after(inode_previous, *node);
705 adjust_first_last_markers_after_insert(&bucket);
707
708 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
709 result.second = true;
710 }
711
712 return result;
713 }
714
715#if ETL_USING_CPP11
716 //*********************************************************************
720 //*********************************************************************
721 ETL_OR_STD::pair<iterator, bool> insert(rvalue_reference key)
722 {
723 ETL_OR_STD::pair<iterator, bool> result(end(), false);
724
726
727 // Get the hash index.
728 size_t index = get_bucket_index(key);
729
730 // Get the bucket & bucket iterator.
731 bucket_t* pbucket = pbuckets + index;
732 bucket_t& bucket = *pbucket;
733
734 // The first one in the bucket?
735 if (bucket.empty())
736 {
737 // Get a new node.
738 node_t* node = allocate_data_node();
739 node->clear();
740 ::new (&node->key) value_type(etl::move(key));
741 ETL_INCREMENT_DEBUG_COUNT;
742
743 // Just add the pointer to the bucket;
744 bucket.insert_after(bucket.before_begin(), *node);
745 adjust_first_last_markers_after_insert(&bucket);
746
747 result.first = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
748 result.second = true;
749 }
750 else
751 {
752 // Step though the bucket looking for a place to insert.
753 local_iterator inode_previous = bucket.before_begin();
754 local_iterator inode = bucket.begin();
755
756 while (inode != bucket.end())
757 {
758 // Do we already have this key?
759 if (key_equal_function(inode->key, key))
760 {
761 break;
762 }
763
764 ++inode_previous;
765 ++inode;
766 }
767
768 // Get a new node.
769 node_t* node = allocate_data_node();
770 node->clear();
771 ::new (&node->key) value_type(etl::move(key));
772 ETL_INCREMENT_DEBUG_COUNT;
773
774 // Add the node to the end of the bucket;
775 bucket.insert_after(inode_previous, *node);
776 adjust_first_last_markers_after_insert(&bucket);
777 ++inode_previous;
778
779 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
780 result.second = true;
781 }
782
783 return result;
784 }
785#endif
786
787 //*********************************************************************
792 //*********************************************************************
794 {
795 return insert(key).first;
796 }
797
798 //*********************************************************************
804 //*********************************************************************
805 template <class TIterator>
807 {
808 while (first_ != last_)
809 {
810 insert(*first_);
811 ++first_;
812 }
813 }
814
815 //*********************************************************************
819 //*********************************************************************
821 {
822 size_t n = 0UL;
823 size_t bucket_id = get_bucket_index(key);
824
825 bucket_t& bucket = pbuckets[bucket_id];
826
827 local_iterator iprevious = bucket.before_begin();
828 local_iterator icurrent = bucket.begin();
829
830 while (icurrent != bucket.end())
831 {
832 if (key_equal_function(icurrent->key, key))
833 {
834 delete_data_node(iprevious, icurrent, bucket);
835 ++n;
837 }
838 else
839 {
840 ++iprevious;
841 }
842
843 ++icurrent;
844 }
845
846 return n;
847 }
848
849 //*********************************************************************
852 //*********************************************************************
854 {
855 // Make a note of the next one.
856 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
857 ++inext;
858
859 bucket_t& bucket = ielement.get_bucket();
860 local_iterator iprevious = bucket.before_begin();
861 local_iterator icurrent = ielement.get_local_iterator();
862
863 // Find the node previous to the one we're interested in.
864 while (iprevious->etl_next != &*icurrent)
865 {
866 ++iprevious;
867 }
868
869 delete_data_node(iprevious, icurrent, bucket);
870
871 return inext;
872 }
873
874 //*********************************************************************
880 //*********************************************************************
882 {
883 // Erasing everything?
884 if ((first_ == begin()) && (last_ == end()))
885 {
886 clear();
887 return end();
888 }
889
890 // Get the starting point.
891 bucket_t* pbucket = first_.get_bucket_list_iterator();
892 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
893 local_iterator iprevious = pbucket->before_begin();
894 local_iterator icurrent = first_.get_local_iterator();
895 local_iterator iend = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
896
897 // Find the node previous to the first one.
898 while (iprevious->etl_next != &*icurrent)
899 {
900 ++iprevious;
901 }
902
903 // Remember the item before the first erased one.
904 iterator ibefore_erased = iterator((pbuckets + number_of_buckets), pbucket, iprevious);
905
906 // Until we reach the end.
907 while ((icurrent != iend) || (pbucket != pend_bucket))
908 {
909 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
910
911 // Have we not reached the end?
912 if ((icurrent != iend) || (pbucket != pend_bucket))
913 {
914 // At the end of this bucket?
915 if ((icurrent == pbucket->end()))
916 {
917 // Find the next non-empty one.
918 do
919 {
920 ++pbucket;
921 } while (pbucket->empty());
922
923 iprevious = pbucket->before_begin();
924 icurrent = pbucket->begin();
925 }
926 }
927 }
928
929 return ++ibefore_erased;
930 }
931
932 //*************************************************************************
934 //*************************************************************************
935 void clear()
936 {
937 initialise();
938 }
939
940 //*********************************************************************
944 //*********************************************************************
945 size_t count(key_parameter_t key) const
946 {
947 size_t n = 0UL;
948 const_iterator f = find(key);
950
951 if (l != end())
952 {
953 ++l;
954 ++n;
955
956 while ((l != end()) && key_equal_function(key, *l))
957 {
958 ++l;
959 ++n;
960 }
961 }
962
963 return n;
964 }
965
966 //*********************************************************************
970 //*********************************************************************
972 {
973 size_t index = get_bucket_index(key);
974
975 bucket_t* pbucket = pbuckets + index;
976 bucket_t& bucket = *pbucket;
977
978 // Is the bucket not empty?
979 if (!bucket.empty())
980 {
981 // Step though the list until we find the end or an equivalent key.
982 local_iterator inode = bucket.begin();
983 local_iterator iend = bucket.end();
984
985 while (inode != iend)
986 {
987 // Do we have this one?
988 if (key_equal_function(key, inode->key))
989 {
990 return iterator((pbuckets + number_of_buckets), pbucket, inode);
991 }
992
993 ++inode;
994 }
995 }
996
997 return end();
998 }
999
1000 //*********************************************************************
1004 //*********************************************************************
1006 {
1007 size_t index = get_bucket_index(key);
1008
1009 bucket_t* pbucket = pbuckets + index;
1010 bucket_t& bucket = *pbucket;
1011
1012 // Is the bucket not empty?
1013 if (!bucket.empty())
1014 {
1015 // Step though the list until we find the end or an equivalent key.
1016 local_iterator inode = bucket.begin();
1017 local_iterator iend = bucket.end();
1018
1019 while (inode != iend)
1020 {
1021 // Do we have this one?
1022 if (key_equal_function(key, inode->key))
1023 {
1024 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1025 }
1026
1027 ++inode;
1028 }
1029 }
1030
1031 return end();
1032 }
1033
1034 //*********************************************************************
1041 //*********************************************************************
1042 ETL_OR_STD::pair<iterator, iterator> equal_range(key_parameter_t key)
1043 {
1044 iterator f = find(key);
1045 iterator l = f;
1046
1047 if (l != end())
1048 {
1049 ++l;
1050
1051 while ((l != end()) && key_equal_function(key, *l))
1052 {
1053 ++l;
1054 }
1055 }
1056
1057 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1058 }
1059
1060 //*********************************************************************
1067 //*********************************************************************
1068 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
1069 {
1070 const_iterator f = find(key);
1071 const_iterator l = f;
1072
1073 if (l != end())
1074 {
1075 ++l;
1076
1077 while ((l != end()) && key_equal_function(key, *l))
1078 {
1079 ++l;
1080 }
1081 }
1082
1083 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1084 }
1085
1086 //*************************************************************************
1088 //*************************************************************************
1090 {
1091 return pnodepool->size();
1092 }
1093
1094 //*************************************************************************
1096 //*************************************************************************
1098 {
1099 return pnodepool->max_size();
1100 }
1101
1102 //*************************************************************************
1104 //*************************************************************************
1106 {
1107 return pnodepool->max_size();
1108 }
1109
1110 //*************************************************************************
1112 //*************************************************************************
1113 bool empty() const
1114 {
1115 return pnodepool->empty();
1116 }
1117
1118 //*************************************************************************
1120 //*************************************************************************
1121 bool full() const
1122 {
1123 return pnodepool->full();
1124 }
1125
1126 //*************************************************************************
1129 //*************************************************************************
1130 size_t available() const
1131 {
1132 return pnodepool->available();
1133 }
1134
1135 //*************************************************************************
1138 //*************************************************************************
1139 float load_factor() const
1140 {
1141 return static_cast<float>(size()) / static_cast<float>(bucket_count());
1142 }
1143
1144 //*************************************************************************
1147 //*************************************************************************
1149 {
1150 return key_hash_function;
1151 }
1152
1153 //*************************************************************************
1156 //*************************************************************************
1158 {
1159 return key_equal_function;
1160 }
1161
1162 //*************************************************************************
1164 //*************************************************************************
1166 {
1167 // Skip if doing self assignment
1168 if (this != &rhs)
1169 {
1170 key_hash_function = rhs.hash_function();
1171 key_equal_function = rhs.key_eq();
1172 assign(rhs.cbegin(), rhs.cend());
1173 }
1174
1175 return *this;
1176 }
1177
1178#if ETL_USING_CPP11
1179 //*************************************************************************
1181 //*************************************************************************
1183 {
1184 // Skip if doing self assignment
1185 if (this != &rhs)
1186 {
1187 clear();
1188 key_hash_function = rhs.hash_function();
1189 key_equal_function = rhs.key_eq();
1190 move(rhs.begin(), rhs.end());
1191 }
1192
1193 return *this;
1194 }
1195#endif
1196
1197 protected:
1198
1199 //*********************************************************************
1201 //*********************************************************************
1203 : pnodepool(&node_pool_)
1204 , pbuckets(pbuckets_)
1205 , number_of_buckets(number_of_buckets_)
1206 , first(pbuckets)
1207 , last(pbuckets)
1208 , key_hash_function(key_hash_function_)
1209 , key_equal_function(key_equal_function_)
1210 {
1211 }
1212
1213 //*********************************************************************
1215 //*********************************************************************
1217 {
1218 if (!empty())
1219 {
1220 // For each bucket...
1221 for (size_t i = 0UL; i < number_of_buckets; ++i)
1222 {
1223 bucket_t& bucket = pbuckets[i];
1224
1225 if (!bucket.empty())
1226 {
1227 // For each item in the bucket...
1228 local_iterator it = bucket.begin();
1229
1230 while (it != bucket.end())
1231 {
1232 // Destroy the value contents.
1233 it->key.~value_type();
1234 ++it;
1235 ETL_DECREMENT_DEBUG_COUNT;
1236 }
1237
1238 // Now it's safe to clear the bucket.
1239 bucket.clear();
1240 }
1241 }
1242
1243 // Now it's safe to clear the entire pool in one go.
1244 pnodepool->release_all();
1245 }
1246
1247 first = pbuckets;
1248 last = first;
1249 }
1250
1251#if ETL_USING_CPP11
1252 //*************************************************************************
1254 //*************************************************************************
1255 void move(iterator b, iterator e)
1256 {
1257 while (b != e)
1258 {
1259 iterator temp = b;
1260 ++temp;
1261 insert(etl::move(*b));
1262 b = temp;
1263 }
1264 }
1265#endif
1266
1267 private:
1268
1269 //*************************************************************************
1271 //*************************************************************************
1272 node_t* allocate_data_node()
1273 {
1274 node_t* (etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1275 return (pnodepool->*func)();
1276 }
1277
1278 //*********************************************************************
1280 //*********************************************************************
1281 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1282 {
1283 if (size() == 1)
1284 {
1285 first = pbucket;
1286 last = pbucket;
1287 }
1288 else
1289 {
1290 if (pbucket < first)
1291 {
1292 first = pbucket;
1293 }
1294 else if (pbucket > last)
1295 {
1296 last = pbucket;
1297 }
1298 }
1299 }
1300
1301 //*********************************************************************
1303 //*********************************************************************
1304 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1305 {
1306 if (empty())
1307 {
1308 first = pbuckets;
1309 last = pbuckets;
1310 }
1311 else
1312 {
1313 if (pbucket == first)
1314 {
1315 // We erased the first so, we need to search again from where we erased.
1316 while (first->empty())
1317 {
1318 ++first;
1319 }
1320 }
1321 else if (pbucket == last)
1322 {
1323 // We erased the last, so we need to search again. Start from the first, go no further than the current last.
1324 pbucket = first;
1325 bucket_t* pend = last;
1326
1327 last = first;
1328
1329 while (pbucket != pend)
1330 {
1331 if (!pbucket->empty())
1332 {
1333 last = pbucket;
1334 }
1335
1336 ++pbucket;
1337 }
1338 }
1339 }
1340 }
1341
1342 //*********************************************************************
1344 //*********************************************************************
1345 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1346 {
1347 local_iterator inext = bucket.erase_after(iprevious); // Unlink from the bucket.
1348 icurrent->key.~value_type(); // Destroy the value.
1349 pnodepool->release(&*icurrent); // Release it back to the pool.
1350 adjust_first_last_markers_after_erase(&bucket);
1351 ETL_DECREMENT_DEBUG_COUNT;
1352
1353 return inext;
1354 }
1355
1356 // Disable copy construction.
1357 iunordered_multiset(const iunordered_multiset&);
1358
1360 pool_t* pnodepool;
1361
1363 bucket_t* pbuckets;
1364
1366 const size_t number_of_buckets;
1367
1369 bucket_t* first;
1370 bucket_t* last;
1371
1373 hasher key_hash_function;
1374
1376 key_equal key_equal_function;
1377
1379 ETL_DECLARE_DEBUG_COUNT;
1380
1381 //*************************************************************************
1383 //*************************************************************************
1384#if defined(ETL_POLYMORPHIC_UNORDERED_MULTISET) || defined(ETL_POLYMORPHIC_CONTAINERS)
1385 public:
1386 virtual ~iunordered_multiset()
1387 {
1388 }
1389#else
1390 protected:
1392 {
1393 }
1394#endif
1395 };
1396
1397 //***************************************************************************
1403 //***************************************************************************
1404 template <typename TKey, typename THash, typename TKeyEqual>
1407 {
1408 const bool sizes_match = (lhs.size() == rhs.size());
1409 bool elements_match = true;
1410
1412
1413 if (sizes_match)
1414 {
1415 itr_t l_begin = lhs.begin();
1416 itr_t l_end = lhs.end();
1417
1418 while ((l_begin != l_end) && elements_match)
1419 {
1420 const TKey l_value = *l_begin;
1421
1422 // See if the lhs keys exist in the rhs.
1423 ETL_OR_STD::pair<itr_t, itr_t> l_range = lhs.equal_range(l_value);
1424 ETL_OR_STD::pair<itr_t, itr_t> r_range = rhs.equal_range(l_value);
1425
1426 if (r_range.first != rhs.end())
1427 {
1428 bool distance_match = (etl::distance(l_range.first, l_range.second) == etl::distance(r_range.first, r_range.second));
1429
1430 if (distance_match)
1431 {
1433 }
1434 else
1435 {
1436 elements_match = false;
1437 }
1438 }
1439 else
1440 {
1441 elements_match = false;
1442 }
1443
1444 ++l_begin;
1445 }
1446 }
1447
1448 return (sizes_match && elements_match);
1449 }
1450
1451 //***************************************************************************
1457 //***************************************************************************
1458 template <typename TKey, typename THash, typename TKeyEqual>
1464
1465 //*************************************************************************
1467 //*************************************************************************
1468 template <typename TKey, const size_t MAX_SIZE_, size_t MAX_BUCKETS_ = MAX_SIZE_, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
1469 class unordered_multiset : public etl::iunordered_multiset<TKey, THash, TKeyEqual>
1470 {
1471 private:
1472
1474
1475 public:
1476
1477 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1478 static ETL_CONSTANT size_t MAX_BUCKETS = MAX_BUCKETS_;
1479
1480
1481 //*************************************************************************
1483 //*************************************************************************
1484 unordered_multiset(const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1485 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1486 {
1487 }
1488
1489 //*************************************************************************
1491 //*************************************************************************
1493 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1494 {
1495 // Skip if doing self assignment
1496 if (this != &other)
1497 {
1498 base::assign(other.cbegin(), other.cend());
1499 }
1500 }
1501
1502
1503#if ETL_USING_CPP11
1504 //*************************************************************************
1506 //*************************************************************************
1508 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1509 {
1510 // Skip if doing self assignment
1511 if (this != &other)
1512 {
1513 base::move(other.begin(), other.end());
1514 }
1515 }
1516#endif
1517
1518 //*************************************************************************
1523 //*************************************************************************
1524 template <typename TIterator>
1526 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1527 {
1528 base::assign(first_, last_);
1529 }
1530
1531#if ETL_HAS_INITIALIZER_LIST
1532 //*************************************************************************
1534 //*************************************************************************
1535 unordered_multiset(std::initializer_list<TKey> init, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1536 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1537 {
1538 base::assign(init.begin(), init.end());
1539 }
1540#endif
1541
1542 //*************************************************************************
1544 //*************************************************************************
1546 {
1547 base::initialise();
1548 }
1549
1550 //*************************************************************************
1552 //*************************************************************************
1554 {
1555 base::operator =(rhs);
1556
1557 return *this;
1558 }
1559
1560#if ETL_USING_CPP11
1561 //*************************************************************************
1563 //*************************************************************************
1565 {
1566 base::operator =(etl::move(rhs));
1567
1568 return *this;
1569 }
1570#endif
1571
1572 private:
1573
1576
1578 typename base::bucket_t buckets[MAX_BUCKETS_];
1579 };
1580
1581 //*************************************************************************
1583 //*************************************************************************
1584#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1585 template <typename... T>
1586 unordered_multiset(T...) -> unordered_multiset<etl::nth_type_t<0, T...>, sizeof...(T)>;
1587#endif
1588
1589 //*************************************************************************
1591 //*************************************************************************
1592#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1593 template <typename TKey, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey>, typename... T>
1594 constexpr auto make_unordered_multiset(T&&... keys) -> etl::unordered_multiset<TKey, sizeof...(T), sizeof...(T), THash, TKeyEqual>
1595 {
1596 return { etl::forward<T>(keys)... };
1597 }
1598#endif
1599}
1600
1601#endif
Definition unordered_multiset.h:323
Definition unordered_multiset.h:181
A templated unordered_multiset implementation that uses a fixed size buffer.
Definition unordered_multiset.h:1470
unordered_multiset(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_multiset.h:1484
~unordered_multiset()
Destructor.
Definition unordered_multiset.h:1545
unordered_multiset(const unordered_multiset &other)
Copy constructor.
Definition unordered_multiset.h:1492
unordered_multiset(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_multiset.h:1525
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
~iunordered_multiset()
Destructor.
Definition unordered_multiset.h:1391
ETL_OR_STD::pair< iterator, bool > insert(const_reference key)
Definition unordered_multiset.h:650
size_t available() const
Definition unordered_multiset.h:1130
const_iterator cend() const
Definition unordered_multiset.h:550
iunordered_multiset & operator=(const iunordered_multiset &rhs)
Assignment operator.
Definition unordered_multiset.h:1165
const_iterator begin() const
Definition unordered_multiset.h:487
size_t erase(key_parameter_t key)
Definition unordered_multiset.h:820
void initialise()
Initialise the unordered_multiset.
Definition unordered_multiset.h:1216
iterator end()
Definition unordered_multiset.h:532
size_type max_size() const
Gets the maximum possible size of the unordered_multiset.
Definition unordered_multiset.h:1097
iterator insert(const_iterator, const_reference key)
Definition unordered_multiset.h:793
const_local_iterator end(size_t i) const
Definition unordered_multiset.h:568
size_type get_bucket_index(key_parameter_t key) const
Definition unordered_multiset.h:586
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(key_parameter_t key) const
Definition unordered_multiset.h:1068
const_iterator find(key_parameter_t key) const
Definition unordered_multiset.h:1005
local_iterator begin(size_t i)
Definition unordered_multiset.h:505
void assign(TIterator first_, TIterator last_)
Definition unordered_multiset.h:628
const_iterator cbegin() const
Definition unordered_multiset.h:496
iunordered_multiset(pool_t &node_pool_, bucket_t *pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
Constructor.
Definition unordered_multiset.h:1202
const_iterator end() const
Definition unordered_multiset.h:541
size_type bucket_size(key_parameter_t key) const
Definition unordered_multiset.h:595
void insert(TIterator first_, TIterator last_)
Definition unordered_multiset.h:806
void clear()
Clears the unordered_multiset.
Definition unordered_multiset.h:935
const_local_iterator cend(size_t i) const
Definition unordered_multiset.h:577
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_multiset.h:881
const_local_iterator cbegin(size_t i) const
Definition unordered_multiset.h:523
iterator find(key_parameter_t key)
Definition unordered_multiset.h:971
iterator begin()
Definition unordered_multiset.h:478
iterator erase(const_iterator ielement)
Definition unordered_multiset.h:853
key_equal key_eq() const
Definition unordered_multiset.h:1157
local_iterator end(size_t i)
Definition unordered_multiset.h:559
const_local_iterator begin(size_t i) const
Definition unordered_multiset.h:514
size_type max_bucket_count() const
Definition unordered_multiset.h:606
size_type size() const
Gets the size of the unordered_multiset.
Definition unordered_multiset.h:1089
hasher hash_function() const
Definition unordered_multiset.h:1148
size_type bucket_count() const
Definition unordered_multiset.h:615
size_type capacity() const
Gets the maximum possible size of the unordered_multiset.
Definition unordered_multiset.h:1105
size_t count(key_parameter_t key) const
Definition unordered_multiset.h:945
bool full() const
Checks to see if the unordered_multiset is full.
Definition unordered_multiset.h:1121
float load_factor() const
Definition unordered_multiset.h:1139
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition unordered_multiset.h:1042
bool empty() const
Checks to see if the unordered_multiset is empty.
Definition unordered_multiset.h:1113
Definition unordered_multiset.h:126
Definition unordered_multiset.h:69
Definition unordered_multiset.h:83
Definition unordered_multiset.h:110
Definition unordered_multiset.h:97
bitset_ext
Definition absolute.h:38
Definition compare.h:51
iterator
Definition iterator.h:399
Definition unordered_multiset.h:149
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