[gcc] GCC 4.5.0=>4.5.1

gcc/libstdc++-v3/src/tree.cc

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