stl_tree.h: Move larger member functions in _Rb_tree_base_iterator and _Rb_tree_node to...

2003-07-09  Gawain Bolton  <gp.bolton@computer.org>

	* include/bits/stl_tree.h: Move larger member functions in
	_Rb_tree_base_iterator and _Rb_tree_node to...
	* src/stl_tree.cc: Here.
	* src/Makefile.in: Add stl_tree.cc.
	* src/Makefile.in: Regenerated.
	* config/linker-map.gnu: Add symbols here.

From-SVN: r69150

6 files changed, 470 insertions, 312 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 190d2d7..a5392b4 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,12 @@
+2003-07-09  Gawain Bolton  <gp.bolton@computer.org>
+
+	* include/bits/stl_tree.h: Move larger member functions in
+	_Rb_tree_base_iterator and _Rb_tree_node to...
+	* src/stl_tree.cc: Here.
+	* src/Makefile.in: Add stl_tree.cc.
+	* src/Makefile.in: Regenerated.
+	* config/linker-map.gnu: Add symbols here.
+
 2003-07-08  Benjamin Kosnik  <bkoz@redhat.com>
 
 	* testsuite/ext/pod_char_traits.cc: New.
@@ -5,7 +14,7 @@
 	* include/Makefile.am (ext_headers): Add pod_char_traits.h.
 	* include/Makefile.in: Regenerate.
 	* docs/html/21_strings/howto.html: Update.
-	
+		
 2003-07-08  Gawain Bolton  <gp.bolton@computer.org>
 
 	* testsuite/performance/list_create_fill_sort.cc: New.
diff --git a/libstdc++-v3/config/linker-map.gnu b/libstdc++-v3/config/linker-map.gnu
index 5cf3dd9..b633567 100644
--- a/libstdc++-v3/config/linker-map.gnu
+++ b/libstdc++-v3/config/linker-map.gnu
@@ -73,6 +73,14 @@ GLIBCXX_3.4 {
     # bool has_facet 
     _ZSt9has_facet*;
 
+    # _Rb_tree
+    _ZNSt22_Rb_tree_base_iterator12_M_decrementEv;
+    _ZNSt22_Rb_tree_base_iterator12_M_incrementEv;
+    _ZSt18_Rb_tree_rebalancePSt18_Rb_tree_node_baseRS0_;
+    _ZSt20_Rb_tree_rotate_leftPSt18_Rb_tree_node_baseRS0_;
+    _ZSt21_Rb_tree_rotate_rightPSt18_Rb_tree_node_baseRS0_;
+    _ZSt28_Rb_tree_rebalance_for_erasePSt18_Rb_tree_node_baseRS_;
+
     # virtual table
     _ZTVNSt8ios_base7failureE;
     _ZTVNSt6locale5facetE;
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index eb124de..9ce52f3 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -132,51 +132,10 @@ namespace std
     _Base_ptr _M_node;
 
     void 
-    _M_increment()
-    {
-      if (_M_node->_M_right != 0) 
-	{
-	  _M_node = _M_node->_M_right;
-	  while (_M_node->_M_left != 0)
-	    _M_node = _M_node->_M_left;
-	}
-      else 
-	{
-	  _Base_ptr __y = _M_node->_M_parent;
-	  while (_M_node == __y->_M_right) 
-	    {
-	      _M_node = __y;
-	      __y = __y->_M_parent;
-	    }
-	  if (_M_node->_M_right != __y)
-	    _M_node = __y;
-	}
-    }
+    _M_increment();
 
     void 
-    _M_decrement()
-    {
-      if (_M_node->_M_color == _S_red 
-	  && _M_node->_M_parent->_M_parent == _M_node)
-	_M_node = _M_node->_M_right;
-      else if (_M_node->_M_left != 0) 
-	{
-	  _Base_ptr __y = _M_node->_M_left;
-	  while (__y->_M_right != 0)
-	    __y = __y->_M_right;
-	  _M_node = __y;
-	}
-      else 
-	{
-	  _Base_ptr __y = _M_node->_M_parent;
-	  while (_M_node == __y->_M_left) 
-	    {
-	      _M_node = __y;
-	      __y = __y->_M_parent;
-	    }
-	  _M_node = __y;
-	}
-    }
+    _M_decrement();
   };
 
   template<typename _Val, typename _Ref, typename _Ptr>
@@ -264,255 +223,18 @@ namespace std
 	       const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y) 
     { return __x._M_node != __y._M_node; }
 
-  inline 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_left(_Rb_tree_node_base* const __x, _Rb_tree_node_base*& __root);
 
-  inline 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;
-  }
-
-  inline void 
-  _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
-  {
-    __x->_M_color = _S_red;
-    while (__x != __root 
-	   && __x->_M_parent->_M_color == _S_red) 
-      {
-	_Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent;
+  void 
+  _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, _Rb_tree_node_base*& __root);
 
-	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;
-  }
+  void 
+  _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root);
 
-  inline _Rb_tree_node_base*
+  _Rb_tree_node_base*
   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 
-			       _Rb_tree_node_base*& 	 __root,
-			       _Rb_tree_node_base*& 	 __leftmost,
-			       _Rb_tree_node_base*& 	 __rightmost)
-  {
-    _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;
-  }
+			       _Rb_tree_node_base& 	 __header);
 
   // Base class to encapsulate the differences between old SGI-style
   // allocators and standard-conforming allocators.  In order to avoid
@@ -1209,9 +931,7 @@ namespace std
     {
       _Link_type __y = 
 	(_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
-						  this->_M_header._M_parent,
-						  this->_M_header._M_left,
-						  this->_M_header._M_right);
+						  this->_M_header);
       destroy_node(__y);
       --_M_node_count;
     }
diff --git a/libstdc++-v3/src/Makefile.am b/libstdc++-v3/src/Makefile.am
index 72f7cbd..33d1719 100644
--- a/libstdc++-v3/src/Makefile.am
+++ b/libstdc++-v3/src/Makefile.am
@@ -144,6 +144,7 @@ sources = \
 	ostream-inst.cc \
 	sstream-inst.cc \
 	stdexcept.cc \
+	stl_tree.cc \
 	streambuf-inst.cc \
 	string-inst.cc \
 	strstream.cc \
diff --git a/libstdc++-v3/src/Makefile.in b/libstdc++-v3/src/Makefile.in
index 9062d7c..7548e58 100644
--- a/libstdc++-v3/src/Makefile.in
+++ b/libstdc++-v3/src/Makefile.in
@@ -149,8 +149,8 @@ toolexeclibdir = @glibcxx_toolexeclibdir@
 toolexeclib_LTLIBRARIES = libstdc++.la
 
 # Symbol versioning for shared libraries.
-@GLIBCXX_BUILD_VERSIONED_SHLIB_TRUE@port_specific_symbol_file = @port_specific_symbol_file@
-@GLIBCXX_BUILD_VERSIONED_SHLIB_TRUE@version_arg = -Wl,--version-script=libstdc++-symbol.ver
+@GLIBCXX_BUILD_VERSIONED_SHLIB_TRUE@port_specific_symbol_file = @GLIBCXX_BUILD_VERSIONED_SHLIB_TRUE@@port_specific_symbol_file@
+@GLIBCXX_BUILD_VERSIONED_SHLIB_TRUE@version_arg = @GLIBCXX_BUILD_VERSIONED_SHLIB_TRUE@-Wl,--version-script=libstdc++-symbol.ver
 @GLIBCXX_BUILD_VERSIONED_SHLIB_FALSE@version_arg = 
 
 # Compile flags that should be constant throughout the build, both for
@@ -159,11 +159,13 @@ OPTIMIZE_CXXFLAGS = @OPTIMIZE_CXXFLAGS@
 
 # These bits are all figured out from configure. Look in acinclude.m4
 # or configure.in to see how they are set. See GLIBCXX_EXPORT_FLAGS
-CONFIG_CXXFLAGS =  	@SECTION_FLAGS@ @EXTRA_CXX_FLAGS@
+CONFIG_CXXFLAGS = \
+	@SECTION_FLAGS@ @EXTRA_CXX_FLAGS@
 
 
 # Warning flags to use.
-WARN_CXXFLAGS =  	@WARN_FLAGS@ $(WERROR) -fdiagnostics-show-location=once
+WARN_CXXFLAGS = \
+	@WARN_FLAGS@ $(WERROR) -fdiagnostics-show-location=once
 
 
 # Use common includes from acinclude.m4/GLIBCXX_EXPORT_INCLUDES
@@ -172,33 +174,79 @@ LIBMATH_INCLUDES = @LIBMATH_INCLUDES@
 LIBSUPCXX_INCLUDES = @LIBSUPCXX_INCLUDES@
 TOPLEVEL_INCLUDES = @TOPLEVEL_INCLUDES@
 
-INCLUDES =  	-nostdinc++ 	$(GLIBCXX_INCLUDES) 	$(LIBSUPCXX_INCLUDES) $(LIBMATH_INCLUDES) 	$(TOPLEVEL_INCLUDES)
+INCLUDES = \
+	-nostdinc++ \
+	$(GLIBCXX_INCLUDES) \
+	$(LIBSUPCXX_INCLUDES) $(LIBMATH_INCLUDES) \
+	$(TOPLEVEL_INCLUDES)
 
 
 # Source files linked in via configuration/make substitution for a
 # particular host.
-host_sources =  	codecvt_members.cc 	collate_members.cc 	ctype_members.cc 	messages_members.cc 	monetary_members.cc 	numeric_members.cc 	time_members.cc
+host_sources = \
+	codecvt_members.cc \
+	collate_members.cc \
+	ctype_members.cc \
+	messages_members.cc \
+	monetary_members.cc \
+	numeric_members.cc \
+	time_members.cc
 
 
 # Source files linked in via configuration/make substitution for a
 # particular host, but with ad hoc naming rules.
-host_sources_extra =  	basic_file.cc 	c++locale.cc
+host_sources_extra = \
+	basic_file.cc \
+	c++locale.cc
 
 
 # Sources present in the src directory.
-sources =  	allocator-inst.cc 	codecvt.cc 	complex_io.cc 	concept-inst.cc 	ctype.cc 	demangle.cc 	ext-inst.cc 	fstream-inst.cc 	functexcept.cc 	globals.cc 	io-inst.cc 	ios.cc 	istream-inst.cc 	limits.cc 	locale.cc 	locale-inst.cc 	localename.cc 	misc-inst.cc 	ostream-inst.cc 	sstream-inst.cc 	stdexcept.cc 	streambuf-inst.cc 	string-inst.cc 	strstream.cc 	valarray-inst.cc 	wstring-inst.cc 	${host_sources} 	${host_sources_extra}
+sources = \
+	allocator-inst.cc \
+	codecvt.cc \
+	complex_io.cc \
+	concept-inst.cc \
+	ctype.cc \
+	demangle.cc \
+	ext-inst.cc \
+	fstream-inst.cc \
+	functexcept.cc \
+	globals.cc \
+	io-inst.cc \
+	ios.cc \
+	istream-inst.cc \
+	limits.cc \
+	locale.cc \
+	locale-inst.cc \
+	localename.cc \
+	misc-inst.cc \
+	ostream-inst.cc \
+	sstream-inst.cc \
+	stdexcept.cc \
+	stl_tree.cc \
+	streambuf-inst.cc \
+	string-inst.cc \
+	strstream.cc \
+	valarray-inst.cc \
+	wstring-inst.cc \
+	${host_sources} \
+	${host_sources_extra}
 
 
 VPATH = $(top_srcdir)/src:$(top_srcdir)
 
 libstdc___la_SOURCES = $(sources)
 
-libstdc___la_LIBADD =  	$(top_builddir)/libmath/libmath.la 	$(top_builddir)/libsupc++/libsupc++convenience.la
+libstdc___la_LIBADD = \
+	$(top_builddir)/libmath/libmath.la \
+	$(top_builddir)/libsupc++/libsupc++convenience.la
 
 
 libstdc___la_DEPENDENCIES = libstdc++-symbol.ver $(libstdc___la_LIBADD)
 
-libstdc___la_LDFLAGS =  	-version-info @libtool_VERSION@ ${version_arg} 	-lm @LIBUNWIND_FLAG@
+libstdc___la_LDFLAGS = \
+	-version-info @libtool_VERSION@ ${version_arg} \
+	-lm @LIBUNWIND_FLAG@
 
 
 # Use special rules for the deprecated source files so that they find
@@ -210,7 +258,12 @@ GLIBCXX_INCLUDE_DIR = @glibcxx_builddir@/include
 # set this option because CONFIG_CXXFLAGS has to be after
 # OPTIMIZE_CXXFLAGS on the compile line so that -O2 can be overridden
 # as the occasion calls for it.
-AM_CXXFLAGS =  	-fno-implicit-templates 	$(LIBSUPCXX_CXXFLAGS) 	$(WARN_CXXFLAGS) 	$(OPTIMIZE_CXXFLAGS) 	$(CONFIG_CXXFLAGS)
+AM_CXXFLAGS = \
+	-fno-implicit-templates \
+	$(LIBSUPCXX_CXXFLAGS) \
+	$(WARN_CXXFLAGS) \
+	$(OPTIMIZE_CXXFLAGS) \
+	$(CONFIG_CXXFLAGS)
 
 
 # libstdc++ libtool notes
@@ -231,7 +284,8 @@ AM_CXXFLAGS =  	-fno-implicit-templates 	$(LIBSUPCXX_CXXFLAGS) 	$(WARN_CXXFLAGS)
 # correct solution is to add `--tag CXX' to LTCXXCOMPILE and maybe
 # CXXLINK, just after $(LIBTOOL), so that libtool doesn't have to
 # attempt to infer which configuration to use
-LTCXXCOMPILE = $(LIBTOOL) --tag CXX --mode=compile $(CXX) $(INCLUDES) 	       $(AM_CPPFLAGS) $(CPPFLAGS) $(CXXFLAGS) $(AM_CXXFLAGS)
+LTCXXCOMPILE = $(LIBTOOL) --tag CXX --mode=compile $(CXX) $(INCLUDES) \
+	       $(AM_CPPFLAGS) $(CPPFLAGS) $(CXXFLAGS) $(AM_CXXFLAGS)
 
 
 # 3) We'd have a problem when building the shared libstdc++ object if
@@ -240,7 +294,8 @@ LTCXXCOMPILE = $(LIBTOOL) --tag CXX --mode=compile $(CXX) $(INCLUDES) 	       $(
 # course is problematic at this point.  So, we get the top-level
 # directory to configure libstdc++-v3 to use gcc as the C++
 # compilation driver.
-CXXLINK = $(LIBTOOL) --tag CXX --mode=link $(CXX) 	  @OPT_LDFLAGS@ @SECTION_LDFLAGS@ $(AM_CXXFLAGS) $(LDFLAGS) -o $@
+CXXLINK = $(LIBTOOL) --tag CXX --mode=link $(CXX) \
+	  @OPT_LDFLAGS@ @SECTION_LDFLAGS@ $(AM_CXXFLAGS) $(LDFLAGS) -o $@
 
 
 debugdir = debug
@@ -257,11 +312,11 @@ libstdc___la_OBJECTS =  allocator-inst.lo codecvt.lo complex_io.lo \
 concept-inst.lo ctype.lo demangle.lo ext-inst.lo fstream-inst.lo \
 functexcept.lo globals.lo io-inst.lo ios.lo istream-inst.lo limits.lo \
 locale.lo locale-inst.lo localename.lo misc-inst.lo ostream-inst.lo \
-sstream-inst.lo stdexcept.lo streambuf-inst.lo string-inst.lo \
-strstream.lo valarray-inst.lo wstring-inst.lo codecvt_members.lo \
-collate_members.lo ctype_members.lo messages_members.lo \
-monetary_members.lo numeric_members.lo time_members.lo basic_file.lo \
-c++locale.lo
+sstream-inst.lo stdexcept.lo stl_tree.lo streambuf-inst.lo \
+string-inst.lo strstream.lo valarray-inst.lo wstring-inst.lo \
+codecvt_members.lo collate_members.lo ctype_members.lo \
+messages_members.lo monetary_members.lo numeric_members.lo \
+time_members.lo basic_file.lo c++locale.lo
 CXXFLAGS = @CXXFLAGS@
 CXXCOMPILE = $(CXX) $(DEFS) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS)
 CXXLD = $(CXX)
@@ -270,7 +325,7 @@ DIST_COMMON =  Makefile.am Makefile.in
 
 DISTFILES = $(DIST_COMMON) $(SOURCES) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST)
 
-TAR = tar
+TAR = gtar
 GZIP_ENV = --best
 SOURCES = $(libstdc___la_SOURCES)
 OBJECTS = $(libstdc___la_OBJECTS)
@@ -382,7 +437,7 @@ TAGS:  $(HEADERS) $(SOURCES)  $(TAGS_DEPENDENCIES) $(LISP)
 	  awk '    { files[$$0] = 1; } \
 	       END { for (i in files) print i; }'`; \
 	test -z "$(ETAGS_ARGS)$$unique$(LISP)$$tags" \
-	  || (cd $(srcdir) && etags -o $$here/TAGS $(ETAGS_ARGS) $$tags  $$unique $(LISP))
+	  || (cd $(srcdir) && etags $(ETAGS_ARGS) $$tags  $$unique $(LISP) -o $$here/TAGS)
 
 mostlyclean-tags:
 
diff --git a/libstdc++-v3/src/stl_tree.cc b/libstdc++-v3/src/stl_tree.cc
new file mode 100644
index 0000000..99f8143
--- /dev/null
+++ b/libstdc++-v3/src/stl_tree.cc
@@ -0,0 +1,365 @@
+// RB tree utilities implementation -*- C++ -*-
+
+// Copyright (C) 2003 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 2, 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.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+/*
+ *
+ * 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
+{
+  void 
+  _Rb_tree_base_iterator::_M_increment()
+  {
+    if (_M_node->_M_right != 0) 
+      {
+        _M_node = _M_node->_M_right;
+        while (_M_node->_M_left != 0)
+          _M_node = _M_node->_M_left;
+      }
+    else 
+      {
+        _Base_ptr __y = _M_node->_M_parent;
+        while (_M_node == __y->_M_right) 
+          {
+            _M_node = __y;
+            __y = __y->_M_parent;
+          }
+        if (_M_node->_M_right != __y)
+          _M_node = __y;
+      }
+  }
+
+  void 
+  _Rb_tree_base_iterator::_M_decrement()
+  {
+    if (_M_node->_M_color == _S_red 
+        && _M_node->_M_parent->_M_parent == _M_node)
+      _M_node = _M_node->_M_right;
+    else if (_M_node->_M_left != 0) 
+      {
+        _Base_ptr __y = _M_node->_M_left;
+        while (__y->_M_right != 0)
+          __y = __y->_M_right;
+        _M_node = __y;
+      }
+    else 
+      {
+        _Base_ptr __y = _M_node->_M_parent;
+        while (_M_node == __y->_M_left) 
+          {
+            _M_node = __y;
+            __y = __y->_M_parent;
+          }
+        _M_node = __y;
+      }
+  }
+
+  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_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
+  {
+    __x->_M_color = _S_red;
+
+    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;
+  }
+} // namespace std