10b57cec5SDimitry Andric// -*- C++ -*- 20b57cec5SDimitry Andric//===----------------------------------------------------------------------===// 30b57cec5SDimitry Andric// 40b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 50b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information. 60b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 70b57cec5SDimitry Andric// 80b57cec5SDimitry Andric//===----------------------------------------------------------------------===// 90b57cec5SDimitry Andric 100b57cec5SDimitry Andric#ifndef _LIBCPP___TREE 110b57cec5SDimitry Andric#define _LIBCPP___TREE 120b57cec5SDimitry Andric 130b57cec5SDimitry Andric#include <__config> 140b57cec5SDimitry Andric#include <iterator> 150b57cec5SDimitry Andric#include <memory> 160b57cec5SDimitry Andric#include <stdexcept> 170b57cec5SDimitry Andric#include <algorithm> 180b57cec5SDimitry Andric 190b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 200b57cec5SDimitry Andric#pragma GCC system_header 210b57cec5SDimitry Andric#endif 220b57cec5SDimitry Andric 230b57cec5SDimitry Andric_LIBCPP_PUSH_MACROS 240b57cec5SDimitry Andric#include <__undef_macros> 250b57cec5SDimitry Andric 260b57cec5SDimitry Andric 270b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 280b57cec5SDimitry Andric 290b57cec5SDimitry Andric#if defined(__GNUC__) && !defined(__clang__) // gcc.gnu.org/PR37804 300b57cec5SDimitry Andrictemplate <class, class, class, class> class _LIBCPP_TEMPLATE_VIS map; 310b57cec5SDimitry Andrictemplate <class, class, class, class> class _LIBCPP_TEMPLATE_VIS multimap; 320b57cec5SDimitry Andrictemplate <class, class, class> class _LIBCPP_TEMPLATE_VIS set; 330b57cec5SDimitry Andrictemplate <class, class, class> class _LIBCPP_TEMPLATE_VIS multiset; 340b57cec5SDimitry Andric#endif 350b57cec5SDimitry Andric 360b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> class __tree; 370b57cec5SDimitry Andrictemplate <class _Tp, class _NodePtr, class _DiffType> 380b57cec5SDimitry Andric class _LIBCPP_TEMPLATE_VIS __tree_iterator; 390b57cec5SDimitry Andrictemplate <class _Tp, class _ConstNodePtr, class _DiffType> 400b57cec5SDimitry Andric class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; 410b57cec5SDimitry Andric 420b57cec5SDimitry Andrictemplate <class _Pointer> class __tree_end_node; 430b57cec5SDimitry Andrictemplate <class _VoidPtr> class __tree_node_base; 440b57cec5SDimitry Andrictemplate <class _Tp, class _VoidPtr> class __tree_node; 450b57cec5SDimitry Andric 460b57cec5SDimitry Andrictemplate <class _Key, class _Value> 470b57cec5SDimitry Andricstruct __value_type; 480b57cec5SDimitry Andric 490b57cec5SDimitry Andrictemplate <class _Allocator> class __map_node_destructor; 500b57cec5SDimitry Andrictemplate <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_iterator; 510b57cec5SDimitry Andrictemplate <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_const_iterator; 520b57cec5SDimitry Andric 530b57cec5SDimitry Andric/* 540b57cec5SDimitry Andric 550b57cec5SDimitry Andric_NodePtr algorithms 560b57cec5SDimitry Andric 570b57cec5SDimitry AndricThe algorithms taking _NodePtr are red black tree algorithms. Those 580b57cec5SDimitry Andricalgorithms taking a parameter named __root should assume that __root 590b57cec5SDimitry Andricpoints to a proper red black tree (unless otherwise specified). 600b57cec5SDimitry Andric 610b57cec5SDimitry AndricEach algorithm herein assumes that __root->__parent_ points to a non-null 620b57cec5SDimitry Andricstructure which has a member __left_ which points back to __root. No other 630b57cec5SDimitry Andricmember is read or written to at __root->__parent_. 640b57cec5SDimitry Andric 650b57cec5SDimitry Andric__root->__parent_ will be referred to below (in comments only) as end_node. 660b57cec5SDimitry Andricend_node->__left_ is an externably accessible lvalue for __root, and can be 670b57cec5SDimitry Andricchanged by node insertion and removal (without explicit reference to end_node). 680b57cec5SDimitry Andric 690b57cec5SDimitry AndricAll nodes (with the exception of end_node), even the node referred to as 700b57cec5SDimitry Andric__root, have a non-null __parent_ field. 710b57cec5SDimitry Andric 720b57cec5SDimitry Andric*/ 730b57cec5SDimitry Andric 740b57cec5SDimitry Andric// Returns: true if __x is a left child of its parent, else false 750b57cec5SDimitry Andric// Precondition: __x != nullptr. 760b57cec5SDimitry Andrictemplate <class _NodePtr> 770b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 780b57cec5SDimitry Andricbool 790b57cec5SDimitry Andric__tree_is_left_child(_NodePtr __x) _NOEXCEPT 800b57cec5SDimitry Andric{ 810b57cec5SDimitry Andric return __x == __x->__parent_->__left_; 820b57cec5SDimitry Andric} 830b57cec5SDimitry Andric 840b57cec5SDimitry Andric// Determines if the subtree rooted at __x is a proper red black subtree. If 850b57cec5SDimitry Andric// __x is a proper subtree, returns the black height (null counts as 1). If 860b57cec5SDimitry Andric// __x is an improper subtree, returns 0. 870b57cec5SDimitry Andrictemplate <class _NodePtr> 880b57cec5SDimitry Andricunsigned 890b57cec5SDimitry Andric__tree_sub_invariant(_NodePtr __x) 900b57cec5SDimitry Andric{ 910b57cec5SDimitry Andric if (__x == nullptr) 920b57cec5SDimitry Andric return 1; 930b57cec5SDimitry Andric // parent consistency checked by caller 940b57cec5SDimitry Andric // check __x->__left_ consistency 950b57cec5SDimitry Andric if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x) 960b57cec5SDimitry Andric return 0; 970b57cec5SDimitry Andric // check __x->__right_ consistency 980b57cec5SDimitry Andric if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x) 990b57cec5SDimitry Andric return 0; 1000b57cec5SDimitry Andric // check __x->__left_ != __x->__right_ unless both are nullptr 1010b57cec5SDimitry Andric if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr) 1020b57cec5SDimitry Andric return 0; 1030b57cec5SDimitry Andric // If this is red, neither child can be red 1040b57cec5SDimitry Andric if (!__x->__is_black_) 1050b57cec5SDimitry Andric { 1060b57cec5SDimitry Andric if (__x->__left_ && !__x->__left_->__is_black_) 1070b57cec5SDimitry Andric return 0; 1080b57cec5SDimitry Andric if (__x->__right_ && !__x->__right_->__is_black_) 1090b57cec5SDimitry Andric return 0; 1100b57cec5SDimitry Andric } 111*e8d8bef9SDimitry Andric unsigned __h = _VSTD::__tree_sub_invariant(__x->__left_); 1120b57cec5SDimitry Andric if (__h == 0) 1130b57cec5SDimitry Andric return 0; // invalid left subtree 114*e8d8bef9SDimitry Andric if (__h != _VSTD::__tree_sub_invariant(__x->__right_)) 1150b57cec5SDimitry Andric return 0; // invalid or different height right subtree 1160b57cec5SDimitry Andric return __h + __x->__is_black_; // return black height of this node 1170b57cec5SDimitry Andric} 1180b57cec5SDimitry Andric 1190b57cec5SDimitry Andric// Determines if the red black tree rooted at __root is a proper red black tree. 1200b57cec5SDimitry Andric// __root == nullptr is a proper tree. Returns true is __root is a proper 1210b57cec5SDimitry Andric// red black tree, else returns false. 1220b57cec5SDimitry Andrictemplate <class _NodePtr> 1230b57cec5SDimitry Andricbool 1240b57cec5SDimitry Andric__tree_invariant(_NodePtr __root) 1250b57cec5SDimitry Andric{ 1260b57cec5SDimitry Andric if (__root == nullptr) 1270b57cec5SDimitry Andric return true; 1280b57cec5SDimitry Andric // check __x->__parent_ consistency 1290b57cec5SDimitry Andric if (__root->__parent_ == nullptr) 1300b57cec5SDimitry Andric return false; 131*e8d8bef9SDimitry Andric if (!_VSTD::__tree_is_left_child(__root)) 1320b57cec5SDimitry Andric return false; 1330b57cec5SDimitry Andric // root must be black 1340b57cec5SDimitry Andric if (!__root->__is_black_) 1350b57cec5SDimitry Andric return false; 1360b57cec5SDimitry Andric // do normal node checks 137*e8d8bef9SDimitry Andric return _VSTD::__tree_sub_invariant(__root) != 0; 1380b57cec5SDimitry Andric} 1390b57cec5SDimitry Andric 1400b57cec5SDimitry Andric// Returns: pointer to the left-most node under __x. 1410b57cec5SDimitry Andric// Precondition: __x != nullptr. 1420b57cec5SDimitry Andrictemplate <class _NodePtr> 1430b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 1440b57cec5SDimitry Andric_NodePtr 1450b57cec5SDimitry Andric__tree_min(_NodePtr __x) _NOEXCEPT 1460b57cec5SDimitry Andric{ 1470b57cec5SDimitry Andric while (__x->__left_ != nullptr) 1480b57cec5SDimitry Andric __x = __x->__left_; 1490b57cec5SDimitry Andric return __x; 1500b57cec5SDimitry Andric} 1510b57cec5SDimitry Andric 1520b57cec5SDimitry Andric// Returns: pointer to the right-most node under __x. 1530b57cec5SDimitry Andric// Precondition: __x != nullptr. 1540b57cec5SDimitry Andrictemplate <class _NodePtr> 1550b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 1560b57cec5SDimitry Andric_NodePtr 1570b57cec5SDimitry Andric__tree_max(_NodePtr __x) _NOEXCEPT 1580b57cec5SDimitry Andric{ 1590b57cec5SDimitry Andric while (__x->__right_ != nullptr) 1600b57cec5SDimitry Andric __x = __x->__right_; 1610b57cec5SDimitry Andric return __x; 1620b57cec5SDimitry Andric} 1630b57cec5SDimitry Andric 1640b57cec5SDimitry Andric// Returns: pointer to the next in-order node after __x. 1650b57cec5SDimitry Andric// Precondition: __x != nullptr. 1660b57cec5SDimitry Andrictemplate <class _NodePtr> 1670b57cec5SDimitry Andric_NodePtr 1680b57cec5SDimitry Andric__tree_next(_NodePtr __x) _NOEXCEPT 1690b57cec5SDimitry Andric{ 1700b57cec5SDimitry Andric if (__x->__right_ != nullptr) 171*e8d8bef9SDimitry Andric return _VSTD::__tree_min(__x->__right_); 172*e8d8bef9SDimitry Andric while (!_VSTD::__tree_is_left_child(__x)) 1730b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 1740b57cec5SDimitry Andric return __x->__parent_unsafe(); 1750b57cec5SDimitry Andric} 1760b57cec5SDimitry Andric 1770b57cec5SDimitry Andrictemplate <class _EndNodePtr, class _NodePtr> 1780b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 1790b57cec5SDimitry Andric_EndNodePtr 1800b57cec5SDimitry Andric__tree_next_iter(_NodePtr __x) _NOEXCEPT 1810b57cec5SDimitry Andric{ 1820b57cec5SDimitry Andric if (__x->__right_ != nullptr) 183*e8d8bef9SDimitry Andric return static_cast<_EndNodePtr>(_VSTD::__tree_min(__x->__right_)); 184*e8d8bef9SDimitry Andric while (!_VSTD::__tree_is_left_child(__x)) 1850b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 1860b57cec5SDimitry Andric return static_cast<_EndNodePtr>(__x->__parent_); 1870b57cec5SDimitry Andric} 1880b57cec5SDimitry Andric 1890b57cec5SDimitry Andric// Returns: pointer to the previous in-order node before __x. 1900b57cec5SDimitry Andric// Precondition: __x != nullptr. 1910b57cec5SDimitry Andric// Note: __x may be the end node. 1920b57cec5SDimitry Andrictemplate <class _NodePtr, class _EndNodePtr> 1930b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 1940b57cec5SDimitry Andric_NodePtr 1950b57cec5SDimitry Andric__tree_prev_iter(_EndNodePtr __x) _NOEXCEPT 1960b57cec5SDimitry Andric{ 1970b57cec5SDimitry Andric if (__x->__left_ != nullptr) 198*e8d8bef9SDimitry Andric return _VSTD::__tree_max(__x->__left_); 1990b57cec5SDimitry Andric _NodePtr __xx = static_cast<_NodePtr>(__x); 200*e8d8bef9SDimitry Andric while (_VSTD::__tree_is_left_child(__xx)) 2010b57cec5SDimitry Andric __xx = __xx->__parent_unsafe(); 2020b57cec5SDimitry Andric return __xx->__parent_unsafe(); 2030b57cec5SDimitry Andric} 2040b57cec5SDimitry Andric 2050b57cec5SDimitry Andric// Returns: pointer to a node which has no children 2060b57cec5SDimitry Andric// Precondition: __x != nullptr. 2070b57cec5SDimitry Andrictemplate <class _NodePtr> 2080b57cec5SDimitry Andric_NodePtr 2090b57cec5SDimitry Andric__tree_leaf(_NodePtr __x) _NOEXCEPT 2100b57cec5SDimitry Andric{ 2110b57cec5SDimitry Andric while (true) 2120b57cec5SDimitry Andric { 2130b57cec5SDimitry Andric if (__x->__left_ != nullptr) 2140b57cec5SDimitry Andric { 2150b57cec5SDimitry Andric __x = __x->__left_; 2160b57cec5SDimitry Andric continue; 2170b57cec5SDimitry Andric } 2180b57cec5SDimitry Andric if (__x->__right_ != nullptr) 2190b57cec5SDimitry Andric { 2200b57cec5SDimitry Andric __x = __x->__right_; 2210b57cec5SDimitry Andric continue; 2220b57cec5SDimitry Andric } 2230b57cec5SDimitry Andric break; 2240b57cec5SDimitry Andric } 2250b57cec5SDimitry Andric return __x; 2260b57cec5SDimitry Andric} 2270b57cec5SDimitry Andric 2280b57cec5SDimitry Andric// Effects: Makes __x->__right_ the subtree root with __x as its left child 2290b57cec5SDimitry Andric// while preserving in-order order. 2300b57cec5SDimitry Andric// Precondition: __x->__right_ != nullptr 2310b57cec5SDimitry Andrictemplate <class _NodePtr> 2320b57cec5SDimitry Andricvoid 2330b57cec5SDimitry Andric__tree_left_rotate(_NodePtr __x) _NOEXCEPT 2340b57cec5SDimitry Andric{ 2350b57cec5SDimitry Andric _NodePtr __y = __x->__right_; 2360b57cec5SDimitry Andric __x->__right_ = __y->__left_; 2370b57cec5SDimitry Andric if (__x->__right_ != nullptr) 2380b57cec5SDimitry Andric __x->__right_->__set_parent(__x); 2390b57cec5SDimitry Andric __y->__parent_ = __x->__parent_; 240*e8d8bef9SDimitry Andric if (_VSTD::__tree_is_left_child(__x)) 2410b57cec5SDimitry Andric __x->__parent_->__left_ = __y; 2420b57cec5SDimitry Andric else 2430b57cec5SDimitry Andric __x->__parent_unsafe()->__right_ = __y; 2440b57cec5SDimitry Andric __y->__left_ = __x; 2450b57cec5SDimitry Andric __x->__set_parent(__y); 2460b57cec5SDimitry Andric} 2470b57cec5SDimitry Andric 2480b57cec5SDimitry Andric// Effects: Makes __x->__left_ the subtree root with __x as its right child 2490b57cec5SDimitry Andric// while preserving in-order order. 2500b57cec5SDimitry Andric// Precondition: __x->__left_ != nullptr 2510b57cec5SDimitry Andrictemplate <class _NodePtr> 2520b57cec5SDimitry Andricvoid 2530b57cec5SDimitry Andric__tree_right_rotate(_NodePtr __x) _NOEXCEPT 2540b57cec5SDimitry Andric{ 2550b57cec5SDimitry Andric _NodePtr __y = __x->__left_; 2560b57cec5SDimitry Andric __x->__left_ = __y->__right_; 2570b57cec5SDimitry Andric if (__x->__left_ != nullptr) 2580b57cec5SDimitry Andric __x->__left_->__set_parent(__x); 2590b57cec5SDimitry Andric __y->__parent_ = __x->__parent_; 260*e8d8bef9SDimitry Andric if (_VSTD::__tree_is_left_child(__x)) 2610b57cec5SDimitry Andric __x->__parent_->__left_ = __y; 2620b57cec5SDimitry Andric else 2630b57cec5SDimitry Andric __x->__parent_unsafe()->__right_ = __y; 2640b57cec5SDimitry Andric __y->__right_ = __x; 2650b57cec5SDimitry Andric __x->__set_parent(__y); 2660b57cec5SDimitry Andric} 2670b57cec5SDimitry Andric 2680b57cec5SDimitry Andric// Effects: Rebalances __root after attaching __x to a leaf. 2690b57cec5SDimitry Andric// Precondition: __root != nulptr && __x != nullptr. 2700b57cec5SDimitry Andric// __x has no children. 2710b57cec5SDimitry Andric// __x == __root or == a direct or indirect child of __root. 2720b57cec5SDimitry Andric// If __x were to be unlinked from __root (setting __root to 2730b57cec5SDimitry Andric// nullptr if __root == __x), __tree_invariant(__root) == true. 2740b57cec5SDimitry Andric// Postcondition: __tree_invariant(end_node->__left_) == true. end_node->__left_ 2750b57cec5SDimitry Andric// may be different than the value passed in as __root. 2760b57cec5SDimitry Andrictemplate <class _NodePtr> 2770b57cec5SDimitry Andricvoid 2780b57cec5SDimitry Andric__tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT 2790b57cec5SDimitry Andric{ 2800b57cec5SDimitry Andric __x->__is_black_ = __x == __root; 2810b57cec5SDimitry Andric while (__x != __root && !__x->__parent_unsafe()->__is_black_) 2820b57cec5SDimitry Andric { 2830b57cec5SDimitry Andric // __x->__parent_ != __root because __x->__parent_->__is_black == false 284*e8d8bef9SDimitry Andric if (_VSTD::__tree_is_left_child(__x->__parent_unsafe())) 2850b57cec5SDimitry Andric { 2860b57cec5SDimitry Andric _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_; 2870b57cec5SDimitry Andric if (__y != nullptr && !__y->__is_black_) 2880b57cec5SDimitry Andric { 2890b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 2900b57cec5SDimitry Andric __x->__is_black_ = true; 2910b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 2920b57cec5SDimitry Andric __x->__is_black_ = __x == __root; 2930b57cec5SDimitry Andric __y->__is_black_ = true; 2940b57cec5SDimitry Andric } 2950b57cec5SDimitry Andric else 2960b57cec5SDimitry Andric { 297*e8d8bef9SDimitry Andric if (!_VSTD::__tree_is_left_child(__x)) 2980b57cec5SDimitry Andric { 2990b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 300*e8d8bef9SDimitry Andric _VSTD::__tree_left_rotate(__x); 3010b57cec5SDimitry Andric } 3020b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 3030b57cec5SDimitry Andric __x->__is_black_ = true; 3040b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 3050b57cec5SDimitry Andric __x->__is_black_ = false; 306*e8d8bef9SDimitry Andric _VSTD::__tree_right_rotate(__x); 3070b57cec5SDimitry Andric break; 3080b57cec5SDimitry Andric } 3090b57cec5SDimitry Andric } 3100b57cec5SDimitry Andric else 3110b57cec5SDimitry Andric { 3120b57cec5SDimitry Andric _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_; 3130b57cec5SDimitry Andric if (__y != nullptr && !__y->__is_black_) 3140b57cec5SDimitry Andric { 3150b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 3160b57cec5SDimitry Andric __x->__is_black_ = true; 3170b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 3180b57cec5SDimitry Andric __x->__is_black_ = __x == __root; 3190b57cec5SDimitry Andric __y->__is_black_ = true; 3200b57cec5SDimitry Andric } 3210b57cec5SDimitry Andric else 3220b57cec5SDimitry Andric { 323*e8d8bef9SDimitry Andric if (_VSTD::__tree_is_left_child(__x)) 3240b57cec5SDimitry Andric { 3250b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 326*e8d8bef9SDimitry Andric _VSTD::__tree_right_rotate(__x); 3270b57cec5SDimitry Andric } 3280b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 3290b57cec5SDimitry Andric __x->__is_black_ = true; 3300b57cec5SDimitry Andric __x = __x->__parent_unsafe(); 3310b57cec5SDimitry Andric __x->__is_black_ = false; 332*e8d8bef9SDimitry Andric _VSTD::__tree_left_rotate(__x); 3330b57cec5SDimitry Andric break; 3340b57cec5SDimitry Andric } 3350b57cec5SDimitry Andric } 3360b57cec5SDimitry Andric } 3370b57cec5SDimitry Andric} 3380b57cec5SDimitry Andric 3390b57cec5SDimitry Andric// Precondition: __root != nullptr && __z != nullptr. 3400b57cec5SDimitry Andric// __tree_invariant(__root) == true. 3410b57cec5SDimitry Andric// __z == __root or == a direct or indirect child of __root. 3420b57cec5SDimitry Andric// Effects: unlinks __z from the tree rooted at __root, rebalancing as needed. 3430b57cec5SDimitry Andric// Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_ 3440b57cec5SDimitry Andric// nor any of its children refer to __z. end_node->__left_ 3450b57cec5SDimitry Andric// may be different than the value passed in as __root. 3460b57cec5SDimitry Andrictemplate <class _NodePtr> 3470b57cec5SDimitry Andricvoid 3480b57cec5SDimitry Andric__tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT 3490b57cec5SDimitry Andric{ 3500b57cec5SDimitry Andric // __z will be removed from the tree. Client still needs to destruct/deallocate it 3510b57cec5SDimitry Andric // __y is either __z, or if __z has two children, __tree_next(__z). 3520b57cec5SDimitry Andric // __y will have at most one child. 3530b57cec5SDimitry Andric // __y will be the initial hole in the tree (make the hole at a leaf) 3540b57cec5SDimitry Andric _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ? 355*e8d8bef9SDimitry Andric __z : _VSTD::__tree_next(__z); 3560b57cec5SDimitry Andric // __x is __y's possibly null single child 3570b57cec5SDimitry Andric _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_; 3580b57cec5SDimitry Andric // __w is __x's possibly null uncle (will become __x's sibling) 3590b57cec5SDimitry Andric _NodePtr __w = nullptr; 3600b57cec5SDimitry Andric // link __x to __y's parent, and find __w 3610b57cec5SDimitry Andric if (__x != nullptr) 3620b57cec5SDimitry Andric __x->__parent_ = __y->__parent_; 363*e8d8bef9SDimitry Andric if (_VSTD::__tree_is_left_child(__y)) 3640b57cec5SDimitry Andric { 3650b57cec5SDimitry Andric __y->__parent_->__left_ = __x; 3660b57cec5SDimitry Andric if (__y != __root) 3670b57cec5SDimitry Andric __w = __y->__parent_unsafe()->__right_; 3680b57cec5SDimitry Andric else 3690b57cec5SDimitry Andric __root = __x; // __w == nullptr 3700b57cec5SDimitry Andric } 3710b57cec5SDimitry Andric else 3720b57cec5SDimitry Andric { 3730b57cec5SDimitry Andric __y->__parent_unsafe()->__right_ = __x; 3740b57cec5SDimitry Andric // __y can't be root if it is a right child 3750b57cec5SDimitry Andric __w = __y->__parent_->__left_; 3760b57cec5SDimitry Andric } 3770b57cec5SDimitry Andric bool __removed_black = __y->__is_black_; 3780b57cec5SDimitry Andric // If we didn't remove __z, do so now by splicing in __y for __z, 3790b57cec5SDimitry Andric // but copy __z's color. This does not impact __x or __w. 3800b57cec5SDimitry Andric if (__y != __z) 3810b57cec5SDimitry Andric { 3820b57cec5SDimitry Andric // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr 3830b57cec5SDimitry Andric __y->__parent_ = __z->__parent_; 384*e8d8bef9SDimitry Andric if (_VSTD::__tree_is_left_child(__z)) 3850b57cec5SDimitry Andric __y->__parent_->__left_ = __y; 3860b57cec5SDimitry Andric else 3870b57cec5SDimitry Andric __y->__parent_unsafe()->__right_ = __y; 3880b57cec5SDimitry Andric __y->__left_ = __z->__left_; 3890b57cec5SDimitry Andric __y->__left_->__set_parent(__y); 3900b57cec5SDimitry Andric __y->__right_ = __z->__right_; 3910b57cec5SDimitry Andric if (__y->__right_ != nullptr) 3920b57cec5SDimitry Andric __y->__right_->__set_parent(__y); 3930b57cec5SDimitry Andric __y->__is_black_ = __z->__is_black_; 3940b57cec5SDimitry Andric if (__root == __z) 3950b57cec5SDimitry Andric __root = __y; 3960b57cec5SDimitry Andric } 3970b57cec5SDimitry Andric // There is no need to rebalance if we removed a red, or if we removed 3980b57cec5SDimitry Andric // the last node. 3990b57cec5SDimitry Andric if (__removed_black && __root != nullptr) 4000b57cec5SDimitry Andric { 4010b57cec5SDimitry Andric // Rebalance: 4020b57cec5SDimitry Andric // __x has an implicit black color (transferred from the removed __y) 4030b57cec5SDimitry Andric // associated with it, no matter what its color is. 4040b57cec5SDimitry Andric // If __x is __root (in which case it can't be null), it is supposed 4050b57cec5SDimitry Andric // to be black anyway, and if it is doubly black, then the double 4060b57cec5SDimitry Andric // can just be ignored. 4070b57cec5SDimitry Andric // If __x is red (in which case it can't be null), then it can absorb 4080b57cec5SDimitry Andric // the implicit black just by setting its color to black. 4090b57cec5SDimitry Andric // Since __y was black and only had one child (which __x points to), __x 4100b57cec5SDimitry Andric // is either red with no children, else null, otherwise __y would have 4110b57cec5SDimitry Andric // different black heights under left and right pointers. 4120b57cec5SDimitry Andric // if (__x == __root || __x != nullptr && !__x->__is_black_) 4130b57cec5SDimitry Andric if (__x != nullptr) 4140b57cec5SDimitry Andric __x->__is_black_ = true; 4150b57cec5SDimitry Andric else 4160b57cec5SDimitry Andric { 4170b57cec5SDimitry Andric // Else __x isn't root, and is "doubly black", even though it may 4180b57cec5SDimitry Andric // be null. __w can not be null here, else the parent would 4190b57cec5SDimitry Andric // see a black height >= 2 on the __x side and a black height 4200b57cec5SDimitry Andric // of 1 on the __w side (__w must be a non-null black or a red 4210b57cec5SDimitry Andric // with a non-null black child). 4220b57cec5SDimitry Andric while (true) 4230b57cec5SDimitry Andric { 424*e8d8bef9SDimitry Andric if (!_VSTD::__tree_is_left_child(__w)) // if x is left child 4250b57cec5SDimitry Andric { 4260b57cec5SDimitry Andric if (!__w->__is_black_) 4270b57cec5SDimitry Andric { 4280b57cec5SDimitry Andric __w->__is_black_ = true; 4290b57cec5SDimitry Andric __w->__parent_unsafe()->__is_black_ = false; 430*e8d8bef9SDimitry Andric _VSTD::__tree_left_rotate(__w->__parent_unsafe()); 4310b57cec5SDimitry Andric // __x is still valid 4320b57cec5SDimitry Andric // reset __root only if necessary 4330b57cec5SDimitry Andric if (__root == __w->__left_) 4340b57cec5SDimitry Andric __root = __w; 4350b57cec5SDimitry Andric // reset sibling, and it still can't be null 4360b57cec5SDimitry Andric __w = __w->__left_->__right_; 4370b57cec5SDimitry Andric } 4380b57cec5SDimitry Andric // __w->__is_black_ is now true, __w may have null children 4390b57cec5SDimitry Andric if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && 4400b57cec5SDimitry Andric (__w->__right_ == nullptr || __w->__right_->__is_black_)) 4410b57cec5SDimitry Andric { 4420b57cec5SDimitry Andric __w->__is_black_ = false; 4430b57cec5SDimitry Andric __x = __w->__parent_unsafe(); 4440b57cec5SDimitry Andric // __x can no longer be null 4450b57cec5SDimitry Andric if (__x == __root || !__x->__is_black_) 4460b57cec5SDimitry Andric { 4470b57cec5SDimitry Andric __x->__is_black_ = true; 4480b57cec5SDimitry Andric break; 4490b57cec5SDimitry Andric } 4500b57cec5SDimitry Andric // reset sibling, and it still can't be null 451*e8d8bef9SDimitry Andric __w = _VSTD::__tree_is_left_child(__x) ? 4520b57cec5SDimitry Andric __x->__parent_unsafe()->__right_ : 4530b57cec5SDimitry Andric __x->__parent_->__left_; 4540b57cec5SDimitry Andric // continue; 4550b57cec5SDimitry Andric } 4560b57cec5SDimitry Andric else // __w has a red child 4570b57cec5SDimitry Andric { 4580b57cec5SDimitry Andric if (__w->__right_ == nullptr || __w->__right_->__is_black_) 4590b57cec5SDimitry Andric { 4600b57cec5SDimitry Andric // __w left child is non-null and red 4610b57cec5SDimitry Andric __w->__left_->__is_black_ = true; 4620b57cec5SDimitry Andric __w->__is_black_ = false; 463*e8d8bef9SDimitry Andric _VSTD::__tree_right_rotate(__w); 4640b57cec5SDimitry Andric // __w is known not to be root, so root hasn't changed 4650b57cec5SDimitry Andric // reset sibling, and it still can't be null 4660b57cec5SDimitry Andric __w = __w->__parent_unsafe(); 4670b57cec5SDimitry Andric } 4680b57cec5SDimitry Andric // __w has a right red child, left child may be null 4690b57cec5SDimitry Andric __w->__is_black_ = __w->__parent_unsafe()->__is_black_; 4700b57cec5SDimitry Andric __w->__parent_unsafe()->__is_black_ = true; 4710b57cec5SDimitry Andric __w->__right_->__is_black_ = true; 472*e8d8bef9SDimitry Andric _VSTD::__tree_left_rotate(__w->__parent_unsafe()); 4730b57cec5SDimitry Andric break; 4740b57cec5SDimitry Andric } 4750b57cec5SDimitry Andric } 4760b57cec5SDimitry Andric else 4770b57cec5SDimitry Andric { 4780b57cec5SDimitry Andric if (!__w->__is_black_) 4790b57cec5SDimitry Andric { 4800b57cec5SDimitry Andric __w->__is_black_ = true; 4810b57cec5SDimitry Andric __w->__parent_unsafe()->__is_black_ = false; 482*e8d8bef9SDimitry Andric _VSTD::__tree_right_rotate(__w->__parent_unsafe()); 4830b57cec5SDimitry Andric // __x is still valid 4840b57cec5SDimitry Andric // reset __root only if necessary 4850b57cec5SDimitry Andric if (__root == __w->__right_) 4860b57cec5SDimitry Andric __root = __w; 4870b57cec5SDimitry Andric // reset sibling, and it still can't be null 4880b57cec5SDimitry Andric __w = __w->__right_->__left_; 4890b57cec5SDimitry Andric } 4900b57cec5SDimitry Andric // __w->__is_black_ is now true, __w may have null children 4910b57cec5SDimitry Andric if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && 4920b57cec5SDimitry Andric (__w->__right_ == nullptr || __w->__right_->__is_black_)) 4930b57cec5SDimitry Andric { 4940b57cec5SDimitry Andric __w->__is_black_ = false; 4950b57cec5SDimitry Andric __x = __w->__parent_unsafe(); 4960b57cec5SDimitry Andric // __x can no longer be null 4970b57cec5SDimitry Andric if (!__x->__is_black_ || __x == __root) 4980b57cec5SDimitry Andric { 4990b57cec5SDimitry Andric __x->__is_black_ = true; 5000b57cec5SDimitry Andric break; 5010b57cec5SDimitry Andric } 5020b57cec5SDimitry Andric // reset sibling, and it still can't be null 503*e8d8bef9SDimitry Andric __w = _VSTD::__tree_is_left_child(__x) ? 5040b57cec5SDimitry Andric __x->__parent_unsafe()->__right_ : 5050b57cec5SDimitry Andric __x->__parent_->__left_; 5060b57cec5SDimitry Andric // continue; 5070b57cec5SDimitry Andric } 5080b57cec5SDimitry Andric else // __w has a red child 5090b57cec5SDimitry Andric { 5100b57cec5SDimitry Andric if (__w->__left_ == nullptr || __w->__left_->__is_black_) 5110b57cec5SDimitry Andric { 5120b57cec5SDimitry Andric // __w right child is non-null and red 5130b57cec5SDimitry Andric __w->__right_->__is_black_ = true; 5140b57cec5SDimitry Andric __w->__is_black_ = false; 515*e8d8bef9SDimitry Andric _VSTD::__tree_left_rotate(__w); 5160b57cec5SDimitry Andric // __w is known not to be root, so root hasn't changed 5170b57cec5SDimitry Andric // reset sibling, and it still can't be null 5180b57cec5SDimitry Andric __w = __w->__parent_unsafe(); 5190b57cec5SDimitry Andric } 5200b57cec5SDimitry Andric // __w has a left red child, right child may be null 5210b57cec5SDimitry Andric __w->__is_black_ = __w->__parent_unsafe()->__is_black_; 5220b57cec5SDimitry Andric __w->__parent_unsafe()->__is_black_ = true; 5230b57cec5SDimitry Andric __w->__left_->__is_black_ = true; 524*e8d8bef9SDimitry Andric _VSTD::__tree_right_rotate(__w->__parent_unsafe()); 5250b57cec5SDimitry Andric break; 5260b57cec5SDimitry Andric } 5270b57cec5SDimitry Andric } 5280b57cec5SDimitry Andric } 5290b57cec5SDimitry Andric } 5300b57cec5SDimitry Andric } 5310b57cec5SDimitry Andric} 5320b57cec5SDimitry Andric 5330b57cec5SDimitry Andric// node traits 5340b57cec5SDimitry Andric 5350b57cec5SDimitry Andric 5360b57cec5SDimitry Andrictemplate <class _Tp> 5370b57cec5SDimitry Andricstruct __is_tree_value_type_imp : false_type {}; 5380b57cec5SDimitry Andric 5390b57cec5SDimitry Andrictemplate <class _Key, class _Value> 5400b57cec5SDimitry Andricstruct __is_tree_value_type_imp<__value_type<_Key, _Value> > : true_type {}; 5410b57cec5SDimitry Andric 5420b57cec5SDimitry Andrictemplate <class ..._Args> 5430b57cec5SDimitry Andricstruct __is_tree_value_type : false_type {}; 5440b57cec5SDimitry Andric 5450b57cec5SDimitry Andrictemplate <class _One> 5460b57cec5SDimitry Andricstruct __is_tree_value_type<_One> : __is_tree_value_type_imp<typename __uncvref<_One>::type> {}; 5470b57cec5SDimitry Andric 5480b57cec5SDimitry Andrictemplate <class _Tp> 5490b57cec5SDimitry Andricstruct __tree_key_value_types { 5500b57cec5SDimitry Andric typedef _Tp key_type; 5510b57cec5SDimitry Andric typedef _Tp __node_value_type; 5520b57cec5SDimitry Andric typedef _Tp __container_value_type; 5530b57cec5SDimitry Andric static const bool __is_map = false; 5540b57cec5SDimitry Andric 5550b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5560b57cec5SDimitry Andric static key_type const& __get_key(_Tp const& __v) { 5570b57cec5SDimitry Andric return __v; 5580b57cec5SDimitry Andric } 5590b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5600b57cec5SDimitry Andric static __container_value_type const& __get_value(__node_value_type const& __v) { 5610b57cec5SDimitry Andric return __v; 5620b57cec5SDimitry Andric } 5630b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5640b57cec5SDimitry Andric static __container_value_type* __get_ptr(__node_value_type& __n) { 5650b57cec5SDimitry Andric return _VSTD::addressof(__n); 5660b57cec5SDimitry Andric } 5670b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5680b57cec5SDimitry Andric static __container_value_type&& __move(__node_value_type& __v) { 5690b57cec5SDimitry Andric return _VSTD::move(__v); 5700b57cec5SDimitry Andric } 5710b57cec5SDimitry Andric}; 5720b57cec5SDimitry Andric 5730b57cec5SDimitry Andrictemplate <class _Key, class _Tp> 5740b57cec5SDimitry Andricstruct __tree_key_value_types<__value_type<_Key, _Tp> > { 5750b57cec5SDimitry Andric typedef _Key key_type; 5760b57cec5SDimitry Andric typedef _Tp mapped_type; 5770b57cec5SDimitry Andric typedef __value_type<_Key, _Tp> __node_value_type; 5780b57cec5SDimitry Andric typedef pair<const _Key, _Tp> __container_value_type; 5790b57cec5SDimitry Andric typedef __container_value_type __map_value_type; 5800b57cec5SDimitry Andric static const bool __is_map = true; 5810b57cec5SDimitry Andric 5820b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5830b57cec5SDimitry Andric static key_type const& 5840b57cec5SDimitry Andric __get_key(__node_value_type const& __t) { 5850b57cec5SDimitry Andric return __t.__get_value().first; 5860b57cec5SDimitry Andric } 5870b57cec5SDimitry Andric 5880b57cec5SDimitry Andric template <class _Up> 5890b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5900b57cec5SDimitry Andric static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value, 5910b57cec5SDimitry Andric key_type const&>::type 5920b57cec5SDimitry Andric __get_key(_Up& __t) { 5930b57cec5SDimitry Andric return __t.first; 5940b57cec5SDimitry Andric } 5950b57cec5SDimitry Andric 5960b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5970b57cec5SDimitry Andric static __container_value_type const& 5980b57cec5SDimitry Andric __get_value(__node_value_type const& __t) { 5990b57cec5SDimitry Andric return __t.__get_value(); 6000b57cec5SDimitry Andric } 6010b57cec5SDimitry Andric 6020b57cec5SDimitry Andric template <class _Up> 6030b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6040b57cec5SDimitry Andric static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value, 6050b57cec5SDimitry Andric __container_value_type const&>::type 6060b57cec5SDimitry Andric __get_value(_Up& __t) { 6070b57cec5SDimitry Andric return __t; 6080b57cec5SDimitry Andric } 6090b57cec5SDimitry Andric 6100b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6110b57cec5SDimitry Andric static __container_value_type* __get_ptr(__node_value_type& __n) { 6120b57cec5SDimitry Andric return _VSTD::addressof(__n.__get_value()); 6130b57cec5SDimitry Andric } 6140b57cec5SDimitry Andric 6150b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6160b57cec5SDimitry Andric static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { 6170b57cec5SDimitry Andric return __v.__move(); 6180b57cec5SDimitry Andric } 6190b57cec5SDimitry Andric}; 6200b57cec5SDimitry Andric 6210b57cec5SDimitry Andrictemplate <class _VoidPtr> 6220b57cec5SDimitry Andricstruct __tree_node_base_types { 6230b57cec5SDimitry Andric typedef _VoidPtr __void_pointer; 6240b57cec5SDimitry Andric 6250b57cec5SDimitry Andric typedef __tree_node_base<__void_pointer> __node_base_type; 6260b57cec5SDimitry Andric typedef typename __rebind_pointer<_VoidPtr, __node_base_type>::type 6270b57cec5SDimitry Andric __node_base_pointer; 6280b57cec5SDimitry Andric 6290b57cec5SDimitry Andric typedef __tree_end_node<__node_base_pointer> __end_node_type; 6300b57cec5SDimitry Andric typedef typename __rebind_pointer<_VoidPtr, __end_node_type>::type 6310b57cec5SDimitry Andric __end_node_pointer; 6320b57cec5SDimitry Andric#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB) 6330b57cec5SDimitry Andric typedef __end_node_pointer __parent_pointer; 6340b57cec5SDimitry Andric#else 6350b57cec5SDimitry Andric typedef typename conditional< 6360b57cec5SDimitry Andric is_pointer<__end_node_pointer>::value, 6370b57cec5SDimitry Andric __end_node_pointer, 6380b57cec5SDimitry Andric __node_base_pointer>::type __parent_pointer; 6390b57cec5SDimitry Andric#endif 6400b57cec5SDimitry Andric 6410b57cec5SDimitry Andricprivate: 6420b57cec5SDimitry Andric static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value), 6430b57cec5SDimitry Andric "_VoidPtr does not point to unqualified void type"); 6440b57cec5SDimitry Andric}; 6450b57cec5SDimitry Andric 6460b57cec5SDimitry Andrictemplate <class _Tp, class _AllocPtr, class _KVTypes = __tree_key_value_types<_Tp>, 6470b57cec5SDimitry Andric bool = _KVTypes::__is_map> 6480b57cec5SDimitry Andricstruct __tree_map_pointer_types {}; 6490b57cec5SDimitry Andric 6500b57cec5SDimitry Andrictemplate <class _Tp, class _AllocPtr, class _KVTypes> 6510b57cec5SDimitry Andricstruct __tree_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> { 6520b57cec5SDimitry Andric typedef typename _KVTypes::__map_value_type _Mv; 6530b57cec5SDimitry Andric typedef typename __rebind_pointer<_AllocPtr, _Mv>::type 6540b57cec5SDimitry Andric __map_value_type_pointer; 6550b57cec5SDimitry Andric typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type 6560b57cec5SDimitry Andric __const_map_value_type_pointer; 6570b57cec5SDimitry Andric}; 6580b57cec5SDimitry Andric 6590b57cec5SDimitry Andrictemplate <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type> 6600b57cec5SDimitry Andricstruct __tree_node_types; 6610b57cec5SDimitry Andric 6620b57cec5SDimitry Andrictemplate <class _NodePtr, class _Tp, class _VoidPtr> 6630b57cec5SDimitry Andricstruct __tree_node_types<_NodePtr, __tree_node<_Tp, _VoidPtr> > 6640b57cec5SDimitry Andric : public __tree_node_base_types<_VoidPtr>, 6650b57cec5SDimitry Andric __tree_key_value_types<_Tp>, 6660b57cec5SDimitry Andric __tree_map_pointer_types<_Tp, _VoidPtr> 6670b57cec5SDimitry Andric{ 6680b57cec5SDimitry Andric typedef __tree_node_base_types<_VoidPtr> __base; 6690b57cec5SDimitry Andric typedef __tree_key_value_types<_Tp> __key_base; 6700b57cec5SDimitry Andric typedef __tree_map_pointer_types<_Tp, _VoidPtr> __map_pointer_base; 6710b57cec5SDimitry Andricpublic: 6720b57cec5SDimitry Andric 6730b57cec5SDimitry Andric typedef typename pointer_traits<_NodePtr>::element_type __node_type; 6740b57cec5SDimitry Andric typedef _NodePtr __node_pointer; 6750b57cec5SDimitry Andric 6760b57cec5SDimitry Andric typedef _Tp __node_value_type; 6770b57cec5SDimitry Andric typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type 6780b57cec5SDimitry Andric __node_value_type_pointer; 6790b57cec5SDimitry Andric typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type 6800b57cec5SDimitry Andric __const_node_value_type_pointer; 6810b57cec5SDimitry Andric#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB) 6820b57cec5SDimitry Andric typedef typename __base::__end_node_pointer __iter_pointer; 6830b57cec5SDimitry Andric#else 6840b57cec5SDimitry Andric typedef typename conditional< 6850b57cec5SDimitry Andric is_pointer<__node_pointer>::value, 6860b57cec5SDimitry Andric typename __base::__end_node_pointer, 6870b57cec5SDimitry Andric __node_pointer>::type __iter_pointer; 6880b57cec5SDimitry Andric#endif 6890b57cec5SDimitry Andricprivate: 6900b57cec5SDimitry Andric static_assert(!is_const<__node_type>::value, 6910b57cec5SDimitry Andric "_NodePtr should never be a pointer to const"); 6920b57cec5SDimitry Andric static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type, 6930b57cec5SDimitry Andric _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr."); 6940b57cec5SDimitry Andric}; 6950b57cec5SDimitry Andric 6960b57cec5SDimitry Andrictemplate <class _ValueTp, class _VoidPtr> 6970b57cec5SDimitry Andricstruct __make_tree_node_types { 6980b57cec5SDimitry Andric typedef typename __rebind_pointer<_VoidPtr, __tree_node<_ValueTp, _VoidPtr> >::type 6990b57cec5SDimitry Andric _NodePtr; 7000b57cec5SDimitry Andric typedef __tree_node_types<_NodePtr> type; 7010b57cec5SDimitry Andric}; 7020b57cec5SDimitry Andric 7030b57cec5SDimitry Andric// node 7040b57cec5SDimitry Andric 7050b57cec5SDimitry Andrictemplate <class _Pointer> 7060b57cec5SDimitry Andricclass __tree_end_node 7070b57cec5SDimitry Andric{ 7080b57cec5SDimitry Andricpublic: 7090b57cec5SDimitry Andric typedef _Pointer pointer; 7100b57cec5SDimitry Andric pointer __left_; 7110b57cec5SDimitry Andric 7120b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7130b57cec5SDimitry Andric __tree_end_node() _NOEXCEPT : __left_() {} 7140b57cec5SDimitry Andric}; 7150b57cec5SDimitry Andric 7160b57cec5SDimitry Andrictemplate <class _VoidPtr> 7170b57cec5SDimitry Andricclass __tree_node_base 7180b57cec5SDimitry Andric : public __tree_node_base_types<_VoidPtr>::__end_node_type 7190b57cec5SDimitry Andric{ 7200b57cec5SDimitry Andric typedef __tree_node_base_types<_VoidPtr> _NodeBaseTypes; 7210b57cec5SDimitry Andric 7220b57cec5SDimitry Andricpublic: 7230b57cec5SDimitry Andric typedef typename _NodeBaseTypes::__node_base_pointer pointer; 7240b57cec5SDimitry Andric typedef typename _NodeBaseTypes::__parent_pointer __parent_pointer; 7250b57cec5SDimitry Andric 7260b57cec5SDimitry Andric pointer __right_; 7270b57cec5SDimitry Andric __parent_pointer __parent_; 7280b57cec5SDimitry Andric bool __is_black_; 7290b57cec5SDimitry Andric 7300b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7310b57cec5SDimitry Andric pointer __parent_unsafe() const { return static_cast<pointer>(__parent_);} 7320b57cec5SDimitry Andric 7330b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7340b57cec5SDimitry Andric void __set_parent(pointer __p) { 7350b57cec5SDimitry Andric __parent_ = static_cast<__parent_pointer>(__p); 7360b57cec5SDimitry Andric } 7370b57cec5SDimitry Andric 7380b57cec5SDimitry Andricprivate: 7390b57cec5SDimitry Andric ~__tree_node_base() _LIBCPP_EQUAL_DELETE; 7400b57cec5SDimitry Andric __tree_node_base(__tree_node_base const&) _LIBCPP_EQUAL_DELETE; 7410b57cec5SDimitry Andric __tree_node_base& operator=(__tree_node_base const&) _LIBCPP_EQUAL_DELETE; 7420b57cec5SDimitry Andric}; 7430b57cec5SDimitry Andric 7440b57cec5SDimitry Andrictemplate <class _Tp, class _VoidPtr> 7450b57cec5SDimitry Andricclass __tree_node 7460b57cec5SDimitry Andric : public __tree_node_base<_VoidPtr> 7470b57cec5SDimitry Andric{ 7480b57cec5SDimitry Andricpublic: 7490b57cec5SDimitry Andric typedef _Tp __node_value_type; 7500b57cec5SDimitry Andric 7510b57cec5SDimitry Andric __node_value_type __value_; 7520b57cec5SDimitry Andric 7530b57cec5SDimitry Andricprivate: 7540b57cec5SDimitry Andric ~__tree_node() _LIBCPP_EQUAL_DELETE; 7550b57cec5SDimitry Andric __tree_node(__tree_node const&) _LIBCPP_EQUAL_DELETE; 7560b57cec5SDimitry Andric __tree_node& operator=(__tree_node const&) _LIBCPP_EQUAL_DELETE; 7570b57cec5SDimitry Andric}; 7580b57cec5SDimitry Andric 7590b57cec5SDimitry Andric 7600b57cec5SDimitry Andrictemplate <class _Allocator> 7610b57cec5SDimitry Andricclass __tree_node_destructor 7620b57cec5SDimitry Andric{ 7630b57cec5SDimitry Andric typedef _Allocator allocator_type; 7640b57cec5SDimitry Andric typedef allocator_traits<allocator_type> __alloc_traits; 7650b57cec5SDimitry Andric 7660b57cec5SDimitry Andricpublic: 7670b57cec5SDimitry Andric typedef typename __alloc_traits::pointer pointer; 7680b57cec5SDimitry Andricprivate: 7690b57cec5SDimitry Andric typedef __tree_node_types<pointer> _NodeTypes; 7700b57cec5SDimitry Andric allocator_type& __na_; 7710b57cec5SDimitry Andric 7720b57cec5SDimitry Andric 7730b57cec5SDimitry Andricpublic: 7740b57cec5SDimitry Andric bool __value_constructed; 7750b57cec5SDimitry Andric 776cd0c3137SDimitry Andric 777cd0c3137SDimitry Andric __tree_node_destructor(const __tree_node_destructor &) = default; 778cd0c3137SDimitry Andric __tree_node_destructor& operator=(const __tree_node_destructor&) = delete; 779cd0c3137SDimitry Andric 7800b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7810b57cec5SDimitry Andric explicit __tree_node_destructor(allocator_type& __na, bool __val = false) _NOEXCEPT 7820b57cec5SDimitry Andric : __na_(__na), 7830b57cec5SDimitry Andric __value_constructed(__val) 7840b57cec5SDimitry Andric {} 7850b57cec5SDimitry Andric 7860b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7870b57cec5SDimitry Andric void operator()(pointer __p) _NOEXCEPT 7880b57cec5SDimitry Andric { 7890b57cec5SDimitry Andric if (__value_constructed) 7900b57cec5SDimitry Andric __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_)); 7910b57cec5SDimitry Andric if (__p) 7920b57cec5SDimitry Andric __alloc_traits::deallocate(__na_, __p, 1); 7930b57cec5SDimitry Andric } 7940b57cec5SDimitry Andric 7950b57cec5SDimitry Andric template <class> friend class __map_node_destructor; 7960b57cec5SDimitry Andric}; 7970b57cec5SDimitry Andric 7980b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 7990b57cec5SDimitry Andrictemplate <class _NodeType, class _Alloc> 8000b57cec5SDimitry Andricstruct __generic_container_node_destructor; 8010b57cec5SDimitry Andrictemplate <class _Tp, class _VoidPtr, class _Alloc> 8020b57cec5SDimitry Andricstruct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc> 8030b57cec5SDimitry Andric : __tree_node_destructor<_Alloc> 8040b57cec5SDimitry Andric{ 8050b57cec5SDimitry Andric using __tree_node_destructor<_Alloc>::__tree_node_destructor; 8060b57cec5SDimitry Andric}; 8070b57cec5SDimitry Andric#endif 8080b57cec5SDimitry Andric 8090b57cec5SDimitry Andrictemplate <class _Tp, class _NodePtr, class _DiffType> 8100b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS __tree_iterator 8110b57cec5SDimitry Andric{ 8120b57cec5SDimitry Andric typedef __tree_node_types<_NodePtr> _NodeTypes; 8130b57cec5SDimitry Andric typedef _NodePtr __node_pointer; 8140b57cec5SDimitry Andric typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 8150b57cec5SDimitry Andric typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; 8160b57cec5SDimitry Andric typedef typename _NodeTypes::__iter_pointer __iter_pointer; 8170b57cec5SDimitry Andric typedef pointer_traits<__node_pointer> __pointer_traits; 8180b57cec5SDimitry Andric 8190b57cec5SDimitry Andric __iter_pointer __ptr_; 8200b57cec5SDimitry Andric 8210b57cec5SDimitry Andricpublic: 8220b57cec5SDimitry Andric typedef bidirectional_iterator_tag iterator_category; 8230b57cec5SDimitry Andric typedef _Tp value_type; 8240b57cec5SDimitry Andric typedef _DiffType difference_type; 8250b57cec5SDimitry Andric typedef value_type& reference; 8260b57cec5SDimitry Andric typedef typename _NodeTypes::__node_value_type_pointer pointer; 8270b57cec5SDimitry Andric 8280b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT 8290b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 8300b57cec5SDimitry Andric : __ptr_(nullptr) 8310b57cec5SDimitry Andric#endif 8320b57cec5SDimitry Andric {} 8330b57cec5SDimitry Andric 8340b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY reference operator*() const 8350b57cec5SDimitry Andric {return __get_np()->__value_;} 8360b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY pointer operator->() const 8370b57cec5SDimitry Andric {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);} 8380b57cec5SDimitry Andric 8390b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8400b57cec5SDimitry Andric __tree_iterator& operator++() { 8410b57cec5SDimitry Andric __ptr_ = static_cast<__iter_pointer>( 842*e8d8bef9SDimitry Andric _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); 8430b57cec5SDimitry Andric return *this; 8440b57cec5SDimitry Andric } 8450b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8460b57cec5SDimitry Andric __tree_iterator operator++(int) 8470b57cec5SDimitry Andric {__tree_iterator __t(*this); ++(*this); return __t;} 8480b57cec5SDimitry Andric 8490b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8500b57cec5SDimitry Andric __tree_iterator& operator--() { 851*e8d8bef9SDimitry Andric __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>( 8520b57cec5SDimitry Andric static_cast<__end_node_pointer>(__ptr_))); 8530b57cec5SDimitry Andric return *this; 8540b57cec5SDimitry Andric } 8550b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8560b57cec5SDimitry Andric __tree_iterator operator--(int) 8570b57cec5SDimitry Andric {__tree_iterator __t(*this); --(*this); return __t;} 8580b57cec5SDimitry Andric 8590b57cec5SDimitry Andric friend _LIBCPP_INLINE_VISIBILITY 8600b57cec5SDimitry Andric bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) 8610b57cec5SDimitry Andric {return __x.__ptr_ == __y.__ptr_;} 8620b57cec5SDimitry Andric friend _LIBCPP_INLINE_VISIBILITY 8630b57cec5SDimitry Andric bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) 8640b57cec5SDimitry Andric {return !(__x == __y);} 8650b57cec5SDimitry Andric 8660b57cec5SDimitry Andricprivate: 8670b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8680b57cec5SDimitry Andric explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 8690b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8700b57cec5SDimitry Andric explicit __tree_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 8710b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8720b57cec5SDimitry Andric __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); } 8730b57cec5SDimitry Andric template <class, class, class> friend class __tree; 8740b57cec5SDimitry Andric template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; 8750b57cec5SDimitry Andric template <class> friend class _LIBCPP_TEMPLATE_VIS __map_iterator; 8760b57cec5SDimitry Andric template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 8770b57cec5SDimitry Andric template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 8780b57cec5SDimitry Andric template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set; 8790b57cec5SDimitry Andric template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset; 8800b57cec5SDimitry Andric}; 8810b57cec5SDimitry Andric 8820b57cec5SDimitry Andrictemplate <class _Tp, class _NodePtr, class _DiffType> 8830b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS __tree_const_iterator 8840b57cec5SDimitry Andric{ 8850b57cec5SDimitry Andric typedef __tree_node_types<_NodePtr> _NodeTypes; 8860b57cec5SDimitry Andric typedef typename _NodeTypes::__node_pointer __node_pointer; 8870b57cec5SDimitry Andric typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 8880b57cec5SDimitry Andric typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; 8890b57cec5SDimitry Andric typedef typename _NodeTypes::__iter_pointer __iter_pointer; 8900b57cec5SDimitry Andric typedef pointer_traits<__node_pointer> __pointer_traits; 8910b57cec5SDimitry Andric 8920b57cec5SDimitry Andric __iter_pointer __ptr_; 8930b57cec5SDimitry Andric 8940b57cec5SDimitry Andricpublic: 8950b57cec5SDimitry Andric typedef bidirectional_iterator_tag iterator_category; 8960b57cec5SDimitry Andric typedef _Tp value_type; 8970b57cec5SDimitry Andric typedef _DiffType difference_type; 8980b57cec5SDimitry Andric typedef const value_type& reference; 8990b57cec5SDimitry Andric typedef typename _NodeTypes::__const_node_value_type_pointer pointer; 9000b57cec5SDimitry Andric 9010b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT 9020b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 9030b57cec5SDimitry Andric : __ptr_(nullptr) 9040b57cec5SDimitry Andric#endif 9050b57cec5SDimitry Andric {} 9060b57cec5SDimitry Andric 9070b57cec5SDimitry Andricprivate: 9080b57cec5SDimitry Andric typedef __tree_iterator<value_type, __node_pointer, difference_type> 9090b57cec5SDimitry Andric __non_const_iterator; 9100b57cec5SDimitry Andricpublic: 9110b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9120b57cec5SDimitry Andric __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT 9130b57cec5SDimitry Andric : __ptr_(__p.__ptr_) {} 9140b57cec5SDimitry Andric 9150b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY reference operator*() const 9160b57cec5SDimitry Andric {return __get_np()->__value_;} 9170b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY pointer operator->() const 9180b57cec5SDimitry Andric {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);} 9190b57cec5SDimitry Andric 9200b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9210b57cec5SDimitry Andric __tree_const_iterator& operator++() { 9220b57cec5SDimitry Andric __ptr_ = static_cast<__iter_pointer>( 923*e8d8bef9SDimitry Andric _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); 9240b57cec5SDimitry Andric return *this; 9250b57cec5SDimitry Andric } 9260b57cec5SDimitry Andric 9270b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9280b57cec5SDimitry Andric __tree_const_iterator operator++(int) 9290b57cec5SDimitry Andric {__tree_const_iterator __t(*this); ++(*this); return __t;} 9300b57cec5SDimitry Andric 9310b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9320b57cec5SDimitry Andric __tree_const_iterator& operator--() { 933*e8d8bef9SDimitry Andric __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>( 9340b57cec5SDimitry Andric static_cast<__end_node_pointer>(__ptr_))); 9350b57cec5SDimitry Andric return *this; 9360b57cec5SDimitry Andric } 9370b57cec5SDimitry Andric 9380b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9390b57cec5SDimitry Andric __tree_const_iterator operator--(int) 9400b57cec5SDimitry Andric {__tree_const_iterator __t(*this); --(*this); return __t;} 9410b57cec5SDimitry Andric 9420b57cec5SDimitry Andric friend _LIBCPP_INLINE_VISIBILITY 9430b57cec5SDimitry Andric bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 9440b57cec5SDimitry Andric {return __x.__ptr_ == __y.__ptr_;} 9450b57cec5SDimitry Andric friend _LIBCPP_INLINE_VISIBILITY 9460b57cec5SDimitry Andric bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 9470b57cec5SDimitry Andric {return !(__x == __y);} 9480b57cec5SDimitry Andric 9490b57cec5SDimitry Andricprivate: 9500b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9510b57cec5SDimitry Andric explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT 9520b57cec5SDimitry Andric : __ptr_(__p) {} 9530b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9540b57cec5SDimitry Andric explicit __tree_const_iterator(__end_node_pointer __p) _NOEXCEPT 9550b57cec5SDimitry Andric : __ptr_(__p) {} 9560b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9570b57cec5SDimitry Andric __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); } 9580b57cec5SDimitry Andric 9590b57cec5SDimitry Andric template <class, class, class> friend class __tree; 9600b57cec5SDimitry Andric template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 9610b57cec5SDimitry Andric template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 9620b57cec5SDimitry Andric template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set; 9630b57cec5SDimitry Andric template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset; 9640b57cec5SDimitry Andric template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator; 9650b57cec5SDimitry Andric 9660b57cec5SDimitry Andric}; 9670b57cec5SDimitry Andric 9680b57cec5SDimitry Andrictemplate<class _Tp, class _Compare> 9690b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 970*e8d8bef9SDimitry Andric _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Compare const&, _Tp const&, _Tp const&>::value, 9710b57cec5SDimitry Andric "the specified comparator type does not provide a viable const call operator") 9720b57cec5SDimitry Andric#endif 9730b57cec5SDimitry Andricint __diagnose_non_const_comparator(); 9740b57cec5SDimitry Andric 9750b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 9760b57cec5SDimitry Andricclass __tree 9770b57cec5SDimitry Andric{ 9780b57cec5SDimitry Andricpublic: 9790b57cec5SDimitry Andric typedef _Tp value_type; 9800b57cec5SDimitry Andric typedef _Compare value_compare; 9810b57cec5SDimitry Andric typedef _Allocator allocator_type; 9820b57cec5SDimitry Andric 9830b57cec5SDimitry Andricprivate: 9840b57cec5SDimitry Andric typedef allocator_traits<allocator_type> __alloc_traits; 9850b57cec5SDimitry Andric typedef typename __make_tree_node_types<value_type, 9860b57cec5SDimitry Andric typename __alloc_traits::void_pointer>::type 9870b57cec5SDimitry Andric _NodeTypes; 9880b57cec5SDimitry Andric typedef typename _NodeTypes::key_type key_type; 9890b57cec5SDimitry Andricpublic: 9900b57cec5SDimitry Andric typedef typename _NodeTypes::__node_value_type __node_value_type; 9910b57cec5SDimitry Andric typedef typename _NodeTypes::__container_value_type __container_value_type; 9920b57cec5SDimitry Andric 9930b57cec5SDimitry Andric typedef typename __alloc_traits::pointer pointer; 9940b57cec5SDimitry Andric typedef typename __alloc_traits::const_pointer const_pointer; 9950b57cec5SDimitry Andric typedef typename __alloc_traits::size_type size_type; 9960b57cec5SDimitry Andric typedef typename __alloc_traits::difference_type difference_type; 9970b57cec5SDimitry Andric 9980b57cec5SDimitry Andricpublic: 9990b57cec5SDimitry Andric typedef typename _NodeTypes::__void_pointer __void_pointer; 10000b57cec5SDimitry Andric 10010b57cec5SDimitry Andric typedef typename _NodeTypes::__node_type __node; 10020b57cec5SDimitry Andric typedef typename _NodeTypes::__node_pointer __node_pointer; 10030b57cec5SDimitry Andric 10040b57cec5SDimitry Andric typedef typename _NodeTypes::__node_base_type __node_base; 10050b57cec5SDimitry Andric typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 10060b57cec5SDimitry Andric 10070b57cec5SDimitry Andric typedef typename _NodeTypes::__end_node_type __end_node_t; 10080b57cec5SDimitry Andric typedef typename _NodeTypes::__end_node_pointer __end_node_ptr; 10090b57cec5SDimitry Andric 10100b57cec5SDimitry Andric typedef typename _NodeTypes::__parent_pointer __parent_pointer; 10110b57cec5SDimitry Andric typedef typename _NodeTypes::__iter_pointer __iter_pointer; 10120b57cec5SDimitry Andric 10130b57cec5SDimitry Andric typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 10140b57cec5SDimitry Andric typedef allocator_traits<__node_allocator> __node_traits; 10150b57cec5SDimitry Andric 10160b57cec5SDimitry Andricprivate: 10170b57cec5SDimitry Andric // check for sane allocator pointer rebinding semantics. Rebinding the 10180b57cec5SDimitry Andric // allocator for a new pointer type should be exactly the same as rebinding 10190b57cec5SDimitry Andric // the pointer using 'pointer_traits'. 10200b57cec5SDimitry Andric static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value), 10210b57cec5SDimitry Andric "Allocator does not rebind pointers in a sane manner."); 10220b57cec5SDimitry Andric typedef typename __rebind_alloc_helper<__node_traits, __node_base>::type 10230b57cec5SDimitry Andric __node_base_allocator; 10240b57cec5SDimitry Andric typedef allocator_traits<__node_base_allocator> __node_base_traits; 10250b57cec5SDimitry Andric static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value), 10260b57cec5SDimitry Andric "Allocator does not rebind pointers in a sane manner."); 10270b57cec5SDimitry Andric 10280b57cec5SDimitry Andricprivate: 10290b57cec5SDimitry Andric __iter_pointer __begin_node_; 10300b57cec5SDimitry Andric __compressed_pair<__end_node_t, __node_allocator> __pair1_; 10310b57cec5SDimitry Andric __compressed_pair<size_type, value_compare> __pair3_; 10320b57cec5SDimitry Andric 10330b57cec5SDimitry Andricpublic: 10340b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10350b57cec5SDimitry Andric __iter_pointer __end_node() _NOEXCEPT 10360b57cec5SDimitry Andric { 10370b57cec5SDimitry Andric return static_cast<__iter_pointer>( 10380b57cec5SDimitry Andric pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first()) 10390b57cec5SDimitry Andric ); 10400b57cec5SDimitry Andric } 10410b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10420b57cec5SDimitry Andric __iter_pointer __end_node() const _NOEXCEPT 10430b57cec5SDimitry Andric { 10440b57cec5SDimitry Andric return static_cast<__iter_pointer>( 10450b57cec5SDimitry Andric pointer_traits<__end_node_ptr>::pointer_to( 10460b57cec5SDimitry Andric const_cast<__end_node_t&>(__pair1_.first()) 10470b57cec5SDimitry Andric ) 10480b57cec5SDimitry Andric ); 10490b57cec5SDimitry Andric } 10500b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10510b57cec5SDimitry Andric __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();} 10520b57cec5SDimitry Andricprivate: 10530b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10540b57cec5SDimitry Andric const __node_allocator& __node_alloc() const _NOEXCEPT 10550b57cec5SDimitry Andric {return __pair1_.second();} 10560b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10570b57cec5SDimitry Andric __iter_pointer& __begin_node() _NOEXCEPT {return __begin_node_;} 10580b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10590b57cec5SDimitry Andric const __iter_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;} 10600b57cec5SDimitry Andricpublic: 10610b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10620b57cec5SDimitry Andric allocator_type __alloc() const _NOEXCEPT 10630b57cec5SDimitry Andric {return allocator_type(__node_alloc());} 10640b57cec5SDimitry Andricprivate: 10650b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10660b57cec5SDimitry Andric size_type& size() _NOEXCEPT {return __pair3_.first();} 10670b57cec5SDimitry Andricpublic: 10680b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10690b57cec5SDimitry Andric const size_type& size() const _NOEXCEPT {return __pair3_.first();} 10700b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10710b57cec5SDimitry Andric value_compare& value_comp() _NOEXCEPT {return __pair3_.second();} 10720b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10730b57cec5SDimitry Andric const value_compare& value_comp() const _NOEXCEPT 10740b57cec5SDimitry Andric {return __pair3_.second();} 10750b57cec5SDimitry Andricpublic: 10760b57cec5SDimitry Andric 10770b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10780b57cec5SDimitry Andric __node_pointer __root() const _NOEXCEPT 10790b57cec5SDimitry Andric {return static_cast<__node_pointer>(__end_node()->__left_);} 10800b57cec5SDimitry Andric 10810b57cec5SDimitry Andric __node_base_pointer* __root_ptr() const _NOEXCEPT { 10820b57cec5SDimitry Andric return _VSTD::addressof(__end_node()->__left_); 10830b57cec5SDimitry Andric } 10840b57cec5SDimitry Andric 10850b57cec5SDimitry Andric typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator; 10860b57cec5SDimitry Andric typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator; 10870b57cec5SDimitry Andric 10880b57cec5SDimitry Andric explicit __tree(const value_compare& __comp) 10890b57cec5SDimitry Andric _NOEXCEPT_( 10900b57cec5SDimitry Andric is_nothrow_default_constructible<__node_allocator>::value && 10910b57cec5SDimitry Andric is_nothrow_copy_constructible<value_compare>::value); 10920b57cec5SDimitry Andric explicit __tree(const allocator_type& __a); 10930b57cec5SDimitry Andric __tree(const value_compare& __comp, const allocator_type& __a); 10940b57cec5SDimitry Andric __tree(const __tree& __t); 10950b57cec5SDimitry Andric __tree& operator=(const __tree& __t); 10960b57cec5SDimitry Andric template <class _ForwardIterator> 10970b57cec5SDimitry Andric void __assign_unique(_ForwardIterator __first, _ForwardIterator __last); 10980b57cec5SDimitry Andric template <class _InputIterator> 10990b57cec5SDimitry Andric void __assign_multi(_InputIterator __first, _InputIterator __last); 11000b57cec5SDimitry Andric __tree(__tree&& __t) 11010b57cec5SDimitry Andric _NOEXCEPT_( 11020b57cec5SDimitry Andric is_nothrow_move_constructible<__node_allocator>::value && 11030b57cec5SDimitry Andric is_nothrow_move_constructible<value_compare>::value); 11040b57cec5SDimitry Andric __tree(__tree&& __t, const allocator_type& __a); 11050b57cec5SDimitry Andric __tree& operator=(__tree&& __t) 11060b57cec5SDimitry Andric _NOEXCEPT_( 11070b57cec5SDimitry Andric __node_traits::propagate_on_container_move_assignment::value && 11080b57cec5SDimitry Andric is_nothrow_move_assignable<value_compare>::value && 11090b57cec5SDimitry Andric is_nothrow_move_assignable<__node_allocator>::value); 11100b57cec5SDimitry Andric ~__tree(); 11110b57cec5SDimitry Andric 11120b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11130b57cec5SDimitry Andric iterator begin() _NOEXCEPT {return iterator(__begin_node());} 11140b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11150b57cec5SDimitry Andric const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());} 11160b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11170b57cec5SDimitry Andric iterator end() _NOEXCEPT {return iterator(__end_node());} 11180b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11190b57cec5SDimitry Andric const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());} 11200b57cec5SDimitry Andric 11210b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11220b57cec5SDimitry Andric size_type max_size() const _NOEXCEPT 1123*e8d8bef9SDimitry Andric {return _VSTD::min<size_type>( 11240b57cec5SDimitry Andric __node_traits::max_size(__node_alloc()), 11250b57cec5SDimitry Andric numeric_limits<difference_type >::max());} 11260b57cec5SDimitry Andric 11270b57cec5SDimitry Andric void clear() _NOEXCEPT; 11280b57cec5SDimitry Andric 11290b57cec5SDimitry Andric void swap(__tree& __t) 11300b57cec5SDimitry Andric#if _LIBCPP_STD_VER <= 11 11310b57cec5SDimitry Andric _NOEXCEPT_( 11320b57cec5SDimitry Andric __is_nothrow_swappable<value_compare>::value 11330b57cec5SDimitry Andric && (!__node_traits::propagate_on_container_swap::value || 11340b57cec5SDimitry Andric __is_nothrow_swappable<__node_allocator>::value) 11350b57cec5SDimitry Andric ); 11360b57cec5SDimitry Andric#else 11370b57cec5SDimitry Andric _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value); 11380b57cec5SDimitry Andric#endif 11390b57cec5SDimitry Andric 11400b57cec5SDimitry Andric template <class _Key, class ..._Args> 11410b57cec5SDimitry Andric pair<iterator, bool> 11420b57cec5SDimitry Andric __emplace_unique_key_args(_Key const&, _Args&&... __args); 11430b57cec5SDimitry Andric template <class _Key, class ..._Args> 1144*e8d8bef9SDimitry Andric pair<iterator, bool> 11450b57cec5SDimitry Andric __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...); 11460b57cec5SDimitry Andric 11470b57cec5SDimitry Andric template <class... _Args> 11480b57cec5SDimitry Andric pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); 11490b57cec5SDimitry Andric 11500b57cec5SDimitry Andric template <class... _Args> 11510b57cec5SDimitry Andric iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args); 11520b57cec5SDimitry Andric 11530b57cec5SDimitry Andric template <class... _Args> 11540b57cec5SDimitry Andric iterator __emplace_multi(_Args&&... __args); 11550b57cec5SDimitry Andric 11560b57cec5SDimitry Andric template <class... _Args> 11570b57cec5SDimitry Andric iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 11580b57cec5SDimitry Andric 11590b57cec5SDimitry Andric template <class _Pp> 11600b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11610b57cec5SDimitry Andric pair<iterator, bool> __emplace_unique(_Pp&& __x) { 11620b57cec5SDimitry Andric return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x), 11630b57cec5SDimitry Andric __can_extract_key<_Pp, key_type>()); 11640b57cec5SDimitry Andric } 11650b57cec5SDimitry Andric 11660b57cec5SDimitry Andric template <class _First, class _Second> 11670b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11680b57cec5SDimitry Andric typename enable_if< 11690b57cec5SDimitry Andric __can_extract_map_key<_First, key_type, __container_value_type>::value, 11700b57cec5SDimitry Andric pair<iterator, bool> 11710b57cec5SDimitry Andric >::type __emplace_unique(_First&& __f, _Second&& __s) { 11720b57cec5SDimitry Andric return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f), 11730b57cec5SDimitry Andric _VSTD::forward<_Second>(__s)); 11740b57cec5SDimitry Andric } 11750b57cec5SDimitry Andric 11760b57cec5SDimitry Andric template <class... _Args> 11770b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11780b57cec5SDimitry Andric pair<iterator, bool> __emplace_unique(_Args&&... __args) { 11790b57cec5SDimitry Andric return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...); 11800b57cec5SDimitry Andric } 11810b57cec5SDimitry Andric 11820b57cec5SDimitry Andric template <class _Pp> 11830b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11840b57cec5SDimitry Andric pair<iterator, bool> 11850b57cec5SDimitry Andric __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { 11860b57cec5SDimitry Andric return __emplace_unique_impl(_VSTD::forward<_Pp>(__x)); 11870b57cec5SDimitry Andric } 11880b57cec5SDimitry Andric 11890b57cec5SDimitry Andric template <class _Pp> 11900b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11910b57cec5SDimitry Andric pair<iterator, bool> 11920b57cec5SDimitry Andric __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { 11930b57cec5SDimitry Andric return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x)); 11940b57cec5SDimitry Andric } 11950b57cec5SDimitry Andric 11960b57cec5SDimitry Andric template <class _Pp> 11970b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11980b57cec5SDimitry Andric pair<iterator, bool> 11990b57cec5SDimitry Andric __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { 12000b57cec5SDimitry Andric return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x)); 12010b57cec5SDimitry Andric } 12020b57cec5SDimitry Andric 12030b57cec5SDimitry Andric template <class _Pp> 12040b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12050b57cec5SDimitry Andric iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) { 12060b57cec5SDimitry Andric return __emplace_hint_unique_extract_key(__p, _VSTD::forward<_Pp>(__x), 12070b57cec5SDimitry Andric __can_extract_key<_Pp, key_type>()); 12080b57cec5SDimitry Andric } 12090b57cec5SDimitry Andric 12100b57cec5SDimitry Andric template <class _First, class _Second> 12110b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12120b57cec5SDimitry Andric typename enable_if< 12130b57cec5SDimitry Andric __can_extract_map_key<_First, key_type, __container_value_type>::value, 12140b57cec5SDimitry Andric iterator 12150b57cec5SDimitry Andric >::type __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) { 12160b57cec5SDimitry Andric return __emplace_hint_unique_key_args(__p, __f, 12170b57cec5SDimitry Andric _VSTD::forward<_First>(__f), 1218*e8d8bef9SDimitry Andric _VSTD::forward<_Second>(__s)).first; 12190b57cec5SDimitry Andric } 12200b57cec5SDimitry Andric 12210b57cec5SDimitry Andric template <class... _Args> 12220b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12230b57cec5SDimitry Andric iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) { 12240b57cec5SDimitry Andric return __emplace_hint_unique_impl(__p, _VSTD::forward<_Args>(__args)...); 12250b57cec5SDimitry Andric } 12260b57cec5SDimitry Andric 12270b57cec5SDimitry Andric template <class _Pp> 12280b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12290b57cec5SDimitry Andric iterator 12300b57cec5SDimitry Andric __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) { 12310b57cec5SDimitry Andric return __emplace_hint_unique_impl(__p, _VSTD::forward<_Pp>(__x)); 12320b57cec5SDimitry Andric } 12330b57cec5SDimitry Andric 12340b57cec5SDimitry Andric template <class _Pp> 12350b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12360b57cec5SDimitry Andric iterator 12370b57cec5SDimitry Andric __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) { 1238*e8d8bef9SDimitry Andric return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x)).first; 12390b57cec5SDimitry Andric } 12400b57cec5SDimitry Andric 12410b57cec5SDimitry Andric template <class _Pp> 12420b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12430b57cec5SDimitry Andric iterator 12440b57cec5SDimitry Andric __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) { 1245*e8d8bef9SDimitry Andric return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x)).first; 12460b57cec5SDimitry Andric } 12470b57cec5SDimitry Andric 12480b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12490b57cec5SDimitry Andric pair<iterator, bool> __insert_unique(const __container_value_type& __v) { 12500b57cec5SDimitry Andric return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v); 12510b57cec5SDimitry Andric } 12520b57cec5SDimitry Andric 12530b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12540b57cec5SDimitry Andric iterator __insert_unique(const_iterator __p, const __container_value_type& __v) { 1255*e8d8bef9SDimitry Andric return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v).first; 12560b57cec5SDimitry Andric } 12570b57cec5SDimitry Andric 12580b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12590b57cec5SDimitry Andric pair<iterator, bool> __insert_unique(__container_value_type&& __v) { 12600b57cec5SDimitry Andric return __emplace_unique_key_args(_NodeTypes::__get_key(__v), _VSTD::move(__v)); 12610b57cec5SDimitry Andric } 12620b57cec5SDimitry Andric 12630b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12640b57cec5SDimitry Andric iterator __insert_unique(const_iterator __p, __container_value_type&& __v) { 1265*e8d8bef9SDimitry Andric return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v)).first; 12660b57cec5SDimitry Andric } 12670b57cec5SDimitry Andric 12680b57cec5SDimitry Andric template <class _Vp, class = typename enable_if< 12690b57cec5SDimitry Andric !is_same<typename __unconstref<_Vp>::type, 12700b57cec5SDimitry Andric __container_value_type 12710b57cec5SDimitry Andric >::value 12720b57cec5SDimitry Andric >::type> 12730b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12740b57cec5SDimitry Andric pair<iterator, bool> __insert_unique(_Vp&& __v) { 12750b57cec5SDimitry Andric return __emplace_unique(_VSTD::forward<_Vp>(__v)); 12760b57cec5SDimitry Andric } 12770b57cec5SDimitry Andric 12780b57cec5SDimitry Andric template <class _Vp, class = typename enable_if< 12790b57cec5SDimitry Andric !is_same<typename __unconstref<_Vp>::type, 12800b57cec5SDimitry Andric __container_value_type 12810b57cec5SDimitry Andric >::value 12820b57cec5SDimitry Andric >::type> 12830b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12840b57cec5SDimitry Andric iterator __insert_unique(const_iterator __p, _Vp&& __v) { 12850b57cec5SDimitry Andric return __emplace_hint_unique(__p, _VSTD::forward<_Vp>(__v)); 12860b57cec5SDimitry Andric } 12870b57cec5SDimitry Andric 12880b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12890b57cec5SDimitry Andric iterator __insert_multi(__container_value_type&& __v) { 12900b57cec5SDimitry Andric return __emplace_multi(_VSTD::move(__v)); 12910b57cec5SDimitry Andric } 12920b57cec5SDimitry Andric 12930b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12940b57cec5SDimitry Andric iterator __insert_multi(const_iterator __p, __container_value_type&& __v) { 12950b57cec5SDimitry Andric return __emplace_hint_multi(__p, _VSTD::move(__v)); 12960b57cec5SDimitry Andric } 12970b57cec5SDimitry Andric 12980b57cec5SDimitry Andric template <class _Vp> 12990b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13000b57cec5SDimitry Andric iterator __insert_multi(_Vp&& __v) { 13010b57cec5SDimitry Andric return __emplace_multi(_VSTD::forward<_Vp>(__v)); 13020b57cec5SDimitry Andric } 13030b57cec5SDimitry Andric 13040b57cec5SDimitry Andric template <class _Vp> 13050b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13060b57cec5SDimitry Andric iterator __insert_multi(const_iterator __p, _Vp&& __v) { 13070b57cec5SDimitry Andric return __emplace_hint_multi(__p, _VSTD::forward<_Vp>(__v)); 13080b57cec5SDimitry Andric } 13090b57cec5SDimitry Andric 13100b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13110b57cec5SDimitry Andric pair<iterator, bool> __node_assign_unique(const __container_value_type& __v, __node_pointer __dest); 13120b57cec5SDimitry Andric 13130b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13140b57cec5SDimitry Andric iterator __node_insert_multi(__node_pointer __nd); 13150b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13160b57cec5SDimitry Andric iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); 13170b57cec5SDimitry Andric 13180b57cec5SDimitry Andric 13190b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY iterator 13200b57cec5SDimitry Andric __remove_node_pointer(__node_pointer) _NOEXCEPT; 13210b57cec5SDimitry Andric 13220b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 13230b57cec5SDimitry Andric template <class _NodeHandle, class _InsertReturnType> 13240b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13250b57cec5SDimitry Andric _InsertReturnType __node_handle_insert_unique(_NodeHandle&&); 13260b57cec5SDimitry Andric template <class _NodeHandle> 13270b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13280b57cec5SDimitry Andric iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); 13290b57cec5SDimitry Andric template <class _Tree> 13300b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13310b57cec5SDimitry Andric void __node_handle_merge_unique(_Tree& __source); 13320b57cec5SDimitry Andric 13330b57cec5SDimitry Andric template <class _NodeHandle> 13340b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13350b57cec5SDimitry Andric iterator __node_handle_insert_multi(_NodeHandle&&); 13360b57cec5SDimitry Andric template <class _NodeHandle> 13370b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13380b57cec5SDimitry Andric iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); 13390b57cec5SDimitry Andric template <class _Tree> 13400b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13410b57cec5SDimitry Andric void __node_handle_merge_multi(_Tree& __source); 13420b57cec5SDimitry Andric 13430b57cec5SDimitry Andric 13440b57cec5SDimitry Andric template <class _NodeHandle> 13450b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13460b57cec5SDimitry Andric _NodeHandle __node_handle_extract(key_type const&); 13470b57cec5SDimitry Andric template <class _NodeHandle> 13480b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13490b57cec5SDimitry Andric _NodeHandle __node_handle_extract(const_iterator); 13500b57cec5SDimitry Andric#endif 13510b57cec5SDimitry Andric 13520b57cec5SDimitry Andric iterator erase(const_iterator __p); 13530b57cec5SDimitry Andric iterator erase(const_iterator __f, const_iterator __l); 13540b57cec5SDimitry Andric template <class _Key> 13550b57cec5SDimitry Andric size_type __erase_unique(const _Key& __k); 13560b57cec5SDimitry Andric template <class _Key> 13570b57cec5SDimitry Andric size_type __erase_multi(const _Key& __k); 13580b57cec5SDimitry Andric 13590b57cec5SDimitry Andric void __insert_node_at(__parent_pointer __parent, 13600b57cec5SDimitry Andric __node_base_pointer& __child, 13610b57cec5SDimitry Andric __node_base_pointer __new_node) _NOEXCEPT; 13620b57cec5SDimitry Andric 13630b57cec5SDimitry Andric template <class _Key> 13640b57cec5SDimitry Andric iterator find(const _Key& __v); 13650b57cec5SDimitry Andric template <class _Key> 13660b57cec5SDimitry Andric const_iterator find(const _Key& __v) const; 13670b57cec5SDimitry Andric 13680b57cec5SDimitry Andric template <class _Key> 13690b57cec5SDimitry Andric size_type __count_unique(const _Key& __k) const; 13700b57cec5SDimitry Andric template <class _Key> 13710b57cec5SDimitry Andric size_type __count_multi(const _Key& __k) const; 13720b57cec5SDimitry Andric 13730b57cec5SDimitry Andric template <class _Key> 13740b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13750b57cec5SDimitry Andric iterator lower_bound(const _Key& __v) 13760b57cec5SDimitry Andric {return __lower_bound(__v, __root(), __end_node());} 13770b57cec5SDimitry Andric template <class _Key> 13780b57cec5SDimitry Andric iterator __lower_bound(const _Key& __v, 13790b57cec5SDimitry Andric __node_pointer __root, 13800b57cec5SDimitry Andric __iter_pointer __result); 13810b57cec5SDimitry Andric template <class _Key> 13820b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13830b57cec5SDimitry Andric const_iterator lower_bound(const _Key& __v) const 13840b57cec5SDimitry Andric {return __lower_bound(__v, __root(), __end_node());} 13850b57cec5SDimitry Andric template <class _Key> 13860b57cec5SDimitry Andric const_iterator __lower_bound(const _Key& __v, 13870b57cec5SDimitry Andric __node_pointer __root, 13880b57cec5SDimitry Andric __iter_pointer __result) const; 13890b57cec5SDimitry Andric template <class _Key> 13900b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13910b57cec5SDimitry Andric iterator upper_bound(const _Key& __v) 13920b57cec5SDimitry Andric {return __upper_bound(__v, __root(), __end_node());} 13930b57cec5SDimitry Andric template <class _Key> 13940b57cec5SDimitry Andric iterator __upper_bound(const _Key& __v, 13950b57cec5SDimitry Andric __node_pointer __root, 13960b57cec5SDimitry Andric __iter_pointer __result); 13970b57cec5SDimitry Andric template <class _Key> 13980b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13990b57cec5SDimitry Andric const_iterator upper_bound(const _Key& __v) const 14000b57cec5SDimitry Andric {return __upper_bound(__v, __root(), __end_node());} 14010b57cec5SDimitry Andric template <class _Key> 14020b57cec5SDimitry Andric const_iterator __upper_bound(const _Key& __v, 14030b57cec5SDimitry Andric __node_pointer __root, 14040b57cec5SDimitry Andric __iter_pointer __result) const; 14050b57cec5SDimitry Andric template <class _Key> 14060b57cec5SDimitry Andric pair<iterator, iterator> 14070b57cec5SDimitry Andric __equal_range_unique(const _Key& __k); 14080b57cec5SDimitry Andric template <class _Key> 14090b57cec5SDimitry Andric pair<const_iterator, const_iterator> 14100b57cec5SDimitry Andric __equal_range_unique(const _Key& __k) const; 14110b57cec5SDimitry Andric 14120b57cec5SDimitry Andric template <class _Key> 14130b57cec5SDimitry Andric pair<iterator, iterator> 14140b57cec5SDimitry Andric __equal_range_multi(const _Key& __k); 14150b57cec5SDimitry Andric template <class _Key> 14160b57cec5SDimitry Andric pair<const_iterator, const_iterator> 14170b57cec5SDimitry Andric __equal_range_multi(const _Key& __k) const; 14180b57cec5SDimitry Andric 14190b57cec5SDimitry Andric typedef __tree_node_destructor<__node_allocator> _Dp; 14200b57cec5SDimitry Andric typedef unique_ptr<__node, _Dp> __node_holder; 14210b57cec5SDimitry Andric 14220b57cec5SDimitry Andric __node_holder remove(const_iterator __p) _NOEXCEPT; 14230b57cec5SDimitry Andricprivate: 14240b57cec5SDimitry Andric __node_base_pointer& 14250b57cec5SDimitry Andric __find_leaf_low(__parent_pointer& __parent, const key_type& __v); 14260b57cec5SDimitry Andric __node_base_pointer& 14270b57cec5SDimitry Andric __find_leaf_high(__parent_pointer& __parent, const key_type& __v); 14280b57cec5SDimitry Andric __node_base_pointer& 14290b57cec5SDimitry Andric __find_leaf(const_iterator __hint, 14300b57cec5SDimitry Andric __parent_pointer& __parent, const key_type& __v); 1431*e8d8bef9SDimitry Andric // FIXME: Make this function const qualified. Unfortunately doing so 14320b57cec5SDimitry Andric // breaks existing code which uses non-const callable comparators. 14330b57cec5SDimitry Andric template <class _Key> 14340b57cec5SDimitry Andric __node_base_pointer& 14350b57cec5SDimitry Andric __find_equal(__parent_pointer& __parent, const _Key& __v); 14360b57cec5SDimitry Andric template <class _Key> 14370b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY __node_base_pointer& 14380b57cec5SDimitry Andric __find_equal(__parent_pointer& __parent, const _Key& __v) const { 14390b57cec5SDimitry Andric return const_cast<__tree*>(this)->__find_equal(__parent, __v); 14400b57cec5SDimitry Andric } 14410b57cec5SDimitry Andric template <class _Key> 14420b57cec5SDimitry Andric __node_base_pointer& 14430b57cec5SDimitry Andric __find_equal(const_iterator __hint, __parent_pointer& __parent, 14440b57cec5SDimitry Andric __node_base_pointer& __dummy, 14450b57cec5SDimitry Andric const _Key& __v); 14460b57cec5SDimitry Andric 14470b57cec5SDimitry Andric template <class ..._Args> 14480b57cec5SDimitry Andric __node_holder __construct_node(_Args&& ...__args); 14490b57cec5SDimitry Andric 14500b57cec5SDimitry Andric void destroy(__node_pointer __nd) _NOEXCEPT; 14510b57cec5SDimitry Andric 14520b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14530b57cec5SDimitry Andric void __copy_assign_alloc(const __tree& __t) 14540b57cec5SDimitry Andric {__copy_assign_alloc(__t, integral_constant<bool, 14550b57cec5SDimitry Andric __node_traits::propagate_on_container_copy_assignment::value>());} 14560b57cec5SDimitry Andric 14570b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14580b57cec5SDimitry Andric void __copy_assign_alloc(const __tree& __t, true_type) 14590b57cec5SDimitry Andric { 14600b57cec5SDimitry Andric if (__node_alloc() != __t.__node_alloc()) 14610b57cec5SDimitry Andric clear(); 14620b57cec5SDimitry Andric __node_alloc() = __t.__node_alloc(); 14630b57cec5SDimitry Andric } 14640b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14650b57cec5SDimitry Andric void __copy_assign_alloc(const __tree&, false_type) {} 14660b57cec5SDimitry Andric 14670b57cec5SDimitry Andric void __move_assign(__tree& __t, false_type); 14680b57cec5SDimitry Andric void __move_assign(__tree& __t, true_type) 14690b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 14700b57cec5SDimitry Andric is_nothrow_move_assignable<__node_allocator>::value); 14710b57cec5SDimitry Andric 14720b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14730b57cec5SDimitry Andric void __move_assign_alloc(__tree& __t) 14740b57cec5SDimitry Andric _NOEXCEPT_( 14750b57cec5SDimitry Andric !__node_traits::propagate_on_container_move_assignment::value || 14760b57cec5SDimitry Andric is_nothrow_move_assignable<__node_allocator>::value) 14770b57cec5SDimitry Andric {__move_assign_alloc(__t, integral_constant<bool, 14780b57cec5SDimitry Andric __node_traits::propagate_on_container_move_assignment::value>());} 14790b57cec5SDimitry Andric 14800b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14810b57cec5SDimitry Andric void __move_assign_alloc(__tree& __t, true_type) 14820b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 14830b57cec5SDimitry Andric {__node_alloc() = _VSTD::move(__t.__node_alloc());} 14840b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14850b57cec5SDimitry Andric void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {} 14860b57cec5SDimitry Andric 14870b57cec5SDimitry Andric struct _DetachedTreeCache { 14880b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14890b57cec5SDimitry Andric explicit _DetachedTreeCache(__tree *__t) _NOEXCEPT : __t_(__t), 14900b57cec5SDimitry Andric __cache_root_(__detach_from_tree(__t)) { 14910b57cec5SDimitry Andric __advance(); 14920b57cec5SDimitry Andric } 14930b57cec5SDimitry Andric 14940b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14950b57cec5SDimitry Andric __node_pointer __get() const _NOEXCEPT { 14960b57cec5SDimitry Andric return __cache_elem_; 14970b57cec5SDimitry Andric } 14980b57cec5SDimitry Andric 14990b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 15000b57cec5SDimitry Andric void __advance() _NOEXCEPT { 15010b57cec5SDimitry Andric __cache_elem_ = __cache_root_; 15020b57cec5SDimitry Andric if (__cache_root_) { 15030b57cec5SDimitry Andric __cache_root_ = __detach_next(__cache_root_); 15040b57cec5SDimitry Andric } 15050b57cec5SDimitry Andric } 15060b57cec5SDimitry Andric 15070b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 15080b57cec5SDimitry Andric ~_DetachedTreeCache() { 15090b57cec5SDimitry Andric __t_->destroy(__cache_elem_); 15100b57cec5SDimitry Andric if (__cache_root_) { 15110b57cec5SDimitry Andric while (__cache_root_->__parent_ != nullptr) 15120b57cec5SDimitry Andric __cache_root_ = static_cast<__node_pointer>(__cache_root_->__parent_); 15130b57cec5SDimitry Andric __t_->destroy(__cache_root_); 15140b57cec5SDimitry Andric } 15150b57cec5SDimitry Andric } 15160b57cec5SDimitry Andric 15170b57cec5SDimitry Andric _DetachedTreeCache(_DetachedTreeCache const&) = delete; 15180b57cec5SDimitry Andric _DetachedTreeCache& operator=(_DetachedTreeCache const&) = delete; 15190b57cec5SDimitry Andric 15200b57cec5SDimitry Andric private: 15210b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 15220b57cec5SDimitry Andric static __node_pointer __detach_from_tree(__tree *__t) _NOEXCEPT; 15230b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 15240b57cec5SDimitry Andric static __node_pointer __detach_next(__node_pointer) _NOEXCEPT; 15250b57cec5SDimitry Andric 15260b57cec5SDimitry Andric __tree *__t_; 15270b57cec5SDimitry Andric __node_pointer __cache_root_; 15280b57cec5SDimitry Andric __node_pointer __cache_elem_; 15290b57cec5SDimitry Andric }; 15300b57cec5SDimitry Andric 15310b57cec5SDimitry Andric 15320b57cec5SDimitry Andric template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; 15330b57cec5SDimitry Andric template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; 15340b57cec5SDimitry Andric}; 15350b57cec5SDimitry Andric 15360b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 15370b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) 15380b57cec5SDimitry Andric _NOEXCEPT_( 15390b57cec5SDimitry Andric is_nothrow_default_constructible<__node_allocator>::value && 15400b57cec5SDimitry Andric is_nothrow_copy_constructible<value_compare>::value) 15410b57cec5SDimitry Andric : __pair3_(0, __comp) 15420b57cec5SDimitry Andric{ 15430b57cec5SDimitry Andric __begin_node() = __end_node(); 15440b57cec5SDimitry Andric} 15450b57cec5SDimitry Andric 15460b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 15470b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) 15480b57cec5SDimitry Andric : __begin_node_(__iter_pointer()), 1549480093f4SDimitry Andric __pair1_(__default_init_tag(), __node_allocator(__a)), 1550480093f4SDimitry Andric __pair3_(0, __default_init_tag()) 15510b57cec5SDimitry Andric{ 15520b57cec5SDimitry Andric __begin_node() = __end_node(); 15530b57cec5SDimitry Andric} 15540b57cec5SDimitry Andric 15550b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 15560b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, 15570b57cec5SDimitry Andric const allocator_type& __a) 15580b57cec5SDimitry Andric : __begin_node_(__iter_pointer()), 1559480093f4SDimitry Andric __pair1_(__default_init_tag(), __node_allocator(__a)), 15600b57cec5SDimitry Andric __pair3_(0, __comp) 15610b57cec5SDimitry Andric{ 15620b57cec5SDimitry Andric __begin_node() = __end_node(); 15630b57cec5SDimitry Andric} 15640b57cec5SDimitry Andric 15650b57cec5SDimitry Andric// Precondition: size() != 0 15660b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 15670b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::__node_pointer 15680b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree *__t) _NOEXCEPT 15690b57cec5SDimitry Andric{ 15700b57cec5SDimitry Andric __node_pointer __cache = static_cast<__node_pointer>(__t->__begin_node()); 15710b57cec5SDimitry Andric __t->__begin_node() = __t->__end_node(); 15720b57cec5SDimitry Andric __t->__end_node()->__left_->__parent_ = nullptr; 15730b57cec5SDimitry Andric __t->__end_node()->__left_ = nullptr; 15740b57cec5SDimitry Andric __t->size() = 0; 15750b57cec5SDimitry Andric // __cache->__left_ == nullptr 15760b57cec5SDimitry Andric if (__cache->__right_ != nullptr) 15770b57cec5SDimitry Andric __cache = static_cast<__node_pointer>(__cache->__right_); 15780b57cec5SDimitry Andric // __cache->__left_ == nullptr 15790b57cec5SDimitry Andric // __cache->__right_ == nullptr 15800b57cec5SDimitry Andric return __cache; 15810b57cec5SDimitry Andric} 15820b57cec5SDimitry Andric 15830b57cec5SDimitry Andric// Precondition: __cache != nullptr 15840b57cec5SDimitry Andric// __cache->left_ == nullptr 15850b57cec5SDimitry Andric// __cache->right_ == nullptr 15860b57cec5SDimitry Andric// This is no longer a red-black tree 15870b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 15880b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::__node_pointer 15890b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT 15900b57cec5SDimitry Andric{ 15910b57cec5SDimitry Andric if (__cache->__parent_ == nullptr) 15920b57cec5SDimitry Andric return nullptr; 1593*e8d8bef9SDimitry Andric if (_VSTD::__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) 15940b57cec5SDimitry Andric { 15950b57cec5SDimitry Andric __cache->__parent_->__left_ = nullptr; 15960b57cec5SDimitry Andric __cache = static_cast<__node_pointer>(__cache->__parent_); 15970b57cec5SDimitry Andric if (__cache->__right_ == nullptr) 15980b57cec5SDimitry Andric return __cache; 1599*e8d8bef9SDimitry Andric return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__right_)); 16000b57cec5SDimitry Andric } 16010b57cec5SDimitry Andric // __cache is right child 16020b57cec5SDimitry Andric __cache->__parent_unsafe()->__right_ = nullptr; 16030b57cec5SDimitry Andric __cache = static_cast<__node_pointer>(__cache->__parent_); 16040b57cec5SDimitry Andric if (__cache->__left_ == nullptr) 16050b57cec5SDimitry Andric return __cache; 1606*e8d8bef9SDimitry Andric return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__left_)); 16070b57cec5SDimitry Andric} 16080b57cec5SDimitry Andric 16090b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 16100b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>& 16110b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) 16120b57cec5SDimitry Andric{ 16130b57cec5SDimitry Andric if (this != &__t) 16140b57cec5SDimitry Andric { 16150b57cec5SDimitry Andric value_comp() = __t.value_comp(); 16160b57cec5SDimitry Andric __copy_assign_alloc(__t); 16170b57cec5SDimitry Andric __assign_multi(__t.begin(), __t.end()); 16180b57cec5SDimitry Andric } 16190b57cec5SDimitry Andric return *this; 16200b57cec5SDimitry Andric} 16210b57cec5SDimitry Andric 16220b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 16230b57cec5SDimitry Andrictemplate <class _ForwardIterator> 16240b57cec5SDimitry Andricvoid 16250b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last) 16260b57cec5SDimitry Andric{ 16270b57cec5SDimitry Andric typedef iterator_traits<_ForwardIterator> _ITraits; 16280b57cec5SDimitry Andric typedef typename _ITraits::value_type _ItValueType; 16290b57cec5SDimitry Andric static_assert((is_same<_ItValueType, __container_value_type>::value), 16300b57cec5SDimitry Andric "__assign_unique may only be called with the containers value type"); 1631480093f4SDimitry Andric static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value, 16320b57cec5SDimitry Andric "__assign_unique requires a forward iterator"); 16330b57cec5SDimitry Andric if (size() != 0) 16340b57cec5SDimitry Andric { 16350b57cec5SDimitry Andric _DetachedTreeCache __cache(this); 16360b57cec5SDimitry Andric for (; __cache.__get() != nullptr && __first != __last; ++__first) { 16370b57cec5SDimitry Andric if (__node_assign_unique(*__first, __cache.__get()).second) 16380b57cec5SDimitry Andric __cache.__advance(); 16390b57cec5SDimitry Andric } 16400b57cec5SDimitry Andric } 16410b57cec5SDimitry Andric for (; __first != __last; ++__first) 16420b57cec5SDimitry Andric __insert_unique(*__first); 16430b57cec5SDimitry Andric} 16440b57cec5SDimitry Andric 16450b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 16460b57cec5SDimitry Andrictemplate <class _InputIterator> 16470b57cec5SDimitry Andricvoid 16480b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) 16490b57cec5SDimitry Andric{ 16500b57cec5SDimitry Andric typedef iterator_traits<_InputIterator> _ITraits; 16510b57cec5SDimitry Andric typedef typename _ITraits::value_type _ItValueType; 16520b57cec5SDimitry Andric static_assert((is_same<_ItValueType, __container_value_type>::value || 16530b57cec5SDimitry Andric is_same<_ItValueType, __node_value_type>::value), 16540b57cec5SDimitry Andric "__assign_multi may only be called with the containers value type" 16550b57cec5SDimitry Andric " or the nodes value type"); 16560b57cec5SDimitry Andric if (size() != 0) 16570b57cec5SDimitry Andric { 16580b57cec5SDimitry Andric _DetachedTreeCache __cache(this); 16590b57cec5SDimitry Andric for (; __cache.__get() && __first != __last; ++__first) { 16600b57cec5SDimitry Andric __cache.__get()->__value_ = *__first; 16610b57cec5SDimitry Andric __node_insert_multi(__cache.__get()); 16620b57cec5SDimitry Andric __cache.__advance(); 16630b57cec5SDimitry Andric } 16640b57cec5SDimitry Andric } 16650b57cec5SDimitry Andric for (; __first != __last; ++__first) 16660b57cec5SDimitry Andric __insert_multi(_NodeTypes::__get_value(*__first)); 16670b57cec5SDimitry Andric} 16680b57cec5SDimitry Andric 16690b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 16700b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) 16710b57cec5SDimitry Andric : __begin_node_(__iter_pointer()), 1672480093f4SDimitry Andric __pair1_(__default_init_tag(), __node_traits::select_on_container_copy_construction(__t.__node_alloc())), 16730b57cec5SDimitry Andric __pair3_(0, __t.value_comp()) 16740b57cec5SDimitry Andric{ 16750b57cec5SDimitry Andric __begin_node() = __end_node(); 16760b57cec5SDimitry Andric} 16770b57cec5SDimitry Andric 16780b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 16790b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) 16800b57cec5SDimitry Andric _NOEXCEPT_( 16810b57cec5SDimitry Andric is_nothrow_move_constructible<__node_allocator>::value && 16820b57cec5SDimitry Andric is_nothrow_move_constructible<value_compare>::value) 16830b57cec5SDimitry Andric : __begin_node_(_VSTD::move(__t.__begin_node_)), 16840b57cec5SDimitry Andric __pair1_(_VSTD::move(__t.__pair1_)), 16850b57cec5SDimitry Andric __pair3_(_VSTD::move(__t.__pair3_)) 16860b57cec5SDimitry Andric{ 16870b57cec5SDimitry Andric if (size() == 0) 16880b57cec5SDimitry Andric __begin_node() = __end_node(); 16890b57cec5SDimitry Andric else 16900b57cec5SDimitry Andric { 16910b57cec5SDimitry Andric __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 16920b57cec5SDimitry Andric __t.__begin_node() = __t.__end_node(); 16930b57cec5SDimitry Andric __t.__end_node()->__left_ = nullptr; 16940b57cec5SDimitry Andric __t.size() = 0; 16950b57cec5SDimitry Andric } 16960b57cec5SDimitry Andric} 16970b57cec5SDimitry Andric 16980b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 16990b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a) 1700480093f4SDimitry Andric : __pair1_(__default_init_tag(), __node_allocator(__a)), 17010b57cec5SDimitry Andric __pair3_(0, _VSTD::move(__t.value_comp())) 17020b57cec5SDimitry Andric{ 17030b57cec5SDimitry Andric if (__a == __t.__alloc()) 17040b57cec5SDimitry Andric { 17050b57cec5SDimitry Andric if (__t.size() == 0) 17060b57cec5SDimitry Andric __begin_node() = __end_node(); 17070b57cec5SDimitry Andric else 17080b57cec5SDimitry Andric { 17090b57cec5SDimitry Andric __begin_node() = __t.__begin_node(); 17100b57cec5SDimitry Andric __end_node()->__left_ = __t.__end_node()->__left_; 17110b57cec5SDimitry Andric __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 17120b57cec5SDimitry Andric size() = __t.size(); 17130b57cec5SDimitry Andric __t.__begin_node() = __t.__end_node(); 17140b57cec5SDimitry Andric __t.__end_node()->__left_ = nullptr; 17150b57cec5SDimitry Andric __t.size() = 0; 17160b57cec5SDimitry Andric } 17170b57cec5SDimitry Andric } 17180b57cec5SDimitry Andric else 17190b57cec5SDimitry Andric { 17200b57cec5SDimitry Andric __begin_node() = __end_node(); 17210b57cec5SDimitry Andric } 17220b57cec5SDimitry Andric} 17230b57cec5SDimitry Andric 17240b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 17250b57cec5SDimitry Andricvoid 17260b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) 17270b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 17280b57cec5SDimitry Andric is_nothrow_move_assignable<__node_allocator>::value) 17290b57cec5SDimitry Andric{ 17300b57cec5SDimitry Andric destroy(static_cast<__node_pointer>(__end_node()->__left_)); 17310b57cec5SDimitry Andric __begin_node_ = __t.__begin_node_; 17320b57cec5SDimitry Andric __pair1_.first() = __t.__pair1_.first(); 17330b57cec5SDimitry Andric __move_assign_alloc(__t); 17340b57cec5SDimitry Andric __pair3_ = _VSTD::move(__t.__pair3_); 17350b57cec5SDimitry Andric if (size() == 0) 17360b57cec5SDimitry Andric __begin_node() = __end_node(); 17370b57cec5SDimitry Andric else 17380b57cec5SDimitry Andric { 17390b57cec5SDimitry Andric __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 17400b57cec5SDimitry Andric __t.__begin_node() = __t.__end_node(); 17410b57cec5SDimitry Andric __t.__end_node()->__left_ = nullptr; 17420b57cec5SDimitry Andric __t.size() = 0; 17430b57cec5SDimitry Andric } 17440b57cec5SDimitry Andric} 17450b57cec5SDimitry Andric 17460b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 17470b57cec5SDimitry Andricvoid 17480b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) 17490b57cec5SDimitry Andric{ 17500b57cec5SDimitry Andric if (__node_alloc() == __t.__node_alloc()) 17510b57cec5SDimitry Andric __move_assign(__t, true_type()); 17520b57cec5SDimitry Andric else 17530b57cec5SDimitry Andric { 17540b57cec5SDimitry Andric value_comp() = _VSTD::move(__t.value_comp()); 17550b57cec5SDimitry Andric const_iterator __e = end(); 17560b57cec5SDimitry Andric if (size() != 0) 17570b57cec5SDimitry Andric { 17580b57cec5SDimitry Andric _DetachedTreeCache __cache(this); 17590b57cec5SDimitry Andric while (__cache.__get() != nullptr && __t.size() != 0) { 17600b57cec5SDimitry Andric __cache.__get()->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_); 17610b57cec5SDimitry Andric __node_insert_multi(__cache.__get()); 17620b57cec5SDimitry Andric __cache.__advance(); 17630b57cec5SDimitry Andric } 17640b57cec5SDimitry Andric } 17650b57cec5SDimitry Andric while (__t.size() != 0) 17660b57cec5SDimitry Andric __insert_multi(__e, _NodeTypes::__move(__t.remove(__t.begin())->__value_)); 17670b57cec5SDimitry Andric } 17680b57cec5SDimitry Andric} 17690b57cec5SDimitry Andric 17700b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 17710b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>& 17720b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) 17730b57cec5SDimitry Andric _NOEXCEPT_( 17740b57cec5SDimitry Andric __node_traits::propagate_on_container_move_assignment::value && 17750b57cec5SDimitry Andric is_nothrow_move_assignable<value_compare>::value && 17760b57cec5SDimitry Andric is_nothrow_move_assignable<__node_allocator>::value) 17770b57cec5SDimitry Andric 17780b57cec5SDimitry Andric{ 17790b57cec5SDimitry Andric __move_assign(__t, integral_constant<bool, 17800b57cec5SDimitry Andric __node_traits::propagate_on_container_move_assignment::value>()); 17810b57cec5SDimitry Andric return *this; 17820b57cec5SDimitry Andric} 17830b57cec5SDimitry Andric 17840b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 17850b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::~__tree() 17860b57cec5SDimitry Andric{ 17870b57cec5SDimitry Andric static_assert((is_copy_constructible<value_compare>::value), 17880b57cec5SDimitry Andric "Comparator must be copy-constructible."); 17890b57cec5SDimitry Andric destroy(__root()); 17900b57cec5SDimitry Andric} 17910b57cec5SDimitry Andric 17920b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 17930b57cec5SDimitry Andricvoid 17940b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT 17950b57cec5SDimitry Andric{ 17960b57cec5SDimitry Andric if (__nd != nullptr) 17970b57cec5SDimitry Andric { 17980b57cec5SDimitry Andric destroy(static_cast<__node_pointer>(__nd->__left_)); 17990b57cec5SDimitry Andric destroy(static_cast<__node_pointer>(__nd->__right_)); 18000b57cec5SDimitry Andric __node_allocator& __na = __node_alloc(); 18010b57cec5SDimitry Andric __node_traits::destroy(__na, _NodeTypes::__get_ptr(__nd->__value_)); 18020b57cec5SDimitry Andric __node_traits::deallocate(__na, __nd, 1); 18030b57cec5SDimitry Andric } 18040b57cec5SDimitry Andric} 18050b57cec5SDimitry Andric 18060b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 18070b57cec5SDimitry Andricvoid 18080b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) 18090b57cec5SDimitry Andric#if _LIBCPP_STD_VER <= 11 18100b57cec5SDimitry Andric _NOEXCEPT_( 18110b57cec5SDimitry Andric __is_nothrow_swappable<value_compare>::value 18120b57cec5SDimitry Andric && (!__node_traits::propagate_on_container_swap::value || 18130b57cec5SDimitry Andric __is_nothrow_swappable<__node_allocator>::value) 18140b57cec5SDimitry Andric ) 18150b57cec5SDimitry Andric#else 18160b57cec5SDimitry Andric _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value) 18170b57cec5SDimitry Andric#endif 18180b57cec5SDimitry Andric{ 18190b57cec5SDimitry Andric using _VSTD::swap; 18200b57cec5SDimitry Andric swap(__begin_node_, __t.__begin_node_); 18210b57cec5SDimitry Andric swap(__pair1_.first(), __t.__pair1_.first()); 1822*e8d8bef9SDimitry Andric _VSTD::__swap_allocator(__node_alloc(), __t.__node_alloc()); 18230b57cec5SDimitry Andric __pair3_.swap(__t.__pair3_); 18240b57cec5SDimitry Andric if (size() == 0) 18250b57cec5SDimitry Andric __begin_node() = __end_node(); 18260b57cec5SDimitry Andric else 18270b57cec5SDimitry Andric __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); 18280b57cec5SDimitry Andric if (__t.size() == 0) 18290b57cec5SDimitry Andric __t.__begin_node() = __t.__end_node(); 18300b57cec5SDimitry Andric else 18310b57cec5SDimitry Andric __t.__end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__t.__end_node()); 18320b57cec5SDimitry Andric} 18330b57cec5SDimitry Andric 18340b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 18350b57cec5SDimitry Andricvoid 18360b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT 18370b57cec5SDimitry Andric{ 18380b57cec5SDimitry Andric destroy(__root()); 18390b57cec5SDimitry Andric size() = 0; 18400b57cec5SDimitry Andric __begin_node() = __end_node(); 18410b57cec5SDimitry Andric __end_node()->__left_ = nullptr; 18420b57cec5SDimitry Andric} 18430b57cec5SDimitry Andric 18440b57cec5SDimitry Andric// Find lower_bound place to insert 18450b57cec5SDimitry Andric// Set __parent to parent of null leaf 18460b57cec5SDimitry Andric// Return reference to null leaf 18470b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 18480b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 18490b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent, 18500b57cec5SDimitry Andric const key_type& __v) 18510b57cec5SDimitry Andric{ 18520b57cec5SDimitry Andric __node_pointer __nd = __root(); 18530b57cec5SDimitry Andric if (__nd != nullptr) 18540b57cec5SDimitry Andric { 18550b57cec5SDimitry Andric while (true) 18560b57cec5SDimitry Andric { 18570b57cec5SDimitry Andric if (value_comp()(__nd->__value_, __v)) 18580b57cec5SDimitry Andric { 18590b57cec5SDimitry Andric if (__nd->__right_ != nullptr) 18600b57cec5SDimitry Andric __nd = static_cast<__node_pointer>(__nd->__right_); 18610b57cec5SDimitry Andric else 18620b57cec5SDimitry Andric { 18630b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__nd); 18640b57cec5SDimitry Andric return __nd->__right_; 18650b57cec5SDimitry Andric } 18660b57cec5SDimitry Andric } 18670b57cec5SDimitry Andric else 18680b57cec5SDimitry Andric { 18690b57cec5SDimitry Andric if (__nd->__left_ != nullptr) 18700b57cec5SDimitry Andric __nd = static_cast<__node_pointer>(__nd->__left_); 18710b57cec5SDimitry Andric else 18720b57cec5SDimitry Andric { 18730b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__nd); 18740b57cec5SDimitry Andric return __parent->__left_; 18750b57cec5SDimitry Andric } 18760b57cec5SDimitry Andric } 18770b57cec5SDimitry Andric } 18780b57cec5SDimitry Andric } 18790b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__end_node()); 18800b57cec5SDimitry Andric return __parent->__left_; 18810b57cec5SDimitry Andric} 18820b57cec5SDimitry Andric 18830b57cec5SDimitry Andric// Find upper_bound place to insert 18840b57cec5SDimitry Andric// Set __parent to parent of null leaf 18850b57cec5SDimitry Andric// Return reference to null leaf 18860b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 18870b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 18880b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent, 18890b57cec5SDimitry Andric const key_type& __v) 18900b57cec5SDimitry Andric{ 18910b57cec5SDimitry Andric __node_pointer __nd = __root(); 18920b57cec5SDimitry Andric if (__nd != nullptr) 18930b57cec5SDimitry Andric { 18940b57cec5SDimitry Andric while (true) 18950b57cec5SDimitry Andric { 18960b57cec5SDimitry Andric if (value_comp()(__v, __nd->__value_)) 18970b57cec5SDimitry Andric { 18980b57cec5SDimitry Andric if (__nd->__left_ != nullptr) 18990b57cec5SDimitry Andric __nd = static_cast<__node_pointer>(__nd->__left_); 19000b57cec5SDimitry Andric else 19010b57cec5SDimitry Andric { 19020b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__nd); 19030b57cec5SDimitry Andric return __parent->__left_; 19040b57cec5SDimitry Andric } 19050b57cec5SDimitry Andric } 19060b57cec5SDimitry Andric else 19070b57cec5SDimitry Andric { 19080b57cec5SDimitry Andric if (__nd->__right_ != nullptr) 19090b57cec5SDimitry Andric __nd = static_cast<__node_pointer>(__nd->__right_); 19100b57cec5SDimitry Andric else 19110b57cec5SDimitry Andric { 19120b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__nd); 19130b57cec5SDimitry Andric return __nd->__right_; 19140b57cec5SDimitry Andric } 19150b57cec5SDimitry Andric } 19160b57cec5SDimitry Andric } 19170b57cec5SDimitry Andric } 19180b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__end_node()); 19190b57cec5SDimitry Andric return __parent->__left_; 19200b57cec5SDimitry Andric} 19210b57cec5SDimitry Andric 19220b57cec5SDimitry Andric// Find leaf place to insert closest to __hint 19230b57cec5SDimitry Andric// First check prior to __hint. 19240b57cec5SDimitry Andric// Next check after __hint. 19250b57cec5SDimitry Andric// Next do O(log N) search. 19260b57cec5SDimitry Andric// Set __parent to parent of null leaf 19270b57cec5SDimitry Andric// Return reference to null leaf 19280b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 19290b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 19300b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, 19310b57cec5SDimitry Andric __parent_pointer& __parent, 19320b57cec5SDimitry Andric const key_type& __v) 19330b57cec5SDimitry Andric{ 19340b57cec5SDimitry Andric if (__hint == end() || !value_comp()(*__hint, __v)) // check before 19350b57cec5SDimitry Andric { 19360b57cec5SDimitry Andric // __v <= *__hint 19370b57cec5SDimitry Andric const_iterator __prior = __hint; 19380b57cec5SDimitry Andric if (__prior == begin() || !value_comp()(__v, *--__prior)) 19390b57cec5SDimitry Andric { 19400b57cec5SDimitry Andric // *prev(__hint) <= __v <= *__hint 19410b57cec5SDimitry Andric if (__hint.__ptr_->__left_ == nullptr) 19420b57cec5SDimitry Andric { 19430b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__hint.__ptr_); 19440b57cec5SDimitry Andric return __parent->__left_; 19450b57cec5SDimitry Andric } 19460b57cec5SDimitry Andric else 19470b57cec5SDimitry Andric { 19480b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__prior.__ptr_); 19490b57cec5SDimitry Andric return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_; 19500b57cec5SDimitry Andric } 19510b57cec5SDimitry Andric } 19520b57cec5SDimitry Andric // __v < *prev(__hint) 19530b57cec5SDimitry Andric return __find_leaf_high(__parent, __v); 19540b57cec5SDimitry Andric } 19550b57cec5SDimitry Andric // else __v > *__hint 19560b57cec5SDimitry Andric return __find_leaf_low(__parent, __v); 19570b57cec5SDimitry Andric} 19580b57cec5SDimitry Andric 19590b57cec5SDimitry Andric// Find place to insert if __v doesn't exist 19600b57cec5SDimitry Andric// Set __parent to parent of null leaf 19610b57cec5SDimitry Andric// Return reference to null leaf 19620b57cec5SDimitry Andric// If __v exists, set parent to node of __v and return reference to node of __v 19630b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 19640b57cec5SDimitry Andrictemplate <class _Key> 19650b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 19660b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent, 19670b57cec5SDimitry Andric const _Key& __v) 19680b57cec5SDimitry Andric{ 19690b57cec5SDimitry Andric __node_pointer __nd = __root(); 19700b57cec5SDimitry Andric __node_base_pointer* __nd_ptr = __root_ptr(); 19710b57cec5SDimitry Andric if (__nd != nullptr) 19720b57cec5SDimitry Andric { 19730b57cec5SDimitry Andric while (true) 19740b57cec5SDimitry Andric { 19750b57cec5SDimitry Andric if (value_comp()(__v, __nd->__value_)) 19760b57cec5SDimitry Andric { 19770b57cec5SDimitry Andric if (__nd->__left_ != nullptr) { 19780b57cec5SDimitry Andric __nd_ptr = _VSTD::addressof(__nd->__left_); 19790b57cec5SDimitry Andric __nd = static_cast<__node_pointer>(__nd->__left_); 19800b57cec5SDimitry Andric } else { 19810b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__nd); 19820b57cec5SDimitry Andric return __parent->__left_; 19830b57cec5SDimitry Andric } 19840b57cec5SDimitry Andric } 19850b57cec5SDimitry Andric else if (value_comp()(__nd->__value_, __v)) 19860b57cec5SDimitry Andric { 19870b57cec5SDimitry Andric if (__nd->__right_ != nullptr) { 19880b57cec5SDimitry Andric __nd_ptr = _VSTD::addressof(__nd->__right_); 19890b57cec5SDimitry Andric __nd = static_cast<__node_pointer>(__nd->__right_); 19900b57cec5SDimitry Andric } else { 19910b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__nd); 19920b57cec5SDimitry Andric return __nd->__right_; 19930b57cec5SDimitry Andric } 19940b57cec5SDimitry Andric } 19950b57cec5SDimitry Andric else 19960b57cec5SDimitry Andric { 19970b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__nd); 19980b57cec5SDimitry Andric return *__nd_ptr; 19990b57cec5SDimitry Andric } 20000b57cec5SDimitry Andric } 20010b57cec5SDimitry Andric } 20020b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__end_node()); 20030b57cec5SDimitry Andric return __parent->__left_; 20040b57cec5SDimitry Andric} 20050b57cec5SDimitry Andric 20060b57cec5SDimitry Andric// Find place to insert if __v doesn't exist 20070b57cec5SDimitry Andric// First check prior to __hint. 20080b57cec5SDimitry Andric// Next check after __hint. 20090b57cec5SDimitry Andric// Next do O(log N) search. 20100b57cec5SDimitry Andric// Set __parent to parent of null leaf 20110b57cec5SDimitry Andric// Return reference to null leaf 20120b57cec5SDimitry Andric// If __v exists, set parent to node of __v and return reference to node of __v 20130b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 20140b57cec5SDimitry Andrictemplate <class _Key> 20150b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& 20160b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, 20170b57cec5SDimitry Andric __parent_pointer& __parent, 20180b57cec5SDimitry Andric __node_base_pointer& __dummy, 20190b57cec5SDimitry Andric const _Key& __v) 20200b57cec5SDimitry Andric{ 20210b57cec5SDimitry Andric if (__hint == end() || value_comp()(__v, *__hint)) // check before 20220b57cec5SDimitry Andric { 20230b57cec5SDimitry Andric // __v < *__hint 20240b57cec5SDimitry Andric const_iterator __prior = __hint; 20250b57cec5SDimitry Andric if (__prior == begin() || value_comp()(*--__prior, __v)) 20260b57cec5SDimitry Andric { 20270b57cec5SDimitry Andric // *prev(__hint) < __v < *__hint 20280b57cec5SDimitry Andric if (__hint.__ptr_->__left_ == nullptr) 20290b57cec5SDimitry Andric { 20300b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__hint.__ptr_); 20310b57cec5SDimitry Andric return __parent->__left_; 20320b57cec5SDimitry Andric } 20330b57cec5SDimitry Andric else 20340b57cec5SDimitry Andric { 20350b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__prior.__ptr_); 20360b57cec5SDimitry Andric return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_; 20370b57cec5SDimitry Andric } 20380b57cec5SDimitry Andric } 20390b57cec5SDimitry Andric // __v <= *prev(__hint) 20400b57cec5SDimitry Andric return __find_equal(__parent, __v); 20410b57cec5SDimitry Andric } 20420b57cec5SDimitry Andric else if (value_comp()(*__hint, __v)) // check after 20430b57cec5SDimitry Andric { 20440b57cec5SDimitry Andric // *__hint < __v 20450b57cec5SDimitry Andric const_iterator __next = _VSTD::next(__hint); 20460b57cec5SDimitry Andric if (__next == end() || value_comp()(__v, *__next)) 20470b57cec5SDimitry Andric { 20480b57cec5SDimitry Andric // *__hint < __v < *_VSTD::next(__hint) 20490b57cec5SDimitry Andric if (__hint.__get_np()->__right_ == nullptr) 20500b57cec5SDimitry Andric { 20510b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__hint.__ptr_); 20520b57cec5SDimitry Andric return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_; 20530b57cec5SDimitry Andric } 20540b57cec5SDimitry Andric else 20550b57cec5SDimitry Andric { 20560b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__next.__ptr_); 20570b57cec5SDimitry Andric return __parent->__left_; 20580b57cec5SDimitry Andric } 20590b57cec5SDimitry Andric } 20600b57cec5SDimitry Andric // *next(__hint) <= __v 20610b57cec5SDimitry Andric return __find_equal(__parent, __v); 20620b57cec5SDimitry Andric } 20630b57cec5SDimitry Andric // else __v == *__hint 20640b57cec5SDimitry Andric __parent = static_cast<__parent_pointer>(__hint.__ptr_); 20650b57cec5SDimitry Andric __dummy = static_cast<__node_base_pointer>(__hint.__ptr_); 20660b57cec5SDimitry Andric return __dummy; 20670b57cec5SDimitry Andric} 20680b57cec5SDimitry Andric 20690b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 20700b57cec5SDimitry Andricvoid __tree<_Tp, _Compare, _Allocator>::__insert_node_at( 20710b57cec5SDimitry Andric __parent_pointer __parent, __node_base_pointer& __child, 20720b57cec5SDimitry Andric __node_base_pointer __new_node) _NOEXCEPT 20730b57cec5SDimitry Andric{ 20740b57cec5SDimitry Andric __new_node->__left_ = nullptr; 20750b57cec5SDimitry Andric __new_node->__right_ = nullptr; 20760b57cec5SDimitry Andric __new_node->__parent_ = __parent; 20770b57cec5SDimitry Andric // __new_node->__is_black_ is initialized in __tree_balance_after_insert 20780b57cec5SDimitry Andric __child = __new_node; 20790b57cec5SDimitry Andric if (__begin_node()->__left_ != nullptr) 20800b57cec5SDimitry Andric __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_); 2081*e8d8bef9SDimitry Andric _VSTD::__tree_balance_after_insert(__end_node()->__left_, __child); 20820b57cec5SDimitry Andric ++size(); 20830b57cec5SDimitry Andric} 20840b57cec5SDimitry Andric 20850b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 20860b57cec5SDimitry Andrictemplate <class _Key, class... _Args> 20870b57cec5SDimitry Andricpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 20880b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) 20890b57cec5SDimitry Andric{ 20900b57cec5SDimitry Andric __parent_pointer __parent; 20910b57cec5SDimitry Andric __node_base_pointer& __child = __find_equal(__parent, __k); 20920b57cec5SDimitry Andric __node_pointer __r = static_cast<__node_pointer>(__child); 20930b57cec5SDimitry Andric bool __inserted = false; 20940b57cec5SDimitry Andric if (__child == nullptr) 20950b57cec5SDimitry Andric { 20960b57cec5SDimitry Andric __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 20970b57cec5SDimitry Andric __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 20980b57cec5SDimitry Andric __r = __h.release(); 20990b57cec5SDimitry Andric __inserted = true; 21000b57cec5SDimitry Andric } 21010b57cec5SDimitry Andric return pair<iterator, bool>(iterator(__r), __inserted); 21020b57cec5SDimitry Andric} 21030b57cec5SDimitry Andric 21040b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 21050b57cec5SDimitry Andrictemplate <class _Key, class... _Args> 2106*e8d8bef9SDimitry Andricpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 21070b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( 21080b57cec5SDimitry Andric const_iterator __p, _Key const& __k, _Args&&... __args) 21090b57cec5SDimitry Andric{ 21100b57cec5SDimitry Andric __parent_pointer __parent; 21110b57cec5SDimitry Andric __node_base_pointer __dummy; 21120b57cec5SDimitry Andric __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k); 21130b57cec5SDimitry Andric __node_pointer __r = static_cast<__node_pointer>(__child); 2114*e8d8bef9SDimitry Andric bool __inserted = false; 21150b57cec5SDimitry Andric if (__child == nullptr) 21160b57cec5SDimitry Andric { 21170b57cec5SDimitry Andric __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 21180b57cec5SDimitry Andric __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 21190b57cec5SDimitry Andric __r = __h.release(); 2120*e8d8bef9SDimitry Andric __inserted = true; 21210b57cec5SDimitry Andric } 2122*e8d8bef9SDimitry Andric return pair<iterator, bool>(iterator(__r), __inserted); 21230b57cec5SDimitry Andric} 21240b57cec5SDimitry Andric 21250b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 21260b57cec5SDimitry Andrictemplate <class ..._Args> 21270b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::__node_holder 21280b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args) 21290b57cec5SDimitry Andric{ 21300b57cec5SDimitry Andric static_assert(!__is_tree_value_type<_Args...>::value, 21310b57cec5SDimitry Andric "Cannot construct from __value_type"); 21320b57cec5SDimitry Andric __node_allocator& __na = __node_alloc(); 21330b57cec5SDimitry Andric __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 21340b57cec5SDimitry Andric __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...); 21350b57cec5SDimitry Andric __h.get_deleter().__value_constructed = true; 21360b57cec5SDimitry Andric return __h; 21370b57cec5SDimitry Andric} 21380b57cec5SDimitry Andric 21390b57cec5SDimitry Andric 21400b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 21410b57cec5SDimitry Andrictemplate <class... _Args> 21420b57cec5SDimitry Andricpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 21430b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args) 21440b57cec5SDimitry Andric{ 21450b57cec5SDimitry Andric __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 21460b57cec5SDimitry Andric __parent_pointer __parent; 21470b57cec5SDimitry Andric __node_base_pointer& __child = __find_equal(__parent, __h->__value_); 21480b57cec5SDimitry Andric __node_pointer __r = static_cast<__node_pointer>(__child); 21490b57cec5SDimitry Andric bool __inserted = false; 21500b57cec5SDimitry Andric if (__child == nullptr) 21510b57cec5SDimitry Andric { 21520b57cec5SDimitry Andric __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 21530b57cec5SDimitry Andric __r = __h.release(); 21540b57cec5SDimitry Andric __inserted = true; 21550b57cec5SDimitry Andric } 21560b57cec5SDimitry Andric return pair<iterator, bool>(iterator(__r), __inserted); 21570b57cec5SDimitry Andric} 21580b57cec5SDimitry Andric 21590b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 21600b57cec5SDimitry Andrictemplate <class... _Args> 21610b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 21620b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args) 21630b57cec5SDimitry Andric{ 21640b57cec5SDimitry Andric __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 21650b57cec5SDimitry Andric __parent_pointer __parent; 21660b57cec5SDimitry Andric __node_base_pointer __dummy; 21670b57cec5SDimitry Andric __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_); 21680b57cec5SDimitry Andric __node_pointer __r = static_cast<__node_pointer>(__child); 21690b57cec5SDimitry Andric if (__child == nullptr) 21700b57cec5SDimitry Andric { 21710b57cec5SDimitry Andric __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 21720b57cec5SDimitry Andric __r = __h.release(); 21730b57cec5SDimitry Andric } 21740b57cec5SDimitry Andric return iterator(__r); 21750b57cec5SDimitry Andric} 21760b57cec5SDimitry Andric 21770b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 21780b57cec5SDimitry Andrictemplate <class... _Args> 21790b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 21800b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) 21810b57cec5SDimitry Andric{ 21820b57cec5SDimitry Andric __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 21830b57cec5SDimitry Andric __parent_pointer __parent; 21840b57cec5SDimitry Andric __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_)); 21850b57cec5SDimitry Andric __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 21860b57cec5SDimitry Andric return iterator(static_cast<__node_pointer>(__h.release())); 21870b57cec5SDimitry Andric} 21880b57cec5SDimitry Andric 21890b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 21900b57cec5SDimitry Andrictemplate <class... _Args> 21910b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 21920b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, 21930b57cec5SDimitry Andric _Args&&... __args) 21940b57cec5SDimitry Andric{ 21950b57cec5SDimitry Andric __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 21960b57cec5SDimitry Andric __parent_pointer __parent; 21970b57cec5SDimitry Andric __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_)); 21980b57cec5SDimitry Andric __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 21990b57cec5SDimitry Andric return iterator(static_cast<__node_pointer>(__h.release())); 22000b57cec5SDimitry Andric} 22010b57cec5SDimitry Andric 22020b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 22030b57cec5SDimitry Andricpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 22040b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const __container_value_type& __v, __node_pointer __nd) 22050b57cec5SDimitry Andric{ 22060b57cec5SDimitry Andric __parent_pointer __parent; 22070b57cec5SDimitry Andric __node_base_pointer& __child = __find_equal(__parent, _NodeTypes::__get_key(__v)); 22080b57cec5SDimitry Andric __node_pointer __r = static_cast<__node_pointer>(__child); 22090b57cec5SDimitry Andric bool __inserted = false; 22100b57cec5SDimitry Andric if (__child == nullptr) 22110b57cec5SDimitry Andric { 22120b57cec5SDimitry Andric __nd->__value_ = __v; 22130b57cec5SDimitry Andric __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 22140b57cec5SDimitry Andric __r = __nd; 22150b57cec5SDimitry Andric __inserted = true; 22160b57cec5SDimitry Andric } 22170b57cec5SDimitry Andric return pair<iterator, bool>(iterator(__r), __inserted); 22180b57cec5SDimitry Andric} 22190b57cec5SDimitry Andric 22200b57cec5SDimitry Andric 22210b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 22220b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 22230b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) 22240b57cec5SDimitry Andric{ 22250b57cec5SDimitry Andric __parent_pointer __parent; 22260b57cec5SDimitry Andric __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_)); 22270b57cec5SDimitry Andric __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 22280b57cec5SDimitry Andric return iterator(__nd); 22290b57cec5SDimitry Andric} 22300b57cec5SDimitry Andric 22310b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 22320b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 22330b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, 22340b57cec5SDimitry Andric __node_pointer __nd) 22350b57cec5SDimitry Andric{ 22360b57cec5SDimitry Andric __parent_pointer __parent; 22370b57cec5SDimitry Andric __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_)); 22380b57cec5SDimitry Andric __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 22390b57cec5SDimitry Andric return iterator(__nd); 22400b57cec5SDimitry Andric} 22410b57cec5SDimitry Andric 22420b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 22430b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 22440b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT 22450b57cec5SDimitry Andric{ 22460b57cec5SDimitry Andric iterator __r(__ptr); 22470b57cec5SDimitry Andric ++__r; 22480b57cec5SDimitry Andric if (__begin_node() == __ptr) 22490b57cec5SDimitry Andric __begin_node() = __r.__ptr_; 22500b57cec5SDimitry Andric --size(); 2251*e8d8bef9SDimitry Andric _VSTD::__tree_remove(__end_node()->__left_, 22520b57cec5SDimitry Andric static_cast<__node_base_pointer>(__ptr)); 22530b57cec5SDimitry Andric return __r; 22540b57cec5SDimitry Andric} 22550b57cec5SDimitry Andric 22560b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 22570b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 22580b57cec5SDimitry Andrictemplate <class _NodeHandle, class _InsertReturnType> 22590b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY 22600b57cec5SDimitry Andric_InsertReturnType 22610b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique( 22620b57cec5SDimitry Andric _NodeHandle&& __nh) 22630b57cec5SDimitry Andric{ 22640b57cec5SDimitry Andric if (__nh.empty()) 22650b57cec5SDimitry Andric return _InsertReturnType{end(), false, _NodeHandle()}; 22660b57cec5SDimitry Andric 22670b57cec5SDimitry Andric __node_pointer __ptr = __nh.__ptr_; 22680b57cec5SDimitry Andric __parent_pointer __parent; 22690b57cec5SDimitry Andric __node_base_pointer& __child = __find_equal(__parent, 22700b57cec5SDimitry Andric __ptr->__value_); 22710b57cec5SDimitry Andric if (__child != nullptr) 22720b57cec5SDimitry Andric return _InsertReturnType{ 22730b57cec5SDimitry Andric iterator(static_cast<__node_pointer>(__child)), 22740b57cec5SDimitry Andric false, _VSTD::move(__nh)}; 22750b57cec5SDimitry Andric 22760b57cec5SDimitry Andric __insert_node_at(__parent, __child, 22770b57cec5SDimitry Andric static_cast<__node_base_pointer>(__ptr)); 22780b57cec5SDimitry Andric __nh.__release_ptr(); 22790b57cec5SDimitry Andric return _InsertReturnType{iterator(__ptr), true, _NodeHandle()}; 22800b57cec5SDimitry Andric} 22810b57cec5SDimitry Andric 22820b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 22830b57cec5SDimitry Andrictemplate <class _NodeHandle> 22840b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY 22850b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 22860b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique( 22870b57cec5SDimitry Andric const_iterator __hint, _NodeHandle&& __nh) 22880b57cec5SDimitry Andric{ 22890b57cec5SDimitry Andric if (__nh.empty()) 22900b57cec5SDimitry Andric return end(); 22910b57cec5SDimitry Andric 22920b57cec5SDimitry Andric __node_pointer __ptr = __nh.__ptr_; 22930b57cec5SDimitry Andric __parent_pointer __parent; 22940b57cec5SDimitry Andric __node_base_pointer __dummy; 22950b57cec5SDimitry Andric __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy, 22960b57cec5SDimitry Andric __ptr->__value_); 22970b57cec5SDimitry Andric __node_pointer __r = static_cast<__node_pointer>(__child); 22980b57cec5SDimitry Andric if (__child == nullptr) 22990b57cec5SDimitry Andric { 23000b57cec5SDimitry Andric __insert_node_at(__parent, __child, 23010b57cec5SDimitry Andric static_cast<__node_base_pointer>(__ptr)); 23020b57cec5SDimitry Andric __r = __ptr; 23030b57cec5SDimitry Andric __nh.__release_ptr(); 23040b57cec5SDimitry Andric } 23050b57cec5SDimitry Andric return iterator(__r); 23060b57cec5SDimitry Andric} 23070b57cec5SDimitry Andric 23080b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 23090b57cec5SDimitry Andrictemplate <class _NodeHandle> 23100b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY 23110b57cec5SDimitry Andric_NodeHandle 23120b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key) 23130b57cec5SDimitry Andric{ 23140b57cec5SDimitry Andric iterator __it = find(__key); 23150b57cec5SDimitry Andric if (__it == end()) 23160b57cec5SDimitry Andric return _NodeHandle(); 23170b57cec5SDimitry Andric return __node_handle_extract<_NodeHandle>(__it); 23180b57cec5SDimitry Andric} 23190b57cec5SDimitry Andric 23200b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 23210b57cec5SDimitry Andrictemplate <class _NodeHandle> 23220b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY 23230b57cec5SDimitry Andric_NodeHandle 23240b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p) 23250b57cec5SDimitry Andric{ 23260b57cec5SDimitry Andric __node_pointer __np = __p.__get_np(); 23270b57cec5SDimitry Andric __remove_node_pointer(__np); 23280b57cec5SDimitry Andric return _NodeHandle(__np, __alloc()); 23290b57cec5SDimitry Andric} 23300b57cec5SDimitry Andric 23310b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 23320b57cec5SDimitry Andrictemplate <class _Tree> 23330b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY 23340b57cec5SDimitry Andricvoid 23350b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) 23360b57cec5SDimitry Andric{ 23370b57cec5SDimitry Andric static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); 23380b57cec5SDimitry Andric 23390b57cec5SDimitry Andric for (typename _Tree::iterator __i = __source.begin(); 23400b57cec5SDimitry Andric __i != __source.end();) 23410b57cec5SDimitry Andric { 23420b57cec5SDimitry Andric __node_pointer __src_ptr = __i.__get_np(); 23430b57cec5SDimitry Andric __parent_pointer __parent; 23440b57cec5SDimitry Andric __node_base_pointer& __child = 23450b57cec5SDimitry Andric __find_equal(__parent, _NodeTypes::__get_key(__src_ptr->__value_)); 23460b57cec5SDimitry Andric ++__i; 23470b57cec5SDimitry Andric if (__child != nullptr) 23480b57cec5SDimitry Andric continue; 23490b57cec5SDimitry Andric __source.__remove_node_pointer(__src_ptr); 23500b57cec5SDimitry Andric __insert_node_at(__parent, __child, 23510b57cec5SDimitry Andric static_cast<__node_base_pointer>(__src_ptr)); 23520b57cec5SDimitry Andric } 23530b57cec5SDimitry Andric} 23540b57cec5SDimitry Andric 23550b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 23560b57cec5SDimitry Andrictemplate <class _NodeHandle> 23570b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY 23580b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 23590b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh) 23600b57cec5SDimitry Andric{ 23610b57cec5SDimitry Andric if (__nh.empty()) 23620b57cec5SDimitry Andric return end(); 23630b57cec5SDimitry Andric __node_pointer __ptr = __nh.__ptr_; 23640b57cec5SDimitry Andric __parent_pointer __parent; 23650b57cec5SDimitry Andric __node_base_pointer& __child = __find_leaf_high( 23660b57cec5SDimitry Andric __parent, _NodeTypes::__get_key(__ptr->__value_)); 23670b57cec5SDimitry Andric __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); 23680b57cec5SDimitry Andric __nh.__release_ptr(); 23690b57cec5SDimitry Andric return iterator(__ptr); 23700b57cec5SDimitry Andric} 23710b57cec5SDimitry Andric 23720b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 23730b57cec5SDimitry Andrictemplate <class _NodeHandle> 23740b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY 23750b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 23760b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi( 23770b57cec5SDimitry Andric const_iterator __hint, _NodeHandle&& __nh) 23780b57cec5SDimitry Andric{ 23790b57cec5SDimitry Andric if (__nh.empty()) 23800b57cec5SDimitry Andric return end(); 23810b57cec5SDimitry Andric 23820b57cec5SDimitry Andric __node_pointer __ptr = __nh.__ptr_; 23830b57cec5SDimitry Andric __parent_pointer __parent; 23840b57cec5SDimitry Andric __node_base_pointer& __child = __find_leaf(__hint, __parent, 23850b57cec5SDimitry Andric _NodeTypes::__get_key(__ptr->__value_)); 23860b57cec5SDimitry Andric __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); 23870b57cec5SDimitry Andric __nh.__release_ptr(); 23880b57cec5SDimitry Andric return iterator(__ptr); 23890b57cec5SDimitry Andric} 23900b57cec5SDimitry Andric 23910b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 23920b57cec5SDimitry Andrictemplate <class _Tree> 23930b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY 23940b57cec5SDimitry Andricvoid 23950b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) 23960b57cec5SDimitry Andric{ 23970b57cec5SDimitry Andric static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); 23980b57cec5SDimitry Andric 23990b57cec5SDimitry Andric for (typename _Tree::iterator __i = __source.begin(); 24000b57cec5SDimitry Andric __i != __source.end();) 24010b57cec5SDimitry Andric { 24020b57cec5SDimitry Andric __node_pointer __src_ptr = __i.__get_np(); 24030b57cec5SDimitry Andric __parent_pointer __parent; 24040b57cec5SDimitry Andric __node_base_pointer& __child = __find_leaf_high( 24050b57cec5SDimitry Andric __parent, _NodeTypes::__get_key(__src_ptr->__value_)); 24060b57cec5SDimitry Andric ++__i; 24070b57cec5SDimitry Andric __source.__remove_node_pointer(__src_ptr); 24080b57cec5SDimitry Andric __insert_node_at(__parent, __child, 24090b57cec5SDimitry Andric static_cast<__node_base_pointer>(__src_ptr)); 24100b57cec5SDimitry Andric } 24110b57cec5SDimitry Andric} 24120b57cec5SDimitry Andric 24130b57cec5SDimitry Andric#endif // _LIBCPP_STD_VER > 14 24140b57cec5SDimitry Andric 24150b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 24160b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 24170b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) 24180b57cec5SDimitry Andric{ 24190b57cec5SDimitry Andric __node_pointer __np = __p.__get_np(); 24200b57cec5SDimitry Andric iterator __r = __remove_node_pointer(__np); 24210b57cec5SDimitry Andric __node_allocator& __na = __node_alloc(); 24220b57cec5SDimitry Andric __node_traits::destroy(__na, _NodeTypes::__get_ptr( 24230b57cec5SDimitry Andric const_cast<__node_value_type&>(*__p))); 24240b57cec5SDimitry Andric __node_traits::deallocate(__na, __np, 1); 24250b57cec5SDimitry Andric return __r; 24260b57cec5SDimitry Andric} 24270b57cec5SDimitry Andric 24280b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 24290b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 24300b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l) 24310b57cec5SDimitry Andric{ 24320b57cec5SDimitry Andric while (__f != __l) 24330b57cec5SDimitry Andric __f = erase(__f); 24340b57cec5SDimitry Andric return iterator(__l.__ptr_); 24350b57cec5SDimitry Andric} 24360b57cec5SDimitry Andric 24370b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 24380b57cec5SDimitry Andrictemplate <class _Key> 24390b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::size_type 24400b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) 24410b57cec5SDimitry Andric{ 24420b57cec5SDimitry Andric iterator __i = find(__k); 24430b57cec5SDimitry Andric if (__i == end()) 24440b57cec5SDimitry Andric return 0; 24450b57cec5SDimitry Andric erase(__i); 24460b57cec5SDimitry Andric return 1; 24470b57cec5SDimitry Andric} 24480b57cec5SDimitry Andric 24490b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 24500b57cec5SDimitry Andrictemplate <class _Key> 24510b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::size_type 24520b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) 24530b57cec5SDimitry Andric{ 24540b57cec5SDimitry Andric pair<iterator, iterator> __p = __equal_range_multi(__k); 24550b57cec5SDimitry Andric size_type __r = 0; 24560b57cec5SDimitry Andric for (; __p.first != __p.second; ++__r) 24570b57cec5SDimitry Andric __p.first = erase(__p.first); 24580b57cec5SDimitry Andric return __r; 24590b57cec5SDimitry Andric} 24600b57cec5SDimitry Andric 24610b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 24620b57cec5SDimitry Andrictemplate <class _Key> 24630b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 24640b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) 24650b57cec5SDimitry Andric{ 24660b57cec5SDimitry Andric iterator __p = __lower_bound(__v, __root(), __end_node()); 24670b57cec5SDimitry Andric if (__p != end() && !value_comp()(__v, *__p)) 24680b57cec5SDimitry Andric return __p; 24690b57cec5SDimitry Andric return end(); 24700b57cec5SDimitry Andric} 24710b57cec5SDimitry Andric 24720b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 24730b57cec5SDimitry Andrictemplate <class _Key> 24740b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::const_iterator 24750b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const 24760b57cec5SDimitry Andric{ 24770b57cec5SDimitry Andric const_iterator __p = __lower_bound(__v, __root(), __end_node()); 24780b57cec5SDimitry Andric if (__p != end() && !value_comp()(__v, *__p)) 24790b57cec5SDimitry Andric return __p; 24800b57cec5SDimitry Andric return end(); 24810b57cec5SDimitry Andric} 24820b57cec5SDimitry Andric 24830b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 24840b57cec5SDimitry Andrictemplate <class _Key> 24850b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::size_type 24860b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const 24870b57cec5SDimitry Andric{ 24880b57cec5SDimitry Andric __node_pointer __rt = __root(); 24890b57cec5SDimitry Andric while (__rt != nullptr) 24900b57cec5SDimitry Andric { 24910b57cec5SDimitry Andric if (value_comp()(__k, __rt->__value_)) 24920b57cec5SDimitry Andric { 24930b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__left_); 24940b57cec5SDimitry Andric } 24950b57cec5SDimitry Andric else if (value_comp()(__rt->__value_, __k)) 24960b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__right_); 24970b57cec5SDimitry Andric else 24980b57cec5SDimitry Andric return 1; 24990b57cec5SDimitry Andric } 25000b57cec5SDimitry Andric return 0; 25010b57cec5SDimitry Andric} 25020b57cec5SDimitry Andric 25030b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 25040b57cec5SDimitry Andrictemplate <class _Key> 25050b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::size_type 25060b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const 25070b57cec5SDimitry Andric{ 25080b57cec5SDimitry Andric __iter_pointer __result = __end_node(); 25090b57cec5SDimitry Andric __node_pointer __rt = __root(); 25100b57cec5SDimitry Andric while (__rt != nullptr) 25110b57cec5SDimitry Andric { 25120b57cec5SDimitry Andric if (value_comp()(__k, __rt->__value_)) 25130b57cec5SDimitry Andric { 25140b57cec5SDimitry Andric __result = static_cast<__iter_pointer>(__rt); 25150b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__left_); 25160b57cec5SDimitry Andric } 25170b57cec5SDimitry Andric else if (value_comp()(__rt->__value_, __k)) 25180b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__right_); 25190b57cec5SDimitry Andric else 25200b57cec5SDimitry Andric return _VSTD::distance( 25210b57cec5SDimitry Andric __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), 25220b57cec5SDimitry Andric __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result) 25230b57cec5SDimitry Andric ); 25240b57cec5SDimitry Andric } 25250b57cec5SDimitry Andric return 0; 25260b57cec5SDimitry Andric} 25270b57cec5SDimitry Andric 25280b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 25290b57cec5SDimitry Andrictemplate <class _Key> 25300b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 25310b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 25320b57cec5SDimitry Andric __node_pointer __root, 25330b57cec5SDimitry Andric __iter_pointer __result) 25340b57cec5SDimitry Andric{ 25350b57cec5SDimitry Andric while (__root != nullptr) 25360b57cec5SDimitry Andric { 25370b57cec5SDimitry Andric if (!value_comp()(__root->__value_, __v)) 25380b57cec5SDimitry Andric { 25390b57cec5SDimitry Andric __result = static_cast<__iter_pointer>(__root); 25400b57cec5SDimitry Andric __root = static_cast<__node_pointer>(__root->__left_); 25410b57cec5SDimitry Andric } 25420b57cec5SDimitry Andric else 25430b57cec5SDimitry Andric __root = static_cast<__node_pointer>(__root->__right_); 25440b57cec5SDimitry Andric } 25450b57cec5SDimitry Andric return iterator(__result); 25460b57cec5SDimitry Andric} 25470b57cec5SDimitry Andric 25480b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 25490b57cec5SDimitry Andrictemplate <class _Key> 25500b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::const_iterator 25510b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 25520b57cec5SDimitry Andric __node_pointer __root, 25530b57cec5SDimitry Andric __iter_pointer __result) const 25540b57cec5SDimitry Andric{ 25550b57cec5SDimitry Andric while (__root != nullptr) 25560b57cec5SDimitry Andric { 25570b57cec5SDimitry Andric if (!value_comp()(__root->__value_, __v)) 25580b57cec5SDimitry Andric { 25590b57cec5SDimitry Andric __result = static_cast<__iter_pointer>(__root); 25600b57cec5SDimitry Andric __root = static_cast<__node_pointer>(__root->__left_); 25610b57cec5SDimitry Andric } 25620b57cec5SDimitry Andric else 25630b57cec5SDimitry Andric __root = static_cast<__node_pointer>(__root->__right_); 25640b57cec5SDimitry Andric } 25650b57cec5SDimitry Andric return const_iterator(__result); 25660b57cec5SDimitry Andric} 25670b57cec5SDimitry Andric 25680b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 25690b57cec5SDimitry Andrictemplate <class _Key> 25700b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::iterator 25710b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 25720b57cec5SDimitry Andric __node_pointer __root, 25730b57cec5SDimitry Andric __iter_pointer __result) 25740b57cec5SDimitry Andric{ 25750b57cec5SDimitry Andric while (__root != nullptr) 25760b57cec5SDimitry Andric { 25770b57cec5SDimitry Andric if (value_comp()(__v, __root->__value_)) 25780b57cec5SDimitry Andric { 25790b57cec5SDimitry Andric __result = static_cast<__iter_pointer>(__root); 25800b57cec5SDimitry Andric __root = static_cast<__node_pointer>(__root->__left_); 25810b57cec5SDimitry Andric } 25820b57cec5SDimitry Andric else 25830b57cec5SDimitry Andric __root = static_cast<__node_pointer>(__root->__right_); 25840b57cec5SDimitry Andric } 25850b57cec5SDimitry Andric return iterator(__result); 25860b57cec5SDimitry Andric} 25870b57cec5SDimitry Andric 25880b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 25890b57cec5SDimitry Andrictemplate <class _Key> 25900b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::const_iterator 25910b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 25920b57cec5SDimitry Andric __node_pointer __root, 25930b57cec5SDimitry Andric __iter_pointer __result) const 25940b57cec5SDimitry Andric{ 25950b57cec5SDimitry Andric while (__root != nullptr) 25960b57cec5SDimitry Andric { 25970b57cec5SDimitry Andric if (value_comp()(__v, __root->__value_)) 25980b57cec5SDimitry Andric { 25990b57cec5SDimitry Andric __result = static_cast<__iter_pointer>(__root); 26000b57cec5SDimitry Andric __root = static_cast<__node_pointer>(__root->__left_); 26010b57cec5SDimitry Andric } 26020b57cec5SDimitry Andric else 26030b57cec5SDimitry Andric __root = static_cast<__node_pointer>(__root->__right_); 26040b57cec5SDimitry Andric } 26050b57cec5SDimitry Andric return const_iterator(__result); 26060b57cec5SDimitry Andric} 26070b57cec5SDimitry Andric 26080b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 26090b57cec5SDimitry Andrictemplate <class _Key> 26100b57cec5SDimitry Andricpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 26110b57cec5SDimitry Andric typename __tree<_Tp, _Compare, _Allocator>::iterator> 26120b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) 26130b57cec5SDimitry Andric{ 26140b57cec5SDimitry Andric typedef pair<iterator, iterator> _Pp; 26150b57cec5SDimitry Andric __iter_pointer __result = __end_node(); 26160b57cec5SDimitry Andric __node_pointer __rt = __root(); 26170b57cec5SDimitry Andric while (__rt != nullptr) 26180b57cec5SDimitry Andric { 26190b57cec5SDimitry Andric if (value_comp()(__k, __rt->__value_)) 26200b57cec5SDimitry Andric { 26210b57cec5SDimitry Andric __result = static_cast<__iter_pointer>(__rt); 26220b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__left_); 26230b57cec5SDimitry Andric } 26240b57cec5SDimitry Andric else if (value_comp()(__rt->__value_, __k)) 26250b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__right_); 26260b57cec5SDimitry Andric else 26270b57cec5SDimitry Andric return _Pp(iterator(__rt), 26280b57cec5SDimitry Andric iterator( 26290b57cec5SDimitry Andric __rt->__right_ != nullptr ? 2630*e8d8bef9SDimitry Andric static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_)) 26310b57cec5SDimitry Andric : __result)); 26320b57cec5SDimitry Andric } 26330b57cec5SDimitry Andric return _Pp(iterator(__result), iterator(__result)); 26340b57cec5SDimitry Andric} 26350b57cec5SDimitry Andric 26360b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 26370b57cec5SDimitry Andrictemplate <class _Key> 26380b57cec5SDimitry Andricpair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 26390b57cec5SDimitry Andric typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 26400b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const 26410b57cec5SDimitry Andric{ 26420b57cec5SDimitry Andric typedef pair<const_iterator, const_iterator> _Pp; 26430b57cec5SDimitry Andric __iter_pointer __result = __end_node(); 26440b57cec5SDimitry Andric __node_pointer __rt = __root(); 26450b57cec5SDimitry Andric while (__rt != nullptr) 26460b57cec5SDimitry Andric { 26470b57cec5SDimitry Andric if (value_comp()(__k, __rt->__value_)) 26480b57cec5SDimitry Andric { 26490b57cec5SDimitry Andric __result = static_cast<__iter_pointer>(__rt); 26500b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__left_); 26510b57cec5SDimitry Andric } 26520b57cec5SDimitry Andric else if (value_comp()(__rt->__value_, __k)) 26530b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__right_); 26540b57cec5SDimitry Andric else 26550b57cec5SDimitry Andric return _Pp(const_iterator(__rt), 26560b57cec5SDimitry Andric const_iterator( 26570b57cec5SDimitry Andric __rt->__right_ != nullptr ? 2658*e8d8bef9SDimitry Andric static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_)) 26590b57cec5SDimitry Andric : __result)); 26600b57cec5SDimitry Andric } 26610b57cec5SDimitry Andric return _Pp(const_iterator(__result), const_iterator(__result)); 26620b57cec5SDimitry Andric} 26630b57cec5SDimitry Andric 26640b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 26650b57cec5SDimitry Andrictemplate <class _Key> 26660b57cec5SDimitry Andricpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 26670b57cec5SDimitry Andric typename __tree<_Tp, _Compare, _Allocator>::iterator> 26680b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) 26690b57cec5SDimitry Andric{ 26700b57cec5SDimitry Andric typedef pair<iterator, iterator> _Pp; 26710b57cec5SDimitry Andric __iter_pointer __result = __end_node(); 26720b57cec5SDimitry Andric __node_pointer __rt = __root(); 26730b57cec5SDimitry Andric while (__rt != nullptr) 26740b57cec5SDimitry Andric { 26750b57cec5SDimitry Andric if (value_comp()(__k, __rt->__value_)) 26760b57cec5SDimitry Andric { 26770b57cec5SDimitry Andric __result = static_cast<__iter_pointer>(__rt); 26780b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__left_); 26790b57cec5SDimitry Andric } 26800b57cec5SDimitry Andric else if (value_comp()(__rt->__value_, __k)) 26810b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__right_); 26820b57cec5SDimitry Andric else 26830b57cec5SDimitry Andric return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), 26840b57cec5SDimitry Andric __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 26850b57cec5SDimitry Andric } 26860b57cec5SDimitry Andric return _Pp(iterator(__result), iterator(__result)); 26870b57cec5SDimitry Andric} 26880b57cec5SDimitry Andric 26890b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 26900b57cec5SDimitry Andrictemplate <class _Key> 26910b57cec5SDimitry Andricpair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 26920b57cec5SDimitry Andric typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 26930b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const 26940b57cec5SDimitry Andric{ 26950b57cec5SDimitry Andric typedef pair<const_iterator, const_iterator> _Pp; 26960b57cec5SDimitry Andric __iter_pointer __result = __end_node(); 26970b57cec5SDimitry Andric __node_pointer __rt = __root(); 26980b57cec5SDimitry Andric while (__rt != nullptr) 26990b57cec5SDimitry Andric { 27000b57cec5SDimitry Andric if (value_comp()(__k, __rt->__value_)) 27010b57cec5SDimitry Andric { 27020b57cec5SDimitry Andric __result = static_cast<__iter_pointer>(__rt); 27030b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__left_); 27040b57cec5SDimitry Andric } 27050b57cec5SDimitry Andric else if (value_comp()(__rt->__value_, __k)) 27060b57cec5SDimitry Andric __rt = static_cast<__node_pointer>(__rt->__right_); 27070b57cec5SDimitry Andric else 27080b57cec5SDimitry Andric return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), 27090b57cec5SDimitry Andric __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 27100b57cec5SDimitry Andric } 27110b57cec5SDimitry Andric return _Pp(const_iterator(__result), const_iterator(__result)); 27120b57cec5SDimitry Andric} 27130b57cec5SDimitry Andric 27140b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 27150b57cec5SDimitry Andrictypename __tree<_Tp, _Compare, _Allocator>::__node_holder 27160b57cec5SDimitry Andric__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT 27170b57cec5SDimitry Andric{ 27180b57cec5SDimitry Andric __node_pointer __np = __p.__get_np(); 27190b57cec5SDimitry Andric if (__begin_node() == __p.__ptr_) 27200b57cec5SDimitry Andric { 27210b57cec5SDimitry Andric if (__np->__right_ != nullptr) 27220b57cec5SDimitry Andric __begin_node() = static_cast<__iter_pointer>(__np->__right_); 27230b57cec5SDimitry Andric else 27240b57cec5SDimitry Andric __begin_node() = static_cast<__iter_pointer>(__np->__parent_); 27250b57cec5SDimitry Andric } 27260b57cec5SDimitry Andric --size(); 2727*e8d8bef9SDimitry Andric _VSTD::__tree_remove(__end_node()->__left_, 27280b57cec5SDimitry Andric static_cast<__node_base_pointer>(__np)); 27290b57cec5SDimitry Andric return __node_holder(__np, _Dp(__node_alloc(), true)); 27300b57cec5SDimitry Andric} 27310b57cec5SDimitry Andric 27320b57cec5SDimitry Andrictemplate <class _Tp, class _Compare, class _Allocator> 27330b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 27340b57cec5SDimitry Andricvoid 27350b57cec5SDimitry Andricswap(__tree<_Tp, _Compare, _Allocator>& __x, 27360b57cec5SDimitry Andric __tree<_Tp, _Compare, _Allocator>& __y) 27370b57cec5SDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 27380b57cec5SDimitry Andric{ 27390b57cec5SDimitry Andric __x.swap(__y); 27400b57cec5SDimitry Andric} 27410b57cec5SDimitry Andric 27420b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 27430b57cec5SDimitry Andric 27440b57cec5SDimitry Andric_LIBCPP_POP_MACROS 27450b57cec5SDimitry Andric 27460b57cec5SDimitry Andric#endif // _LIBCPP___TREE 2747