1*e4b17023SJohn Marino // RB tree utilities implementation -*- C++ -*- 2*e4b17023SJohn Marino 3*e4b17023SJohn Marino // Copyright (C) 2003, 2005, 2009, 2012 Free Software Foundation, Inc. 4*e4b17023SJohn Marino // 5*e4b17023SJohn Marino // This file is part of the GNU ISO C++ Library. This library is free 6*e4b17023SJohn Marino // software; you can redistribute it and/or modify it under the 7*e4b17023SJohn Marino // terms of the GNU General Public License as published by the 8*e4b17023SJohn Marino // Free Software Foundation; either version 3, or (at your option) 9*e4b17023SJohn Marino // any later version. 10*e4b17023SJohn Marino 11*e4b17023SJohn Marino // This library is distributed in the hope that it will be useful, 12*e4b17023SJohn Marino // but WITHOUT ANY WARRANTY; without even the implied warranty of 13*e4b17023SJohn Marino // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14*e4b17023SJohn Marino // GNU General Public License for more details. 15*e4b17023SJohn Marino 16*e4b17023SJohn Marino // Under Section 7 of GPL version 3, you are granted additional 17*e4b17023SJohn Marino // permissions described in the GCC Runtime Library Exception, version 18*e4b17023SJohn Marino // 3.1, as published by the Free Software Foundation. 19*e4b17023SJohn Marino 20*e4b17023SJohn Marino // You should have received a copy of the GNU General Public License and 21*e4b17023SJohn Marino // a copy of the GCC Runtime Library Exception along with this program; 22*e4b17023SJohn Marino // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23*e4b17023SJohn Marino // <http://www.gnu.org/licenses/>. 24*e4b17023SJohn Marino 25*e4b17023SJohn Marino /* 26*e4b17023SJohn Marino * 27*e4b17023SJohn Marino * Copyright (c) 1996,1997 28*e4b17023SJohn Marino * Silicon Graphics Computer Systems, Inc. 29*e4b17023SJohn Marino * 30*e4b17023SJohn Marino * Permission to use, copy, modify, distribute and sell this software 31*e4b17023SJohn Marino * and its documentation for any purpose is hereby granted without fee, 32*e4b17023SJohn Marino * provided that the above copyright notice appear in all copies and 33*e4b17023SJohn Marino * that both that copyright notice and this permission notice appear 34*e4b17023SJohn Marino * in supporting documentation. Silicon Graphics makes no 35*e4b17023SJohn Marino * representations about the suitability of this software for any 36*e4b17023SJohn Marino * purpose. It is provided "as is" without express or implied warranty. 37*e4b17023SJohn Marino * 38*e4b17023SJohn Marino * 39*e4b17023SJohn Marino * Copyright (c) 1994 40*e4b17023SJohn Marino * Hewlett-Packard Company 41*e4b17023SJohn Marino * 42*e4b17023SJohn Marino * Permission to use, copy, modify, distribute and sell this software 43*e4b17023SJohn Marino * and its documentation for any purpose is hereby granted without fee, 44*e4b17023SJohn Marino * provided that the above copyright notice appear in all copies and 45*e4b17023SJohn Marino * that both that copyright notice and this permission notice appear 46*e4b17023SJohn Marino * in supporting documentation. Hewlett-Packard Company makes no 47*e4b17023SJohn Marino * representations about the suitability of this software for any 48*e4b17023SJohn Marino * purpose. It is provided "as is" without express or implied warranty. 49*e4b17023SJohn Marino * 50*e4b17023SJohn Marino * 51*e4b17023SJohn Marino */ 52*e4b17023SJohn Marino 53*e4b17023SJohn Marino #include <bits/stl_tree.h> 54*e4b17023SJohn Marino 55*e4b17023SJohn Marino namespace std _GLIBCXX_VISIBILITY(default) 56*e4b17023SJohn Marino { 57*e4b17023SJohn Marino _GLIBCXX_BEGIN_NAMESPACE_VERSION 58*e4b17023SJohn Marino 59*e4b17023SJohn Marino static _Rb_tree_node_base* local_Rb_tree_increment(_Rb_tree_node_base * __x)60*e4b17023SJohn Marino local_Rb_tree_increment(_Rb_tree_node_base* __x) throw () 61*e4b17023SJohn Marino { 62*e4b17023SJohn Marino if (__x->_M_right != 0) 63*e4b17023SJohn Marino { 64*e4b17023SJohn Marino __x = __x->_M_right; 65*e4b17023SJohn Marino while (__x->_M_left != 0) 66*e4b17023SJohn Marino __x = __x->_M_left; 67*e4b17023SJohn Marino } 68*e4b17023SJohn Marino else 69*e4b17023SJohn Marino { 70*e4b17023SJohn Marino _Rb_tree_node_base* __y = __x->_M_parent; 71*e4b17023SJohn Marino while (__x == __y->_M_right) 72*e4b17023SJohn Marino { 73*e4b17023SJohn Marino __x = __y; 74*e4b17023SJohn Marino __y = __y->_M_parent; 75*e4b17023SJohn Marino } 76*e4b17023SJohn Marino if (__x->_M_right != __y) 77*e4b17023SJohn Marino __x = __y; 78*e4b17023SJohn Marino } 79*e4b17023SJohn Marino return __x; 80*e4b17023SJohn Marino } 81*e4b17023SJohn Marino 82*e4b17023SJohn Marino _Rb_tree_node_base* _Rb_tree_increment(_Rb_tree_node_base * __x)83*e4b17023SJohn Marino _Rb_tree_increment(_Rb_tree_node_base* __x) throw () 84*e4b17023SJohn Marino { 85*e4b17023SJohn Marino return local_Rb_tree_increment(__x); 86*e4b17023SJohn Marino } 87*e4b17023SJohn Marino 88*e4b17023SJohn Marino const _Rb_tree_node_base* _Rb_tree_increment(const _Rb_tree_node_base * __x)89*e4b17023SJohn Marino _Rb_tree_increment(const _Rb_tree_node_base* __x) throw () 90*e4b17023SJohn Marino { 91*e4b17023SJohn Marino return local_Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x)); 92*e4b17023SJohn Marino } 93*e4b17023SJohn Marino 94*e4b17023SJohn Marino static _Rb_tree_node_base* local_Rb_tree_decrement(_Rb_tree_node_base * __x)95*e4b17023SJohn Marino local_Rb_tree_decrement(_Rb_tree_node_base* __x) throw () 96*e4b17023SJohn Marino { 97*e4b17023SJohn Marino if (__x->_M_color == _S_red 98*e4b17023SJohn Marino && __x->_M_parent->_M_parent == __x) 99*e4b17023SJohn Marino __x = __x->_M_right; 100*e4b17023SJohn Marino else if (__x->_M_left != 0) 101*e4b17023SJohn Marino { 102*e4b17023SJohn Marino _Rb_tree_node_base* __y = __x->_M_left; 103*e4b17023SJohn Marino while (__y->_M_right != 0) 104*e4b17023SJohn Marino __y = __y->_M_right; 105*e4b17023SJohn Marino __x = __y; 106*e4b17023SJohn Marino } 107*e4b17023SJohn Marino else 108*e4b17023SJohn Marino { 109*e4b17023SJohn Marino _Rb_tree_node_base* __y = __x->_M_parent; 110*e4b17023SJohn Marino while (__x == __y->_M_left) 111*e4b17023SJohn Marino { 112*e4b17023SJohn Marino __x = __y; 113*e4b17023SJohn Marino __y = __y->_M_parent; 114*e4b17023SJohn Marino } 115*e4b17023SJohn Marino __x = __y; 116*e4b17023SJohn Marino } 117*e4b17023SJohn Marino return __x; 118*e4b17023SJohn Marino } 119*e4b17023SJohn Marino 120*e4b17023SJohn Marino _Rb_tree_node_base* _Rb_tree_decrement(_Rb_tree_node_base * __x)121*e4b17023SJohn Marino _Rb_tree_decrement(_Rb_tree_node_base* __x) throw () 122*e4b17023SJohn Marino { 123*e4b17023SJohn Marino return local_Rb_tree_decrement(__x); 124*e4b17023SJohn Marino } 125*e4b17023SJohn Marino 126*e4b17023SJohn Marino const _Rb_tree_node_base* _Rb_tree_decrement(const _Rb_tree_node_base * __x)127*e4b17023SJohn Marino _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw () 128*e4b17023SJohn Marino { 129*e4b17023SJohn Marino return local_Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x)); 130*e4b17023SJohn Marino } 131*e4b17023SJohn Marino 132*e4b17023SJohn Marino static void local_Rb_tree_rotate_left(_Rb_tree_node_base * const __x,_Rb_tree_node_base * & __root)133*e4b17023SJohn Marino local_Rb_tree_rotate_left(_Rb_tree_node_base* const __x, 134*e4b17023SJohn Marino _Rb_tree_node_base*& __root) 135*e4b17023SJohn Marino { 136*e4b17023SJohn Marino _Rb_tree_node_base* const __y = __x->_M_right; 137*e4b17023SJohn Marino 138*e4b17023SJohn Marino __x->_M_right = __y->_M_left; 139*e4b17023SJohn Marino if (__y->_M_left !=0) 140*e4b17023SJohn Marino __y->_M_left->_M_parent = __x; 141*e4b17023SJohn Marino __y->_M_parent = __x->_M_parent; 142*e4b17023SJohn Marino 143*e4b17023SJohn Marino if (__x == __root) 144*e4b17023SJohn Marino __root = __y; 145*e4b17023SJohn Marino else if (__x == __x->_M_parent->_M_left) 146*e4b17023SJohn Marino __x->_M_parent->_M_left = __y; 147*e4b17023SJohn Marino else 148*e4b17023SJohn Marino __x->_M_parent->_M_right = __y; 149*e4b17023SJohn Marino __y->_M_left = __x; 150*e4b17023SJohn Marino __x->_M_parent = __y; 151*e4b17023SJohn Marino } 152*e4b17023SJohn Marino 153*e4b17023SJohn Marino /* Static keyword was missing on _Rb_tree_rotate_left. 154*e4b17023SJohn Marino Export the symbol for backward compatibility until 155*e4b17023SJohn Marino next ABI change. */ 156*e4b17023SJohn Marino void _Rb_tree_rotate_left(_Rb_tree_node_base * const __x,_Rb_tree_node_base * & __root)157*e4b17023SJohn Marino _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, 158*e4b17023SJohn Marino _Rb_tree_node_base*& __root) 159*e4b17023SJohn Marino { 160*e4b17023SJohn Marino local_Rb_tree_rotate_left (__x, __root); 161*e4b17023SJohn Marino } 162*e4b17023SJohn Marino 163*e4b17023SJohn Marino static void local_Rb_tree_rotate_right(_Rb_tree_node_base * const __x,_Rb_tree_node_base * & __root)164*e4b17023SJohn Marino local_Rb_tree_rotate_right(_Rb_tree_node_base* const __x, 165*e4b17023SJohn Marino _Rb_tree_node_base*& __root) 166*e4b17023SJohn Marino { 167*e4b17023SJohn Marino _Rb_tree_node_base* const __y = __x->_M_left; 168*e4b17023SJohn Marino 169*e4b17023SJohn Marino __x->_M_left = __y->_M_right; 170*e4b17023SJohn Marino if (__y->_M_right != 0) 171*e4b17023SJohn Marino __y->_M_right->_M_parent = __x; 172*e4b17023SJohn Marino __y->_M_parent = __x->_M_parent; 173*e4b17023SJohn Marino 174*e4b17023SJohn Marino if (__x == __root) 175*e4b17023SJohn Marino __root = __y; 176*e4b17023SJohn Marino else if (__x == __x->_M_parent->_M_right) 177*e4b17023SJohn Marino __x->_M_parent->_M_right = __y; 178*e4b17023SJohn Marino else 179*e4b17023SJohn Marino __x->_M_parent->_M_left = __y; 180*e4b17023SJohn Marino __y->_M_right = __x; 181*e4b17023SJohn Marino __x->_M_parent = __y; 182*e4b17023SJohn Marino } 183*e4b17023SJohn Marino 184*e4b17023SJohn Marino /* Static keyword was missing on _Rb_tree_rotate_right 185*e4b17023SJohn Marino Export the symbol for backward compatibility until 186*e4b17023SJohn Marino next ABI change. */ 187*e4b17023SJohn Marino void _Rb_tree_rotate_right(_Rb_tree_node_base * const __x,_Rb_tree_node_base * & __root)188*e4b17023SJohn Marino _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, 189*e4b17023SJohn Marino _Rb_tree_node_base*& __root) 190*e4b17023SJohn Marino { 191*e4b17023SJohn Marino local_Rb_tree_rotate_right (__x, __root); 192*e4b17023SJohn Marino } 193*e4b17023SJohn Marino 194*e4b17023SJohn Marino void _Rb_tree_insert_and_rebalance(const bool __insert_left,_Rb_tree_node_base * __x,_Rb_tree_node_base * __p,_Rb_tree_node_base & __header)195*e4b17023SJohn Marino _Rb_tree_insert_and_rebalance(const bool __insert_left, 196*e4b17023SJohn Marino _Rb_tree_node_base* __x, 197*e4b17023SJohn Marino _Rb_tree_node_base* __p, 198*e4b17023SJohn Marino _Rb_tree_node_base& __header) throw () 199*e4b17023SJohn Marino { 200*e4b17023SJohn Marino _Rb_tree_node_base *& __root = __header._M_parent; 201*e4b17023SJohn Marino 202*e4b17023SJohn Marino // Initialize fields in new node to insert. 203*e4b17023SJohn Marino __x->_M_parent = __p; 204*e4b17023SJohn Marino __x->_M_left = 0; 205*e4b17023SJohn Marino __x->_M_right = 0; 206*e4b17023SJohn Marino __x->_M_color = _S_red; 207*e4b17023SJohn Marino 208*e4b17023SJohn Marino // Insert. 209*e4b17023SJohn Marino // Make new node child of parent and maintain root, leftmost and 210*e4b17023SJohn Marino // rightmost nodes. 211*e4b17023SJohn Marino // N.B. First node is always inserted left. 212*e4b17023SJohn Marino if (__insert_left) 213*e4b17023SJohn Marino { 214*e4b17023SJohn Marino __p->_M_left = __x; // also makes leftmost = __x when __p == &__header 215*e4b17023SJohn Marino 216*e4b17023SJohn Marino if (__p == &__header) 217*e4b17023SJohn Marino { 218*e4b17023SJohn Marino __header._M_parent = __x; 219*e4b17023SJohn Marino __header._M_right = __x; 220*e4b17023SJohn Marino } 221*e4b17023SJohn Marino else if (__p == __header._M_left) 222*e4b17023SJohn Marino __header._M_left = __x; // maintain leftmost pointing to min node 223*e4b17023SJohn Marino } 224*e4b17023SJohn Marino else 225*e4b17023SJohn Marino { 226*e4b17023SJohn Marino __p->_M_right = __x; 227*e4b17023SJohn Marino 228*e4b17023SJohn Marino if (__p == __header._M_right) 229*e4b17023SJohn Marino __header._M_right = __x; // maintain rightmost pointing to max node 230*e4b17023SJohn Marino } 231*e4b17023SJohn Marino // Rebalance. 232*e4b17023SJohn Marino while (__x != __root 233*e4b17023SJohn Marino && __x->_M_parent->_M_color == _S_red) 234*e4b17023SJohn Marino { 235*e4b17023SJohn Marino _Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent; 236*e4b17023SJohn Marino 237*e4b17023SJohn Marino if (__x->_M_parent == __xpp->_M_left) 238*e4b17023SJohn Marino { 239*e4b17023SJohn Marino _Rb_tree_node_base* const __y = __xpp->_M_right; 240*e4b17023SJohn Marino if (__y && __y->_M_color == _S_red) 241*e4b17023SJohn Marino { 242*e4b17023SJohn Marino __x->_M_parent->_M_color = _S_black; 243*e4b17023SJohn Marino __y->_M_color = _S_black; 244*e4b17023SJohn Marino __xpp->_M_color = _S_red; 245*e4b17023SJohn Marino __x = __xpp; 246*e4b17023SJohn Marino } 247*e4b17023SJohn Marino else 248*e4b17023SJohn Marino { 249*e4b17023SJohn Marino if (__x == __x->_M_parent->_M_right) 250*e4b17023SJohn Marino { 251*e4b17023SJohn Marino __x = __x->_M_parent; 252*e4b17023SJohn Marino local_Rb_tree_rotate_left(__x, __root); 253*e4b17023SJohn Marino } 254*e4b17023SJohn Marino __x->_M_parent->_M_color = _S_black; 255*e4b17023SJohn Marino __xpp->_M_color = _S_red; 256*e4b17023SJohn Marino local_Rb_tree_rotate_right(__xpp, __root); 257*e4b17023SJohn Marino } 258*e4b17023SJohn Marino } 259*e4b17023SJohn Marino else 260*e4b17023SJohn Marino { 261*e4b17023SJohn Marino _Rb_tree_node_base* const __y = __xpp->_M_left; 262*e4b17023SJohn Marino if (__y && __y->_M_color == _S_red) 263*e4b17023SJohn Marino { 264*e4b17023SJohn Marino __x->_M_parent->_M_color = _S_black; 265*e4b17023SJohn Marino __y->_M_color = _S_black; 266*e4b17023SJohn Marino __xpp->_M_color = _S_red; 267*e4b17023SJohn Marino __x = __xpp; 268*e4b17023SJohn Marino } 269*e4b17023SJohn Marino else 270*e4b17023SJohn Marino { 271*e4b17023SJohn Marino if (__x == __x->_M_parent->_M_left) 272*e4b17023SJohn Marino { 273*e4b17023SJohn Marino __x = __x->_M_parent; 274*e4b17023SJohn Marino local_Rb_tree_rotate_right(__x, __root); 275*e4b17023SJohn Marino } 276*e4b17023SJohn Marino __x->_M_parent->_M_color = _S_black; 277*e4b17023SJohn Marino __xpp->_M_color = _S_red; 278*e4b17023SJohn Marino local_Rb_tree_rotate_left(__xpp, __root); 279*e4b17023SJohn Marino } 280*e4b17023SJohn Marino } 281*e4b17023SJohn Marino } 282*e4b17023SJohn Marino __root->_M_color = _S_black; 283*e4b17023SJohn Marino } 284*e4b17023SJohn Marino 285*e4b17023SJohn Marino _Rb_tree_node_base* _Rb_tree_rebalance_for_erase(_Rb_tree_node_base * const __z,_Rb_tree_node_base & __header)286*e4b17023SJohn Marino _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 287*e4b17023SJohn Marino _Rb_tree_node_base& __header) throw () 288*e4b17023SJohn Marino { 289*e4b17023SJohn Marino _Rb_tree_node_base *& __root = __header._M_parent; 290*e4b17023SJohn Marino _Rb_tree_node_base *& __leftmost = __header._M_left; 291*e4b17023SJohn Marino _Rb_tree_node_base *& __rightmost = __header._M_right; 292*e4b17023SJohn Marino _Rb_tree_node_base* __y = __z; 293*e4b17023SJohn Marino _Rb_tree_node_base* __x = 0; 294*e4b17023SJohn Marino _Rb_tree_node_base* __x_parent = 0; 295*e4b17023SJohn Marino 296*e4b17023SJohn Marino if (__y->_M_left == 0) // __z has at most one non-null child. y == z. 297*e4b17023SJohn Marino __x = __y->_M_right; // __x might be null. 298*e4b17023SJohn Marino else 299*e4b17023SJohn Marino if (__y->_M_right == 0) // __z has exactly one non-null child. y == z. 300*e4b17023SJohn Marino __x = __y->_M_left; // __x is not null. 301*e4b17023SJohn Marino else 302*e4b17023SJohn Marino { 303*e4b17023SJohn Marino // __z has two non-null children. Set __y to 304*e4b17023SJohn Marino __y = __y->_M_right; // __z's successor. __x might be null. 305*e4b17023SJohn Marino while (__y->_M_left != 0) 306*e4b17023SJohn Marino __y = __y->_M_left; 307*e4b17023SJohn Marino __x = __y->_M_right; 308*e4b17023SJohn Marino } 309*e4b17023SJohn Marino if (__y != __z) 310*e4b17023SJohn Marino { 311*e4b17023SJohn Marino // relink y in place of z. y is z's successor 312*e4b17023SJohn Marino __z->_M_left->_M_parent = __y; 313*e4b17023SJohn Marino __y->_M_left = __z->_M_left; 314*e4b17023SJohn Marino if (__y != __z->_M_right) 315*e4b17023SJohn Marino { 316*e4b17023SJohn Marino __x_parent = __y->_M_parent; 317*e4b17023SJohn Marino if (__x) __x->_M_parent = __y->_M_parent; 318*e4b17023SJohn Marino __y->_M_parent->_M_left = __x; // __y must be a child of _M_left 319*e4b17023SJohn Marino __y->_M_right = __z->_M_right; 320*e4b17023SJohn Marino __z->_M_right->_M_parent = __y; 321*e4b17023SJohn Marino } 322*e4b17023SJohn Marino else 323*e4b17023SJohn Marino __x_parent = __y; 324*e4b17023SJohn Marino if (__root == __z) 325*e4b17023SJohn Marino __root = __y; 326*e4b17023SJohn Marino else if (__z->_M_parent->_M_left == __z) 327*e4b17023SJohn Marino __z->_M_parent->_M_left = __y; 328*e4b17023SJohn Marino else 329*e4b17023SJohn Marino __z->_M_parent->_M_right = __y; 330*e4b17023SJohn Marino __y->_M_parent = __z->_M_parent; 331*e4b17023SJohn Marino std::swap(__y->_M_color, __z->_M_color); 332*e4b17023SJohn Marino __y = __z; 333*e4b17023SJohn Marino // __y now points to node to be actually deleted 334*e4b17023SJohn Marino } 335*e4b17023SJohn Marino else 336*e4b17023SJohn Marino { // __y == __z 337*e4b17023SJohn Marino __x_parent = __y->_M_parent; 338*e4b17023SJohn Marino if (__x) 339*e4b17023SJohn Marino __x->_M_parent = __y->_M_parent; 340*e4b17023SJohn Marino if (__root == __z) 341*e4b17023SJohn Marino __root = __x; 342*e4b17023SJohn Marino else 343*e4b17023SJohn Marino if (__z->_M_parent->_M_left == __z) 344*e4b17023SJohn Marino __z->_M_parent->_M_left = __x; 345*e4b17023SJohn Marino else 346*e4b17023SJohn Marino __z->_M_parent->_M_right = __x; 347*e4b17023SJohn Marino if (__leftmost == __z) 348*e4b17023SJohn Marino { 349*e4b17023SJohn Marino if (__z->_M_right == 0) // __z->_M_left must be null also 350*e4b17023SJohn Marino __leftmost = __z->_M_parent; 351*e4b17023SJohn Marino // makes __leftmost == _M_header if __z == __root 352*e4b17023SJohn Marino else 353*e4b17023SJohn Marino __leftmost = _Rb_tree_node_base::_S_minimum(__x); 354*e4b17023SJohn Marino } 355*e4b17023SJohn Marino if (__rightmost == __z) 356*e4b17023SJohn Marino { 357*e4b17023SJohn Marino if (__z->_M_left == 0) // __z->_M_right must be null also 358*e4b17023SJohn Marino __rightmost = __z->_M_parent; 359*e4b17023SJohn Marino // makes __rightmost == _M_header if __z == __root 360*e4b17023SJohn Marino else // __x == __z->_M_left 361*e4b17023SJohn Marino __rightmost = _Rb_tree_node_base::_S_maximum(__x); 362*e4b17023SJohn Marino } 363*e4b17023SJohn Marino } 364*e4b17023SJohn Marino if (__y->_M_color != _S_red) 365*e4b17023SJohn Marino { 366*e4b17023SJohn Marino while (__x != __root && (__x == 0 || __x->_M_color == _S_black)) 367*e4b17023SJohn Marino if (__x == __x_parent->_M_left) 368*e4b17023SJohn Marino { 369*e4b17023SJohn Marino _Rb_tree_node_base* __w = __x_parent->_M_right; 370*e4b17023SJohn Marino if (__w->_M_color == _S_red) 371*e4b17023SJohn Marino { 372*e4b17023SJohn Marino __w->_M_color = _S_black; 373*e4b17023SJohn Marino __x_parent->_M_color = _S_red; 374*e4b17023SJohn Marino local_Rb_tree_rotate_left(__x_parent, __root); 375*e4b17023SJohn Marino __w = __x_parent->_M_right; 376*e4b17023SJohn Marino } 377*e4b17023SJohn Marino if ((__w->_M_left == 0 || 378*e4b17023SJohn Marino __w->_M_left->_M_color == _S_black) && 379*e4b17023SJohn Marino (__w->_M_right == 0 || 380*e4b17023SJohn Marino __w->_M_right->_M_color == _S_black)) 381*e4b17023SJohn Marino { 382*e4b17023SJohn Marino __w->_M_color = _S_red; 383*e4b17023SJohn Marino __x = __x_parent; 384*e4b17023SJohn Marino __x_parent = __x_parent->_M_parent; 385*e4b17023SJohn Marino } 386*e4b17023SJohn Marino else 387*e4b17023SJohn Marino { 388*e4b17023SJohn Marino if (__w->_M_right == 0 389*e4b17023SJohn Marino || __w->_M_right->_M_color == _S_black) 390*e4b17023SJohn Marino { 391*e4b17023SJohn Marino __w->_M_left->_M_color = _S_black; 392*e4b17023SJohn Marino __w->_M_color = _S_red; 393*e4b17023SJohn Marino local_Rb_tree_rotate_right(__w, __root); 394*e4b17023SJohn Marino __w = __x_parent->_M_right; 395*e4b17023SJohn Marino } 396*e4b17023SJohn Marino __w->_M_color = __x_parent->_M_color; 397*e4b17023SJohn Marino __x_parent->_M_color = _S_black; 398*e4b17023SJohn Marino if (__w->_M_right) 399*e4b17023SJohn Marino __w->_M_right->_M_color = _S_black; 400*e4b17023SJohn Marino local_Rb_tree_rotate_left(__x_parent, __root); 401*e4b17023SJohn Marino break; 402*e4b17023SJohn Marino } 403*e4b17023SJohn Marino } 404*e4b17023SJohn Marino else 405*e4b17023SJohn Marino { 406*e4b17023SJohn Marino // same as above, with _M_right <-> _M_left. 407*e4b17023SJohn Marino _Rb_tree_node_base* __w = __x_parent->_M_left; 408*e4b17023SJohn Marino if (__w->_M_color == _S_red) 409*e4b17023SJohn Marino { 410*e4b17023SJohn Marino __w->_M_color = _S_black; 411*e4b17023SJohn Marino __x_parent->_M_color = _S_red; 412*e4b17023SJohn Marino local_Rb_tree_rotate_right(__x_parent, __root); 413*e4b17023SJohn Marino __w = __x_parent->_M_left; 414*e4b17023SJohn Marino } 415*e4b17023SJohn Marino if ((__w->_M_right == 0 || 416*e4b17023SJohn Marino __w->_M_right->_M_color == _S_black) && 417*e4b17023SJohn Marino (__w->_M_left == 0 || 418*e4b17023SJohn Marino __w->_M_left->_M_color == _S_black)) 419*e4b17023SJohn Marino { 420*e4b17023SJohn Marino __w->_M_color = _S_red; 421*e4b17023SJohn Marino __x = __x_parent; 422*e4b17023SJohn Marino __x_parent = __x_parent->_M_parent; 423*e4b17023SJohn Marino } 424*e4b17023SJohn Marino else 425*e4b17023SJohn Marino { 426*e4b17023SJohn Marino if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black) 427*e4b17023SJohn Marino { 428*e4b17023SJohn Marino __w->_M_right->_M_color = _S_black; 429*e4b17023SJohn Marino __w->_M_color = _S_red; 430*e4b17023SJohn Marino local_Rb_tree_rotate_left(__w, __root); 431*e4b17023SJohn Marino __w = __x_parent->_M_left; 432*e4b17023SJohn Marino } 433*e4b17023SJohn Marino __w->_M_color = __x_parent->_M_color; 434*e4b17023SJohn Marino __x_parent->_M_color = _S_black; 435*e4b17023SJohn Marino if (__w->_M_left) 436*e4b17023SJohn Marino __w->_M_left->_M_color = _S_black; 437*e4b17023SJohn Marino local_Rb_tree_rotate_right(__x_parent, __root); 438*e4b17023SJohn Marino break; 439*e4b17023SJohn Marino } 440*e4b17023SJohn Marino } 441*e4b17023SJohn Marino if (__x) __x->_M_color = _S_black; 442*e4b17023SJohn Marino } 443*e4b17023SJohn Marino return __y; 444*e4b17023SJohn Marino } 445*e4b17023SJohn Marino 446*e4b17023SJohn Marino unsigned int _Rb_tree_black_count(const _Rb_tree_node_base * __node,const _Rb_tree_node_base * __root)447*e4b17023SJohn Marino _Rb_tree_black_count(const _Rb_tree_node_base* __node, 448*e4b17023SJohn Marino const _Rb_tree_node_base* __root) throw () 449*e4b17023SJohn Marino { 450*e4b17023SJohn Marino if (__node == 0) 451*e4b17023SJohn Marino return 0; 452*e4b17023SJohn Marino unsigned int __sum = 0; 453*e4b17023SJohn Marino do 454*e4b17023SJohn Marino { 455*e4b17023SJohn Marino if (__node->_M_color == _S_black) 456*e4b17023SJohn Marino ++__sum; 457*e4b17023SJohn Marino if (__node == __root) 458*e4b17023SJohn Marino break; 459*e4b17023SJohn Marino __node = __node->_M_parent; 460*e4b17023SJohn Marino } 461*e4b17023SJohn Marino while (1); 462*e4b17023SJohn Marino return __sum; 463*e4b17023SJohn Marino } 464*e4b17023SJohn Marino 465*e4b17023SJohn Marino _GLIBCXX_END_NAMESPACE_VERSION 466*e4b17023SJohn Marino } // namespace 467