Embedded Template Library 1.0
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 //***************************************************************************
69 {
70 public:
71
72 unordered_multiset_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
73 : etl::exception(reason_, file_name_, line_number_)
74 {
75 }
76 };
77
78 //***************************************************************************
81 //***************************************************************************
83 {
84 public:
85
86 unordered_multiset_full(string_type file_name_, numeric_type line_number_)
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
100 unordered_multiset_out_of_range(string_type file_name_, numeric_type line_number_)
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
113 unordered_multiset_iterator(string_type file_name_, numeric_type line_number_)
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
136 typedef value_type&& rvalue_reference;
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 {
150 node_t(const_reference key_)
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
184 typedef typename etl::iterator<ETL_OR_STD::forward_iterator_tag, TKey>::value_type value_type;
185 typedef typename iunordered_multiset::key_type key_type;
186 typedef typename iunordered_multiset::hasher hasher;
187 typedef typename iunordered_multiset::key_equal key_equal;
188 typedef typename iunordered_multiset::reference reference;
189 typedef typename iunordered_multiset::const_reference const_reference;
190 typedef typename iunordered_multiset::pointer pointer;
191 typedef typename iunordered_multiset::const_pointer const_pointer;
192 typedef typename iunordered_multiset::size_type size_type;
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 //*********************************
211 iterator& operator ++()
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 //*********************************
236 iterator operator ++(int)
237 {
238 iterator temp(*this);
239 operator++();
240 return temp;
241 }
242
243 //*********************************
244 iterator& operator =(const iterator& other)
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 //*********************************
285 iterator(bucket_t* pbuckets_end_, bucket_t* pbucket_, local_iterator inode_)
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
326 typedef typename etl::iterator<ETL_OR_STD::forward_iterator_tag, const TKey>::value_type value_type;
327 typedef typename iunordered_multiset::key_type key_type;
328 typedef typename iunordered_multiset::hasher hasher;
329 typedef typename iunordered_multiset::key_equal key_equal;
330 typedef typename iunordered_multiset::reference reference;
331 typedef typename iunordered_multiset::const_reference const_reference;
332 typedef typename iunordered_multiset::pointer pointer;
333 typedef typename iunordered_multiset::const_pointer const_pointer;
334 typedef typename iunordered_multiset::size_type size_type;
335
336 friend class iunordered_multiset;
337 friend class iterator;
338
339 //*********************************
341 {
342 }
343
344 //*********************************
345 const_iterator(const typename iunordered_multiset::iterator& other)
346 : pbuckets_end(other.pbuckets_end)
347 , pbucket(other.pbucket)
348 , inode(other.inode)
349 {
350 }
351
352 //*********************************
353 const_iterator(const const_iterator& other)
354 : pbuckets_end(other.pbuckets_end)
355 , pbucket(other.pbucket)
356 , inode(other.inode)
357 {
358 }
359
360 //*********************************
361 const_iterator& operator ++()
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 //*********************************
387 const_iterator operator ++(int)
388 {
389 const_iterator temp(*this);
390 operator++();
391 return temp;
392 }
393
394 //*********************************
395 const_iterator& operator =(const const_iterator& other)
396 {
397 pbuckets_end = other.pbuckets_end;
398 pbucket = other.pbucket;
399 inode = other.inode;
400 return *this;
401 }
402
403 //*********************************
404 const_reference operator *() const
405 {
406 return inode->key;
407 }
408
409 //*********************************
410 const_pointer operator &() const
411 {
412 return &(inode->key);
413 }
414
415 //*********************************
416 const_pointer operator ->() const
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 //*********************************
436 const_iterator(bucket_t* pbuckets_end_, bucket_t* pbucket_, local_iterator inode_)
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 //*********************************************************************
506 {
507 return pbuckets[i].begin();
508 }
509
510 //*********************************************************************
513 //*********************************************************************
515 {
516 return pbuckets[i].cbegin();
517 }
518
519 //*********************************************************************
522 //*********************************************************************
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 //*********************************************************************
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 //*********************************************************************
578 {
579 return pbuckets[i].cend();
580 }
581
582 //*********************************************************************
585 //*********************************************************************
586 size_type get_bucket_index(key_parameter_t key) const
587 {
588 return key_hash_function(key) % number_of_buckets;
589 }
590
591 //*********************************************************************
594 //*********************************************************************
595 size_type bucket_size(key_parameter_t key) const
596 {
597 size_t index = bucket(key);
598
599 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
600 }
601
602 //*********************************************************************
605 //*********************************************************************
606 size_type max_bucket_count() const
607 {
608 return number_of_buckets;
609 }
610
611 //*********************************************************************
614 //*********************************************************************
615 size_type bucket_count() const
616 {
617 return number_of_buckets;
618 }
619
620 //*********************************************************************
626 //*********************************************************************
627 template <typename TIterator>
628 void assign(TIterator first_, TIterator last_)
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
693 ++inode_previous;
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);
706 ++inode_previous;
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 //*********************************************************************
793 iterator insert(const_iterator /*position*/, const_reference key)
794 {
795 return insert(key).first;
796 }
797
798 //*********************************************************************
804 //*********************************************************************
805 template <class TIterator>
806 void insert(TIterator first_, TIterator last_)
807 {
808 while (first_ != last_)
809 {
810 insert(*first_);
811 ++first_;
812 }
813 }
814
815 //*********************************************************************
819 //*********************************************************************
820 size_t erase(key_parameter_t key)
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;
836 icurrent = iprevious;
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);
949 const_iterator l = f;
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 //*********************************************************************
971 iterator find(key_parameter_t key)
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 //*********************************************************************
1005 const_iterator find(key_parameter_t key) const
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 //*************************************************************************
1089 size_type size() const
1090 {
1091 return pnodepool->size();
1092 }
1093
1094 //*************************************************************************
1096 //*************************************************************************
1097 size_type max_size() const
1098 {
1099 return pnodepool->max_size();
1100 }
1101
1102 //*************************************************************************
1104 //*************************************************************************
1105 size_type capacity() const
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 //*************************************************************************
1148 hasher hash_function() const
1149 {
1150 return key_hash_function;
1151 }
1152
1153 //*************************************************************************
1156 //*************************************************************************
1157 key_equal key_eq() const
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 //*********************************************************************
1202 iunordered_multiset(pool_t& node_pool_, bucket_t* pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
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 first, iterator last)
1256 {
1257 while (first != last)
1258 {
1259 iterator temp = first;
1260 ++temp;
1261 insert(etl::move(*first));
1262 first = 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* pcurrent)
1305 {
1306 if (empty())
1307 {
1308 first = pbuckets;
1309 last = pbuckets;
1310 }
1311 else
1312 {
1313 if (pcurrent == 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 (pcurrent == 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 bucket_t* pcurrent = first;
1325 bucket_t* pend = last;
1326
1327 last = first;
1328
1329 while (pcurrent != pend)
1330 {
1331 if (!pcurrent->empty())
1332 {
1333 last = pcurrent;
1334 }
1335
1336 ++pcurrent;
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.
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 TMapped, typename TKeyCompare>
1406 {
1407 const bool sizes_match = (lhs.size() == rhs.size());
1408 bool elements_match = true;
1409
1410 if (sizes_match)
1411 {
1412 for (size_t i = 0; (i < lhs.bucket_count()) && elements_match; ++i)
1413 {
1414 if (!etl::is_permutation(lhs.begin(i), lhs.end(i), rhs.begin(i)))
1415 {
1416 elements_match = false;
1417 }
1418 }
1419 }
1420
1421 return (sizes_match && elements_match);
1422 }
1423
1424 //***************************************************************************
1430 //***************************************************************************
1431 template <typename TKey, typename TMapped, typename TKeyCompare>
1433 {
1434 return !(lhs == rhs);
1435 }
1436
1437 //*************************************************************************
1439 //*************************************************************************
1440 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> >
1441 class unordered_multiset : public etl::iunordered_multiset<TKey, THash, TKeyEqual>
1442 {
1443 private:
1444
1446
1447 public:
1448
1449 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1450 static ETL_CONSTANT size_t MAX_BUCKETS = MAX_BUCKETS_;
1451
1452
1453 //*************************************************************************
1455 //*************************************************************************
1456 unordered_multiset(const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1457 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1458 {
1459 }
1460
1461 //*************************************************************************
1463 //*************************************************************************
1465 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1466 {
1467 // Skip if doing self assignment
1468 if (this != &other)
1469 {
1470 base::assign(other.cbegin(), other.cend());
1471 }
1472 }
1473
1474
1475#if ETL_USING_CPP11
1476 //*************************************************************************
1478 //*************************************************************************
1480 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1481 {
1482 // Skip if doing self assignment
1483 if (this != &other)
1484 {
1485 base::move(other.begin(), other.end());
1486 }
1487 }
1488#endif
1489
1490 //*************************************************************************
1495 //*************************************************************************
1496 template <typename TIterator>
1497 unordered_multiset(TIterator first_, TIterator last_, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1498 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1499 {
1500 base::assign(first_, last_);
1501 }
1502
1503#if ETL_HAS_INITIALIZER_LIST
1504 //*************************************************************************
1506 //*************************************************************************
1507 unordered_multiset(std::initializer_list<TKey> init, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1508 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1509 {
1510 base::assign(init.begin(), init.end());
1511 }
1512#endif
1513
1514 //*************************************************************************
1516 //*************************************************************************
1518 {
1519 base::initialise();
1520 }
1521
1522 //*************************************************************************
1524 //*************************************************************************
1526 {
1527 base::operator =(rhs);
1528
1529 return *this;
1530 }
1531
1532#if ETL_USING_CPP11
1533 //*************************************************************************
1535 //*************************************************************************
1537 {
1538 base::operator =(etl::move(rhs));
1539
1540 return *this;
1541 }
1542#endif
1543
1544 private:
1545
1548
1550 typename base::bucket_t buckets[MAX_BUCKETS_];
1551 };
1552
1553 //*************************************************************************
1555 //*************************************************************************
1556#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1557 template <typename... T>
1558 unordered_multiset(T...) -> unordered_multiset<etl::nth_type_t<0, T...>, sizeof...(T)>;
1559#endif
1560
1561 //*************************************************************************
1563 //*************************************************************************
1564#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1565 template <typename TKey, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey>, typename... T>
1566 constexpr auto make_unordered_multiset(T&&... keys) -> etl::unordered_multiset<TKey, sizeof...(T), sizeof...(T), THash, TKeyEqual>
1567 {
1568 return { {etl::forward<T>(keys)...} };
1569 }
1570#endif
1571}
1572
1573#endif
const_iterator
Definition: intrusive_forward_list.h:448
iterator.
Definition: intrusive_forward_list.h:372
bool empty() const
Returns true if the list has no elements.
Definition: intrusive_forward_list.h:247
void clear()
Clears the intrusive_forward_list.
Definition: intrusive_forward_list.h:149
Definition: intrusive_forward_list.h:352
const_iterator cbegin() const
Gets the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:584
iterator insert_after(iterator position, value_type &value)
Inserts a value to the intrusive_forward_list after the specified position.
Definition: intrusive_forward_list.h:632
iterator end()
Gets the end of the intrusive_forward_list.
Definition: intrusive_forward_list.h:592
iterator before_begin()
Gets before the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:568
const_iterator cend() const
Gets the end of the intrusive_forward_list.
Definition: intrusive_forward_list.h:608
iterator begin()
Gets the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:552
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:1442
unordered_multiset(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition: unordered_multiset.h:1456
~unordered_multiset()
Destructor.
Definition: unordered_multiset.h:1517
unordered_multiset(const unordered_multiset &other)
Copy constructor.
Definition: unordered_multiset.h:1464
unordered_multiset(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition: unordered_multiset.h:1497
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition: algorithm.h:1495
#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
Definition: pool.h:54
~iunordered_multiset()
For library debugging purposes only.
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
bool operator==(const etl::iunordered_multiset< TKey, TMapped, TKeyCompare > &lhs, const etl::iunordered_multiset< TKey, TMapped, TKeyCompare > &rhs)
Definition: unordered_multiset.h:1405
bool operator!=(const etl::iunordered_multiset< TKey, TMapped, TKeyCompare > &lhs, const etl::iunordered_multiset< TKey, TMapped, TKeyCompare > &rhs)
Definition: unordered_multiset.h:1432
bitset_ext
Definition: absolute.h:38
etl::byte operator&(etl::byte lhs, etl::byte rhs)
And.
Definition: byte.h:273
Definition: compare.h:52
iterator
Definition: iterator.h:399
Definition: unordered_multiset.h:149