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> >
129 typedef TKey value_type;
130 typedef TKey key_type;
131 typedef THash hasher;
132 typedef TKeyEqual key_equal;
133 typedef value_type& reference;
134 typedef const value_type& const_reference;
136 typedef value_type&& rvalue_reference;
138 typedef value_type* pointer;
139 typedef const value_type* const_pointer;
140 typedef size_t size_type;
142 typedef const TKey& key_parameter_t;
150 node_t(const_reference key_)
158 friend bool operator ==(
const node_t& lhs,
const node_t& rhs)
160 return (lhs.key == rhs.key);
163 friend bool operator !=(
const node_t& lhs,
const node_t& rhs)
165 return !(lhs == rhs);
176 typedef typename bucket_t::iterator local_iterator;
177 typedef typename bucket_t::const_iterator const_local_iterator;
184 typedef typename etl::iterator<ETL_OR_STD::forward_iterator_tag, TKey>::value_type value_type;
185 typedef typename iunordered_multiset::key_type key_type;
186 typedef typename iunordered_multiset::hasher hasher;
187 typedef typename iunordered_multiset::key_equal key_equal;
188 typedef typename iunordered_multiset::reference reference;
189 typedef typename iunordered_multiset::const_reference const_reference;
190 typedef typename iunordered_multiset::pointer pointer;
191 typedef typename iunordered_multiset::const_pointer const_pointer;
192 typedef typename iunordered_multiset::size_type size_type;
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;
253 reference operator *()
const
261 return &(inode->key);
265 pointer operator ->()
const
267 return &(inode->key);
273 return lhs.compare(rhs);
279 return !(lhs == rhs);
286 : pbuckets_end(pbuckets_end_)
295 return rhs.inode == inode;
305 bucket_t*& get_bucket_list_iterator()
326 typedef typename etl::iterator<ETL_OR_STD::forward_iterator_tag, const TKey>::value_type value_type;
327 typedef typename iunordered_multiset::key_type key_type;
328 typedef typename iunordered_multiset::hasher hasher;
329 typedef typename iunordered_multiset::key_equal key_equal;
330 typedef typename iunordered_multiset::reference reference;
331 typedef typename iunordered_multiset::const_reference const_reference;
332 typedef typename iunordered_multiset::pointer pointer;
333 typedef typename iunordered_multiset::const_pointer const_pointer;
334 typedef typename iunordered_multiset::size_type size_type;
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;
404 const_reference operator *()
const
412 return &(inode->key);
416 const_pointer operator ->()
const
418 return &(inode->key);
424 return lhs.compare(rhs);
430 return !(lhs == rhs);
437 : pbuckets_end(pbuckets_end_)
446 return rhs.inode == inode;
456 bucket_t*& get_bucket_list_iterator()
472 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
480 return iterator((pbuckets + number_of_buckets), first, first->
begin());
507 return pbuckets[i].
begin();
516 return pbuckets[i].
cbegin();
525 return pbuckets[i].
cbegin();
534 return iterator((pbuckets + number_of_buckets), last, last->
end());
561 return pbuckets[i].
end();
570 return pbuckets[i].
cend();
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>
628 void assign(TIterator first_, TIterator last_)
630#if ETL_IS_DEBUG_BUILD
631 difference_type d = etl::distance(first_, last_);
638 while (first_ != last_)
650 ETL_OR_STD::pair<iterator, bool>
insert(const_reference key)
652 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
660 bucket_t* pbucket = pbuckets + index;
667 node_t& node = allocate_data_node();
669 ::new (&node.key) value_type(key);
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;
685 while (inode != bucket.
end())
688 if (key_equal_function(inode->key, key))
698 node_t& node = allocate_data_node();
700 ::new (&node.key) value_type(key);
701 ETL_INCREMENT_DEBUG_COUNT
705 adjust_first_last_markers_after_insert(&bucket);
708 result.first =
iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
709 result.second =
true;
721 ETL_OR_STD::pair<iterator, bool>
insert(rvalue_reference key)
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
744 bucket.insert_after(bucket.before_begin(), node);
745 adjust_first_last_markers_after_insert(&bucket);
747 result.first =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->
begin());
748 result.second = true;
753 local_iterator inode_previous = bucket.before_begin();
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>
806 void insert(TIterator first_, TIterator last_)
808 while (first_ != last_)
825 bucket_t& bucket = pbuckets[bucket_id];
830 while (icurrent != bucket.
end())
832 if (key_equal_function(icurrent->key, key))
834 delete_data_node(iprevious, icurrent, bucket);
836 icurrent = iprevious;
856 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
859 bucket_t& bucket = ielement.get_bucket();
864 while (iprevious->etl_next != &*icurrent)
869 delete_data_node(iprevious, icurrent, bucket);
884 if ((first_ ==
begin()) && (last_ ==
end()))
891 bucket_t* pbucket = first_.get_bucket_list_iterator();
892 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
898 while (iprevious->etl_next != &*icurrent)
904 iterator ibefore_erased =
iterator((pbuckets + number_of_buckets), pbucket, iprevious);
907 while ((icurrent != iend) || (pbucket != pend_bucket))
909 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
912 if ((icurrent != iend) || (pbucket != pend_bucket))
915 if ((icurrent == pbucket->
end()))
921 }
while (pbucket->
empty());
924 icurrent = pbucket->
begin();
929 return ++ibefore_erased;
945 size_t count(key_parameter_t key)
const
956 while ((l !=
end()) && key_equal_function(key, *l))
975 bucket_t* pbucket = pbuckets + index;
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;
1013 if (!bucket.
empty())
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);
1068 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(key_parameter_t key)
const
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;
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());
1203 : pnodepool(&node_pool_)
1204 , pbuckets(pbuckets_)
1205 , number_of_buckets(number_of_buckets_)
1208 , key_hash_function(key_hash_function_)
1209 , key_equal_function(key_equal_function_)
1221 for (
size_t i = 0UL; i < number_of_buckets; ++i)
1225 if (!bucket.
empty())
1230 while (it != bucket.
end())
1233 it->key.~value_type();
1235 ETL_DECREMENT_DEBUG_COUNT
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_MULTISET) || 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_;
1457 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1485 base::move(other.begin(), other.end());
1496 template <
typename TIterator>
1497 unordered_multiset(TIterator first_, TIterator last_,
const THash& hash = THash(),
const TKeyEqual& equal = TKeyEqual())
1498 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1500 base::assign(first_, last_);
1503#if ETL_HAS_INITIALIZER_LIST
1507 unordered_multiset(std::initializer_list<TKey> init,
const THash& hash = THash(),
const TKeyEqual& equal = TKeyEqual())
1508 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1510 base::assign(init.begin(), init.end());
1527 base::operator =(rhs);
1538 base::operator =(etl::move(rhs));
1550 typename base::bucket_t buckets[MAX_BUCKETS_];
1556#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1557 template <
typename... T>
1558 unordered_multiset(T...) -> unordered_multiset<etl::nth_type_t<0, T...>,
sizeof...(T)>;
1564#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1565 template <
typename TKey,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey>,
typename... T>
1566 constexpr auto make_unordered_multiset(T&&... keys) ->
etl::unordered_multiset<TKey,
sizeof...(T),
sizeof...(T), THash, TKeyEqual>
1568 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_multiset.h:323
Definition: unordered_multiset.h:181
A templated unordered_multiset implementation that uses a fixed size buffer.
Definition: unordered_multiset.h:1442
unordered_multiset(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition: unordered_multiset.h:1456
~unordered_multiset()
Destructor.
Definition: unordered_multiset.h:1517
unordered_multiset(const unordered_multiset &other)
Copy constructor.
Definition: unordered_multiset.h:1464
unordered_multiset(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition: unordered_multiset.h:1497
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
~iunordered_multiset()
For library debugging purposes only.
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
bool operator==(const etl::iunordered_multiset< TKey, TMapped, TKeyCompare > &lhs, const etl::iunordered_multiset< TKey, TMapped, TKeyCompare > &rhs)
Definition: unordered_multiset.h:1405
bool operator!=(const etl::iunordered_multiset< TKey, TMapped, TKeyCompare > &lhs, const etl::iunordered_multiset< TKey, TMapped, TKeyCompare > &rhs)
Definition: unordered_multiset.h:1432
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_multiset.h:149