Embedded Template Library 1.0
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 //***************************************************************************
70 {
71 public:
72
73 unordered_set_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
74 : etl::exception(reason_, file_name_, line_number_)
75 {
76 }
77 };
78
79 //***************************************************************************
82 //***************************************************************************
84 {
85 public:
86
87 unordered_set_full(string_type file_name_, numeric_type line_number_)
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
101 unordered_set_out_of_range(string_type file_name_, numeric_type line_number_)
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
114 unordered_set_iterator(string_type file_name_, numeric_type line_number_)
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
137 typedef value_type&& rvalue_reference;
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 {
151 node_t(const_reference key_)
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
185 typedef typename etl::iterator<ETL_OR_STD::forward_iterator_tag, TKey>::value_type value_type;
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;
190 typedef typename iunordered_set::const_reference const_reference;
191 typedef typename iunordered_set::pointer pointer;
192 typedef typename iunordered_set::const_pointer const_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 //*********************************
212 iterator& operator ++()
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 //*********************************
237 iterator operator ++(int)
238 {
239 iterator temp(*this);
240 operator++();
241 return temp;
242 }
243
244 //*********************************
245 iterator& operator =(const iterator& other)
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 //*********************************
286 iterator(bucket_t* pbuckets_end_, bucket_t* pbucket_, local_iterator inode_)
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
327 typedef typename etl::iterator<ETL_OR_STD::forward_iterator_tag, const TKey>::value_type value_type;
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;
332 typedef typename iunordered_set::const_reference const_reference;
333 typedef typename iunordered_set::pointer pointer;
334 typedef typename iunordered_set::const_pointer const_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 //*********************************
346 const_iterator(const typename iunordered_set::iterator& other)
347 : pbuckets_end(other.pbuckets_end)
348 , pbucket(other.pbucket)
349 , inode(other.inode)
350 {
351 }
352
353 //*********************************
354 const_iterator(const const_iterator& other)
355 : pbuckets_end(other.pbuckets_end)
356 , pbucket(other.pbucket)
357 , inode(other.inode)
358 {
359 }
360
361 //*********************************
362 const_iterator& operator ++()
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 //*********************************
388 const_iterator operator ++(int)
389 {
390 const_iterator temp(*this);
391 operator++();
392 return temp;
393 }
394
395 //*********************************
396 const_iterator& operator =(const const_iterator& other)
397 {
398 pbuckets_end = other.pbuckets_end;
399 pbucket = other.pbucket;
400 inode = other.inode;
401 return *this;
402 }
403
404 //*********************************
405 const_reference operator *() const
406 {
407 return inode->key;
408 }
409
410 //*********************************
411 const_pointer operator &() const
412 {
413 return &(inode->key);
414 }
415
416 //*********************************
417 const_pointer operator ->() const
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 //*********************************
437 const_iterator(bucket_t* pbuckets_end_, bucket_t* pbucket_, local_iterator inode_)
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 //*********************************************************************
507 {
508 return pbuckets[i].begin();
509 }
510
511 //*********************************************************************
514 //*********************************************************************
516 {
517 return pbuckets[i].cbegin();
518 }
519
520 //*********************************************************************
523 //*********************************************************************
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 //*********************************************************************
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 //*********************************************************************
579 {
580 return pbuckets[i].cend();
581 }
582
583 //*********************************************************************
586 //*********************************************************************
587 size_type get_bucket_index(key_parameter_t key) const
588 {
589 return key_hash_function(key) % number_of_buckets;
590 }
591
592 //*********************************************************************
595 //*********************************************************************
596 size_type bucket_size(key_parameter_t key) const
597 {
598 size_t index = bucket(key);
599
600 return etl::distance(pbuckets[index].begin(), pbuckets[index].end());
601 }
602
603 //*********************************************************************
606 //*********************************************************************
607 size_type max_bucket_count() const
608 {
609 return number_of_buckets;
610 }
611
612 //*********************************************************************
615 //*********************************************************************
616 size_type bucket_count() const
617 {
618 return number_of_buckets;
619 }
620
621 //*********************************************************************
627 //*********************************************************************
628 template <typename TIterator>
629 void assign(TIterator first_, TIterator last_)
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 ETL_ASSERT(!full(), ETL_ERROR(unordered_set_full));
656
657 // Get the hash index.
658 size_t index = get_bucket_index(key);
659
660 // Get the bucket & bucket iterator.
661 bucket_t* pbucket = pbuckets + index;
662 bucket_t& bucket = *pbucket;
663
664 // The first one in the bucket?
665 if (bucket.empty())
666 {
667 // Get a new node.
668 node_t& node = allocate_data_node();
669 node.clear();
670 ::new (&node.key) value_type(key);
671 ETL_INCREMENT_DEBUG_COUNT
672
673 // Just add the pointer to the bucket;
674 bucket.insert_after(bucket.before_begin(), node);
675 adjust_first_last_markers_after_insert(&bucket);
676
677 result.first = iterator(pbuckets + number_of_buckets, pbucket, pbucket->begin());
678 result.second = true;
679 }
680 else
681 {
682 // Step though the bucket looking for a place to insert.
683 local_iterator inode_previous = bucket.before_begin();
684 local_iterator inode = bucket.begin();
685
686 while (inode != bucket.end())
687 {
688 // Do we already have this key?
689 if (key_equal_function(inode->key, key))
690 {
691 break;
692 }
693
694 ++inode_previous;
695 ++inode;
696 }
697
698 // Not already there?
699 if (inode == bucket.end())
700 {
701 // Get a new node.
702 node_t& node = allocate_data_node();
703 node.clear();
704 ::new (&node.key) value_type(key);
705 ETL_INCREMENT_DEBUG_COUNT
706
707 // Add the node to the end of the bucket;
708 bucket.insert_after(inode_previous, node);
709 adjust_first_last_markers_after_insert(&bucket);
710 ++inode_previous;
711
712 result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
713 result.second = true;
714 }
715 }
716
717 return result;
718 }
719
720#if ETL_USING_CPP11
721 //*********************************************************************
725 //*********************************************************************
726 ETL_OR_STD::pair<iterator, bool> insert(rvalue_reference key)
727 {
728 ETL_OR_STD::pair<iterator, bool> result(end(), false);
729
730 ETL_ASSERT(!full(), ETL_ERROR(unordered_set_full));
731
732 // Get the hash index.
733 size_t index = get_bucket_index(key);
734
735 // Get the bucket & bucket iterator.
736 bucket_t* pbucket = pbuckets + index;
737 bucket_t& bucket = *pbucket;
738
739 // The first one in the bucket?
740 if (bucket.empty())
741 {
742 // Get a new node.
743 node_t& node = allocate_data_node();
744 node.clear();
745 ::new (&node.key) value_type(etl::move(key));
746 ETL_INCREMENT_DEBUG_COUNT
747
748 // Just add the pointer to the bucket;
749 bucket.insert_after(bucket.before_begin(), node);
750 adjust_first_last_markers_after_insert(&bucket);
751
752 result.first = iterator(pbuckets + number_of_buckets, pbucket, pbucket->begin());
753 result.second = true;
754 }
755 else
756 {
757 // Step though the bucket looking for a place to insert.
758 local_iterator inode_previous = bucket.before_begin();
759 local_iterator inode = bucket.begin();
760
761 while (inode != bucket.end())
762 {
763 // Do we already have this key?
764 if (key_equal_function(inode->key, key))
765 {
766 break;
767 }
768
769 ++inode_previous;
770 ++inode;
771 }
772
773 // Not already there?
774 if (inode == bucket.end())
775 {
776 // Get a new node.
777 node_t& node = allocate_data_node();
778 node.clear();
779 ::new (&node.key) value_type(etl::move(key));
780 ETL_INCREMENT_DEBUG_COUNT
781
782 // Add the node to the end of the bucket;
783 bucket.insert_after(inode_previous, node);
784 adjust_first_last_markers_after_insert(&bucket);
785 ++inode_previous;
786
787 result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
788 result.second = true;
789 }
790 }
791
792 return result;
793 }
794#endif
795
796 //*********************************************************************
801 //*********************************************************************
802 iterator insert(const_iterator, const_reference key)
803 {
804 return insert(key).first;
805 }
806
807#if ETL_USING_CPP11
808 //*********************************************************************
813 //*********************************************************************
814 iterator insert(const_iterator, rvalue_reference key)
815 {
816 return insert(etl::move(key)).first;
817 }
818#endif
819
820 //*********************************************************************
826 //*********************************************************************
827 template <class TIterator>
828 void insert(TIterator first_, TIterator last_)
829 {
830 while (first_ != last_)
831 {
832 insert(*first_);
833 ++first_;
834 }
835 }
836
837 //*********************************************************************
841 //*********************************************************************
842 size_t erase(key_parameter_t key)
843 {
844 size_t n = 0UL;
845 size_t index = get_bucket_index(key);
846
847 bucket_t& bucket = pbuckets[index];
848
849 local_iterator iprevious = bucket.before_begin();
850 local_iterator icurrent = bucket.begin();
851
852 // Search for the key, if we have it.
853 while ((icurrent != bucket.end()) && (!key_equal_function(icurrent->key, key)))
854 {
855 ++iprevious;
856 ++icurrent;
857 }
858
859 // Did we find it?
860 if (icurrent != bucket.end())
861 {
862 delete_data_node(iprevious, icurrent, bucket);
863 n = 1;
864 }
865
866 return n;
867 }
868
869 //*********************************************************************
872 //*********************************************************************
874 {
875 // Make a note of the next one.
876 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
877 ++inext;
878
879 bucket_t& bucket = ielement.get_bucket();
880 local_iterator iprevious = bucket.before_begin();
881 local_iterator icurrent = ielement.get_local_iterator();
882
883 // Find the node previous to the one we're interested in.
884 while (iprevious->etl_next != &*icurrent)
885 {
886 ++iprevious;
887 }
888
889 delete_data_node(iprevious, icurrent, bucket);
890
891 return inext;
892 }
893
894 //*********************************************************************
900 //*********************************************************************
902 {
903 // Erasing everything?
904 if ((first_ == begin()) && (last_ == end()))
905 {
906 clear();
907 return end();
908 }
909
910 // Get the starting point.
911 bucket_t* pbucket = first_.get_bucket_list_iterator();
912 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
913 local_iterator iprevious = pbucket->before_begin();
914 local_iterator icurrent = first_.get_local_iterator();
915 local_iterator iend = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
916
917 // Find the node previous to the first one.
918 while (iprevious->etl_next != &*icurrent)
919 {
920 ++iprevious;
921 }
922
923 // Remember the item before the first erased one.
924 iterator ibefore_erased = iterator((pbuckets + number_of_buckets), pbucket, iprevious);
925
926 // Until we reach the end.
927 while ((icurrent != iend) || (pbucket != pend_bucket))
928 {
929 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
930
931 // Have we not reached the end?
932 if ((icurrent != iend) || (pbucket != pend_bucket))
933 {
934 // At the end of this bucket?
935 if ((icurrent == pbucket->end()))
936 {
937 // Find the next non-empty one.
938 do
939 {
940 ++pbucket;
941 } while (pbucket->empty());
942
943 iprevious = pbucket->before_begin();
944 icurrent = pbucket->begin();
945 }
946 }
947 }
948
949 return ++ibefore_erased;
950 }
951
952 //*************************************************************************
954 //*************************************************************************
955 void clear()
956 {
957 initialise();
958 }
959
960 //*********************************************************************
964 //*********************************************************************
965 size_t count(key_parameter_t key) const
966 {
967 return (find(key) == end()) ? 0 : 1;
968 }
969
970 //*********************************************************************
974 //*********************************************************************
975 iterator find(key_parameter_t key)
976 {
977 size_t index = get_bucket_index(key);
978
979 bucket_t* pbucket = pbuckets + index;
980 bucket_t& bucket = *pbucket;
981
982 // Is the bucket not empty?
983 if (!bucket.empty())
984 {
985 // Step though the list until we find the end or an equivalent key.
986 local_iterator inode = bucket.begin();
987 local_iterator iend = bucket.end();
988
989 while (inode != iend)
990 {
991 // Do we have this one?
992 if (key_equal_function(key, inode->key))
993 {
994 return iterator(pbuckets + number_of_buckets, pbucket, inode);
995 }
996
997 ++inode;
998 }
999 }
1000
1001 return end();
1002 }
1003
1004 //*********************************************************************
1008 //*********************************************************************
1009 const_iterator find(key_parameter_t key) const
1010 {
1011 size_t index = get_bucket_index(key);
1012
1013 bucket_t* pbucket = pbuckets + index;
1014 bucket_t& bucket = *pbucket;
1015
1016 // Is the bucket not empty?
1017 if (!bucket.empty())
1018 {
1019 // Step though the list until we find the end or an equivalent key.
1020 local_iterator inode = bucket.begin();
1021 local_iterator iend = bucket.end();
1022
1023 while (inode != iend)
1024 {
1025 // Do we have this one?
1026 if (key_equal_function(key, inode->key))
1027 {
1028 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1029 }
1030
1031 ++inode;
1032 }
1033 }
1034
1035 return end();
1036 }
1037
1038 //*********************************************************************
1045 //*********************************************************************
1046 ETL_OR_STD::pair<iterator, iterator> equal_range(key_parameter_t key)
1047 {
1048 iterator f = find(key);
1049 iterator l = f;
1050
1051 if (l != end())
1052 {
1053 ++l;
1054 }
1055
1056 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1057 }
1058
1059 //*********************************************************************
1066 //*********************************************************************
1067 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
1068 {
1069 const_iterator f = find(key);
1070 const_iterator l = f;
1071
1072 if (l != end())
1073 {
1074 ++l;
1075 }
1076
1077 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1078 }
1079
1080 //*************************************************************************
1082 //*************************************************************************
1083 size_type size() const
1084 {
1085 return pnodepool->size();
1086 }
1087
1088 //*************************************************************************
1090 //*************************************************************************
1091 size_type max_size() const
1092 {
1093 return pnodepool->max_size();
1094 }
1095
1096 //*************************************************************************
1098 //*************************************************************************
1099 size_type capacity() const
1100 {
1101 return pnodepool->max_size();
1102 }
1103
1104 //*************************************************************************
1106 //*************************************************************************
1107 bool empty() const
1108 {
1109 return pnodepool->empty();
1110 }
1111
1112 //*************************************************************************
1114 //*************************************************************************
1115 bool full() const
1116 {
1117 return pnodepool->full();
1118 }
1119
1120 //*************************************************************************
1123 //*************************************************************************
1124 size_t available() const
1125 {
1126 return pnodepool->available();
1127 }
1128
1129 //*************************************************************************
1132 //*************************************************************************
1133 float load_factor() const
1134 {
1135 return static_cast<float>(size()) / static_cast<float>(bucket_count());
1136 }
1137
1138 //*************************************************************************
1141 //*************************************************************************
1142 hasher hash_function() const
1143 {
1144 return key_hash_function;
1145 }
1146
1147 //*************************************************************************
1150 //*************************************************************************
1151 key_equal key_eq() const
1152 {
1153 return key_equal_function;
1154 }
1155
1156 //*************************************************************************
1158 //*************************************************************************
1160 {
1161 // Skip if doing self assignment
1162 if (this != &rhs)
1163 {
1164 key_hash_function = rhs.hash_function();
1165 key_equal_function = rhs.key_eq();
1166 assign(rhs.cbegin(), rhs.cend());
1167 }
1168
1169 return *this;
1170 }
1171
1172#if ETL_USING_CPP11
1173 //*************************************************************************
1175 //*************************************************************************
1177 {
1178 // Skip if doing self assignment
1179 if (this != &rhs)
1180 {
1181 clear();
1182 key_hash_function = rhs.hash_function();
1183 key_equal_function = rhs.key_eq();
1184 move(rhs.begin(), rhs.end());
1185 }
1186
1187 return *this;
1188 }
1189#endif
1190
1191 protected:
1192
1193 //*********************************************************************
1195 //*********************************************************************
1196 iunordered_set(pool_t& node_pool_, bucket_t* pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
1197 : pnodepool(&node_pool_)
1198 , pbuckets(pbuckets_)
1199 , number_of_buckets(number_of_buckets_)
1200 , first(pbuckets)
1201 , last(pbuckets)
1202 , key_hash_function(key_hash_function_)
1203 , key_equal_function(key_equal_function_)
1204 {
1205 }
1206
1207 //*********************************************************************
1209 //*********************************************************************
1211 {
1212 if (!empty())
1213 {
1214 // For each bucket...
1215 for (size_t i = 0UL; i < number_of_buckets; ++i)
1216 {
1217 bucket_t& bucket = pbuckets[i];
1218
1219 if (!bucket.empty())
1220 {
1221 // For each item in the bucket...
1222 local_iterator it = bucket.begin();
1223
1224 while (it != bucket.end())
1225 {
1226 // Destroy the value contents.
1227 it->key.~value_type();
1228 ++it;
1229 ETL_DECREMENT_DEBUG_COUNT
1230 }
1231
1232 // Now it's safe to clear the bucket.
1233 bucket.clear();
1234 }
1235 }
1236
1237 // Now it's safe to clear the entire pool in one go.
1238 pnodepool->release_all();
1239 }
1240
1241 first = pbuckets;
1242 last = first;
1243 }
1244
1245#if ETL_USING_CPP11
1246 //*************************************************************************
1248 //*************************************************************************
1249 void move(iterator first, iterator last)
1250 {
1251#if ETL_IS_DEBUG_BUILD
1252 difference_type d = etl::distance(first, last);
1253 ETL_ASSERT(d >= 0, ETL_ERROR(unordered_set_iterator));
1254 ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_set_full));
1255#endif
1256
1257 while (first != last)
1258 {
1259 iterator temp = first;
1260 ++temp;
1261 insert(etl::move(*first));
1262 first = temp;
1263 }
1264 }
1265#endif
1266
1267 private:
1268
1269 //*************************************************************************
1271 //*************************************************************************
1272 node_t& allocate_data_node()
1273 {
1274 node_t* (etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1275 return *(pnodepool->*func)();
1276 }
1277
1278 //*********************************************************************
1280 //*********************************************************************
1281 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1282 {
1283 if (size() == 1)
1284 {
1285 first = pbucket;
1286 last = pbucket;
1287 }
1288 else
1289 {
1290 if (pbucket < first)
1291 {
1292 first = pbucket;
1293 }
1294 else if (pbucket > last)
1295 {
1296 last = pbucket;
1297 }
1298 }
1299 }
1300
1301 //*********************************************************************
1303 //*********************************************************************
1304 void adjust_first_last_markers_after_erase(bucket_t* pcurrent)
1305 {
1306 if (empty())
1307 {
1308 first = pbuckets;
1309 last = pbuckets;
1310 }
1311 else
1312 {
1313 if (pcurrent == first)
1314 {
1315 // We erased the first so, we need to search again from where we erased.
1316 while (first->empty())
1317 {
1318 ++first;
1319 }
1320 }
1321 else if (pcurrent == last)
1322 {
1323 // We erased the last, so we need to search again. Start from the first, go no further than the current last.
1324 bucket_t* pcurrent = first;
1325 bucket_t* pend = last;
1326
1327 last = first;
1328
1329 while (pcurrent != pend)
1330 {
1331 if (!pcurrent->empty())
1332 {
1333 last = pcurrent;
1334 }
1335
1336 ++pcurrent;
1337 }
1338 }
1339 }
1340 }
1341
1342 //*********************************************************************
1344 //*********************************************************************
1345 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1346 {
1347 local_iterator inext = bucket.erase_after(iprevious); // Unlink from the bucket.
1348 icurrent->key.~value_type(); // Destroy the value.
1349 pnodepool->release(&*icurrent); // Release it back to the pool.
1350 adjust_first_last_markers_after_erase(&bucket);
1351 ETL_DECREMENT_DEBUG_COUNT
1352
1353 return inext;
1354 }
1355
1356 // Disable copy construction.
1358
1360 pool_t* pnodepool;
1361
1363 bucket_t* pbuckets;
1364
1366 const size_t number_of_buckets;
1367
1369 bucket_t* first;
1370 bucket_t* last;
1371
1373 hasher key_hash_function;
1374
1376 key_equal key_equal_function;
1377
1379 ETL_DECLARE_DEBUG_COUNT
1380
1381 //*************************************************************************
1383 //*************************************************************************
1384#if defined(ETL_POLYMORPHIC_UNORDERED_SET) || defined(ETL_POLYMORPHIC_CONTAINERS)
1385 public:
1386 virtual ~iunordered_set()
1387 {
1388 }
1389#else
1390 protected:
1392 {
1393 }
1394#endif
1395 };
1396
1397 //***************************************************************************
1403 //***************************************************************************
1404 template <typename TKey, typename TMapped, typename TKeyCompare>
1406 {
1407 const bool sizes_match = (lhs.size() == rhs.size());
1408 bool elements_match = true;
1409
1410 if (sizes_match)
1411 {
1412 for (size_t i = 0; (i < lhs.bucket_count()) && elements_match; ++i)
1413 {
1414 if (!etl::is_permutation(lhs.begin(i), lhs.end(i), rhs.begin(i)))
1415 {
1416 elements_match = false;
1417 }
1418 }
1419 }
1420
1421 return (sizes_match && elements_match);
1422 }
1423
1424 //***************************************************************************
1430 //***************************************************************************
1431 template <typename TKey, typename TMapped, typename TKeyCompare>
1433 {
1434 return !(lhs == rhs);
1435 }
1436
1437 //*************************************************************************
1439 //*************************************************************************
1440 template <typename TKey, const size_t MAX_SIZE_, size_t MAX_BUCKETS_ = MAX_SIZE_, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey> >
1441 class unordered_set : public etl::iunordered_set<TKey, THash, TKeyEqual>
1442 {
1443 private:
1444
1446
1447 public:
1448
1449 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1450 static ETL_CONSTANT size_t MAX_BUCKETS = MAX_BUCKETS_;
1451
1452 //*************************************************************************
1454 //*************************************************************************
1455 unordered_set(const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1456 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1457 {
1458 }
1459
1460 //*************************************************************************
1462 //*************************************************************************
1464 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1465 {
1466 // Skip if doing self assignment
1467 if (this != &other)
1468 {
1469 base::assign(other.cbegin(), other.cend());
1470 }
1471 }
1472
1473#if ETL_USING_CPP11
1474 //*************************************************************************
1476 //*************************************************************************
1478 : base(node_pool, buckets, MAX_BUCKETS, other.hash_function(), other.key_eq())
1479 {
1480 // Skip if doing self assignment
1481 if (this != &other)
1482 {
1483 base::move(other.begin(), other.end());
1484 }
1485 }
1486#endif
1487
1488 //*************************************************************************
1493 //*************************************************************************
1494 template <typename TIterator>
1495 unordered_set(TIterator first_, TIterator last_, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1496 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1497 {
1498 base::assign(first_, last_);
1499 }
1500
1501#if ETL_HAS_INITIALIZER_LIST
1502 //*************************************************************************
1504 //*************************************************************************
1505 unordered_set(std::initializer_list<TKey> init, const THash& hash = THash(), const TKeyEqual& equal = TKeyEqual())
1506 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1507 {
1508 base::assign(init.begin(), init.end());
1509 }
1510#endif
1511
1512 //*************************************************************************
1514 //*************************************************************************
1516 {
1517 base::initialise();
1518 }
1519
1520 //*************************************************************************
1522 //*************************************************************************
1524 {
1525 base::operator=(rhs);
1526
1527 return *this;
1528 }
1529
1530#if ETL_USING_CPP11
1531 //*************************************************************************
1533 //*************************************************************************
1535 {
1536 base::operator=(etl::move(rhs));
1537
1538 return *this;
1539 }
1540#endif
1541
1542 private:
1543
1546
1548 typename base::bucket_t buckets[MAX_BUCKETS_];
1549 };
1550
1551 //*************************************************************************
1553 //*************************************************************************
1554#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1555 template <typename... T>
1556 unordered_set(T...) -> unordered_set<etl::nth_type_t<0, T...>, sizeof...(T)>;
1557#endif
1558
1559 //*************************************************************************
1561 //*************************************************************************
1562#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1563 template <typename TKey, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey>, typename... T>
1564 constexpr auto make_unordered_set(T&&... keys) -> etl::unordered_set<TKey, sizeof...(T), sizeof...(T), THash, TKeyEqual>
1565 {
1566 return { {etl::forward<T>(keys)...} };
1567 }
1568#endif
1569}
1570
1571#endif
const_iterator
Definition: intrusive_forward_list.h:448
iterator.
Definition: intrusive_forward_list.h:372
bool empty() const
Returns true if the list has no elements.
Definition: intrusive_forward_list.h:247
void clear()
Clears the intrusive_forward_list.
Definition: intrusive_forward_list.h:149
Definition: intrusive_forward_list.h:352
const_iterator cbegin() const
Gets the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:584
iterator insert_after(iterator position, value_type &value)
Inserts a value to the intrusive_forward_list after the specified position.
Definition: intrusive_forward_list.h:632
iterator end()
Gets the end of the intrusive_forward_list.
Definition: intrusive_forward_list.h:592
iterator before_begin()
Gets before the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:568
const_iterator cend() const
Gets the end of the intrusive_forward_list.
Definition: intrusive_forward_list.h:608
iterator begin()
Gets the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:552
Definition: unordered_set.h:324
Definition: unordered_set.h:182
A templated unordered_set implementation that uses a fixed size buffer.
Definition: unordered_set.h:1442
unordered_set(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition: unordered_set.h:1495
~unordered_set()
Destructor.
Definition: unordered_set.h:1515
unordered_set(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition: unordered_set.h:1455
unordered_set(const unordered_set &other)
Copy constructor.
Definition: unordered_set.h:1463
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition: algorithm.h:1495
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
Definition: exception.h:47
size_t size() const
Returns the number of allocated items in the pool.
Definition: ipool.h:293
bool empty() const
Definition: ipool.h:302
void release_all()
Release all objects in the pool.
Definition: ipool.h:248
bool full() const
Definition: ipool.h:311
size_t max_size() const
Returns the maximum number of items in the pool.
Definition: ipool.h:269
void release(const void *const p_object)
Definition: ipool.h:239
size_t available() const
Returns the number of free items in the pool.
Definition: ipool.h:285
Definition: ipool.h:102
Definition: pool.h:54
size_t count(key_parameter_t key) const
Definition: unordered_set.h:965
const_local_iterator begin(size_t i) const
Definition: unordered_set.h:515
key_equal key_eq() const
Definition: unordered_set.h:1151
iterator erase(const_iterator first_, const_iterator last_)
Definition: unordered_set.h:901
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:1091
size_type size() const
Gets the size of the unordered_set.
Definition: unordered_set.h:1083
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:1196
iunordered_set & operator=(const iunordered_set &rhs)
Assignment operator.
Definition: unordered_set.h:1159
local_iterator begin(size_t i)
Definition: unordered_set.h:506
void insert(TIterator first_, TIterator last_)
Definition: unordered_set.h:828
float load_factor() const
Definition: unordered_set.h:1133
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:1115
size_type bucket_size(key_parameter_t key) const
Definition: unordered_set.h:596
~iunordered_set()
For library debugging purposes only.
Definition: unordered_set.h:1391
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:955
size_t available() const
Definition: unordered_set.h:1124
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:802
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:1067
iterator find(key_parameter_t key)
Definition: unordered_set.h:975
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition: unordered_set.h:1046
iterator end()
Definition: unordered_set.h:533
size_t erase(key_parameter_t key)
Definition: unordered_set.h:842
const_iterator find(key_parameter_t key) const
Definition: unordered_set.h:1009
hasher hash_function() const
Definition: unordered_set.h:1142
bool empty() const
Checks to see if the unordered_set is empty.
Definition: unordered_set.h:1107
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:1210
size_type capacity() const
Gets the maximum possible size of the unordered_set.
Definition: unordered_set.h:1099
const_iterator cbegin() const
Definition: unordered_set.h:497
iterator erase(const_iterator ielement)
Definition: unordered_set.h:873
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
bool operator!=(const etl::iunordered_set< TKey, TMapped, TKeyCompare > &lhs, const etl::iunordered_set< TKey, TMapped, TKeyCompare > &rhs)
Definition: unordered_set.h:1432
bool operator==(const etl::iunordered_set< TKey, TMapped, TKeyCompare > &lhs, const etl::iunordered_set< TKey, TMapped, TKeyCompare > &rhs)
Definition: unordered_set.h:1405
bitset_ext
Definition: absolute.h:38
etl::byte operator&(etl::byte lhs, etl::byte rhs)
And.
Definition: byte.h:273
Definition: compare.h:52
iterator
Definition: iterator.h:399
Definition: unordered_set.h:150