Embedded Template Library 1.0
Loading...
Searching...
No Matches
unordered_set.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_SET_INCLUDED
32#define ETL_UNORDERED_SET_INCLUDED
33
34#include "platform.h"
35#include "algorithm.h"
36#include "iterator.h"
37#include "functional.h"
38#include "utility.h"
39#include "pool.h"
40#include "vector.h"
42#include "hash.h"
43#include "type_traits.h"
44#include "nth_type.h"
45#include "parameter_type.h"
46#include "nullptr.h"
47#include "error_handler.h"
48#include "exception.h"
49#include "error_handler.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_set_exception(ETL_ERROR_TEXT("unordered_set:full", ETL_UNORDERED_SET_FILE_ID"A"), file_name_, line_number_)
89 {
90 }
91 };
92
93 //***************************************************************************
96 //***************************************************************************
98 {
99 public:
100
102 : etl::unordered_set_exception(ETL_ERROR_TEXT("unordered_set:range", ETL_UNORDERED_SET_FILE_ID"B"), file_name_, line_number_)
103 {}
104 };
105
106 //***************************************************************************
109 //***************************************************************************
111 {
112 public:
113
115 : etl::unordered_set_exception(ETL_ERROR_TEXT("unordered_set:iterator", ETL_UNORDERED_SET_FILE_ID"C"), file_name_, line_number_)
116 {
117 }
118 };
119
120 //***************************************************************************
124 //***************************************************************************
125 template <typename TKey, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
127 {
128 public:
129
130 typedef TKey value_type;
131 typedef TKey key_type;
132 typedef THash hasher;
133 typedef TKeyEqual key_equal;
134 typedef value_type& reference;
135 typedef const value_type& const_reference;
136#if ETL_USING_CPP11
138#endif
139 typedef value_type* pointer;
140 typedef const value_type* const_pointer;
141 typedef size_t size_type;
142
143 typedef const TKey& key_parameter_t;
144
146
147 //*********************************************************************
148 // The nodes that store the elements.
149 struct node_t : public link_t
150 {
152 : key(key_)
153 {
154 }
155
156 value_type key;
157 };
158
159 friend bool operator ==(const node_t& lhs, const node_t& rhs)
160 {
161 return (lhs.key == rhs.key);
162 }
163
164 friend bool operator !=(const node_t& lhs, const node_t& rhs)
165 {
166 return !(lhs == rhs);
167 }
168
169 protected:
170
172 typedef etl::ipool pool_t;
173
174 public:
175
176 // Local iterators iterate over one bucket.
177 typedef typename bucket_t::iterator local_iterator;
178 typedef typename bucket_t::const_iterator const_local_iterator;
179
180 //*********************************************************************
181 class iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, TKey>
182 {
183 public:
184
186 typedef typename iunordered_set::key_type key_type;
187 typedef typename iunordered_set::hasher hasher;
188 typedef typename iunordered_set::key_equal key_equal;
189 typedef typename iunordered_set::reference reference;
191 typedef typename iunordered_set::pointer pointer;
193 typedef typename iunordered_set::size_type size_type;
194
195 friend class iunordered_set;
196 friend class const_iterator;
197
198 //*********************************
199 iterator()
200 {
201 }
202
203 //*********************************
204 iterator(const iterator& other)
205 : pbuckets_end(other.pbuckets_end)
206 , pbucket(other.pbucket)
207 , inode(other.inode)
208 {
209 }
210
211 //*********************************
213 {
214 ++inode;
215
216 // The end of this node list?
217 if (inode == pbucket->end())
218 {
219 // Search for the next non-empty bucket.
220 ++pbucket;
221 while ((pbucket != pbuckets_end) && (pbucket->empty()))
222 {
223 ++pbucket;
224 }
225
226 // If not past the end, get the first node in the bucket.
227 if (pbucket != pbuckets_end)
228 {
229 inode = pbucket->begin();
230 }
231 }
232
233 return *this;
234 }
235
236 //*********************************
238 {
239 iterator temp(*this);
240 operator++();
241 return temp;
242 }
243
244 //*********************************
246 {
247 pbuckets_end = other.pbuckets_end;
248 pbucket = other.pbucket;
249 inode = other.inode;
250 return *this;
251 }
252
253 //*********************************
254 reference operator *() const
255 {
256 return inode->key;
257 }
258
259 //*********************************
260 pointer operator &() const
261 {
262 return &(inode->key);
263 }
264
265 //*********************************
266 pointer operator ->() const
267 {
268 return &(inode->key);
269 }
270
271 //*********************************
272 friend bool operator == (const iterator& lhs, const iterator& rhs)
273 {
274 return lhs.compare(rhs);
275 }
276
277 //*********************************
278 friend bool operator != (const iterator& lhs, const iterator& rhs)
279 {
280 return !(lhs == rhs);
281 }
282
283 private:
284
285 //*********************************
287 : pbuckets_end(pbuckets_end_)
288 , pbucket(pbucket_)
289 , inode(inode_)
290 {
291 }
292
293 //*********************************
294 bool compare(const iterator& rhs) const
295 {
296 return rhs.inode == inode;
297 }
298
299 //*********************************
300 bucket_t& get_bucket()
301 {
302 return *pbucket;
303 }
304
305 //*********************************
306 bucket_t*& get_bucket_list_iterator()
307 {
308 return pbucket;
309 }
310
311 //*********************************
312 local_iterator get_local_iterator()
313 {
314 return inode;
315 }
316
317 bucket_t* pbuckets_end;
318 bucket_t* pbucket;
319 local_iterator inode;
320 };
321
322 //*********************************************************************
323 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const TKey>
324 {
325 public:
326
328 typedef typename iunordered_set::key_type key_type;
329 typedef typename iunordered_set::hasher hasher;
330 typedef typename iunordered_set::key_equal key_equal;
331 typedef typename iunordered_set::reference reference;
333 typedef typename iunordered_set::pointer pointer;
335 typedef typename iunordered_set::size_type size_type;
336
337 friend class iunordered_set;
338 friend class iterator;
339
340 //*********************************
342 {
343 }
344
345 //*********************************
347 : pbuckets_end(other.pbuckets_end)
348 , pbucket(other.pbucket)
349 , inode(other.inode)
350 {
351 }
352
353 //*********************************
355 : pbuckets_end(other.pbuckets_end)
356 , pbucket(other.pbucket)
357 , inode(other.inode)
358 {
359 }
360
361 //*********************************
363 {
364 ++inode;
365
366 // The end of this node list?
367 if (inode == pbucket->end())
368 {
369 // Search for the next non-empty bucket.
370
371 ++pbucket;
372 while ((pbucket != pbuckets_end) && (pbucket->empty()))
373 {
374 ++pbucket;
375 }
376
377 // If not past the end, get the first node in the bucket.
378 if (pbucket != pbuckets_end)
379 {
380 inode = pbucket->begin();
381 }
382 }
383
384 return *this;
385 }
386
387 //*********************************
389 {
390 const_iterator temp(*this);
391 operator++();
392 return temp;
393 }
394
395 //*********************************
397 {
398 pbuckets_end = other.pbuckets_end;
399 pbucket = other.pbucket;
400 inode = other.inode;
401 return *this;
402 }
403
404 //*********************************
406 {
407 return inode->key;
408 }
409
410 //*********************************
412 {
413 return &(inode->key);
414 }
415
416 //*********************************
418 {
419 return &(inode->key);
420 }
421
422 //*********************************
423 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
424 {
425 return lhs.compare(rhs);
426 }
427
428 //*********************************
429 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
430 {
431 return !(lhs == rhs);
432 }
433
434 private:
435
436 //*********************************
438 : pbuckets_end(pbuckets_end_)
439 , pbucket(pbucket_)
440 , inode(inode_)
441 {
442 }
443
444 //*********************************
445 bool compare(const const_iterator& rhs) const
446 {
447 return rhs.inode == inode;
448 }
449
450 //*********************************
451 bucket_t& get_bucket()
452 {
453 return *pbucket;
454 }
455
456 //*********************************
457 bucket_t*& get_bucket_list_iterator()
458 {
459 return pbucket;
460 }
461
462 //*********************************
463 local_iterator get_local_iterator()
464 {
465 return inode;
466 }
467
468 bucket_t* pbuckets_end;
469 bucket_t* pbucket;
470 local_iterator inode;
471 };
472
473 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
474
475 //*********************************************************************
478 //*********************************************************************
480 {
481 return iterator(pbuckets + number_of_buckets, first, first->begin());
482 }
483
484 //*********************************************************************
487 //*********************************************************************
489 {
490 return const_iterator(pbuckets + number_of_buckets, first, first->begin());
491 }
492
493 //*********************************************************************
496 //*********************************************************************
498 {
499 return const_iterator(pbuckets + number_of_buckets, first, first->begin());
500 }
501
502 //*********************************************************************
505 //*********************************************************************
506 local_iterator begin(size_t i)
507 {
508 return pbuckets[i].begin();
509 }
510
511 //*********************************************************************
514 //*********************************************************************
515 const_local_iterator begin(size_t i) const
516 {
517 return pbuckets[i].cbegin();
518 }
519
520 //*********************************************************************
523 //*********************************************************************
524 const_local_iterator cbegin(size_t i) const
525 {
526 return pbuckets[i].cbegin();
527 }
528
529 //*********************************************************************
532 //*********************************************************************
534 {
535 return iterator(pbuckets + number_of_buckets, last, last->end());
536 }
537
538 //*********************************************************************
541 //*********************************************************************
543 {
544 return const_iterator(pbuckets + number_of_buckets, last, last->end());
545 }
546
547 //*********************************************************************
550 //*********************************************************************
552 {
553 return const_iterator(pbuckets + number_of_buckets, last, last->end());
554 }
555
556 //*********************************************************************
559 //*********************************************************************
560 local_iterator end(size_t i)
561 {
562 return pbuckets[i].end();
563 }
564
565 //*********************************************************************
568 //*********************************************************************
569 const_local_iterator end(size_t i) const
570 {
571 return pbuckets[i].cend();
572 }
573
574 //*********************************************************************
577 //*********************************************************************
578 const_local_iterator cend(size_t i) const
579 {
580 return pbuckets[i].cend();
581 }
582
583 //*********************************************************************
586 //*********************************************************************
588 {
589 return key_hash_function(key) % number_of_buckets;
590 }
591
592 //*********************************************************************
595 //*********************************************************************
597 {
598 size_t index = bucket(key);
599
600 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
601 }
602
603 //*********************************************************************
606 //*********************************************************************
608 {
609 return number_of_buckets;
610 }
611
612 //*********************************************************************
615 //*********************************************************************
617 {
618 return number_of_buckets;
619 }
620
621 //*********************************************************************
627 //*********************************************************************
628 template <typename TIterator>
630 {
631#if ETL_IS_DEBUG_BUILD
632 difference_type d = etl::distance(first_, last_);
633 ETL_ASSERT(d >= 0, ETL_ERROR(unordered_set_iterator));
634 ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_set_full));
635#endif
636
637 clear();
638
639 while (first_ != last_)
640 {
641 insert(*first_);
642 ++first_;
643 }
644 }
645
646 //*********************************************************************
650 //*********************************************************************
651 ETL_OR_STD::pair<iterator, bool> insert(const_reference key)
652 {
653 ETL_OR_STD::pair<iterator, bool> result(end(), false);
654
655 if (full())
656 {
657 iterator iter = find(key);
658 if (iter == end())
659 {
660 ETL_ASSERT_FAIL(ETL_ERROR(unordered_set_full));
661 }
662 else
663 {
664 result.first = iter;
665 result.second = false;
666 return result;
667 }
668 }
669
670 // Get the hash index.
671 size_t index = get_bucket_index(key);
672
673 // Get the bucket & bucket iterator.
674 bucket_t* pbucket = pbuckets + index;
675 bucket_t& bucket = *pbucket;
676
677 // The first one in the bucket?
678 if (bucket.empty())
679 {
680 // Get a new node.
681 node_t* node = allocate_data_node();
682 node->clear();
683 ::new (&node->key) value_type(key);
684 ETL_INCREMENT_DEBUG_COUNT;
685
686 // Just add the pointer to the bucket;
687 bucket.insert_after(bucket.before_begin(), *node);
688 adjust_first_last_markers_after_insert(&bucket);
689
690 result.first = iterator(pbuckets + number_of_buckets, pbucket, pbucket->begin());
691 result.second = true;
692 }
693 else
694 {
695 // Step though the bucket looking for a place to insert.
696 local_iterator inode_previous = bucket.before_begin();
697 local_iterator inode = bucket.begin();
698
699 while (inode != bucket.end())
700 {
701 // Do we already have this key?
702 if (key_equal_function(inode->key, key))
703 {
704 break;
705 }
706
708 ++inode;
709 }
710
711 // Not already there?
712 if (inode == bucket.end())
713 {
714 // Get a new node.
715 node_t* node = allocate_data_node();
716 node->clear();
717 ::new (&node->key) value_type(key);
718 ETL_INCREMENT_DEBUG_COUNT;
719
720 // Add the node to the end of the bucket;
721 bucket.insert_after(inode_previous, *node);
722 adjust_first_last_markers_after_insert(&bucket);
724
725 result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
726 result.second = true;
727 }
728 }
729
730 return result;
731 }
732
733#if ETL_USING_CPP11
734 //*********************************************************************
738 //*********************************************************************
739 ETL_OR_STD::pair<iterator, bool> insert(rvalue_reference key)
740 {
741 ETL_OR_STD::pair<iterator, bool> result(end(), false);
742
743 if (full())
744 {
745 iterator iter = find(key);
746 if (iter == end())
747 {
748 ETL_ASSERT_FAIL(ETL_ERROR(unordered_set_full));
749 }
750 else
751 {
752 result.first = iter;
753 result.second = false;
754 return result;
755 }
756 }
757
758 // Get the hash index.
759 size_t index = get_bucket_index(key);
760
761 // Get the bucket & bucket iterator.
762 bucket_t* pbucket = pbuckets + index;
763 bucket_t& bucket = *pbucket;
764
765 // The first one in the bucket?
766 if (bucket.empty())
767 {
768 // Get a new node.
769 node_t* node = allocate_data_node();
770 node->clear();
771 ::new (&node->key) value_type(etl::move(key));
772 ETL_INCREMENT_DEBUG_COUNT;
773
774 // Just add the pointer to the bucket;
775 bucket.insert_after(bucket.before_begin(), *node);
776 adjust_first_last_markers_after_insert(&bucket);
777
778 result.first = iterator(pbuckets + number_of_buckets, pbucket, pbucket->begin());
779 result.second = true;
780 }
781 else
782 {
783 // Step though the bucket looking for a place to insert.
784 local_iterator inode_previous = bucket.before_begin();
785 local_iterator inode = bucket.begin();
786
787 while (inode != bucket.end())
788 {
789 // Do we already have this key?
790 if (key_equal_function(inode->key, key))
791 {
792 break;
793 }
794
795 ++inode_previous;
796 ++inode;
797 }
798
799 // Not already there?
800 if (inode == bucket.end())
801 {
802 // Get a new node.
803 node_t* node = allocate_data_node();
804 node->clear();
805 ::new (&node->key) value_type(etl::move(key));
806 ETL_INCREMENT_DEBUG_COUNT;
807
808 // Add the node to the end of the bucket;
809 bucket.insert_after(inode_previous, *node);
810 adjust_first_last_markers_after_insert(&bucket);
811 ++inode_previous;
812
813 result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
814 result.second = true;
815 }
816 }
817
818 return result;
819 }
820#endif
821
822 //*********************************************************************
827 //*********************************************************************
829 {
830 return insert(key).first;
831 }
832
833#if ETL_USING_CPP11
834 //*********************************************************************
839 //*********************************************************************
840 iterator insert(const_iterator, rvalue_reference key)
841 {
842 return insert(etl::move(key)).first;
843 }
844#endif
845
846 //*********************************************************************
852 //*********************************************************************
853 template <class TIterator>
855 {
856 while (first_ != last_)
857 {
858 insert(*first_);
859 ++first_;
860 }
861 }
862
863 //*********************************************************************
867 //*********************************************************************
869 {
870 size_t n = 0UL;
871 size_t index = get_bucket_index(key);
872
873 bucket_t& bucket = pbuckets[index];
874
875 local_iterator iprevious = bucket.before_begin();
876 local_iterator icurrent = bucket.begin();
877
878 // Search for the key, if we have it.
879 while ((icurrent != bucket.end()) && (!key_equal_function(icurrent->key, key)))
880 {
881 ++iprevious;
882 ++icurrent;
883 }
884
885 // Did we find it?
886 if (icurrent != bucket.end())
887 {
888 delete_data_node(iprevious, icurrent, bucket);
889 n = 1;
890 }
891
892 return n;
893 }
894
895 //*********************************************************************
898 //*********************************************************************
900 {
901 // Make a note of the next one.
902 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
903 ++inext;
904
905 bucket_t& bucket = ielement.get_bucket();
906 local_iterator iprevious = bucket.before_begin();
907 local_iterator icurrent = ielement.get_local_iterator();
908
909 // Find the node previous to the one we're interested in.
910 while (iprevious->etl_next != &*icurrent)
911 {
912 ++iprevious;
913 }
914
915 delete_data_node(iprevious, icurrent, bucket);
916
917 return inext;
918 }
919
920 //*********************************************************************
926 //*********************************************************************
928 {
929 // Erasing everything?
930 if ((first_ == begin()) && (last_ == end()))
931 {
932 clear();
933 return end();
934 }
935
936 // Get the starting point.
937 bucket_t* pbucket = first_.get_bucket_list_iterator();
938 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
939 local_iterator iprevious = pbucket->before_begin();
940 local_iterator icurrent = first_.get_local_iterator();
941 local_iterator iend = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
942
943 // Find the node previous to the first one.
944 while (iprevious->etl_next != &*icurrent)
945 {
946 ++iprevious;
947 }
948
949 // Remember the item before the first erased one.
950 iterator ibefore_erased = iterator((pbuckets + number_of_buckets), pbucket, iprevious);
951
952 // Until we reach the end.
953 while ((icurrent != iend) || (pbucket != pend_bucket))
954 {
955 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
956
957 // Have we not reached the end?
958 if ((icurrent != iend) || (pbucket != pend_bucket))
959 {
960 // At the end of this bucket?
961 if ((icurrent == pbucket->end()))
962 {
963 // Find the next non-empty one.
964 do
965 {
966 ++pbucket;
967 } while (pbucket->empty());
968
969 iprevious = pbucket->before_begin();
970 icurrent = pbucket->begin();
971 }
972 }
973 }
974
975 return ++ibefore_erased;
976 }
977
978 //*************************************************************************
980 //*************************************************************************
981 void clear()
982 {
983 initialise();
984 }
985
986 //*********************************************************************
990 //*********************************************************************
991 size_t count(key_parameter_t key) const
992 {
993 return (find(key) == end()) ? 0 : 1;
994 }
995
996 //*********************************************************************
1000 //*********************************************************************
1002 {
1003 size_t index = get_bucket_index(key);
1004
1005 bucket_t* pbucket = pbuckets + index;
1006 bucket_t& bucket = *pbucket;
1007
1008 // Is the bucket not empty?
1009 if (!bucket.empty())
1010 {
1011 // Step though the list until we find the end or an equivalent key.
1012 local_iterator inode = bucket.begin();
1013 local_iterator iend = bucket.end();
1014
1015 while (inode != iend)
1016 {
1017 // Do we have this one?
1018 if (key_equal_function(key, inode->key))
1019 {
1020 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1021 }
1022
1023 ++inode;
1024 }
1025 }
1026
1027 return end();
1028 }
1029
1030 //*********************************************************************
1034 //*********************************************************************
1036 {
1037 size_t index = get_bucket_index(key);
1038
1039 bucket_t* pbucket = pbuckets + index;
1040 bucket_t& bucket = *pbucket;
1041
1042 // Is the bucket not empty?
1043 if (!bucket.empty())
1044 {
1045 // Step though the list until we find the end or an equivalent key.
1046 local_iterator inode = bucket.begin();
1047 local_iterator iend = bucket.end();
1048
1049 while (inode != iend)
1050 {
1051 // Do we have this one?
1052 if (key_equal_function(key, inode->key))
1053 {
1054 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1055 }
1056
1057 ++inode;
1058 }
1059 }
1060
1061 return end();
1062 }
1063
1064 //*********************************************************************
1071 //*********************************************************************
1072 ETL_OR_STD::pair<iterator, iterator> equal_range(key_parameter_t key)
1073 {
1074 iterator f = find(key);
1075 iterator l = f;
1076
1077 if (l != end())
1078 {
1079 ++l;
1080 }
1081
1082 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1083 }
1084
1085 //*********************************************************************
1092 //*********************************************************************
1093 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
1094 {
1095 const_iterator f = find(key);
1096 const_iterator l = f;
1097
1098 if (l != end())
1099 {
1100 ++l;
1101 }
1102
1103 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1104 }
1105
1106 //*************************************************************************
1108 //*************************************************************************
1110 {
1111 return pnodepool->size();
1112 }
1113
1114 //*************************************************************************
1116 //*************************************************************************
1118 {
1119 return pnodepool->max_size();
1120 }
1121
1122 //*************************************************************************
1124 //*************************************************************************
1126 {
1127 return pnodepool->max_size();
1128 }
1129
1130 //*************************************************************************
1132 //*************************************************************************
1133 bool empty() const
1134 {
1135 return pnodepool->empty();
1136 }
1137
1138 //*************************************************************************
1140 //*************************************************************************
1141 bool full() const
1142 {
1143 return pnodepool->full();
1144 }
1145
1146 //*************************************************************************
1149 //*************************************************************************
1150 size_t available() const
1151 {
1152 return pnodepool->available();
1153 }
1154
1155 //*************************************************************************
1158 //*************************************************************************
1159 float load_factor() const
1160 {
1161 return static_cast<float>(size()) / static_cast<float>(bucket_count());
1162 }
1163
1164 //*************************************************************************
1167 //*************************************************************************
1169 {
1170 return key_hash_function;
1171 }
1172
1173 //*************************************************************************
1176 //*************************************************************************
1178 {
1179 return key_equal_function;
1180 }
1181
1182 //*************************************************************************
1184 //*************************************************************************
1186 {
1187 // Skip if doing self assignment
1188 if (this != &rhs)
1189 {
1190 key_hash_function = rhs.hash_function();
1191 key_equal_function = rhs.key_eq();
1192 assign(rhs.cbegin(), rhs.cend());
1193 }
1194
1195 return *this;
1196 }
1197
1198#if ETL_USING_CPP11
1199 //*************************************************************************
1201 //*************************************************************************
1203 {
1204 // Skip if doing self assignment
1205 if (this != &rhs)
1206 {
1207 clear();
1208 key_hash_function = rhs.hash_function();
1209 key_equal_function = rhs.key_eq();
1210 move(rhs.begin(), rhs.end());
1211 }
1212
1213 return *this;
1214 }
1215#endif
1216
1217 protected:
1218
1219 //*********************************************************************
1221 //*********************************************************************
1223 : pnodepool(&node_pool_)
1224 , pbuckets(pbuckets_)
1225 , number_of_buckets(number_of_buckets_)
1226 , first(pbuckets)
1227 , last(pbuckets)
1228 , key_hash_function(key_hash_function_)
1229 , key_equal_function(key_equal_function_)
1230 {
1231 }
1232
1233 //*********************************************************************
1235 //*********************************************************************
1237 {
1238 if (!empty())
1239 {
1240 // For each bucket...
1241 for (size_t i = 0UL; i < number_of_buckets; ++i)
1242 {
1243 bucket_t& bucket = pbuckets[i];
1244
1245 if (!bucket.empty())
1246 {
1247 // For each item in the bucket...
1248 local_iterator it = bucket.begin();
1249
1250 while (it != bucket.end())
1251 {
1252 // Destroy the value contents.
1253 it->key.~value_type();
1254 ++it;
1255 ETL_DECREMENT_DEBUG_COUNT;
1256 }
1257
1258 // Now it's safe to clear the bucket.
1259 bucket.clear();
1260 }
1261 }
1262
1263 // Now it's safe to clear the entire pool in one go.
1264 pnodepool->release_all();
1265 }
1266
1267 first = pbuckets;
1268 last = first;
1269 }
1270
1271#if ETL_USING_CPP11
1272 //*************************************************************************
1274 //*************************************************************************
1275 void move(iterator b, iterator e)
1276 {
1277#if ETL_IS_DEBUG_BUILD
1278 difference_type d = etl::distance(b, e);
1279 ETL_ASSERT(d >= 0, ETL_ERROR(unordered_set_iterator));
1280 ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_set_full));
1281#endif
1282
1283 while (b != e)
1284 {
1285 iterator temp = b;
1286 ++temp;
1287 insert(etl::move(*b));
1288 b = temp;
1289 }
1290 }
1291#endif
1292
1293 private:
1294
1295 //*************************************************************************
1297 //*************************************************************************
1298 node_t* allocate_data_node()
1299 {
1300 node_t* (etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1301 return (pnodepool->*func)();
1302 }
1303
1304 //*********************************************************************
1306 //*********************************************************************
1307 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1308 {
1309 if (size() == 1)
1310 {
1311 first = pbucket;
1312 last = pbucket;
1313 }
1314 else
1315 {
1316 if (pbucket < first)
1317 {
1318 first = pbucket;
1319 }
1320 else if (pbucket > last)
1321 {
1322 last = pbucket;
1323 }
1324 }
1325 }
1326
1327 //*********************************************************************
1329 //*********************************************************************
1330 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1331 {
1332 if (empty())
1333 {
1334 first = pbuckets;
1335 last = pbuckets;
1336 }
1337 else
1338 {
1339 if (pbucket == first)
1340 {
1341 // We erased the first so, we need to search again from where we erased.
1342 while (first->empty())
1343 {
1344 ++first;
1345 }
1346 }
1347 else if (pbucket == last)
1348 {
1349 // We erased the last, so we need to search again. Start from the first, go no further than the current last.
1350 pbucket = first;
1351 bucket_t* pend = last;
1352
1353 last = first;
1354
1355 while (pbucket != pend)
1356 {
1357 if (!pbucket->empty())
1358 {
1359 last = pbucket;
1360 }
1361
1362 ++pbucket;
1363 }
1364 }
1365 }
1366 }
1367
1368 //*********************************************************************
1370 //*********************************************************************
1371 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1372 {
1373 local_iterator inext = bucket.erase_after(iprevious); // Unlink from the bucket.
1374 icurrent->key.~value_type(); // Destroy the value.
1375 pnodepool->release(&*icurrent); // Release it back to the pool.
1376 adjust_first_last_markers_after_erase(&bucket);
1377 ETL_DECREMENT_DEBUG_COUNT;
1378
1379 return inext;
1380 }
1381
1382 // Disable copy construction.
1383 iunordered_set(const iunordered_set&);
1384
1386 pool_t* pnodepool;
1387
1389 bucket_t* pbuckets;
1390
1392 const size_t number_of_buckets;
1393
1395 bucket_t* first;
1396 bucket_t* last;
1397
1399 hasher key_hash_function;
1400
1402 key_equal key_equal_function;
1403
1405 ETL_DECLARE_DEBUG_COUNT;
1406
1407 //*************************************************************************
1409 //*************************************************************************
1410#if defined(ETL_POLYMORPHIC_UNORDERED_SET) || defined(ETL_POLYMORPHIC_CONTAINERS)
1411 public:
1412 virtual ~iunordered_set()
1413 {
1414 }
1415#else
1416 protected:
1418 {
1419 }
1420#endif
1421 };
1422
1423 //***************************************************************************
1429 //***************************************************************************
1430 template <typename TKey, typename THash, typename TKeyEqual>
1433 {
1434 const bool sizes_match = (lhs.size() == rhs.size());
1435 bool elements_match = true;
1436
1438
1439 if (sizes_match)
1440 {
1441 itr_t l_begin = lhs.begin();
1442 itr_t l_end = lhs.end();
1443
1444 while ((l_begin != l_end) && elements_match)
1445 {
1446 const TKey l_value = *l_begin;
1447
1448 // See if the lhs key exists in the rhs.
1449 ETL_OR_STD::pair<itr_t, itr_t> range = rhs.equal_range(l_value);
1450
1451 if (range.first != rhs.end())
1452 {
1453 // See if the values match
1454 const TKey r_value = *(range.first);
1455
1457 }
1458 else
1459 {
1460 elements_match = false;
1461 }
1462
1463 ++l_begin;
1464 }
1465 }
1466
1467 return (sizes_match && elements_match);
1468 }
1469
1470 //***************************************************************************
1476 //***************************************************************************
1477 template <typename TKey, typename THash, typename TKeyEqual>
1483
1484 //*************************************************************************
1486 //*************************************************************************
1487 template <typename TKey, const size_t MAX_SIZE_, size_t MAX_BUCKETS_ = MAX_SIZE_, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
1488 class unordered_set : public etl::iunordered_set<TKey, THash, TKeyEqual>
1489 {
1490 private:
1491
1493
1494 public:
1495
1496 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1497 static ETL_CONSTANT size_t MAX_BUCKETS = MAX_BUCKETS_;
1498
1499 //*************************************************************************
1501 //*************************************************************************
1502 unordered_set(const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1503 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1504 {
1505 }
1506
1507 //*************************************************************************
1509 //*************************************************************************
1511 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1512 {
1513 // Skip if doing self assignment
1514 if (this != &other)
1515 {
1516 base::assign(other.cbegin(), other.cend());
1517 }
1518 }
1519
1520#if ETL_USING_CPP11
1521 //*************************************************************************
1523 //*************************************************************************
1525 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1526 {
1527 // Skip if doing self assignment
1528 if (this != &other)
1529 {
1530 base::move(other.begin(), other.end());
1531 }
1532 }
1533#endif
1534
1535 //*************************************************************************
1540 //*************************************************************************
1541 template <typename TIterator>
1543 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1544 {
1545 base::assign(first_, last_);
1546 }
1547
1548#if ETL_HAS_INITIALIZER_LIST
1549 //*************************************************************************
1551 //*************************************************************************
1552 unordered_set(std::initializer_list<TKey> init, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1553 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1554 {
1555 base::assign(init.begin(), init.end());
1556 }
1557#endif
1558
1559 //*************************************************************************
1561 //*************************************************************************
1563 {
1564 base::initialise();
1565 }
1566
1567 //*************************************************************************
1569 //*************************************************************************
1571 {
1572 base::operator=(rhs);
1573
1574 return *this;
1575 }
1576
1577#if ETL_USING_CPP11
1578 //*************************************************************************
1580 //*************************************************************************
1582 {
1583 base::operator=(etl::move(rhs));
1584
1585 return *this;
1586 }
1587#endif
1588
1589 private:
1590
1593
1595 typename base::bucket_t buckets[MAX_BUCKETS_];
1596 };
1597
1598 //*************************************************************************
1600 //*************************************************************************
1601#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1602 template <typename... T>
1603 unordered_set(T...) -> unordered_set<etl::nth_type_t<0, T...>, sizeof...(T)>;
1604#endif
1605
1606 //*************************************************************************
1608 //*************************************************************************
1609#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1610 template <typename TKey, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey>, typename... T>
1611 constexpr auto make_unordered_set(T&&... keys) -> etl::unordered_set<TKey, sizeof...(T), sizeof...(T), THash, TKeyEqual>
1612 {
1613 return { etl::forward<T>(keys)... };
1614 }
1615#endif
1616}
1617
1618#endif
Definition unordered_set.h:324
Definition unordered_set.h:182
A templated unordered_set implementation that uses a fixed size buffer.
Definition unordered_set.h:1489
unordered_set(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_set.h:1542
~unordered_set()
Destructor.
Definition unordered_set.h:1562
unordered_set(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_set.h:1502
unordered_set(const unordered_set &other)
Copy constructor.
Definition unordered_set.h:1510
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
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
size_t count(key_parameter_t key) const
Definition unordered_set.h:991
const_local_iterator begin(size_t i) const
Definition unordered_set.h:515
key_equal key_eq() const
Definition unordered_set.h:1177
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_set.h:927
local_iterator end(size_t i)
Definition unordered_set.h:560
size_type bucket_count() const
Definition unordered_set.h:616
size_type max_size() const
Gets the maximum possible size of the unordered_set.
Definition unordered_set.h:1117
size_type size() const
Gets the size of the unordered_set.
Definition unordered_set.h:1109
iunordered_set(pool_t &node_pool_, bucket_t *pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
Constructor.
Definition unordered_set.h:1222
iunordered_set & operator=(const iunordered_set &rhs)
Assignment operator.
Definition unordered_set.h:1185
local_iterator begin(size_t i)
Definition unordered_set.h:506
void insert(TIterator first_, TIterator last_)
Definition unordered_set.h:854
float load_factor() const
Definition unordered_set.h:1159
const_iterator begin() const
Definition unordered_set.h:488
const_local_iterator cbegin(size_t i) const
Definition unordered_set.h:524
bool full() const
Checks to see if the unordered_set is full.
Definition unordered_set.h:1141
size_type bucket_size(key_parameter_t key) const
Definition unordered_set.h:596
~iunordered_set()
Destructor.
Definition unordered_set.h:1417
size_type get_bucket_index(key_parameter_t key) const
Definition unordered_set.h:587
const_iterator end() const
Definition unordered_set.h:542
void clear()
Clears the unordered_set.
Definition unordered_set.h:981
size_t available() const
Definition unordered_set.h:1150
ETL_OR_STD::pair< iterator, bool > insert(const_reference key)
Definition unordered_set.h:651
iterator insert(const_iterator, const_reference key)
Definition unordered_set.h:828
void assign(TIterator first_, TIterator last_)
Definition unordered_set.h:629
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(key_parameter_t key) const
Definition unordered_set.h:1093
iterator find(key_parameter_t key)
Definition unordered_set.h:1001
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition unordered_set.h:1072
iterator end()
Definition unordered_set.h:533
size_t erase(key_parameter_t key)
Definition unordered_set.h:868
const_iterator find(key_parameter_t key) const
Definition unordered_set.h:1035
hasher hash_function() const
Definition unordered_set.h:1168
bool empty() const
Checks to see if the unordered_set is empty.
Definition unordered_set.h:1133
size_type max_bucket_count() const
Definition unordered_set.h:607
iterator begin()
Definition unordered_set.h:479
const_local_iterator cend(size_t i) const
Definition unordered_set.h:578
const_iterator cend() const
Definition unordered_set.h:551
const_local_iterator end(size_t i) const
Definition unordered_set.h:569
void initialise()
Initialise the unordered_set.
Definition unordered_set.h:1236
size_type capacity() const
Gets the maximum possible size of the unordered_set.
Definition unordered_set.h:1125
const_iterator cbegin() const
Definition unordered_set.h:497
iterator erase(const_iterator ielement)
Definition unordered_set.h:899
Definition unordered_set.h:127
Definition unordered_set.h:70
Definition unordered_set.h:84
Definition unordered_set.h:111
Definition unordered_set.h:98
bitset_ext
Definition absolute.h:38
Definition compare.h:51
iterator
Definition iterator.h:399
Definition unordered_set.h:150
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