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 namespace std
_GLIBCXX_VISIBILITY(default)
57 _GLIBCXX_BEGIN_NAMESPACE_VERSION
60 _Rb_tree_increment(_Rb_tree_node_base
* __x
) throw ()
62 if (__x
->_M_right
!= 0)
65 while (__x
->_M_left
!= 0)
70 _Rb_tree_node_base
* __y
= __x
->_M_parent
;
71 while (__x
== __y
->_M_right
)
76 if (__x
->_M_right
!= __y
)
82 const _Rb_tree_node_base
*
83 _Rb_tree_increment(const _Rb_tree_node_base
* __x
) throw ()
85 return _Rb_tree_increment(const_cast<_Rb_tree_node_base
*>(__x
));
89 _Rb_tree_decrement(_Rb_tree_node_base
* __x
) throw ()
91 if (__x
->_M_color
== _S_red
92 && __x
->_M_parent
->_M_parent
== __x
)
94 else if (__x
->_M_left
!= 0)
96 _Rb_tree_node_base
* __y
= __x
->_M_left
;
97 while (__y
->_M_right
!= 0)
103 _Rb_tree_node_base
* __y
= __x
->_M_parent
;
104 while (__x
== __y
->_M_left
)
107 __y
= __y
->_M_parent
;
114 const _Rb_tree_node_base
*
115 _Rb_tree_decrement(const _Rb_tree_node_base
* __x
) throw ()
117 return _Rb_tree_decrement(const_cast<_Rb_tree_node_base
*>(__x
));
121 local_Rb_tree_rotate_left(_Rb_tree_node_base
* const __x
,
122 _Rb_tree_node_base
*& __root
)
124 _Rb_tree_node_base
* const __y
= __x
->_M_right
;
126 __x
->_M_right
= __y
->_M_left
;
127 if (__y
->_M_left
!=0)
128 __y
->_M_left
->_M_parent
= __x
;
129 __y
->_M_parent
= __x
->_M_parent
;
133 else if (__x
== __x
->_M_parent
->_M_left
)
134 __x
->_M_parent
->_M_left
= __y
;
136 __x
->_M_parent
->_M_right
= __y
;
138 __x
->_M_parent
= __y
;
141 /* Static keyword was missing on _Rb_tree_rotate_left.
142 Export the symbol for backward compatibility until
145 _Rb_tree_rotate_left(_Rb_tree_node_base
* const __x
,
146 _Rb_tree_node_base
*& __root
)
148 local_Rb_tree_rotate_left (__x
, __root
);
152 local_Rb_tree_rotate_right(_Rb_tree_node_base
* const __x
,
153 _Rb_tree_node_base
*& __root
)
155 _Rb_tree_node_base
* const __y
= __x
->_M_left
;
157 __x
->_M_left
= __y
->_M_right
;
158 if (__y
->_M_right
!= 0)
159 __y
->_M_right
->_M_parent
= __x
;
160 __y
->_M_parent
= __x
->_M_parent
;
164 else if (__x
== __x
->_M_parent
->_M_right
)
165 __x
->_M_parent
->_M_right
= __y
;
167 __x
->_M_parent
->_M_left
= __y
;
169 __x
->_M_parent
= __y
;
172 /* Static keyword was missing on _Rb_tree_rotate_right
173 Export the symbol for backward compatibility until
176 _Rb_tree_rotate_right(_Rb_tree_node_base
* const __x
,
177 _Rb_tree_node_base
*& __root
)
179 local_Rb_tree_rotate_right (__x
, __root
);
183 _Rb_tree_insert_and_rebalance(const bool __insert_left
,
184 _Rb_tree_node_base
* __x
,
185 _Rb_tree_node_base
* __p
,
186 _Rb_tree_node_base
& __header
) throw ()
188 _Rb_tree_node_base
*& __root
= __header
._M_parent
;
190 // Initialize fields in new node to insert.
191 __x
->_M_parent
= __p
;
194 __x
->_M_color
= _S_red
;
197 // Make new node child of parent and maintain root, leftmost and
199 // N.B. First node is always inserted left.
202 __p
->_M_left
= __x
; // also makes leftmost = __x when __p == &__header
204 if (__p
== &__header
)
206 __header
._M_parent
= __x
;
207 __header
._M_right
= __x
;
209 else if (__p
== __header
._M_left
)
210 __header
._M_left
= __x
; // maintain leftmost pointing to min node
216 if (__p
== __header
._M_right
)
217 __header
._M_right
= __x
; // maintain rightmost pointing to max node
221 && __x
->_M_parent
->_M_color
== _S_red
)
223 _Rb_tree_node_base
* const __xpp
= __x
->_M_parent
->_M_parent
;
225 if (__x
->_M_parent
== __xpp
->_M_left
)
227 _Rb_tree_node_base
* const __y
= __xpp
->_M_right
;
228 if (__y
&& __y
->_M_color
== _S_red
)
230 __x
->_M_parent
->_M_color
= _S_black
;
231 __y
->_M_color
= _S_black
;
232 __xpp
->_M_color
= _S_red
;
237 if (__x
== __x
->_M_parent
->_M_right
)
239 __x
= __x
->_M_parent
;
240 local_Rb_tree_rotate_left(__x
, __root
);
242 __x
->_M_parent
->_M_color
= _S_black
;
243 __xpp
->_M_color
= _S_red
;
244 local_Rb_tree_rotate_right(__xpp
, __root
);
249 _Rb_tree_node_base
* const __y
= __xpp
->_M_left
;
250 if (__y
&& __y
->_M_color
== _S_red
)
252 __x
->_M_parent
->_M_color
= _S_black
;
253 __y
->_M_color
= _S_black
;
254 __xpp
->_M_color
= _S_red
;
259 if (__x
== __x
->_M_parent
->_M_left
)
261 __x
= __x
->_M_parent
;
262 local_Rb_tree_rotate_right(__x
, __root
);
264 __x
->_M_parent
->_M_color
= _S_black
;
265 __xpp
->_M_color
= _S_red
;
266 local_Rb_tree_rotate_left(__xpp
, __root
);
270 __root
->_M_color
= _S_black
;
274 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
275 _Rb_tree_node_base
& __header
) throw ()
277 _Rb_tree_node_base
*& __root
= __header
._M_parent
;
278 _Rb_tree_node_base
*& __leftmost
= __header
._M_left
;
279 _Rb_tree_node_base
*& __rightmost
= __header
._M_right
;
280 _Rb_tree_node_base
* __y
= __z
;
281 _Rb_tree_node_base
* __x
= 0;
282 _Rb_tree_node_base
* __x_parent
= 0;
284 if (__y
->_M_left
== 0) // __z has at most one non-null child. y == z.
285 __x
= __y
->_M_right
; // __x might be null.
287 if (__y
->_M_right
== 0) // __z has exactly one non-null child. y == z.
288 __x
= __y
->_M_left
; // __x is not null.
291 // __z has two non-null children. Set __y to
292 __y
= __y
->_M_right
; // __z's successor. __x might be null.
293 while (__y
->_M_left
!= 0)
299 // relink y in place of z. y is z's successor
300 __z
->_M_left
->_M_parent
= __y
;
301 __y
->_M_left
= __z
->_M_left
;
302 if (__y
!= __z
->_M_right
)
304 __x_parent
= __y
->_M_parent
;
305 if (__x
) __x
->_M_parent
= __y
->_M_parent
;
306 __y
->_M_parent
->_M_left
= __x
; // __y must be a child of _M_left
307 __y
->_M_right
= __z
->_M_right
;
308 __z
->_M_right
->_M_parent
= __y
;
314 else if (__z
->_M_parent
->_M_left
== __z
)
315 __z
->_M_parent
->_M_left
= __y
;
317 __z
->_M_parent
->_M_right
= __y
;
318 __y
->_M_parent
= __z
->_M_parent
;
319 std::swap(__y
->_M_color
, __z
->_M_color
);
321 // __y now points to node to be actually deleted
325 __x_parent
= __y
->_M_parent
;
327 __x
->_M_parent
= __y
->_M_parent
;
331 if (__z
->_M_parent
->_M_left
== __z
)
332 __z
->_M_parent
->_M_left
= __x
;
334 __z
->_M_parent
->_M_right
= __x
;
335 if (__leftmost
== __z
)
337 if (__z
->_M_right
== 0) // __z->_M_left must be null also
338 __leftmost
= __z
->_M_parent
;
339 // makes __leftmost == _M_header if __z == __root
341 __leftmost
= _Rb_tree_node_base::_S_minimum(__x
);
343 if (__rightmost
== __z
)
345 if (__z
->_M_left
== 0) // __z->_M_right must be null also
346 __rightmost
= __z
->_M_parent
;
347 // makes __rightmost == _M_header if __z == __root
348 else // __x == __z->_M_left
349 __rightmost
= _Rb_tree_node_base::_S_maximum(__x
);
352 if (__y
->_M_color
!= _S_red
)
354 while (__x
!= __root
&& (__x
== 0 || __x
->_M_color
== _S_black
))
355 if (__x
== __x_parent
->_M_left
)
357 _Rb_tree_node_base
* __w
= __x_parent
->_M_right
;
358 if (__w
->_M_color
== _S_red
)
360 __w
->_M_color
= _S_black
;
361 __x_parent
->_M_color
= _S_red
;
362 local_Rb_tree_rotate_left(__x_parent
, __root
);
363 __w
= __x_parent
->_M_right
;
365 if ((__w
->_M_left
== 0 ||
366 __w
->_M_left
->_M_color
== _S_black
) &&
367 (__w
->_M_right
== 0 ||
368 __w
->_M_right
->_M_color
== _S_black
))
370 __w
->_M_color
= _S_red
;
372 __x_parent
= __x_parent
->_M_parent
;
376 if (__w
->_M_right
== 0
377 || __w
->_M_right
->_M_color
== _S_black
)
379 __w
->_M_left
->_M_color
= _S_black
;
380 __w
->_M_color
= _S_red
;
381 local_Rb_tree_rotate_right(__w
, __root
);
382 __w
= __x_parent
->_M_right
;
384 __w
->_M_color
= __x_parent
->_M_color
;
385 __x_parent
->_M_color
= _S_black
;
387 __w
->_M_right
->_M_color
= _S_black
;
388 local_Rb_tree_rotate_left(__x_parent
, __root
);
394 // same as above, with _M_right <-> _M_left.
395 _Rb_tree_node_base
* __w
= __x_parent
->_M_left
;
396 if (__w
->_M_color
== _S_red
)
398 __w
->_M_color
= _S_black
;
399 __x_parent
->_M_color
= _S_red
;
400 local_Rb_tree_rotate_right(__x_parent
, __root
);
401 __w
= __x_parent
->_M_left
;
403 if ((__w
->_M_right
== 0 ||
404 __w
->_M_right
->_M_color
== _S_black
) &&
405 (__w
->_M_left
== 0 ||
406 __w
->_M_left
->_M_color
== _S_black
))
408 __w
->_M_color
= _S_red
;
410 __x_parent
= __x_parent
->_M_parent
;
414 if (__w
->_M_left
== 0 || __w
->_M_left
->_M_color
== _S_black
)
416 __w
->_M_right
->_M_color
= _S_black
;
417 __w
->_M_color
= _S_red
;
418 local_Rb_tree_rotate_left(__w
, __root
);
419 __w
= __x_parent
->_M_left
;
421 __w
->_M_color
= __x_parent
->_M_color
;
422 __x_parent
->_M_color
= _S_black
;
424 __w
->_M_left
->_M_color
= _S_black
;
425 local_Rb_tree_rotate_right(__x_parent
, __root
);
429 if (__x
) __x
->_M_color
= _S_black
;
435 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
436 const _Rb_tree_node_base
* __root
) throw ()
440 unsigned int __sum
= 0;
443 if (__node
->_M_color
== _S_black
)
445 if (__node
== __root
)
447 __node
= __node
->_M_parent
;
453 _GLIBCXX_END_NAMESPACE_VERSION