31#ifndef ETL_UNORDERED_MULTIMAP_INCLUDED
32#define ETL_UNORDERED_MULTIMAP_INCLUDED
125 template <
typename TKey,
typename T,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey> >
130 typedef ETL_OR_STD::pair<const TKey, T> value_type;
132 typedef TKey key_type;
133 typedef T mapped_type;
134 typedef THash hasher;
135 typedef TKeyEqual key_equal;
136 typedef value_type& reference;
137 typedef const value_type& const_reference;
139 typedef value_type&& rvalue_reference;
141 typedef value_type* pointer;
142 typedef const value_type* const_pointer;
143 typedef size_t size_type;
145 typedef const key_type& const_key_reference;
147 typedef key_type&& rvalue_key_reference;
156 node_t(const_reference key_value_pair_)
157 : key_value_pair(key_value_pair_)
161 value_type key_value_pair;
164 friend bool operator ==(
const node_t& lhs,
const node_t& rhs)
166 return (lhs.key_value_pair.first == rhs.key_value_pair.first) &&
167 (lhs.key_value_pair.second == rhs.key_value_pair.second);
170 friend bool operator !=(
const node_t& lhs,
const node_t& rhs)
172 return !(lhs == rhs);
183 typedef typename bucket_t::iterator local_iterator;
184 typedef typename bucket_t::const_iterator const_local_iterator;
191 typedef typename etl::iterator<ETL_OR_STD::forward_iterator_tag, T>::value_type value_type;
192 typedef typename iunordered_multimap::key_type key_type;
193 typedef typename iunordered_multimap::mapped_type mapped_type;
194 typedef typename iunordered_multimap::hasher hasher;
195 typedef typename iunordered_multimap::key_equal key_equal;
196 typedef typename iunordered_multimap::reference reference;
197 typedef typename iunordered_multimap::const_reference const_reference;
198 typedef typename iunordered_multimap::pointer pointer;
199 typedef typename iunordered_multimap::const_pointer const_pointer;
200 typedef typename iunordered_multimap::size_type size_type;
212 : pbuckets_end(other.pbuckets_end)
213 , pbucket(other.pbucket)
224 if (inode == pbucket->
end())
228 while ((pbucket != pbuckets_end) && (pbucket->
empty()))
234 if (pbucket != pbuckets_end)
236 inode = pbucket->
begin();
254 pbuckets_end = other.pbuckets_end;
255 pbucket = other.pbucket;
261 reference operator *()
const
263 return inode->key_value_pair;
269 return &(inode->key_value_pair);
273 pointer operator ->()
const
275 return &(inode->key_value_pair);
281 return lhs.compare(rhs);
287 return !(lhs == rhs);
294 : pbuckets_end(pbuckets_end_)
303 return rhs.inode == inode;
313 bucket_t*& get_bucket_list_iterator()
334 typedef typename etl::iterator<ETL_OR_STD::forward_iterator_tag, const T>::value_type value_type;
335 typedef typename iunordered_multimap::key_type key_type;
336 typedef typename iunordered_multimap::mapped_type mapped_type;
337 typedef typename iunordered_multimap::hasher hasher;
338 typedef typename iunordered_multimap::key_equal key_equal;
339 typedef typename iunordered_multimap::reference reference;
340 typedef typename iunordered_multimap::const_reference const_reference;
341 typedef typename iunordered_multimap::pointer pointer;
342 typedef typename iunordered_multimap::const_pointer const_pointer;
343 typedef typename iunordered_multimap::size_type size_type;
355 : pbuckets_end(other.pbuckets_end)
356 , pbucket(other.pbucket)
363 : pbuckets_end(other.pbuckets_end)
364 , pbucket(other.pbucket)
375 if (inode == pbucket->
end())
380 while ((pbucket != pbuckets_end) && (pbucket->
empty()))
386 if (pbucket != pbuckets_end)
388 inode = pbucket->
begin();
406 pbuckets_end = other.pbuckets_end;
407 pbucket = other.pbucket;
413 const_reference operator *()
const
415 return inode->key_value_pair;
421 return &(inode->key_value_pair);
425 const_pointer operator ->()
const
427 return &(inode->key_value_pair);
433 return lhs.compare(rhs);
439 return !(lhs == rhs);
446 : pbuckets_end(pbuckets_end_)
455 return rhs.inode == inode;
465 bucket_t*& get_bucket_list_iterator()
481 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
489 return iterator((pbuckets + number_of_buckets), first, first->
begin());
516 return pbuckets[i].
begin();
525 return pbuckets[i].
cbegin();
534 return pbuckets[i].
cbegin();
543 return iterator((pbuckets + number_of_buckets), last, last->
end());
570 return pbuckets[i].
end();
579 return pbuckets[i].
cend();
588 return pbuckets[i].
cend();
597 return key_hash_function(key) % number_of_buckets;
606 size_t index = bucket(key);
608 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
617 return number_of_buckets;
626 return number_of_buckets;
636 template <
typename TIterator>
637 void assign(TIterator first_, TIterator last_)
639#if ETL_IS_DEBUG_BUILD
640 difference_type d = etl::distance(first_, last_);
647 while (first_ != last_)
665 const_key_reference key = key_value_pair.first;
671 bucket_t* pbucket = pbuckets + index;
678 node_t& node = allocate_data_node();
680 ::new (&node.key_value_pair) value_type(key_value_pair);
681 ETL_INCREMENT_DEBUG_COUNT
685 adjust_first_last_markers_after_insert(pbucket);
687 result =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->
begin());
695 while (inode != bucket.
end())
698 if (key_equal_function(inode->key_value_pair.first, key))
708 node_t& node = allocate_data_node();
710 ::new (&node.key_value_pair) value_type(key_value_pair);
711 ETL_INCREMENT_DEBUG_COUNT
715 adjust_first_last_markers_after_insert(&bucket);
718 result =
iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
736 const_key_reference key = key_value_pair.first;
742 bucket_t* pbucket = pbuckets + index;
743 bucket_t& bucket = *pbucket;
749 node_t& node = allocate_data_node();
751 ::new (&node.key_value_pair) value_type(
etl::move(key_value_pair));
752 ETL_INCREMENT_DEBUG_COUNT
755 bucket.insert_after(bucket.before_begin(), node);
756 adjust_first_last_markers_after_insert(pbucket);
758 result =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->
begin());
763 local_iterator inode_previous = bucket.before_begin();
764 local_iterator inode = bucket.begin();
766 while (inode != bucket.end())
769 if (key_equal_function(inode->key_value_pair.first, key))
779 node_t& node = allocate_data_node();
781 ::new (&node.key_value_pair) value_type(
etl::move(key_value_pair));
782 ETL_INCREMENT_DEBUG_COUNT
785 bucket.insert_after(inode_previous, node);
786 adjust_first_last_markers_after_insert(&bucket);
789 result = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
804 return insert(key_value_pair);
816 return insert(etl::move(key_value_pair));
827 template <
class TIterator>
828 void insert(TIterator first_, TIterator last_)
830 while (first_ != last_)
842 size_t erase(const_key_reference key)
847 bucket_t& bucket = pbuckets[bucket_id];
852 while (icurrent != bucket.
end())
854 if (key_equal_function(icurrent->key_value_pair.first, key))
856 delete_data_node(iprevious, icurrent, bucket);
858 icurrent = iprevious;
878 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
881 bucket_t& bucket = ielement.get_bucket();
886 while (iprevious->etl_next != &*icurrent)
891 delete_data_node(iprevious, icurrent, bucket);
906 if ((first_ ==
begin()) && (last_ ==
end()))
913 bucket_t* pbucket = first_.get_bucket_list_iterator();
914 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
920 while (iprevious->etl_next != &*icurrent)
926 iterator ibefore_erased =
iterator((pbuckets + number_of_buckets), pbucket, iprevious);
929 while ((icurrent != iend) || (pbucket != pend_bucket))
931 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
934 if ((icurrent != iend) || (pbucket != pend_bucket))
937 if ((icurrent == pbucket->
end()))
943 }
while (pbucket->
empty());
946 icurrent = pbucket->
begin();
951 return ++ibefore_erased;
967 size_t count(const_key_reference key)
const
978 while ((l !=
end()) && key_equal_function(key, l->first))
997 bucket_t* pbucket = pbuckets + index;
1001 if (!bucket.
empty())
1007 while (inode != iend)
1010 if (key_equal_function(key, inode->key_value_pair.first))
1012 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1031 bucket_t* pbucket = pbuckets + index;
1035 if (!bucket.
empty())
1041 while (inode != iend)
1044 if (key_equal_function(key, inode->key_value_pair.first))
1046 return const_iterator((pbuckets + number_of_buckets), pbucket, inode);
1064 ETL_OR_STD::pair<iterator, iterator>
equal_range(const_key_reference key)
1073 while ((l !=
end()) && key_equal_function(key, l->first))
1079 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1090 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(const_key_reference key)
const
1099 while ((l !=
end()) && key_equal_function(key, l->first))
1105 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1113 return pnodepool->
size();
1137 return pnodepool->
empty();
1145 return pnodepool->
full();
1172 return key_hash_function;
1181 return key_equal_function;
1193 key_equal_function = rhs.
key_eq();
1210 key_hash_function = rhs.hash_function();
1211 key_equal_function = rhs.key_eq();
1212 move(rhs.begin(), rhs.end());
1225 : pnodepool(&node_pool_)
1226 , pbuckets(pbuckets_)
1227 , number_of_buckets(number_of_buckets_)
1230 , key_hash_function(key_hash_function_)
1231 , key_equal_function(key_equal_function_)
1243 for (
size_t i = 0UL; i < number_of_buckets; ++i)
1247 if (!bucket.
empty())
1252 while (it != bucket.
end())
1255 it->key_value_pair.~value_type();
1257 ETL_DECREMENT_DEBUG_COUNT
1279 while (first != last)
1283 insert(etl::move(*first));
1294 node_t& allocate_data_node()
1296 node_t* (
etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1297 return *(pnodepool->*func)();
1303 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1312 if (pbucket < first)
1316 else if (pbucket > last)
1326 void adjust_first_last_markers_after_erase(bucket_t* pcurrent)
1335 if (pcurrent == first)
1338 while (first->empty())
1343 else if (pcurrent == last)
1346 bucket_t* pcurrent = first;
1347 bucket_t* pend = last;
1351 while (pcurrent != pend)
1353 if (!pcurrent->empty())
1367 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1369 local_iterator inext = bucket.erase_after(iprevious);
1370 icurrent->key_value_pair.~value_type();
1371 pnodepool->
release(&*icurrent);
1372 adjust_first_last_markers_after_erase(&bucket);
1373 ETL_DECREMENT_DEBUG_COUNT
1388 const size_t number_of_buckets;
1395 hasher key_hash_function;
1398 key_equal key_equal_function;
1401 ETL_DECLARE_DEBUG_COUNT
1406#if defined(ETL_POLYMORPHIC_UNORDERED_MULTIMAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
1426 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
1429 const bool sizes_match = (lhs.
size() == rhs.
size());
1430 bool elements_match =
true;
1434 for (
size_t i = 0; (i < lhs.
bucket_count()) && elements_match; ++i)
1438 elements_match =
false;
1443 return (sizes_match && elements_match);
1453 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
1456 return !(lhs == rhs);
1462 template <
typename TKey,
typename TValue, const
size_t MAX_SIZE_, const
size_t MAX_BUCKETS_ = MAX_SIZE_,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey> >
1471 static ETL_CONSTANT
size_t MAX_SIZE = MAX_SIZE_;
1472 static ETL_CONSTANT
size_t MAX_BUCKETS = MAX_BUCKETS_;
1478 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1505 base::move(other.begin(), other.end());
1516 template <
typename TIterator>
1517 unordered_multimap(TIterator first_, TIterator last_,
const THash& hash = THash(),
const TKeyEqual& equal = TKeyEqual())
1518 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1520 base::assign(first_, last_);
1523#if ETL_HAS_INITIALIZER_LIST
1527 unordered_multimap(std::initializer_list<ETL_OR_STD::pair<TKey, TValue>> init,
const THash& hash = THash(),
const TKeyEqual& equal = TKeyEqual())
1528 : base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
1530 base::assign(init.begin(), init.end());
1547 base::operator=(rhs);
1558 base::operator=(etl::move(rhs));
1570 typename base::bucket_t buckets[MAX_BUCKETS_];
1576#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1577 template <
typename... TPairs>
1578 unordered_multimap(TPairs...) -> unordered_multimap<
typename etl::nth_type_t<0, TPairs...>::first_type,
1579 typename etl::nth_type_t<0, TPairs...>::second_type,
1586#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1587 template <
typename TKey,
typename T,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey>,
typename... TPairs>
1588 constexpr auto make_unordered_multimap(TPairs&&... pairs) ->
etl::unordered_multimap<TKey, T,
sizeof...(TPairs),
sizeof...(TPairs), THash, TKeyEqual>
1590 return { {etl::forward<TPairs>(pairs)...} };
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_multimap.h:331
Definition: unordered_multimap.h:188
A templated unordered_multimap implementation that uses a fixed size buffer.
Definition: unordered_multimap.h:1464
unordered_multimap(const unordered_multimap &other)
Copy constructor.
Definition: unordered_multimap.h:1485
unordered_multimap(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition: unordered_multimap.h:1517
unordered_multimap(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition: unordered_multimap.h:1477
~unordered_multimap()
Destructor.
Definition: unordered_multimap.h:1537
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
iterator end()
Definition: unordered_multimap.h:541
iunordered_multimap & operator=(const iunordered_multimap &rhs)
Assignment operator.
Definition: unordered_multimap.h:1187
const_local_iterator cend(size_t i) const
Definition: unordered_multimap.h:586
const_local_iterator cbegin(size_t i) const
Definition: unordered_multimap.h:532
float load_factor() const
Definition: unordered_multimap.h:1161
void assign(TIterator first_, TIterator last_)
Definition: unordered_multimap.h:637
size_t available() const
Definition: unordered_multimap.h:1152
const_local_iterator end(size_t i) const
Definition: unordered_multimap.h:577
key_equal key_eq() const
Definition: unordered_multimap.h:1179
const_iterator find(const_key_reference key) const
Definition: unordered_multimap.h:1027
bool empty() const
Checks to see if the unordered_multimap is empty.
Definition: unordered_multimap.h:1135
size_type bucket_count() const
Definition: unordered_multimap.h:624
iterator insert(const_reference key_value_pair)
Definition: unordered_multimap.h:659
iterator erase(const_iterator ielement)
Definition: unordered_multimap.h:875
local_iterator end(size_t i)
Definition: unordered_multimap.h:568
size_type capacity() const
Gets the maximum possible size of the unordered_multimap.
Definition: unordered_multimap.h:1127
const_local_iterator begin(size_t i) const
Definition: unordered_multimap.h:523
void initialise()
Initialise the unordered_multimap.
Definition: unordered_multimap.h:1238
const_iterator end() const
Definition: unordered_multimap.h:550
size_t count(const_key_reference key) const
Definition: unordered_multimap.h:967
iterator find(const_key_reference key)
Definition: unordered_multimap.h:993
size_type size() const
Gets the size of the unordered_multimap.
Definition: unordered_multimap.h:1111
void clear()
Clears the unordered_multimap.
Definition: unordered_multimap.h:957
const_iterator begin() const
Definition: unordered_multimap.h:496
hasher hash_function() const
Definition: unordered_multimap.h:1170
iterator erase(const_iterator first_, const_iterator last_)
Definition: unordered_multimap.h:903
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition: unordered_multimap.h:1090
iterator insert(const_iterator, const_reference key_value_pair)
Definition: unordered_multimap.h:802
size_type max_size() const
Gets the maximum possible size of the unordered_multimap.
Definition: unordered_multimap.h:1119
const_iterator cbegin() const
Definition: unordered_multimap.h:505
local_iterator begin(size_t i)
Definition: unordered_multimap.h:514
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition: unordered_multimap.h:1064
~iunordered_multimap()
For library debugging purposes only.
Definition: unordered_multimap.h:1413
iunordered_multimap(pool_t &node_pool_, bucket_t *pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
Constructor.
Definition: unordered_multimap.h:1224
size_type bucket_size(const_key_reference key) const
Definition: unordered_multimap.h:604
size_type max_bucket_count() const
Definition: unordered_multimap.h:615
const_iterator cend() const
Definition: unordered_multimap.h:559
void insert(TIterator first_, TIterator last_)
Definition: unordered_multimap.h:828
bool full() const
Checks to see if the unordered_multimap is full.
Definition: unordered_multimap.h:1143
size_t erase(const_key_reference key)
Definition: unordered_multimap.h:842
size_type get_bucket_index(const_key_reference key) const
Definition: unordered_multimap.h:595
iterator begin()
Definition: unordered_multimap.h:487
Definition: unordered_multimap.h:127
Definition: unordered_multimap.h:70
Definition: unordered_multimap.h:84
Definition: unordered_multimap.h:111
Definition: unordered_multimap.h:98
bool operator==(const etl::iunordered_multimap< TKey, TMapped, TKeyCompare > &lhs, const etl::iunordered_multimap< TKey, TMapped, TKeyCompare > &rhs)
Definition: unordered_multimap.h:1427
bool operator!=(const etl::iunordered_multimap< TKey, TMapped, TKeyCompare > &lhs, const etl::iunordered_multimap< TKey, TMapped, TKeyCompare > &rhs)
Definition: unordered_multimap.h:1454
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_multimap.h:155