diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/src/tree.cc')
| -rw-r--r-- | gcc-4.4.3/libstdc++-v3/src/tree.cc | 431 |
1 files changed, 0 insertions, 431 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/src/tree.cc b/gcc-4.4.3/libstdc++-v3/src/tree.cc deleted file mode 100644 index c8ba93590..000000000 --- a/gcc-4.4.3/libstdc++-v3/src/tree.cc +++ /dev/null @@ -1,431 +0,0 @@ -// RB tree utilities implementation -*- C++ -*- - -// Copyright (C) 2003, 2005, 2009 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 3, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// Under Section 7 of GPL version 3, you are granted additional -// permissions described in the GCC Runtime Library Exception, version -// 3.1, as published by the Free Software Foundation. - -// You should have received a copy of the GNU General Public License and -// a copy of the GCC Runtime Library Exception along with this program; -// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -// <http://www.gnu.org/licenses/>. - -/* - * - * Copyright (c) 1996,1997 - * Silicon Graphics Computer Systems, Inc. - * - * Permission to use, copy, modify, distribute and sell this software - * and its documentation for any purpose is hereby granted without fee, - * provided that the above copyright notice appear in all copies and - * that both that copyright notice and this permission notice appear - * in supporting documentation. Silicon Graphics makes no - * representations about the suitability of this software for any - * purpose. It is provided "as is" without express or implied warranty. - * - * - * Copyright (c) 1994 - * Hewlett-Packard Company - * - * Permission to use, copy, modify, distribute and sell this software - * and its documentation for any purpose is hereby granted without fee, - * provided that the above copyright notice appear in all copies and - * that both that copyright notice and this permission notice appear - * in supporting documentation. Hewlett-Packard Company makes no - * representations about the suitability of this software for any - * purpose. It is provided "as is" without express or implied warranty. - * - * - */ - -#include <bits/stl_tree.h> - -_GLIBCXX_BEGIN_NAMESPACE(std) - - _Rb_tree_node_base* - _Rb_tree_increment(_Rb_tree_node_base* __x) - { - if (__x->_M_right != 0) - { - __x = __x->_M_right; - while (__x->_M_left != 0) - __x = __x->_M_left; - } - else - { - _Rb_tree_node_base* __y = __x->_M_parent; - while (__x == __y->_M_right) - { - __x = __y; - __y = __y->_M_parent; - } - if (__x->_M_right != __y) - __x = __y; - } - return __x; - } - - const _Rb_tree_node_base* - _Rb_tree_increment(const _Rb_tree_node_base* __x) - { - return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x)); - } - - _Rb_tree_node_base* - _Rb_tree_decrement(_Rb_tree_node_base* __x) - { - if (__x->_M_color == _S_red - && __x->_M_parent->_M_parent == __x) - __x = __x->_M_right; - else if (__x->_M_left != 0) - { - _Rb_tree_node_base* __y = __x->_M_left; - while (__y->_M_right != 0) - __y = __y->_M_right; - __x = __y; - } - else - { - _Rb_tree_node_base* __y = __x->_M_parent; - while (__x == __y->_M_left) - { - __x = __y; - __y = __y->_M_parent; - } - __x = __y; - } - return __x; - } - - const _Rb_tree_node_base* - _Rb_tree_decrement(const _Rb_tree_node_base* __x) - { - return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x)); - } - - void - _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, - _Rb_tree_node_base*& __root) - { - _Rb_tree_node_base* const __y = __x->_M_right; - - __x->_M_right = __y->_M_left; - if (__y->_M_left !=0) - __y->_M_left->_M_parent = __x; - __y->_M_parent = __x->_M_parent; - - if (__x == __root) - __root = __y; - else if (__x == __x->_M_parent->_M_left) - __x->_M_parent->_M_left = __y; - else - __x->_M_parent->_M_right = __y; - __y->_M_left = __x; - __x->_M_parent = __y; - } - - void - _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, - _Rb_tree_node_base*& __root) - { - _Rb_tree_node_base* const __y = __x->_M_left; - - __x->_M_left = __y->_M_right; - if (__y->_M_right != 0) - __y->_M_right->_M_parent = __x; - __y->_M_parent = __x->_M_parent; - - if (__x == __root) - __root = __y; - else if (__x == __x->_M_parent->_M_right) - __x->_M_parent->_M_right = __y; - else - __x->_M_parent->_M_left = __y; - __y->_M_right = __x; - __x->_M_parent = __y; - } - - 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) - { - _Rb_tree_node_base *& __root = __header._M_parent; - - // Initialize fields in new node to insert. - __x->_M_parent = __p; - __x->_M_left = 0; - __x->_M_right = 0; - __x->_M_color = _S_red; - - // Insert. - // Make new node child of parent and maintain root, leftmost and - // rightmost nodes. - // N.B. First node is always inserted left. - if (__insert_left) - { - __p->_M_left = __x; // also makes leftmost = __x when __p == &__header - - if (__p == &__header) - { - __header._M_parent = __x; - __header._M_right = __x; - } - else if (__p == __header._M_left) - __header._M_left = __x; // maintain leftmost pointing to min node - } - else - { - __p->_M_right = __x; - - if (__p == __header._M_right) - __header._M_right = __x; // maintain rightmost pointing to max node - } - // Rebalance. - while (__x != __root - && __x->_M_parent->_M_color == _S_red) - { - _Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent; - - if (__x->_M_parent == __xpp->_M_left) - { - _Rb_tree_node_base* const __y = __xpp->_M_right; - if (__y && __y->_M_color == _S_red) - { - __x->_M_parent->_M_color = _S_black; - __y->_M_color = _S_black; - __xpp->_M_color = _S_red; - __x = __xpp; - } - else - { - if (__x == __x->_M_parent->_M_right) - { - __x = __x->_M_parent; - _Rb_tree_rotate_left(__x, __root); - } - __x->_M_parent->_M_color = _S_black; - __xpp->_M_color = _S_red; - _Rb_tree_rotate_right(__xpp, __root); - } - } - else - { - _Rb_tree_node_base* const __y = __xpp->_M_left; - if (__y && __y->_M_color == _S_red) - { - __x->_M_parent->_M_color = _S_black; - __y->_M_color = _S_black; - __xpp->_M_color = _S_red; - __x = __xpp; - } - else - { - if (__x == __x->_M_parent->_M_left) - { - __x = __x->_M_parent; - _Rb_tree_rotate_right(__x, __root); - } - __x->_M_parent->_M_color = _S_black; - __xpp->_M_color = _S_red; - _Rb_tree_rotate_left(__xpp, __root); - } - } - } - __root->_M_color = _S_black; - } - - _Rb_tree_node_base* - _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, - _Rb_tree_node_base& __header) - { - _Rb_tree_node_base *& __root = __header._M_parent; - _Rb_tree_node_base *& __leftmost = __header._M_left; - _Rb_tree_node_base *& __rightmost = __header._M_right; - _Rb_tree_node_base* __y = __z; - _Rb_tree_node_base* __x = 0; - _Rb_tree_node_base* __x_parent = 0; - - if (__y->_M_left == 0) // __z has at most one non-null child. y == z. - __x = __y->_M_right; // __x might be null. - else - if (__y->_M_right == 0) // __z has exactly one non-null child. y == z. - __x = __y->_M_left; // __x is not null. - else - { - // __z has two non-null children. Set __y to - __y = __y->_M_right; // __z's successor. __x might be null. - while (__y->_M_left != 0) - __y = __y->_M_left; - __x = __y->_M_right; - } - if (__y != __z) - { - // relink y in place of z. y is z's successor - __z->_M_left->_M_parent = __y; - __y->_M_left = __z->_M_left; - if (__y != __z->_M_right) - { - __x_parent = __y->_M_parent; - if (__x) __x->_M_parent = __y->_M_parent; - __y->_M_parent->_M_left = __x; // __y must be a child of _M_left - __y->_M_right = __z->_M_right; - __z->_M_right->_M_parent = __y; - } - else - __x_parent = __y; - if (__root == __z) - __root = __y; - else if (__z->_M_parent->_M_left == __z) - __z->_M_parent->_M_left = __y; - else - __z->_M_parent->_M_right = __y; - __y->_M_parent = __z->_M_parent; - std::swap(__y->_M_color, __z->_M_color); - __y = __z; - // __y now points to node to be actually deleted - } - else - { // __y == __z - __x_parent = __y->_M_parent; - if (__x) - __x->_M_parent = __y->_M_parent; - if (__root == __z) - __root = __x; - else - if (__z->_M_parent->_M_left == __z) - __z->_M_parent->_M_left = __x; - else - __z->_M_parent->_M_right = __x; - if (__leftmost == __z) - { - if (__z->_M_right == 0) // __z->_M_left must be null also - __leftmost = __z->_M_parent; - // makes __leftmost == _M_header if __z == __root - else - __leftmost = _Rb_tree_node_base::_S_minimum(__x); - } - if (__rightmost == __z) - { - if (__z->_M_left == 0) // __z->_M_right must be null also - __rightmost = __z->_M_parent; - // makes __rightmost == _M_header if __z == __root - else // __x == __z->_M_left - __rightmost = _Rb_tree_node_base::_S_maximum(__x); - } - } - if (__y->_M_color != _S_red) - { - while (__x != __root && (__x == 0 || __x->_M_color == _S_black)) - if (__x == __x_parent->_M_left) - { - _Rb_tree_node_base* __w = __x_parent->_M_right; - if (__w->_M_color == _S_red) - { - __w->_M_color = _S_black; - __x_parent->_M_color = _S_red; - _Rb_tree_rotate_left(__x_parent, __root); - __w = __x_parent->_M_right; - } - if ((__w->_M_left == 0 || - __w->_M_left->_M_color == _S_black) && - (__w->_M_right == 0 || - __w->_M_right->_M_color == _S_black)) - { - __w->_M_color = _S_red; - __x = __x_parent; - __x_parent = __x_parent->_M_parent; - } - else - { - if (__w->_M_right == 0 - || __w->_M_right->_M_color == _S_black) - { - __w->_M_left->_M_color = _S_black; - __w->_M_color = _S_red; - _Rb_tree_rotate_right(__w, __root); - __w = __x_parent->_M_right; - } - __w->_M_color = __x_parent->_M_color; - __x_parent->_M_color = _S_black; - if (__w->_M_right) - __w->_M_right->_M_color = _S_black; - _Rb_tree_rotate_left(__x_parent, __root); - break; - } - } - else - { - // same as above, with _M_right <-> _M_left. - _Rb_tree_node_base* __w = __x_parent->_M_left; - if (__w->_M_color == _S_red) - { - __w->_M_color = _S_black; - __x_parent->_M_color = _S_red; - _Rb_tree_rotate_right(__x_parent, __root); - __w = __x_parent->_M_left; - } - if ((__w->_M_right == 0 || - __w->_M_right->_M_color == _S_black) && - (__w->_M_left == 0 || - __w->_M_left->_M_color == _S_black)) - { - __w->_M_color = _S_red; - __x = __x_parent; - __x_parent = __x_parent->_M_parent; - } - else - { - if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black) - { - __w->_M_right->_M_color = _S_black; - __w->_M_color = _S_red; - _Rb_tree_rotate_left(__w, __root); - __w = __x_parent->_M_left; - } - __w->_M_color = __x_parent->_M_color; - __x_parent->_M_color = _S_black; - if (__w->_M_left) - __w->_M_left->_M_color = _S_black; - _Rb_tree_rotate_right(__x_parent, __root); - break; - } - } - if (__x) __x->_M_color = _S_black; - } - return __y; - } - - unsigned int - _Rb_tree_black_count(const _Rb_tree_node_base* __node, - const _Rb_tree_node_base* __root) - { - if (__node == 0) - return 0; - unsigned int __sum = 0; - do - { - if (__node->_M_color == _S_black) - ++__sum; - if (__node == __root) - break; - __node = __node->_M_parent; - } - while (1); - return __sum; - } - -_GLIBCXX_END_NAMESPACE |