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