1132720Skan// RB tree utilities implementation -*- C++ -*- 2132720Skan 3169691Skan// Copyright (C) 2003, 2005 Free Software Foundation, Inc. 4132720Skan// 5132720Skan// This file is part of the GNU ISO C++ Library. This library is free 6132720Skan// software; you can redistribute it and/or modify it under the 7132720Skan// terms of the GNU General Public License as published by the 8132720Skan// Free Software Foundation; either version 2, or (at your option) 9132720Skan// any later version. 10132720Skan 11132720Skan// This library is distributed in the hope that it will be useful, 12132720Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 13132720Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14132720Skan// GNU General Public License for more details. 15132720Skan 16132720Skan// You should have received a copy of the GNU General Public License along 17132720Skan// with this library; see the file COPYING. If not, write to the Free 18169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19132720Skan// USA. 20132720Skan 21132720Skan// As a special exception, you may use this file as part of a free software 22132720Skan// library without restriction. Specifically, if other files instantiate 23132720Skan// templates or use macros or inline functions from this file, or you compile 24132720Skan// this file and link it with other files to produce an executable, this 25132720Skan// file does not by itself cause the resulting executable to be covered by 26132720Skan// the GNU General Public License. This exception does not however 27132720Skan// invalidate any other reasons why the executable file might be covered by 28132720Skan// the GNU General Public License. 29132720Skan 30132720Skan/* 31132720Skan * 32132720Skan * Copyright (c) 1996,1997 33132720Skan * Silicon Graphics Computer Systems, Inc. 34132720Skan * 35132720Skan * Permission to use, copy, modify, distribute and sell this software 36132720Skan * and its documentation for any purpose is hereby granted without fee, 37132720Skan * provided that the above copyright notice appear in all copies and 38132720Skan * that both that copyright notice and this permission notice appear 39132720Skan * in supporting documentation. Silicon Graphics makes no 40132720Skan * representations about the suitability of this software for any 41132720Skan * purpose. It is provided "as is" without express or implied warranty. 42132720Skan * 43132720Skan * 44132720Skan * Copyright (c) 1994 45132720Skan * Hewlett-Packard Company 46132720Skan * 47132720Skan * Permission to use, copy, modify, distribute and sell this software 48132720Skan * and its documentation for any purpose is hereby granted without fee, 49132720Skan * provided that the above copyright notice appear in all copies and 50132720Skan * that both that copyright notice and this permission notice appear 51132720Skan * in supporting documentation. Hewlett-Packard Company makes no 52132720Skan * representations about the suitability of this software for any 53132720Skan * purpose. It is provided "as is" without express or implied warranty. 54132720Skan * 55132720Skan * 56132720Skan */ 57132720Skan 58132720Skan#include <bits/stl_tree.h> 59132720Skan 60169691Skan_GLIBCXX_BEGIN_NAMESPACE(std) 61169691Skan 62132720Skan _Rb_tree_node_base* 63132720Skan _Rb_tree_increment(_Rb_tree_node_base* __x) 64132720Skan { 65132720Skan if (__x->_M_right != 0) 66132720Skan { 67132720Skan __x = __x->_M_right; 68132720Skan while (__x->_M_left != 0) 69132720Skan __x = __x->_M_left; 70132720Skan } 71132720Skan else 72132720Skan { 73132720Skan _Rb_tree_node_base* __y = __x->_M_parent; 74132720Skan while (__x == __y->_M_right) 75132720Skan { 76132720Skan __x = __y; 77132720Skan __y = __y->_M_parent; 78132720Skan } 79132720Skan if (__x->_M_right != __y) 80132720Skan __x = __y; 81132720Skan } 82132720Skan return __x; 83132720Skan } 84132720Skan 85132720Skan const _Rb_tree_node_base* 86132720Skan _Rb_tree_increment(const _Rb_tree_node_base* __x) 87132720Skan { 88132720Skan return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x)); 89132720Skan } 90132720Skan 91132720Skan _Rb_tree_node_base* 92132720Skan _Rb_tree_decrement(_Rb_tree_node_base* __x) 93132720Skan { 94132720Skan if (__x->_M_color == _S_red 95132720Skan && __x->_M_parent->_M_parent == __x) 96132720Skan __x = __x->_M_right; 97132720Skan else if (__x->_M_left != 0) 98132720Skan { 99132720Skan _Rb_tree_node_base* __y = __x->_M_left; 100132720Skan while (__y->_M_right != 0) 101132720Skan __y = __y->_M_right; 102132720Skan __x = __y; 103132720Skan } 104132720Skan else 105132720Skan { 106132720Skan _Rb_tree_node_base* __y = __x->_M_parent; 107132720Skan while (__x == __y->_M_left) 108132720Skan { 109132720Skan __x = __y; 110132720Skan __y = __y->_M_parent; 111132720Skan } 112132720Skan __x = __y; 113132720Skan } 114132720Skan return __x; 115132720Skan } 116132720Skan 117132720Skan const _Rb_tree_node_base* 118132720Skan _Rb_tree_decrement(const _Rb_tree_node_base* __x) 119132720Skan { 120132720Skan return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x)); 121132720Skan } 122132720Skan 123132720Skan void 124132720Skan _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, 125132720Skan _Rb_tree_node_base*& __root) 126132720Skan { 127132720Skan _Rb_tree_node_base* const __y = __x->_M_right; 128132720Skan 129132720Skan __x->_M_right = __y->_M_left; 130132720Skan if (__y->_M_left !=0) 131132720Skan __y->_M_left->_M_parent = __x; 132132720Skan __y->_M_parent = __x->_M_parent; 133132720Skan 134132720Skan if (__x == __root) 135132720Skan __root = __y; 136132720Skan else if (__x == __x->_M_parent->_M_left) 137132720Skan __x->_M_parent->_M_left = __y; 138132720Skan else 139132720Skan __x->_M_parent->_M_right = __y; 140132720Skan __y->_M_left = __x; 141132720Skan __x->_M_parent = __y; 142132720Skan } 143132720Skan 144132720Skan void 145132720Skan _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, 146132720Skan _Rb_tree_node_base*& __root) 147132720Skan { 148132720Skan _Rb_tree_node_base* const __y = __x->_M_left; 149132720Skan 150132720Skan __x->_M_left = __y->_M_right; 151132720Skan if (__y->_M_right != 0) 152132720Skan __y->_M_right->_M_parent = __x; 153132720Skan __y->_M_parent = __x->_M_parent; 154132720Skan 155132720Skan if (__x == __root) 156132720Skan __root = __y; 157132720Skan else if (__x == __x->_M_parent->_M_right) 158132720Skan __x->_M_parent->_M_right = __y; 159132720Skan else 160132720Skan __x->_M_parent->_M_left = __y; 161132720Skan __y->_M_right = __x; 162132720Skan __x->_M_parent = __y; 163132720Skan } 164132720Skan 165132720Skan void 166132720Skan _Rb_tree_insert_and_rebalance(const bool __insert_left, 167132720Skan _Rb_tree_node_base* __x, 168132720Skan _Rb_tree_node_base* __p, 169132720Skan _Rb_tree_node_base& __header) 170132720Skan { 171132720Skan _Rb_tree_node_base *& __root = __header._M_parent; 172132720Skan 173132720Skan // Initialize fields in new node to insert. 174132720Skan __x->_M_parent = __p; 175132720Skan __x->_M_left = 0; 176132720Skan __x->_M_right = 0; 177132720Skan __x->_M_color = _S_red; 178132720Skan 179132720Skan // Insert. 180132720Skan // Make new node child of parent and maintain root, leftmost and 181132720Skan // rightmost nodes. 182132720Skan // N.B. First node is always inserted left. 183132720Skan if (__insert_left) 184132720Skan { 185132720Skan __p->_M_left = __x; // also makes leftmost = __x when __p == &__header 186132720Skan 187132720Skan if (__p == &__header) 188132720Skan { 189132720Skan __header._M_parent = __x; 190132720Skan __header._M_right = __x; 191132720Skan } 192132720Skan else if (__p == __header._M_left) 193132720Skan __header._M_left = __x; // maintain leftmost pointing to min node 194132720Skan } 195132720Skan else 196132720Skan { 197132720Skan __p->_M_right = __x; 198132720Skan 199132720Skan if (__p == __header._M_right) 200132720Skan __header._M_right = __x; // maintain rightmost pointing to max node 201132720Skan } 202132720Skan // Rebalance. 203132720Skan while (__x != __root 204132720Skan && __x->_M_parent->_M_color == _S_red) 205132720Skan { 206132720Skan _Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent; 207132720Skan 208132720Skan if (__x->_M_parent == __xpp->_M_left) 209132720Skan { 210132720Skan _Rb_tree_node_base* const __y = __xpp->_M_right; 211132720Skan if (__y && __y->_M_color == _S_red) 212132720Skan { 213132720Skan __x->_M_parent->_M_color = _S_black; 214132720Skan __y->_M_color = _S_black; 215132720Skan __xpp->_M_color = _S_red; 216132720Skan __x = __xpp; 217132720Skan } 218132720Skan else 219132720Skan { 220132720Skan if (__x == __x->_M_parent->_M_right) 221132720Skan { 222132720Skan __x = __x->_M_parent; 223132720Skan _Rb_tree_rotate_left(__x, __root); 224132720Skan } 225132720Skan __x->_M_parent->_M_color = _S_black; 226132720Skan __xpp->_M_color = _S_red; 227132720Skan _Rb_tree_rotate_right(__xpp, __root); 228132720Skan } 229132720Skan } 230132720Skan else 231132720Skan { 232132720Skan _Rb_tree_node_base* const __y = __xpp->_M_left; 233132720Skan if (__y && __y->_M_color == _S_red) 234132720Skan { 235132720Skan __x->_M_parent->_M_color = _S_black; 236132720Skan __y->_M_color = _S_black; 237132720Skan __xpp->_M_color = _S_red; 238132720Skan __x = __xpp; 239132720Skan } 240132720Skan else 241132720Skan { 242132720Skan if (__x == __x->_M_parent->_M_left) 243132720Skan { 244132720Skan __x = __x->_M_parent; 245132720Skan _Rb_tree_rotate_right(__x, __root); 246132720Skan } 247132720Skan __x->_M_parent->_M_color = _S_black; 248132720Skan __xpp->_M_color = _S_red; 249132720Skan _Rb_tree_rotate_left(__xpp, __root); 250132720Skan } 251132720Skan } 252132720Skan } 253132720Skan __root->_M_color = _S_black; 254132720Skan } 255132720Skan 256132720Skan _Rb_tree_node_base* 257132720Skan _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 258132720Skan _Rb_tree_node_base& __header) 259132720Skan { 260132720Skan _Rb_tree_node_base *& __root = __header._M_parent; 261132720Skan _Rb_tree_node_base *& __leftmost = __header._M_left; 262132720Skan _Rb_tree_node_base *& __rightmost = __header._M_right; 263132720Skan _Rb_tree_node_base* __y = __z; 264132720Skan _Rb_tree_node_base* __x = 0; 265132720Skan _Rb_tree_node_base* __x_parent = 0; 266132720Skan 267132720Skan if (__y->_M_left == 0) // __z has at most one non-null child. y == z. 268132720Skan __x = __y->_M_right; // __x might be null. 269132720Skan else 270132720Skan if (__y->_M_right == 0) // __z has exactly one non-null child. y == z. 271132720Skan __x = __y->_M_left; // __x is not null. 272132720Skan else 273132720Skan { 274132720Skan // __z has two non-null children. Set __y to 275132720Skan __y = __y->_M_right; // __z's successor. __x might be null. 276132720Skan while (__y->_M_left != 0) 277132720Skan __y = __y->_M_left; 278132720Skan __x = __y->_M_right; 279132720Skan } 280132720Skan if (__y != __z) 281132720Skan { 282132720Skan // relink y in place of z. y is z's successor 283132720Skan __z->_M_left->_M_parent = __y; 284132720Skan __y->_M_left = __z->_M_left; 285132720Skan if (__y != __z->_M_right) 286132720Skan { 287132720Skan __x_parent = __y->_M_parent; 288132720Skan if (__x) __x->_M_parent = __y->_M_parent; 289132720Skan __y->_M_parent->_M_left = __x; // __y must be a child of _M_left 290132720Skan __y->_M_right = __z->_M_right; 291132720Skan __z->_M_right->_M_parent = __y; 292132720Skan } 293132720Skan else 294132720Skan __x_parent = __y; 295132720Skan if (__root == __z) 296132720Skan __root = __y; 297132720Skan else if (__z->_M_parent->_M_left == __z) 298132720Skan __z->_M_parent->_M_left = __y; 299132720Skan else 300132720Skan __z->_M_parent->_M_right = __y; 301132720Skan __y->_M_parent = __z->_M_parent; 302132720Skan std::swap(__y->_M_color, __z->_M_color); 303132720Skan __y = __z; 304132720Skan // __y now points to node to be actually deleted 305132720Skan } 306132720Skan else 307132720Skan { // __y == __z 308132720Skan __x_parent = __y->_M_parent; 309132720Skan if (__x) 310132720Skan __x->_M_parent = __y->_M_parent; 311132720Skan if (__root == __z) 312132720Skan __root = __x; 313132720Skan else 314132720Skan if (__z->_M_parent->_M_left == __z) 315132720Skan __z->_M_parent->_M_left = __x; 316132720Skan else 317132720Skan __z->_M_parent->_M_right = __x; 318132720Skan if (__leftmost == __z) 319242347Sdim { 320242347Sdim if (__z->_M_right == 0) // __z->_M_left must be null also 321242347Sdim __leftmost = __z->_M_parent; 322242347Sdim // makes __leftmost == _M_header if __z == __root 323242347Sdim else 324242347Sdim __leftmost = _Rb_tree_node_base::_S_minimum(__x); 325242347Sdim } 326132720Skan if (__rightmost == __z) 327242347Sdim { 328242347Sdim if (__z->_M_left == 0) // __z->_M_right must be null also 329242347Sdim __rightmost = __z->_M_parent; 330242347Sdim // makes __rightmost == _M_header if __z == __root 331242347Sdim else // __x == __z->_M_left 332242347Sdim __rightmost = _Rb_tree_node_base::_S_maximum(__x); 333242347Sdim } 334132720Skan } 335132720Skan if (__y->_M_color != _S_red) 336132720Skan { 337132720Skan while (__x != __root && (__x == 0 || __x->_M_color == _S_black)) 338132720Skan if (__x == __x_parent->_M_left) 339132720Skan { 340132720Skan _Rb_tree_node_base* __w = __x_parent->_M_right; 341132720Skan if (__w->_M_color == _S_red) 342132720Skan { 343132720Skan __w->_M_color = _S_black; 344132720Skan __x_parent->_M_color = _S_red; 345132720Skan _Rb_tree_rotate_left(__x_parent, __root); 346132720Skan __w = __x_parent->_M_right; 347132720Skan } 348132720Skan if ((__w->_M_left == 0 || 349132720Skan __w->_M_left->_M_color == _S_black) && 350132720Skan (__w->_M_right == 0 || 351132720Skan __w->_M_right->_M_color == _S_black)) 352132720Skan { 353132720Skan __w->_M_color = _S_red; 354132720Skan __x = __x_parent; 355132720Skan __x_parent = __x_parent->_M_parent; 356132720Skan } 357132720Skan else 358132720Skan { 359132720Skan if (__w->_M_right == 0 360132720Skan || __w->_M_right->_M_color == _S_black) 361132720Skan { 362132720Skan __w->_M_left->_M_color = _S_black; 363132720Skan __w->_M_color = _S_red; 364132720Skan _Rb_tree_rotate_right(__w, __root); 365132720Skan __w = __x_parent->_M_right; 366132720Skan } 367132720Skan __w->_M_color = __x_parent->_M_color; 368132720Skan __x_parent->_M_color = _S_black; 369132720Skan if (__w->_M_right) 370132720Skan __w->_M_right->_M_color = _S_black; 371132720Skan _Rb_tree_rotate_left(__x_parent, __root); 372132720Skan break; 373132720Skan } 374132720Skan } 375132720Skan else 376132720Skan { 377132720Skan // same as above, with _M_right <-> _M_left. 378132720Skan _Rb_tree_node_base* __w = __x_parent->_M_left; 379132720Skan if (__w->_M_color == _S_red) 380132720Skan { 381132720Skan __w->_M_color = _S_black; 382132720Skan __x_parent->_M_color = _S_red; 383132720Skan _Rb_tree_rotate_right(__x_parent, __root); 384132720Skan __w = __x_parent->_M_left; 385132720Skan } 386132720Skan if ((__w->_M_right == 0 || 387132720Skan __w->_M_right->_M_color == _S_black) && 388132720Skan (__w->_M_left == 0 || 389132720Skan __w->_M_left->_M_color == _S_black)) 390132720Skan { 391132720Skan __w->_M_color = _S_red; 392132720Skan __x = __x_parent; 393132720Skan __x_parent = __x_parent->_M_parent; 394132720Skan } 395132720Skan else 396132720Skan { 397132720Skan if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black) 398132720Skan { 399132720Skan __w->_M_right->_M_color = _S_black; 400132720Skan __w->_M_color = _S_red; 401132720Skan _Rb_tree_rotate_left(__w, __root); 402132720Skan __w = __x_parent->_M_left; 403132720Skan } 404132720Skan __w->_M_color = __x_parent->_M_color; 405132720Skan __x_parent->_M_color = _S_black; 406132720Skan if (__w->_M_left) 407132720Skan __w->_M_left->_M_color = _S_black; 408132720Skan _Rb_tree_rotate_right(__x_parent, __root); 409132720Skan break; 410132720Skan } 411132720Skan } 412132720Skan if (__x) __x->_M_color = _S_black; 413132720Skan } 414132720Skan return __y; 415132720Skan } 416132720Skan 417132720Skan unsigned int 418132720Skan _Rb_tree_black_count(const _Rb_tree_node_base* __node, 419132720Skan const _Rb_tree_node_base* __root) 420132720Skan { 421132720Skan if (__node == 0) 422132720Skan return 0; 423132720Skan unsigned int __sum = 0; 424132720Skan do 425132720Skan { 426132720Skan if (__node->_M_color == _S_black) 427132720Skan ++__sum; 428132720Skan if (__node == __root) 429132720Skan break; 430132720Skan __node = __node->_M_parent; 431132720Skan } 432132720Skan while (1); 433132720Skan return __sum; 434132720Skan } 435169691Skan 436169691Skan_GLIBCXX_END_NAMESPACE 437