31#ifndef ETL_UNORDERED_MULTISET_INCLUDED
32#define ETL_UNORDERED_MULTISET_INCLUDED
124 template <
typename TKey,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey> >
160 return (
lhs.key ==
rhs.key);
176 typedef typename bucket_t::iterator local_iterator;
177 typedef typename bucket_t::const_iterator const_local_iterator;
204 : pbuckets_end(
other.pbuckets_end)
205 , pbucket(
other.pbucket)
216 if (inode == pbucket->end())
220 while ((pbucket != pbuckets_end) && (pbucket->empty()))
226 if (pbucket != pbuckets_end)
228 inode = pbucket->begin();
246 pbuckets_end =
other.pbuckets_end;
247 pbucket =
other.pbucket;
261 return &(inode->key);
267 return &(inode->key);
295 return rhs.inode == inode;
305 bucket_t*& get_bucket_list_iterator()
311 local_iterator get_local_iterator()
318 local_iterator inode;
346 : pbuckets_end(
other.pbuckets_end)
347 , pbucket(
other.pbucket)
354 : pbuckets_end(
other.pbuckets_end)
355 , pbucket(
other.pbucket)
366 if (inode == pbucket->end())
371 while ((pbucket != pbuckets_end) && (pbucket->empty()))
377 if (pbucket != pbuckets_end)
379 inode = pbucket->begin();
397 pbuckets_end =
other.pbuckets_end;
398 pbucket =
other.pbucket;
412 return &(inode->key);
418 return &(inode->key);
446 return rhs.inode == inode;
456 bucket_t*& get_bucket_list_iterator()
462 local_iterator get_local_iterator()
469 local_iterator inode;
472 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
480 return iterator((pbuckets + number_of_buckets), first, first->begin());
489 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
498 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
507 return pbuckets[
i].begin();
514 const_local_iterator
begin(
size_t i)
const
516 return pbuckets[
i].cbegin();
525 return pbuckets[
i].cbegin();
534 return iterator((pbuckets + number_of_buckets), last, last->end());
543 return const_iterator((pbuckets + number_of_buckets), last, last->end());
552 return const_iterator((pbuckets + number_of_buckets), last, last->end());
561 return pbuckets[
i].end();
568 const_local_iterator
end(
size_t i)
const
570 return pbuckets[
i].cend();
577 const_local_iterator
cend(
size_t i)
const
579 return pbuckets[
i].cend();
588 return key_hash_function(key) % number_of_buckets;
597 size_t index =
bucket(key);
599 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
608 return number_of_buckets;
617 return number_of_buckets;
627 template <
typename TIterator>
630#if ETL_IS_DEBUG_BUILD
652 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
660 bucket_t* pbucket = pbuckets + index;
670 ETL_INCREMENT_DEBUG_COUNT;
674 adjust_first_last_markers_after_insert(&
bucket);
676 result.first =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
677 result.second =
true;
683 local_iterator inode =
bucket.begin();
685 while (inode !=
bucket.end())
688 if (key_equal_function(inode->key, key))
701 ETL_INCREMENT_DEBUG_COUNT;
705 adjust_first_last_markers_after_insert(&
bucket);
709 result.second =
true;
723 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
731 bucket_t* pbucket = pbuckets + index;
732 bucket_t&
bucket = *pbucket;
738 node_t*
node = allocate_data_node();
740 ::new (&
node->key) value_type(
etl::move(key));
741 ETL_INCREMENT_DEBUG_COUNT;
745 adjust_first_last_markers_after_insert(&
bucket);
747 result.first =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->
begin());
748 result.second =
true;
754 local_iterator inode =
bucket.begin();
756 while (inode !=
bucket.end())
759 if (key_equal_function(inode->key, key))
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(inode_previous, *node);
776 adjust_first_last_markers_after_insert(&bucket);
779 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
780 result.second = true;
805 template <
class TIterator>
832 if (key_equal_function(
icurrent->key, key))
893 local_iterator
iprevious = pbucket->before_begin();
895 local_iterator
iend =
last_.get_local_iterator();
921 }
while (pbucket->empty());
956 while ((
l !=
end()) && key_equal_function(key, *
l))
975 bucket_t* pbucket = pbuckets + index;
982 local_iterator inode =
bucket.begin();
985 while (inode !=
iend)
988 if (key_equal_function(key, inode->key))
990 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1009 bucket_t* pbucket = pbuckets + index;
1016 local_iterator inode =
bucket.begin();
1019 while (inode !=
iend)
1022 if (key_equal_function(key, inode->key))
1024 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1051 while ((
l !=
end()) && key_equal_function(key, *
l))
1057 return ETL_OR_STD::pair<iterator, iterator>(
f,
l);
1077 while ((
l !=
end()) && key_equal_function(key, *
l))
1083 return ETL_OR_STD::pair<const_iterator, const_iterator>(
f,
l);
1091 return pnodepool->
size();
1115 return pnodepool->
empty();
1123 return pnodepool->
full();
1150 return key_hash_function;
1159 return key_equal_function;
1170 key_hash_function =
rhs.hash_function();
1171 key_equal_function =
rhs.key_eq();
1188 key_hash_function =
rhs.hash_function();
1189 key_equal_function =
rhs.key_eq();
1190 move(
rhs.begin(),
rhs.end());
1221 for (
size_t i = 0
UL;
i < number_of_buckets; ++
i)
1228 local_iterator it =
bucket.begin();
1230 while (it !=
bucket.end())
1233 it->key.~value_type();
1235 ETL_DECREMENT_DEBUG_COUNT;
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* pbucket)
1313 if (pbucket == first)
1316 while (first->empty())
1321 else if (pbucket == last)
1325 bucket_t* pend = last;
1329 while (pbucket != pend)
1331 if (!pbucket->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_MULTISET) || defined(ETL_POLYMORPHIC_CONTAINERS)
1404 template <
typename TKey,
typename THash,
typename TKeyEqual>
1458 template <
typename TKey,
typename THash,
typename TKeyEqual>
1468 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> >
1477 static ETL_CONSTANT
size_t MAX_SIZE =
MAX_SIZE_;
1485 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1493 :
base(node_pool, buckets, MAX_BUCKETS,
other.hash_function(),
other.key_eq())
1508 : base(node_pool, buckets, MAX_BUCKETS,
other.hash_function(),
other.key_eq())
1524 template <
typename TIterator>
1526 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1531#if ETL_HAS_INITIALIZER_LIST
1536 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1538 base::assign(
init.begin(),
init.end());
1555 base::operator =(
rhs);
1566 base::operator =(etl::move(
rhs));
1578 typename base::bucket_t buckets[MAX_BUCKETS_];
1584#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1585 template <
typename... T>
1586 unordered_multiset(T...) -> unordered_multiset<
etl::nth_type_t<0, T...>,
sizeof...(T)>;
1592#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1593 template <
typename TKey,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey>,
typename... T>
1594 constexpr auto make_unordered_multiset(T&&... keys) ->
etl::unordered_multiset<TKey,
sizeof...(T),
sizeof...(T), THash, TKeyEqual>
Definition unordered_multiset.h:323
Definition unordered_multiset.h:181
A templated unordered_multiset implementation that uses a fixed size buffer.
Definition unordered_multiset.h:1470
unordered_multiset(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_multiset.h:1484
~unordered_multiset()
Destructor.
Definition unordered_multiset.h:1545
unordered_multiset(const unordered_multiset &other)
Copy constructor.
Definition unordered_multiset.h:1492
unordered_multiset(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_multiset.h:1525
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:966
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition algorithm.h:1727
#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
~iunordered_multiset()
Destructor.
Definition unordered_multiset.h:1391
ETL_OR_STD::pair< iterator, bool > insert(const_reference key)
Definition unordered_multiset.h:650
size_t available() const
Definition unordered_multiset.h:1130
const_iterator cend() const
Definition unordered_multiset.h:550
iunordered_multiset & operator=(const iunordered_multiset &rhs)
Assignment operator.
Definition unordered_multiset.h:1165
const_iterator begin() const
Definition unordered_multiset.h:487
size_t erase(key_parameter_t key)
Definition unordered_multiset.h:820
void initialise()
Initialise the unordered_multiset.
Definition unordered_multiset.h:1216
iterator end()
Definition unordered_multiset.h:532
size_type max_size() const
Gets the maximum possible size of the unordered_multiset.
Definition unordered_multiset.h:1097
iterator insert(const_iterator, const_reference key)
Definition unordered_multiset.h:793
const_local_iterator end(size_t i) const
Definition unordered_multiset.h:568
size_type get_bucket_index(key_parameter_t key) const
Definition unordered_multiset.h:586
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(key_parameter_t key) const
Definition unordered_multiset.h:1068
const_iterator find(key_parameter_t key) const
Definition unordered_multiset.h:1005
local_iterator begin(size_t i)
Definition unordered_multiset.h:505
void assign(TIterator first_, TIterator last_)
Definition unordered_multiset.h:628
const_iterator cbegin() const
Definition unordered_multiset.h:496
iunordered_multiset(pool_t &node_pool_, bucket_t *pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
Constructor.
Definition unordered_multiset.h:1202
const_iterator end() const
Definition unordered_multiset.h:541
size_type bucket_size(key_parameter_t key) const
Definition unordered_multiset.h:595
void insert(TIterator first_, TIterator last_)
Definition unordered_multiset.h:806
void clear()
Clears the unordered_multiset.
Definition unordered_multiset.h:935
const_local_iterator cend(size_t i) const
Definition unordered_multiset.h:577
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_multiset.h:881
const_local_iterator cbegin(size_t i) const
Definition unordered_multiset.h:523
iterator find(key_parameter_t key)
Definition unordered_multiset.h:971
iterator begin()
Definition unordered_multiset.h:478
iterator erase(const_iterator ielement)
Definition unordered_multiset.h:853
key_equal key_eq() const
Definition unordered_multiset.h:1157
local_iterator end(size_t i)
Definition unordered_multiset.h:559
const_local_iterator begin(size_t i) const
Definition unordered_multiset.h:514
size_type max_bucket_count() const
Definition unordered_multiset.h:606
size_type size() const
Gets the size of the unordered_multiset.
Definition unordered_multiset.h:1089
hasher hash_function() const
Definition unordered_multiset.h:1148
size_type bucket_count() const
Definition unordered_multiset.h:615
size_type capacity() const
Gets the maximum possible size of the unordered_multiset.
Definition unordered_multiset.h:1105
size_t count(key_parameter_t key) const
Definition unordered_multiset.h:945
bool full() const
Checks to see if the unordered_multiset is full.
Definition unordered_multiset.h:1121
float load_factor() const
Definition unordered_multiset.h:1139
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition unordered_multiset.h:1042
bool empty() const
Checks to see if the unordered_multiset is empty.
Definition unordered_multiset.h:1113
Definition unordered_multiset.h:126
Definition unordered_multiset.h:69
Definition unordered_multiset.h:83
Definition unordered_multiset.h:110
Definition unordered_multiset.h:97
bitset_ext
Definition absolute.h:38
A forward link.
Definition intrusive_links.h:88
iterator
Definition iterator.h:399
Definition unordered_multiset.h:149
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
T2 second
second is a copy of the second object
Definition utility.h:169