tree.cc
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 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* 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* 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* 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 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 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 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* 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 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