Index: gcc/libstdc++-v3/src/tree.cc |
diff --git a/gcc/libstdc++-v3/src/tree.cc b/gcc/libstdc++-v3/src/tree.cc |
deleted file mode 100644 |
index c8ba935902483e4cdc63a84e1af6cc5380d50855..0000000000000000000000000000000000000000 |
--- a/gcc/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 |