31#ifndef ETL_UNORDERED_MAP_INCLUDED
32#define ETL_UNORDERED_MAP_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;
148 typedef key_type&& rvalue_key_reference;
150 typedef mapped_type& mapped_reference;
151 typedef const mapped_type& const_mapped_reference;
159 node_t(const_reference key_value_pair_)
160 : key_value_pair(key_value_pair_)
164 value_type key_value_pair;
167 friend bool operator ==(
const node_t& lhs,
const node_t& rhs)
169 return (lhs.key_value_pair.first == rhs.key_value_pair.first) &&
170 (lhs.key_value_pair.second == rhs.key_value_pair.second);
173 friend bool operator !=(
const node_t& lhs,
const node_t& rhs)
175 return !(lhs == rhs);
186 typedef typename bucket_t::iterator local_iterator;
187 typedef typename bucket_t::const_iterator const_local_iterator;
194 typedef typename etl::iterator<ETL_OR_STD::forward_iterator_tag, T>::value_type value_type;
195 typedef typename iunordered_map::key_type key_type;
196 typedef typename iunordered_map::mapped_type mapped_type;
197 typedef typename iunordered_map::hasher hasher;
198 typedef typename iunordered_map::key_equal key_equal;
199 typedef typename iunordered_map::reference reference;
200 typedef typename iunordered_map::const_reference const_reference;
201 typedef typename iunordered_map::pointer pointer;
202 typedef typename iunordered_map::const_pointer const_pointer;
203 typedef typename iunordered_map::size_type size_type;
215 : pbuckets_end(other.pbuckets_end)
216 , pbucket(other.pbucket)
227 if (inode == pbucket->
end())
231 while ((pbucket != pbuckets_end) && (pbucket->
empty()))
237 if (pbucket != pbuckets_end)
239 inode = pbucket->
begin();
257 pbuckets_end = other.pbuckets_end;
258 pbucket = other.pbucket;
264 reference operator *()
const
266 return inode->key_value_pair;
272 return &(inode->key_value_pair);
276 pointer operator ->()
const
278 return &(inode->key_value_pair);
284 return lhs.compare(rhs);
290 return !(lhs == rhs);
297 : pbuckets_end(pbuckets_end_)
306 return rhs.inode == inode;
316 bucket_t* get_bucket_list_iterator()
337 typedef typename etl::iterator<ETL_OR_STD::forward_iterator_tag, const T>::value_type value_type;
338 typedef typename iunordered_map::key_type key_type;
339 typedef typename iunordered_map::mapped_type mapped_type;
340 typedef typename iunordered_map::hasher hasher;
341 typedef typename iunordered_map::key_equal key_equal;
342 typedef typename iunordered_map::reference reference;
343 typedef typename iunordered_map::const_reference const_reference;
344 typedef typename iunordered_map::pointer pointer;
345 typedef typename iunordered_map::const_pointer const_pointer;
346 typedef typename iunordered_map::size_type size_type;
358 : pbuckets_end(other.pbuckets_end)
359 , pbucket(other.pbucket)
366 : pbuckets_end(other.pbuckets_end)
367 , pbucket(other.pbucket)
378 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;
415 const_reference operator *()
const
417 return inode->key_value_pair;
423 return &(inode->key_value_pair);
427 const_pointer operator ->()
const
429 return &(inode->key_value_pair);
435 return lhs.compare(rhs);
441 return !(lhs == rhs);
448 : pbuckets_end(pbuckets_end_)
457 return rhs.inode == inode;
467 bucket_t* get_bucket_list_iterator()
483 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
491 return iterator((pbuckets + number_of_buckets), first, first->
begin());
518 return pbuckets[i].
begin();
527 return pbuckets[i].
cbegin();
536 return pbuckets[i].
cbegin();
545 return iterator((pbuckets + number_of_buckets), last, last->
end());
572 return pbuckets[i].
end();
581 return pbuckets[i].
cend();
590 return pbuckets[i].
cend();
599 return key_hash_function(key) % number_of_buckets;
608 size_t index = bucket(key);
610 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
619 return number_of_buckets;
628 return number_of_buckets;
637 mapped_reference
operator [](rvalue_key_reference key)
643 local_iterator inode = pbucket->begin();
646 while (inode != pbucket->end())
649 if (key_equal_function(key, inode->key_value_pair.first))
652 return inode->key_value_pair.second;
662 node_t& node = allocate_data_node();
664 ::new ((
void*)
etl::addressof(node.key_value_pair.first)) key_type(
etl::move(key));
665 ::new ((
void*)
etl::
addressof(node.key_value_pair.second)) mapped_type();
666 ETL_INCREMENT_DEBUG_COUNT
668 pbucket->insert_after(pbucket->before_begin(), node);
670 adjust_first_last_markers_after_insert(pbucket);
672 return pbucket->
begin()->key_value_pair.second;
690 while (inode != pbucket->
end())
693 if (key_equal_function(key, inode->key_value_pair.first))
696 return inode->key_value_pair.second;
706 node_t& node = allocate_data_node();
708 ::new ((
void*)
etl::addressof(node.key_value_pair.first)) key_type(key);
709 ::new ((
void*)
etl::addressof(node.key_value_pair.second)) mapped_type();
710 ETL_INCREMENT_DEBUG_COUNT
714 adjust_first_last_markers_after_insert(pbucket);
716 return pbucket->
begin()->key_value_pair.second;
734 while (inode != pbucket->
end())
737 if (key_equal_function(key, inode->key_value_pair.first))
740 return inode->key_value_pair.second;
751 return begin()->second;
769 while (inode != pbucket->
end())
772 if (key_equal_function(key, inode->key_value_pair.first))
775 return inode->key_value_pair.second;
786 return begin()->second;
796 template <
typename TIterator>
797 void assign(TIterator first_, TIterator last_)
799#if ETL_IS_DEBUG_BUILD
800 difference_type d = etl::distance(first_, last_);
807 while (first_ != last_)
819 ETL_OR_STD::pair<iterator, bool>
insert(const_reference key_value_pair)
821 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
825 const key_type& key = key_value_pair.first;
831 bucket_t* pbucket = pbuckets + index;
838 node_t& node = allocate_data_node();
840 ::new ((
void*)
etl::addressof(node.key_value_pair)) value_type(key_value_pair);
841 ETL_INCREMENT_DEBUG_COUNT
846 adjust_first_last_markers_after_insert(pbucket);
848 result.first =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->
begin());
849 result.second =
true;
857 while (inode != bucket.
end())
860 if (key_equal_function(inode->key_value_pair.first, key))
870 if (inode == bucket.
end())
873 node_t& node = allocate_data_node();
875 ::new ((
void*)
etl::addressof(node.key_value_pair)) value_type(key_value_pair);
876 ETL_INCREMENT_DEBUG_COUNT
880 adjust_first_last_markers_after_insert(&bucket);
883 result.first =
iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
884 result.second =
true;
897 ETL_OR_STD::pair<iterator, bool>
insert(rvalue_reference key_value_pair)
899 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
903 const key_type& key = key_value_pair.first;
909 bucket_t* pbucket = pbuckets + index;
910 bucket_t& bucket = *pbucket;
916 node_t& node = allocate_data_node();
918 ::new ((
void*)
etl::addressof(node.key_value_pair)) value_type(
etl::move(key_value_pair));
919 ETL_INCREMENT_DEBUG_COUNT
922 bucket.insert_after(bucket.before_begin(), node);
924 adjust_first_last_markers_after_insert(pbucket);
926 result.first =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->
begin());
927 result.second = true;
932 local_iterator inode_previous = bucket.before_begin();
933 local_iterator inode = bucket.begin();
935 while (inode != bucket.end())
938 if (key_equal_function(inode->key_value_pair.first, key))
948 if (inode == bucket.end())
951 node_t& node = allocate_data_node();
953 ::new ((
void*)
etl::addressof(node.key_value_pair)) value_type(
etl::move(key_value_pair));
954 ETL_INCREMENT_DEBUG_COUNT
957 bucket.insert_after(inode_previous, node);
958 adjust_first_last_markers_after_insert(&bucket);
961 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
962 result.second = true;
978 return insert(key_value_pair).first;
990 return insert(etl::move(key_value_pair)).first;
1001 template <
class TIterator>
1002 void insert(TIterator first_, TIterator last_)
1004 while (first_ != last_)
1021 bucket_t& bucket = pbuckets[index];
1027 while ((icurrent != bucket.
end()) && (!key_equal_function(icurrent->key_value_pair.first, key)))
1034 if (icurrent != bucket.
end())
1036 delete_data_node(iprevious, icurrent, bucket);
1050 iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
1053 bucket_t& bucket = ielement.get_bucket();
1058 while (iprevious->etl_next != &*icurrent)
1063 delete_data_node(iprevious, icurrent, bucket);
1078 if ((first_ ==
begin()) && (last_ ==
end()))
1085 bucket_t* pbucket = first_.get_bucket_list_iterator();
1086 bucket_t* pend_bucket = last_.get_bucket_list_iterator();
1092 while (iprevious->etl_next != &*icurrent)
1098 iterator ibefore_erased =
iterator((pbuckets + number_of_buckets), pbucket, iprevious);
1101 while ((icurrent != iend) || (pbucket != pend_bucket))
1103 icurrent = delete_data_node(iprevious, icurrent, *pbucket);
1106 if ((icurrent != iend) || (pbucket != pend_bucket))
1109 if ((icurrent == pbucket->
end()))
1115 }
while (pbucket->
empty());
1118 icurrent = pbucket->
begin();
1123 return ++ibefore_erased;
1141 return (
find(key) ==
end()) ? 0 : 1;
1153 bucket_t* pbucket = pbuckets + index;
1157 if (!bucket.
empty())
1163 while (inode != iend)
1166 if (key_equal_function(key, inode->key_value_pair.first))
1168 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1187 bucket_t* pbucket = pbuckets + index;
1191 if (!bucket.
empty())
1197 while (inode != iend)
1200 if (key_equal_function(key, inode->key_value_pair.first))
1202 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1230 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1251 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1259 return pnodepool->
size();
1283 return pnodepool->
empty();
1291 return pnodepool->
full();
1318 return key_hash_function;
1327 return key_equal_function;
1339 key_equal_function = rhs.
key_eq();
1355 key_hash_function = rhs.hash_function();
1356 key_equal_function = rhs.key_eq();
1357 this->move(rhs.begin(), rhs.end());
1370 : pnodepool(&node_pool_)
1371 , pbuckets(pbuckets_)
1372 , number_of_buckets(number_of_buckets_)
1375 , key_hash_function(key_hash_function_)
1376 , key_equal_function(key_equal_function_)
1388 for (
size_t i = 0UL; i < number_of_buckets; ++i)
1392 if (!bucket.
empty())
1397 while (it != bucket.
end())
1400 it->key_value_pair.~value_type();
1401 ETL_DECREMENT_DEBUG_COUNT
1425 while (first != last)
1429 insert(etl::move(*first));
1440 node_t& allocate_data_node()
1442 node_t* (
etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1443 return *(pnodepool->*func)();
1449 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1458 if (pbucket < first)
1462 else if (pbucket > last)
1472 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1481 if (pbucket == first)
1484 while (first->empty())
1489 else if (pbucket == last)
1492 bucket_t* pcurrent = first;
1493 bucket_t* pend = last;
1497 while (pcurrent != pend)
1499 if (!pcurrent->empty())
1513 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1515 local_iterator inext = bucket.erase_after(iprevious);
1516 icurrent->key_value_pair.~value_type();
1517 pnodepool->
release(&*icurrent);
1518 adjust_first_last_markers_after_erase(&bucket);
1519 ETL_DECREMENT_DEBUG_COUNT
1534 const size_t number_of_buckets;
1541 hasher key_hash_function;
1544 key_equal key_equal_function;
1547 ETL_DECLARE_DEBUG_COUNT
1552#if defined(ETL_POLYMORPHIC_UNORDERED_MAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
1572 template <
typename TKey,
typename T,
typename TKeyCompare>
1575 const bool sizes_match = (lhs.
size() == rhs.
size());
1576 bool elements_match =
true;
1580 for (
size_t i = 0; (i < lhs.
bucket_count()) && elements_match; ++i)
1584 elements_match =
false;
1589 return (sizes_match && elements_match);
1599 template <
typename TKey,
typename T,
typename TKeyCompare>
1602 return !(lhs == rhs);
1608 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> >
1617 static ETL_CONSTANT
size_t MAX_SIZE = MAX_SIZE_;
1618 static ETL_CONSTANT
size_t MAX_BUCKETS = MAX_BUCKETS_;
1623 unordered_map(
const THash& hash = THash(),
const TKeyEqual& equal = TKeyEqual())
1624 :
base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
1646 base::move(other.begin(), other.end());
1657 template <
typename TIterator>
1658 unordered_map(TIterator first_, TIterator last_,
const THash& hash = THash(),
const TKeyEqual& equal = TKeyEqual())
1659 :
base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
1661 base::assign(first_, last_);
1664#if ETL_HAS_INITIALIZER_LIST
1668 unordered_map(std::initializer_list<ETL_OR_STD::pair<TKey, TValue>> init,
const THash& hash = THash(),
const TKeyEqual& equal = TKeyEqual())
1669 : base(node_pool, buckets, MAX_BUCKETS_, hash, equal)
1671 base::assign(init.begin(), init.end());
1688 base::operator=(rhs);
1698 base::operator=(etl::move(rhs));
1709 typename base::bucket_t buckets[MAX_BUCKETS_];
1715#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1716 template <
typename... TPairs>
1717 unordered_map(TPairs...) -> unordered_map<
typename etl::nth_type_t<0, TPairs...>::first_type,
1718 typename etl::nth_type_t<0, TPairs...>::second_type,
1725#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1726 template <
typename TKey,
typename T,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey>,
typename... TPairs>
1727 constexpr auto make_unordered_map(TPairs&&... pairs) ->
etl::unordered_map<TKey, T,
sizeof...(TPairs),
sizeof...(TPairs), THash, TKeyEqual>
1729 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_map.h:334
Definition: unordered_map.h:191
A templated unordered_map implementation that uses a fixed size buffer.
Definition: unordered_map.h:1610
unordered_map(const unordered_map &other)
Copy constructor.
Definition: unordered_map.h:1631
unordered_map(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition: unordered_map.h:1623
~unordered_map()
Destructor.
Definition: unordered_map.h:1678
unordered_map(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition: unordered_map.h:1658
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
ETL_CONSTEXPR17 T * addressof(T &t)
Definition: addressof.h:51
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
float load_factor() const
Definition: unordered_map.h:1307
iterator erase(const_iterator first_, const_iterator last_)
Definition: unordered_map.h:1075
size_type get_bucket_index(const_key_reference key) const
Definition: unordered_map.h:597
iterator begin()
Definition: unordered_map.h:489
void initialise()
Initialise the unordered_map.
Definition: unordered_map.h:1383
const_iterator find(const_key_reference key) const
Definition: unordered_map.h:1183
size_type size() const
Gets the size of the unordered_map.
Definition: unordered_map.h:1257
const_local_iterator cend(size_t i) const
Definition: unordered_map.h:588
~iunordered_map()
For library debugging purposes only.
Definition: unordered_map.h:1559
iterator end()
Definition: unordered_map.h:543
size_t available() const
Definition: unordered_map.h:1298
local_iterator end(size_t i)
Definition: unordered_map.h:570
hasher hash_function() const
Definition: unordered_map.h:1316
const_local_iterator cbegin(size_t i) const
Definition: unordered_map.h:534
local_iterator begin(size_t i)
Definition: unordered_map.h:516
const_local_iterator end(size_t i) const
Definition: unordered_map.h:579
iunordered_map & operator=(const iunordered_map &rhs)
Assignment operator.
Definition: unordered_map.h:1333
size_type bucket_size(const_key_reference key) const
Definition: unordered_map.h:606
void insert(TIterator first_, TIterator last_)
Definition: unordered_map.h:1002
size_type max_bucket_count() const
Definition: unordered_map.h:617
const_iterator end() const
Definition: unordered_map.h:552
mapped_reference operator[](const_key_reference key)
Definition: unordered_map.h:681
bool full() const
Checks to see if the unordered_map is full.
Definition: unordered_map.h:1289
size_t count(const_key_reference key) const
Definition: unordered_map.h:1139
iterator find(const_key_reference key)
Definition: unordered_map.h:1149
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition: unordered_map.h:1241
const_iterator begin() const
Definition: unordered_map.h:498
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition: unordered_map.h:1220
void clear()
Clears the unordered_map.
Definition: unordered_map.h:1129
iterator erase(const_iterator ielement)
Definition: unordered_map.h:1047
iunordered_map(pool_t &node_pool_, bucket_t *pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
Constructor.
Definition: unordered_map.h:1369
const_local_iterator begin(size_t i) const
Definition: unordered_map.h:525
bool empty() const
Checks to see if the unordered_map is empty.
Definition: unordered_map.h:1281
key_equal key_eq() const
Definition: unordered_map.h:1325
mapped_reference at(const_key_reference key)
Definition: unordered_map.h:725
size_t erase(const_key_reference key)
Definition: unordered_map.h:1016
const key_type & const_key_reference
Defines the parameter types.
Definition: unordered_map.h:146
size_type capacity() const
Gets the maximum possible size of the unordered_map.
Definition: unordered_map.h:1273
size_type bucket_count() const
Definition: unordered_map.h:626
const_iterator cend() const
Definition: unordered_map.h:561
iterator insert(const_iterator, const_reference key_value_pair)
Definition: unordered_map.h:976
const_mapped_reference at(const_key_reference key) const
Definition: unordered_map.h:760
size_type max_size() const
Gets the maximum possible size of the unordered_map.
Definition: unordered_map.h:1265
ETL_OR_STD::pair< iterator, bool > insert(const_reference key_value_pair)
Definition: unordered_map.h:819
void assign(TIterator first_, TIterator last_)
Definition: unordered_map.h:797
const_iterator cbegin() const
Definition: unordered_map.h:507
Definition: unordered_map.h:127
Definition: unordered_map.h:70
Definition: unordered_map.h:84
Definition: unordered_map.h:111
Definition: unordered_map.h:98
bool operator!=(const etl::iunordered_map< TKey, T, TKeyCompare > &lhs, const etl::iunordered_map< TKey, T, TKeyCompare > &rhs)
Definition: unordered_map.h:1600
bool operator==(const etl::iunordered_map< TKey, T, TKeyCompare > &lhs, const etl::iunordered_map< TKey, T, TKeyCompare > &rhs)
Definition: unordered_map.h:1573
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_map.h:158