1 // RB tree utilities implementation -*- C++ -*-
3 // Copyright (C) 2003, 2005, 2009 Free Software Foundation, Inc.
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 3, or (at your option)
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.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
27 * Copyright (c) 1996,1997
28 * Silicon Graphics Computer Systems, Inc.
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Silicon Graphics makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
40 * Hewlett-Packard Company
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Hewlett-Packard Company makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
53 #include <bits/stl_tree.h>
55 _GLIBCXX_BEGIN_NAMESPACE(std
)
58 _Rb_tree_increment(_Rb_tree_node_base
* __x
) throw ()
60 if (__x
->_M_right
!= 0)
63 while (__x
->_M_left
!= 0)
68 _Rb_tree_node_base
* __y
= __x
->_M_parent
;
69 while (__x
== __y
->_M_right
)
74 if (__x
->_M_right
!= __y
)
80 const _Rb_tree_node_base
*
81 _Rb_tree_increment(const _Rb_tree_node_base
* __x
) throw ()
83 return _Rb_tree_increment(const_cast<_Rb_tree_node_base
*>(__x
));
87 _Rb_tree_decrement(_Rb_tree_node_base
* __x
) throw ()
89 if (__x
->_M_color
== _S_red
90 && __x
->_M_parent
->_M_parent
== __x
)
92 else if (__x
->_M_left
!= 0)
94 _Rb_tree_node_base
* __y
= __x
->_M_left
;
95 while (__y
->_M_right
!= 0)
101 _Rb_tree_node_base
* __y
= __x
->_M_parent
;
102 while (__x
== __y
->_M_left
)
105 __y
= __y
->_M_parent
;
112 const _Rb_tree_node_base
*
113 _Rb_tree_decrement(const _Rb_tree_node_base
* __x
) throw ()
115 return _Rb_tree_decrement(const_cast<_Rb_tree_node_base
*>(__x
));
119 local_Rb_tree_rotate_left(_Rb_tree_node_base
* const __x
,
120 _Rb_tree_node_base
*& __root
)
122 _Rb_tree_node_base
* const __y
= __x
->_M_right
;
124 __x
->_M_right
= __y
->_M_left
;
125 if (__y
->_M_left
!=0)
126 __y
->_M_left
->_M_parent
= __x
;
127 __y
->_M_parent
= __x
->_M_parent
;
131 else if (__x
== __x
->_M_parent
->_M_left
)
132 __x
->_M_parent
->_M_left
= __y
;
134 __x
->_M_parent
->_M_right
= __y
;
136 __x
->_M_parent
= __y
;
139 /* Static keyword was missing on _Rb_tree_rotate_left.
140 Export the symbol for backward compatibility until
143 _Rb_tree_rotate_left(_Rb_tree_node_base
* const __x
,
144 _Rb_tree_node_base
*& __root
)
146 local_Rb_tree_rotate_left (__x
, __root
);
150 local_Rb_tree_rotate_right(_Rb_tree_node_base
* const __x
,
151 _Rb_tree_node_base
*& __root
)
153 _Rb_tree_node_base
* const __y
= __x
->_M_left
;
155 __x
->_M_left
= __y
->_M_right
;
156 if (__y
->_M_right
!= 0)
157 __y
->_M_right
->_M_parent
= __x
;
158 __y
->_M_parent
= __x
->_M_parent
;
162 else if (__x
== __x
->_M_parent
->_M_right
)
163 __x
->_M_parent
->_M_right
= __y
;
165 __x
->_M_parent
->_M_left
= __y
;
167 __x
->_M_parent
= __y
;
170 /* Static keyword was missing on _Rb_tree_rotate_right
171 Export the symbol for backward compatibility until
174 _Rb_tree_rotate_right(_Rb_tree_node_base
* const __x
,
175 _Rb_tree_node_base
*& __root
)
177 local_Rb_tree_rotate_right (__x
, __root
);
181 _Rb_tree_insert_and_rebalance(const bool __insert_left
,
182 _Rb_tree_node_base
* __x
,
183 _Rb_tree_node_base
* __p
,
184 _Rb_tree_node_base
& __header
) throw ()
186 _Rb_tree_node_base
*& __root
= __header
._M_parent
;
188 // Initialize fields in new node to insert.
189 __x
->_M_parent
= __p
;
192 __x
->_M_color
= _S_red
;
195 // Make new node child of parent and maintain root, leftmost and
197 // N.B. First node is always inserted left.
200 __p
->_M_left
= __x
; // also makes leftmost = __x when __p == &__header
202 if (__p
== &__header
)
204 __header
._M_parent
= __x
;
205 __header
._M_right
= __x
;
207 else if (__p
== __header
._M_left
)
208 __header
._M_left
= __x
; // maintain leftmost pointing to min node
214 if (__p
== __header
._M_right
)
215 __header
._M_right
= __x
; // maintain rightmost pointing to max node
219 && __x
->_M_parent
->_M_color
== _S_red
)
221 _Rb_tree_node_base
* const __xpp
= __x
->_M_parent
->_M_parent
;
223 if (__x
->_M_parent
== __xpp
->_M_left
)
225 _Rb_tree_node_base
* const __y
= __xpp
->_M_right
;
226 if (__y
&& __y
->_M_color
== _S_red
)
228 __x
->_M_parent
->_M_color
= _S_black
;
229 __y
->_M_color
= _S_black
;
230 __xpp
->_M_color
= _S_red
;
235 if (__x
== __x
->_M_parent
->_M_right
)
237 __x
= __x
->_M_parent
;
238 local_Rb_tree_rotate_left(__x
, __root
);
240 __x
->_M_parent
->_M_color
= _S_black
;
241 __xpp
->_M_color
= _S_red
;
242 local_Rb_tree_rotate_right(__xpp
, __root
);
247 _Rb_tree_node_base
* const __y
= __xpp
->_M_left
;
248 if (__y
&& __y
->_M_color
== _S_red
)
250 __x
->_M_parent
->_M_color
= _S_black
;
251 __y
->_M_color
= _S_black
;
252 __xpp
->_M_color
= _S_red
;
257 if (__x
== __x
->_M_parent
->_M_left
)
259 __x
= __x
->_M_parent
;
260 local_Rb_tree_rotate_right(__x
, __root
);
262 __x
->_M_parent
->_M_color
= _S_black
;
263 __xpp
->_M_color
= _S_red
;
264 local_Rb_tree_rotate_left(__xpp
, __root
);
268 __root
->_M_color
= _S_black
;
272 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
273 _Rb_tree_node_base
& __header
) throw ()
275 _Rb_tree_node_base
*& __root
= __header
._M_parent
;
276 _Rb_tree_node_base
*& __leftmost
= __header
._M_left
;
277 _Rb_tree_node_base
*& __rightmost
= __header
._M_right
;
278 _Rb_tree_node_base
* __y
= __z
;
279 _Rb_tree_node_base
* __x
= 0;
280 _Rb_tree_node_base
* __x_parent
= 0;
282 if (__y
->_M_left
== 0) // __z has at most one non-null child. y == z.
283 __x
= __y
->_M_right
; // __x might be null.
285 if (__y
->_M_right
== 0) // __z has exactly one non-null child. y == z.
286 __x
= __y
->_M_left
; // __x is not null.
289 // __z has two non-null children. Set __y to
290 __y
= __y
->_M_right
; // __z's successor. __x might be null.
291 while (__y
->_M_left
!= 0)
297 // relink y in place of z. y is z's successor
298 __z
->_M_left
->_M_parent
= __y
;
299 __y
->_M_left
= __z
->_M_left
;
300 if (__y
!= __z
->_M_right
)
302 __x_parent
= __y
->_M_parent
;
303 if (__x
) __x
->_M_parent
= __y
->_M_parent
;
304 __y
->_M_parent
->_M_left
= __x
; // __y must be a child of _M_left
305 __y
->_M_right
= __z
->_M_right
;
306 __z
->_M_right
->_M_parent
= __y
;
312 else if (__z
->_M_parent
->_M_left
== __z
)
313 __z
->_M_parent
->_M_left
= __y
;
315 __z
->_M_parent
->_M_right
= __y
;
316 __y
->_M_parent
= __z
->_M_parent
;
317 std::swap(__y
->_M_color
, __z
->_M_color
);
319 // __y now points to node to be actually deleted
323 __x_parent
= __y
->_M_parent
;
325 __x
->_M_parent
= __y
->_M_parent
;
329 if (__z
->_M_parent
->_M_left
== __z
)
330 __z
->_M_parent
->_M_left
= __x
;
332 __z
->_M_parent
->_M_right
= __x
;
333 if (__leftmost
== __z
)
335 if (__z
->_M_right
== 0) // __z->_M_left must be null also
336 __leftmost
= __z
->_M_parent
;
337 // makes __leftmost == _M_header if __z == __root
339 __leftmost
= _Rb_tree_node_base::_S_minimum(__x
);
341 if (__rightmost
== __z
)
343 if (__z
->_M_left
== 0) // __z->_M_right must be null also
344 __rightmost
= __z
->_M_parent
;
345 // makes __rightmost == _M_header if __z == __root
346 else // __x == __z->_M_left
347 __rightmost
= _Rb_tree_node_base::_S_maximum(__x
);
350 if (__y
->_M_color
!= _S_red
)
352 while (__x
!= __root
&& (__x
== 0 || __x
->_M_color
== _S_black
))
353 if (__x
== __x_parent
->_M_left
)
355 _Rb_tree_node_base
* __w
= __x_parent
->_M_right
;
356 if (__w
->_M_color
== _S_red
)
358 __w
->_M_color
= _S_black
;
359 __x_parent
->_M_color
= _S_red
;
360 local_Rb_tree_rotate_left(__x_parent
, __root
);
361 __w
= __x_parent
->_M_right
;
363 if ((__w
->_M_left
== 0 ||
364 __w
->_M_left
->_M_color
== _S_black
) &&
365 (__w
->_M_right
== 0 ||
366 __w
->_M_right
->_M_color
== _S_black
))
368 __w
->_M_color
= _S_red
;
370 __x_parent
= __x_parent
->_M_parent
;
374 if (__w
->_M_right
== 0
375 || __w
->_M_right
->_M_color
== _S_black
)
377 __w
->_M_left
->_M_color
= _S_black
;
378 __w
->_M_color
= _S_red
;
379 local_Rb_tree_rotate_right(__w
, __root
);
380 __w
= __x_parent
->_M_right
;
382 __w
->_M_color
= __x_parent
->_M_color
;
383 __x_parent
->_M_color
= _S_black
;
385 __w
->_M_right
->_M_color
= _S_black
;
386 local_Rb_tree_rotate_left(__x_parent
, __root
);
392 // same as above, with _M_right <-> _M_left.
393 _Rb_tree_node_base
* __w
= __x_parent
->_M_left
;
394 if (__w
->_M_color
== _S_red
)
396 __w
->_M_color
= _S_black
;
397 __x_parent
->_M_color
= _S_red
;
398 local_Rb_tree_rotate_right(__x_parent
, __root
);
399 __w
= __x_parent
->_M_left
;
401 if ((__w
->_M_right
== 0 ||
402 __w
->_M_right
->_M_color
== _S_black
) &&
403 (__w
->_M_left
== 0 ||
404 __w
->_M_left
->_M_color
== _S_black
))
406 __w
->_M_color
= _S_red
;
408 __x_parent
= __x_parent
->_M_parent
;
412 if (__w
->_M_left
== 0 || __w
->_M_left
->_M_color
== _S_black
)
414 __w
->_M_right
->_M_color
= _S_black
;
415 __w
->_M_color
= _S_red
;
416 local_Rb_tree_rotate_left(__w
, __root
);
417 __w
= __x_parent
->_M_left
;
419 __w
->_M_color
= __x_parent
->_M_color
;
420 __x_parent
->_M_color
= _S_black
;
422 __w
->_M_left
->_M_color
= _S_black
;
423 local_Rb_tree_rotate_right(__x_parent
, __root
);
427 if (__x
) __x
->_M_color
= _S_black
;
433 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
434 const _Rb_tree_node_base
* __root
) throw ()
438 unsigned int __sum
= 0;
441 if (__node
->_M_color
== _S_black
)
443 if (__node
== __root
)
445 __node
= __node
->_M_parent
;
451 _GLIBCXX_END_NAMESPACE