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> >
161 return (
lhs.key ==
rhs.key);
177 typedef typename bucket_t::iterator local_iterator;
178 typedef typename bucket_t::const_iterator const_local_iterator;
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;
262 return &(inode->key);
268 return &(inode->key);
296 return rhs.inode == inode;
306 bucket_t*& get_bucket_list_iterator()
312 local_iterator get_local_iterator()
319 local_iterator inode;
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;
413 return &(inode->key);
419 return &(inode->key);
447 return rhs.inode == inode;
457 bucket_t*& get_bucket_list_iterator()
463 local_iterator get_local_iterator()
470 local_iterator inode;
473 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
481 return iterator(pbuckets + number_of_buckets, first, first->begin());
490 return const_iterator(pbuckets + number_of_buckets, first, first->begin());
499 return const_iterator(pbuckets + number_of_buckets, first, first->begin());
508 return pbuckets[
i].begin();
515 const_local_iterator
begin(
size_t i)
const
517 return pbuckets[
i].cbegin();
526 return pbuckets[
i].cbegin();
535 return iterator(pbuckets + number_of_buckets, last, last->end());
544 return const_iterator(pbuckets + number_of_buckets, last, last->end());
553 return const_iterator(pbuckets + number_of_buckets, last, last->end());
562 return pbuckets[
i].end();
569 const_local_iterator
end(
size_t i)
const
571 return pbuckets[
i].cend();
578 const_local_iterator
cend(
size_t i)
const
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>
631#if ETL_IS_DEBUG_BUILD
653 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
665 result.second =
false;
674 bucket_t* pbucket = pbuckets + index;
684 ETL_INCREMENT_DEBUG_COUNT;
688 adjust_first_last_markers_after_insert(&
bucket);
690 result.first =
iterator(pbuckets + number_of_buckets, pbucket, pbucket->begin());
691 result.second =
true;
697 local_iterator inode =
bucket.begin();
699 while (inode !=
bucket.end())
702 if (key_equal_function(inode->key, key))
712 if (inode ==
bucket.end())
718 ETL_INCREMENT_DEBUG_COUNT;
722 adjust_first_last_markers_after_insert(&
bucket);
726 result.second =
true;
741 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
753 result.second =
false;
762 bucket_t* pbucket = pbuckets + index;
763 bucket_t& bucket = *pbucket;
769 node_t* node = allocate_data_node();
771 ::new (&node->key) value_type(
etl::move(key));
772 ETL_INCREMENT_DEBUG_COUNT;
775 bucket.insert_after(bucket.before_begin(), *node);
776 adjust_first_last_markers_after_insert(&bucket);
778 result.first = iterator(pbuckets + number_of_buckets, pbucket, pbucket->
begin());
779 result.second = true;
784 local_iterator inode_previous = bucket.before_begin();
785 local_iterator inode = bucket.begin();
787 while (inode != bucket.end())
790 if (key_equal_function(inode->key, key))
800 if (inode == bucket.end())
803 node_t* node = allocate_data_node();
805 ::new (&node->key) value_type(
etl::move(key));
806 ETL_INCREMENT_DEBUG_COUNT;
809 bucket.insert_after(inode_previous, *node);
810 adjust_first_last_markers_after_insert(&bucket);
813 result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
814 result.second = true;
842 return insert(etl::move(key)).first;
853 template <
class TIterator>
939 local_iterator
iprevious = pbucket->before_begin();
941 local_iterator
iend =
last_.get_local_iterator();
967 }
while (pbucket->empty());
993 return (
find(key) ==
end()) ? 0 : 1;
1005 bucket_t* pbucket = pbuckets + index;
1012 local_iterator inode =
bucket.begin();
1015 while (inode !=
iend)
1018 if (key_equal_function(key, inode->key))
1020 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1039 bucket_t* pbucket = pbuckets + index;
1046 local_iterator inode =
bucket.begin();
1049 while (inode !=
iend)
1052 if (key_equal_function(key, inode->key))
1054 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1082 return ETL_OR_STD::pair<iterator, iterator>(
f,
l);
1103 return ETL_OR_STD::pair<const_iterator, const_iterator>(
f,
l);
1111 return pnodepool->
size();
1135 return pnodepool->
empty();
1143 return pnodepool->
full();
1170 return key_hash_function;
1179 return key_equal_function;
1190 key_hash_function =
rhs.hash_function();
1191 key_equal_function =
rhs.key_eq();
1208 key_hash_function =
rhs.hash_function();
1209 key_equal_function =
rhs.key_eq();
1210 move(
rhs.begin(),
rhs.end());
1241 for (
size_t i = 0
UL;
i < number_of_buckets; ++
i)
1248 local_iterator it =
bucket.begin();
1250 while (it !=
bucket.end())
1253 it->key.~value_type();
1255 ETL_DECREMENT_DEBUG_COUNT;
1277#if ETL_IS_DEBUG_BUILD
1278 difference_type
d = etl::distance(
b, e);
1298 node_t* allocate_data_node()
1300 node_t* (
etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1301 return (pnodepool->*func)();
1307 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1316 if (pbucket < first)
1320 else if (pbucket > last)
1330 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1339 if (pbucket == first)
1342 while (first->empty())
1347 else if (pbucket == last)
1351 bucket_t* pend = last;
1355 while (pbucket != pend)
1357 if (!pbucket->empty())
1371 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1373 local_iterator inext = bucket.erase_after(iprevious);
1374 icurrent->key.~value_type();
1375 pnodepool->
release(&*icurrent);
1376 adjust_first_last_markers_after_erase(&bucket);
1377 ETL_DECREMENT_DEBUG_COUNT;
1392 const size_t number_of_buckets;
1399 hasher key_hash_function;
1402 key_equal key_equal_function;
1405 ETL_DECLARE_DEBUG_COUNT;
1410#if defined(ETL_POLYMORPHIC_UNORDERED_SET) || defined(ETL_POLYMORPHIC_CONTAINERS)
1430 template <
typename TKey,
typename THash,
typename TKeyEqual>
1449 ETL_OR_STD::pair<itr_t, itr_t> range =
rhs.equal_range(
l_value);
1451 if (range.first !=
rhs.end())
1477 template <
typename TKey,
typename THash,
typename TKeyEqual>
1487 template <
typename TKey, const
size_t MAX_SIZE_,
size_t MAX_BUCKETS_ = MAX_SIZE_,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey> >
1496 static ETL_CONSTANT
size_t MAX_SIZE =
MAX_SIZE_;
1503 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1511 :
base(node_pool, buckets, MAX_BUCKETS,
other.hash_function(),
other.key_eq())
1525 : base(node_pool, buckets, MAX_BUCKETS,
other.hash_function(),
other.key_eq())
1541 template <
typename TIterator>
1543 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1548#if ETL_HAS_INITIALIZER_LIST
1553 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1555 base::assign(
init.begin(),
init.end());
1572 base::operator=(
rhs);
1583 base::operator=(etl::move(
rhs));
1595 typename base::bucket_t buckets[MAX_BUCKETS_];
1601#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1602 template <
typename... T>
1603 unordered_set(T...) -> unordered_set<
etl::nth_type_t<0, T...>,
sizeof...(T)>;
1609#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1610 template <
typename TKey,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey>,
typename... T>
1611 constexpr auto make_unordered_set(T&&... keys) ->
etl::unordered_set<TKey,
sizeof...(T),
sizeof...(T), THash, TKeyEqual>
Definition unordered_set.h:324
Definition unordered_set.h:182
A templated unordered_set implementation that uses a fixed size buffer.
Definition unordered_set.h:1489
unordered_set(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_set.h:1542
~unordered_set()
Destructor.
Definition unordered_set.h:1562
unordered_set(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_set.h:1502
unordered_set(const unordered_set &other)
Copy constructor.
Definition unordered_set.h:1510
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:966
#define ETL_ASSERT(b, e)
Definition error_handler.h:316
Definition exception.h:47
size_t size() const
Returns the number of allocated items in the pool.
Definition ipool.h:293
bool empty() const
Definition ipool.h:302
void release_all()
Release all objects in the pool.
Definition ipool.h:248
bool full() const
Definition ipool.h:311
size_t max_size() const
Returns the maximum number of items in the pool.
Definition ipool.h:269
void release(const void *const p_object)
Definition ipool.h:239
size_t available() const
Returns the number of free items in the pool.
Definition ipool.h:285
size_t count(key_parameter_t key) const
Definition unordered_set.h:991
const_local_iterator begin(size_t i) const
Definition unordered_set.h:515
key_equal key_eq() const
Definition unordered_set.h:1177
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_set.h:927
local_iterator end(size_t i)
Definition unordered_set.h:560
size_type bucket_count() const
Definition unordered_set.h:616
size_type max_size() const
Gets the maximum possible size of the unordered_set.
Definition unordered_set.h:1117
size_type size() const
Gets the size of the unordered_set.
Definition unordered_set.h:1109
iunordered_set(pool_t &node_pool_, bucket_t *pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
Constructor.
Definition unordered_set.h:1222
iunordered_set & operator=(const iunordered_set &rhs)
Assignment operator.
Definition unordered_set.h:1185
local_iterator begin(size_t i)
Definition unordered_set.h:506
void insert(TIterator first_, TIterator last_)
Definition unordered_set.h:854
float load_factor() const
Definition unordered_set.h:1159
const_iterator begin() const
Definition unordered_set.h:488
const_local_iterator cbegin(size_t i) const
Definition unordered_set.h:524
bool full() const
Checks to see if the unordered_set is full.
Definition unordered_set.h:1141
size_type bucket_size(key_parameter_t key) const
Definition unordered_set.h:596
~iunordered_set()
Destructor.
Definition unordered_set.h:1417
size_type get_bucket_index(key_parameter_t key) const
Definition unordered_set.h:587
const_iterator end() const
Definition unordered_set.h:542
void clear()
Clears the unordered_set.
Definition unordered_set.h:981
size_t available() const
Definition unordered_set.h:1150
ETL_OR_STD::pair< iterator, bool > insert(const_reference key)
Definition unordered_set.h:651
iterator insert(const_iterator, const_reference key)
Definition unordered_set.h:828
void assign(TIterator first_, TIterator last_)
Definition unordered_set.h:629
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(key_parameter_t key) const
Definition unordered_set.h:1093
iterator find(key_parameter_t key)
Definition unordered_set.h:1001
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition unordered_set.h:1072
iterator end()
Definition unordered_set.h:533
size_t erase(key_parameter_t key)
Definition unordered_set.h:868
const_iterator find(key_parameter_t key) const
Definition unordered_set.h:1035
hasher hash_function() const
Definition unordered_set.h:1168
bool empty() const
Checks to see if the unordered_set is empty.
Definition unordered_set.h:1133
size_type max_bucket_count() const
Definition unordered_set.h:607
iterator begin()
Definition unordered_set.h:479
const_local_iterator cend(size_t i) const
Definition unordered_set.h:578
const_iterator cend() const
Definition unordered_set.h:551
const_local_iterator end(size_t i) const
Definition unordered_set.h:569
void initialise()
Initialise the unordered_set.
Definition unordered_set.h:1236
size_type capacity() const
Gets the maximum possible size of the unordered_set.
Definition unordered_set.h:1125
const_iterator cbegin() const
Definition unordered_set.h:497
iterator erase(const_iterator ielement)
Definition unordered_set.h:899
Definition unordered_set.h:127
Definition unordered_set.h:70
Definition unordered_set.h:84
Definition unordered_set.h:111
Definition unordered_set.h:98
bitset_ext
Definition absolute.h:38
A forward link.
Definition intrusive_links.h:88
iterator
Definition iterator.h:399
Definition unordered_set.h:150
pair holds two objects of arbitrary type
Definition utility.h:164
T1 first
first is a copy of the first object
Definition utility.h:168