466 typedef ETL_OR_STD::pair<const TKey, TMapped> value_type;
469 typedef value_type& reference;
470 typedef const value_type& const_reference;
474 typedef value_type* pointer;
475 typedef const value_type* const_pointer;
490 bool operator()(const_reference
lhs, const_reference
rhs)
const
535 return kcompare(key, node.value.first);
539 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
540 bool node_comp(
const Data_Node& node,
const K& key)
const
542 return kcompare(node.value.first, key);
545 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
546 bool node_comp(
const K& key,
const Data_Node& node)
const
548 return kcompare(key, node.value.first);
557 key_compare kcompare;
558 value_compare vcompare;
563 static Data_Node* data_cast(Node* p_node)
565 return static_cast<Data_Node*
>(p_node);
571 static Data_Node& data_cast(Node& node)
573 return static_cast<Data_Node&
>(node);
579 static const Data_Node* data_cast(
const Node* p_node)
581 return static_cast<const Data_Node*
>(p_node);
587 static const Data_Node& data_cast(
const Node& node)
589 return static_cast<const Data_Node&
>(node);
606 , p_node(ETL_NULLPTR)
612 , p_node(ETL_NULLPTR)
624 , p_node(
other.p_node)
634 p_map->next_node(p_node);
641 p_map->next_node(p_node);
647 p_map->prev_node(p_node);
654 p_map->prev_node(p_node);
661 p_node =
other.p_node;
667 return imap::data_cast(p_node)->value;
672 return &(imap::data_cast(p_node)->value);
677 return &(imap::data_cast(p_node)->value);
682 return lhs.p_map ==
rhs.p_map &&
lhs.p_node ==
rhs.p_node;
712 , p_node(ETL_NULLPTR)
718 , p_node(ETL_NULLPTR)
730 , p_node(
other.p_node)
736 , p_node(
other.p_node)
746 p_map->next_node(p_node);
753 p_map->next_node(p_node);
759 p_map->prev_node(p_node);
766 p_map->prev_node(p_node);
773 p_node =
other.p_node;
779 return imap::data_cast(p_node)->value;
784 return imap::data_cast(p_node)->value;
789 return &(imap::data_cast(p_node)->value);
794 return lhs.p_map ==
rhs.p_map &&
lhs.p_node ==
rhs.p_node;
819 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
821 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
822 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
877 return reverse_iterator(
iterator(*
this));
899 const_reverse_iterator
rend()
const
915 const_reverse_iterator
crend()
const
938 Data_Node&
node = allocate_data_node_with_key(etl::move(key));
947 return i_element->second;
998 mapped_reference
at(
const K& key)
1026 const_mapped_reference
at(
const K& key)
const
1043 template <
typename TIterator>
1065 return find_node(
root_node, key) ? 1 : 0;
1071 size_type
count(
const K& key)
const
1073 return find_node(
root_node, key) ? 1 : 0;
1083 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
1090 ETL_OR_STD::pair<iterator, iterator>
equal_range(
const K& key)
1092 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
1103 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(
const_iterator(*
this, find_lower_node(
root_node, key)),
1110 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(
const K& key)
const
1112 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*
this, find_lower_node(
root_node, key)),
1113 const_iterator(*
this, find_upper_node(
root_node, key)));
1127 remove_node(
root_node, (*position).first);
1138 return remove_node(
root_node, key) ? 1 : 0;
1143 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1144 size_type
erase(K&& key)
1156 while (first != last)
1158 first =
erase(first);
1161 return last.to_iterator();
1196 const_iterator
find(
const K&
k)
const
1198 return const_iterator(*
this, find_node(
root_node,
k));
1207 ETL_OR_STD::pair<iterator, bool>
insert(const_reference value)
1241 Data_Node&
node = allocate_data_node(etl::move(value));
1290 Data_Node&
node = allocate_data_node(etl::move(value));
1307 template <
class TIterator>
1310 while (first != last)
1353 return const_iterator(*
this, find_lower_node(
root_node, key));
1393 return const_iterator(*
this, find_upper_node(
root_node, key));
1475 , p_node_pool(&node_pool)
1497 Data_Node& allocate_data_node(const_reference value)
1499 Data_Node*
node = allocate_data_node();
1500 ::new (&
node->value) value_type(value);
1501 ETL_INCREMENT_DEBUG_COUNT;
1510 Data_Node*
node = allocate_data_node();
1514 ETL_INCREMENT_DEBUG_COUNT;
1524 Data_Node*
node = allocate_data_node();
1525 ::new (&
node->value) value_type(
etl::move(value));
1526 ETL_INCREMENT_DEBUG_COUNT;
1535 Data_Node*
node = allocate_data_node();
1539 ETL_INCREMENT_DEBUG_COUNT;
1548 Data_Node* allocate_data_node()
1550 Data_Node* (
etl::ipool::*
func)() = &etl::ipool::allocate<Data_Node>;
1551 return (p_node_pool->*
func)();
1557 void destroy_data_node(Data_Node& node)
1559 node.value.~value_type();
1560 p_node_pool->release(&node);
1561 ETL_DECREMENT_DEBUG_COUNT;
1569 Node* found = position;
1573 Data_Node& found_data_node = imap::data_cast(*found);
1579 found = found->children[kLeft];
1581 else if (
node_comp(found_data_node, key))
1584 found = found->children[kRight];
1599 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1600 Node* find_node(Node* position,
const K& key)
1602 Node* found = position;
1606 Data_Node& found_data_node = imap::data_cast(*found);
1612 found = found->children[kLeft];
1614 else if (
node_comp(found_data_node, key))
1617 found = found->children[kRight];
1636 const Node* found = position;
1640 const Data_Node& found_data_node = imap::data_cast(*found);
1646 found = found->children[kLeft];
1648 else if (
node_comp(found_data_node, key))
1651 found = found->children[kRight];
1666 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1667 const Node* find_node(
const Node* position,
const K& key)
const
1669 const Node* found = position;
1673 const Data_Node& found_data_node = imap::data_cast(*found);
1679 found = found->children[kLeft];
1681 else if (
node_comp(found_data_node, key))
1684 found = found->children[kRight];
1701 Node*& find_node(Node*& position,
const Node* node)
1703 Node* found = position;
1706 if (found->children[kLeft] == node)
1708 return found->children[kLeft];
1710 else if (found->children[kRight] == node)
1712 return found->children[kRight];
1717 Data_Node& found_data_node = imap::data_cast(*found);
1718 const Data_Node& data_node = imap::data_cast(*node);
1721 if (
node_comp(data_node, found_data_node))
1724 found = found->children[kLeft];
1726 else if (
node_comp(found_data_node, data_node))
1729 found = found->children[kRight];
1747 Node* find_parent_node(Node* position,
const Node* node)
1750 Node* found = ETL_NULLPTR;
1753 if (position && node && position != node)
1758 if (position->children[kLeft] != node &&
1759 position->children[kRight] != node)
1762 const Data_Node& node_data_node = imap::data_cast(*node);
1763 Data_Node& position_data_node = imap::data_cast(*position);
1765 if (
node_comp(node_data_node, position_data_node))
1768 position = position->children[kLeft];
1770 else if (
node_comp(position_data_node, node_data_node))
1773 position = position->children[kRight];
1795 const Node* find_parent_node(
const Node* position,
const Node* node)
const
1798 const Node* found = ETL_NULLPTR;
1801 if (position && node && position != node)
1806 if (position->children[kLeft] != node &&
1807 position->children[kRight] != node)
1810 const Data_Node& node_data_node = imap::data_cast(*node);
1811 const Data_Node& position_data_node = imap::data_cast(*position);
1813 if (
node_comp(node_data_node, position_data_node))
1816 position = position->children[kLeft];
1818 else if (
node_comp(position_data_node, node_data_node))
1821 position = position->children[kRight];
1845 Node* lower_node = ETL_NULLPTR;
1849 Data_Node& data_node = imap::data_cast(*position);
1853 lower_node = position;
1854 if (position->children[kLeft])
1856 position = position->children[kLeft];
1866 position = position->children[kRight];
1871 lower_node = position;
1872 position = position->children[kLeft];
1882 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1883 Node* find_lower_node(Node* position,
const K& key)
const
1886 Node* lower_node = ETL_NULLPTR;
1890 Data_Node& data_node = imap::data_cast(*position);
1894 lower_node = position;
1895 if (position->children[kLeft])
1897 position = position->children[kLeft];
1907 position = position->children[kRight];
1912 lower_node = position;
1913 position = position->children[kLeft];
1928 Node* upper_node = ETL_NULLPTR;
1930 Node* node = position;
1934 Data_Node& data_node = imap::data_cast(*node);
1939 node = node->children[kLeft];
1943 node = node->children[kRight];
1945 else if (node->children[kRight])
1962 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1963 Node* find_upper_node(Node* position,
const K& key)
const
1966 Node* upper_node = ETL_NULLPTR;
1968 Node* node = position;
1972 Data_Node& data_node = imap::data_cast(*node);
1977 node = node->children[kLeft];
1981 node = node->children[kRight];
1983 else if (node->children[kRight])
2002 Node* insert_node(Node*& position, Data_Node& node)
2005 Node* found = position;
2011 Node* critical_parent_node = ETL_NULLPTR;
2018 if (kNeither != found->weight)
2020 critical_node = found;
2024 Data_Node& found_data_node = imap::data_cast(*found);
2033 else if (
node_comp(found_data_node, node))
2036 found->dir = kRight;
2041 found->dir = kNeither;
2044 critical_node = ETL_NULLPTR;
2047 destroy_data_node(node);
2054 if (found->children[found->dir])
2058 if (kNeither != found->children[found->dir]->weight)
2060 critical_parent_node = found;
2064 found = found->children[found->dir];
2072 found = found->children[found->dir];
2082 if (critical_parent_node == ETL_NULLPTR && critical_node ==
root_node)
2086 else if (critical_parent_node == ETL_NULLPTR && critical_node == position)
2092 if (critical_parent_node != ETL_NULLPTR)
2094 balance_node(critical_parent_node->children[critical_parent_node->dir]);
2115 void next_node(Node*&position)
2120 if (position->children[kRight])
2129 Node* parent = position;
2134 parent = find_parent_node(
root_node, position);
2136 }
while (parent && parent->children[kRight] == position);
2147 void next_node(
const Node*& position)
const
2152 if (position->children[kRight])
2161 const Node* parent = position;
2166 parent = find_parent_node(
root_node, position);
2168 }
while (parent && parent->children[kRight] == position);
2179 void prev_node(Node*&position)
2190 if (position->children[kLeft])
2199 Node* parent = position;
2204 parent = find_parent_node(
root_node, position);
2206 }
while (parent && parent->children[kLeft] == position);
2217 void prev_node(
const Node*& position)
const
2228 if (position->children[kLeft])
2237 const Node* parent = position;
2242 parent = find_parent_node(
root_node, position);
2244 }
while (parent && parent->children[kLeft] == position);
2261 Node* found_parent = ETL_NULLPTR;
2262 Node* found = ETL_NULLPTR;
2263 Node* replace_parent = ETL_NULLPTR;
2264 Node* replace = position;
2265 Node* balance_parent = ETL_NULLPTR;
2270 Data_Node& replace_data_node = imap::data_cast(*replace);
2276 replace->dir = kLeft;
2278 else if (
node_comp(replace_data_node, key))
2281 replace->dir = kRight;
2286 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2289 found_parent = replace_parent;
2294 if (replace->children[replace->dir] == ETL_NULLPTR)
2304 if ((replace->weight == kNeither) ||
2305 (replace->weight == (1 - replace->dir) &&
2306 replace->children[1 - replace->dir]->weight == kNeither))
2309 balance_parent = replace_parent;
2314 replace_parent = replace;
2315 replace = replace->children[replace->dir];
2324 if (balance->children[balance->dir] == ETL_NULLPTR)
2329 if (balance->weight == kNeither)
2331 balance->weight = 1 - balance->dir;
2333 else if (balance->weight == balance->dir)
2335 balance->weight = kNeither;
2339 int weight = balance->children[1 - balance->dir]->weight;
2341 if (weight == balance->dir)
2344 if (balance_parent == ETL_NULLPTR)
2347 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2351 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2352 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2357 else if (weight == kNeither)
2360 if (balance_parent == ETL_NULLPTR)
2367 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2368 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2371 balance->weight = 1 - balance->dir;
2377 if (balance_parent == ETL_NULLPTR)
2383 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2389 if (balance == found)
2393 found_parent = balance_parent->children[balance_parent->dir];
2395 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2406 balance_parent = balance;
2407 balance = balance->children[balance->dir];
2414 detach_node(found_parent->children[found_parent->dir],
2415 replace_parent->children[replace_parent->dir]);
2433 Data_Node& found_data_node = imap::data_cast(*found);
2439 destroy_data_node(found_data_node);
2451 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
2452 Node* remove_node(Node*& position,
const K& key)
2457 Node* found_parent = ETL_NULLPTR;
2458 Node* found = ETL_NULLPTR;
2459 Node* replace_parent = ETL_NULLPTR;
2460 Node* replace = position;
2461 Node* balance_parent = ETL_NULLPTR;
2466 Data_Node& replace_data_node = imap::data_cast(*replace);
2472 replace->dir = kLeft;
2474 else if (
node_comp(replace_data_node, key))
2477 replace->dir = kRight;
2482 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2485 found_parent = replace_parent;
2490 if (replace->children[replace->dir] == ETL_NULLPTR)
2500 if ((replace->weight == kNeither) ||
2501 (replace->weight == (1 - replace->dir) &&
2502 replace->children[1 - replace->dir]->weight == kNeither))
2505 balance_parent = replace_parent;
2510 replace_parent = replace;
2511 replace = replace->children[replace->dir];
2520 if (balance->children[balance->dir] == ETL_NULLPTR)
2525 if (balance->weight == kNeither)
2527 balance->weight = 1 - balance->dir;
2529 else if (balance->weight == balance->dir)
2531 balance->weight = kNeither;
2535 int weight = balance->children[1 - balance->dir]->weight;
2537 if (weight == balance->dir)
2540 if (balance_parent == ETL_NULLPTR)
2543 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2547 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2548 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2553 else if (weight == kNeither)
2556 if (balance_parent == ETL_NULLPTR)
2563 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2564 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2567 balance->weight = 1 - balance->dir;
2573 if (balance_parent == ETL_NULLPTR)
2579 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2585 if (balance == found)
2589 found_parent = balance_parent->children[balance_parent->dir];
2591 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2602 balance_parent = balance;
2603 balance = balance->children[balance->dir];
2610 detach_node(found_parent->children[found_parent->dir],
2611 replace_parent->children[replace_parent->dir]);
2629 Data_Node& found_data_node = imap::data_cast(*found);
2635 destroy_data_node(found_data_node);
2649#if defined(ETL_POLYMORPHIC_MAP) || defined(ETL_POLYMORPHIC_CONTAINERS)