1// RB tree utilities implementation -*- C++ -*- 2 3// Copyright (C) 2003-2022 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 55namespace std _GLIBCXX_VISIBILITY(default) 56{ 57_GLIBCXX_BEGIN_NAMESPACE_VERSION 58 59 static _Rb_tree_node_base* 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* 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* 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* 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* 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* 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 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 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 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 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 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* 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 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