31#ifndef ETL_UNORDERED_SET_INCLUDED
32#define ETL_UNORDERED_SET_INCLUDED
127 template <
typename TKey,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey> >
163 return (
lhs.key ==
rhs.key);
179 typedef typename bucket_t::iterator local_iterator;
180 typedef typename bucket_t::const_iterator const_local_iterator;
207 : pbuckets_end(
other.pbuckets_end)
208 , pbucket(
other.pbucket)
219 if (inode == pbucket->end())
223 while ((pbucket != pbuckets_end) && (pbucket->empty()))
229 if (pbucket != pbuckets_end)
231 inode = pbucket->begin();
249 pbuckets_end =
other.pbuckets_end;
250 pbucket =
other.pbucket;
264 return &(inode->key);
270 return &(inode->key);
298 return rhs.inode == inode;
308 bucket_t*& get_bucket_list_iterator()
314 local_iterator get_local_iterator()
321 local_iterator inode;
349 : pbuckets_end(
other.pbuckets_end)
350 , pbucket(
other.pbucket)
357 : pbuckets_end(
other.pbuckets_end)
358 , pbucket(
other.pbucket)
369 if (inode == pbucket->end())
374 while ((pbucket != pbuckets_end) && (pbucket->empty()))
380 if (pbucket != pbuckets_end)
382 inode = pbucket->begin();
400 pbuckets_end =
other.pbuckets_end;
401 pbucket =
other.pbucket;
415 return &(inode->key);
421 return &(inode->key);
449 return rhs.inode == inode;
459 bucket_t*& get_bucket_list_iterator()
465 local_iterator get_local_iterator()
472 local_iterator inode;
475 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
483 return iterator(pbuckets + number_of_buckets, first, first->begin());
492 return const_iterator(pbuckets + number_of_buckets, first, first->begin());
501 return const_iterator(pbuckets + number_of_buckets, first, first->begin());
510 return pbuckets[
i].begin();
517 const_local_iterator
begin(
size_t i)
const
519 return pbuckets[
i].cbegin();
528 return pbuckets[
i].cbegin();
537 return iterator(pbuckets + number_of_buckets, last, last->end());
546 return const_iterator(pbuckets + number_of_buckets, last, last->end());
555 return const_iterator(pbuckets + number_of_buckets, last, last->end());
564 return pbuckets[
i].end();
571 const_local_iterator
end(
size_t i)
const
573 return pbuckets[
i].cend();
580 const_local_iterator
cend(
size_t i)
const
582 return pbuckets[
i].cend();
591 return key_hash_function(key) % number_of_buckets;
602 return key_hash_function(key) % number_of_buckets;
612 size_t index =
bucket(key);
614 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
625 size_t index =
bucket(key);
627 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
637 return number_of_buckets;
646 return number_of_buckets;
656 template <
typename TIterator>
659#if ETL_IS_DEBUG_BUILD
681 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
693 result.second =
false;
702 bucket_t* pbucket = pbuckets + index;
712 ETL_INCREMENT_DEBUG_COUNT;
716 adjust_first_last_markers_after_insert(&
bucket);
718 result.first =
iterator(pbuckets + number_of_buckets, pbucket, pbucket->begin());
719 result.second =
true;
725 local_iterator inode =
bucket.begin();
727 while (inode !=
bucket.end())
730 if (key_equal_function(inode->key, key))
740 if (inode ==
bucket.end())
746 ETL_INCREMENT_DEBUG_COUNT;
750 adjust_first_last_markers_after_insert(&
bucket);
754 result.second =
true;
768 ETL_OR_STD::pair<iterator, bool>
insert(
const K& key)
770 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
782 result.second =
false;
791 bucket_t* pbucket = pbuckets + index;
792 bucket_t& bucket = *pbucket;
798 node_t* node = allocate_data_node();
800 ::new (&node->key) value_type(key);
801 ETL_INCREMENT_DEBUG_COUNT;
804 bucket.insert_after(bucket.before_begin(), *node);
805 adjust_first_last_markers_after_insert(&bucket);
807 result.first = iterator(pbuckets + number_of_buckets, pbucket, pbucket->
begin());
808 result.second = true;
813 local_iterator inode_previous = bucket.before_begin();
814 local_iterator inode = bucket.begin();
816 while (inode != bucket.end())
819 if (key_equal_function(inode->key, key))
829 if (inode == bucket.end())
832 node_t* node = allocate_data_node();
834 ::new (&node->key) value_type(key);
835 ETL_INCREMENT_DEBUG_COUNT;
838 bucket.insert_after(inode_previous, *node);
839 adjust_first_last_markers_after_insert(&bucket);
842 result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
843 result.second = true;
857 ETL_OR_STD::pair<iterator, bool>
insert(rvalue_reference key)
859 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
863 iterator iter =
find(key);
866 ETL_ASSERT_FAIL(ETL_ERROR(unordered_set_full));
871 result.second =
false;
880 bucket_t* pbucket = pbuckets + index;
881 bucket_t& bucket = *pbucket;
887 node_t* node = allocate_data_node();
889 ::new (&node->key) value_type(
etl::move(key));
890 ETL_INCREMENT_DEBUG_COUNT;
893 bucket.insert_after(bucket.before_begin(), *node);
894 adjust_first_last_markers_after_insert(&bucket);
896 result.first = iterator(pbuckets + number_of_buckets, pbucket, pbucket->
begin());
897 result.second = true;
902 local_iterator inode_previous = bucket.before_begin();
903 local_iterator inode = bucket.begin();
905 while (inode != bucket.end())
908 if (key_equal_function(inode->key, key))
918 if (inode == bucket.end())
921 node_t* node = allocate_data_node();
923 ::new (&node->key) value_type(
etl::move(key));
924 ETL_INCREMENT_DEBUG_COUNT;
927 bucket.insert_after(inode_previous, *node);
928 adjust_first_last_markers_after_insert(&bucket);
931 result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
932 result.second = true;
960 return insert(etl::move(key)).first;
971 template <
class TIterator>
1020 size_t erase(
const K& key)
1025 bucket_t&
bucket = pbuckets[index];
1038 if (icurrent != bucket.end())
1040 delete_data_node(iprevious, icurrent, bucket);
1092 local_iterator
iprevious = pbucket->before_begin();
1094 local_iterator
iend =
last_.get_local_iterator();
1120 }
while (pbucket->empty());
1146 return (
find(key) ==
end()) ? 0 : 1;
1156 size_t count(
const K& key)
const
1158 return (
find(key) ==
end()) ? 0 : 1;
1171 bucket_t* pbucket = pbuckets + index;
1178 local_iterator inode =
bucket.begin();
1181 while (inode !=
iend)
1184 if (key_equal_function(key, inode->key))
1186 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1205 bucket_t* pbucket = pbuckets + index;
1212 local_iterator inode =
bucket.begin();
1215 while (inode !=
iend)
1218 if (key_equal_function(key, inode->key))
1220 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1241 bucket_t* pbucket = pbuckets + index;
1242 bucket_t&
bucket = *pbucket;
1248 local_iterator inode =
bucket.begin();
1251 while (inode !=
iend)
1254 if (key_equal_function(key, inode->key))
1256 return iterator(pbuckets + number_of_buckets, pbucket, inode);
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
1278 bucket_t* pbucket = pbuckets + index;
1279 bucket_t& bucket = *pbucket;
1282 if (!bucket.empty())
1285 local_iterator inode = bucket.begin();
1286 local_iterator iend = bucket.end();
1288 while (inode != iend)
1291 if (key_equal_function(key, inode->key))
1293 return iterator(pbuckets + number_of_buckets, pbucket, inode);
1322 return ETL_OR_STD::pair<iterator, iterator>(
f,
l);
1343 return ETL_OR_STD::pair<const_iterator, const_iterator>(
f,
l);
1356 ETL_OR_STD::pair<iterator, iterator>
equal_range(
const K& key)
1366 return ETL_OR_STD::pair<iterator, iterator>(f, l);
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
1382 const_iterator f =
find(key);
1383 const_iterator l = f;
1390 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1399 return pnodepool->
size();
1423 return pnodepool->
empty();
1431 return pnodepool->
full();
1458 return key_hash_function;
1467 return key_equal_function;
1478 key_hash_function =
rhs.hash_function();
1479 key_equal_function =
rhs.key_eq();
1496 key_hash_function =
rhs.hash_function();
1497 key_equal_function =
rhs.key_eq();
1498 move(
rhs.begin(),
rhs.end());
1548 for (
size_t i = 0
UL;
i < number_of_buckets; ++
i)
1555 local_iterator it =
bucket.begin();
1557 while (it !=
bucket.end())
1560 it->key.~value_type();
1562 ETL_DECREMENT_DEBUG_COUNT;
1584#if ETL_IS_DEBUG_BUILD
1585 difference_type
d = etl::distance(
b, e);
1605 node_t* allocate_data_node()
1607 node_t* (
etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1608 return (pnodepool->*func)();
1614 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1623 if (pbucket < first)
1627 else if (pbucket > last)
1637 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1646 if (pbucket == first)
1649 while (first->empty())
1654 else if (pbucket == last)
1658 bucket_t* pend = last;
1662 while (pbucket != pend)
1664 if (!pbucket->empty())
1678 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1680 local_iterator inext = bucket.erase_after(iprevious);
1681 icurrent->key.~value_type();
1682 pnodepool->
release(&*icurrent);
1683 adjust_first_last_markers_after_erase(&bucket);
1684 ETL_DECREMENT_DEBUG_COUNT;
1699 const size_t number_of_buckets;
1706 hasher key_hash_function;
1709 key_equal key_equal_function;
1712 ETL_DECLARE_DEBUG_COUNT;
1717#if defined(ETL_POLYMORPHIC_UNORDERED_SET) || defined(ETL_POLYMORPHIC_CONTAINERS)
1737 template <
typename TKey,
typename THash,
typename TKeyEqual>
1756 ETL_OR_STD::pair<itr_t, itr_t> range =
rhs.equal_range(
l_value);
1758 if (range.first !=
rhs.end())
1784 template <
typename TKey,
typename THash,
typename TKeyEqual>
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> >
1803 static ETL_CONSTANT
size_t MAX_SIZE =
MAX_SIZE_;
1810 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1818 :
base(node_pool, buckets, MAX_BUCKETS,
other.hash_function(),
other.key_eq())
1832 : base(node_pool, buckets, MAX_BUCKETS,
other.hash_function(),
other.key_eq())
1848 template <
typename TIterator>
1850 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1855#if ETL_HAS_INITIALIZER_LIST
1860 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1862 base::assign(
init.begin(),
init.end());
1879 base::operator=(
rhs);
1890 base::operator=(etl::move(
rhs));
1902 typename base::bucket_t buckets[MAX_BUCKETS_];
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)>;
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>
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
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
A forward link.
Definition intrusive_links.h:88
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