xref: /freebsd/contrib/llvm-project/libcxx/include/__tree (revision e8d8bef961a50d4dc22501cde4fb9fb0be1b2532)
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