31#ifndef ETL_UNORDERED_SET_INCLUDED
32#define ETL_UNORDERED_SET_INCLUDED
125 template <
typename TKey,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey> >
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;
137 typedef value_type&& rvalue_reference;
139 typedef value_type* pointer;
140 typedef const value_type* const_pointer;
141 typedef size_t size_type;
143 typedef const TKey& key_parameter_t;
151 node_t(const_reference key_)
159 friend bool operator ==(
const node_t& lhs,
const node_t& rhs)
161 return (lhs.key == rhs.key);
164 friend bool operator !=(
const node_t& lhs,
const node_t& rhs)
166 return !(lhs == rhs);
177 typedef typename bucket_t::iterator local_iterator;
178 typedef typename bucket_t::const_iterator const_local_iterator;
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;
205 : pbuckets_end(other.pbuckets_end)
206 , pbucket(other.pbucket)
217 if (inode == pbucket->
end())
221 while ((pbucket != pbuckets_end) && (pbucket->
empty()))
227 if (pbucket != pbuckets_end)
229 inode = pbucket->
begin();
247 pbuckets_end = other.pbuckets_end;
248 pbucket = other.pbucket;
254 reference operator *()
const
262 return &(inode->key);
266 pointer operator ->()
const
268 return &(inode->key);
274 return lhs.compare(rhs);
280 return !(lhs == rhs);
287 : pbuckets_end(pbuckets_end_)
296 return rhs.inode == inode;
306 bucket_t*& get_bucket_list_iterator()
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;
347 : pbuckets_end(other.pbuckets_end)
348 , pbucket(other.pbucket)
355 : pbuckets_end(other.pbuckets_end)
356 , pbucket(other.pbucket)
367 if (inode == pbucket->
end())
372 while ((pbucket != pbuckets_end) && (pbucket->
empty()))
378 if (pbucket != pbuckets_end)
380 inode = pbucket->
begin();
398 pbuckets_end = other.pbuckets_end;
399 pbucket = other.pbucket;
405 const_reference operator *()
const
413 return &(inode->key);
417 const_pointer operator ->()
const
419 return &(inode->key);
425 return lhs.compare(rhs);
431 return !(lhs == rhs);
438 : pbuckets_end(pbuckets_end_)
447 return rhs.inode == inode;
457 bucket_t*& get_bucket_list_iterator()
473 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
481 return iterator(pbuckets + number_of_buckets, first, first->
begin());
508 return pbuckets[i].
begin();
517 return pbuckets[i].
cbegin();
526 return pbuckets[i].
cbegin();
535 return iterator(pbuckets + number_of_buckets, last, last->
end());
562 return pbuckets[i].
end();
571 return pbuckets[i].
cend();
580 return pbuckets[i].
cend();
589 return key_hash_function(key) % number_of_buckets;
598 size_t index = bucket(key);
600 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
609 return number_of_buckets;
618 return number_of_buckets;
628 template <
typename TIterator>
629 void assign(TIterator first_, TIterator last_)
631#if ETL_IS_DEBUG_BUILD
632 difference_type d = etl::distance(first_, last_);
639 while (first_ != last_)
651 ETL_OR_STD::pair<iterator, bool>
insert(const_reference key)
653 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
661 bucket_t* pbucket = pbuckets + index;
668 node_t& node = allocate_data_node();
670 ::new (&node.key) value_type(key);
671 ETL_INCREMENT_DEBUG_COUNT
675 adjust_first_last_markers_after_insert(&bucket);
677 result.first =
iterator(pbuckets + number_of_buckets, pbucket, pbucket->
begin());
678 result.second =
true;
686 while (inode != bucket.
end())
689 if (key_equal_function(inode->key, key))
699 if (inode == bucket.
end())
702 node_t& node = allocate_data_node();
704 ::new (&node.key) value_type(key);
705 ETL_INCREMENT_DEBUG_COUNT
709 adjust_first_last_markers_after_insert(&bucket);
712 result.first =
iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
713 result.second =
true;
726 ETL_OR_STD::pair<iterator, bool>
insert(rvalue_reference key)
728 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
736 bucket_t* pbucket = pbuckets + index;
737 bucket_t& bucket = *pbucket;
743 node_t& node = allocate_data_node();
745 ::new (&node.key) value_type(
etl::move(key));
746 ETL_INCREMENT_DEBUG_COUNT
749 bucket.insert_after(bucket.before_begin(), node);
750 adjust_first_last_markers_after_insert(&bucket);
752 result.first =
iterator(pbuckets + number_of_buckets, pbucket, pbucket->
begin());
753 result.second = true;
758 local_iterator inode_previous = bucket.before_begin();
759 local_iterator inode = bucket.begin();
761 while (inode != bucket.end())
764 if (key_equal_function(inode->key, key))
774 if (inode == bucket.end())
777 node_t& node = allocate_data_node();
779 ::new (&node.key) value_type(
etl::move(key));
780 ETL_INCREMENT_DEBUG_COUNT
783 bucket.insert_after(inode_previous, node);
784 adjust_first_last_markers_after_insert(&bucket);
787 result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
788 result.second = true;
816 return insert(etl::move(key)).first;
827 template <
class TIterator>
828 void insert(TIterator first_, TIterator last_)
830 while (first_ != last_)
853 while ((icurrent != bucket.
end()) && (!key_equal_function(icurrent->key, key)))
860 if (icurrent != bucket.
end())
862 delete_data_node(iprevious, icurrent, bucket);
876 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
879 bucket_t& bucket = ielement.get_bucket();
884 while (iprevious->etl_next != &*icurrent)
889 delete_data_node(iprevious, icurrent, bucket);
904 if ((first_ ==
begin()) && (last_ ==
end()))
911 bucket_t* pbucket = first_.get_bucket_list_iterator();
912 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
918 while (iprevious->etl_next != &*icurrent)
924 iterator ibefore_erased =
iterator((pbuckets + number_of_buckets), pbucket, iprevious);
927 while ((icurrent != iend) || (pbucket != pend_bucket))
929 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
932 if ((icurrent != iend) || (pbucket != pend_bucket))
935 if ((icurrent == pbucket->
end()))
941 }
while (pbucket->
empty());
944 icurrent = pbucket->
begin();
949 return ++ibefore_erased;
965 size_t count(key_parameter_t key)
const
967 return (
find(key) ==
end()) ? 0 : 1;
979 bucket_t* pbucket = pbuckets + index;
989 while (inode != iend)
992 if (key_equal_function(key, inode->key))
994 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1013 bucket_t* pbucket = pbuckets + index;
1017 if (!bucket.
empty())
1023 while (inode != iend)
1026 if (key_equal_function(key, inode->key))
1028 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1056 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1067 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(key_parameter_t key)
const
1077 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1085 return pnodepool->
size();
1109 return pnodepool->
empty();
1117 return pnodepool->
full();
1144 return key_hash_function;
1153 return key_equal_function;
1165 key_equal_function = rhs.
key_eq();
1182 key_hash_function = rhs.hash_function();
1183 key_equal_function = rhs.key_eq();
1184 move(rhs.begin(), rhs.end());
1197 : pnodepool(&node_pool_)
1198 , pbuckets(pbuckets_)
1199 , number_of_buckets(number_of_buckets_)
1202 , key_hash_function(key_hash_function_)
1203 , key_equal_function(key_equal_function_)
1215 for (
size_t i = 0UL; i < number_of_buckets; ++i)
1219 if (!bucket.
empty())
1224 while (it != bucket.
end())
1227 it->key.~value_type();
1229 ETL_DECREMENT_DEBUG_COUNT
1251#if ETL_IS_DEBUG_BUILD
1252 difference_type d = etl::distance(first, last);
1257 while (first != last)
1261 insert(etl::move(*first));
1272 node_t& allocate_data_node()
1274 node_t* (
etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1275 return *(pnodepool->*func)();
1281 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1290 if (pbucket < first)
1294 else if (pbucket > last)
1304 void adjust_first_last_markers_after_erase(bucket_t* pcurrent)
1313 if (pcurrent == first)
1316 while (first->empty())
1321 else if (pcurrent == last)
1324 bucket_t* pcurrent = first;
1325 bucket_t* pend = last;
1329 while (pcurrent != pend)
1331 if (!pcurrent->empty())
1345 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1347 local_iterator inext = bucket.erase_after(iprevious);
1348 icurrent->key.~value_type();
1349 pnodepool->
release(&*icurrent);
1350 adjust_first_last_markers_after_erase(&bucket);
1351 ETL_DECREMENT_DEBUG_COUNT
1366 const size_t number_of_buckets;
1373 hasher key_hash_function;
1376 key_equal key_equal_function;
1379 ETL_DECLARE_DEBUG_COUNT
1384#if defined(ETL_POLYMORPHIC_UNORDERED_SET) || defined(ETL_POLYMORPHIC_CONTAINERS)
1404 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
1407 const bool sizes_match = (lhs.
size() == rhs.
size());
1408 bool elements_match =
true;
1412 for (
size_t i = 0; (i < lhs.
bucket_count()) && elements_match; ++i)
1416 elements_match =
false;
1421 return (sizes_match && elements_match);
1431 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
1434 return !(lhs == rhs);
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> >
1449 static ETL_CONSTANT
size_t MAX_SIZE = MAX_SIZE_;
1450 static ETL_CONSTANT
size_t MAX_BUCKETS = MAX_BUCKETS_;
1455 unordered_set(
const THash& hash = THash(),
const TKeyEqual& equal = TKeyEqual())
1456 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1483 base::move(other.begin(), other.end());
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)
1498 base::assign(first_, last_);
1501#if ETL_HAS_INITIALIZER_LIST
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)
1508 base::assign(init.begin(), init.end());
1525 base::operator=(rhs);
1536 base::operator=(etl::move(rhs));
1548 typename base::bucket_t buckets[MAX_BUCKETS_];
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)>;
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>
1566 return { {etl::forward<T>(keys)...} };
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
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
A forward link.
Definition: intrusive_links.h:88
iterator
Definition: iterator.h:399
Definition: unordered_set.h:150