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