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