xref: /dflybsd-src/contrib/gcc-4.7/libstdc++-v3/src/c++98/tree.cc (revision 04febcfb30580676d3e95f58a16c5137ee478b32)
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