31#ifndef ETL_UNORDERED_MAP_INCLUDED
32#define ETL_UNORDERED_MAP_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;
166 value_type key_value_pair;
188 typedef typename bucket_t::iterator local_iterator;
189 typedef typename bucket_t::const_iterator const_local_iterator;
201 typedef typename iunordered_map::reference reference;
202 typedef typename iunordered_map::const_reference const_reference;
203 typedef typename iunordered_map::pointer pointer;
204 typedef typename iunordered_map::const_pointer const_pointer;
217 : pbuckets_end(
other.pbuckets_end)
218 , pbucket(
other.pbucket)
229 if (inode == pbucket->end())
233 while ((pbucket != pbuckets_end) && (pbucket->empty()))
239 if (pbucket != pbuckets_end)
241 inode = pbucket->begin();
259 pbuckets_end =
other.pbuckets_end;
260 pbucket =
other.pbucket;
268 return inode->key_value_pair;
274 return &(inode->key_value_pair);
280 return &(inode->key_value_pair);
308 return rhs.inode == inode;
318 bucket_t* get_bucket_list_iterator()
324 local_iterator get_local_iterator()
331 local_iterator inode;
344 typedef typename iunordered_map::reference reference;
345 typedef typename iunordered_map::const_reference const_reference;
346 typedef typename iunordered_map::pointer pointer;
347 typedef typename iunordered_map::const_pointer const_pointer;
360 : pbuckets_end(
other.pbuckets_end)
361 , pbucket(
other.pbucket)
368 : pbuckets_end(
other.pbuckets_end)
369 , pbucket(
other.pbucket)
380 if (inode == pbucket->end())
384 while ((pbucket != pbuckets_end) && (pbucket->empty()))
390 if (pbucket != pbuckets_end)
392 inode = pbucket->begin();
410 pbuckets_end =
other.pbuckets_end;
411 pbucket =
other.pbucket;
419 return inode->key_value_pair;
425 return &(inode->key_value_pair);
431 return &(inode->key_value_pair);
459 return rhs.inode == inode;
469 bucket_t* get_bucket_list_iterator()
475 local_iterator get_local_iterator()
482 local_iterator inode;
485 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
493 return iterator((pbuckets + number_of_buckets), first, first->begin());
502 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
511 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
520 return pbuckets[
i].begin();
527 const_local_iterator
begin(
size_t i)
const
529 return pbuckets[
i].cbegin();
538 return pbuckets[
i].cbegin();
547 return iterator((pbuckets + number_of_buckets), last, last->end());
556 return const_iterator((pbuckets + number_of_buckets), last, last->end());
565 return const_iterator((pbuckets + number_of_buckets), last, last->end());
574 return pbuckets[
i].end();
581 const_local_iterator
end(
size_t i)
const
583 return pbuckets[
i].cend();
590 const_local_iterator
cend(
size_t i)
const
592 return pbuckets[
i].cend();
601 return key_hash_function(key) % number_of_buckets;
612 return key_hash_function(key) % number_of_buckets;
622 size_t index =
bucket(key);
624 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
635 size_t index =
bucket(key);
637 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
647 return number_of_buckets;
656 return number_of_buckets;
671 local_iterator inode = pbucket->begin();
674 while (inode != pbucket->end())
677 if (key_equal_function(key, inode->key_value_pair.first))
680 return inode->key_value_pair.second;
690 node_t* node = allocate_data_node();
692 ::new ((
void*)
etl::addressof(node->key_value_pair.first)) key_type(
etl::move(key));
693 ::new ((
void*)
etl::
addressof(node->key_value_pair.second)) mapped_type();
694 ETL_INCREMENT_DEBUG_COUNT;
696 pbucket->insert_after(pbucket->before_begin(), *node);
698 adjust_first_last_markers_after_insert(pbucket);
700 return pbucket->
begin()->key_value_pair.second;
715 local_iterator inode = pbucket->begin();
718 while (inode != pbucket->end())
721 if (key_equal_function(key, inode->key_value_pair.
first))
724 return inode->key_value_pair.
second;
738 ETL_INCREMENT_DEBUG_COUNT;
740 pbucket->insert_after(pbucket->before_begin(), *
node);
742 adjust_first_last_markers_after_insert(pbucket);
744 return pbucket->begin()->key_value_pair.
second;
760 local_iterator inode = pbucket->begin();
763 while (inode != pbucket->end())
766 if (key_equal_function(key, inode->key_value_pair.first))
769 return inode->key_value_pair.second;
779 node_t* node = allocate_data_node();
781 ::new ((
void*)
etl::addressof(node->key_value_pair.first)) key_type(key);
782 ::new ((
void*)
etl::
addressof(node->key_value_pair.second)) mapped_type();
783 ETL_INCREMENT_DEBUG_COUNT;
785 pbucket->insert_after(pbucket->before_begin(), *node);
787 adjust_first_last_markers_after_insert(pbucket);
789 return pbucket->
begin()->key_value_pair.second;
805 local_iterator inode = pbucket->begin();
808 while (inode != pbucket->end())
811 if (key_equal_function(key, inode->key_value_pair.
first))
814 return inode->key_value_pair.
second;
825 return begin()->second;
840 local_iterator inode = pbucket->begin();
843 while (inode != pbucket->end())
846 if (key_equal_function(key, inode->key_value_pair.
first))
849 return inode->key_value_pair.
second;
860 return begin()->second;
871 mapped_reference
at(
const K& key)
877 local_iterator inode = pbucket->begin();
880 while (inode != pbucket->end())
883 if (key_equal_function(key, inode->key_value_pair.first))
886 return inode->key_value_pair.second;
895 ETL_ASSERT(
false, ETL_ERROR(unordered_map_out_of_range));
897 return begin()->second;
908 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value,
int> = 0>
909 const_mapped_reference
at(
const K& key)
const
915 local_iterator inode = pbucket->begin();
918 while (inode != pbucket->end())
921 if (key_equal_function(key, inode->key_value_pair.first))
924 return inode->key_value_pair.second;
933 ETL_ASSERT(
false, ETL_ERROR(unordered_map_out_of_range));
935 return begin()->second;
946 template <
typename TIterator>
949#if ETL_IS_DEBUG_BUILD
969 ETL_OR_STD::pair<iterator, bool>
insert(const_reference key_value_pair)
971 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
981 bucket_t* pbucket = pbuckets + index;
991 ETL_INCREMENT_DEBUG_COUNT;
996 adjust_first_last_markers_after_insert(pbucket);
998 result.first =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
999 result.second =
true;
1005 local_iterator inode =
bucket.begin();
1007 while (inode !=
bucket.end())
1010 if (key_equal_function(inode->key_value_pair.first, key))
1020 if (inode ==
bucket.end())
1026 ETL_INCREMENT_DEBUG_COUNT;
1030 adjust_first_last_markers_after_insert(&
bucket);
1034 result.second =
true;
1049 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
1053 const key_type& key = key_value_pair.
first;
1059 bucket_t* pbucket = pbuckets + index;
1060 bucket_t&
bucket = *pbucket;
1066 node_t*
node = allocate_data_node();
1069 ETL_INCREMENT_DEBUG_COUNT;
1074 adjust_first_last_markers_after_insert(pbucket);
1076 result.first =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->
begin());
1077 result.second = true;
1083 local_iterator inode =
bucket.begin();
1085 while (inode !=
bucket.end())
1088 if (key_equal_function(inode->key_value_pair.first, key))
1098 if (inode == bucket.end())
1101 node_t* node = allocate_data_node();
1103 ::new ((
void*)
etl::addressof(node->key_value_pair)) value_type(
etl::move(key_value_pair));
1104 ETL_INCREMENT_DEBUG_COUNT;
1107 bucket.insert_after(inode_previous, *node);
1108 adjust_first_last_markers_after_insert(&bucket);
1111 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
1112 result.second = true;
1128 return insert(key_value_pair).first;
1140 return insert(etl::move(key_value_pair)).first;
1151 template <
class TIterator>
1200 size_t erase(
const K& key)
1205 bucket_t&
bucket = pbuckets[index];
1218 if (icurrent != bucket.end())
1220 delete_data_node(iprevious, icurrent, bucket);
1272 local_iterator
iprevious = pbucket->before_begin();
1274 local_iterator
iend =
last_.get_local_iterator();
1300 }
while (pbucket->empty());
1326 return (
find(key) ==
end()) ? 0 : 1;
1336 size_t count(
const K& key)
const
1338 return (
find(key) ==
end()) ? 0 : 1;
1351 bucket_t* pbucket = pbuckets + index;
1358 local_iterator inode =
bucket.begin();
1361 while (inode !=
iend)
1364 if (key_equal_function(key, inode->key_value_pair.
first))
1366 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1385 bucket_t* pbucket = pbuckets + index;
1392 local_iterator inode =
bucket.begin();
1395 while (inode !=
iend)
1398 if (key_equal_function(key, inode->key_value_pair.
first))
1400 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1421 bucket_t* pbucket = pbuckets + index;
1422 bucket_t&
bucket = *pbucket;
1428 local_iterator inode =
bucket.begin();
1431 while (inode !=
iend)
1434 if (key_equal_function(key, inode->key_value_pair.first))
1436 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1453 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value,
int> = 0>
1454 const_iterator
find(
const K& key)
const
1458 bucket_t* pbucket = pbuckets + index;
1459 bucket_t& bucket = *pbucket;
1462 if (!bucket.empty())
1465 local_iterator inode = bucket.begin();
1466 local_iterator iend = bucket.end();
1468 while (inode != iend)
1471 if (key_equal_function(key, inode->key_value_pair.first))
1473 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1502 return ETL_OR_STD::pair<iterator, iterator>(
f,
l);
1523 return ETL_OR_STD::pair<const_iterator, const_iterator>(
f,
l);
1536 ETL_OR_STD::pair<iterator, iterator>
equal_range(
const K& key)
1546 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1559 template <typename K, typename KE = TKeyEqual, etl::enable_if_t<comparator_is_transparent<KE>::value,
int> = 0>
1560 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(
const K& key)
const
1562 const_iterator f =
find(key);
1563 const_iterator l = f;
1570 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1579 return pnodepool->
size();
1603 return pnodepool->
empty();
1611 return pnodepool->
full();
1638 return key_hash_function;
1647 return key_equal_function;
1658 key_hash_function =
rhs.hash_function();
1659 key_equal_function =
rhs.key_eq();
1675 key_hash_function =
rhs.hash_function();
1676 key_equal_function =
rhs.key_eq();
1677 this->move(
rhs.begin(),
rhs.end());
1727 for (
size_t i = 0
UL;
i < number_of_buckets; ++
i)
1734 local_iterator it =
bucket.begin();
1736 while (it !=
bucket.end())
1739 it->key_value_pair.~value_type();
1740 ETL_DECREMENT_DEBUG_COUNT;
1779 node_t* allocate_data_node()
1781 node_t* (
etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1782 return (pnodepool->*func)();
1788 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1797 if (pbucket < first)
1801 else if (pbucket > last)
1811 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1820 if (pbucket == first)
1823 while (first->empty())
1828 else if (pbucket == last)
1832 bucket_t* pend = last;
1836 while (pbucket != pend)
1838 if (!pbucket->empty())
1852 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1854 local_iterator inext = bucket.erase_after(iprevious);
1855 icurrent->key_value_pair.~value_type();
1856 pnodepool->
release(&*icurrent);
1857 adjust_first_last_markers_after_erase(&bucket);
1858 ETL_DECREMENT_DEBUG_COUNT;
1873 const size_t number_of_buckets;
1880 hasher key_hash_function;
1883 key_equal key_equal_function;
1886 ETL_DECLARE_DEBUG_COUNT;
1891#if defined(ETL_POLYMORPHIC_UNORDERED_MAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
1911 template <
typename TKey,
typename T,
typename THash,
typename TKeyEqual>
1931 ETL_OR_STD::pair<itr_t, itr_t> range =
rhs.equal_range(key);
1933 if (range.first !=
rhs.end())
1959 template <
typename TKey,
typename T,
typename THash,
typename TKeyEqual>
1969 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> >
1978 static ETL_CONSTANT
size_t MAX_SIZE =
MAX_SIZE_;
2018 template <
typename TIterator>
2025#if ETL_HAS_INITIALIZER_LIST
2032 base::assign(
init.begin(),
init.end());
2049 base::operator=(
rhs);
2059 base::operator=(etl::move(
rhs));
2070 typename base::bucket_t buckets[MAX_BUCKETS_];
2076#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2077 template <
typename... TPairs>
2078 unordered_map(TPairs...) -> unordered_map<
typename etl::nth_type_t<0, TPairs...>::first_type,
2086#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2087 template <
typename TKey,
typename T,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey>,
typename... TPairs>
2088 constexpr auto make_unordered_map(TPairs&&... pairs) ->
etl::unordered_map<TKey, T,
sizeof...(TPairs),
sizeof...(TPairs), THash, TKeyEqual>
Definition unordered_map.h:336
Definition unordered_map.h:193
A templated unordered_map implementation that uses a fixed size buffer.
Definition unordered_map.h:1971
unordered_map(const unordered_map &other)
Copy constructor.
Definition unordered_map.h:1992
unordered_map(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_map.h:1984
~unordered_map()
Destructor.
Definition unordered_map.h:2039
unordered_map(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_map.h:2019
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:968
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
ETL_CONSTEXPR17 etl::enable_if<!etl::is_same< T, etl::nullptr_t >::value, T >::type * addressof(T &t)
Definition addressof.h:52
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
float load_factor() const
Definition unordered_map.h:1627
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_map.h:1260
size_type get_bucket_index(const_key_reference key) const
Definition unordered_map.h:599
iterator begin()
Definition unordered_map.h:491
void initialise()
Initialise the unordered_map.
Definition unordered_map.h:1722
const_iterator find(const_key_reference key) const
Definition unordered_map.h:1381
size_type size() const
Gets the size of the unordered_map.
Definition unordered_map.h:1577
const_local_iterator cend(size_t i) const
Definition unordered_map.h:590
~iunordered_map()
Destructor.
Definition unordered_map.h:1898
iterator end()
Definition unordered_map.h:545
size_t available() const
Definition unordered_map.h:1618
local_iterator end(size_t i)
Definition unordered_map.h:572
hasher hash_function() const
Definition unordered_map.h:1636
const_local_iterator cbegin(size_t i) const
Definition unordered_map.h:536
local_iterator begin(size_t i)
Definition unordered_map.h:518
const_local_iterator end(size_t i) const
Definition unordered_map.h:581
iunordered_map & operator=(const iunordered_map &rhs)
Assignment operator.
Definition unordered_map.h:1653
size_type bucket_size(const_key_reference key) const
Definition unordered_map.h:620
void insert(TIterator first_, TIterator last_)
Definition unordered_map.h:1152
size_type max_bucket_count() const
Definition unordered_map.h:645
const_iterator end() const
Definition unordered_map.h:554
mapped_reference operator[](const_key_reference key)
Definition unordered_map.h:709
bool full() const
Checks to see if the unordered_map is full.
Definition unordered_map.h:1609
size_t count(const_key_reference key) const
Definition unordered_map.h:1324
iterator find(const_key_reference key)
Definition unordered_map.h:1347
bool contains(const_key_reference key) const
Check if the unordered_map contains the key.
Definition unordered_map.h:1687
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition unordered_map.h:1513
const_iterator begin() const
Definition unordered_map.h:500
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition unordered_map.h:1492
void clear()
Clears the unordered_map.
Definition unordered_map.h:1314
iterator erase(const_iterator ielement)
Definition unordered_map.h:1232
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:1708
const_local_iterator begin(size_t i) const
Definition unordered_map.h:527
bool empty() const
Checks to see if the unordered_map is empty.
Definition unordered_map.h:1601
key_equal key_eq() const
Definition unordered_map.h:1645
mapped_reference at(const_key_reference key)
Definition unordered_map.h:799
size_t erase(const_key_reference key)
Definition unordered_map.h:1166
const key_type & const_key_reference
Defines the parameter types.
Definition unordered_map.h:148
size_type capacity() const
Gets the maximum possible size of the unordered_map.
Definition unordered_map.h:1593
size_type bucket_count() const
Definition unordered_map.h:654
const_iterator cend() const
Definition unordered_map.h:563
iterator insert(const_iterator, const_reference key_value_pair)
Definition unordered_map.h:1126
const_mapped_reference at(const_key_reference key) const
Definition unordered_map.h:834
size_type max_size() const
Gets the maximum possible size of the unordered_map.
Definition unordered_map.h:1585
ETL_OR_STD::pair< iterator, bool > insert(const_reference key_value_pair)
Definition unordered_map.h:969
void assign(TIterator first_, TIterator last_)
Definition unordered_map.h:947
const_iterator cbegin() const
Definition unordered_map.h:509
Definition unordered_map.h:129
Definition unordered_map.h:72
Definition unordered_map.h:86
Definition unordered_map.h:113
Definition unordered_map.h:100
bitset_ext
Definition absolute.h:38
A forward link.
Definition intrusive_links.h:88
iterator
Definition iterator.h:399
Definition unordered_map.h:160
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