1 // RB tree utilities implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2021 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 3, 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 // 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.
19 
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/>.
24 
25 /*
26  *
27  * Copyright (c) 1996,1997
28  * Silicon Graphics Computer Systems, Inc.
29  *
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.
37  *
38  *
39  * Copyright (c) 1994
40  * Hewlett-Packard Company
41  *
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.
49  *
50  *
51  */
52 
53 #include <bits/stl_tree.h>
54 
55 namespace std _GLIBCXX_VISIBILITY(default)
56 {
57 _GLIBCXX_BEGIN_NAMESPACE_VERSION
58 
59   static _Rb_tree_node_base*
local_Rb_tree_increment(_Rb_tree_node_base * __x)60   local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
61   {
62     if (__x->_M_right != 0)
63       {
64         __x = __x->_M_right;
65         while (__x->_M_left != 0)
66           __x = __x->_M_left;
67       }
68     else
69       {
70         _Rb_tree_node_base* __y = __x->_M_parent;
71         while (__x == __y->_M_right)
72           {
73             __x = __y;
74             __y = __y->_M_parent;
75           }
76         if (__x->_M_right != __y)
77           __x = __y;
78       }
79     return __x;
80   }
81 
82   _Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base * __x)83   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
84   {
85     return local_Rb_tree_increment(__x);
86   }
87 
88   const _Rb_tree_node_base*
_Rb_tree_increment(const _Rb_tree_node_base * __x)89   _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ()
90   {
91     return local_Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
92   }
93 
94   static _Rb_tree_node_base*
local_Rb_tree_decrement(_Rb_tree_node_base * __x)95   local_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
96   {
97     if (__x->_M_color == _S_red
98         && __x->_M_parent->_M_parent == __x)
99       __x = __x->_M_right;
100     else if (__x->_M_left != 0)
101       {
102         _Rb_tree_node_base* __y = __x->_M_left;
103         while (__y->_M_right != 0)
104           __y = __y->_M_right;
105         __x = __y;
106       }
107     else
108       {
109         _Rb_tree_node_base* __y = __x->_M_parent;
110         while (__x == __y->_M_left)
111           {
112             __x = __y;
113             __y = __y->_M_parent;
114           }
115         __x = __y;
116       }
117     return __x;
118   }
119 
120   _Rb_tree_node_base*
_Rb_tree_decrement(_Rb_tree_node_base * __x)121   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
122   {
123     return local_Rb_tree_decrement(__x);
124   }
125 
126   const _Rb_tree_node_base*
_Rb_tree_decrement(const _Rb_tree_node_base * __x)127   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ()
128   {
129     return local_Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));
130   }
131 
132   static void
local_Rb_tree_rotate_left(_Rb_tree_node_base * const __x,_Rb_tree_node_base * & __root)133   local_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
134 		             _Rb_tree_node_base*& __root)
135   {
136     _Rb_tree_node_base* const __y = __x->_M_right;
137 
138     __x->_M_right = __y->_M_left;
139     if (__y->_M_left !=0)
140       __y->_M_left->_M_parent = __x;
141     __y->_M_parent = __x->_M_parent;
142 
143     if (__x == __root)
144       __root = __y;
145     else if (__x == __x->_M_parent->_M_left)
146       __x->_M_parent->_M_left = __y;
147     else
148       __x->_M_parent->_M_right = __y;
149     __y->_M_left = __x;
150     __x->_M_parent = __y;
151   }
152 
153 #if !_GLIBCXX_INLINE_VERSION
154   /* Static keyword was missing on _Rb_tree_rotate_left.
155      Export the symbol for backward compatibility until
156      next ABI change.  */
157   void
_Rb_tree_rotate_left(_Rb_tree_node_base * const __x,_Rb_tree_node_base * & __root)158   _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
159 		       _Rb_tree_node_base*& __root)
160   { local_Rb_tree_rotate_left (__x, __root); }
161 #endif
162 
163   static void
local_Rb_tree_rotate_right(_Rb_tree_node_base * const __x,_Rb_tree_node_base * & __root)164   local_Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
165 			     _Rb_tree_node_base*& __root)
166   {
167     _Rb_tree_node_base* const __y = __x->_M_left;
168 
169     __x->_M_left = __y->_M_right;
170     if (__y->_M_right != 0)
171       __y->_M_right->_M_parent = __x;
172     __y->_M_parent = __x->_M_parent;
173 
174     if (__x == __root)
175       __root = __y;
176     else if (__x == __x->_M_parent->_M_right)
177       __x->_M_parent->_M_right = __y;
178     else
179       __x->_M_parent->_M_left = __y;
180     __y->_M_right = __x;
181     __x->_M_parent = __y;
182   }
183 
184 #if !_GLIBCXX_INLINE_VERSION
185   /* Static keyword was missing on _Rb_tree_rotate_right
186      Export the symbol for backward compatibility until
187      next ABI change.  */
188   void
_Rb_tree_rotate_right(_Rb_tree_node_base * const __x,_Rb_tree_node_base * & __root)189   _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
190 			_Rb_tree_node_base*& __root)
191   { local_Rb_tree_rotate_right (__x, __root); }
192 #endif
193 
194   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   _Rb_tree_insert_and_rebalance(const bool          __insert_left,
196                                 _Rb_tree_node_base* __x,
197                                 _Rb_tree_node_base* __p,
198                                 _Rb_tree_node_base& __header) throw ()
199   {
200     _Rb_tree_node_base *& __root = __header._M_parent;
201 
202     // Initialize fields in new node to insert.
203     __x->_M_parent = __p;
204     __x->_M_left = 0;
205     __x->_M_right = 0;
206     __x->_M_color = _S_red;
207 
208     // Insert.
209     // Make new node child of parent and maintain root, leftmost and
210     // rightmost nodes.
211     // N.B. First node is always inserted left.
212     if (__insert_left)
213       {
214         __p->_M_left = __x; // also makes leftmost = __x when __p == &__header
215 
216         if (__p == &__header)
217         {
218             __header._M_parent = __x;
219             __header._M_right = __x;
220         }
221         else if (__p == __header._M_left)
222           __header._M_left = __x; // maintain leftmost pointing to min node
223       }
224     else
225       {
226         __p->_M_right = __x;
227 
228         if (__p == __header._M_right)
229           __header._M_right = __x; // maintain rightmost pointing to max node
230       }
231     // Rebalance.
232     while (__x != __root
233 	   && __x->_M_parent->_M_color == _S_red)
234       {
235 	_Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent;
236 
237 	if (__x->_M_parent == __xpp->_M_left)
238 	  {
239 	    _Rb_tree_node_base* const __y = __xpp->_M_right;
240 	    if (__y && __y->_M_color == _S_red)
241 	      {
242 		__x->_M_parent->_M_color = _S_black;
243 		__y->_M_color = _S_black;
244 		__xpp->_M_color = _S_red;
245 		__x = __xpp;
246 	      }
247 	    else
248 	      {
249 		if (__x == __x->_M_parent->_M_right)
250 		  {
251 		    __x = __x->_M_parent;
252 		    local_Rb_tree_rotate_left(__x, __root);
253 		  }
254 		__x->_M_parent->_M_color = _S_black;
255 		__xpp->_M_color = _S_red;
256 		local_Rb_tree_rotate_right(__xpp, __root);
257 	      }
258 	  }
259 	else
260 	  {
261 	    _Rb_tree_node_base* const __y = __xpp->_M_left;
262 	    if (__y && __y->_M_color == _S_red)
263 	      {
264 		__x->_M_parent->_M_color = _S_black;
265 		__y->_M_color = _S_black;
266 		__xpp->_M_color = _S_red;
267 		__x = __xpp;
268 	      }
269 	    else
270 	      {
271 		if (__x == __x->_M_parent->_M_left)
272 		  {
273 		    __x = __x->_M_parent;
274 		    local_Rb_tree_rotate_right(__x, __root);
275 		  }
276 		__x->_M_parent->_M_color = _S_black;
277 		__xpp->_M_color = _S_red;
278 		local_Rb_tree_rotate_left(__xpp, __root);
279 	      }
280 	  }
281       }
282     __root->_M_color = _S_black;
283   }
284 
285   _Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base * const __z,_Rb_tree_node_base & __header)286   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
287 			       _Rb_tree_node_base& __header) throw ()
288   {
289     _Rb_tree_node_base *& __root = __header._M_parent;
290     _Rb_tree_node_base *& __leftmost = __header._M_left;
291     _Rb_tree_node_base *& __rightmost = __header._M_right;
292     _Rb_tree_node_base* __y = __z;
293     _Rb_tree_node_base* __x = 0;
294     _Rb_tree_node_base* __x_parent = 0;
295 
296     if (__y->_M_left == 0)     // __z has at most one non-null child. y == z.
297       __x = __y->_M_right;     // __x might be null.
298     else
299       if (__y->_M_right == 0)  // __z has exactly one non-null child. y == z.
300 	__x = __y->_M_left;    // __x is not null.
301       else
302 	{
303 	  // __z has two non-null children.  Set __y to
304 	  __y = __y->_M_right;   //   __z's successor.  __x might be null.
305 	  while (__y->_M_left != 0)
306 	    __y = __y->_M_left;
307 	  __x = __y->_M_right;
308 	}
309     if (__y != __z)
310       {
311 	// relink y in place of z.  y is z's successor
312 	__z->_M_left->_M_parent = __y;
313 	__y->_M_left = __z->_M_left;
314 	if (__y != __z->_M_right)
315 	  {
316 	    __x_parent = __y->_M_parent;
317 	    if (__x) __x->_M_parent = __y->_M_parent;
318 	    __y->_M_parent->_M_left = __x;   // __y must be a child of _M_left
319 	    __y->_M_right = __z->_M_right;
320 	    __z->_M_right->_M_parent = __y;
321 	  }
322 	else
323 	  __x_parent = __y;
324 	if (__root == __z)
325 	  __root = __y;
326 	else if (__z->_M_parent->_M_left == __z)
327 	  __z->_M_parent->_M_left = __y;
328 	else
329 	  __z->_M_parent->_M_right = __y;
330 	__y->_M_parent = __z->_M_parent;
331 	std::swap(__y->_M_color, __z->_M_color);
332 	__y = __z;
333 	// __y now points to node to be actually deleted
334       }
335     else
336       {                        // __y == __z
337 	__x_parent = __y->_M_parent;
338 	if (__x)
339 	  __x->_M_parent = __y->_M_parent;
340 	if (__root == __z)
341 	  __root = __x;
342 	else
343 	  if (__z->_M_parent->_M_left == __z)
344 	    __z->_M_parent->_M_left = __x;
345 	  else
346 	    __z->_M_parent->_M_right = __x;
347 	if (__leftmost == __z)
348 	  {
349 	    if (__z->_M_right == 0)        // __z->_M_left must be null also
350 	      __leftmost = __z->_M_parent;
351 	    // makes __leftmost == _M_header if __z == __root
352 	    else
353 	      __leftmost = _Rb_tree_node_base::_S_minimum(__x);
354 	  }
355 	if (__rightmost == __z)
356 	  {
357 	    if (__z->_M_left == 0)         // __z->_M_right must be null also
358 	      __rightmost = __z->_M_parent;
359 	    // makes __rightmost == _M_header if __z == __root
360 	    else                      // __x == __z->_M_left
361 	      __rightmost = _Rb_tree_node_base::_S_maximum(__x);
362 	  }
363       }
364     if (__y->_M_color != _S_red)
365       {
366 	while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
367 	  if (__x == __x_parent->_M_left)
368 	    {
369 	      _Rb_tree_node_base* __w = __x_parent->_M_right;
370 	      if (__w->_M_color == _S_red)
371 		{
372 		  __w->_M_color = _S_black;
373 		  __x_parent->_M_color = _S_red;
374 		  local_Rb_tree_rotate_left(__x_parent, __root);
375 		  __w = __x_parent->_M_right;
376 		}
377 	      if ((__w->_M_left == 0 ||
378 		   __w->_M_left->_M_color == _S_black) &&
379 		  (__w->_M_right == 0 ||
380 		   __w->_M_right->_M_color == _S_black))
381 		{
382 		  __w->_M_color = _S_red;
383 		  __x = __x_parent;
384 		  __x_parent = __x_parent->_M_parent;
385 		}
386 	      else
387 		{
388 		  if (__w->_M_right == 0
389 		      || __w->_M_right->_M_color == _S_black)
390 		    {
391 		      __w->_M_left->_M_color = _S_black;
392 		      __w->_M_color = _S_red;
393 		      local_Rb_tree_rotate_right(__w, __root);
394 		      __w = __x_parent->_M_right;
395 		    }
396 		  __w->_M_color = __x_parent->_M_color;
397 		  __x_parent->_M_color = _S_black;
398 		  if (__w->_M_right)
399 		    __w->_M_right->_M_color = _S_black;
400 		  local_Rb_tree_rotate_left(__x_parent, __root);
401 		  break;
402 		}
403 	    }
404 	  else
405 	    {
406 	      // same as above, with _M_right <-> _M_left.
407 	      _Rb_tree_node_base* __w = __x_parent->_M_left;
408 	      if (__w->_M_color == _S_red)
409 		{
410 		  __w->_M_color = _S_black;
411 		  __x_parent->_M_color = _S_red;
412 		  local_Rb_tree_rotate_right(__x_parent, __root);
413 		  __w = __x_parent->_M_left;
414 		}
415 	      if ((__w->_M_right == 0 ||
416 		   __w->_M_right->_M_color == _S_black) &&
417 		  (__w->_M_left == 0 ||
418 		   __w->_M_left->_M_color == _S_black))
419 		{
420 		  __w->_M_color = _S_red;
421 		  __x = __x_parent;
422 		  __x_parent = __x_parent->_M_parent;
423 		}
424 	      else
425 		{
426 		  if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black)
427 		    {
428 		      __w->_M_right->_M_color = _S_black;
429 		      __w->_M_color = _S_red;
430 		      local_Rb_tree_rotate_left(__w, __root);
431 		      __w = __x_parent->_M_left;
432 		    }
433 		  __w->_M_color = __x_parent->_M_color;
434 		  __x_parent->_M_color = _S_black;
435 		  if (__w->_M_left)
436 		    __w->_M_left->_M_color = _S_black;
437 		  local_Rb_tree_rotate_right(__x_parent, __root);
438 		  break;
439 		}
440 	    }
441 	if (__x) __x->_M_color = _S_black;
442       }
443     return __y;
444   }
445 
446   unsigned int
_Rb_tree_black_count(const _Rb_tree_node_base * __node,const _Rb_tree_node_base * __root)447   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
448                        const _Rb_tree_node_base* __root) throw ()
449   {
450     if (__node == 0)
451       return 0;
452     unsigned int __sum = 0;
453     do
454       {
455 	if (__node->_M_color == _S_black)
456 	  ++__sum;
457 	if (__node == __root)
458 	  break;
459 	__node = __node->_M_parent;
460       }
461     while (1);
462     return __sum;
463   }
464 
465 _GLIBCXX_END_NAMESPACE_VERSION
466 } // namespace
467