[multiple changes]

2006-11-25  Paolo Carlini  <pcarlini@suse.de>

	PR libstdc++/29385 (partial)
	* include/bits/stl_tree.h (_Rb_tree<>::destroy_node): Uglify.
	(_M_erase, erase(iterator), erase(const_iterator)): Adjust

2006-11-25  Paolo Carlini  <pcarlini@suse.de>

	PR libstdc++/29385 (partial)
	* include/bits/stl_tree.h (_Rb_tree<>::_M_lower_bound(_Const_Link_type,
	_Const_Link_type, const _Key&), _M_upper_bound(_Const_Link_type,
	_Const_Link_type, const _Key&)): Add.
	(lower_bound(const key_type&), upper_bound(const key_type&),
	find(const key_type&)): Call the latter.

2006-11-25  Gawain Bolton  <gp.bolton@computer.org>

	PR libstdc++/29385 (partial)
	* include/bits/stl_tree.h (_Rb_tree_rotate_left,
	_Rb_tree_rotate_right): Do not declare.
	(_Rb_tree<>::_M_insert(_Base_ptr, _Base_ptr, const value_type&),
	_M_insert(_Const_Base_ptr, _Const_Base_ptr, const value_type&),
	_M_insert_unique(iterator, const value_type&),
	_M_insert_unique(const_iterator, const value_type&),
	_M_insert_equal(iterator, const value_type&),
	_M_insert_equal(const_iterator, const value_type&)):
	Remove.
	(_Rb_tree<>::_M_insert_(_Const_Base_ptr, _Const_Base_ptr,
	const value_type&), _M_insert_unique_(const_iterator,
	const value_type&), _M_insert_equal_(const_iterator,
	const value_type&)): Add, adjust all callers.
	* include/bits/stl_map.h (map<>::insert(iterator, const value_type&)):
	Adjust.
	* include/bits/stl_set.h (set<>::insert(iterator, const value_type&)):
	Likewise.
	* include/bits/stl_multimap.h (multimap<>::insert(iterator,
	const value_type&)): Likewise.
	* include/bits/stl_multiset.h (multiset<>::insert(iterator,
	const value_type&)): Likewise.

From-SVN: r119190

6 files changed, 199 insertions, 353 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index dde783a..2566535 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,43 @@
+2006-11-25  Paolo Carlini  <pcarlini@suse.de>
+
+	PR libstdc++/29385 (partial)
+	* include/bits/stl_tree.h (_Rb_tree<>::destroy_node): Uglify.
+	(_M_erase, erase(iterator), erase(const_iterator)): Adjust
+
+2006-11-25  Paolo Carlini  <pcarlini@suse.de>
+
+	PR libstdc++/29385 (partial)
+	* include/bits/stl_tree.h (_Rb_tree<>::_M_lower_bound(_Const_Link_type,
+	_Const_Link_type, const _Key&), _M_upper_bound(_Const_Link_type,
+	_Const_Link_type, const _Key&)): Add.
+	(lower_bound(const key_type&), upper_bound(const key_type&),
+	find(const key_type&)): Call the latter.
+
+2006-11-25  Gawain Bolton  <gp.bolton@computer.org>
+
+	PR libstdc++/29385 (partial)
+	* include/bits/stl_tree.h (_Rb_tree_rotate_left,
+	_Rb_tree_rotate_right): Do not declare.
+	(_Rb_tree<>::_M_insert(_Base_ptr, _Base_ptr, const value_type&),
+	_M_insert(_Const_Base_ptr, _Const_Base_ptr, const value_type&),
+	_M_insert_unique(iterator, const value_type&),
+	_M_insert_unique(const_iterator, const value_type&),
+	_M_insert_equal(iterator, const value_type&),
+	_M_insert_equal(const_iterator, const value_type&)):
+	Remove.
+	(_Rb_tree<>::_M_insert_(_Const_Base_ptr, _Const_Base_ptr,
+	const value_type&), _M_insert_unique_(const_iterator,
+	const value_type&), _M_insert_equal_(const_iterator,
+	const value_type&)): Add, adjust all callers.
+	* include/bits/stl_map.h (map<>::insert(iterator, const value_type&)):
+	Adjust.
+	* include/bits/stl_set.h (set<>::insert(iterator, const value_type&)):
+	Likewise.
+	* include/bits/stl_multimap.h (multimap<>::insert(iterator,
+	const value_type&)): Likewise.
+	* include/bits/stl_multiset.h (multiset<>::insert(iterator,
+	const value_type&)): Likewise.
+
 2006-11-22  Antony King <anthony.king@st.com>
             J"orn Rennecke <joern.rennecke@st.com>
 
diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index 6dc53e9..d04b376 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -423,7 +423,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
        */
       iterator
       insert(iterator position, const value_type& __x)
-      { return _M_t._M_insert_unique(position, __x); }
+      { return _M_t._M_insert_unique_(position, __x); }
 
       /**
        *  @brief Template function that attemps to insert a range of elements.
diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
index b11b6e4..554035a 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -361,7 +361,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
        */
       iterator
       insert(iterator __position, const value_type& __x)
-      { return _M_t._M_insert_equal(__position, __x); }
+      { return _M_t._M_insert_equal_(__position, __x); }
 
       /**
        *  @brief A template function that attemps to insert a range of elements.
diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
index 8c499c3..3979cd6 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -316,7 +316,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
        */
       iterator
       insert(iterator __position, const value_type& __x)
-      { return _M_t._M_insert_equal(__position, __x); }
+      { return _M_t._M_insert_equal_(__position, __x); }
 
       /**
        *  @brief A template function that attemps to insert a range of elements.
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
index b61106a..6ee8526 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -329,7 +329,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
        */
       iterator
       insert(iterator __position, const value_type& __x)
-      { return _M_t._M_insert_unique(__position, __x); }
+      { return _M_t._M_insert_unique_(__position, __x); }
 
       /**
        *  @brief A template function that attemps to insert a range of elements.
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 96b7a52..c4dba4f 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -306,14 +306,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     { return __x._M_node != __y._M_node; }
 
   void
-  _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
-                       _Rb_tree_node_base*& __root);
-
-  void
-  _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
-                        _Rb_tree_node_base*& __root);
-
-  void
   _Rb_tree_insert_and_rebalance(const bool __insert_left,
                                 _Rb_tree_node_base* __x,
                                 _Rb_tree_node_base* __p,
@@ -395,7 +387,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       }
 
       void
-      destroy_node(_Link_type __p)
+      _M_destroy_node(_Link_type __p)
       {
 	get_allocator().destroy(&__p->_M_value_field);
 	_M_put_node(__p);
@@ -546,16 +538,16 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
     private:
       iterator
-      _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
+      _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
+		 const value_type& __v);
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // 233. Insertion hints in associative containers.
       iterator
       _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 
-      const_iterator
-      _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,
-		const value_type& __v);
+      iterator
+      _M_insert_equal_lower(const value_type& __x);
 
       _Link_type
       _M_copy(_Const_Link_type __x, _Link_type __p);
@@ -563,6 +555,14 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       void
       _M_erase(_Link_type __x);
 
+      iterator
+      _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
+		     const _Key& __k) const;
+
+      iterator
+      _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
+		     const _Key& __k) const;
+
     public:
       // allocation/deallocation
       _Rb_tree()
@@ -662,22 +662,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       iterator
       _M_insert_equal(const value_type& __x);
 
-      // _GLIBCXX_RESOLVE_LIB_DEFECTS
-      // 233. Insertion hints in associative containers.
-      iterator
-      _M_insert_equal_lower(const value_type& __x);
-
       iterator
-      _M_insert_unique(iterator __position, const value_type& __x);
-
-      const_iterator
-      _M_insert_unique(const_iterator __position, const value_type& __x);
+      _M_insert_unique_(const_iterator __position, const value_type& __x);
 
       iterator
-      _M_insert_equal(iterator __position, const value_type& __x);
-
-      const_iterator
-      _M_insert_equal(const_iterator __position, const value_type& __x);
+      _M_insert_equal_(const_iterator __position, const value_type& __x);
 
       template<typename _InputIterator>
         void
@@ -717,31 +706,35 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
       // Set operations.
       iterator
-      find(const key_type& __x);
+      find(const key_type& __k);
 
       const_iterator
-      find(const key_type& __x) const;
+      find(const key_type& __k) const;
 
       size_type
-      count(const key_type& __x) const;
+      count(const key_type& __k) const;
 
       iterator
-      lower_bound(const key_type& __x);
+      lower_bound(const key_type& __k)
+      { return iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); }
 
       const_iterator
-      lower_bound(const key_type& __x) const;
+      lower_bound(const key_type& __k) const
+      { return const_iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); }
 
       iterator
-      upper_bound(const key_type& __x);
+      upper_bound(const key_type& __k)
+      { return iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); }
 
       const_iterator
-      upper_bound(const key_type& __x) const;
+      upper_bound(const key_type& __k) const
+      { return const_iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); }
 
-      pair<iterator,iterator>
-      equal_range(const key_type& __x);
+      pair<iterator, iterator>
+      equal_range(const key_type& __k);
 
       pair<const_iterator, const_iterator>
-      equal_range(const key_type& __x) const;
+      equal_range(const key_type& __k) const;
 
       // Debugging.
       bool
@@ -829,7 +822,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
            typename _Compare, typename _Alloc>
     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
+    _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
     {
       bool __insert_left = (__x != 0 || __p == _M_end()
 			    || _M_impl._M_key_compare(_KeyOfValue()(__v), 
@@ -837,7 +830,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
       _Link_type __z = _M_create_node(__v);
 
-      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
+      _Rb_tree_insert_and_rebalance(__insert_left, __z,
+				    const_cast<_Base_ptr>(__p),  
 				    this->_M_impl._M_header);
       ++_M_impl._M_node_count;
       return iterator(__z);
@@ -863,55 +857,101 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
+    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
+    _M_insert_equal_lower(const _Val& __v)
     {
-      bool __insert_left = (__x != 0 || __p == _M_end()
-			    || _M_impl._M_key_compare(_KeyOfValue()(__v), 
-						      _S_key(__p)));
+      _Link_type __x = _M_begin();
+      _Link_type __y = _M_end();
+      while (__x != 0)
+	{
+	  __y = __x;
+	  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
+	        _S_left(__x) : _S_right(__x);
+	}
+      return _M_insert_lower(__x, __y, __v);
+    }
 
-      _Link_type __z = _M_create_node(__v);
+  template<typename _Key, typename _Val, typename _KoV,
+           typename _Compare, typename _Alloc>
+    typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
+    _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
+    _M_copy(_Const_Link_type __x, _Link_type __p)
+    {
+      // Structural copy.  __x and __p must be non-null.
+      _Link_type __top = _M_clone_node(__x);
+      __top->_M_parent = __p;
 
-      _Rb_tree_insert_and_rebalance(__insert_left, __z,
-				    const_cast<_Base_ptr>(__p),  
-				    this->_M_impl._M_header);
-      ++_M_impl._M_node_count;
-      return const_iterator(__z);
+      try
+	{
+	  if (__x->_M_right)
+	    __top->_M_right = _M_copy(_S_right(__x), __top);
+	  __p = __top;
+	  __x = _S_left(__x);
+
+	  while (__x != 0)
+	    {
+	      _Link_type __y = _M_clone_node(__x);
+	      __p->_M_left = __y;
+	      __y->_M_parent = __p;
+	      if (__x->_M_right)
+		__y->_M_right = _M_copy(_S_right(__x), __y);
+	      __p = __y;
+	      __x = _S_left(__x);
+	    }
+	}
+      catch(...)
+	{
+	  _M_erase(__top);
+	  __throw_exception_again;
+	}
+      return __top;
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    void
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_insert_equal(const _Val& __v)
+    _M_erase(_Link_type __x)
     {
-      _Link_type __x = _M_begin();
-      _Link_type __y = _M_end();
+      // Erase without rebalancing.
       while (__x != 0)
 	{
-	  __y = __x;
-	  __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
-	        _S_left(__x) : _S_right(__x);
+	  _M_erase(_S_right(__x));
+	  _Link_type __y = _S_left(__x);
+	  _M_destroy_node(__x);
+	  __x = __y;
 	}
-      return _M_insert(__x, __y, __v);
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_insert_equal_lower(const _Val& __v)
+    _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
+		   const _Key& __k) const
     {
-      _Link_type __x = _M_begin();
-      _Link_type __y = _M_end();
       while (__x != 0)
-	{
-	  __y = __x;
-	  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
-	        _S_left(__x) : _S_right(__x);
-	}
-      return _M_insert_lower(__x, __y, __v);
+	if (!_M_impl._M_key_compare(_S_key(__x), __k))
+	  __y = __x, __x = _S_left(__x);
+	else
+	  __x = _S_right(__x);
+      return iterator(const_cast<_Link_type>(__y));
+    }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
+		   const _Key& __k) const
+    {
+      while (__x != 0)
+	if (_M_impl._M_key_compare(__k, _S_key(__x)))
+	  __y = __x, __x = _S_left(__x);
+	else
+	  __x = _S_right(__x);
+      return iterator(const_cast<_Link_type>(__y));
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -983,11 +1023,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       iterator __j = iterator(__y);
       if (__comp)
 	if (__j == begin())
-	  return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
+	  return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
 	else
 	  --__j;
       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
-	return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
+	return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
       return pair<iterator, bool>(__j, false);
     }
 
@@ -995,64 +1035,24 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
            typename _Compare, typename _Alloc>
     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_insert_unique(iterator __position, const _Val& __v)
+    _M_insert_equal(const _Val& __v)
     {
-      // end()
-      if (__position._M_node == _M_end())
-	{
-	  if (size() > 0
-	      && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
-					_KeyOfValue()(__v)))
-	    return _M_insert(0, _M_rightmost(), __v);
-	  else
-	    return _M_insert_unique(__v).first;
-	}
-      else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
-				      _S_key(__position._M_node)))
-	{
-	  // First, try before...
-	  iterator __before = __position;
-	  if (__position._M_node == _M_leftmost()) // begin()
-	    return _M_insert(_M_leftmost(), _M_leftmost(), __v);
-	  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 
-					  _KeyOfValue()(__v)))
-	    {
-	      if (_S_right(__before._M_node) == 0)
-		return _M_insert(0, __before._M_node, __v);
-	      else
-		return _M_insert(__position._M_node,
-				 __position._M_node, __v);
-	    }
-	  else
-	    return _M_insert_unique(__v).first;
-	}
-      else if (_M_impl._M_key_compare(_S_key(__position._M_node),
-				      _KeyOfValue()(__v)))
+      _Link_type __x = _M_begin();
+      _Link_type __y = _M_end();
+      while (__x != 0)
 	{
-	  // ... then try after.
-	  iterator __after = __position;
-	  if (__position._M_node == _M_rightmost())
-	    return _M_insert(0, _M_rightmost(), __v);
-	  else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
-					  _S_key((++__after)._M_node)))
-	    {
-	      if (_S_right(__position._M_node) == 0)
-		return _M_insert(0, __position._M_node, __v);
-	      else
-		return _M_insert(__after._M_node, __after._M_node, __v);
-	    }
-	  else
-	    return _M_insert_unique(__v).first;
+	  __y = __x;
+	  __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
+	        _S_left(__x) : _S_right(__x);
 	}
-      else
-	return __position; // Equivalent keys.
+      return _M_insert_(__x, __y, __v);
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
+    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_insert_unique(const_iterator __position, const _Val& __v)
+    _M_insert_unique_(const_iterator __position, const _Val& __v)
     {
       // end()
       if (__position._M_node == _M_end())
@@ -1060,9 +1060,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	  if (size() > 0
 	      && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
 					_KeyOfValue()(__v)))
-	    return _M_insert(0, _M_rightmost(), __v);
+	    return _M_insert_(0, _M_rightmost(), __v);
 	  else
-	    return const_iterator(_M_insert_unique(__v).first);
+	    return _M_insert_unique(__v).first;
 	}
       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
 				      _S_key(__position._M_node)))
@@ -1070,18 +1070,18 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	  // First, try before...
 	  const_iterator __before = __position;
 	  if (__position._M_node == _M_leftmost()) // begin()
-	    return _M_insert(_M_leftmost(), _M_leftmost(), __v);
+	    return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
 	  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 
 					  _KeyOfValue()(__v)))
 	    {
 	      if (_S_right(__before._M_node) == 0)
-		return _M_insert(0, __before._M_node, __v);
+		return _M_insert_(0, __before._M_node, __v);
 	      else
-		return _M_insert(__position._M_node,
-				 __position._M_node, __v);
+		return _M_insert_(__position._M_node,
+				  __position._M_node, __v);
 	    }
 	  else
-	    return const_iterator(_M_insert_unique(__v).first);
+	    return _M_insert_unique(__v).first;
 	}
       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
 				      _KeyOfValue()(__v)))
@@ -1089,27 +1089,29 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	  // ... then try after.
 	  const_iterator __after = __position;
 	  if (__position._M_node == _M_rightmost())
-	    return _M_insert(0, _M_rightmost(), __v);
+	    return _M_insert_(0, _M_rightmost(), __v);
 	  else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
 					  _S_key((++__after)._M_node)))
 	    {
 	      if (_S_right(__position._M_node) == 0)
-		return _M_insert(0, __position._M_node, __v);
+		return _M_insert_(0, __position._M_node, __v);
 	      else
-		return _M_insert(__after._M_node, __after._M_node, __v);
+		return _M_insert_(__after._M_node, __after._M_node, __v);
 	    }
 	  else
-	    return const_iterator(_M_insert_unique(__v).first);
+	    return _M_insert_unique(__v).first;
 	}
       else
-	return __position; // Equivalent keys.
+	// Equivalent keys.
+	return iterator(static_cast<_Link_type>
+			(const_cast<_Base_ptr>(__position._M_node)));
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_insert_equal(iterator __position, const _Val& __v)
+    _M_insert_equal_(const_iterator __position, const _Val& __v)
     {
       // end()
       if (__position._M_node == _M_end())
@@ -1117,7 +1119,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	  if (size() > 0
 	      && !_M_impl._M_key_compare(_KeyOfValue()(__v),
 					 _S_key(_M_rightmost())))
-	    return _M_insert(0, _M_rightmost(), __v);
+	    return _M_insert_(0, _M_rightmost(), __v);
 	  else
 	    return _M_insert_equal(__v);
 	}
@@ -1125,91 +1127,37 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 				       _KeyOfValue()(__v)))
 	{
 	  // First, try before...
-	  iterator __before = __position;
-	  if (__position._M_node == _M_leftmost()) // begin()
-	    return _M_insert(_M_leftmost(), _M_leftmost(), __v);
-	  else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
-					   _S_key((--__before)._M_node)))
-	    {
-	      if (_S_right(__before._M_node) == 0)
-		return _M_insert(0, __before._M_node, __v);
-	      else
-		return _M_insert(__position._M_node,
-				 __position._M_node, __v);
-	    }
-	  else
-	    return _M_insert_equal(__v);
-	}
-      else
-	{
-	  // ... then try after.  
-	  iterator __after = __position;
-	  if (__position._M_node == _M_rightmost())
-	    return _M_insert(0, _M_rightmost(), __v);
-	  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
-					   _KeyOfValue()(__v)))
-	    {
-	      if (_S_right(__position._M_node) == 0)
-		return _M_insert(0, __position._M_node, __v);
-	      else
-		return _M_insert(__after._M_node, __after._M_node, __v);
-	    }
-	  else
-	    return _M_insert_equal_lower(__v);
-	}
-    }
-
-  template<typename _Key, typename _Val, typename _KeyOfValue,
-           typename _Compare, typename _Alloc>
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_insert_equal(const_iterator __position, const _Val& __v)
-    {
-      // end()
-      if (__position._M_node == _M_end())
-	{
-	  if (size() > 0
-	      && !_M_impl._M_key_compare(_KeyOfValue()(__v),
-					 _S_key(_M_rightmost())))
-	    return _M_insert(0, _M_rightmost(), __v);
-	  else
-	    return const_iterator(_M_insert_equal(__v));
-	}
-      else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
-				       _KeyOfValue()(__v)))
-	{
-	  // First, try before...
 	  const_iterator __before = __position;
 	  if (__position._M_node == _M_leftmost()) // begin()
-	    return _M_insert(_M_leftmost(), _M_leftmost(), __v);
+	    return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
 	  else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
 					   _S_key((--__before)._M_node)))
 	    {
 	      if (_S_right(__before._M_node) == 0)
-		return _M_insert(0, __before._M_node, __v);
+		return _M_insert_(0, __before._M_node, __v);
 	      else
-		return _M_insert(__position._M_node,
-				 __position._M_node, __v);
+		return _M_insert_(__position._M_node,
+				  __position._M_node, __v);
 	    }
 	  else
-	    return const_iterator(_M_insert_equal(__v));
+	    return _M_insert_equal(__v);
 	}
       else
 	{
 	  // ... then try after.  
 	  const_iterator __after = __position;
 	  if (__position._M_node == _M_rightmost())
-	    return _M_insert(0, _M_rightmost(), __v);
+	    return _M_insert_(0, _M_rightmost(), __v);
 	  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
 					   _KeyOfValue()(__v)))
 	    {
 	      if (_S_right(__position._M_node) == 0)
-		return _M_insert(0, __position._M_node, __v);
+		return _M_insert_(0, __position._M_node, __v);
 	      else
-		return _M_insert(__after._M_node, __after._M_node, __v);
+		return _M_insert_(__after._M_node, __after._M_node, __v);
 	    }
 	  else
-	    return const_iterator(_M_insert_equal_lower(__v));
+	    return _M_insert_equal_lower(__v);
 	}
     }
 
@@ -1218,10 +1166,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     template<class _II>
       void
       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
-      _M_insert_equal(_II __first, _II __last)
+      _M_insert_unique(_II __first, _II __last)
       {
 	for (; __first != __last; ++__first)
-	  _M_insert_equal(end(), *__first);
+	  _M_insert_unique_(end(), *__first);
       }
 
   template<typename _Key, typename _Val, typename _KoV,
@@ -1229,10 +1177,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     template<class _II>
       void
       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
-      _M_insert_unique(_II __first, _II __last)
+      _M_insert_equal(_II __first, _II __last)
       {
 	for (; __first != __last; ++__first)
-	  _M_insert_unique(end(), *__first);
+	  _M_insert_equal_(end(), *__first);
       }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1245,7 +1193,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
 				(__position._M_node,
 				 this->_M_impl._M_header));
-      destroy_node(__y);
+      _M_destroy_node(__y);
       --_M_impl._M_node_count;
     }
 
@@ -1259,7 +1207,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
 				(const_cast<_Base_ptr>(__position._M_node),
 				 this->_M_impl._M_header));
-      destroy_node(__y);
+      _M_destroy_node(__y);
       --_M_impl._M_node_count;
     }
 
@@ -1275,58 +1223,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       return __old_size - size();
     }
 
-  template<typename _Key, typename _Val, typename _KoV,
-           typename _Compare, typename _Alloc>
-    typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
-    _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
-    _M_copy(_Const_Link_type __x, _Link_type __p)
-    {
-      // Structural copy.  __x and __p must be non-null.
-      _Link_type __top = _M_clone_node(__x);
-      __top->_M_parent = __p;
-
-      try
-	{
-	  if (__x->_M_right)
-	    __top->_M_right = _M_copy(_S_right(__x), __top);
-	  __p = __top;
-	  __x = _S_left(__x);
-
-	  while (__x != 0)
-	    {
-	      _Link_type __y = _M_clone_node(__x);
-	      __p->_M_left = __y;
-	      __y->_M_parent = __p;
-	      if (__x->_M_right)
-		__y->_M_right = _M_copy(_S_right(__x), __y);
-	      __p = __y;
-	      __x = _S_left(__x);
-	    }
-	}
-      catch(...)
-	{
-	  _M_erase(__top);
-	  __throw_exception_again;
-	}
-      return __top;
-    }
-
-  template<typename _Key, typename _Val, typename _KeyOfValue,
-           typename _Compare, typename _Alloc>
-    void
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_erase(_Link_type __x)
-    {
-      // Erase without rebalancing.
-      while (__x != 0)
-	{
-	  _M_erase(_S_right(__x));
-	  _Link_type __y = _S_left(__x);
-	  destroy_node(__x);
-	  __x = __y;
-	}
-    }
-
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
     void
@@ -1369,16 +1265,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     find(const _Key& __k)
     {
-      _Link_type __x = _M_begin(); // Current node.
-      _Link_type __y = _M_end(); // Last node which is not less than __k.
-
-      while (__x != 0)
-	if (!_M_impl._M_key_compare(_S_key(__x), __k))
-	  __y = __x, __x = _S_left(__x);
-	else
-	  __x = _S_right(__x);
-
-      iterator __j = iterator(__y);
+      iterator __j = iterator(_M_lower_bound(_M_begin(), _M_end(), __k));
       return (__j == end()
 	      || _M_impl._M_key_compare(__k,
 					_S_key(__j._M_node))) ? end() : __j;
@@ -1390,20 +1277,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     find(const _Key& __k) const
     {
-      _Const_Link_type __x = _M_begin(); // Current node.
-      _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
-
-     while (__x != 0)
-       {
-	 if (!_M_impl._M_key_compare(_S_key(__x), __k))
-	   __y = __x, __x = _S_left(__x);
-	 else
-	   __x = _S_right(__x);
-       }
-     const_iterator __j = const_iterator(__y);
-     return (__j == end()
-	     || _M_impl._M_key_compare(__k, 
-				       _S_key(__j._M_node))) ? end() : __j;
+      const_iterator __j = const_iterator(_M_lower_bound(_M_begin(),
+							 _M_end(), __k));
+      return (__j == end()
+	      || _M_impl._M_key_compare(__k, 
+					_S_key(__j._M_node))) ? end() : __j;
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1419,78 +1297,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    lower_bound(const _Key& __k)
-    {
-      _Link_type __x = _M_begin(); // Current node.
-      _Link_type __y = _M_end(); // Last node which is not less than __k.
-
-      while (__x != 0)
-	if (!_M_impl._M_key_compare(_S_key(__x), __k))
-	  __y = __x, __x = _S_left(__x);
-	else
-	  __x = _S_right(__x);
-
-      return iterator(__y);
-    }
-
-  template<typename _Key, typename _Val, typename _KeyOfValue,
-           typename _Compare, typename _Alloc>
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    lower_bound(const _Key& __k) const
-    {
-      _Const_Link_type __x = _M_begin(); // Current node.
-      _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
-
-      while (__x != 0)
-	if (!_M_impl._M_key_compare(_S_key(__x), __k))
-	  __y = __x, __x = _S_left(__x);
-	else
-	  __x = _S_right(__x);
-
-      return const_iterator(__y);
-    }
-
-  template<typename _Key, typename _Val, typename _KeyOfValue,
-           typename _Compare, typename _Alloc>
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    upper_bound(const _Key& __k)
-    {
-      _Link_type __x = _M_begin(); // Current node.
-      _Link_type __y = _M_end(); // Last node which is greater than __k.
-
-      while (__x != 0)
-	if (_M_impl._M_key_compare(__k, _S_key(__x)))
-	  __y = __x, __x = _S_left(__x);
-	else
-	  __x = _S_right(__x);
-
-      return iterator(__y);
-    }
-
-  template<typename _Key, typename _Val, typename _KeyOfValue,
-           typename _Compare, typename _Alloc>
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    upper_bound(const _Key& __k) const
-    {
-      _Const_Link_type __x = _M_begin(); // Current node.
-      _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
-
-      while (__x != 0)
-	if (_M_impl._M_key_compare(__k, _S_key(__x)))
-	  __y = __x, __x = _S_left(__x);
-	else
-	  __x = _S_right(__x);
-
-      return const_iterator(__y);
-    }
-
-  template<typename _Key, typename _Val, typename _KeyOfValue,
-           typename _Compare, typename _Alloc>
     inline
     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
 			   _Compare, _Alloc>::iterator,