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
55
56#include <stddef.h>
57
58//*****************************************************************************
62//*****************************************************************************
63
64namespace etl
65{
66 //***************************************************************************
69 //***************************************************************************
79
80 //***************************************************************************
83 //***************************************************************************
85 {
86 public:
87
89 : etl::unordered_multiset_exception(ETL_ERROR_TEXT("unordered_multiset:full", ETL_UNORDERED_MULTISET_FILE_ID"A"), file_name_, line_number_)
90 {
91 }
92 };
93
94 //***************************************************************************
97 //***************************************************************************
99 {
100 public:
101
103 : etl::unordered_multiset_exception(ETL_ERROR_TEXT("unordered_multiset:range", ETL_UNORDERED_MULTISET_FILE_ID"B"), file_name_, line_number_)
104 {}
105 };
106
107 //***************************************************************************
110 //***************************************************************************
112 {
113 public:
114
116 : etl::unordered_multiset_exception(ETL_ERROR_TEXT("unordered_multiset:iterator", ETL_UNORDERED_MULTISET_FILE_ID"C"), file_name_, line_number_)
117 {
118 }
119 };
120
121 //***************************************************************************
125 //***************************************************************************
126 template <typename TKey, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
128 {
129 public:
130
131 typedef TKey value_type;
132 typedef TKey key_type;
133 typedef THash hasher;
134 typedef TKeyEqual key_equal;
135 typedef value_type& reference;
136 typedef const value_type& const_reference;
137#if ETL_USING_CPP11
139#endif
140 typedef value_type* pointer;
141 typedef const value_type* const_pointer;
142 typedef size_t size_type;
143
144 typedef const TKey& key_parameter_t;
145
147
148 //*********************************************************************
149 // The nodes that store the elements.
150 struct node_t : public link_t
151 {
153 : key(key_)
154 {
155 }
156
157 value_type key;
158 };
159
160 friend bool operator ==(const node_t& lhs, const node_t& rhs)
161 {
162 return (lhs.key == rhs.key);
163 }
164
165 friend bool operator !=(const node_t& lhs, const node_t& rhs)
166 {
167 return !(lhs == rhs);
168 }
169
170 protected:
171
173 typedef etl::ipool pool_t;
174
175 public:
176
177 // Local iterators iterate over one bucket.
178 typedef typename bucket_t::iterator local_iterator;
179 typedef typename bucket_t::const_iterator const_local_iterator;
180
181 //*********************************************************************
182 class iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, TKey>
183 {
184 public:
185
188 typedef typename iunordered_multiset::hasher hasher;
192 typedef typename iunordered_multiset::pointer pointer;
195
196 friend class iunordered_multiset;
197 friend class const_iterator;
198
199 //*********************************
200 iterator()
201 {
202 }
203
204 //*********************************
205 iterator(const iterator& other)
206 : pbuckets_end(other.pbuckets_end)
207 , pbucket(other.pbucket)
208 , inode(other.inode)
209 {
210 }
211
212 //*********************************
214 {
215 ++inode;
216
217 // The end of this node list?
218 if (inode == pbucket->end())
219 {
220 // Search for the next non-empty bucket.
221 ++pbucket;
222 while ((pbucket != pbuckets_end) && (pbucket->empty()))
223 {
224 ++pbucket;
225 }
226
227 // If not past the end, get the first node in the bucket.
228 if (pbucket != pbuckets_end)
229 {
230 inode = pbucket->begin();
231 }
232 }
233
234 return *this;
235 }
236
237 //*********************************
239 {
240 iterator temp(*this);
241 operator++();
242 return temp;
243 }
244
245 //*********************************
247 {
248 pbuckets_end = other.pbuckets_end;
249 pbucket = other.pbucket;
250 inode = other.inode;
251 return *this;
252 }
253
254 //*********************************
255 reference operator *() const
256 {
257 return inode->key;
258 }
259
260 //*********************************
261 pointer operator &() const
262 {
263 return &(inode->key);
264 }
265
266 //*********************************
267 pointer operator ->() const
268 {
269 return &(inode->key);
270 }
271
272 //*********************************
273 friend bool operator == (const iterator& lhs, const iterator& rhs)
274 {
275 return lhs.compare(rhs);
276 }
277
278 //*********************************
279 friend bool operator != (const iterator& lhs, const iterator& rhs)
280 {
281 return !(lhs == rhs);
282 }
283
284 private:
285
286 //*********************************
288 : pbuckets_end(pbuckets_end_)
289 , pbucket(pbucket_)
290 , inode(inode_)
291 {
292 }
293
294 //*********************************
295 bool compare(const iterator& rhs) const
296 {
297 return rhs.inode == inode;
298 }
299
300 //*********************************
301 bucket_t& get_bucket()
302 {
303 return *pbucket;
304 }
305
306 //*********************************
307 bucket_t*& get_bucket_list_iterator()
308 {
309 return pbucket;
310 }
311
312 //*********************************
313 local_iterator get_local_iterator()
314 {
315 return inode;
316 }
317
318 bucket_t* pbuckets_end;
319 bucket_t* pbucket;
320 local_iterator inode;
321 };
322
323 //*********************************************************************
324 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const TKey>
325 {
326 public:
327
330 typedef typename iunordered_multiset::hasher hasher;
334 typedef typename iunordered_multiset::pointer pointer;
337
338 friend class iunordered_multiset;
339 friend class iterator;
340
341 //*********************************
343 {
344 }
345
346 //*********************************
348 : pbuckets_end(other.pbuckets_end)
349 , pbucket(other.pbucket)
350 , inode(other.inode)
351 {
352 }
353
354 //*********************************
356 : pbuckets_end(other.pbuckets_end)
357 , pbucket(other.pbucket)
358 , inode(other.inode)
359 {
360 }
361
362 //*********************************
364 {
365 ++inode;
366
367 // The end of this node list?
368 if (inode == pbucket->end())
369 {
370 // Search for the next non-empty bucket.
371
372 ++pbucket;
373 while ((pbucket != pbuckets_end) && (pbucket->empty()))
374 {
375 ++pbucket;
376 }
377
378 // If not past the end, get the first node in the bucket.
379 if (pbucket != pbuckets_end)
380 {
381 inode = pbucket->begin();
382 }
383 }
384
385 return *this;
386 }
387
388 //*********************************
390 {
391 const_iterator temp(*this);
392 operator++();
393 return temp;
394 }
395
396 //*********************************
398 {
399 pbuckets_end = other.pbuckets_end;
400 pbucket = other.pbucket;
401 inode = other.inode;
402 return *this;
403 }
404
405 //*********************************
407 {
408 return inode->key;
409 }
410
411 //*********************************
413 {
414 return &(inode->key);
415 }
416
417 //*********************************
419 {
420 return &(inode->key);
421 }
422
423 //*********************************
424 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
425 {
426 return lhs.compare(rhs);
427 }
428
429 //*********************************
430 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
431 {
432 return !(lhs == rhs);
433 }
434
435 private:
436
437 //*********************************
439 : pbuckets_end(pbuckets_end_)
440 , pbucket(pbucket_)
441 , inode(inode_)
442 {
443 }
444
445 //*********************************
446 bool compare(const const_iterator& rhs) const
447 {
448 return rhs.inode == inode;
449 }
450
451 //*********************************
452 bucket_t& get_bucket()
453 {
454 return *pbucket;
455 }
456
457 //*********************************
458 bucket_t*& get_bucket_list_iterator()
459 {
460 return pbucket;
461 }
462
463 //*********************************
464 local_iterator get_local_iterator()
465 {
466 return inode;
467 }
468
469 bucket_t* pbuckets_end;
470 bucket_t* pbucket;
471 local_iterator inode;
472 };
473
474 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
475
476 //*********************************************************************
479 //*********************************************************************
481 {
482 return iterator((pbuckets + number_of_buckets), first, first->begin());
483 }
484
485 //*********************************************************************
488 //*********************************************************************
490 {
491 return const_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 //*********************************************************************
507 local_iterator begin(size_t i)
508 {
509 return pbuckets[i].begin();
510 }
511
512 //*********************************************************************
515 //*********************************************************************
516 const_local_iterator begin(size_t i) const
517 {
518 return pbuckets[i].cbegin();
519 }
520
521 //*********************************************************************
524 //*********************************************************************
525 const_local_iterator cbegin(size_t i) const
526 {
527 return pbuckets[i].cbegin();
528 }
529
530 //*********************************************************************
533 //*********************************************************************
535 {
536 return iterator((pbuckets + number_of_buckets), last, last->end());
537 }
538
539 //*********************************************************************
542 //*********************************************************************
544 {
545 return const_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 //*********************************************************************
561 local_iterator end(size_t i)
562 {
563 return pbuckets[i].end();
564 }
565
566 //*********************************************************************
569 //*********************************************************************
570 const_local_iterator end(size_t i) const
571 {
572 return pbuckets[i].cend();
573 }
574
575 //*********************************************************************
578 //*********************************************************************
579 const_local_iterator cend(size_t i) const
580 {
581 return pbuckets[i].cend();
582 }
583
584 //*********************************************************************
587 //*********************************************************************
589 {
590 return key_hash_function(key) % number_of_buckets;
591 }
592
593#if ETL_USING_CPP11
594 //*********************************************************************
597 //*********************************************************************
599 size_type get_bucket_index(const K& key) const
600 {
601 return key_hash_function(key) % number_of_buckets;
602 }
603#endif
604
605 //*********************************************************************
608 //*********************************************************************
610 {
611 size_t index = bucket(key);
612
613 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
614 }
615
616#if ETL_USING_CPP11
617 //*********************************************************************
620 //*********************************************************************
622 size_type bucket_size(const K& key) const
623 {
624 size_t index = bucket(key);
625
626 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
627 }
628#endif
629
630 //*********************************************************************
633 //*********************************************************************
635 {
636 return number_of_buckets;
637 }
638
639 //*********************************************************************
642 //*********************************************************************
644 {
645 return number_of_buckets;
646 }
647
648 //*********************************************************************
654 //*********************************************************************
655 template <typename TIterator>
657 {
658#if ETL_IS_DEBUG_BUILD
659 difference_type d = etl::distance(first_, last_);
660 ETL_ASSERT(d >= 0, ETL_ERROR(unordered_multiset_iterator));
661 ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_multiset_full));
662#endif
663
664 clear();
665
666 while (first_ != last_)
667 {
668 insert(*first_);
669 ++first_;
670 }
671 }
672
673 //*********************************************************************
677 //*********************************************************************
678 ETL_OR_STD::pair<iterator, bool> insert(const_reference key)
679 {
680 ETL_OR_STD::pair<iterator, bool> result(end(), false);
681
683
684 // Get the hash index.
685 size_t index = get_bucket_index(key);
686
687 // Get the bucket & bucket iterator.
688 bucket_t* pbucket = pbuckets + index;
689 bucket_t& bucket = *pbucket;
690
691 // The first one in the bucket?
692 if (bucket.empty())
693 {
694 // Get a new node.
695 node_t* node = allocate_data_node();
696 node->clear();
697 ::new (&node->key) value_type(key);
698 ETL_INCREMENT_DEBUG_COUNT;
699
700 // Just add the pointer to the bucket;
701 bucket.insert_after(bucket.before_begin(), *node);
702 adjust_first_last_markers_after_insert(&bucket);
703
704 result.first = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
705 result.second = true;
706 }
707 else
708 {
709 // Step though the bucket looking for a place to insert.
710 local_iterator inode_previous = bucket.before_begin();
711 local_iterator inode = bucket.begin();
712
713 while (inode != bucket.end())
714 {
715 // Do we already have this key?
716 if (key_equal_function(inode->key, key))
717 {
718 break;
719 }
720
722 ++inode;
723 }
724
725 // Get a new node.
726 node_t* node = allocate_data_node();
727 node->clear();
728 ::new (&node->key) value_type(key);
729 ETL_INCREMENT_DEBUG_COUNT;
730
731 // Add the node to the end of the bucket;
732 bucket.insert_after(inode_previous, *node);
733 adjust_first_last_markers_after_insert(&bucket);
735
736 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
737 result.second = true;
738 }
739
740 return result;
741 }
742
743#if ETL_USING_CPP11
744 //*********************************************************************
748 //*********************************************************************
750 ETL_OR_STD::pair<iterator, bool> insert(const K& key)
751 {
752 ETL_OR_STD::pair<iterator, bool> result(end(), false);
753
755
756 // Get the hash index.
757 size_t index = get_bucket_index(key);
758
759 // Get the bucket & bucket iterator.
760 bucket_t* pbucket = pbuckets + index;
761 bucket_t& bucket = *pbucket;
762
763 // The first one in the bucket?
764 if (bucket.empty())
765 {
766 // Get a new node.
767 node_t* node = allocate_data_node();
768 node->clear();
769 ::new (&node->key) value_type(key);
770 ETL_INCREMENT_DEBUG_COUNT;
771
772 // Just add the pointer to the bucket;
773 bucket.insert_after(bucket.before_begin(), *node);
774 adjust_first_last_markers_after_insert(&bucket);
775
776 result.first = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
777 result.second = true;
778 }
779 else
780 {
781 // Step though the bucket looking for a place to insert.
782 local_iterator inode_previous = bucket.before_begin();
783 local_iterator inode = bucket.begin();
784
785 while (inode != bucket.end())
786 {
787 // Do we already have this key?
788 if (key_equal_function(inode->key, key))
789 {
790 break;
791 }
792
793 ++inode_previous;
794 ++inode;
795 }
796
797 // Get a new node.
798 node_t* node = allocate_data_node();
799 node->clear();
800 ::new (&node->key) value_type(key);
801 ETL_INCREMENT_DEBUG_COUNT;
802
803 // Add the node to the end of the bucket;
804 bucket.insert_after(inode_previous, *node);
805 adjust_first_last_markers_after_insert(&bucket);
806 ++inode_previous;
807
808 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
809 result.second = true;
810 }
811
812 return result;
813 }
814#endif
815
816#if ETL_USING_CPP11
817 //*********************************************************************
821 //*********************************************************************
822 ETL_OR_STD::pair<iterator, bool> insert(rvalue_reference key)
823 {
824 ETL_OR_STD::pair<iterator, bool> result(end(), false);
825
826 ETL_ASSERT(!full(), ETL_ERROR(unordered_multiset_full));
827
828 // Get the hash index.
829 size_t index = get_bucket_index(key);
830
831 // Get the bucket & bucket iterator.
832 bucket_t* pbucket = pbuckets + index;
833 bucket_t& bucket = *pbucket;
834
835 // The first one in the bucket?
836 if (bucket.empty())
837 {
838 // Get a new node.
839 node_t* node = allocate_data_node();
840 node->clear();
841 ::new (&node->key) value_type(etl::move(key));
842 ETL_INCREMENT_DEBUG_COUNT;
843
844 // Just add the pointer to the bucket;
845 bucket.insert_after(bucket.before_begin(), *node);
846 adjust_first_last_markers_after_insert(&bucket);
847
848 result.first = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
849 result.second = true;
850 }
851 else
852 {
853 // Step though the bucket looking for a place to insert.
854 local_iterator inode_previous = bucket.before_begin();
855 local_iterator inode = bucket.begin();
856
857 while (inode != bucket.end())
858 {
859 // Do we already have this key?
860 if (key_equal_function(inode->key, key))
861 {
862 break;
863 }
864
865 ++inode_previous;
866 ++inode;
867 }
868
869 // Get a new node.
870 node_t* node = allocate_data_node();
871 node->clear();
872 ::new (&node->key) value_type(etl::move(key));
873 ETL_INCREMENT_DEBUG_COUNT;
874
875 // Add the node to the end of the bucket;
876 bucket.insert_after(inode_previous, *node);
877 adjust_first_last_markers_after_insert(&bucket);
878 ++inode_previous;
879
880 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
881 result.second = true;
882 }
883
884 return result;
885 }
886#endif
887
888 //*********************************************************************
893 //*********************************************************************
895 {
896 return insert(key).first;
897 }
898
899 //*********************************************************************
905 //*********************************************************************
906 template <class TIterator>
908 {
909 while (first_ != last_)
910 {
911 insert(*first_);
912 ++first_;
913 }
914 }
915
916 //*********************************************************************
920 //*********************************************************************
922 {
923 size_t n = 0UL;
924 size_t bucket_id = get_bucket_index(key);
925
926 bucket_t& bucket = pbuckets[bucket_id];
927
928 local_iterator iprevious = bucket.before_begin();
929 local_iterator icurrent = bucket.begin();
930
931 while (icurrent != bucket.end())
932 {
933 if (key_equal_function(icurrent->key, key))
934 {
935 delete_data_node(iprevious, icurrent, bucket);
936 ++n;
938 }
939 else
940 {
941 ++iprevious;
942 }
943
944 ++icurrent;
945 }
946
947 return n;
948 }
949
950#if ETL_USING_CPP11
951 //*********************************************************************
955 //*********************************************************************
957 size_t erase(const K& key)
958 {
959 size_t n = 0UL;
960 size_t bucket_id = get_bucket_index(key);
961
962 bucket_t& bucket = pbuckets[bucket_id];
963
964 local_iterator iprevious = bucket.before_begin();
965 local_iterator icurrent = bucket.begin();
966
967 while (icurrent != bucket.end())
968 {
969 if (key_equal_function(icurrent->key, key))
970 {
971 delete_data_node(iprevious, icurrent, bucket);
972 ++n;
974 }
975 else
976 {
977 ++iprevious;
978 }
979
980 ++icurrent;
981 }
982
983 return n;
984 }
985#endif
986
987 //*********************************************************************
990 //*********************************************************************
992 {
993 // Make a note of the next one.
994 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
995 ++inext;
996
997 bucket_t& bucket = ielement.get_bucket();
998 local_iterator iprevious = bucket.before_begin();
999 local_iterator icurrent = ielement.get_local_iterator();
1000
1001 // Find the node previous to the one we're interested in.
1002 while (iprevious->etl_next != &*icurrent)
1003 {
1004 ++iprevious;
1005 }
1006
1007 delete_data_node(iprevious, icurrent, bucket);
1008
1009 return inext;
1010 }
1011
1012 //*********************************************************************
1018 //*********************************************************************
1020 {
1021 // Erasing everything?
1022 if ((first_ == begin()) && (last_ == end()))
1023 {
1024 clear();
1025 return end();
1026 }
1027
1028 // Get the starting point.
1029 bucket_t* pbucket = first_.get_bucket_list_iterator();
1030 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
1031 local_iterator iprevious = pbucket->before_begin();
1032 local_iterator icurrent = first_.get_local_iterator();
1033 local_iterator iend = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
1034
1035 // Find the node previous to the first one.
1036 while (iprevious->etl_next != &*icurrent)
1037 {
1038 ++iprevious;
1039 }
1040
1041 // Remember the item before the first erased one.
1042 iterator ibefore_erased = iterator((pbuckets + number_of_buckets), pbucket, iprevious);
1043
1044 // Until we reach the end.
1045 while ((icurrent != iend) || (pbucket != pend_bucket))
1046 {
1047 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
1048
1049 // Have we not reached the end?
1050 if ((icurrent != iend) || (pbucket != pend_bucket))
1051 {
1052 // At the end of this bucket?
1053 if ((icurrent == pbucket->end()))
1054 {
1055 // Find the next non-empty one.
1056 do
1057 {
1058 ++pbucket;
1059 } while (pbucket->empty());
1060
1061 iprevious = pbucket->before_begin();
1062 icurrent = pbucket->begin();
1063 }
1064 }
1065 }
1066
1067 return ++ibefore_erased;
1068 }
1069
1070 //*************************************************************************
1072 //*************************************************************************
1073 void clear()
1074 {
1075 initialise();
1076 }
1077
1078 //*********************************************************************
1082 //*********************************************************************
1083 size_t count(key_parameter_t key) const
1084 {
1085 size_t n = 0UL;
1086 const_iterator f = find(key);
1087 const_iterator l = f;
1088
1089 if (l != end())
1090 {
1091 ++l;
1092 ++n;
1093
1094 while ((l != end()) && key_equal_function(key, *l))
1095 {
1096 ++l;
1097 ++n;
1098 }
1099 }
1100
1101 return n;
1102 }
1103
1104#if ETL_USING_CPP11
1105 //*********************************************************************
1109 //*********************************************************************
1111 size_t count(const K& key) const
1112 {
1113 size_t n = 0UL;
1114 const_iterator f = find(key);
1115 const_iterator l = f;
1116
1117 if (l != end())
1118 {
1119 ++l;
1120 ++n;
1121
1122 while ((l != end()) && key_equal_function(key, *l))
1123 {
1124 ++l;
1125 ++n;
1126 }
1127 }
1128
1129 return n;
1130 }
1131#endif
1132
1133 //*********************************************************************
1137 //*********************************************************************
1139 {
1140 size_t index = get_bucket_index(key);
1141
1142 bucket_t* pbucket = pbuckets + index;
1143 bucket_t& bucket = *pbucket;
1144
1145 // Is the bucket not empty?
1146 if (!bucket.empty())
1147 {
1148 // Step though the list until we find the end or an equivalent key.
1149 local_iterator inode = bucket.begin();
1150 local_iterator iend = bucket.end();
1151
1152 while (inode != iend)
1153 {
1154 // Do we have this one?
1155 if (key_equal_function(key, inode->key))
1156 {
1157 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1158 }
1159
1160 ++inode;
1161 }
1162 }
1163
1164 return end();
1165 }
1166
1167#if ETL_USING_CPP11
1168 //*********************************************************************
1172 //*********************************************************************
1174 iterator find(const K& key)
1175 {
1176 size_t index = get_bucket_index(key);
1177
1178 bucket_t* pbucket = pbuckets + index;
1179 bucket_t& bucket = *pbucket;
1180
1181 // Is the bucket not empty?
1182 if (!bucket.empty())
1183 {
1184 // Step though the list until we find the end or an equivalent key.
1185 local_iterator inode = bucket.begin();
1186 local_iterator iend = bucket.end();
1187
1188 while (inode != iend)
1189 {
1190 // Do we have this one?
1191 if (key_equal_function(key, inode->key))
1192 {
1193 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1194 }
1195
1196 ++inode;
1197 }
1198 }
1199
1200 return end();
1201 }
1202#endif
1203
1204 //*********************************************************************
1208 //*********************************************************************
1210 {
1211 size_t index = get_bucket_index(key);
1212
1213 bucket_t* pbucket = pbuckets + index;
1214 bucket_t& bucket = *pbucket;
1215
1216 // Is the bucket not empty?
1217 if (!bucket.empty())
1218 {
1219 // Step though the list until we find the end or an equivalent key.
1220 local_iterator inode = bucket.begin();
1221 local_iterator iend = bucket.end();
1222
1223 while (inode != iend)
1224 {
1225 // Do we have this one?
1226 if (key_equal_function(key, inode->key))
1227 {
1228 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1229 }
1230
1231 ++inode;
1232 }
1233 }
1234
1235 return end();
1236 }
1237
1238#if ETL_USING_CPP11
1239 //*********************************************************************
1243 //*********************************************************************
1245 const_iterator find(const K& key) const
1246 {
1247 size_t index = get_bucket_index(key);
1248
1249 bucket_t* pbucket = pbuckets + index;
1250 bucket_t& bucket = *pbucket;
1251
1252 // Is the bucket not empty?
1253 if (!bucket.empty())
1254 {
1255 // Step though the list until we find the end or an equivalent key.
1256 local_iterator inode = bucket.begin();
1257 local_iterator iend = bucket.end();
1258
1259 while (inode != iend)
1260 {
1261 // Do we have this one?
1262 if (key_equal_function(key, inode->key))
1263 {
1264 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1265 }
1266
1267 ++inode;
1268 }
1269 }
1270
1271 return end();
1272 }
1273#endif
1274
1275 //*********************************************************************
1282 //*********************************************************************
1283 ETL_OR_STD::pair<iterator, iterator> equal_range(key_parameter_t key)
1284 {
1285 iterator f = find(key);
1286 iterator l = f;
1287
1288 if (l != end())
1289 {
1290 ++l;
1291
1292 while ((l != end()) && key_equal_function(key, *l))
1293 {
1294 ++l;
1295 }
1296 }
1297
1298 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1299 }
1300
1301#if ETL_USING_CPP11
1302 //*********************************************************************
1309 //*********************************************************************
1311 ETL_OR_STD::pair<iterator, iterator> equal_range(const K& key)
1312 {
1313 iterator f = find(key);
1314 iterator l = f;
1315
1316 if (l != end())
1317 {
1318 ++l;
1319
1320 while ((l != end()) && key_equal_function(key, *l))
1321 {
1322 ++l;
1323 }
1324 }
1325
1326 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1327 }
1328#endif
1329
1330 //*********************************************************************
1337 //*********************************************************************
1338 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
1339 {
1340 const_iterator f = find(key);
1341 const_iterator l = f;
1342
1343 if (l != end())
1344 {
1345 ++l;
1346
1347 while ((l != end()) && key_equal_function(key, *l))
1348 {
1349 ++l;
1350 }
1351 }
1352
1353 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1354 }
1355
1356#if ETL_USING_CPP11
1357 //*********************************************************************
1364 //*********************************************************************
1366 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const K& key) const
1367 {
1368 const_iterator f = find(key);
1369 const_iterator l = f;
1370
1371 if (l != end())
1372 {
1373 ++l;
1374
1375 while ((l != end()) && key_equal_function(key, *l))
1376 {
1377 ++l;
1378 }
1379 }
1380
1381 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1382 }
1383#endif
1384
1385 //*************************************************************************
1387 //*************************************************************************
1389 {
1390 return pnodepool->size();
1391 }
1392
1393 //*************************************************************************
1395 //*************************************************************************
1397 {
1398 return pnodepool->max_size();
1399 }
1400
1401 //*************************************************************************
1403 //*************************************************************************
1405 {
1406 return pnodepool->max_size();
1407 }
1408
1409 //*************************************************************************
1411 //*************************************************************************
1412 bool empty() const
1413 {
1414 return pnodepool->empty();
1415 }
1416
1417 //*************************************************************************
1419 //*************************************************************************
1420 bool full() const
1421 {
1422 return pnodepool->full();
1423 }
1424
1425 //*************************************************************************
1428 //*************************************************************************
1429 size_t available() const
1430 {
1431 return pnodepool->available();
1432 }
1433
1434 //*************************************************************************
1437 //*************************************************************************
1438 float load_factor() const
1439 {
1440 return static_cast<float>(size()) / static_cast<float>(bucket_count());
1441 }
1442
1443 //*************************************************************************
1446 //*************************************************************************
1448 {
1449 return key_hash_function;
1450 }
1451
1452 //*************************************************************************
1455 //*************************************************************************
1457 {
1458 return key_equal_function;
1459 }
1460
1461 //*************************************************************************
1463 //*************************************************************************
1465 {
1466 // Skip if doing self assignment
1467 if (this != &rhs)
1468 {
1469 key_hash_function = rhs.hash_function();
1470 key_equal_function = rhs.key_eq();
1471 assign(rhs.cbegin(), rhs.cend());
1472 }
1473
1474 return *this;
1475 }
1476
1477#if ETL_USING_CPP11
1478 //*************************************************************************
1480 //*************************************************************************
1482 {
1483 // Skip if doing self assignment
1484 if (this != &rhs)
1485 {
1486 clear();
1487 key_hash_function = rhs.hash_function();
1488 key_equal_function = rhs.key_eq();
1489 move(rhs.begin(), rhs.end());
1490 }
1491
1492 return *this;
1493 }
1494#endif
1495
1496 //*************************************************************************
1498 //*************************************************************************
1500 {
1501 return find(key) != end();
1502 }
1503
1504#if ETL_USING_CPP11
1505 //*************************************************************************
1507 //*************************************************************************
1509 bool contains(const K& key) const
1510 {
1511 return find(key) != end();
1512 }
1513#endif
1514
1515 protected:
1516
1517 //*********************************************************************
1519 //*********************************************************************
1521 : pnodepool(&node_pool_)
1522 , pbuckets(pbuckets_)
1523 , number_of_buckets(number_of_buckets_)
1524 , first(pbuckets)
1525 , last(pbuckets)
1526 , key_hash_function(key_hash_function_)
1527 , key_equal_function(key_equal_function_)
1528 {
1529 }
1530
1531 //*********************************************************************
1533 //*********************************************************************
1535 {
1536 if (!empty())
1537 {
1538 // For each bucket...
1539 for (size_t i = 0UL; i < number_of_buckets; ++i)
1540 {
1541 bucket_t& bucket = pbuckets[i];
1542
1543 if (!bucket.empty())
1544 {
1545 // For each item in the bucket...
1546 local_iterator it = bucket.begin();
1547
1548 while (it != bucket.end())
1549 {
1550 // Destroy the value contents.
1551 it->key.~value_type();
1552 ++it;
1553 ETL_DECREMENT_DEBUG_COUNT;
1554 }
1555
1556 // Now it's safe to clear the bucket.
1557 bucket.clear();
1558 }
1559 }
1560
1561 // Now it's safe to clear the entire pool in one go.
1562 pnodepool->release_all();
1563 }
1564
1565 first = pbuckets;
1566 last = first;
1567 }
1568
1569#if ETL_USING_CPP11
1570 //*************************************************************************
1572 //*************************************************************************
1573 void move(iterator b, iterator e)
1574 {
1575 while (b != e)
1576 {
1577 iterator temp = b;
1578 ++temp;
1579 insert(etl::move(*b));
1580 b = temp;
1581 }
1582 }
1583#endif
1584
1585 private:
1586
1587 //*************************************************************************
1589 //*************************************************************************
1590 node_t* allocate_data_node()
1591 {
1592 node_t* (etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1593 return (pnodepool->*func)();
1594 }
1595
1596 //*********************************************************************
1598 //*********************************************************************
1599 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1600 {
1601 if (size() == 1)
1602 {
1603 first = pbucket;
1604 last = pbucket;
1605 }
1606 else
1607 {
1608 if (pbucket < first)
1609 {
1610 first = pbucket;
1611 }
1612 else if (pbucket > last)
1613 {
1614 last = pbucket;
1615 }
1616 }
1617 }
1618
1619 //*********************************************************************
1621 //*********************************************************************
1622 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1623 {
1624 if (empty())
1625 {
1626 first = pbuckets;
1627 last = pbuckets;
1628 }
1629 else
1630 {
1631 if (pbucket == first)
1632 {
1633 // We erased the first so, we need to search again from where we erased.
1634 while (first->empty())
1635 {
1636 ++first;
1637 }
1638 }
1639 else if (pbucket == last)
1640 {
1641 // We erased the last, so we need to search again. Start from the first, go no further than the current last.
1642 pbucket = first;
1643 bucket_t* pend = last;
1644
1645 last = first;
1646
1647 while (pbucket != pend)
1648 {
1649 if (!pbucket->empty())
1650 {
1651 last = pbucket;
1652 }
1653
1654 ++pbucket;
1655 }
1656 }
1657 }
1658 }
1659
1660 //*********************************************************************
1662 //*********************************************************************
1663 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1664 {
1665 local_iterator inext = bucket.erase_after(iprevious); // Unlink from the bucket.
1666 icurrent->key.~value_type(); // Destroy the value.
1667 pnodepool->release(&*icurrent); // Release it back to the pool.
1668 adjust_first_last_markers_after_erase(&bucket);
1669 ETL_DECREMENT_DEBUG_COUNT;
1670
1671 return inext;
1672 }
1673
1674 // Disable copy construction.
1675 iunordered_multiset(const iunordered_multiset&);
1676
1678 pool_t* pnodepool;
1679
1681 bucket_t* pbuckets;
1682
1684 const size_t number_of_buckets;
1685
1687 bucket_t* first;
1688 bucket_t* last;
1689
1691 hasher key_hash_function;
1692
1694 key_equal key_equal_function;
1695
1697 ETL_DECLARE_DEBUG_COUNT;
1698
1699 //*************************************************************************
1701 //*************************************************************************
1702#if defined(ETL_POLYMORPHIC_UNORDERED_MULTISET) || defined(ETL_POLYMORPHIC_CONTAINERS)
1703 public:
1704 virtual ~iunordered_multiset()
1705 {
1706 }
1707#else
1708 protected:
1710 {
1711 }
1712#endif
1713 };
1714
1715 //***************************************************************************
1721 //***************************************************************************
1722 template <typename TKey, typename THash, typename TKeyEqual>
1725 {
1726 const bool sizes_match = (lhs.size() == rhs.size());
1727 bool elements_match = true;
1728
1730
1731 if (sizes_match)
1732 {
1733 itr_t l_begin = lhs.begin();
1734 itr_t l_end = lhs.end();
1735
1736 while ((l_begin != l_end) && elements_match)
1737 {
1738 const TKey l_value = *l_begin;
1739
1740 // See if the lhs keys exist in the rhs.
1741 ETL_OR_STD::pair<itr_t, itr_t> l_range = lhs.equal_range(l_value);
1742 ETL_OR_STD::pair<itr_t, itr_t> r_range = rhs.equal_range(l_value);
1743
1744 if (r_range.first != rhs.end())
1745 {
1746 bool distance_match = (etl::distance(l_range.first, l_range.second) == etl::distance(r_range.first, r_range.second));
1747
1748 if (distance_match)
1749 {
1751 }
1752 else
1753 {
1754 elements_match = false;
1755 }
1756 }
1757 else
1758 {
1759 elements_match = false;
1760 }
1761
1762 ++l_begin;
1763 }
1764 }
1765
1766 return (sizes_match && elements_match);
1767 }
1768
1769 //***************************************************************************
1775 //***************************************************************************
1776 template <typename TKey, typename THash, typename TKeyEqual>
1782
1783 //*************************************************************************
1785 //*************************************************************************
1786 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> >
1787 class unordered_multiset : public etl::iunordered_multiset<TKey, THash, TKeyEqual>
1788 {
1789 private:
1790
1792
1793 public:
1794
1795 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1796 static ETL_CONSTANT size_t MAX_BUCKETS = MAX_BUCKETS_;
1797
1798
1799 //*************************************************************************
1801 //*************************************************************************
1802 unordered_multiset(const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1803 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1804 {
1805 }
1806
1807 //*************************************************************************
1809 //*************************************************************************
1811 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1812 {
1813 // Skip if doing self assignment
1814 if (this != &other)
1815 {
1816 base::assign(other.cbegin(), other.cend());
1817 }
1818 }
1819
1820
1821#if ETL_USING_CPP11
1822 //*************************************************************************
1824 //*************************************************************************
1826 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1827 {
1828 // Skip if doing self assignment
1829 if (this != &other)
1830 {
1831 base::move(other.begin(), other.end());
1832 }
1833 }
1834#endif
1835
1836 //*************************************************************************
1841 //*************************************************************************
1842 template <typename TIterator>
1844 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1845 {
1846 base::assign(first_, last_);
1847 }
1848
1849#if ETL_HAS_INITIALIZER_LIST
1850 //*************************************************************************
1852 //*************************************************************************
1853 unordered_multiset(std::initializer_list<TKey> init, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1854 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1855 {
1856 base::assign(init.begin(), init.end());
1857 }
1858#endif
1859
1860 //*************************************************************************
1862 //*************************************************************************
1864 {
1865 base::initialise();
1866 }
1867
1868 //*************************************************************************
1870 //*************************************************************************
1872 {
1873 base::operator =(rhs);
1874
1875 return *this;
1876 }
1877
1878#if ETL_USING_CPP11
1879 //*************************************************************************
1881 //*************************************************************************
1883 {
1884 base::operator =(etl::move(rhs));
1885
1886 return *this;
1887 }
1888#endif
1889
1890 private:
1891
1894
1896 typename base::bucket_t buckets[MAX_BUCKETS_];
1897 };
1898
1899 //*************************************************************************
1901 //*************************************************************************
1902#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1903 template <typename... T>
1904 unordered_multiset(T...) -> unordered_multiset<etl::nth_type_t<0, T...>, sizeof...(T)>;
1905#endif
1906
1907 //*************************************************************************
1909 //*************************************************************************
1910#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1911 template <typename TKey, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey>, typename... T>
1912 constexpr auto make_unordered_multiset(T&&... keys) -> etl::unordered_multiset<TKey, sizeof...(T), sizeof...(T), THash, TKeyEqual>
1913 {
1914 return { etl::forward<T>(keys)... };
1915 }
1916#endif
1917}
1918
1919#endif
Definition unordered_multiset.h:325
Definition unordered_multiset.h:183
A templated unordered_multiset implementation that uses a fixed size buffer.
Definition unordered_multiset.h:1788
unordered_multiset(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_multiset.h:1802
~unordered_multiset()
Destructor.
Definition unordered_multiset.h:1863
unordered_multiset(const unordered_multiset &other)
Copy constructor.
Definition unordered_multiset.h:1810
unordered_multiset(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_multiset.h:1843
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
~iunordered_multiset()
Destructor.
Definition unordered_multiset.h:1709
ETL_OR_STD::pair< iterator, bool > insert(const_reference key)
Definition unordered_multiset.h:678
size_t available() const
Definition unordered_multiset.h:1429
const_iterator cend() const
Definition unordered_multiset.h:552
iunordered_multiset & operator=(const iunordered_multiset &rhs)
Assignment operator.
Definition unordered_multiset.h:1464
const_iterator begin() const
Definition unordered_multiset.h:489
size_t erase(key_parameter_t key)
Definition unordered_multiset.h:921
void initialise()
Initialise the unordered_multiset.
Definition unordered_multiset.h:1534
iterator end()
Definition unordered_multiset.h:534
size_type max_size() const
Gets the maximum possible size of the unordered_multiset.
Definition unordered_multiset.h:1396
iterator insert(const_iterator, const_reference key)
Definition unordered_multiset.h:894
const_local_iterator end(size_t i) const
Definition unordered_multiset.h:570
size_type get_bucket_index(key_parameter_t key) const
Definition unordered_multiset.h:588
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(key_parameter_t key) const
Definition unordered_multiset.h:1338
const_iterator find(key_parameter_t key) const
Definition unordered_multiset.h:1209
local_iterator begin(size_t i)
Definition unordered_multiset.h:507
void assign(TIterator first_, TIterator last_)
Definition unordered_multiset.h:656
const_iterator cbegin() const
Definition unordered_multiset.h:498
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:1520
const_iterator end() const
Definition unordered_multiset.h:543
size_type bucket_size(key_parameter_t key) const
Definition unordered_multiset.h:609
void insert(TIterator first_, TIterator last_)
Definition unordered_multiset.h:907
void clear()
Clears the unordered_multiset.
Definition unordered_multiset.h:1073
const_local_iterator cend(size_t i) const
Definition unordered_multiset.h:579
bool contains(key_parameter_t key) const
Check if the unordered_multiset contains the key.
Definition unordered_multiset.h:1499
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_multiset.h:1019
const_local_iterator cbegin(size_t i) const
Definition unordered_multiset.h:525
iterator find(key_parameter_t key)
Definition unordered_multiset.h:1138
iterator begin()
Definition unordered_multiset.h:480
iterator erase(const_iterator ielement)
Definition unordered_multiset.h:991
key_equal key_eq() const
Definition unordered_multiset.h:1456
local_iterator end(size_t i)
Definition unordered_multiset.h:561
const_local_iterator begin(size_t i) const
Definition unordered_multiset.h:516
size_type max_bucket_count() const
Definition unordered_multiset.h:634
size_type size() const
Gets the size of the unordered_multiset.
Definition unordered_multiset.h:1388
hasher hash_function() const
Definition unordered_multiset.h:1447
size_type bucket_count() const
Definition unordered_multiset.h:643
size_type capacity() const
Gets the maximum possible size of the unordered_multiset.
Definition unordered_multiset.h:1404
size_t count(key_parameter_t key) const
Definition unordered_multiset.h:1083
bool full() const
Checks to see if the unordered_multiset is full.
Definition unordered_multiset.h:1420
float load_factor() const
Definition unordered_multiset.h:1438
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition unordered_multiset.h:1283
bool empty() const
Checks to see if the unordered_multiset is empty.
Definition unordered_multiset.h:1412
Definition unordered_multiset.h:128
Definition unordered_multiset.h:71
Definition unordered_multiset.h:85
Definition unordered_multiset.h:112
Definition unordered_multiset.h:99
bitset_ext
Definition absolute.h:38
Definition compare.h:51
iterator
Definition iterator.h:399
Definition unordered_multiset.h:151
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