31#ifndef ETL_UNORDERED_MULTIMAP_INCLUDED
32#define ETL_UNORDERED_MULTIMAP_INCLUDED
127 template <
typename TKey,
typename T,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey> >
132 typedef ETL_OR_STD::pair<const TKey, T> value_type;
138 typedef value_type& reference;
139 typedef const value_type& const_reference;
143 typedef value_type* pointer;
144 typedef const value_type* const_pointer;
163 value_type key_value_pair;
185 typedef typename bucket_t::iterator local_iterator;
186 typedef typename bucket_t::const_iterator const_local_iterator;
198 typedef typename iunordered_multimap::reference reference;
199 typedef typename iunordered_multimap::const_reference const_reference;
200 typedef typename iunordered_multimap::pointer pointer;
201 typedef typename iunordered_multimap::const_pointer const_pointer;
214 : pbuckets_end(
other.pbuckets_end)
215 , pbucket(
other.pbucket)
226 if (inode == pbucket->end())
230 while ((pbucket != pbuckets_end) && (pbucket->empty()))
236 if (pbucket != pbuckets_end)
238 inode = pbucket->begin();
256 pbuckets_end =
other.pbuckets_end;
257 pbucket =
other.pbucket;
265 return inode->key_value_pair;
271 return &(inode->key_value_pair);
277 return &(inode->key_value_pair);
305 return rhs.inode == inode;
315 bucket_t*& get_bucket_list_iterator()
321 local_iterator get_local_iterator()
328 local_iterator inode;
341 typedef typename iunordered_multimap::reference reference;
342 typedef typename iunordered_multimap::const_reference const_reference;
343 typedef typename iunordered_multimap::pointer pointer;
344 typedef typename iunordered_multimap::const_pointer const_pointer;
357 : pbuckets_end(
other.pbuckets_end)
358 , pbucket(
other.pbucket)
365 : pbuckets_end(
other.pbuckets_end)
366 , pbucket(
other.pbucket)
377 if (inode == pbucket->end())
382 while ((pbucket != pbuckets_end) && (pbucket->empty()))
388 if (pbucket != pbuckets_end)
390 inode = pbucket->begin();
408 pbuckets_end =
other.pbuckets_end;
409 pbucket =
other.pbucket;
417 return inode->key_value_pair;
423 return &(inode->key_value_pair);
429 return &(inode->key_value_pair);
457 return rhs.inode == inode;
467 bucket_t*& get_bucket_list_iterator()
473 local_iterator get_local_iterator()
480 local_iterator inode;
483 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
491 return iterator((pbuckets + number_of_buckets), first, first->begin());
500 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
509 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
518 return pbuckets[
i].begin();
525 const_local_iterator
begin(
size_t i)
const
527 return pbuckets[
i].cbegin();
536 return pbuckets[
i].cbegin();
545 return iterator((pbuckets + number_of_buckets), last, last->end());
554 return const_iterator((pbuckets + number_of_buckets), last, last->end());
563 return const_iterator((pbuckets + number_of_buckets), last, last->end());
572 return pbuckets[
i].end();
579 const_local_iterator
end(
size_t i)
const
581 return pbuckets[
i].cend();
588 const_local_iterator
cend(
size_t i)
const
590 return pbuckets[
i].cend();
599 return key_hash_function(key) % number_of_buckets;
610 return key_hash_function(key) % number_of_buckets;
620 size_t index =
bucket(key);
622 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
633 size_t index =
bucket(key);
635 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
645 return number_of_buckets;
654 return number_of_buckets;
664 template <
typename TIterator>
667#if ETL_IS_DEBUG_BUILD
699 bucket_t* pbucket = pbuckets + index;
708 ::new (&
node->key_value_pair) value_type(key_value_pair);
709 ETL_INCREMENT_DEBUG_COUNT;
713 adjust_first_last_markers_after_insert(pbucket);
715 result =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
721 local_iterator inode =
bucket.begin();
723 while (inode !=
bucket.end())
726 if (key_equal_function(inode->key_value_pair.first, key))
738 ::new (&
node->key_value_pair) value_type(key_value_pair);
739 ETL_INCREMENT_DEBUG_COUNT;
743 adjust_first_last_markers_after_insert(&
bucket);
764 const_key_reference key = key_value_pair.
first;
770 bucket_t* pbucket = pbuckets + index;
771 bucket_t&
bucket = *pbucket;
777 node_t*
node = allocate_data_node();
779 ::new (&
node->key_value_pair) value_type(
etl::move(key_value_pair));
780 ETL_INCREMENT_DEBUG_COUNT;
784 adjust_first_last_markers_after_insert(pbucket);
786 result =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->
begin());
792 local_iterator inode =
bucket.begin();
794 while (inode !=
bucket.end())
797 if (key_equal_function(inode->key_value_pair.first, key))
807 node_t* node = allocate_data_node();
809 ::new (&node->key_value_pair) value_type(
etl::move(key_value_pair));
810 ETL_INCREMENT_DEBUG_COUNT;
813 bucket.insert_after(inode_previous, *node);
814 adjust_first_last_markers_after_insert(&bucket);
817 result = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
832 return insert(key_value_pair);
844 return insert(etl::move(key_value_pair));
855 template <
class TIterator>
906 size_t erase(
const K& key)
980 local_iterator
iprevious = pbucket->before_begin();
982 local_iterator
iend =
last_.get_local_iterator();
1008 }
while (pbucket->empty());
1043 while ((
l !=
end()) && key_equal_function(key,
l->
first))
1060 size_t count(
const K& key)
const
1063 const_iterator
f =
find(key);
1064 const_iterator
l =
f;
1071 while ((
l !=
end()) && key_equal_function(key,
l->
first))
1091 bucket_t* pbucket = pbuckets + index;
1098 local_iterator inode =
bucket.begin();
1101 while (inode !=
iend)
1104 if (key_equal_function(key, inode->key_value_pair.
first))
1106 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1125 bucket_t* pbucket = pbuckets + index;
1132 local_iterator inode =
bucket.begin();
1135 while (inode !=
iend)
1138 if (key_equal_function(key, inode->key_value_pair.
first))
1140 return const_iterator((pbuckets + number_of_buckets), pbucket, inode);
1161 bucket_t* pbucket = pbuckets + index;
1162 bucket_t&
bucket = *pbucket;
1168 local_iterator inode =
bucket.begin();
1171 while (inode !=
iend)
1174 if (key_equal_function(key, inode->key_value_pair.first))
1176 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1193 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value,
int> = 0>
1194 const_iterator
find(
const K& key)
const
1198 bucket_t* pbucket = pbuckets + index;
1199 bucket_t& bucket = *pbucket;
1202 if (!bucket.empty())
1205 local_iterator inode = bucket.begin();
1206 local_iterator iend = bucket.end();
1208 while (inode != iend)
1211 if (key_equal_function(key, inode->key_value_pair.first))
1213 return const_iterator((pbuckets + number_of_buckets), pbucket, inode);
1241 while ((
l !=
end()) && key_equal_function(key,
l->
first))
1247 return ETL_OR_STD::pair<iterator, iterator>(
f,
l);
1267 while ((
l !=
end()) && key_equal_function(key,
l->
first))
1273 return ETL_OR_STD::pair<const_iterator, const_iterator>(
f,
l);
1286 ETL_OR_STD::pair<iterator, iterator>
equal_range(
const K& key)
1295 while ((
l !=
end()) && key_equal_function(key,
l->
first))
1301 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1314 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value,
int> = 0>
1315 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(
const K& key)
const
1317 const_iterator f =
find(key);
1318 const_iterator l = f;
1324 while ((l !=
end()) && key_equal_function(key, l->first))
1330 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1339 return pnodepool->
size();
1363 return pnodepool->
empty();
1371 return pnodepool->
full();
1398 return key_hash_function;
1407 return key_equal_function;
1418 key_hash_function =
rhs.hash_function();
1419 key_equal_function =
rhs.key_eq();
1436 key_hash_function =
rhs.hash_function();
1437 key_equal_function =
rhs.key_eq();
1438 move(
rhs.begin(),
rhs.end());
1488 for (
size_t i = 0
UL;
i < number_of_buckets; ++
i)
1495 local_iterator it =
bucket.begin();
1497 while (it !=
bucket.end())
1500 it->key_value_pair.~value_type();
1502 ETL_DECREMENT_DEBUG_COUNT;
1539 node_t* allocate_data_node()
1541 node_t* (
etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1542 return (pnodepool->*func)();
1548 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1557 if (pbucket < first)
1561 else if (pbucket > last)
1571 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1580 if (pbucket == first)
1583 while (first->empty())
1588 else if (pbucket == last)
1592 bucket_t* pend = last;
1596 while (pbucket != pend)
1598 if (!pbucket->empty())
1612 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1614 local_iterator inext = bucket.erase_after(iprevious);
1615 icurrent->key_value_pair.~value_type();
1616 pnodepool->
release(&*icurrent);
1617 adjust_first_last_markers_after_erase(&bucket);
1618 ETL_DECREMENT_DEBUG_COUNT;
1633 const size_t number_of_buckets;
1640 hasher key_hash_function;
1643 key_equal key_equal_function;
1646 ETL_DECLARE_DEBUG_COUNT;
1651#if defined(ETL_POLYMORPHIC_UNORDERED_MULTIMAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
1671 template <
typename TKey,
typename T,
typename THash,
typename TKeyEqual>
1691 ETL_OR_STD::pair<itr_t, itr_t>
l_range =
lhs.equal_range(key);
1692 ETL_OR_STD::pair<itr_t, itr_t>
r_range =
rhs.equal_range(key);
1726 template <
typename TKey,
typename T,
typename THash,
typename TKeyEqual>
1736 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> >
1745 static ETL_CONSTANT
size_t MAX_SIZE =
MAX_SIZE_;
1752 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1760 :
base(node_pool, buckets, MAX_BUCKETS,
other.hash_function(),
other.key_eq())
1774 : base(node_pool, buckets, MAX_BUCKETS,
other.hash_function(),
other.key_eq())
1790 template <
typename TIterator>
1792 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1797#if ETL_HAS_INITIALIZER_LIST
1804 base::assign(
init.begin(),
init.end());
1821 base::operator=(
rhs);
1832 base::operator=(etl::move(
rhs));
1844 typename base::bucket_t buckets[MAX_BUCKETS_];
1850#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1851 template <
typename... TPairs>
1852 unordered_multimap(TPairs...) -> unordered_multimap<
typename etl::nth_type_t<0, TPairs...>::first_type,
1860#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1861 template <
typename TKey,
typename T,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey>,
typename... TPairs>
1862 constexpr auto make_unordered_multimap(TPairs&&... pairs) ->
etl::unordered_multimap<TKey, T,
sizeof...(TPairs),
sizeof...(TPairs), THash, TKeyEqual>
Definition unordered_multimap.h:333
Definition unordered_multimap.h:190
A templated unordered_multimap implementation that uses a fixed size buffer.
Definition unordered_multimap.h:1738
unordered_multimap(const unordered_multimap &other)
Copy constructor.
Definition unordered_multimap.h:1759
unordered_multimap(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_multimap.h:1791
unordered_multimap(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_multimap.h:1751
~unordered_multimap()
Destructor.
Definition unordered_multimap.h:1811
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:968
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition algorithm.h:1739
#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
iterator end()
Definition unordered_multimap.h:543
iunordered_multimap & operator=(const iunordered_multimap &rhs)
Assignment operator.
Definition unordered_multimap.h:1413
const_local_iterator cend(size_t i) const
Definition unordered_multimap.h:588
const_local_iterator cbegin(size_t i) const
Definition unordered_multimap.h:534
float load_factor() const
Definition unordered_multimap.h:1387
void assign(TIterator first_, TIterator last_)
Definition unordered_multimap.h:665
size_t available() const
Definition unordered_multimap.h:1378
const_local_iterator end(size_t i) const
Definition unordered_multimap.h:579
key_equal key_eq() const
Definition unordered_multimap.h:1405
const_iterator find(const_key_reference key) const
Definition unordered_multimap.h:1121
bool contains(const_key_reference key) const
Check if the unordered_multimap contains the key.
Definition unordered_multimap.h:1448
bool empty() const
Checks to see if the unordered_multimap is empty.
Definition unordered_multimap.h:1361
size_type bucket_count() const
Definition unordered_multimap.h:652
iterator insert(const_reference key_value_pair)
Definition unordered_multimap.h:687
iterator erase(const_iterator ielement)
Definition unordered_multimap.h:940
local_iterator end(size_t i)
Definition unordered_multimap.h:570
size_type capacity() const
Gets the maximum possible size of the unordered_multimap.
Definition unordered_multimap.h:1353
const_local_iterator begin(size_t i) const
Definition unordered_multimap.h:525
void initialise()
Initialise the unordered_multimap.
Definition unordered_multimap.h:1483
const_iterator end() const
Definition unordered_multimap.h:552
size_t count(const_key_reference key) const
Definition unordered_multimap.h:1032
iterator find(const_key_reference key)
Definition unordered_multimap.h:1087
size_type size() const
Gets the size of the unordered_multimap.
Definition unordered_multimap.h:1337
void clear()
Clears the unordered_multimap.
Definition unordered_multimap.h:1022
const_iterator begin() const
Definition unordered_multimap.h:498
hasher hash_function() const
Definition unordered_multimap.h:1396
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_multimap.h:968
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition unordered_multimap.h:1258
iterator insert(const_iterator, const_reference key_value_pair)
Definition unordered_multimap.h:830
size_type max_size() const
Gets the maximum possible size of the unordered_multimap.
Definition unordered_multimap.h:1345
const_iterator cbegin() const
Definition unordered_multimap.h:507
local_iterator begin(size_t i)
Definition unordered_multimap.h:516
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition unordered_multimap.h:1232
~iunordered_multimap()
Destructor.
Definition unordered_multimap.h:1658
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:1469
size_type bucket_size(const_key_reference key) const
Definition unordered_multimap.h:618
size_type max_bucket_count() const
Definition unordered_multimap.h:643
const_iterator cend() const
Definition unordered_multimap.h:561
void insert(TIterator first_, TIterator last_)
Definition unordered_multimap.h:856
bool full() const
Checks to see if the unordered_multimap is full.
Definition unordered_multimap.h:1369
size_t erase(const_key_reference key)
Definition unordered_multimap.h:870
size_type get_bucket_index(const_key_reference key) const
Definition unordered_multimap.h:597
iterator begin()
Definition unordered_multimap.h:489
Definition unordered_multimap.h:129
Definition unordered_multimap.h:72
Definition unordered_multimap.h:86
Definition unordered_multimap.h:113
Definition unordered_multimap.h:100
bitset_ext
Definition absolute.h:38
A forward link.
Definition intrusive_links.h:88
iterator
Definition iterator.h:399
Definition unordered_multimap.h:157
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