Embedded Template Library 1.0
Loading...
Searching...
No Matches
unordered_map.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_MAP_INCLUDED
32#define ETL_UNORDERED_MAP_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 "array.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 "vector.h"
48#include "error_handler.h"
49#include "exception.h"
50#include "debug_count.h"
51#include "iterator.h"
52#include "placement_new.h"
53#include "initializer_list.h"
54
55#include <stddef.h>
56
57//*****************************************************************************
61//*****************************************************************************
62
63namespace etl
64{
65 //***************************************************************************
68 //***************************************************************************
78
79 //***************************************************************************
82 //***************************************************************************
84 {
85 public:
86
88 : etl::unordered_map_exception(ETL_ERROR_TEXT("unordered_map:full", ETL_UNORDERED_MAP_FILE_ID"A"), file_name_, line_number_)
89 {
90 }
91 };
92
93 //***************************************************************************
96 //***************************************************************************
98 {
99 public:
100
102 : etl::unordered_map_exception(ETL_ERROR_TEXT("unordered_map:range", ETL_UNORDERED_MAP_FILE_ID"B"), file_name_, line_number_)
103 {}
104 };
105
106 //***************************************************************************
109 //***************************************************************************
111 {
112 public:
113
115 : etl::unordered_map_exception(ETL_ERROR_TEXT("unordered_map:iterator", ETL_UNORDERED_MAP_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
147#if ETL_USING_CPP11
149#endif
151 typedef const mapped_type& const_mapped_reference;
152
153 typedef etl::forward_link<0> link_t; // Default link.
154
155 // The nodes that store the elements.
156 // The nodes that store the elements.
157 struct node_t : public link_t
158 {
159 node_t(const_reference key_value_pair_)
160 : key_value_pair(key_value_pair_)
161 {
162 }
163
164 value_type key_value_pair;
165 };
166
167 friend bool operator ==(const node_t& lhs, const node_t& rhs)
168 {
169 return (lhs.key_value_pair.first == rhs.key_value_pair.first) &&
170 (lhs.key_value_pair.second == rhs.key_value_pair.second);
171 }
172
173 friend bool operator !=(const node_t& lhs, const node_t& rhs)
174 {
175 return !(lhs == rhs);
176 }
177
178 protected:
179
181 typedef etl::ipool pool_t;
182
183 public:
184
185 // Local iterators iterate over one bucket.
186 typedef typename bucket_t::iterator local_iterator;
187 typedef typename bucket_t::const_iterator const_local_iterator;
188
189 //*********************************************************************
190 class iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, T>
191 {
192 public:
193
195 typedef typename iunordered_map::key_type key_type;
197 typedef typename iunordered_map::hasher hasher;
198 typedef typename iunordered_map::key_equal key_equal;
199 typedef typename iunordered_map::reference reference;
200 typedef typename iunordered_map::const_reference const_reference;
201 typedef typename iunordered_map::pointer pointer;
202 typedef typename iunordered_map::const_pointer const_pointer;
203 typedef typename iunordered_map::size_type size_type;
204
205 friend class iunordered_map;
206 friend class const_iterator;
207
208 //*********************************
209 iterator()
210 {
211 }
212
213 //*********************************
214 iterator(const iterator& other)
215 : pbuckets_end(other.pbuckets_end)
216 , pbucket(other.pbucket)
217 , inode(other.inode)
218 {
219 }
220
221 //*********************************
223 {
224 ++inode;
225
226 // The end of this node list?
227 if (inode == pbucket->end())
228 {
229 // Search for the next non-empty bucket.
230 ++pbucket;
231 while ((pbucket != pbuckets_end) && (pbucket->empty()))
232 {
233 ++pbucket;
234 }
235
236 // If not past the end, get the first node in the bucket.
237 if (pbucket != pbuckets_end)
238 {
239 inode = pbucket->begin();
240 }
241 }
242
243 return *this;
244 }
245
246 //*********************************
248 {
249 iterator temp(*this);
250 operator++();
251 return temp;
252 }
253
254 //*********************************
256 {
257 pbuckets_end = other.pbuckets_end;
258 pbucket = other.pbucket;
259 inode = other.inode;
260 return *this;
261 }
262
263 //*********************************
264 reference operator *() const
265 {
266 return inode->key_value_pair;
267 }
268
269 //*********************************
270 pointer operator &() const
271 {
272 return &(inode->key_value_pair);
273 }
274
275 //*********************************
276 pointer operator ->() const
277 {
278 return &(inode->key_value_pair);
279 }
280
281 //*********************************
282 friend bool operator == (const iterator& lhs, const iterator& rhs)
283 {
284 return lhs.compare(rhs);
285 }
286
287 //*********************************
288 friend bool operator != (const iterator& lhs, const iterator& rhs)
289 {
290 return !(lhs == rhs);
291 }
292
293 private:
294
295 //*********************************
297 : pbuckets_end(pbuckets_end_)
298 , pbucket(pbucket_)
299 , inode(inode_)
300 {
301 }
302
303 //*********************************
304 bool compare(const iterator& rhs) const
305 {
306 return rhs.inode == inode;
307 }
308
309 //*********************************
310 bucket_t& get_bucket()
311 {
312 return *pbucket;
313 }
314
315 //*********************************
316 bucket_t* get_bucket_list_iterator()
317 {
318 return pbucket;
319 }
320
321 //*********************************
322 local_iterator get_local_iterator()
323 {
324 return inode;
325 }
326
327 bucket_t* pbuckets_end;
328 bucket_t* pbucket;
329 local_iterator inode;
330 };
331
332 //*********************************************************************
333 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const T>
334 {
335 public:
336
338 typedef typename iunordered_map::key_type key_type;
340 typedef typename iunordered_map::hasher hasher;
341 typedef typename iunordered_map::key_equal key_equal;
342 typedef typename iunordered_map::reference reference;
343 typedef typename iunordered_map::const_reference const_reference;
344 typedef typename iunordered_map::pointer pointer;
345 typedef typename iunordered_map::const_pointer const_pointer;
346 typedef typename iunordered_map::size_type size_type;
347
348 friend class iunordered_map;
349 friend class iterator;
350
351 //*********************************
353 {
354 }
355
356 //*********************************
358 : pbuckets_end(other.pbuckets_end)
359 , pbucket(other.pbucket)
360 , inode(other.inode)
361 {
362 }
363
364 //*********************************
366 : pbuckets_end(other.pbuckets_end)
367 , pbucket(other.pbucket)
368 , inode(other.inode)
369 {
370 }
371
372 //*********************************
374 {
375 ++inode;
376
377 // The end of this node list?
378 if (inode == pbucket->end())
379 {
380 // Search for the next non-empty bucket.
381 ++pbucket;
382 while ((pbucket != pbuckets_end) && (pbucket->empty()))
383 {
384 ++pbucket;
385 }
386
387 // If not past the end, get the first node in the bucket.
388 if (pbucket != pbuckets_end)
389 {
390 inode = pbucket->begin();
391 }
392 }
393
394 return *this;
395 }
396
397 //*********************************
399 {
400 const_iterator temp(*this);
401 operator++();
402 return temp;
403 }
404
405 //*********************************
407 {
408 pbuckets_end = other.pbuckets_end;
409 pbucket = other.pbucket;
410 inode = other.inode;
411 return *this;
412 }
413
414 //*********************************
415 const_reference operator *() const
416 {
417 return inode->key_value_pair;
418 }
419
420 //*********************************
421 const_pointer operator &() const
422 {
423 return &(inode->key_value_pair);
424 }
425
426 //*********************************
427 const_pointer operator ->() const
428 {
429 return &(inode->key_value_pair);
430 }
431
432 //*********************************
433 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
434 {
435 return lhs.compare(rhs);
436 }
437
438 //*********************************
439 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
440 {
441 return !(lhs == rhs);
442 }
443
444 private:
445
446 //*********************************
448 : pbuckets_end(pbuckets_end_)
449 , pbucket(pbucket_)
450 , inode(inode_)
451 {
452 }
453
454 //*********************************
455 bool compare(const const_iterator& rhs) const
456 {
457 return rhs.inode == inode;
458 }
459
460 //*********************************
461 bucket_t& get_bucket()
462 {
463 return *pbucket;
464 }
465
466 //*********************************
467 bucket_t* get_bucket_list_iterator()
468 {
469 return pbucket;
470 }
471
472 //*********************************
473 local_iterator get_local_iterator()
474 {
475 return inode;
476 }
477
478 bucket_t* pbuckets_end;
479 bucket_t* pbucket;
480 local_iterator inode;
481 };
482
483 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
484
485 //*********************************************************************
488 //*********************************************************************
490 {
491 return iterator((pbuckets + number_of_buckets), first, first->begin());
492 }
493
494 //*********************************************************************
497 //*********************************************************************
499 {
500 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
501 }
502
503 //*********************************************************************
506 //*********************************************************************
508 {
509 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
510 }
511
512 //*********************************************************************
515 //*********************************************************************
516 local_iterator begin(size_t i)
517 {
518 return pbuckets[i].begin();
519 }
520
521 //*********************************************************************
524 //*********************************************************************
525 const_local_iterator begin(size_t i) const
526 {
527 return pbuckets[i].cbegin();
528 }
529
530 //*********************************************************************
533 //*********************************************************************
534 const_local_iterator cbegin(size_t i) const
535 {
536 return pbuckets[i].cbegin();
537 }
538
539 //*********************************************************************
542 //*********************************************************************
544 {
545 return iterator((pbuckets + number_of_buckets), last, last->end());
546 }
547
548 //*********************************************************************
551 //*********************************************************************
553 {
554 return const_iterator((pbuckets + number_of_buckets), last, last->end());
555 }
556
557 //*********************************************************************
560 //*********************************************************************
562 {
563 return const_iterator((pbuckets + number_of_buckets), last, last->end());
564 }
565
566 //*********************************************************************
569 //*********************************************************************
570 local_iterator end(size_t i)
571 {
572 return pbuckets[i].end();
573 }
574
575 //*********************************************************************
578 //*********************************************************************
579 const_local_iterator end(size_t i) const
580 {
581 return pbuckets[i].cend();
582 }
583
584 //*********************************************************************
587 //*********************************************************************
588 const_local_iterator cend(size_t i) const
589 {
590 return pbuckets[i].cend();
591 }
592
593 //*********************************************************************
596 //*********************************************************************
598 {
599 return key_hash_function(key) % number_of_buckets;
600 }
601
602 //*********************************************************************
605 //*********************************************************************
607 {
608 size_t index = bucket(key);
609
610 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
611 }
612
613 //*********************************************************************
616 //*********************************************************************
618 {
619 return number_of_buckets;
620 }
621
622 //*********************************************************************
625 //*********************************************************************
627 {
628 return number_of_buckets;
629 }
630
631#if ETL_USING_CPP11
632 //*********************************************************************
636 //*********************************************************************
637 mapped_reference operator [](rvalue_key_reference key)
638 {
639 // Find the bucket.
640 bucket_t* pbucket = pbuckets + get_bucket_index(key);
641
642 // Find the first node in the bucket.
643 local_iterator inode = pbucket->begin();
644
645 // Walk the list looking for the right one.
646 while (inode != pbucket->end())
647 {
648 // Equal keys?
649 if (key_equal_function(key, inode->key_value_pair.first))
650 {
651 // Found a match.
652 return inode->key_value_pair.second;
653 }
654 else
655 {
656 ++inode;
657 }
658 }
659
660 // Doesn't exist, so add a new one.
661 // Get a new node.
662 node_t* node = allocate_data_node();
663 node->clear();
664 ::new ((void*)etl::addressof(node->key_value_pair.first)) key_type(etl::move(key));
665 ::new ((void*)etl::addressof(node->key_value_pair.second)) mapped_type();
666 ETL_INCREMENT_DEBUG_COUNT;
667
668 pbucket->insert_after(pbucket->before_begin(), *node);
669
670 adjust_first_last_markers_after_insert(pbucket);
671
672 return pbucket->begin()->key_value_pair.second;
673 }
674#endif
675
676 //*********************************************************************
680 //*********************************************************************
682 {
683 // Find the bucket.
684 bucket_t* pbucket = pbuckets + get_bucket_index(key);
685
686 // Find the first node in the bucket.
687 local_iterator inode = pbucket->begin();
688
689 // Walk the list looking for the right one.
690 while (inode != pbucket->end())
691 {
692 // Equal keys?
693 if (key_equal_function(key, inode->key_value_pair.first))
694 {
695 // Found a match.
696 return inode->key_value_pair.second;
697 }
698 else
699 {
700 ++inode;
701 }
702 }
703
704 // Doesn't exist, so add a new one.
705 // Get a new node.
706 node_t* node = allocate_data_node();
707 node->clear();
708 ::new ((void*)etl::addressof(node->key_value_pair.first)) key_type(key);
709 ::new ((void*)etl::addressof(node->key_value_pair.second)) mapped_type();
710 ETL_INCREMENT_DEBUG_COUNT;
711
712 pbucket->insert_after(pbucket->before_begin(), *node);
713
714 adjust_first_last_markers_after_insert(pbucket);
715
716 return pbucket->begin()->key_value_pair.second;
717 }
718
719 //*********************************************************************
724 //*********************************************************************
726 {
727 // Find the bucket.
728 bucket_t* pbucket = pbuckets + get_bucket_index(key);
729
730 // Find the first node in the bucket.
731 local_iterator inode = pbucket->begin();
732
733 // Walk the list looking for the right one.
734 while (inode != pbucket->end())
735 {
736 // Equal keys?
737 if (key_equal_function(key, inode->key_value_pair.first))
738 {
739 // Found a match.
740 return inode->key_value_pair.second;
741 }
742 else
743 {
744 ++inode;
745 }
746 }
747
748 // Doesn't exist.
749 ETL_ASSERT(false, ETL_ERROR(unordered_map_out_of_range));
750
751 return begin()->second;
752 }
753
754 //*********************************************************************
759 //*********************************************************************
761 {
762 // Find the bucket.
763 bucket_t* pbucket = pbuckets + get_bucket_index(key);
764
765 // Find the first node in the bucket.
766 local_iterator inode = pbucket->begin();
767
768 // Walk the list looking for the right one.
769 while (inode != pbucket->end())
770 {
771 // Equal keys?
772 if (key_equal_function(key, inode->key_value_pair.first))
773 {
774 // Found a match.
775 return inode->key_value_pair.second;
776 }
777 else
778 {
779 ++inode;
780 }
781 }
782
783 // Doesn't exist.
784 ETL_ASSERT(false, ETL_ERROR(unordered_map_out_of_range));
785
786 return begin()->second;
787 }
788
789 //*********************************************************************
795 //*********************************************************************
796 template <typename TIterator>
798 {
799#if ETL_IS_DEBUG_BUILD
800 difference_type d = etl::distance(first_, last_);
801 ETL_ASSERT(d >= 0, ETL_ERROR(unordered_map_iterator));
802 ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_map_full));
803#endif
804
805 clear();
806
807 while (first_ != last_)
808 {
809 insert(*first_);
810 ++first_;
811 }
812 }
813
814 //*********************************************************************
818 //*********************************************************************
819 ETL_OR_STD::pair<iterator, bool> insert(const_reference key_value_pair)
820 {
821 ETL_OR_STD::pair<iterator, bool> result(end(), false);
822
823 ETL_ASSERT(!full(), ETL_ERROR(unordered_map_full));
824
825 const key_type& key = key_value_pair.first;
826
827 // Get the hash index.
828 size_t index = get_bucket_index(key);
829
830 // Get the bucket & bucket iterator.
831 bucket_t* pbucket = pbuckets + index;
832 bucket_t& bucket = *pbucket;
833
834 // The first one in the bucket?
835 if (bucket.empty())
836 {
837 // Get a new node.
838 node_t* node = allocate_data_node();
839 node->clear();
840 ::new ((void*)etl::addressof(node->key_value_pair)) value_type(key_value_pair);
841 ETL_INCREMENT_DEBUG_COUNT;
842
843 // Just add the pointer to the bucket;
844 bucket.insert_after(bucket.before_begin(), *node);
845
846 adjust_first_last_markers_after_insert(pbucket);
847
848 result.first = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
849 result.second = true;
850 }
851 else
852 {
853 // Step though the bucket looking for a place to insert.
854 local_iterator inode_previous = bucket.before_begin();
855 local_iterator inode = bucket.begin();
856
857 while (inode != bucket.end())
858 {
859 // Do we already have this key?
860 if (key_equal_function(inode->key_value_pair.first, key))
861 {
862 break;
863 }
864
866 ++inode;
867 }
868
869 // Not already there?
870 if (inode == bucket.end())
871 {
872 // Get a new node.
873 node_t* node = allocate_data_node();
874 node->clear();
875 ::new ((void*)etl::addressof(node->key_value_pair)) value_type(key_value_pair);
876 ETL_INCREMENT_DEBUG_COUNT;
877
878 // Add the node to the end of the bucket;
879 bucket.insert_after(inode_previous, *node);
880 adjust_first_last_markers_after_insert(&bucket);
882
883 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
884 result.second = true;
885 }
886 }
887
888 return result;
889 }
890
891#if ETL_USING_CPP11
892 //*********************************************************************
896 //*********************************************************************
897 ETL_OR_STD::pair<iterator, bool> insert(rvalue_reference key_value_pair)
898 {
899 ETL_OR_STD::pair<iterator, bool> result(end(), false);
900
901 ETL_ASSERT(!full(), ETL_ERROR(unordered_map_full));
902
903 const key_type& key = key_value_pair.first;
904
905 // Get the hash index.
906 size_t index = get_bucket_index(key);
907
908 // Get the bucket & bucket iterator.
909 bucket_t* pbucket = pbuckets + index;
910 bucket_t& bucket = *pbucket;
911
912 // The first one in the bucket?
913 if (bucket.empty())
914 {
915 // Get a new node.
916 node_t* node = allocate_data_node();
917 node->clear();
918 ::new ((void*)etl::addressof(node->key_value_pair)) value_type(etl::move(key_value_pair));
919 ETL_INCREMENT_DEBUG_COUNT;
920
921 // Just add the pointer to the bucket;
922 bucket.insert_after(bucket.before_begin(), *node);
923
924 adjust_first_last_markers_after_insert(pbucket);
925
926 result.first = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
927 result.second = true;
928 }
929 else
930 {
931 // Step though the bucket looking for a place to insert.
932 local_iterator inode_previous = bucket.before_begin();
933 local_iterator inode = bucket.begin();
934
935 while (inode != bucket.end())
936 {
937 // Do we already have this key?
938 if (key_equal_function(inode->key_value_pair.first, key))
939 {
940 break;
941 }
942
943 ++inode_previous;
944 ++inode;
945 }
946
947 // Not already there?
948 if (inode == bucket.end())
949 {
950 // Get a new node.
951 node_t* node = allocate_data_node();
952 node->clear();
953 ::new ((void*)etl::addressof(node->key_value_pair)) value_type(etl::move(key_value_pair));
954 ETL_INCREMENT_DEBUG_COUNT;
955
956 // Add the node to the end of the bucket;
957 bucket.insert_after(inode_previous, *node);
958 adjust_first_last_markers_after_insert(&bucket);
959 ++inode_previous;
960
961 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
962 result.second = true;
963 }
964 }
965
966 return result;
967 }
968#endif
969
970 //*********************************************************************
975 //*********************************************************************
976 iterator insert(const_iterator, const_reference key_value_pair)
977 {
978 return insert(key_value_pair).first;
979 }
980
981#if ETL_USING_CPP11
982 //*********************************************************************
987 //*********************************************************************
988 iterator insert(const_iterator, rvalue_reference key_value_pair)
989 {
990 return insert(etl::move(key_value_pair)).first;
991 }
992#endif
993
994 //*********************************************************************
1000 //*********************************************************************
1001 template <class TIterator>
1003 {
1004 while (first_ != last_)
1005 {
1006 insert(*first_);
1007 ++first_;
1008 }
1009 }
1010
1011 //*********************************************************************
1015 //*********************************************************************
1017 {
1018 size_t n = 0UL;
1019 size_t index = get_bucket_index(key);
1020
1021 bucket_t& bucket = pbuckets[index];
1022
1023 local_iterator iprevious = bucket.before_begin();
1024 local_iterator icurrent = bucket.begin();
1025
1026 // Search for the key, if we have it.
1027 while ((icurrent != bucket.end()) && (!key_equal_function(icurrent->key_value_pair.first, key)))
1028 {
1029 ++iprevious;
1030 ++icurrent;
1031 }
1032
1033 // Did we find it?
1034 if (icurrent != bucket.end())
1035 {
1036 delete_data_node(iprevious, icurrent, bucket);
1037 n = 1;
1038 }
1039
1040 return n;
1041 }
1042
1043 //*********************************************************************
1046 //*********************************************************************
1048 {
1049 // Make a note of the next one.
1050 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
1051 ++inext;
1052
1053 bucket_t& bucket = ielement.get_bucket();
1054 local_iterator iprevious = bucket.before_begin();
1055 local_iterator icurrent = ielement.get_local_iterator();
1056
1057 // Find the node previous to the one we're interested in.
1058 while (iprevious->etl_next != &*icurrent)
1059 {
1060 ++iprevious;
1061 }
1062
1063 delete_data_node(iprevious, icurrent, bucket);
1064
1065 return inext;
1066 }
1067
1068 //*********************************************************************
1074 //*********************************************************************
1076 {
1077 // Erasing everything?
1078 if ((first_ == begin()) && (last_ == end()))
1079 {
1080 clear();
1081 return end();
1082 }
1083
1084 // Get the starting point.
1085 bucket_t* pbucket = first_.get_bucket_list_iterator();
1086 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
1087 local_iterator iprevious = pbucket->before_begin();
1088 local_iterator icurrent = first_.get_local_iterator();
1089 local_iterator iend = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
1090
1091 // Find the node previous to the first one.
1092 while (iprevious->etl_next != &*icurrent)
1093 {
1094 ++iprevious;
1095 }
1096
1097 // Remember the item before the first erased one.
1098 iterator ibefore_erased = iterator((pbuckets + number_of_buckets), pbucket, iprevious);
1099
1100 // Until we reach the end.
1101 while ((icurrent != iend) || (pbucket != pend_bucket))
1102 {
1103 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
1104
1105 // Have we not reached the end?
1106 if ((icurrent != iend) || (pbucket != pend_bucket))
1107 {
1108 // At the end of this bucket?
1109 if ((icurrent == pbucket->end()))
1110 {
1111 // Find the next non-empty one.
1112 do
1113 {
1114 ++pbucket;
1115 } while (pbucket->empty());
1116
1117 iprevious = pbucket->before_begin();
1118 icurrent = pbucket->begin();
1119 }
1120 }
1121 }
1122
1123 return ++ibefore_erased;
1124 }
1125
1126 //*************************************************************************
1128 //*************************************************************************
1129 void clear()
1130 {
1131 initialise();
1132 }
1133
1134 //*********************************************************************
1138 //*********************************************************************
1139 size_t count(const_key_reference key) const
1140 {
1141 return (find(key) == end()) ? 0 : 1;
1142 }
1143
1144 //*********************************************************************
1148 //*********************************************************************
1150 {
1151 size_t index = get_bucket_index(key);
1152
1153 bucket_t* pbucket = pbuckets + index;
1154 bucket_t& bucket = *pbucket;
1155
1156 // Is the bucket not empty?
1157 if (!bucket.empty())
1158 {
1159 // Step though the list until we find the end or an equivalent key.
1160 local_iterator inode = bucket.begin();
1161 local_iterator iend = bucket.end();
1162
1163 while (inode != iend)
1164 {
1165 // Do we have this one?
1166 if (key_equal_function(key, inode->key_value_pair.first))
1167 {
1168 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1169 }
1170
1171 ++inode;
1172 }
1173 }
1174
1175 return end();
1176 }
1177
1178 //*********************************************************************
1182 //*********************************************************************
1184 {
1185 size_t index = get_bucket_index(key);
1186
1187 bucket_t* pbucket = pbuckets + index;
1188 bucket_t& bucket = *pbucket;
1189
1190 // Is the bucket not empty?
1191 if (!bucket.empty())
1192 {
1193 // Step though the list until we find the end or an equivalent key.
1194 local_iterator inode = bucket.begin();
1195 local_iterator iend = bucket.end();
1196
1197 while (inode != iend)
1198 {
1199 // Do we have this one?
1200 if (key_equal_function(key, inode->key_value_pair.first))
1201 {
1202 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1203 }
1204
1205 ++inode;
1206 }
1207 }
1208
1209 return end();
1210 }
1211
1212 //*********************************************************************
1219 //*********************************************************************
1220 ETL_OR_STD::pair<iterator, iterator> equal_range(const_key_reference key)
1221 {
1222 iterator f = find(key);
1223 iterator l = f;
1224
1225 if (l != end())
1226 {
1227 ++l;
1228 }
1229
1230 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1231 }
1232
1233 //*********************************************************************
1240 //*********************************************************************
1241 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const_key_reference key) const
1242 {
1243 const_iterator f = find(key);
1244 const_iterator l = f;
1245
1246 if (l != end())
1247 {
1248 ++l;
1249 }
1250
1251 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1252 }
1253
1254 //*************************************************************************
1256 //*************************************************************************
1258 {
1259 return pnodepool->size();
1260 }
1261
1262 //*************************************************************************
1264 //*************************************************************************
1266 {
1267 return pnodepool->max_size();
1268 }
1269
1270 //*************************************************************************
1272 //*************************************************************************
1274 {
1275 return pnodepool->max_size();
1276 }
1277
1278 //*************************************************************************
1280 //*************************************************************************
1281 bool empty() const
1282 {
1283 return pnodepool->empty();
1284 }
1285
1286 //*************************************************************************
1288 //*************************************************************************
1289 bool full() const
1290 {
1291 return pnodepool->full();
1292 }
1293
1294 //*************************************************************************
1297 //*************************************************************************
1298 size_t available() const
1299 {
1300 return pnodepool->available();
1301 }
1302
1303 //*************************************************************************
1306 //*************************************************************************
1307 float load_factor() const
1308 {
1309 return static_cast<float>(size()) / static_cast<float>(bucket_count());
1310 }
1311
1312 //*************************************************************************
1315 //*************************************************************************
1317 {
1318 return key_hash_function;
1319 }
1320
1321 //*************************************************************************
1324 //*************************************************************************
1326 {
1327 return key_equal_function;
1328 }
1329
1330 //*************************************************************************
1332 //*************************************************************************
1334 {
1335 // Skip if doing self assignment
1336 if (this != &rhs)
1337 {
1338 key_hash_function = rhs.hash_function();
1339 key_equal_function = rhs.key_eq();
1340 assign(rhs.cbegin(), rhs.cend());
1341 }
1342
1343 return *this;
1344 }
1345#if ETL_USING_CPP11
1346 //*************************************************************************
1348 //*************************************************************************
1350 {
1351 // Skip if doing self assignment
1352 if (this != &rhs)
1353 {
1354 clear();
1355 key_hash_function = rhs.hash_function();
1356 key_equal_function = rhs.key_eq();
1357 this->move(rhs.begin(), rhs.end());
1358 }
1359
1360 return *this;
1361 }
1362#endif
1363
1364 protected:
1365
1366 //*********************************************************************
1368 //*********************************************************************
1370 : pnodepool(&node_pool_)
1371 , pbuckets(pbuckets_)
1372 , number_of_buckets(number_of_buckets_)
1373 , first(pbuckets)
1374 , last(pbuckets)
1375 , key_hash_function(key_hash_function_)
1376 , key_equal_function(key_equal_function_)
1377 {
1378 }
1379
1380 //*********************************************************************
1382 //*********************************************************************
1384 {
1385 if (!empty())
1386 {
1387 // For each bucket...
1388 for (size_t i = 0UL; i < number_of_buckets; ++i)
1389 {
1390 bucket_t& bucket = pbuckets[i];
1391
1392 if (!bucket.empty())
1393 {
1394 // For each item in the bucket...
1395 local_iterator it = bucket.begin();
1396
1397 while (it != bucket.end())
1398 {
1399 // Destroy the value contents.
1400 it->key_value_pair.~value_type();
1401 ETL_DECREMENT_DEBUG_COUNT;
1402
1403 ++it;
1404 }
1405
1406 // Now it's safe to clear the bucket.
1407 bucket.clear();
1408 }
1409 }
1410
1411 // Now it's safe to clear the entire pool in one go.
1412 pnodepool->release_all();
1413 }
1414
1415 first = pbuckets;
1416 last = first;
1417 }
1418
1419#if ETL_USING_CPP11
1420 //*************************************************************************
1422 //*************************************************************************
1423 void move(iterator b, iterator e)
1424 {
1425 while (b != e)
1426 {
1427 iterator temp = b;
1428 ++temp;
1429 insert(etl::move(*b));
1430 b = temp;
1431 }
1432 }
1433#endif
1434
1435 private:
1436
1437 //*************************************************************************
1439 //*************************************************************************
1440 node_t* allocate_data_node()
1441 {
1442 node_t* (etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1443 return (pnodepool->*func)();
1444 }
1445
1446 //*********************************************************************
1448 //*********************************************************************
1449 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1450 {
1451 if (size() == 1)
1452 {
1453 first = pbucket;
1454 last = pbucket;
1455 }
1456 else
1457 {
1458 if (pbucket < first)
1459 {
1460 first = pbucket;
1461 }
1462 else if (pbucket > last)
1463 {
1464 last = pbucket;
1465 }
1466 }
1467 }
1468
1469 //*********************************************************************
1471 //*********************************************************************
1472 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1473 {
1474 if (empty())
1475 {
1476 first = pbuckets;
1477 last = pbuckets;
1478 }
1479 else
1480 {
1481 if (pbucket == first)
1482 {
1483 // We erased the first so, we need to search again from where we erased.
1484 while (first->empty())
1485 {
1486 ++first;
1487 }
1488 }
1489 else if (pbucket == last)
1490 {
1491 // We erased the last, so we need to search again. Start from the first, go no further than the current last.
1492 pbucket = first;
1493 bucket_t* pend = last;
1494
1495 last = first;
1496
1497 while (pbucket != pend)
1498 {
1499 if (!pbucket->empty())
1500 {
1501 last = pbucket;
1502 }
1503
1504 ++pbucket;
1505 }
1506 }
1507 }
1508 }
1509
1510 //*********************************************************************
1512 //*********************************************************************
1513 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1514 {
1515 local_iterator inext = bucket.erase_after(iprevious); // Unlink from the bucket.
1516 icurrent->key_value_pair.~value_type(); // Destroy the value.
1517 pnodepool->release(&*icurrent); // Release it back to the pool.
1518 adjust_first_last_markers_after_erase(&bucket);
1519 ETL_DECREMENT_DEBUG_COUNT;
1520
1521 return inext;
1522 }
1523
1524 // Disable copy construction.
1525 iunordered_map(const iunordered_map&);
1526
1528 pool_t* pnodepool;
1529
1531 bucket_t* pbuckets;
1532
1534 const size_t number_of_buckets;
1535
1537 bucket_t* first;
1538 bucket_t* last;
1539
1541 hasher key_hash_function;
1542
1544 key_equal key_equal_function;
1545
1547 ETL_DECLARE_DEBUG_COUNT;
1548
1549 //*************************************************************************
1551 //*************************************************************************
1552#if defined(ETL_POLYMORPHIC_UNORDERED_MAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
1553 public:
1554 virtual ~iunordered_map()
1555 {
1556 }
1557#else
1558 protected:
1560 {
1561 }
1562#endif
1563 };
1564
1565 //***************************************************************************
1571 //***************************************************************************
1572 template <typename TKey, typename T, typename THash, typename TKeyEqual>
1575 {
1576 const bool sizes_match = (lhs.size() == rhs.size());
1577 bool elements_match = true;
1578
1580
1581 if (sizes_match)
1582 {
1583 itr_t l_begin = lhs.begin();
1584 itr_t l_end = lhs.end();
1585
1586 while ((l_begin != l_end) && elements_match)
1587 {
1588 const TKey key = l_begin->first;
1589 const T l_value = l_begin->second;
1590
1591 // See if the lhs key exists in the rhs.
1592 ETL_OR_STD::pair<itr_t, itr_t> range = rhs.equal_range(key);
1593
1594 if (range.first != rhs.end())
1595 {
1596 // See if the values match
1597 const T r_value = range.first->second;
1598
1600 }
1601 else
1602 {
1603 elements_match = false;
1604 }
1605
1606 ++l_begin;
1607 }
1608 }
1609
1610 return (sizes_match && elements_match);
1611 }
1612
1613 //***************************************************************************
1619 //***************************************************************************
1620 template <typename TKey, typename T, typename THash, typename TKeyEqual>
1626
1627 //*************************************************************************
1629 //*************************************************************************
1630 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> >
1631 class unordered_map : public etl::iunordered_map<TKey, TValue, THash, TKeyEqual>
1632 {
1633 private:
1634
1636
1637 public:
1638
1639 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1640 static ETL_CONSTANT size_t MAX_BUCKETS = MAX_BUCKETS_;
1641
1642 //*************************************************************************
1644 //*************************************************************************
1645 unordered_map(const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1646 : base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
1647 {
1648 }
1649
1650 //*************************************************************************
1652 //*************************************************************************
1654 : base(node_pool, buckets, MAX_BUCKETS_, other.hash_function(), other.key_eq())
1655 {
1656 base::assign(other.cbegin(), other.cend());
1657 }
1658
1659#if ETL_USING_CPP11
1660 //*************************************************************************
1662 //*************************************************************************
1664 : base(node_pool, buckets, MAX_BUCKETS_, other.hash_function(), other.key_eq())
1665 {
1666 if (this != &other)
1667 {
1668 base::move(other.begin(), other.end());
1669 }
1670 }
1671#endif
1672
1673 //*************************************************************************
1678 //*************************************************************************
1679 template <typename TIterator>
1681 : base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
1682 {
1683 base::assign(first_, last_);
1684 }
1685
1686#if ETL_HAS_INITIALIZER_LIST
1687 //*************************************************************************
1689 //*************************************************************************
1690 unordered_map(std::initializer_list<ETL_OR_STD::pair<TKey, TValue>> init, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1691 : base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
1692 {
1693 base::assign(init.begin(), init.end());
1694 }
1695#endif
1696
1697 //*************************************************************************
1699 //*************************************************************************
1701 {
1702 base::initialise();
1703 }
1704
1705 //*************************************************************************
1707 //*************************************************************************
1709 {
1710 base::operator=(rhs);
1711 return *this;
1712 }
1713
1714#if ETL_USING_CPP11
1715 //*************************************************************************
1717 //*************************************************************************
1719 {
1720 base::operator=(etl::move(rhs));
1721 return *this;
1722 }
1723#endif
1724
1725 private:
1726
1729
1731 typename base::bucket_t buckets[MAX_BUCKETS_];
1732 };
1733
1734 //*************************************************************************
1736 //*************************************************************************
1737#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1738 template <typename... TPairs>
1739 unordered_map(TPairs...) -> unordered_map<typename etl::nth_type_t<0, TPairs...>::first_type,
1740 typename etl::nth_type_t<0, TPairs...>::second_type,
1741 sizeof...(TPairs)>;
1742#endif
1743
1744 //*************************************************************************
1746 //*************************************************************************
1747#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1748 template <typename TKey, typename T, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey>, typename... TPairs>
1749 constexpr auto make_unordered_map(TPairs&&... pairs) -> etl::unordered_map<TKey, T, sizeof...(TPairs), sizeof...(TPairs), THash, TKeyEqual>
1750 {
1751 return { etl::forward<TPairs>(pairs)... };
1752 }
1753#endif
1754}
1755
1756#endif
Definition unordered_map.h:334
Definition unordered_map.h:191
A templated unordered_map implementation that uses a fixed size buffer.
Definition unordered_map.h:1632
unordered_map(const unordered_map &other)
Copy constructor.
Definition unordered_map.h:1653
unordered_map(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_map.h:1645
~unordered_map()
Destructor.
Definition unordered_map.h:1700
unordered_map(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_map.h:1680
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:966
#define ETL_ASSERT(b, e)
Definition error_handler.h:316
Definition exception.h:47
ETL_CONSTEXPR17 etl::enable_if<!etl::is_same< T, etl::nullptr_t >::value, T >::type * addressof(T &t)
Definition addressof.h:52
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
float load_factor() const
Definition unordered_map.h:1307
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_map.h:1075
size_type get_bucket_index(const_key_reference key) const
Definition unordered_map.h:597
iterator begin()
Definition unordered_map.h:489
void initialise()
Initialise the unordered_map.
Definition unordered_map.h:1383
const_iterator find(const_key_reference key) const
Definition unordered_map.h:1183
size_type size() const
Gets the size of the unordered_map.
Definition unordered_map.h:1257
const_local_iterator cend(size_t i) const
Definition unordered_map.h:588
~iunordered_map()
Destructor.
Definition unordered_map.h:1559
iterator end()
Definition unordered_map.h:543
size_t available() const
Definition unordered_map.h:1298
local_iterator end(size_t i)
Definition unordered_map.h:570
hasher hash_function() const
Definition unordered_map.h:1316
const_local_iterator cbegin(size_t i) const
Definition unordered_map.h:534
local_iterator begin(size_t i)
Definition unordered_map.h:516
const_local_iterator end(size_t i) const
Definition unordered_map.h:579
iunordered_map & operator=(const iunordered_map &rhs)
Assignment operator.
Definition unordered_map.h:1333
size_type bucket_size(const_key_reference key) const
Definition unordered_map.h:606
void insert(TIterator first_, TIterator last_)
Definition unordered_map.h:1002
size_type max_bucket_count() const
Definition unordered_map.h:617
const_iterator end() const
Definition unordered_map.h:552
mapped_reference operator[](const_key_reference key)
Definition unordered_map.h:681
bool full() const
Checks to see if the unordered_map is full.
Definition unordered_map.h:1289
size_t count(const_key_reference key) const
Definition unordered_map.h:1139
iterator find(const_key_reference key)
Definition unordered_map.h:1149
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition unordered_map.h:1241
const_iterator begin() const
Definition unordered_map.h:498
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition unordered_map.h:1220
void clear()
Clears the unordered_map.
Definition unordered_map.h:1129
iterator erase(const_iterator ielement)
Definition unordered_map.h:1047
iunordered_map(pool_t &node_pool_, bucket_t *pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
Constructor.
Definition unordered_map.h:1369
const_local_iterator begin(size_t i) const
Definition unordered_map.h:525
bool empty() const
Checks to see if the unordered_map is empty.
Definition unordered_map.h:1281
key_equal key_eq() const
Definition unordered_map.h:1325
mapped_reference at(const_key_reference key)
Definition unordered_map.h:725
size_t erase(const_key_reference key)
Definition unordered_map.h:1016
const key_type & const_key_reference
Defines the parameter types.
Definition unordered_map.h:146
size_type capacity() const
Gets the maximum possible size of the unordered_map.
Definition unordered_map.h:1273
size_type bucket_count() const
Definition unordered_map.h:626
const_iterator cend() const
Definition unordered_map.h:561
iterator insert(const_iterator, const_reference key_value_pair)
Definition unordered_map.h:976
const_mapped_reference at(const_key_reference key) const
Definition unordered_map.h:760
size_type max_size() const
Gets the maximum possible size of the unordered_map.
Definition unordered_map.h:1265
ETL_OR_STD::pair< iterator, bool > insert(const_reference key_value_pair)
Definition unordered_map.h:819
void assign(TIterator first_, TIterator last_)
Definition unordered_map.h:797
const_iterator cbegin() const
Definition unordered_map.h:507
Definition unordered_map.h:127
Definition unordered_map.h:70
Definition unordered_map.h:84
Definition unordered_map.h:111
Definition unordered_map.h:98
bitset_ext
Definition absolute.h:38
Definition compare.h:51
iterator
Definition iterator.h:399
Definition unordered_map.h:158
pair holds two objects of arbitrary type
Definition utility.h:164
T1 first
first is a copy of the first object
Definition utility.h:168
T2 second
second is a copy of the second object
Definition utility.h:169