__tree revision 253159
1168404Spjd// -*- C++ -*- 2168404Spjd//===----------------------------------------------------------------------===// 3168404Spjd// 4168404Spjd// The LLVM Compiler Infrastructure 5168404Spjd// 6168404Spjd// This file is dual licensed under the MIT and the University of Illinois Open 7168404Spjd// Source Licenses. See LICENSE.TXT for details. 8168404Spjd// 9168404Spjd//===----------------------------------------------------------------------===// 10168404Spjd 11168404Spjd#ifndef _LIBCPP___TREE 12168404Spjd#define _LIBCPP___TREE 13168404Spjd 14168404Spjd#include <__config> 15168404Spjd#include <iterator> 16168404Spjd#include <memory> 17168404Spjd#include <stdexcept> 18168404Spjd#include <algorithm> 19168404Spjd 20168404Spjd#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 21168404Spjd#pragma GCC system_header 22219089Spjd#endif 23261620Sdelphij 24286708Smav_LIBCPP_BEGIN_NAMESPACE_STD 25264835Sdelphij 26261620Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> class __tree; 27286575Smavtemplate <class _Tp, class _NodePtr, class _DiffType> 28296519Smav class _LIBCPP_TYPE_VIS __tree_iterator; 29296521Smavtemplate <class _Tp, class _ConstNodePtr, class _DiffType> 30168404Spjd class _LIBCPP_TYPE_VIS __tree_const_iterator; 31168404Spjdtemplate <class _Key, class _Tp, class _Compare, class _Allocator> 32168404Spjd class _LIBCPP_TYPE_VIS map; 33168404Spjdtemplate <class _Key, class _Tp, class _Compare, class _Allocator> 34168404Spjd class _LIBCPP_TYPE_VIS multimap; 35168404Spjdtemplate <class _Key, class _Compare, class _Allocator> 36168404Spjd class _LIBCPP_TYPE_VIS set; 37168404Spjdtemplate <class _Key, class _Compare, class _Allocator> 38235222Smm class _LIBCPP_TYPE_VIS multiset; 39289362Smav 40168404Spjd/* 41168404Spjd 42168404Spjd_NodePtr algorithms 43168404Spjd 44236884SmmThe algorithms taking _NodePtr are red black tree algorithms. Those 45168404Spjdalgorithms taking a parameter named __root should assume that __root 46168404Spjdpoints to a proper red black tree (unless otherwise specified). 47168676Spjd 48185029SpjdEach algorithm herein assumes that __root->__parent_ points to a non-null 49185029Spjdstructure which has a member __left_ which points back to __root. No other 50219089Spjdmember is read or written to at __root->__parent_. 51219089Spjd 52219089Spjd__root->__parent_ will be referred to below (in comments only) as end_node. 53219089Spjdend_node->__left_ is an externably accessible lvalue for __root, and can be 54248571Smmchanged by node insertion and removal (without explicit reference to end_node). 55248571Smm 56260183SdelphijAll nodes (with the exception of end_node), even the node referred to as 57289422Smav__root, have a non-null __parent_ field. 58289422Smav 59289362Smav*/ 60289362Smav 61168404Spjd// Returns: true if __x is a left child of its parent, else false 62274673Sdelphij// Precondition: __x != nullptr. 63274673Sdelphijtemplate <class _NodePtr> 64274337Sdelphijinline _LIBCPP_INLINE_VISIBILITY 65274337Sdelphijbool 66274337Sdelphij__tree_is_left_child(_NodePtr __x) _NOEXCEPT 67274337Sdelphij{ 68274337Sdelphij return __x == __x->__parent_->__left_; 69274337Sdelphij} 70274337Sdelphij 71274337Sdelphij// Determintes if the subtree rooted at __x is a proper red black subtree. If 72274337Sdelphij// __x is a proper subtree, returns the black height (null counts as 1). If 73274337Sdelphij// __x is an improper subtree, returns 0. 74274681Sdelphijtemplate <class _NodePtr> 75274673Sdelphijunsigned 76274673Sdelphij__tree_sub_invariant(_NodePtr __x) 77274337Sdelphij{ 78219089Spjd if (__x == nullptr) 79219089Spjd return 1; 80219089Spjd // parent consistency checked by caller 81219089Spjd // check __x->__left_ consistency 82219089Spjd if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x) 83219089Spjd return 0; 84219089Spjd // check __x->__right_ consistency 85168404Spjd if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x) 86168404Spjd return 0; 87275782Sdelphij // check __x->__left_ != __x->__right_ unless both are nullptr 88275782Sdelphij if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr) 89296521Smav return 0; 90296521Smav // If this is red, neither child can be red 91168404Spjd if (!__x->__is_black_) 92185029Spjd { 93185029Spjd if (__x->__left_ && !__x->__left_->__is_black_) 94185029Spjd return 0; 95168404Spjd if (__x->__right_ && !__x->__right_->__is_black_) 96185029Spjd return 0; 97185029Spjd } 98185029Spjd unsigned __h = __tree_sub_invariant(__x->__left_); 99275782Sdelphij if (__h == 0) 100185029Spjd return 0; // invalid left subtree 101168404Spjd if (__h != __tree_sub_invariant(__x->__right_)) 102185029Spjd return 0; // invalid or different height right subtree 103185029Spjd return __h + __x->__is_black_; // return black height of this node 104168404Spjd} 105275782Sdelphij 106275782Sdelphij// Determintes if the red black tree rooted at __root is a proper red black tree. 107275782Sdelphij// __root == nullptr is a proper tree. Returns true is __root is a proper 108185029Spjd// red black tree, else returns false. 109185029Spjdtemplate <class _NodePtr> 110185029Spjdbool 111185029Spjd__tree_invariant(_NodePtr __root) 112185029Spjd{ 113168404Spjd if (__root == nullptr) 114219089Spjd return true; 115168404Spjd // check __x->__parent_ consistency 116219089Spjd if (__root->__parent_ == nullptr) 117168404Spjd return false; 118168404Spjd if (!__tree_is_left_child(__root)) 119185029Spjd return false; 120168404Spjd // root must be black 121219089Spjd if (!__root->__is_black_) 122168404Spjd return false; 123168404Spjd // do normal node checks 124168404Spjd return __tree_sub_invariant(__root) != 0; 125168404Spjd} 126168404Spjd 127168404Spjd// Returns: pointer to the left-most node under __x. 128236884Smm// Precondition: __x != nullptr. 129168404Spjdtemplate <class _NodePtr> 130239620Smminline _LIBCPP_INLINE_VISIBILITY 131239620Smm_NodePtr 132168404Spjd__tree_min(_NodePtr __x) _NOEXCEPT 133168404Spjd{ 134254757Sdelphij while (__x->__left_ != nullptr) 135168404Spjd __x = __x->__left_; 136168404Spjd return __x; 137185029Spjd} 138275782Sdelphij 139275782Sdelphij// Returns: pointer to the right-most node under __x. 140275782Sdelphij// Precondition: __x != nullptr. 141275782Sdelphijtemplate <class _NodePtr> 142289422Smavinline _LIBCPP_INLINE_VISIBILITY 143286708Smav_NodePtr 144286708Smav__tree_max(_NodePtr __x) _NOEXCEPT 145286708Smav{ 146286708Smav while (__x->__right_ != nullptr) 147289422Smav __x = __x->__right_; 148289422Smav return __x; 149289422Smav} 150289422Smav 151289422Smav// Returns: pointer to the next in-order node after __x. 152168404Spjd// Precondition: __x != nullptr. 153185029Spjdtemplate <class _NodePtr> 154185029Spjd_NodePtr 155185029Spjd__tree_next(_NodePtr __x) _NOEXCEPT 156277419Smav{ 157168404Spjd if (__x->__right_ != nullptr) 158168404Spjd return __tree_min(__x->__right_); 159185029Spjd while (!__tree_is_left_child(__x)) 160219089Spjd __x = __x->__parent_; 161219089Spjd return __x->__parent_; 162168404Spjd} 163260150Sdelphij 164260150Sdelphij// Returns: pointer to the previous in-order node before __x. 165260150Sdelphij// Precondition: __x != nullptr. 166260150Sdelphijtemplate <class _NodePtr> 167219089Spjd_NodePtr 168219089Spjd__tree_prev(_NodePtr __x) _NOEXCEPT 169219089Spjd{ 170219089Spjd if (__x->__left_ != nullptr) 171219089Spjd return __tree_max(__x->__left_); 172219089Spjd while (__tree_is_left_child(__x)) 173168404Spjd __x = __x->__parent_; 174219089Spjd return __x->__parent_; 175239620Smm} 176239620Smm 177185029Spjd// Returns: pointer to a node which has no children 178168404Spjd// Precondition: __x != nullptr. 179168404Spjdtemplate <class _NodePtr> 180168404Spjd_NodePtr 181286575Smav__tree_leaf(_NodePtr __x) _NOEXCEPT 182168404Spjd{ 183168404Spjd while (true) 184275782Sdelphij { 185185029Spjd if (__x->__left_ != nullptr) 186168404Spjd { 187219089Spjd __x = __x->__left_; 188219089Spjd continue; 189168404Spjd } 190168404Spjd if (__x->__right_ != nullptr) 191275782Sdelphij { 192185029Spjd __x = __x->__right_; 193185029Spjd continue; 194275782Sdelphij } 195168404Spjd break; 196185029Spjd } 197185029Spjd return __x; 198185029Spjd} 199277419Smav 200168404Spjd// Effects: Makes __x->__right_ the subtree root with __x as its left child 201168404Spjd// while preserving in-order order. 202219089Spjd// Precondition: __x->__right_ != nullptr 203219089Spjdtemplate <class _NodePtr> 204219089Spjdvoid 205219089Spjd__tree_left_rotate(_NodePtr __x) _NOEXCEPT 206219089Spjd{ 207219089Spjd _NodePtr __y = __x->__right_; 208219089Spjd __x->__right_ = __y->__left_; 209219089Spjd if (__x->__right_ != nullptr) 210219089Spjd __x->__right_->__parent_ = __x; 211219089Spjd __y->__parent_ = __x->__parent_; 212219089Spjd if (__tree_is_left_child(__x)) 213219089Spjd __x->__parent_->__left_ = __y; 214185029Spjd else 215275782Sdelphij __x->__parent_->__right_ = __y; 216275782Sdelphij __y->__left_ = __x; 217168404Spjd __x->__parent_ = __y; 218275782Sdelphij} 219185029Spjd 220275782Sdelphij// Effects: Makes __x->__left_ the subtree root with __x as its right child 221185029Spjd// while preserving in-order order. 222185029Spjd// Precondition: __x->__left_ != nullptr 223275782Sdelphijtemplate <class _NodePtr> 224185029Spjdvoid 225168404Spjd__tree_right_rotate(_NodePtr __x) _NOEXCEPT 226219089Spjd{ 227185029Spjd _NodePtr __y = __x->__left_; 228185029Spjd __x->__left_ = __y->__right_; 229185029Spjd if (__x->__left_ != nullptr) 230168404Spjd __x->__left_->__parent_ = __x; 231168404Spjd __y->__parent_ = __x->__parent_; 232275782Sdelphij if (__tree_is_left_child(__x)) 233275782Sdelphij __x->__parent_->__left_ = __y; 234275782Sdelphij else 235275782Sdelphij __x->__parent_->__right_ = __y; 236275782Sdelphij __y->__right_ = __x; 237275782Sdelphij __x->__parent_ = __y; 238168404Spjd} 239185029Spjd 240185029Spjd// Effects: Rebalances __root after attaching __x to a leaf. 241168404Spjd// Precondition: __root != nulptr && __x != nullptr. 242168404Spjd// __x has no children. 243168404Spjd// __x == __root or == a direct or indirect child of __root. 244168404Spjd// If __x were to be unlinked from __root (setting __root to 245168404Spjd// nullptr if __root == __x), __tree_invariant(__root) == true. 246168404Spjd// Postcondition: __tree_invariant(end_node->__left_) == true. end_node->__left_ 247168404Spjd// may be different than the value passed in as __root. 248168404Spjdtemplate <class _NodePtr> 249168404Spjdvoid 250168404Spjd__tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT 251168404Spjd{ 252168404Spjd __x->__is_black_ = __x == __root; 253168404Spjd while (__x != __root && !__x->__parent_->__is_black_) 254168404Spjd { 255168404Spjd // __x->__parent_ != __root because __x->__parent_->__is_black == false 256168404Spjd if (__tree_is_left_child(__x->__parent_)) 257168404Spjd { 258168404Spjd _NodePtr __y = __x->__parent_->__parent_->__right_; 259168404Spjd if (__y != nullptr && !__y->__is_black_) 260168404Spjd { 261168404Spjd __x = __x->__parent_; 262168404Spjd __x->__is_black_ = true; 263275782Sdelphij __x = __x->__parent_; 264168404Spjd __x->__is_black_ = __x == __root; 265168404Spjd __y->__is_black_ = true; 266209962Smm } 267219089Spjd else 268219089Spjd { 269168404Spjd if (!__tree_is_left_child(__x)) 270260150Sdelphij { 271260150Sdelphij __x = __x->__parent_; 272219089Spjd __tree_left_rotate(__x); 273219089Spjd } 274219089Spjd __x = __x->__parent_; 275219089Spjd __x->__is_black_ = true; 276219089Spjd __x = __x->__parent_; 277168404Spjd __x->__is_black_ = false; 278168404Spjd __tree_right_rotate(__x); 279168404Spjd break; 280286575Smav } 281168404Spjd } 282286575Smav else 283168404Spjd { 284248571Smm _NodePtr __y = __x->__parent_->__parent_->__left_; 285168404Spjd if (__y != nullptr && !__y->__is_black_) 286286575Smav { 287286575Smav __x = __x->__parent_; 288185029Spjd __x->__is_black_ = true; 289168404Spjd __x = __x->__parent_; 290219089Spjd __x->__is_black_ = __x == __root; 291219089Spjd __y->__is_black_ = true; 292168404Spjd } 293168404Spjd else 294248571Smm { 295168404Spjd if (__tree_is_left_child(__x)) 296168404Spjd { 297168404Spjd __x = __x->__parent_; 298219089Spjd __tree_right_rotate(__x); 299286575Smav } 300219089Spjd __x = __x->__parent_; 301185029Spjd __x->__is_black_ = true; 302286575Smav __x = __x->__parent_; 303168404Spjd __x->__is_black_ = false; 304185029Spjd __tree_left_rotate(__x); 305168404Spjd break; 306288204Sdelphij } 307185029Spjd } 308185029Spjd } 309168404Spjd} 310185029Spjd 311185029Spjd// Precondition: __root != nullptr && __z != nullptr. 312185029Spjd// __tree_invariant(__root) == true. 313268713Sdelphij// __z == __root or == a direct or indirect child of __root. 314248571Smm// Effects: unlinks __z from the tree rooted at __root, rebalancing as needed. 315168404Spjd// Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_ 316168404Spjd// nor any of its children refer to __z. end_node->__left_ 317168404Spjd// may be different than the value passed in as __root. 318168404Spjdtemplate <class _NodePtr> 319248571Smmvoid 320168404Spjd__tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT 321168404Spjd{ 322168404Spjd // __z will be removed from the tree. Client still needs to destruct/deallocate it 323168404Spjd // __y is either __z, or if __z has two children, __tree_next(__z). 324168404Spjd // __y will have at most one child. 325168404Spjd // __y will be the initial hole in the tree (make the hole at a leaf) 326168404Spjd _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ? 327168404Spjd __z : __tree_next(__z); 328168404Spjd // __x is __y's possibly null single child 329168404Spjd _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_; 330275782Sdelphij // __w is __x's possibly null uncle (will become __x's sibling) 331168404Spjd _NodePtr __w = nullptr; 332168404Spjd // link __x to __y's parent, and find __w 333275782Sdelphij if (__x != nullptr) 334168404Spjd __x->__parent_ = __y->__parent_; 335248571Smm if (__tree_is_left_child(__y)) 336168404Spjd { 337168404Spjd __y->__parent_->__left_ = __x; 338168404Spjd if (__y != __root) 339185029Spjd __w = __y->__parent_->__right_; 340168404Spjd else 341168404Spjd __root = __x; // __w == nullptr 342168404Spjd } 343168404Spjd else 344248571Smm { 345185029Spjd __y->__parent_->__right_ = __x; 346168404Spjd // __y can't be root if it is a right child 347185029Spjd __w = __y->__parent_->__left_; 348275782Sdelphij } 349185029Spjd bool __removed_black = __y->__is_black_; 350185029Spjd // If we didn't remove __z, do so now by splicing in __y for __z, 351185029Spjd // but copy __z's color. This does not impact __x or __w. 352275782Sdelphij if (__y != __z) 353185029Spjd { 354185029Spjd // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr 355185029Spjd __y->__parent_ = __z->__parent_; 356185029Spjd if (__tree_is_left_child(__z)) 357185029Spjd __y->__parent_->__left_ = __y; 358185029Spjd else 359185029Spjd __y->__parent_->__right_ = __y; 360185029Spjd __y->__left_ = __z->__left_; 361185029Spjd __y->__left_->__parent_ = __y; 362185029Spjd __y->__right_ = __z->__right_; 363185029Spjd if (__y->__right_ != nullptr) 364248571Smm __y->__right_->__parent_ = __y; 365264835Sdelphij __y->__is_black_ = __z->__is_black_; 366264835Sdelphij if (__root == __z) 367185029Spjd __root = __y; 368185029Spjd } 369275782Sdelphij // There is no need to rebalance if we removed a red, or if we removed 370185029Spjd // the last node. 371185029Spjd if (__removed_black && __root != nullptr) 372185029Spjd { 373219089Spjd // Rebalance: 374219089Spjd // __x has an implicit black color (transferred from the removed __y) 375275782Sdelphij // associated with it, no matter what its color is. 376185029Spjd // If __x is __root (in which case it can't be null), it is supposed 377185029Spjd // to be black anyway, and if it is doubly black, then the double 378185029Spjd // can just be ignored. 379185029Spjd // If __x is red (in which case it can't be null), then it can absorb 380185029Spjd // the implicit black just by setting its color to black. 381185029Spjd // Since __y was black and only had one child (which __x points to), __x 382185029Spjd // is either red with no children, else null, otherwise __y would have 383264835Sdelphij // different black heights under left and right pointers. 384264835Sdelphij // if (__x == __root || __x != nullptr && !__x->__is_black_) 385264835Sdelphij if (__x != nullptr) 386264835Sdelphij __x->__is_black_ = true; 387264835Sdelphij else 388185029Spjd { 389185029Spjd // Else __x isn't root, and is "doubly black", even though it may 390185029Spjd // be null. __w can not be null here, else the parent would 391286541Smav // see a black height >= 2 on the __x side and a black height 392286541Smav // of 1 on the __w side (__w must be a non-null black or a red 393286541Smav // with a non-null black child). 394286543Smav while (true) 395286543Smav { 396286543Smav if (!__tree_is_left_child(__w)) // if x is left child 397286543Smav { 398286543Smav if (!__w->__is_black_) 399286543Smav { 400286543Smav __w->__is_black_ = true; 401286543Smav __w->__parent_->__is_black_ = false; 402286543Smav __tree_left_rotate(__w->__parent_); 403286543Smav // __x is still valid 404286543Smav // reset __root only if necessary 405286543Smav if (__root == __w->__left_) 406286543Smav __root = __w; 407286541Smav // reset sibling, and it still can't be null 408286541Smav __w = __w->__left_->__right_; 409248571Smm } 410248571Smm // __w->__is_black_ is now true, __w may have null children 411185029Spjd if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && 412185029Spjd (__w->__right_ == nullptr || __w->__right_->__is_black_)) 413168404Spjd { 414168404Spjd __w->__is_black_ = false; 415168404Spjd __x = __w->__parent_; 416168404Spjd // __x can no longer be null 417219089Spjd if (__x == __root || !__x->__is_black_) 418168404Spjd { 419248571Smm __x->__is_black_ = true; 420168404Spjd break; 421168404Spjd } 422248571Smm // reset sibling, and it still can't be null 423168404Spjd __w = __tree_is_left_child(__x) ? 424219089Spjd __x->__parent_->__right_ : 425219089Spjd __x->__parent_->__left_; 426219089Spjd // continue; 427259813Sdelphij } 428251632Sdelphij else // __w has a red child 429249195Smm { 430251632Sdelphij if (__w->__right_ == nullptr || __w->__right_->__is_black_) 431219089Spjd { 432168404Spjd // __w left child is non-null and red 433168404Spjd __w->__left_->__is_black_ = true; 434247187Smm __w->__is_black_ = false; 435168404Spjd __tree_right_rotate(__w); 436168404Spjd // __w is known not to be root, so root hasn't changed 437168404Spjd // reset sibling, and it still can't be null 438168404Spjd __w = __w->__parent_; 439286575Smav } 440168404Spjd // __w has a right red child, left child may be null 441168404Spjd __w->__is_black_ = __w->__parent_->__is_black_; 442185029Spjd __w->__parent_->__is_black_ = true; 443235222Smm __w->__right_->__is_black_ = true; 444248571Smm __tree_left_rotate(__w->__parent_); 445235222Smm break; 446219089Spjd } 447219089Spjd } 448275782Sdelphij else 449219089Spjd { 450235222Smm if (!__w->__is_black_) 451235222Smm { 452235222Smm __w->__is_black_ = true; 453288204Sdelphij __w->__parent_->__is_black_ = false; 454288204Sdelphij __tree_right_rotate(__w->__parent_); 455288204Sdelphij // __x is still valid 456274337Sdelphij // reset __root only if necessary 457286708Smav if (__root == __w->__right_) 458286708Smav __root = __w; 459286708Smav // reset sibling, and it still can't be null 460286708Smav __w = __w->__right_->__left_; 461286708Smav } 462286708Smav // __w->__is_black_ is now true, __w may have null children 463286708Smav if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && 464286708Smav (__w->__right_ == nullptr || __w->__right_->__is_black_)) 465286708Smav { 466286708Smav __w->__is_black_ = false; 467286708Smav __x = __w->__parent_; 468286708Smav // __x can no longer be null 469275515Sdelphij if (!__x->__is_black_ || __x == __root) 470274337Sdelphij { 471274337Sdelphij __x->__is_black_ = true; 472286708Smav break; 473286708Smav } 474248571Smm // reset sibling, and it still can't be null 475168404Spjd __w = __tree_is_left_child(__x) ? 476185029Spjd __x->__parent_->__right_ : 477268713Sdelphij __x->__parent_->__left_; 478248571Smm // continue; 479219089Spjd } 480219089Spjd else // __w has a red child 481168404Spjd { 482168404Spjd if (__w->__left_ == nullptr || __w->__left_->__is_black_) 483168404Spjd { 484168404Spjd // __w right child is non-null and red 485168404Spjd __w->__right_->__is_black_ = true; 486286575Smav __w->__is_black_ = false; 487168404Spjd __tree_left_rotate(__w); 488275782Sdelphij // __w is known not to be root, so root hasn't changed 489248571Smm // reset sibling, and it still can't be null 490275782Sdelphij __w = __w->__parent_; 491185029Spjd } 492168404Spjd // __w has a left red child, right child may be null 493260183Sdelphij __w->__is_black_ = __w->__parent_->__is_black_; 494260183Sdelphij __w->__parent_->__is_black_ = true; 495260183Sdelphij __w->__left_->__is_black_ = true; 496260183Sdelphij __tree_right_rotate(__w->__parent_); 497260183Sdelphij break; 498260183Sdelphij } 499260183Sdelphij } 500260183Sdelphij } 501219089Spjd } 502219089Spjd } 503219089Spjd} 504275782Sdelphij 505275782Sdelphijtemplate <class _Allocator> class __map_node_destructor; 506219089Spjd 507219089Spjdtemplate <class _Allocator> 508275782Sdelphijclass __tree_node_destructor 509219089Spjd{ 510168404Spjd typedef _Allocator allocator_type; 511168404Spjd typedef allocator_traits<allocator_type> __alloc_traits; 512168404Spjd typedef typename __alloc_traits::value_type::value_type value_type; 513286575Smavpublic: 514248571Smm typedef typename __alloc_traits::pointer pointer; 515248571Smmprivate: 516248571Smm 517185029Spjd allocator_type& __na_; 518248571Smm 519248571Smm __tree_node_destructor& operator=(const __tree_node_destructor&); 520248571Smm 521185029Spjdpublic: 522185029Spjd bool __value_constructed; 523185029Spjd 524185029Spjd _LIBCPP_INLINE_VISIBILITY 525185029Spjd explicit __tree_node_destructor(allocator_type& __na) _NOEXCEPT 526286575Smav : __na_(__na), 527286575Smav __value_constructed(false) 528286575Smav {} 529286575Smav 530286575Smav _LIBCPP_INLINE_VISIBILITY 531219089Spjd void operator()(pointer __p) _NOEXCEPT 532219089Spjd { 533185029Spjd if (__value_constructed) 534248571Smm __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 535248571Smm if (__p) 536168404Spjd __alloc_traits::deallocate(__na_, __p, 1); 537185029Spjd } 538268713Sdelphij 539248571Smm template <class> friend class __map_node_destructor; 540168404Spjd}; 541248571Smm 542168404Spjd// node 543168404Spjd 544168404Spjdtemplate <class _Pointer> 545168404Spjdclass __tree_end_node 546168404Spjd{ 547185029Spjdpublic: 548275782Sdelphij typedef _Pointer pointer; 549168404Spjd pointer __left_; 550168404Spjd 551168404Spjd _LIBCPP_INLINE_VISIBILITY 552275782Sdelphij __tree_end_node() _NOEXCEPT : __left_() {} 553275782Sdelphij}; 554185029Spjd 555185029Spjdtemplate <class _VoidPtr> 556168404Spjdclass __tree_node_base 557168404Spjd : public __tree_end_node 558168404Spjd < 559168404Spjd typename pointer_traits<_VoidPtr>::template 560168404Spjd#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 561248571Smm rebind<__tree_node_base<_VoidPtr> > 562219089Spjd#else 563185029Spjd rebind<__tree_node_base<_VoidPtr> >::other 564168404Spjd#endif 565185029Spjd > 566168404Spjd{ 567168404Spjd __tree_node_base(const __tree_node_base&); 568286705Smav __tree_node_base& operator=(const __tree_node_base&); 569168404Spjdpublic: 570248571Smm typedef typename pointer_traits<_VoidPtr>::template 571248571Smm#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 572168404Spjd rebind<__tree_node_base> 573168404Spjd#else 574248571Smm rebind<__tree_node_base>::other 575275782Sdelphij#endif 576248571Smm pointer; 577286705Smav typedef typename pointer_traits<_VoidPtr>::template 578185029Spjd#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 579249195Smm rebind<const __tree_node_base> 580168404Spjd#else 581185029Spjd rebind<const __tree_node_base>::other 582185029Spjd#endif 583286705Smav const_pointer; 584168404Spjd typedef __tree_end_node<pointer> base; 585185029Spjd 586286705Smav pointer __right_; 587248571Smm pointer __parent_; 588249195Smm bool __is_black_; 589168404Spjd 590168404Spjd _LIBCPP_INLINE_VISIBILITY 591185029Spjd __tree_node_base() _NOEXCEPT 592286705Smav : __right_(), __parent_(), __is_black_(false) {} 593185029Spjd}; 594286705Smav 595286705Smavtemplate <class _Tp, class _VoidPtr> 596185029Spjdclass __tree_node 597248571Smm : public __tree_node_base<_VoidPtr> 598286705Smav{ 599286705Smavpublic: 600286705Smav typedef __tree_node_base<_VoidPtr> base; 601286705Smav typedef _Tp value_type; 602286705Smav 603286705Smav value_type __value_; 604168404Spjd 605168404Spjd#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 606286705Smav template <class ..._Args> 607286705Smav _LIBCPP_INLINE_VISIBILITY 608248571Smm explicit __tree_node(_Args&& ...__args) 609168404Spjd : __value_(_VSTD::forward<_Args>(__args)...) {} 610168404Spjd#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 611168404Spjd _LIBCPP_INLINE_VISIBILITY 612168404Spjd explicit __tree_node(const value_type& __v) 613248571Smm : __value_(__v) {} 614219089Spjd#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 615168404Spjd}; 616248571Smm 617248571Smmtemplate <class _TreeIterator> class _LIBCPP_TYPE_VIS __map_iterator; 618185029Spjdtemplate <class _TreeIterator> class _LIBCPP_TYPE_VIS __map_const_iterator; 619248571Smm 620219089Spjdtemplate <class _Tp, class _NodePtr, class _DiffType> 621248571Smmclass _LIBCPP_TYPE_VIS __tree_iterator 622249195Smm{ 623185029Spjd typedef _NodePtr __node_pointer; 624185029Spjd typedef typename pointer_traits<__node_pointer>::element_type __node; 625168404Spjd typedef typename __node::base __node_base; 626168404Spjd typedef typename __node_base::pointer __node_base_pointer; 627248571Smm 628248571Smm __node_pointer __ptr_; 629248571Smm 630248571Smm typedef pointer_traits<__node_pointer> __pointer_traits; 631248571Smmpublic: 632248571Smm typedef bidirectional_iterator_tag iterator_category; 633248571Smm typedef _Tp value_type; 634248571Smm typedef _DiffType difference_type; 635248571Smm typedef value_type& reference; 636249195Smm typedef typename pointer_traits<__node_pointer>::template 637248571Smm#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 638248571Smm rebind<value_type> 639248571Smm#else 640248571Smm rebind<value_type>::other 641248571Smm#endif 642248571Smm pointer; 643248571Smm 644248571Smm _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT {} 645248571Smm 646248571Smm _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} 647248571Smm _LIBCPP_INLINE_VISIBILITY pointer operator->() const 648248571Smm {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 649248571Smm 650168404Spjd _LIBCPP_INLINE_VISIBILITY 651248571Smm __tree_iterator& operator++() 652248571Smm {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_))); 653248571Smm return *this;} 654248571Smm _LIBCPP_INLINE_VISIBILITY 655248571Smm __tree_iterator operator++(int) 656248571Smm {__tree_iterator __t(*this); ++(*this); return __t;} 657248571Smm 658248571Smm _LIBCPP_INLINE_VISIBILITY 659248571Smm __tree_iterator& operator--() 660248571Smm {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_))); 661248571Smm return *this;} 662248571Smm _LIBCPP_INLINE_VISIBILITY 663248571Smm __tree_iterator operator--(int) 664248571Smm {__tree_iterator __t(*this); --(*this); return __t;} 665248571Smm 666248571Smm friend _LIBCPP_INLINE_VISIBILITY 667248571Smm bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) 668248571Smm {return __x.__ptr_ == __y.__ptr_;} 669248571Smm friend _LIBCPP_INLINE_VISIBILITY 670248571Smm bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) 671168404Spjd {return !(__x == __y);} 672168404Spjd 673168404Spjdprivate: 674168404Spjd _LIBCPP_INLINE_VISIBILITY 675168404Spjd explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 676168404Spjd template <class, class, class> friend class __tree; 677248571Smm template <class, class, class> friend class _LIBCPP_TYPE_VIS __tree_const_iterator; 678168404Spjd template <class> friend class _LIBCPP_TYPE_VIS __map_iterator; 679168404Spjd template <class, class, class, class> friend class _LIBCPP_TYPE_VIS map; 680185029Spjd template <class, class, class, class> friend class _LIBCPP_TYPE_VIS multimap; 681185029Spjd template <class, class, class> friend class _LIBCPP_TYPE_VIS set; 682185029Spjd template <class, class, class> friend class _LIBCPP_TYPE_VIS multiset; 683185029Spjd}; 684168404Spjd 685168404Spjdtemplate <class _Tp, class _ConstNodePtr, class _DiffType> 686168404Spjdclass _LIBCPP_TYPE_VIS __tree_const_iterator 687168404Spjd{ 688168404Spjd typedef _ConstNodePtr __node_pointer; 689168404Spjd typedef typename pointer_traits<__node_pointer>::element_type __node; 690168404Spjd typedef typename __node::base __node_base; 691168404Spjd typedef typename pointer_traits<__node_pointer>::template 692168404Spjd#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 693168404Spjd rebind<__node_base> 694168404Spjd#else 695168404Spjd rebind<__node_base>::other 696248571Smm#endif 697168404Spjd __node_base_pointer; 698185029Spjd 699185029Spjd __node_pointer __ptr_; 700185029Spjd 701185029Spjd typedef pointer_traits<__node_pointer> __pointer_traits; 702219089Spjdpublic: 703185029Spjd typedef bidirectional_iterator_tag iterator_category; 704275735Sdelphij typedef _Tp value_type; 705275735Sdelphij typedef _DiffType difference_type; 706185029Spjd typedef const value_type& reference; 707168404Spjd typedef typename pointer_traits<__node_pointer>::template 708185029Spjd#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 709168404Spjd rebind<const value_type> 710248571Smm#else 711275735Sdelphij rebind<const value_type>::other 712185029Spjd#endif 713168404Spjd pointer; 714185029Spjd 715248571Smm _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() {} 716185029Spjdprivate: 717185029Spjd typedef typename remove_const<__node>::type __non_const_node; 718185029Spjd typedef typename pointer_traits<__node_pointer>::template 719289362Smav#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 720185029Spjd rebind<__non_const_node> 721248571Smm#else 722219089Spjd rebind<__non_const_node>::other 723248571Smm#endif 724185029Spjd __non_const_node_pointer; 725185029Spjd typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type> 726185029Spjd __non_const_iterator; 727185029Spjdpublic: 728168404Spjd _LIBCPP_INLINE_VISIBILITY 729168404Spjd __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT 730289362Smav : __ptr_(__p.__ptr_) {} 731289362Smav 732289362Smav _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} 733289362Smav _LIBCPP_INLINE_VISIBILITY pointer operator->() const 734289362Smav {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);} 735289362Smav 736289362Smav _LIBCPP_INLINE_VISIBILITY 737289362Smav __tree_const_iterator& operator++() 738289362Smav {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_))); 739289362Smav return *this;} 740286708Smav _LIBCPP_INLINE_VISIBILITY 741286708Smav __tree_const_iterator operator++(int) 742286708Smav {__tree_const_iterator __t(*this); ++(*this); return __t;} 743286708Smav 744286708Smav _LIBCPP_INLINE_VISIBILITY 745286708Smav __tree_const_iterator& operator--() 746286708Smav {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_))); 747286708Smav return *this;} 748286708Smav _LIBCPP_INLINE_VISIBILITY 749286708Smav __tree_const_iterator operator--(int) 750286708Smav {__tree_const_iterator __t(*this); --(*this); return __t;} 751286708Smav 752286708Smav friend _LIBCPP_INLINE_VISIBILITY 753286708Smav bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 754286708Smav {return __x.__ptr_ == __y.__ptr_;} 755286708Smav friend _LIBCPP_INLINE_VISIBILITY 756286708Smav bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) 757286708Smav {return !(__x == __y);} 758286708Smav 759286708Smavprivate: 760286708Smav _LIBCPP_INLINE_VISIBILITY 761286708Smav explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT 762286708Smav : __ptr_(__p) {} 763286708Smav template <class, class, class> friend class __tree; 764286708Smav template <class, class, class, class> friend class _LIBCPP_TYPE_VIS map; 765286708Smav template <class, class, class, class> friend class _LIBCPP_TYPE_VIS multimap; 766286708Smav template <class, class, class> friend class _LIBCPP_TYPE_VIS set; 767286708Smav template <class, class, class> friend class _LIBCPP_TYPE_VIS multiset; 768185029Spjd template <class> friend class _LIBCPP_TYPE_VIS __map_const_iterator; 769185029Spjd}; 770185029Spjd 771185029Spjdtemplate <class _Tp, class _Compare, class _Allocator> 772185029Spjdclass __tree 773168404Spjd{ 774168404Spjdpublic: 775168404Spjd typedef _Tp value_type; 776185029Spjd typedef _Compare value_compare; 777168404Spjd typedef _Allocator allocator_type; 778185029Spjd typedef allocator_traits<allocator_type> __alloc_traits; 779185029Spjd typedef typename __alloc_traits::pointer pointer; 780168404Spjd typedef typename __alloc_traits::const_pointer const_pointer; 781185029Spjd typedef typename __alloc_traits::size_type size_type; 782275782Sdelphij typedef typename __alloc_traits::difference_type difference_type; 783185029Spjd 784275782Sdelphij typedef typename __alloc_traits::void_pointer __void_pointer; 785185029Spjd 786168404Spjd typedef __tree_node<value_type, __void_pointer> __node; 787168404Spjd typedef __tree_node_base<__void_pointer> __node_base; 788248571Smm typedef typename __alloc_traits::template 789168404Spjd#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 790168404Spjd rebind_alloc<__node> 791185029Spjd#else 792168404Spjd rebind_alloc<__node>::other 793185029Spjd#endif 794168404Spjd __node_allocator; 795236823Spjd typedef allocator_traits<__node_allocator> __node_traits; 796236823Spjd typedef typename __node_traits::pointer __node_pointer; 797236823Spjd typedef typename __node_traits::pointer __node_const_pointer; 798236823Spjd typedef typename __node_base::pointer __node_base_pointer; 799168404Spjd typedef typename __node_base::pointer __node_base_const_pointer; 800185029Spjdprivate: 801185029Spjd typedef typename __node_base::base __end_node_t; 802168404Spjd typedef typename pointer_traits<__node_pointer>::template 803185029Spjd#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 804185029Spjd rebind<__end_node_t> 805219089Spjd#else 806219089Spjd rebind<__end_node_t>::other 807219089Spjd#endif 808248571Smm __end_node_ptr; 809219089Spjd typedef typename pointer_traits<__node_pointer>::template 810185029Spjd#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 811185029Spjd rebind<__end_node_t> 812275782Sdelphij#else 813236884Smm rebind<__end_node_t>::other 814275782Sdelphij#endif 815185029Spjd __end_node_const_ptr; 816275782Sdelphij 817185029Spjd __node_pointer __begin_node_; 818275782Sdelphij __compressed_pair<__end_node_t, __node_allocator> __pair1_; 819275782Sdelphij __compressed_pair<size_type, value_compare> __pair3_; 820185029Spjd 821272583Sdelphijpublic: 822272583Sdelphij _LIBCPP_INLINE_VISIBILITY 823272583Sdelphij __node_pointer __end_node() _NOEXCEPT 824272583Sdelphij { 825275782Sdelphij return static_cast<__node_pointer> 826272583Sdelphij ( 827272583Sdelphij pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first()) 828286708Smav ); 829286708Smav } 830286708Smav _LIBCPP_INLINE_VISIBILITY 831286708Smav __node_const_pointer __end_node() const _NOEXCEPT 832274337Sdelphij { 833185029Spjd return static_cast<__node_const_pointer> 834275782Sdelphij ( 835185029Spjd pointer_traits<__end_node_const_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first())) 836248571Smm ); 837275782Sdelphij } 838275782Sdelphij _LIBCPP_INLINE_VISIBILITY 839219089Spjd __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();} 840219089Spjdprivate: 841219089Spjd _LIBCPP_INLINE_VISIBILITY 842219089Spjd const __node_allocator& __node_alloc() const _NOEXCEPT 843185029Spjd {return __pair1_.second();} 844275782Sdelphij _LIBCPP_INLINE_VISIBILITY 845275782Sdelphij __node_pointer& __begin_node() _NOEXCEPT {return __begin_node_;} 846185029Spjd _LIBCPP_INLINE_VISIBILITY 847185029Spjd const __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;} 848185029Spjdpublic: 849248571Smm _LIBCPP_INLINE_VISIBILITY 850275782Sdelphij allocator_type __alloc() const _NOEXCEPT 851275782Sdelphij {return allocator_type(__node_alloc());} 852185029Spjdprivate: 853185029Spjd _LIBCPP_INLINE_VISIBILITY 854185029Spjd size_type& size() _NOEXCEPT {return __pair3_.first();} 855275782Sdelphijpublic: 856219089Spjd _LIBCPP_INLINE_VISIBILITY 857275782Sdelphij const size_type& size() const _NOEXCEPT {return __pair3_.first();} 858219089Spjd _LIBCPP_INLINE_VISIBILITY 859275782Sdelphij value_compare& value_comp() _NOEXCEPT {return __pair3_.second();} 860219089Spjd _LIBCPP_INLINE_VISIBILITY 861219089Spjd const value_compare& value_comp() const _NOEXCEPT 862219089Spjd {return __pair3_.second();} 863248571Smmpublic: 864275782Sdelphij _LIBCPP_INLINE_VISIBILITY 865275782Sdelphij __node_pointer __root() _NOEXCEPT 866219089Spjd {return static_cast<__node_pointer> (__end_node()->__left_);} 867185029Spjd _LIBCPP_INLINE_VISIBILITY 868185029Spjd __node_const_pointer __root() const _NOEXCEPT 869185029Spjd {return static_cast<__node_const_pointer>(__end_node()->__left_);} 870185029Spjd 871185029Spjd typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator; 872168404Spjd typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator; 873168404Spjd 874168404Spjd explicit __tree(const value_compare& __comp) 875275782Sdelphij _NOEXCEPT_( 876168404Spjd is_nothrow_default_constructible<__node_allocator>::value && 877185029Spjd is_nothrow_copy_constructible<value_compare>::value); 878168404Spjd explicit __tree(const allocator_type& __a); 879168404Spjd __tree(const value_compare& __comp, const allocator_type& __a); 880248571Smm __tree(const __tree& __t); 881248571Smm __tree& operator=(const __tree& __t); 882248571Smm template <class _InputIterator> 883248571Smm void __assign_unique(_InputIterator __first, _InputIterator __last); 884248571Smm template <class _InputIterator> 885248571Smm void __assign_multi(_InputIterator __first, _InputIterator __last); 886248571Smm#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 887248571Smm __tree(__tree&& __t) 888248571Smm _NOEXCEPT_( 889248571Smm is_nothrow_move_constructible<__node_allocator>::value && 890168404Spjd is_nothrow_move_constructible<value_compare>::value); 891185029Spjd __tree(__tree&& __t, const allocator_type& __a); 892185029Spjd __tree& operator=(__tree&& __t) 893168404Spjd _NOEXCEPT_( 894168404Spjd __node_traits::propagate_on_container_move_assignment::value && 895168404Spjd is_nothrow_move_assignable<value_compare>::value && 896168404Spjd is_nothrow_move_assignable<__node_allocator>::value); 897168404Spjd#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 898248571Smm 899168404Spjd ~__tree(); 900168404Spjd 901185029Spjd _LIBCPP_INLINE_VISIBILITY 902248571Smm iterator begin() _NOEXCEPT {return iterator(__begin_node());} 903168404Spjd _LIBCPP_INLINE_VISIBILITY 904248571Smm const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());} 905248571Smm _LIBCPP_INLINE_VISIBILITY 906168404Spjd iterator end() _NOEXCEPT {return iterator(__end_node());} 907185029Spjd _LIBCPP_INLINE_VISIBILITY 908168404Spjd const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());} 909264835Sdelphij 910264835Sdelphij _LIBCPP_INLINE_VISIBILITY 911264835Sdelphij size_type max_size() const _NOEXCEPT 912264835Sdelphij {return __node_traits::max_size(__node_alloc());} 913264835Sdelphij 914264835Sdelphij void clear() _NOEXCEPT; 915264835Sdelphij 916264835Sdelphij void swap(__tree& __t) 917264835Sdelphij _NOEXCEPT_( 918264835Sdelphij __is_nothrow_swappable<value_compare>::value && 919264835Sdelphij (!__node_traits::propagate_on_container_swap::value || 920264835Sdelphij __is_nothrow_swappable<__node_allocator>::value)); 921264835Sdelphij 922264835Sdelphij#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 923264835Sdelphij#ifndef _LIBCPP_HAS_NO_VARIADICS 924248571Smm template <class... _Args> 925168404Spjd pair<iterator, bool> 926219089Spjd __emplace_unique(_Args&&... __args); 927219089Spjd template <class... _Args> 928219089Spjd iterator 929219089Spjd __emplace_multi(_Args&&... __args); 930248571Smm 931219089Spjd template <class... _Args> 932219089Spjd iterator 933248571Smm __emplace_hint_unique(const_iterator __p, _Args&&... __args); 934248571Smm template <class... _Args> 935219089Spjd iterator 936219089Spjd __emplace_hint_multi(const_iterator __p, _Args&&... __args); 937219089Spjd#endif // _LIBCPP_HAS_NO_VARIADICS 938168404Spjd 939168404Spjd template <class _Vp> 940168404Spjd pair<iterator, bool> __insert_unique(_Vp&& __v); 941228103Smm template <class _Vp> 942228103Smm iterator __insert_unique(const_iterator __p, _Vp&& __v); 943168404Spjd template <class _Vp> 944228103Smm iterator __insert_multi(_Vp&& __v); 945228103Smm template <class _Vp> 946168404Spjd iterator __insert_multi(const_iterator __p, _Vp&& __v); 947168404Spjd#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 948168404Spjd 949228103Smm pair<iterator, bool> __insert_unique(const value_type& __v); 950168404Spjd iterator __insert_unique(const_iterator __p, const value_type& __v); 951168404Spjd iterator __insert_multi(const value_type& __v); 952168404Spjd iterator __insert_multi(const_iterator __p, const value_type& __v); 953219089Spjd 954168404Spjd pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 955219089Spjd iterator __node_insert_unique(const_iterator __p, 956248493Smm __node_pointer __nd); 957248493Smm 958219089Spjd iterator __node_insert_multi(__node_pointer __nd); 959228103Smm iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); 960228103Smm 961228103Smm iterator erase(const_iterator __p); 962228103Smm iterator erase(const_iterator __f, const_iterator __l); 963248571Smm template <class _Key> 964228103Smm size_type __erase_unique(const _Key& __k); 965228103Smm template <class _Key> 966228103Smm size_type __erase_multi(const _Key& __k); 967228103Smm 968228103Smm void __insert_node_at(__node_base_pointer __parent, 969228103Smm __node_base_pointer& __child, 970228103Smm __node_base_pointer __new_node); 971228103Smm 972228103Smm template <class _Key> 973228103Smm iterator find(const _Key& __v); 974228103Smm template <class _Key> 975228103Smm const_iterator find(const _Key& __v) const; 976185029Spjd 977168404Spjd template <class _Key> 978228103Smm size_type __count_unique(const _Key& __k) const; 979228103Smm template <class _Key> 980168404Spjd size_type __count_multi(const _Key& __k) const; 981168404Spjd 982185029Spjd template <class _Key> 983185029Spjd _LIBCPP_INLINE_VISIBILITY 984185029Spjd iterator lower_bound(const _Key& __v) 985185029Spjd {return __lower_bound(__v, __root(), __end_node());} 986185029Spjd template <class _Key> 987185029Spjd iterator __lower_bound(const _Key& __v, 988185029Spjd __node_pointer __root, 989248571Smm __node_pointer __result); 990185029Spjd template <class _Key> 991185029Spjd _LIBCPP_INLINE_VISIBILITY 992185029Spjd const_iterator lower_bound(const _Key& __v) const 993185029Spjd {return __lower_bound(__v, __root(), __end_node());} 994185029Spjd template <class _Key> 995286575Smav const_iterator __lower_bound(const _Key& __v, 996185029Spjd __node_const_pointer __root, 997275782Sdelphij __node_const_pointer __result) const; 998275782Sdelphij template <class _Key> 999185029Spjd _LIBCPP_INLINE_VISIBILITY 1000185029Spjd iterator upper_bound(const _Key& __v) 1001185029Spjd {return __upper_bound(__v, __root(), __end_node());} 1002219089Spjd template <class _Key> 1003185029Spjd iterator __upper_bound(const _Key& __v, 1004185029Spjd __node_pointer __root, 1005275782Sdelphij __node_pointer __result); 1006275782Sdelphij template <class _Key> 1007185029Spjd _LIBCPP_INLINE_VISIBILITY 1008219089Spjd const_iterator upper_bound(const _Key& __v) const 1009185029Spjd {return __upper_bound(__v, __root(), __end_node());} 1010275782Sdelphij template <class _Key> 1011185029Spjd const_iterator __upper_bound(const _Key& __v, 1012185029Spjd __node_const_pointer __root, 1013248571Smm __node_const_pointer __result) const; 1014248571Smm template <class _Key> 1015219089Spjd pair<iterator, iterator> 1016219089Spjd __equal_range_unique(const _Key& __k); 1017209962Smm template <class _Key> 1018209962Smm pair<const_iterator, const_iterator> 1019209962Smm __equal_range_unique(const _Key& __k) const; 1020209962Smm 1021275782Sdelphij template <class _Key> 1022275782Sdelphij pair<iterator, iterator> 1023275782Sdelphij __equal_range_multi(const _Key& __k); 1024209962Smm template <class _Key> 1025209962Smm pair<const_iterator, const_iterator> 1026209962Smm __equal_range_multi(const _Key& __k) const; 1027209962Smm 1028209962Smm typedef __tree_node_destructor<__node_allocator> _Dp; 1029209962Smm typedef unique_ptr<__node, _Dp> __node_holder; 1030209962Smm 1031209962Smm __node_holder remove(const_iterator __p) _NOEXCEPT; 1032209962Smmprivate: 1033209962Smm typename __node_base::pointer& 1034248571Smm __find_leaf_low(typename __node_base::pointer& __parent, const value_type& __v); 1035240415Smm typename __node_base::pointer& 1036275782Sdelphij __find_leaf_high(typename __node_base::pointer& __parent, const value_type& __v); 1037209962Smm typename __node_base::pointer& 1038275782Sdelphij __find_leaf(const_iterator __hint, 1039209962Smm typename __node_base::pointer& __parent, const value_type& __v); 1040209962Smm template <class _Key> 1041248571Smm typename __node_base::pointer& 1042248571Smm __find_equal(typename __node_base::pointer& __parent, const _Key& __v); 1043248571Smm template <class _Key> 1044219089Spjd typename __node_base::pointer& 1045275782Sdelphij __find_equal(const_iterator __hint, typename __node_base::pointer& __parent, 1046219089Spjd const _Key& __v); 1047219089Spjd 1048248571Smm#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1049248571Smm template <class ..._Args> 1050219089Spjd __node_holder __construct_node(_Args&& ...__args); 1051248571Smm#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1052248571Smm __node_holder __construct_node(const value_type& __v); 1053248571Smm#endif 1054248571Smm 1055219089Spjd void destroy(__node_pointer __nd) _NOEXCEPT; 1056248571Smm 1057275782Sdelphij _LIBCPP_INLINE_VISIBILITY 1058219089Spjd void __copy_assign_alloc(const __tree& __t) 1059219089Spjd {__copy_assign_alloc(__t, integral_constant<bool, 1060219089Spjd __node_traits::propagate_on_container_copy_assignment::value>());} 1061248571Smm 1062248571Smm _LIBCPP_INLINE_VISIBILITY 1063219089Spjd void __copy_assign_alloc(const __tree& __t, true_type) 1064248571Smm {__node_alloc() = __t.__node_alloc();} 1065219089Spjd _LIBCPP_INLINE_VISIBILITY 1066219089Spjd void __copy_assign_alloc(const __tree& __t, false_type) {} 1067185029Spjd 1068248571Smm void __move_assign(__tree& __t, false_type); 1069185029Spjd void __move_assign(__tree& __t, true_type) 1070248571Smm _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1071168404Spjd is_nothrow_move_assignable<__node_allocator>::value); 1072248571Smm 1073219089Spjd _LIBCPP_INLINE_VISIBILITY 1074219089Spjd void __move_assign_alloc(__tree& __t) 1075248571Smm _NOEXCEPT_( 1076185029Spjd !__node_traits::propagate_on_container_move_assignment::value || 1077275782Sdelphij is_nothrow_move_assignable<__node_allocator>::value) 1078248571Smm {__move_assign_alloc(__t, integral_constant<bool, 1079219089Spjd __node_traits::propagate_on_container_move_assignment::value>());} 1080248571Smm 1081219089Spjd _LIBCPP_INLINE_VISIBILITY 1082248571Smm void __move_assign_alloc(__tree& __t, true_type) 1083248571Smm _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1084248571Smm {__node_alloc() = _VSTD::move(__t.__node_alloc());} 1085185029Spjd _LIBCPP_INLINE_VISIBILITY 1086248571Smm void __move_assign_alloc(__tree& __t, false_type) _NOEXCEPT {} 1087185029Spjd 1088248571Smm _LIBCPP_INLINE_VISIBILITY 1089248571Smm static void __swap_alloc(__node_allocator& __x, __node_allocator& __y) 1090248571Smm _NOEXCEPT_( 1091248571Smm !__node_traits::propagate_on_container_swap::value || 1092248571Smm __is_nothrow_swappable<__node_allocator>::value) 1093248571Smm {__swap_alloc(__x, __y, integral_constant<bool, 1094248571Smm __node_traits::propagate_on_container_swap::value>());} 1095168404Spjd _LIBCPP_INLINE_VISIBILITY 1096248571Smm static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type) 1097185029Spjd _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value) 1098168404Spjd { 1099185029Spjd using _VSTD::swap; 1100185029Spjd swap(__x, __y); 1101185029Spjd } 1102185029Spjd _LIBCPP_INLINE_VISIBILITY 1103185029Spjd static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type) 1104185029Spjd _NOEXCEPT 1105185029Spjd {} 1106185029Spjd 1107185029Spjd __node_pointer __detach(); 1108185029Spjd static __node_pointer __detach(__node_pointer); 1109185029Spjd 1110185029Spjd template <class, class, class, class> friend class _LIBCPP_TYPE_VIS map; 1111185029Spjd template <class, class, class, class> friend class _LIBCPP_TYPE_VIS multimap; 1112219089Spjd}; 1113275782Sdelphij 1114219089Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1115249195Smm__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) 1116185029Spjd _NOEXCEPT_( 1117185029Spjd is_nothrow_default_constructible<__node_allocator>::value && 1118248571Smm is_nothrow_copy_constructible<value_compare>::value) 1119185029Spjd : __pair3_(0, __comp) 1120185029Spjd{ 1121185029Spjd __begin_node() = __end_node(); 1122185029Spjd} 1123185029Spjd 1124185029Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1125168404Spjd__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) 1126168404Spjd : __pair1_(__node_allocator(__a)), 1127248571Smm __begin_node_(__node_pointer()), 1128248571Smm __pair3_(0) 1129248571Smm{ 1130248571Smm __begin_node() = __end_node(); 1131264835Sdelphij} 1132248571Smm 1133248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1134168404Spjd__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, 1135248571Smm const allocator_type& __a) 1136264835Sdelphij : __pair1_(__node_allocator(__a)), 1137168404Spjd __begin_node_(__node_pointer()), 1138248571Smm __pair3_(0, __comp) 1139168404Spjd{ 1140168404Spjd __begin_node() = __end_node(); 1141248571Smm} 1142248571Smm 1143248571Smm// Precondition: size() != 0 1144248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1145248571Smmtypename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1146168404Spjd__tree<_Tp, _Compare, _Allocator>::__detach() 1147168404Spjd{ 1148168404Spjd __node_pointer __cache = __begin_node(); 1149168404Spjd __begin_node() = __end_node(); 1150275782Sdelphij __end_node()->__left_->__parent_ = nullptr; 1151249195Smm __end_node()->__left_ = nullptr; 1152168404Spjd size() = 0; 1153168404Spjd // __cache->__left_ == nullptr 1154248571Smm if (__cache->__right_ != nullptr) 1155168404Spjd __cache = static_cast<__node_pointer>(__cache->__right_); 1156248571Smm // __cache->__left_ == nullptr 1157248571Smm // __cache->__right_ == nullptr 1158249195Smm return __cache; 1159248571Smm} 1160248571Smm 1161168404Spjd// Precondition: __cache != nullptr 1162253819Sdelphij// __cache->left_ == nullptr 1163253819Sdelphij// __cache->right_ == nullptr 1164253819Sdelphij// This is no longer a red-black tree 1165253819Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 1166253819Sdelphijtypename __tree<_Tp, _Compare, _Allocator>::__node_pointer 1167253819Sdelphij__tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache) 1168253819Sdelphij{ 1169253819Sdelphij if (__cache->__parent_ == nullptr) 1170253819Sdelphij return nullptr; 1171253819Sdelphij if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) 1172253819Sdelphij { 1173253819Sdelphij __cache->__parent_->__left_ = nullptr; 1174264835Sdelphij __cache = static_cast<__node_pointer>(__cache->__parent_); 1175264835Sdelphij if (__cache->__right_ == nullptr) 1176264835Sdelphij return __cache; 1177264835Sdelphij return static_cast<__node_pointer>(__tree_leaf(__cache->__right_)); 1178264835Sdelphij } 1179264835Sdelphij // __cache is right child 1180264835Sdelphij __cache->__parent_->__right_ = nullptr; 1181264835Sdelphij __cache = static_cast<__node_pointer>(__cache->__parent_); 1182264835Sdelphij if (__cache->__left_ == nullptr) 1183264835Sdelphij return __cache; 1184264835Sdelphij return static_cast<__node_pointer>(__tree_leaf(__cache->__left_)); 1185264835Sdelphij} 1186248571Smm 1187248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1188248571Smm__tree<_Tp, _Compare, _Allocator>& 1189168498Spjd__tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) 1190168404Spjd{ 1191168404Spjd if (this != &__t) 1192168404Spjd { 1193248571Smm value_comp() = __t.value_comp(); 1194248571Smm __copy_assign_alloc(__t); 1195248571Smm __assign_multi(__t.begin(), __t.end()); 1196248571Smm } 1197248571Smm return *this; 1198248571Smm} 1199248571Smm 1200248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1201264835Sdelphijtemplate <class _InputIterator> 1202264835Sdelphijvoid 1203264835Sdelphij__tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last) 1204264835Sdelphij{ 1205264835Sdelphij if (size() != 0) 1206264835Sdelphij { 1207264835Sdelphij __node_pointer __cache = __detach(); 1208264835Sdelphij#ifndef _LIBCPP_NO_EXCEPTIONS 1209264835Sdelphij try 1210264835Sdelphij { 1211264835Sdelphij#endif // _LIBCPP_NO_EXCEPTIONS 1212264835Sdelphij for (; __cache != nullptr && __first != __last; ++__first) 1213264835Sdelphij { 1214264835Sdelphij __cache->__value_ = *__first; 1215264835Sdelphij __node_pointer __next = __detach(__cache); 1216264835Sdelphij __node_insert_unique(__cache); 1217264835Sdelphij __cache = __next; 1218264835Sdelphij } 1219264835Sdelphij#ifndef _LIBCPP_NO_EXCEPTIONS 1220264835Sdelphij } 1221264835Sdelphij catch (...) 1222264835Sdelphij { 1223264835Sdelphij while (__cache->__parent_ != nullptr) 1224264835Sdelphij __cache = static_cast<__node_pointer>(__cache->__parent_); 1225264835Sdelphij destroy(__cache); 1226264835Sdelphij throw; 1227264835Sdelphij } 1228264835Sdelphij#endif // _LIBCPP_NO_EXCEPTIONS 1229264835Sdelphij if (__cache != nullptr) 1230264835Sdelphij { 1231264835Sdelphij while (__cache->__parent_ != nullptr) 1232264835Sdelphij __cache = static_cast<__node_pointer>(__cache->__parent_); 1233264835Sdelphij destroy(__cache); 1234264835Sdelphij } 1235264835Sdelphij } 1236264835Sdelphij for (; __first != __last; ++__first) 1237264835Sdelphij __insert_unique(*__first); 1238264835Sdelphij} 1239264835Sdelphij 1240264835Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 1241264835Sdelphijtemplate <class _InputIterator> 1242264835Sdelphijvoid 1243264835Sdelphij__tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) 1244264835Sdelphij{ 1245264835Sdelphij if (size() != 0) 1246264835Sdelphij { 1247264835Sdelphij __node_pointer __cache = __detach(); 1248264835Sdelphij#ifndef _LIBCPP_NO_EXCEPTIONS 1249264835Sdelphij try 1250264835Sdelphij { 1251264835Sdelphij#endif // _LIBCPP_NO_EXCEPTIONS 1252264835Sdelphij for (; __cache != nullptr && __first != __last; ++__first) 1253264835Sdelphij { 1254264835Sdelphij __cache->__value_ = *__first; 1255264835Sdelphij __node_pointer __next = __detach(__cache); 1256264835Sdelphij __node_insert_multi(__cache); 1257264835Sdelphij __cache = __next; 1258264835Sdelphij } 1259264835Sdelphij#ifndef _LIBCPP_NO_EXCEPTIONS 1260264835Sdelphij } 1261264835Sdelphij catch (...) 1262264835Sdelphij { 1263264835Sdelphij while (__cache->__parent_ != nullptr) 1264264835Sdelphij __cache = static_cast<__node_pointer>(__cache->__parent_); 1265264835Sdelphij destroy(__cache); 1266264835Sdelphij throw; 1267264835Sdelphij } 1268264835Sdelphij#endif // _LIBCPP_NO_EXCEPTIONS 1269264835Sdelphij if (__cache != nullptr) 1270264835Sdelphij { 1271264835Sdelphij while (__cache->__parent_ != nullptr) 1272264835Sdelphij __cache = static_cast<__node_pointer>(__cache->__parent_); 1273264835Sdelphij destroy(__cache); 1274264835Sdelphij } 1275264835Sdelphij } 1276264835Sdelphij for (; __first != __last; ++__first) 1277264835Sdelphij __insert_multi(*__first); 1278264835Sdelphij} 1279264835Sdelphij 1280264835Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 1281264835Sdelphij__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) 1282264835Sdelphij : __begin_node_(__node_pointer()), 1283264835Sdelphij __pair1_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())), 1284264835Sdelphij __pair3_(0, __t.value_comp()) 1285264835Sdelphij{ 1286264835Sdelphij __begin_node() = __end_node(); 1287264835Sdelphij} 1288264835Sdelphij 1289264835Sdelphij#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1290264835Sdelphij 1291264835Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 1292264835Sdelphij__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) 1293264835Sdelphij _NOEXCEPT_( 1294248571Smm is_nothrow_move_constructible<__node_allocator>::value && 1295248571Smm is_nothrow_move_constructible<value_compare>::value) 1296248571Smm : __begin_node_(_VSTD::move(__t.__begin_node_)), 1297248571Smm __pair1_(_VSTD::move(__t.__pair1_)), 1298248571Smm __pair3_(_VSTD::move(__t.__pair3_)) 1299248571Smm{ 1300248571Smm if (size() == 0) 1301248571Smm __begin_node() = __end_node(); 1302248571Smm else 1303249195Smm { 1304248571Smm __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1305248571Smm __t.__begin_node() = __t.__end_node(); 1306248571Smm __t.__end_node()->__left_ = nullptr; 1307249195Smm __t.size() = 0; 1308248571Smm } 1309248571Smm} 1310248571Smm 1311248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1312248571Smm__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a) 1313248571Smm : __pair1_(__node_allocator(__a)), 1314264835Sdelphij __pair3_(0, _VSTD::move(__t.value_comp())) 1315248571Smm{ 1316264835Sdelphij if (__a == __t.__alloc()) 1317248571Smm { 1318248571Smm if (__t.size() == 0) 1319248571Smm __begin_node() = __end_node(); 1320248571Smm else 1321248571Smm { 1322248571Smm __begin_node() = __t.__begin_node(); 1323248571Smm __end_node()->__left_ = __t.__end_node()->__left_; 1324248571Smm __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1325248571Smm size() = __t.size(); 1326248571Smm __t.__begin_node() = __t.__end_node(); 1327248571Smm __t.__end_node()->__left_ = nullptr; 1328264835Sdelphij __t.size() = 0; 1329248571Smm } 1330248571Smm } 1331248571Smm else 1332168404Spjd { 1333248571Smm __begin_node() = __end_node(); 1334248571Smm } 1335168404Spjd} 1336248571Smm 1337248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1338168404Spjdvoid 1339168404Spjd__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) 1340168404Spjd _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && 1341185029Spjd is_nothrow_move_assignable<__node_allocator>::value) 1342168404Spjd{ 1343248571Smm destroy(static_cast<__node_pointer>(__end_node()->__left_)); 1344168404Spjd __begin_node_ = __t.__begin_node_; 1345248571Smm __pair1_.first() = __t.__pair1_.first(); 1346168404Spjd __move_assign_alloc(__t); 1347185029Spjd __pair3_ = _VSTD::move(__t.__pair3_); 1348248571Smm if (size() == 0) 1349248571Smm __begin_node() = __end_node(); 1350248571Smm else 1351248571Smm { 1352248571Smm __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1353248571Smm __t.__begin_node() = __t.__end_node(); 1354248571Smm __t.__end_node()->__left_ = nullptr; 1355248571Smm __t.size() = 0; 1356264835Sdelphij } 1357248571Smm} 1358248571Smm 1359185029Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1360185029Spjdvoid 1361185029Spjd__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) 1362185029Spjd{ 1363185029Spjd if (__node_alloc() == __t.__node_alloc()) 1364185029Spjd __move_assign(__t, true_type()); 1365185029Spjd else 1366168404Spjd { 1367168404Spjd value_comp() = _VSTD::move(__t.value_comp()); 1368248571Smm const_iterator __e = end(); 1369168404Spjd if (size() != 0) 1370168404Spjd { 1371185029Spjd __node_pointer __cache = __detach(); 1372168404Spjd#ifndef _LIBCPP_NO_EXCEPTIONS 1373168404Spjd try 1374236823Spjd { 1375236823Spjd#endif // _LIBCPP_NO_EXCEPTIONS 1376236823Spjd while (__cache != nullptr && __t.size() != 0) 1377236823Spjd { 1378275782Sdelphij __cache->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_); 1379275782Sdelphij __node_pointer __next = __detach(__cache); 1380168404Spjd __node_insert_multi(__cache); 1381168404Spjd __cache = __next; 1382168404Spjd } 1383185029Spjd#ifndef _LIBCPP_NO_EXCEPTIONS 1384275782Sdelphij } 1385275782Sdelphij catch (...) 1386275782Sdelphij { 1387275782Sdelphij while (__cache->__parent_ != nullptr) 1388275782Sdelphij __cache = static_cast<__node_pointer>(__cache->__parent_); 1389275782Sdelphij destroy(__cache); 1390275782Sdelphij throw; 1391168404Spjd } 1392168404Spjd#endif // _LIBCPP_NO_EXCEPTIONS 1393286708Smav if (__cache != nullptr) 1394286708Smav { 1395286708Smav while (__cache->__parent_ != nullptr) 1396286708Smav __cache = static_cast<__node_pointer>(__cache->__parent_); 1397274337Sdelphij destroy(__cache); 1398275782Sdelphij } 1399275782Sdelphij } 1400168404Spjd while (__t.size() != 0) 1401185029Spjd __insert_multi(__e, _VSTD::move(__t.remove(__t.begin())->__value_)); 1402275782Sdelphij } 1403275782Sdelphij} 1404168404Spjd 1405275782Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 1406275782Sdelphij__tree<_Tp, _Compare, _Allocator>& 1407275782Sdelphij__tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) 1408168404Spjd _NOEXCEPT_( 1409275782Sdelphij __node_traits::propagate_on_container_move_assignment::value && 1410275782Sdelphij is_nothrow_move_assignable<value_compare>::value && 1411275782Sdelphij is_nothrow_move_assignable<__node_allocator>::value) 1412185029Spjd 1413248571Smm{ 1414209962Smm __move_assign(__t, integral_constant<bool, 1415248571Smm __node_traits::propagate_on_container_move_assignment::value>()); 1416185029Spjd return *this; 1417168404Spjd} 1418168404Spjd 1419168404Spjd#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1420185029Spjd 1421185029Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1422185029Spjd__tree<_Tp, _Compare, _Allocator>::~__tree() 1423185029Spjd{ 1424185029Spjd destroy(__root()); 1425185029Spjd} 1426219089Spjd 1427219089Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1428275782Sdelphijvoid 1429275782Sdelphij__tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT 1430185029Spjd{ 1431219089Spjd if (__nd != nullptr) 1432185029Spjd { 1433185029Spjd destroy(static_cast<__node_pointer>(__nd->__left_)); 1434168404Spjd destroy(static_cast<__node_pointer>(__nd->__right_)); 1435275782Sdelphij __node_allocator& __na = __node_alloc(); 1436275782Sdelphij __node_traits::destroy(__na, _VSTD::addressof(__nd->__value_)); 1437275782Sdelphij __node_traits::deallocate(__na, __nd, 1); 1438219089Spjd } 1439275782Sdelphij} 1440275782Sdelphij 1441219089Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1442275782Sdelphijvoid 1443219089Spjd__tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) 1444275782Sdelphij _NOEXCEPT_( 1445275782Sdelphij __is_nothrow_swappable<value_compare>::value && 1446275782Sdelphij (!__node_traits::propagate_on_container_swap::value || 1447275782Sdelphij __is_nothrow_swappable<__node_allocator>::value)) 1448185029Spjd{ 1449275782Sdelphij using _VSTD::swap; 1450168404Spjd swap(__begin_node_, __t.__begin_node_); 1451275782Sdelphij swap(__pair1_.first(), __t.__pair1_.first()); 1452248571Smm __swap_alloc(__node_alloc(), __t.__node_alloc()); 1453168404Spjd __pair3_.swap(__t.__pair3_); 1454168404Spjd if (size() == 0) 1455248571Smm __begin_node() = __end_node(); 1456248571Smm else 1457275782Sdelphij __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node()); 1458185029Spjd if (__t.size() == 0) 1459219089Spjd __t.__begin_node() = __t.__end_node(); 1460185029Spjd else 1461219089Spjd __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node()); 1462219089Spjd} 1463248571Smm 1464168404Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1465168404Spjdvoid 1466248571Smm__tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT 1467248571Smm{ 1468248571Smm destroy(__root()); 1469248571Smm size() = 0; 1470248571Smm __begin_node() = __end_node(); 1471248571Smm __end_node()->__left_ = nullptr; 1472248571Smm} 1473248571Smm 1474248571Smm// Find lower_bound place to insert 1475248571Smm// Set __parent to parent of null leaf 1476248571Smm// Return reference to null leaf 1477248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1478248571Smmtypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1479248571Smm__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer& __parent, 1480248571Smm const value_type& __v) 1481248571Smm{ 1482248571Smm __node_pointer __nd = __root(); 1483248571Smm if (__nd != nullptr) 1484248571Smm { 1485248571Smm while (true) 1486248571Smm { 1487248571Smm if (value_comp()(__nd->__value_, __v)) 1488248571Smm { 1489248571Smm if (__nd->__right_ != nullptr) 1490248571Smm __nd = static_cast<__node_pointer>(__nd->__right_); 1491248571Smm else 1492248571Smm { 1493248571Smm __parent = static_cast<__node_base_pointer>(__nd); 1494248571Smm return __parent->__right_; 1495248571Smm } 1496248571Smm } 1497248571Smm else 1498248571Smm { 1499248571Smm if (__nd->__left_ != nullptr) 1500248571Smm __nd = static_cast<__node_pointer>(__nd->__left_); 1501248571Smm else 1502248571Smm { 1503248571Smm __parent = static_cast<__node_base_pointer>(__nd); 1504248571Smm return __parent->__left_; 1505248571Smm } 1506248571Smm } 1507248571Smm } 1508248571Smm } 1509248571Smm __parent = static_cast<__node_base_pointer>(__end_node()); 1510248571Smm return __parent->__left_; 1511248571Smm} 1512248571Smm 1513248571Smm// Find upper_bound place to insert 1514248571Smm// Set __parent to parent of null leaf 1515248571Smm// Return reference to null leaf 1516248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1517248571Smmtypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1518248571Smm__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(typename __node_base::pointer& __parent, 1519248571Smm const value_type& __v) 1520248571Smm{ 1521248571Smm __node_pointer __nd = __root(); 1522248571Smm if (__nd != nullptr) 1523248571Smm { 1524248571Smm while (true) 1525248571Smm { 1526248571Smm if (value_comp()(__v, __nd->__value_)) 1527248571Smm { 1528248571Smm if (__nd->__left_ != nullptr) 1529248571Smm __nd = static_cast<__node_pointer>(__nd->__left_); 1530249195Smm else 1531248571Smm { 1532248571Smm __parent = static_cast<__node_base_pointer>(__nd); 1533248571Smm return __parent->__left_; 1534248571Smm } 1535248571Smm } 1536248571Smm else 1537248571Smm { 1538248571Smm if (__nd->__right_ != nullptr) 1539248571Smm __nd = static_cast<__node_pointer>(__nd->__right_); 1540248571Smm else 1541248571Smm { 1542248571Smm __parent = static_cast<__node_base_pointer>(__nd); 1543248571Smm return __parent->__right_; 1544248571Smm } 1545248571Smm } 1546264835Sdelphij } 1547248571Smm } 1548248571Smm __parent = static_cast<__node_base_pointer>(__end_node()); 1549248571Smm return __parent->__left_; 1550248571Smm} 1551268473Sdelphij 1552248571Smm// Find leaf place to insert closest to __hint 1553248571Smm// First check prior to __hint. 1554248571Smm// Next check after __hint. 1555248571Smm// Next do O(log N) search. 1556248571Smm// Set __parent to parent of null leaf 1557248571Smm// Return reference to null leaf 1558248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1559248571Smmtypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1560248571Smm__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, 1561248571Smm typename __node_base::pointer& __parent, 1562248571Smm const value_type& __v) 1563248571Smm{ 1564248571Smm if (__hint == end() || !value_comp()(*__hint, __v)) // check before 1565248571Smm { 1566248571Smm // __v <= *__hint 1567248571Smm const_iterator __prior = __hint; 1568248571Smm if (__prior == begin() || !value_comp()(__v, *--__prior)) 1569248571Smm { 1570248571Smm // *prev(__hint) <= __v <= *__hint 1571248571Smm if (__hint.__ptr_->__left_ == nullptr) 1572248571Smm { 1573248571Smm __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1574248571Smm return __parent->__left_; 1575248571Smm } 1576248571Smm else 1577248571Smm { 1578248571Smm __parent = static_cast<__node_base_pointer>(__prior.__ptr_); 1579248571Smm return __parent->__right_; 1580248571Smm } 1581248571Smm } 1582248571Smm // __v < *prev(__hint) 1583248571Smm return __find_leaf_high(__parent, __v); 1584248571Smm } 1585248571Smm // else __v > *__hint 1586248571Smm return __find_leaf_low(__parent, __v); 1587248571Smm} 1588248571Smm 1589248571Smm// Find place to insert if __v doesn't exist 1590248571Smm// Set __parent to parent of null leaf 1591248571Smm// Return reference to null leaf 1592248571Smm// If __v exists, set parent to node of __v and return reference to node of __v 1593248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1594248571Smmtemplate <class _Key> 1595248571Smmtypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1596264835Sdelphij__tree<_Tp, _Compare, _Allocator>::__find_equal(typename __node_base::pointer& __parent, 1597253819Sdelphij const _Key& __v) 1598264835Sdelphij{ 1599248571Smm __node_pointer __nd = __root(); 1600248571Smm if (__nd != nullptr) 1601248571Smm { 1602248571Smm while (true) 1603248571Smm { 1604248571Smm if (value_comp()(__v, __nd->__value_)) 1605248571Smm { 1606249195Smm if (__nd->__left_ != nullptr) 1607248571Smm __nd = static_cast<__node_pointer>(__nd->__left_); 1608248571Smm else 1609248571Smm { 1610248571Smm __parent = static_cast<__node_base_pointer>(__nd); 1611248571Smm return __parent->__left_; 1612248571Smm } 1613248571Smm } 1614248571Smm else if (value_comp()(__nd->__value_, __v)) 1615248571Smm { 1616248571Smm if (__nd->__right_ != nullptr) 1617248571Smm __nd = static_cast<__node_pointer>(__nd->__right_); 1618248571Smm else 1619248571Smm { 1620248571Smm __parent = static_cast<__node_base_pointer>(__nd); 1621248571Smm return __parent->__right_; 1622248571Smm } 1623248571Smm } 1624248571Smm else 1625248571Smm { 1626248571Smm __parent = static_cast<__node_base_pointer>(__nd); 1627248571Smm return __parent; 1628248571Smm } 1629248571Smm } 1630248571Smm } 1631248571Smm __parent = static_cast<__node_base_pointer>(__end_node()); 1632248571Smm return __parent->__left_; 1633248571Smm} 1634248571Smm 1635248571Smm// Find place to insert if __v doesn't exist 1636248571Smm// First check prior to __hint. 1637248571Smm// Next check after __hint. 1638248571Smm// Next do O(log N) search. 1639248571Smm// Set __parent to parent of null leaf 1640248571Smm// Return reference to null leaf 1641248571Smm// If __v exists, set parent to node of __v and return reference to node of __v 1642248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1643248571Smmtemplate <class _Key> 1644248571Smmtypename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer& 1645248571Smm__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, 1646248571Smm typename __node_base::pointer& __parent, 1647248571Smm const _Key& __v) 1648248571Smm{ 1649248571Smm if (__hint == end() || value_comp()(__v, *__hint)) // check before 1650248571Smm { 1651248571Smm // __v < *__hint 1652248571Smm const_iterator __prior = __hint; 1653248571Smm if (__prior == begin() || value_comp()(*--__prior, __v)) 1654248571Smm { 1655248571Smm // *prev(__hint) < __v < *__hint 1656248571Smm if (__hint.__ptr_->__left_ == nullptr) 1657248571Smm { 1658248571Smm __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1659248571Smm return __parent->__left_; 1660248571Smm } 1661248571Smm else 1662248571Smm { 1663248571Smm __parent = static_cast<__node_base_pointer>(__prior.__ptr_); 1664268473Sdelphij return __parent->__right_; 1665248571Smm } 1666248571Smm } 1667248571Smm // __v <= *prev(__hint) 1668248571Smm return __find_equal(__parent, __v); 1669248571Smm } 1670248571Smm else if (value_comp()(*__hint, __v)) // check after 1671248571Smm { 1672168404Spjd // *__hint < __v 1673168404Spjd const_iterator __next = _VSTD::next(__hint); 1674168404Spjd if (__next == end() || value_comp()(__v, *__next)) 1675168404Spjd { 1676219089Spjd // *__hint < __v < *_VSTD::next(__hint) 1677275782Sdelphij if (__hint.__ptr_->__right_ == nullptr) 1678168404Spjd { 1679185029Spjd __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1680185029Spjd return __parent->__right_; 1681185029Spjd } 1682185029Spjd else 1683185029Spjd { 1684275782Sdelphij __parent = static_cast<__node_base_pointer>(__next.__ptr_); 1685185029Spjd return __parent->__left_; 1686289362Smav } 1687289362Smav } 1688289362Smav // *next(__hint) <= __v 1689289362Smav return __find_equal(__parent, __v); 1690289362Smav } 1691289362Smav // else __v == *__hint 1692289362Smav __parent = static_cast<__node_base_pointer>(__hint.__ptr_); 1693289362Smav return __parent; 1694289362Smav} 1695289362Smav 1696289362Smavtemplate <class _Tp, class _Compare, class _Allocator> 1697289362Smavvoid 1698289362Smav__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent, 1699289362Smav __node_base_pointer& __child, 1700289362Smav __node_base_pointer __new_node) 1701219089Spjd{ 1702274337Sdelphij __new_node->__left_ = nullptr; 1703286708Smav __new_node->__right_ = nullptr; 1704286708Smav __new_node->__parent_ = __parent; 1705286708Smav __child = __new_node; 1706286708Smav if (__begin_node()->__left_ != nullptr) 1707286708Smav __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_); 1708286708Smav __tree_balance_after_insert(__end_node()->__left_, __child); 1709286708Smav ++size(); 1710274337Sdelphij} 1711168404Spjd 1712168404Spjd#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1713228103Smm#ifndef _LIBCPP_HAS_NO_VARIADICS 1714228103Smm 1715228103Smmtemplate <class _Tp, class _Compare, class _Allocator> 1716228103Smmtemplate <class ..._Args> 1717228103Smmtypename __tree<_Tp, _Compare, _Allocator>::__node_holder 1718228103Smm__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args) 1719228103Smm{ 1720248571Smm __node_allocator& __na = __node_alloc(); 1721248571Smm __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1722228103Smm __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 1723248571Smm __h.get_deleter().__value_constructed = true; 1724228103Smm return __h; 1725228103Smm} 1726248571Smm 1727228103Smmtemplate <class _Tp, class _Compare, class _Allocator> 1728228103Smmtemplate <class... _Args> 1729228103Smmpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1730275782Sdelphij__tree<_Tp, _Compare, _Allocator>::__emplace_unique(_Args&&... __args) 1731275782Sdelphij{ 1732228103Smm __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1733228103Smm __node_base_pointer __parent; 1734275782Sdelphij __node_base_pointer& __child = __find_equal(__parent, __h->__value_); 1735228103Smm __node_pointer __r = static_cast<__node_pointer>(__child); 1736275782Sdelphij bool __inserted = false; 1737275782Sdelphij if (__child == nullptr) 1738228103Smm { 1739228103Smm __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1740228103Smm __r = __h.release(); 1741228103Smm __inserted = true; 1742248571Smm } 1743248571Smm return pair<iterator, bool>(iterator(__r), __inserted); 1744228103Smm} 1745248571Smm 1746228103Smmtemplate <class _Tp, class _Compare, class _Allocator> 1747228103Smmtemplate <class... _Args> 1748228103Smmtypename __tree<_Tp, _Compare, _Allocator>::iterator 1749248571Smm__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique(const_iterator __p, _Args&&... __args) 1750248571Smm{ 1751228103Smm __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1752228103Smm __node_base_pointer __parent; 1753228103Smm __node_base_pointer& __child = __find_equal(__p, __parent, __h->__value_); 1754228103Smm __node_pointer __r = static_cast<__node_pointer>(__child); 1755228103Smm if (__child == nullptr) 1756289362Smav { 1757289362Smav __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1758289362Smav __r = __h.release(); 1759289362Smav } 1760289362Smav return iterator(__r); 1761289362Smav} 1762289362Smav 1763289362Smavtemplate <class _Tp, class _Compare, class _Allocator> 1764289362Smavtemplate <class... _Args> 1765289362Smavtypename __tree<_Tp, _Compare, _Allocator>::iterator 1766289362Smav__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) 1767289362Smav{ 1768289362Smav __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1769289362Smav __node_base_pointer __parent; 1770289362Smav __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); 1771289362Smav __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1772289362Smav return iterator(static_cast<__node_pointer>(__h.release())); 1773289362Smav} 1774289362Smav 1775289362Smavtemplate <class _Tp, class _Compare, class _Allocator> 1776289362Smavtemplate <class... _Args> 1777289362Smavtypename __tree<_Tp, _Compare, _Allocator>::iterator 1778289362Smav__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, 1779289362Smav _Args&&... __args) 1780289362Smav{ 1781289362Smav __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1782289362Smav __node_base_pointer __parent; 1783289362Smav __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); 1784289362Smav __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1785289362Smav return iterator(static_cast<__node_pointer>(__h.release())); 1786289362Smav} 1787289362Smav 1788289362Smav#endif // _LIBCPP_HAS_NO_VARIADICS 1789289362Smav 1790289362Smavtemplate <class _Tp, class _Compare, class _Allocator> 1791289362Smavtemplate <class _Vp> 1792289362Smavpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1793289362Smav__tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v) 1794289362Smav{ 1795289362Smav __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1796289362Smav pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1797289362Smav if (__r.second) 1798289362Smav __h.release(); 1799289362Smav return __r; 1800289362Smav} 1801289362Smav 1802289362Smavtemplate <class _Tp, class _Compare, class _Allocator> 1803289362Smavtemplate <class _Vp> 1804289362Smavtypename __tree<_Tp, _Compare, _Allocator>::iterator 1805289362Smav__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v) 1806289422Smav{ 1807289362Smav __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1808289362Smav iterator __r = __node_insert_unique(__p, __h.get()); 1809289362Smav if (__r.__ptr_ == __h.get()) 1810289362Smav __h.release(); 1811289362Smav return __r; 1812289362Smav} 1813289362Smav 1814289362Smavtemplate <class _Tp, class _Compare, class _Allocator> 1815289362Smavtemplate <class _Vp> 1816289362Smavtypename __tree<_Tp, _Compare, _Allocator>::iterator 1817289362Smav__tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v) 1818289362Smav{ 1819289362Smav __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1820289362Smav __node_base_pointer __parent; 1821289362Smav __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); 1822289362Smav __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1823289362Smav return iterator(__h.release()); 1824289362Smav} 1825289362Smav 1826168404Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1827168404Spjdtemplate <class _Vp> 1828168404Spjdtypename __tree<_Tp, _Compare, _Allocator>::iterator 1829248571Smm__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, _Vp&& __v) 1830223623Smm{ 1831185029Spjd __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v)); 1832248571Smm __node_base_pointer __parent; 1833168404Spjd __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); 1834275782Sdelphij __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1835275782Sdelphij return iterator(__h.release()); 1836275782Sdelphij} 1837248571Smm 1838248571Smm#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1839248571Smm 1840275782Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 1841248571Smmtypename __tree<_Tp, _Compare, _Allocator>::__node_holder 1842286575Smav__tree<_Tp, _Compare, _Allocator>::__construct_node(const value_type& __v) 1843248571Smm{ 1844248571Smm __node_allocator& __na = __node_alloc(); 1845275782Sdelphij __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1846248571Smm __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 1847248571Smm __h.get_deleter().__value_constructed = true; 1848268128Sdelphij return _VSTD::move(__h); 1849268128Sdelphij} 1850268128Sdelphij 1851268128Sdelphij#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1852268128Sdelphij 1853268128Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 1854248571Smmpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1855248571Smm__tree<_Tp, _Compare, _Allocator>::__insert_unique(const value_type& __v) 1856248571Smm{ 1857185029Spjd __node_base_pointer __parent; 1858185029Spjd __node_base_pointer& __child = __find_equal(__parent, __v); 1859185029Spjd __node_pointer __r = static_cast<__node_pointer>(__child); 1860185029Spjd bool __inserted = false; 1861168404Spjd if (__child == nullptr) 1862275782Sdelphij { 1863168404Spjd __node_holder __h = __construct_node(__v); 1864275782Sdelphij __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1865185029Spjd __r = __h.release(); 1866185029Spjd __inserted = true; 1867185029Spjd } 1868185029Spjd return pair<iterator, bool>(iterator(__r), __inserted); 1869185029Spjd} 1870275782Sdelphij 1871219089Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1872275782Sdelphijtypename __tree<_Tp, _Compare, _Allocator>::iterator 1873219089Spjd__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, const value_type& __v) 1874219089Spjd{ 1875219089Spjd __node_base_pointer __parent; 1876219089Spjd __node_base_pointer& __child = __find_equal(__p, __parent, __v); 1877219089Spjd __node_pointer __r = static_cast<__node_pointer>(__child); 1878219089Spjd if (__child == nullptr) 1879168404Spjd { 1880275782Sdelphij __node_holder __h = __construct_node(__v); 1881228103Smm __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1882228103Smm __r = __h.release(); 1883228103Smm } 1884228103Smm return iterator(__r); 1885228103Smm} 1886275782Sdelphij 1887228103Smmtemplate <class _Tp, class _Compare, class _Allocator> 1888228103Smmtypename __tree<_Tp, _Compare, _Allocator>::iterator 1889228103Smm__tree<_Tp, _Compare, _Allocator>::__insert_multi(const value_type& __v) 1890228103Smm{ 1891228103Smm __node_base_pointer __parent; 1892228103Smm __node_base_pointer& __child = __find_leaf_high(__parent, __v); 1893228103Smm __node_holder __h = __construct_node(__v); 1894228103Smm __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1895228103Smm return iterator(__h.release()); 1896228103Smm} 1897289362Smav 1898289362Smavtemplate <class _Tp, class _Compare, class _Allocator> 1899289362Smavtypename __tree<_Tp, _Compare, _Allocator>::iterator 1900289362Smav__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const value_type& __v) 1901289362Smav{ 1902289362Smav __node_base_pointer __parent; 1903289362Smav __node_base_pointer& __child = __find_leaf(__p, __parent, __v); 1904289362Smav __node_holder __h = __construct_node(__v); 1905289362Smav __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1906289362Smav return iterator(__h.release()); 1907289362Smav} 1908289362Smav 1909289362Smavtemplate <class _Tp, class _Compare, class _Allocator> 1910289362Smavpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> 1911289362Smav__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd) 1912289362Smav{ 1913289362Smav __node_base_pointer __parent; 1914289362Smav __node_base_pointer& __child = __find_equal(__parent, __nd->__value_); 1915289362Smav __node_pointer __r = static_cast<__node_pointer>(__child); 1916289362Smav bool __inserted = false; 1917289362Smav if (__child == nullptr) 1918289362Smav { 1919289362Smav __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1920168404Spjd __r = __nd; 1921168404Spjd __inserted = true; 1922168404Spjd } 1923168404Spjd return pair<iterator, bool>(iterator(__r), __inserted); 1924168404Spjd} 1925248571Smm 1926248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1927248571Smmtypename __tree<_Tp, _Compare, _Allocator>::iterator 1928275782Sdelphij__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p, 1929275782Sdelphij __node_pointer __nd) 1930275782Sdelphij{ 1931275782Sdelphij __node_base_pointer __parent; 1932248571Smm __node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_); 1933286575Smav __node_pointer __r = static_cast<__node_pointer>(__child); 1934168404Spjd if (__child == nullptr) 1935275782Sdelphij { 1936275782Sdelphij __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1937209962Smm __r = __nd; 1938209962Smm } 1939209962Smm return iterator(__r); 1940168404Spjd} 1941248571Smm 1942248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 1943168404Spjdtypename __tree<_Tp, _Compare, _Allocator>::iterator 1944248571Smm__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) 1945275782Sdelphij{ 1946275782Sdelphij __node_base_pointer __parent; 1947248571Smm __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_); 1948248571Smm __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1949248571Smm return iterator(__nd); 1950168404Spjd} 1951168404Spjd 1952168404Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1953168404Spjdtypename __tree<_Tp, _Compare, _Allocator>::iterator 1954168404Spjd__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, 1955168404Spjd __node_pointer __nd) 1956185029Spjd{ 1957168404Spjd __node_base_pointer __parent; 1958168404Spjd __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_); 1959168404Spjd __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); 1960168404Spjd return iterator(__nd); 1961168404Spjd} 1962168404Spjd 1963168404Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1964275782Sdelphijtypename __tree<_Tp, _Compare, _Allocator>::iterator 1965168404Spjd__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) 1966275782Sdelphij{ 1967275782Sdelphij __node_pointer __np = __p.__ptr_; 1968275782Sdelphij iterator __r(__np); 1969185029Spjd ++__r; 1970185029Spjd if (__begin_node() == __np) 1971185029Spjd __begin_node() = __r.__ptr_; 1972185029Spjd --size(); 1973185029Spjd __node_allocator& __na = __node_alloc(); 1974185029Spjd __node_traits::destroy(__na, const_cast<value_type*>(_VSTD::addressof(*__p))); 1975185029Spjd __tree_remove(__end_node()->__left_, 1976185029Spjd static_cast<__node_base_pointer>(__np)); 1977185029Spjd __node_traits::deallocate(__na, __np, 1); 1978185029Spjd return __r; 1979275782Sdelphij} 1980168404Spjd 1981168404Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1982168404Spjdtypename __tree<_Tp, _Compare, _Allocator>::iterator 1983185029Spjd__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l) 1984253820Sdelphij{ 1985185029Spjd while (__f != __l) 1986185029Spjd __f = erase(__f); 1987185029Spjd return iterator(__l.__ptr_); 1988248571Smm} 1989253820Sdelphij 1990185029Spjdtemplate <class _Tp, class _Compare, class _Allocator> 1991275782Sdelphijtemplate <class _Key> 1992275782Sdelphijtypename __tree<_Tp, _Compare, _Allocator>::size_type 1993253820Sdelphij__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) 1994219089Spjd{ 1995219089Spjd iterator __i = find(__k); 1996219089Spjd if (__i == end()) 1997219089Spjd return 0; 1998219089Spjd erase(__i); 1999219089Spjd return 1; 2000219089Spjd} 2001253820Sdelphij 2002219089Spjdtemplate <class _Tp, class _Compare, class _Allocator> 2003219089Spjdtemplate <class _Key> 2004253820Sdelphijtypename __tree<_Tp, _Compare, _Allocator>::size_type 2005219089Spjd__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) 2006219089Spjd{ 2007185029Spjd pair<iterator, iterator> __p = __equal_range_multi(__k); 2008185029Spjd size_type __r = 0; 2009185029Spjd for (; __p.first != __p.second; ++__r) 2010248571Smm __p.first = erase(__p.first); 2011248571Smm return __r; 2012248571Smm} 2013248571Smm 2014248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 2015248571Smmtemplate <class _Key> 2016248571Smmtypename __tree<_Tp, _Compare, _Allocator>::iterator 2017248571Smm__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) 2018168404Spjd{ 2019168404Spjd iterator __p = __lower_bound(__v, __root(), __end_node()); 2020248571Smm if (__p != end() && !value_comp()(__v, *__p)) 2021248571Smm return __p; 2022168404Spjd return end(); 2023248571Smm} 2024248571Smm 2025168404Spjdtemplate <class _Tp, class _Compare, class _Allocator> 2026168404Spjdtemplate <class _Key> 2027248571Smmtypename __tree<_Tp, _Compare, _Allocator>::const_iterator 2028248571Smm__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const 2029248571Smm{ 2030248571Smm const_iterator __p = __lower_bound(__v, __root(), __end_node()); 2031248571Smm if (__p != end() && !value_comp()(__v, *__p)) 2032168404Spjd return __p; 2033248571Smm return end(); 2034248571Smm} 2035248571Smm 2036249195Smmtemplate <class _Tp, class _Compare, class _Allocator> 2037248571Smmtemplate <class _Key> 2038248571Smmtypename __tree<_Tp, _Compare, _Allocator>::size_type 2039168404Spjd__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const 2040168676Spjd{ 2041248571Smm __node_const_pointer __result = __end_node(); 2042248571Smm __node_const_pointer __rt = __root(); 2043249195Smm while (__rt != nullptr) 2044168676Spjd { 2045248571Smm if (value_comp()(__k, __rt->__value_)) 2046168404Spjd { 2047168404Spjd __result = __rt; 2048248571Smm __rt = static_cast<__node_const_pointer>(__rt->__left_); 2049248571Smm } 2050168404Spjd else if (value_comp()(__rt->__value_, __k)) 2051248571Smm __rt = static_cast<__node_const_pointer>(__rt->__right_); 2052248571Smm else 2053168404Spjd return 1; 2054248571Smm } 2055168404Spjd return 0; 2056248571Smm} 2057248571Smm 2058248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 2059168404Spjdtemplate <class _Key> 2060248571Smmtypename __tree<_Tp, _Compare, _Allocator>::size_type 2061248571Smm__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const 2062248571Smm{ 2063248571Smm typedef pair<const_iterator, const_iterator> _Pp; 2064248571Smm __node_const_pointer __result = __end_node(); 2065248571Smm __node_const_pointer __rt = __root(); 2066248571Smm while (__rt != nullptr) 2067248571Smm { 2068248571Smm if (value_comp()(__k, __rt->__value_)) 2069248571Smm { 2070168404Spjd __result = __rt; 2071248571Smm __rt = static_cast<__node_const_pointer>(__rt->__left_); 2072248571Smm } 2073248571Smm else if (value_comp()(__rt->__value_, __k)) 2074248571Smm __rt = static_cast<__node_const_pointer>(__rt->__right_); 2075248571Smm else 2076248571Smm return _VSTD::distance( 2077248571Smm __lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt), 2078248571Smm __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result) 2079248571Smm ); 2080248571Smm } 2081248571Smm return 0; 2082248571Smm} 2083248571Smm 2084248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 2085248571Smmtemplate <class _Key> 2086248571Smmtypename __tree<_Tp, _Compare, _Allocator>::iterator 2087248571Smm__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2088248571Smm __node_pointer __root, 2089248571Smm __node_pointer __result) 2090248571Smm{ 2091248571Smm while (__root != nullptr) 2092248571Smm { 2093248571Smm if (!value_comp()(__root->__value_, __v)) 2094248571Smm { 2095248571Smm __result = __root; 2096248571Smm __root = static_cast<__node_pointer>(__root->__left_); 2097248571Smm } 2098248571Smm else 2099264835Sdelphij __root = static_cast<__node_pointer>(__root->__right_); 2100264835Sdelphij } 2101168404Spjd return iterator(__result); 2102248571Smm} 2103168404Spjd 2104275782Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 2105275782Sdelphijtemplate <class _Key> 2106248571Smmtypename __tree<_Tp, _Compare, _Allocator>::const_iterator 2107248571Smm__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, 2108248571Smm __node_const_pointer __root, 2109219320Spjd __node_const_pointer __result) const 2110248571Smm{ 2111248571Smm while (__root != nullptr) 2112248571Smm { 2113248571Smm if (!value_comp()(__root->__value_, __v)) 2114248571Smm { 2115248571Smm __result = __root; 2116248571Smm __root = static_cast<__node_const_pointer>(__root->__left_); 2117219317Spjd } 2118248571Smm else 2119248571Smm __root = static_cast<__node_const_pointer>(__root->__right_); 2120219320Spjd } 2121248571Smm return const_iterator(__result); 2122248571Smm} 2123168404Spjd 2124248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 2125168404Spjdtemplate <class _Key> 2126168404Spjdtypename __tree<_Tp, _Compare, _Allocator>::iterator 2127248571Smm__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2128248571Smm __node_pointer __root, 2129168676Spjd __node_pointer __result) 2130248571Smm{ 2131248571Smm while (__root != nullptr) 2132248571Smm { 2133168676Spjd if (value_comp()(__v, __root->__value_)) 2134248571Smm { 2135248571Smm __result = __root; 2136248571Smm __root = static_cast<__node_pointer>(__root->__left_); 2137248571Smm } 2138248571Smm else 2139248571Smm __root = static_cast<__node_pointer>(__root->__right_); 2140248571Smm } 2141248571Smm return iterator(__result); 2142168676Spjd} 2143248571Smm 2144248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 2145168676Spjdtemplate <class _Key> 2146248571Smmtypename __tree<_Tp, _Compare, _Allocator>::const_iterator 2147248571Smm__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, 2148248571Smm __node_const_pointer __root, 2149248571Smm __node_const_pointer __result) const 2150248571Smm{ 2151168676Spjd while (__root != nullptr) 2152248571Smm { 2153248571Smm if (value_comp()(__v, __root->__value_)) 2154248571Smm { 2155248571Smm __result = __root; 2156168676Spjd __root = static_cast<__node_const_pointer>(__root->__left_); 2157248571Smm } 2158268473Sdelphij else 2159268473Sdelphij __root = static_cast<__node_const_pointer>(__root->__right_); 2160168676Spjd } 2161168676Spjd return const_iterator(__result); 2162253816Sdelphij} 2163253816Sdelphij 2164253816Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 2165253816Sdelphijtemplate <class _Key> 2166253816Sdelphijpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2167253816Sdelphij typename __tree<_Tp, _Compare, _Allocator>::iterator> 2168253816Sdelphij__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) 2169168676Spjd{ 2170253816Sdelphij typedef pair<iterator, iterator> _Pp; 2171253816Sdelphij __node_pointer __result = __end_node(); 2172253816Sdelphij __node_pointer __rt = __root(); 2173253816Sdelphij while (__rt != nullptr) 2174253816Sdelphij { 2175253816Sdelphij if (value_comp()(__k, __rt->__value_)) 2176253816Sdelphij { 2177253816Sdelphij __result = __rt; 2178253816Sdelphij __rt = static_cast<__node_pointer>(__rt->__left_); 2179253816Sdelphij } 2180253816Sdelphij else if (value_comp()(__rt->__value_, __k)) 2181253816Sdelphij __rt = static_cast<__node_pointer>(__rt->__right_); 2182253816Sdelphij else 2183253816Sdelphij return _Pp(iterator(__rt), 2184253816Sdelphij iterator( 2185253816Sdelphij __rt->__right_ != nullptr ? 2186253816Sdelphij static_cast<__node_pointer>(__tree_min(__rt->__right_)) 2187253816Sdelphij : __result)); 2188253816Sdelphij } 2189253816Sdelphij return _Pp(iterator(__result), iterator(__result)); 2190253816Sdelphij} 2191253816Sdelphij 2192253816Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 2193253816Sdelphijtemplate <class _Key> 2194253816Sdelphijpair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2195253816Sdelphij typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2196254587Sdelphij__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const 2197253816Sdelphij{ 2198253816Sdelphij typedef pair<const_iterator, const_iterator> _Pp; 2199253816Sdelphij __node_const_pointer __result = __end_node(); 2200248571Smm __node_const_pointer __rt = __root(); 2201168676Spjd while (__rt != nullptr) 2202253816Sdelphij { 2203248571Smm if (value_comp()(__k, __rt->__value_)) 2204248571Smm { 2205248571Smm __result = __rt; 2206248571Smm __rt = static_cast<__node_const_pointer>(__rt->__left_); 2207168676Spjd } 2208253816Sdelphij else if (value_comp()(__rt->__value_, __k)) 2209248571Smm __rt = static_cast<__node_const_pointer>(__rt->__right_); 2210248571Smm else 2211168676Spjd return _Pp(const_iterator(__rt), 2212248571Smm const_iterator( 2213286575Smav __rt->__right_ != nullptr ? 2214248571Smm static_cast<__node_const_pointer>(__tree_min(__rt->__right_)) 2215249195Smm : __result)); 2216168676Spjd } 2217168676Spjd return _Pp(const_iterator(__result), const_iterator(__result)); 2218248571Smm} 2219275782Sdelphij 2220248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 2221249195Smmtemplate <class _Key> 2222248571Smmpair<typename __tree<_Tp, _Compare, _Allocator>::iterator, 2223168676Spjd typename __tree<_Tp, _Compare, _Allocator>::iterator> 2224260183Sdelphij__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) 2225260183Sdelphij{ 2226260183Sdelphij typedef pair<iterator, iterator> _Pp; 2227260183Sdelphij __node_pointer __result = __end_node(); 2228260183Sdelphij __node_pointer __rt = __root(); 2229260183Sdelphij while (__rt != nullptr) 2230260183Sdelphij { 2231260183Sdelphij if (value_comp()(__k, __rt->__value_)) 2232260183Sdelphij { 2233260183Sdelphij __result = __rt; 2234260183Sdelphij __rt = static_cast<__node_pointer>(__rt->__left_); 2235260183Sdelphij } 2236260183Sdelphij else if (value_comp()(__rt->__value_, __k)) 2237260183Sdelphij __rt = static_cast<__node_pointer>(__rt->__right_); 2238275782Sdelphij else 2239260183Sdelphij return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt), 2240260183Sdelphij __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); 2241260183Sdelphij } 2242260183Sdelphij return _Pp(iterator(__result), iterator(__result)); 2243260183Sdelphij} 2244260183Sdelphij 2245260183Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 2246253816Sdelphijtemplate <class _Key> 2247253816Sdelphijpair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, 2248248571Smm typename __tree<_Tp, _Compare, _Allocator>::const_iterator> 2249253816Sdelphij__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const 2250248571Smm{ 2251168676Spjd typedef pair<const_iterator, const_iterator> _Pp; 2252248571Smm __node_const_pointer __result = __end_node(); 2253248571Smm __node_const_pointer __rt = __root(); 2254248571Smm while (__rt != nullptr) 2255248571Smm { 2256248571Smm if (value_comp()(__k, __rt->__value_)) 2257275782Sdelphij { 2258248571Smm __result = __rt; 2259249195Smm __rt = static_cast<__node_const_pointer>(__rt->__left_); 2260168676Spjd } 2261168676Spjd else if (value_comp()(__rt->__value_, __k)) 2262248571Smm __rt = static_cast<__node_const_pointer>(__rt->__right_); 2263248571Smm else 2264248571Smm return _Pp(__lower_bound(__k, static_cast<__node_const_pointer>(__rt->__left_), __rt), 2265248571Smm __upper_bound(__k, static_cast<__node_const_pointer>(__rt->__right_), __result)); 2266248571Smm } 2267248571Smm return _Pp(const_iterator(__result), const_iterator(__result)); 2268248571Smm} 2269248571Smm 2270275782Sdelphijtemplate <class _Tp, class _Compare, class _Allocator> 2271168676Spjdtypename __tree<_Tp, _Compare, _Allocator>::__node_holder 2272248571Smm__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT 2273248571Smm{ 2274248571Smm __node_pointer __np = __p.__ptr_; 2275248571Smm if (__begin_node() == __np) 2276249195Smm { 2277248571Smm if (__np->__right_ != nullptr) 2278168676Spjd __begin_node() = static_cast<__node_pointer>(__np->__right_); 2279248571Smm else 2280185029Spjd __begin_node() = static_cast<__node_pointer>(__np->__parent_); 2281185029Spjd } 2282185029Spjd --size(); 2283248571Smm __tree_remove(__end_node()->__left_, 2284248571Smm static_cast<__node_base_pointer>(__np)); 2285168404Spjd return __node_holder(__np, _Dp(__node_alloc())); 2286253816Sdelphij} 2287248571Smm 2288248571Smmtemplate <class _Tp, class _Compare, class _Allocator> 2289248571Smminline _LIBCPP_INLINE_VISIBILITY 2290254587Sdelphijvoid 2291168404Spjdswap(__tree<_Tp, _Compare, _Allocator>& __x, 2292253816Sdelphij __tree<_Tp, _Compare, _Allocator>& __y) 2293219089Spjd _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2294254587Sdelphij{ 2295254587Sdelphij __x.swap(__y); 2296254587Sdelphij} 2297248571Smm 2298248571Smm_LIBCPP_END_NAMESPACE_STD 2299185029Spjd 2300248571Smm#endif // _LIBCPP___TREE 2301185029Spjd