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
56
57#include <stddef.h>
58
59//*****************************************************************************
63//*****************************************************************************
64
65namespace etl
66{
67 //***************************************************************************
70 //***************************************************************************
80
81 //***************************************************************************
84 //***************************************************************************
86 {
87 public:
88
90 : etl::unordered_set_exception(ETL_ERROR_TEXT("unordered_set:full", ETL_UNORDERED_SET_FILE_ID"A"), file_name_, line_number_)
91 {
92 }
93 };
94
95 //***************************************************************************
98 //***************************************************************************
100 {
101 public:
102
104 : etl::unordered_set_exception(ETL_ERROR_TEXT("unordered_set:range", ETL_UNORDERED_SET_FILE_ID"B"), file_name_, line_number_)
105 {}
106 };
107
108 //***************************************************************************
111 //***************************************************************************
113 {
114 public:
115
117 : etl::unordered_set_exception(ETL_ERROR_TEXT("unordered_set:iterator", ETL_UNORDERED_SET_FILE_ID"C"), file_name_, line_number_)
118 {
119 }
120 };
121
122 //***************************************************************************
126 //***************************************************************************
127 template <typename TKey, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
129 {
130 public:
131
132 typedef TKey value_type;
133 typedef TKey key_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
140#endif
141 typedef value_type* pointer;
142 typedef const value_type* const_pointer;
143 typedef size_t size_type;
144
145 typedef const TKey& key_parameter_t;
146
148
149 //*********************************************************************
150 // The nodes that store the elements.
151 struct node_t : public link_t
152 {
154 : key(key_)
155 {
156 }
157
158 value_type key;
159 };
160
161 friend bool operator ==(const node_t& lhs, const node_t& rhs)
162 {
163 return (lhs.key == rhs.key);
164 }
165
166 friend bool operator !=(const node_t& lhs, const node_t& rhs)
167 {
168 return !(lhs == rhs);
169 }
170
171 protected:
172
174 typedef etl::ipool pool_t;
175
176 public:
177
178 // Local iterators iterate over one bucket.
179 typedef typename bucket_t::iterator local_iterator;
180 typedef typename bucket_t::const_iterator const_local_iterator;
181
182 //*********************************************************************
183 class iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, TKey>
184 {
185 public:
186
188 typedef typename iunordered_set::key_type key_type;
189 typedef typename iunordered_set::hasher hasher;
190 typedef typename iunordered_set::key_equal key_equal;
191 typedef typename iunordered_set::reference reference;
193 typedef typename iunordered_set::pointer pointer;
195 typedef typename iunordered_set::size_type size_type;
196
197 friend class iunordered_set;
198 friend class const_iterator;
199
200 //*********************************
201 iterator()
202 {
203 }
204
205 //*********************************
206 iterator(const iterator& other)
207 : pbuckets_end(other.pbuckets_end)
208 , pbucket(other.pbucket)
209 , inode(other.inode)
210 {
211 }
212
213 //*********************************
215 {
216 ++inode;
217
218 // The end of this node list?
219 if (inode == pbucket->end())
220 {
221 // Search for the next non-empty bucket.
222 ++pbucket;
223 while ((pbucket != pbuckets_end) && (pbucket->empty()))
224 {
225 ++pbucket;
226 }
227
228 // If not past the end, get the first node in the bucket.
229 if (pbucket != pbuckets_end)
230 {
231 inode = pbucket->begin();
232 }
233 }
234
235 return *this;
236 }
237
238 //*********************************
240 {
241 iterator temp(*this);
242 operator++();
243 return temp;
244 }
245
246 //*********************************
248 {
249 pbuckets_end = other.pbuckets_end;
250 pbucket = other.pbucket;
251 inode = other.inode;
252 return *this;
253 }
254
255 //*********************************
256 reference operator *() const
257 {
258 return inode->key;
259 }
260
261 //*********************************
262 pointer operator &() const
263 {
264 return &(inode->key);
265 }
266
267 //*********************************
268 pointer operator ->() const
269 {
270 return &(inode->key);
271 }
272
273 //*********************************
274 friend bool operator == (const iterator& lhs, const iterator& rhs)
275 {
276 return lhs.compare(rhs);
277 }
278
279 //*********************************
280 friend bool operator != (const iterator& lhs, const iterator& rhs)
281 {
282 return !(lhs == rhs);
283 }
284
285 private:
286
287 //*********************************
289 : pbuckets_end(pbuckets_end_)
290 , pbucket(pbucket_)
291 , inode(inode_)
292 {
293 }
294
295 //*********************************
296 bool compare(const iterator& rhs) const
297 {
298 return rhs.inode == inode;
299 }
300
301 //*********************************
302 bucket_t& get_bucket()
303 {
304 return *pbucket;
305 }
306
307 //*********************************
308 bucket_t*& get_bucket_list_iterator()
309 {
310 return pbucket;
311 }
312
313 //*********************************
314 local_iterator get_local_iterator()
315 {
316 return inode;
317 }
318
319 bucket_t* pbuckets_end;
320 bucket_t* pbucket;
321 local_iterator inode;
322 };
323
324 //*********************************************************************
325 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const TKey>
326 {
327 public:
328
330 typedef typename iunordered_set::key_type key_type;
331 typedef typename iunordered_set::hasher hasher;
332 typedef typename iunordered_set::key_equal key_equal;
333 typedef typename iunordered_set::reference reference;
335 typedef typename iunordered_set::pointer pointer;
337 typedef typename iunordered_set::size_type size_type;
338
339 friend class iunordered_set;
340 friend class iterator;
341
342 //*********************************
344 {
345 }
346
347 //*********************************
349 : pbuckets_end(other.pbuckets_end)
350 , pbucket(other.pbucket)
351 , inode(other.inode)
352 {
353 }
354
355 //*********************************
357 : pbuckets_end(other.pbuckets_end)
358 , pbucket(other.pbucket)
359 , inode(other.inode)
360 {
361 }
362
363 //*********************************
365 {
366 ++inode;
367
368 // The end of this node list?
369 if (inode == pbucket->end())
370 {
371 // Search for the next non-empty bucket.
372
373 ++pbucket;
374 while ((pbucket != pbuckets_end) && (pbucket->empty()))
375 {
376 ++pbucket;
377 }
378
379 // If not past the end, get the first node in the bucket.
380 if (pbucket != pbuckets_end)
381 {
382 inode = pbucket->begin();
383 }
384 }
385
386 return *this;
387 }
388
389 //*********************************
391 {
392 const_iterator temp(*this);
393 operator++();
394 return temp;
395 }
396
397 //*********************************
399 {
400 pbuckets_end = other.pbuckets_end;
401 pbucket = other.pbucket;
402 inode = other.inode;
403 return *this;
404 }
405
406 //*********************************
408 {
409 return inode->key;
410 }
411
412 //*********************************
414 {
415 return &(inode->key);
416 }
417
418 //*********************************
420 {
421 return &(inode->key);
422 }
423
424 //*********************************
425 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
426 {
427 return lhs.compare(rhs);
428 }
429
430 //*********************************
431 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
432 {
433 return !(lhs == rhs);
434 }
435
436 private:
437
438 //*********************************
440 : pbuckets_end(pbuckets_end_)
441 , pbucket(pbucket_)
442 , inode(inode_)
443 {
444 }
445
446 //*********************************
447 bool compare(const const_iterator& rhs) const
448 {
449 return rhs.inode == inode;
450 }
451
452 //*********************************
453 bucket_t& get_bucket()
454 {
455 return *pbucket;
456 }
457
458 //*********************************
459 bucket_t*& get_bucket_list_iterator()
460 {
461 return pbucket;
462 }
463
464 //*********************************
465 local_iterator get_local_iterator()
466 {
467 return inode;
468 }
469
470 bucket_t* pbuckets_end;
471 bucket_t* pbucket;
472 local_iterator inode;
473 };
474
475 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
476
477 //*********************************************************************
480 //*********************************************************************
482 {
483 return iterator(pbuckets + number_of_buckets, first, first->begin());
484 }
485
486 //*********************************************************************
489 //*********************************************************************
491 {
492 return const_iterator(pbuckets + number_of_buckets, first, first->begin());
493 }
494
495 //*********************************************************************
498 //*********************************************************************
500 {
501 return const_iterator(pbuckets + number_of_buckets, first, first->begin());
502 }
503
504 //*********************************************************************
507 //*********************************************************************
508 local_iterator begin(size_t i)
509 {
510 return pbuckets[i].begin();
511 }
512
513 //*********************************************************************
516 //*********************************************************************
517 const_local_iterator begin(size_t i) const
518 {
519 return pbuckets[i].cbegin();
520 }
521
522 //*********************************************************************
525 //*********************************************************************
526 const_local_iterator cbegin(size_t i) const
527 {
528 return pbuckets[i].cbegin();
529 }
530
531 //*********************************************************************
534 //*********************************************************************
536 {
537 return iterator(pbuckets + number_of_buckets, last, last->end());
538 }
539
540 //*********************************************************************
543 //*********************************************************************
545 {
546 return const_iterator(pbuckets + number_of_buckets, last, last->end());
547 }
548
549 //*********************************************************************
552 //*********************************************************************
554 {
555 return const_iterator(pbuckets + number_of_buckets, last, last->end());
556 }
557
558 //*********************************************************************
561 //*********************************************************************
562 local_iterator end(size_t i)
563 {
564 return pbuckets[i].end();
565 }
566
567 //*********************************************************************
570 //*********************************************************************
571 const_local_iterator end(size_t i) const
572 {
573 return pbuckets[i].cend();
574 }
575
576 //*********************************************************************
579 //*********************************************************************
580 const_local_iterator cend(size_t i) const
581 {
582 return pbuckets[i].cend();
583 }
584
585 //*********************************************************************
588 //*********************************************************************
590 {
591 return key_hash_function(key) % number_of_buckets;
592 }
593
594#if ETL_USING_CPP11
595 //*********************************************************************
598 //*********************************************************************
600 size_type get_bucket_index(const K& key) const
601 {
602 return key_hash_function(key) % number_of_buckets;
603 }
604#endif
605
606 //*********************************************************************
609 //*********************************************************************
611 {
612 size_t index = bucket(key);
613
614 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
615 }
616
617#if ETL_USING_CPP11
618 //*********************************************************************
621 //*********************************************************************
623 size_type bucket_size(const K& key) const
624 {
625 size_t index = bucket(key);
626
627 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
628 }
629#endif
630
631 //*********************************************************************
634 //*********************************************************************
636 {
637 return number_of_buckets;
638 }
639
640 //*********************************************************************
643 //*********************************************************************
645 {
646 return number_of_buckets;
647 }
648
649 //*********************************************************************
655 //*********************************************************************
656 template <typename TIterator>
658 {
659#if ETL_IS_DEBUG_BUILD
660 difference_type d = etl::distance(first_, last_);
661 ETL_ASSERT(d >= 0, ETL_ERROR(unordered_set_iterator));
662 ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_set_full));
663#endif
664
665 clear();
666
667 while (first_ != last_)
668 {
669 insert(*first_);
670 ++first_;
671 }
672 }
673
674 //*********************************************************************
678 //*********************************************************************
679 ETL_OR_STD::pair<iterator, bool> insert(const_reference key)
680 {
681 ETL_OR_STD::pair<iterator, bool> result(end(), false);
682
683 if (full())
684 {
685 iterator iter = find(key);
686 if (iter == end())
687 {
688 ETL_ASSERT_FAIL(ETL_ERROR(unordered_set_full));
689 }
690 else
691 {
692 result.first = iter;
693 result.second = false;
694 return result;
695 }
696 }
697
698 // Get the hash index.
699 size_t index = get_bucket_index(key);
700
701 // Get the bucket & bucket iterator.
702 bucket_t* pbucket = pbuckets + index;
703 bucket_t& bucket = *pbucket;
704
705 // The first one in the bucket?
706 if (bucket.empty())
707 {
708 // Get a new node.
709 node_t* node = allocate_data_node();
710 node->clear();
711 ::new (&node->key) value_type(key);
712 ETL_INCREMENT_DEBUG_COUNT;
713
714 // Just add the pointer to the bucket;
715 bucket.insert_after(bucket.before_begin(), *node);
716 adjust_first_last_markers_after_insert(&bucket);
717
718 result.first = iterator(pbuckets + number_of_buckets, pbucket, pbucket->begin());
719 result.second = true;
720 }
721 else
722 {
723 // Step though the bucket looking for a place to insert.
724 local_iterator inode_previous = bucket.before_begin();
725 local_iterator inode = bucket.begin();
726
727 while (inode != bucket.end())
728 {
729 // Do we already have this key?
730 if (key_equal_function(inode->key, key))
731 {
732 break;
733 }
734
736 ++inode;
737 }
738
739 // Not already there?
740 if (inode == bucket.end())
741 {
742 // Get a new node.
743 node_t* node = allocate_data_node();
744 node->clear();
745 ::new (&node->key) value_type(key);
746 ETL_INCREMENT_DEBUG_COUNT;
747
748 // Add the node to the end of the bucket;
749 bucket.insert_after(inode_previous, *node);
750 adjust_first_last_markers_after_insert(&bucket);
752
753 result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
754 result.second = true;
755 }
756 }
757
758 return result;
759 }
760
761#if ETL_USING_CPP11
762 //*********************************************************************
766 //*********************************************************************
768 ETL_OR_STD::pair<iterator, bool> insert(const K& key)
769 {
770 ETL_OR_STD::pair<iterator, bool> result(end(), false);
771
772 if (full())
773 {
774 iterator iter = find(key);
775 if (iter == end())
776 {
777 ETL_ASSERT_FAIL(ETL_ERROR(unordered_set_full));
778 }
779 else
780 {
781 result.first = iter;
782 result.second = false;
783 return result;
784 }
785 }
786
787 // Get the hash index.
788 size_t index = get_bucket_index(key);
789
790 // Get the bucket & bucket iterator.
791 bucket_t* pbucket = pbuckets + index;
792 bucket_t& bucket = *pbucket;
793
794 // The first one in the bucket?
795 if (bucket.empty())
796 {
797 // Get a new node.
798 node_t* node = allocate_data_node();
799 node->clear();
800 ::new (&node->key) value_type(key);
801 ETL_INCREMENT_DEBUG_COUNT;
802
803 // Just add the pointer to the bucket;
804 bucket.insert_after(bucket.before_begin(), *node);
805 adjust_first_last_markers_after_insert(&bucket);
806
807 result.first = iterator(pbuckets + number_of_buckets, pbucket, pbucket->begin());
808 result.second = true;
809 }
810 else
811 {
812 // Step though the bucket looking for a place to insert.
813 local_iterator inode_previous = bucket.before_begin();
814 local_iterator inode = bucket.begin();
815
816 while (inode != bucket.end())
817 {
818 // Do we already have this key?
819 if (key_equal_function(inode->key, key))
820 {
821 break;
822 }
823
824 ++inode_previous;
825 ++inode;
826 }
827
828 // Not already there?
829 if (inode == bucket.end())
830 {
831 // Get a new node.
832 node_t* node = allocate_data_node();
833 node->clear();
834 ::new (&node->key) value_type(key);
835 ETL_INCREMENT_DEBUG_COUNT;
836
837 // Add the node to the end of the bucket;
838 bucket.insert_after(inode_previous, *node);
839 adjust_first_last_markers_after_insert(&bucket);
840 ++inode_previous;
841
842 result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
843 result.second = true;
844 }
845 }
846
847 return result;
848 }
849#endif
850
851#if ETL_USING_CPP11
852 //*********************************************************************
856 //*********************************************************************
857 ETL_OR_STD::pair<iterator, bool> insert(rvalue_reference key)
858 {
859 ETL_OR_STD::pair<iterator, bool> result(end(), false);
860
861 if (full())
862 {
863 iterator iter = find(key);
864 if (iter == end())
865 {
866 ETL_ASSERT_FAIL(ETL_ERROR(unordered_set_full));
867 }
868 else
869 {
870 result.first = iter;
871 result.second = false;
872 return result;
873 }
874 }
875
876 // Get the hash index.
877 size_t index = get_bucket_index(key);
878
879 // Get the bucket & bucket iterator.
880 bucket_t* pbucket = pbuckets + index;
881 bucket_t& bucket = *pbucket;
882
883 // The first one in the bucket?
884 if (bucket.empty())
885 {
886 // Get a new node.
887 node_t* node = allocate_data_node();
888 node->clear();
889 ::new (&node->key) value_type(etl::move(key));
890 ETL_INCREMENT_DEBUG_COUNT;
891
892 // Just add the pointer to the bucket;
893 bucket.insert_after(bucket.before_begin(), *node);
894 adjust_first_last_markers_after_insert(&bucket);
895
896 result.first = iterator(pbuckets + number_of_buckets, pbucket, pbucket->begin());
897 result.second = true;
898 }
899 else
900 {
901 // Step though the bucket looking for a place to insert.
902 local_iterator inode_previous = bucket.before_begin();
903 local_iterator inode = bucket.begin();
904
905 while (inode != bucket.end())
906 {
907 // Do we already have this key?
908 if (key_equal_function(inode->key, key))
909 {
910 break;
911 }
912
913 ++inode_previous;
914 ++inode;
915 }
916
917 // Not already there?
918 if (inode == bucket.end())
919 {
920 // Get a new node.
921 node_t* node = allocate_data_node();
922 node->clear();
923 ::new (&node->key) value_type(etl::move(key));
924 ETL_INCREMENT_DEBUG_COUNT;
925
926 // Add the node to the end of the bucket;
927 bucket.insert_after(inode_previous, *node);
928 adjust_first_last_markers_after_insert(&bucket);
929 ++inode_previous;
930
931 result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
932 result.second = true;
933 }
934 }
935
936 return result;
937 }
938#endif
939
940 //*********************************************************************
945 //*********************************************************************
947 {
948 return insert(key).first;
949 }
950
951#if ETL_USING_CPP11
952 //*********************************************************************
957 //*********************************************************************
958 iterator insert(const_iterator, rvalue_reference key)
959 {
960 return insert(etl::move(key)).first;
961 }
962#endif
963
964 //*********************************************************************
970 //*********************************************************************
971 template <class TIterator>
973 {
974 while (first_ != last_)
975 {
976 insert(*first_);
977 ++first_;
978 }
979 }
980
981 //*********************************************************************
985 //*********************************************************************
987 {
988 size_t n = 0UL;
989 size_t index = get_bucket_index(key);
990
991 bucket_t& bucket = pbuckets[index];
992
993 local_iterator iprevious = bucket.before_begin();
994 local_iterator icurrent = bucket.begin();
995
996 // Search for the key, if we have it.
997 while ((icurrent != bucket.end()) && (!key_equal_function(icurrent->key, key)))
998 {
999 ++iprevious;
1000 ++icurrent;
1001 }
1002
1003 // Did we find it?
1004 if (icurrent != bucket.end())
1005 {
1006 delete_data_node(iprevious, icurrent, bucket);
1007 n = 1;
1008 }
1009
1010 return n;
1011 }
1012
1013#if ETL_USING_CPP11
1014 //*********************************************************************
1018 //*********************************************************************
1020 size_t erase(const K& key)
1021 {
1022 size_t n = 0UL;
1023 size_t index = get_bucket_index(key);
1024
1025 bucket_t& bucket = pbuckets[index];
1026
1027 local_iterator iprevious = bucket.before_begin();
1028 local_iterator icurrent = bucket.begin();
1029
1030 // Search for the key, if we have it.
1031 while ((icurrent != bucket.end()) && (!key_equal_function(icurrent->key, key)))
1032 {
1033 ++iprevious;
1034 ++icurrent;
1035 }
1036
1037 // Did we find it?
1038 if (icurrent != bucket.end())
1039 {
1040 delete_data_node(iprevious, icurrent, bucket);
1041 n = 1;
1042 }
1043
1044 return n;
1045 }
1046#endif
1047
1048 //*********************************************************************
1051 //*********************************************************************
1053 {
1054 // Make a note of the next one.
1055 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
1056 ++inext;
1057
1058 bucket_t& bucket = ielement.get_bucket();
1059 local_iterator iprevious = bucket.before_begin();
1060 local_iterator icurrent = ielement.get_local_iterator();
1061
1062 // Find the node previous to the one we're interested in.
1063 while (iprevious->etl_next != &*icurrent)
1064 {
1065 ++iprevious;
1066 }
1067
1068 delete_data_node(iprevious, icurrent, bucket);
1069
1070 return inext;
1071 }
1072
1073 //*********************************************************************
1079 //*********************************************************************
1081 {
1082 // Erasing everything?
1083 if ((first_ == begin()) && (last_ == end()))
1084 {
1085 clear();
1086 return end();
1087 }
1088
1089 // Get the starting point.
1090 bucket_t* pbucket = first_.get_bucket_list_iterator();
1091 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
1092 local_iterator iprevious = pbucket->before_begin();
1093 local_iterator icurrent = first_.get_local_iterator();
1094 local_iterator iend = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
1095
1096 // Find the node previous to the first one.
1097 while (iprevious->etl_next != &*icurrent)
1098 {
1099 ++iprevious;
1100 }
1101
1102 // Remember the item before the first erased one.
1103 iterator ibefore_erased = iterator((pbuckets + number_of_buckets), pbucket, iprevious);
1104
1105 // Until we reach the end.
1106 while ((icurrent != iend) || (pbucket != pend_bucket))
1107 {
1108 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
1109
1110 // Have we not reached the end?
1111 if ((icurrent != iend) || (pbucket != pend_bucket))
1112 {
1113 // At the end of this bucket?
1114 if ((icurrent == pbucket->end()))
1115 {
1116 // Find the next non-empty one.
1117 do
1118 {
1119 ++pbucket;
1120 } while (pbucket->empty());
1121
1122 iprevious = pbucket->before_begin();
1123 icurrent = pbucket->begin();
1124 }
1125 }
1126 }
1127
1128 return ++ibefore_erased;
1129 }
1130
1131 //*************************************************************************
1133 //*************************************************************************
1134 void clear()
1135 {
1136 initialise();
1137 }
1138
1139 //*********************************************************************
1143 //*********************************************************************
1144 size_t count(key_parameter_t key) const
1145 {
1146 return (find(key) == end()) ? 0 : 1;
1147 }
1148
1149#if ETL_USING_CPP11
1150 //*********************************************************************
1154 //*********************************************************************
1156 size_t count(const K& key) const
1157 {
1158 return (find(key) == end()) ? 0 : 1;
1159 }
1160#endif
1161
1162 //*********************************************************************
1166 //*********************************************************************
1168 {
1169 size_t index = get_bucket_index(key);
1170
1171 bucket_t* pbucket = pbuckets + index;
1172 bucket_t& bucket = *pbucket;
1173
1174 // Is the bucket not empty?
1175 if (!bucket.empty())
1176 {
1177 // Step though the list until we find the end or an equivalent key.
1178 local_iterator inode = bucket.begin();
1179 local_iterator iend = bucket.end();
1180
1181 while (inode != iend)
1182 {
1183 // Do we have this one?
1184 if (key_equal_function(key, inode->key))
1185 {
1186 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1187 }
1188
1189 ++inode;
1190 }
1191 }
1192
1193 return end();
1194 }
1195
1196 //*********************************************************************
1200 //*********************************************************************
1202 {
1203 size_t index = get_bucket_index(key);
1204
1205 bucket_t* pbucket = pbuckets + index;
1206 bucket_t& bucket = *pbucket;
1207
1208 // Is the bucket not empty?
1209 if (!bucket.empty())
1210 {
1211 // Step though the list until we find the end or an equivalent key.
1212 local_iterator inode = bucket.begin();
1213 local_iterator iend = bucket.end();
1214
1215 while (inode != iend)
1216 {
1217 // Do we have this one?
1218 if (key_equal_function(key, inode->key))
1219 {
1220 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1221 }
1222
1223 ++inode;
1224 }
1225 }
1226
1227 return end();
1228 }
1229
1230#if ETL_USING_CPP11
1231 //*********************************************************************
1235 //*********************************************************************
1237 iterator find(const K& key)
1238 {
1239 size_t index = get_bucket_index(key);
1240
1241 bucket_t* pbucket = pbuckets + index;
1242 bucket_t& bucket = *pbucket;
1243
1244 // Is the bucket not empty?
1245 if (!bucket.empty())
1246 {
1247 // Step though the list until we find the end or an equivalent key.
1248 local_iterator inode = bucket.begin();
1249 local_iterator iend = bucket.end();
1250
1251 while (inode != iend)
1252 {
1253 // Do we have this one?
1254 if (key_equal_function(key, inode->key))
1255 {
1256 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1257 }
1258
1259 ++inode;
1260 }
1261 }
1262
1263 return end();
1264 }
1265#endif
1266
1267#if ETL_USING_CPP11
1268 //*********************************************************************
1272 //*********************************************************************
1273 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value, int> = 0>
1274 const_iterator find(const K& key) const
1275 {
1276 size_t index = get_bucket_index(key);
1277
1278 bucket_t* pbucket = pbuckets + index;
1279 bucket_t& bucket = *pbucket;
1280
1281 // Is the bucket not empty?
1282 if (!bucket.empty())
1283 {
1284 // Step though the list until we find the end or an equivalent key.
1285 local_iterator inode = bucket.begin();
1286 local_iterator iend = bucket.end();
1287
1288 while (inode != iend)
1289 {
1290 // Do we have this one?
1291 if (key_equal_function(key, inode->key))
1292 {
1293 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1294 }
1295
1296 ++inode;
1297 }
1298 }
1299
1300 return end();
1301 }
1302#endif
1303
1304 //*********************************************************************
1311 //*********************************************************************
1312 ETL_OR_STD::pair<iterator, iterator> equal_range(key_parameter_t key)
1313 {
1314 iterator f = find(key);
1315 iterator l = f;
1316
1317 if (l != end())
1318 {
1319 ++l;
1320 }
1321
1322 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1323 }
1324
1325 //*********************************************************************
1332 //*********************************************************************
1333 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
1334 {
1335 const_iterator f = find(key);
1336 const_iterator l = f;
1337
1338 if (l != end())
1339 {
1340 ++l;
1341 }
1342
1343 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1344 }
1345
1346#if ETL_USING_CPP11
1347 //*********************************************************************
1354 //*********************************************************************
1356 ETL_OR_STD::pair<iterator, iterator> equal_range(const K& key)
1357 {
1358 iterator f = find(key);
1359 iterator l = f;
1360
1361 if (l != end())
1362 {
1363 ++l;
1364 }
1365
1366 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1367 }
1368#endif
1369
1370#if ETL_USING_CPP11
1371 //*********************************************************************
1378 //*********************************************************************
1379 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value, int> = 0>
1380 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const K& key) const
1381 {
1382 const_iterator f = find(key);
1383 const_iterator l = f;
1384
1385 if (l != end())
1386 {
1387 ++l;
1388 }
1389
1390 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1391 }
1392#endif
1393
1394 //*************************************************************************
1396 //*************************************************************************
1398 {
1399 return pnodepool->size();
1400 }
1401
1402 //*************************************************************************
1404 //*************************************************************************
1406 {
1407 return pnodepool->max_size();
1408 }
1409
1410 //*************************************************************************
1412 //*************************************************************************
1414 {
1415 return pnodepool->max_size();
1416 }
1417
1418 //*************************************************************************
1420 //*************************************************************************
1421 bool empty() const
1422 {
1423 return pnodepool->empty();
1424 }
1425
1426 //*************************************************************************
1428 //*************************************************************************
1429 bool full() const
1430 {
1431 return pnodepool->full();
1432 }
1433
1434 //*************************************************************************
1437 //*************************************************************************
1438 size_t available() const
1439 {
1440 return pnodepool->available();
1441 }
1442
1443 //*************************************************************************
1446 //*************************************************************************
1447 float load_factor() const
1448 {
1449 return static_cast<float>(size()) / static_cast<float>(bucket_count());
1450 }
1451
1452 //*************************************************************************
1455 //*************************************************************************
1457 {
1458 return key_hash_function;
1459 }
1460
1461 //*************************************************************************
1464 //*************************************************************************
1466 {
1467 return key_equal_function;
1468 }
1469
1470 //*************************************************************************
1472 //*************************************************************************
1474 {
1475 // Skip if doing self assignment
1476 if (this != &rhs)
1477 {
1478 key_hash_function = rhs.hash_function();
1479 key_equal_function = rhs.key_eq();
1480 assign(rhs.cbegin(), rhs.cend());
1481 }
1482
1483 return *this;
1484 }
1485
1486#if ETL_USING_CPP11
1487 //*************************************************************************
1489 //*************************************************************************
1491 {
1492 // Skip if doing self assignment
1493 if (this != &rhs)
1494 {
1495 clear();
1496 key_hash_function = rhs.hash_function();
1497 key_equal_function = rhs.key_eq();
1498 move(rhs.begin(), rhs.end());
1499 }
1500
1501 return *this;
1502 }
1503#endif
1504
1505 //*************************************************************************
1507 //*************************************************************************
1509 {
1510 return find(key) != end();
1511 }
1512
1513#if ETL_USING_CPP11
1514 //*************************************************************************
1516 //*************************************************************************
1518 bool contains(const K& key) const
1519 {
1520 return find(key) != end();
1521 }
1522#endif
1523
1524 protected:
1525
1526 //*********************************************************************
1528 //*********************************************************************
1530 : pnodepool(&node_pool_)
1531 , pbuckets(pbuckets_)
1532 , number_of_buckets(number_of_buckets_)
1533 , first(pbuckets)
1534 , last(pbuckets)
1535 , key_hash_function(key_hash_function_)
1536 , key_equal_function(key_equal_function_)
1537 {
1538 }
1539
1540 //*********************************************************************
1542 //*********************************************************************
1544 {
1545 if (!empty())
1546 {
1547 // For each bucket...
1548 for (size_t i = 0UL; i < number_of_buckets; ++i)
1549 {
1550 bucket_t& bucket = pbuckets[i];
1551
1552 if (!bucket.empty())
1553 {
1554 // For each item in the bucket...
1555 local_iterator it = bucket.begin();
1556
1557 while (it != bucket.end())
1558 {
1559 // Destroy the value contents.
1560 it->key.~value_type();
1561 ++it;
1562 ETL_DECREMENT_DEBUG_COUNT;
1563 }
1564
1565 // Now it's safe to clear the bucket.
1566 bucket.clear();
1567 }
1568 }
1569
1570 // Now it's safe to clear the entire pool in one go.
1571 pnodepool->release_all();
1572 }
1573
1574 first = pbuckets;
1575 last = first;
1576 }
1577
1578#if ETL_USING_CPP11
1579 //*************************************************************************
1581 //*************************************************************************
1582 void move(iterator b, iterator e)
1583 {
1584#if ETL_IS_DEBUG_BUILD
1585 difference_type d = etl::distance(b, e);
1586 ETL_ASSERT(d >= 0, ETL_ERROR(unordered_set_iterator));
1587 ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_set_full));
1588#endif
1589
1590 while (b != e)
1591 {
1592 iterator temp = b;
1593 ++temp;
1594 insert(etl::move(*b));
1595 b = temp;
1596 }
1597 }
1598#endif
1599
1600 private:
1601
1602 //*************************************************************************
1604 //*************************************************************************
1605 node_t* allocate_data_node()
1606 {
1607 node_t* (etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1608 return (pnodepool->*func)();
1609 }
1610
1611 //*********************************************************************
1613 //*********************************************************************
1614 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1615 {
1616 if (size() == 1)
1617 {
1618 first = pbucket;
1619 last = pbucket;
1620 }
1621 else
1622 {
1623 if (pbucket < first)
1624 {
1625 first = pbucket;
1626 }
1627 else if (pbucket > last)
1628 {
1629 last = pbucket;
1630 }
1631 }
1632 }
1633
1634 //*********************************************************************
1636 //*********************************************************************
1637 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1638 {
1639 if (empty())
1640 {
1641 first = pbuckets;
1642 last = pbuckets;
1643 }
1644 else
1645 {
1646 if (pbucket == first)
1647 {
1648 // We erased the first so, we need to search again from where we erased.
1649 while (first->empty())
1650 {
1651 ++first;
1652 }
1653 }
1654 else if (pbucket == last)
1655 {
1656 // We erased the last, so we need to search again. Start from the first, go no further than the current last.
1657 pbucket = first;
1658 bucket_t* pend = last;
1659
1660 last = first;
1661
1662 while (pbucket != pend)
1663 {
1664 if (!pbucket->empty())
1665 {
1666 last = pbucket;
1667 }
1668
1669 ++pbucket;
1670 }
1671 }
1672 }
1673 }
1674
1675 //*********************************************************************
1677 //*********************************************************************
1678 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1679 {
1680 local_iterator inext = bucket.erase_after(iprevious); // Unlink from the bucket.
1681 icurrent->key.~value_type(); // Destroy the value.
1682 pnodepool->release(&*icurrent); // Release it back to the pool.
1683 adjust_first_last_markers_after_erase(&bucket);
1684 ETL_DECREMENT_DEBUG_COUNT;
1685
1686 return inext;
1687 }
1688
1689 // Disable copy construction.
1690 iunordered_set(const iunordered_set&);
1691
1693 pool_t* pnodepool;
1694
1696 bucket_t* pbuckets;
1697
1699 const size_t number_of_buckets;
1700
1702 bucket_t* first;
1703 bucket_t* last;
1704
1706 hasher key_hash_function;
1707
1709 key_equal key_equal_function;
1710
1712 ETL_DECLARE_DEBUG_COUNT;
1713
1714 //*************************************************************************
1716 //*************************************************************************
1717#if defined(ETL_POLYMORPHIC_UNORDERED_SET) || defined(ETL_POLYMORPHIC_CONTAINERS)
1718 public:
1719 virtual ~iunordered_set()
1720 {
1721 }
1722#else
1723 protected:
1725 {
1726 }
1727#endif
1728 };
1729
1730 //***************************************************************************
1736 //***************************************************************************
1737 template <typename TKey, typename THash, typename TKeyEqual>
1740 {
1741 const bool sizes_match = (lhs.size() == rhs.size());
1742 bool elements_match = true;
1743
1745
1746 if (sizes_match)
1747 {
1748 itr_t l_begin = lhs.begin();
1749 itr_t l_end = lhs.end();
1750
1751 while ((l_begin != l_end) && elements_match)
1752 {
1753 const TKey l_value = *l_begin;
1754
1755 // See if the lhs key exists in the rhs.
1756 ETL_OR_STD::pair<itr_t, itr_t> range = rhs.equal_range(l_value);
1757
1758 if (range.first != rhs.end())
1759 {
1760 // See if the values match
1761 const TKey r_value = *(range.first);
1762
1764 }
1765 else
1766 {
1767 elements_match = false;
1768 }
1769
1770 ++l_begin;
1771 }
1772 }
1773
1774 return (sizes_match && elements_match);
1775 }
1776
1777 //***************************************************************************
1783 //***************************************************************************
1784 template <typename TKey, typename THash, typename TKeyEqual>
1790
1791 //*************************************************************************
1793 //*************************************************************************
1794 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> >
1795 class unordered_set : public etl::iunordered_set<TKey, THash, TKeyEqual>
1796 {
1797 private:
1798
1800
1801 public:
1802
1803 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1804 static ETL_CONSTANT size_t MAX_BUCKETS = MAX_BUCKETS_;
1805
1806 //*************************************************************************
1808 //*************************************************************************
1809 unordered_set(const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1810 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1811 {
1812 }
1813
1814 //*************************************************************************
1816 //*************************************************************************
1818 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1819 {
1820 // Skip if doing self assignment
1821 if (this != &other)
1822 {
1823 base::assign(other.cbegin(), other.cend());
1824 }
1825 }
1826
1827#if ETL_USING_CPP11
1828 //*************************************************************************
1830 //*************************************************************************
1832 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1833 {
1834 // Skip if doing self assignment
1835 if (this != &other)
1836 {
1837 base::move(other.begin(), other.end());
1838 }
1839 }
1840#endif
1841
1842 //*************************************************************************
1847 //*************************************************************************
1848 template <typename TIterator>
1850 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1851 {
1852 base::assign(first_, last_);
1853 }
1854
1855#if ETL_HAS_INITIALIZER_LIST
1856 //*************************************************************************
1858 //*************************************************************************
1859 unordered_set(std::initializer_list<TKey> init, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1860 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1861 {
1862 base::assign(init.begin(), init.end());
1863 }
1864#endif
1865
1866 //*************************************************************************
1868 //*************************************************************************
1870 {
1871 base::initialise();
1872 }
1873
1874 //*************************************************************************
1876 //*************************************************************************
1878 {
1879 base::operator=(rhs);
1880
1881 return *this;
1882 }
1883
1884#if ETL_USING_CPP11
1885 //*************************************************************************
1887 //*************************************************************************
1889 {
1890 base::operator=(etl::move(rhs));
1891
1892 return *this;
1893 }
1894#endif
1895
1896 private:
1897
1900
1902 typename base::bucket_t buckets[MAX_BUCKETS_];
1903 };
1904
1905 //*************************************************************************
1907 //*************************************************************************
1908#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1909 template <typename... T>
1910 unordered_set(T...) -> unordered_set<etl::nth_type_t<0, T...>, sizeof...(T)>;
1911#endif
1912
1913 //*************************************************************************
1915 //*************************************************************************
1916#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1917 template <typename TKey, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey>, typename... T>
1918 constexpr auto make_unordered_set(T&&... keys) -> etl::unordered_set<TKey, sizeof...(T), sizeof...(T), THash, TKeyEqual>
1919 {
1920 return { etl::forward<T>(keys)... };
1921 }
1922#endif
1923}
1924
1925#endif
Definition unordered_set.h:326
Definition unordered_set.h:184
A templated unordered_set implementation that uses a fixed size buffer.
Definition unordered_set.h:1796
unordered_set(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_set.h:1849
~unordered_set()
Destructor.
Definition unordered_set.h:1869
unordered_set(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_set.h:1809
unordered_set(const unordered_set &other)
Copy constructor.
Definition unordered_set.h:1817
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:968
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
size_t size() const
Returns the number of allocated items in the pool.
Definition ipool.h:301
bool empty() const
Definition ipool.h:310
void release_all()
Release all objects in the pool.
Definition ipool.h:248
bool full() const
Definition ipool.h:319
size_t max_size() const
Returns the maximum number of items in the pool.
Definition ipool.h:269
void release(const void *const p_object)
Definition ipool.h:239
size_t available() const
Returns the number of free items in the pool.
Definition ipool.h:293
Definition ipool.h:102
size_t count(key_parameter_t key) const
Definition unordered_set.h:1144
const_local_iterator begin(size_t i) const
Definition unordered_set.h:517
key_equal key_eq() const
Definition unordered_set.h:1465
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_set.h:1080
local_iterator end(size_t i)
Definition unordered_set.h:562
size_type bucket_count() const
Definition unordered_set.h:644
size_type max_size() const
Gets the maximum possible size of the unordered_set.
Definition unordered_set.h:1405
size_type size() const
Gets the size of the unordered_set.
Definition unordered_set.h:1397
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:1529
iunordered_set & operator=(const iunordered_set &rhs)
Assignment operator.
Definition unordered_set.h:1473
local_iterator begin(size_t i)
Definition unordered_set.h:508
void insert(TIterator first_, TIterator last_)
Definition unordered_set.h:972
float load_factor() const
Definition unordered_set.h:1447
const_iterator begin() const
Definition unordered_set.h:490
bool contains(key_parameter_t key) const
Check if the unordered_set contains the key.
Definition unordered_set.h:1508
const_local_iterator cbegin(size_t i) const
Definition unordered_set.h:526
bool full() const
Checks to see if the unordered_set is full.
Definition unordered_set.h:1429
size_type bucket_size(key_parameter_t key) const
Definition unordered_set.h:610
~iunordered_set()
Destructor.
Definition unordered_set.h:1724
size_type get_bucket_index(key_parameter_t key) const
Definition unordered_set.h:589
const_iterator end() const
Definition unordered_set.h:544
void clear()
Clears the unordered_set.
Definition unordered_set.h:1134
size_t available() const
Definition unordered_set.h:1438
ETL_OR_STD::pair< iterator, bool > insert(const_reference key)
Definition unordered_set.h:679
iterator insert(const_iterator, const_reference key)
Definition unordered_set.h:946
void assign(TIterator first_, TIterator last_)
Definition unordered_set.h:657
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(key_parameter_t key) const
Definition unordered_set.h:1333
iterator find(key_parameter_t key)
Definition unordered_set.h:1167
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition unordered_set.h:1312
iterator end()
Definition unordered_set.h:535
size_t erase(key_parameter_t key)
Definition unordered_set.h:986
const_iterator find(key_parameter_t key) const
Definition unordered_set.h:1201
hasher hash_function() const
Definition unordered_set.h:1456
bool empty() const
Checks to see if the unordered_set is empty.
Definition unordered_set.h:1421
size_type max_bucket_count() const
Definition unordered_set.h:635
iterator begin()
Definition unordered_set.h:481
const_local_iterator cend(size_t i) const
Definition unordered_set.h:580
const_iterator cend() const
Definition unordered_set.h:553
const_local_iterator end(size_t i) const
Definition unordered_set.h:571
void initialise()
Initialise the unordered_set.
Definition unordered_set.h:1543
size_type capacity() const
Gets the maximum possible size of the unordered_set.
Definition unordered_set.h:1413
const_iterator cbegin() const
Definition unordered_set.h:499
iterator erase(const_iterator ielement)
Definition unordered_set.h:1052
Definition unordered_set.h:129
Definition unordered_set.h:72
Definition unordered_set.h:86
Definition unordered_set.h:113
Definition unordered_set.h:100
bitset_ext
Definition absolute.h:38
Definition compare.h:51
iterator
Definition iterator.h:399
Definition unordered_set.h:152
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