obtained gcc-4.6.4.tar.bz2 from upstream website;upstream

verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.

downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.

if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.

1 files changed, 454 insertions, 0 deletions

diff --git a/libstdc++-v3/src/tree.cc b/libstdc++-v3/src/tree.cc
new file mode 100644
index 000000000..0a7f6f9e4
--- /dev/null
+++ b/libstdc++-v3/src/tree.cc
@@ -0,0 +1,454 @@
+// 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>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  _Rb_tree_node_base*
+  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
+  {
+    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) throw ()
+  {
+    return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
+  }
+
+  _Rb_tree_node_base*
+  _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
+  {
+    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) throw ()
+  {
+    return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));
+  }
+
+  static void 
+  local_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;
+  }
+
+  /* Static keyword was missing on _Rb_tree_rotate_left.
+     Export the symbol for backward compatibility until
+     next ABI change.  */
+  void 
+  _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, 
+		       _Rb_tree_node_base*& __root)
+  {
+    local_Rb_tree_rotate_left (__x, __root);
+  }
+
+  static void 
+  local_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;
+  }
+
+  /* Static keyword was missing on _Rb_tree_rotate_right
+     Export the symbol for backward compatibility until
+     next ABI change.  */
+  void 
+  _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, 
+			_Rb_tree_node_base*& __root)
+  {
+    local_Rb_tree_rotate_right (__x, __root);
+  }
+
+  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) throw ()
+  {
+    _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;
+		    local_Rb_tree_rotate_left(__x, __root);
+		  }
+		__x->_M_parent->_M_color = _S_black;
+		__xpp->_M_color = _S_red;
+		local_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;
+		    local_Rb_tree_rotate_right(__x, __root);
+		  }
+		__x->_M_parent->_M_color = _S_black;
+		__xpp->_M_color = _S_red;
+		local_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) throw ()
+  {
+    _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;
+		  local_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;
+		      local_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;
+		  local_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;
+		  local_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;
+		      local_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;
+		  local_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) throw ()
+  {
+    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_VERSION
+} // namespace