re PR libstdc++/11504 (-Wcast-qual vs. stl_tree)

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

	PR libstdc++/11504.
	* include/bits/stl_tree.h: Replace C-style casts with C++-style
	casts.  Changes to avoid casting away constness.  Eliminate
	_Rb_tree_base_iterator class.  Change _Rb_tree_iterator to use
	initialization lists.  Move out implementation of __black_count()
	to...
        * src/stl_tree.cc: ...here and rename _Rb_tree_black_count().
        Rename_Rb_tree_base_iterator::_M_increment() to
        _Rb_tree_increment and _Rb_tree_base_iterator::_M_decrement() to
        _Rb_tree_decrement.
        * config/linker-map.gnu: Add and change symbols here.

From-SVN: r69958

4 files changed, 203 insertions, 137 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 90626cc..4dc6b15 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,17 @@
+2003-07-30  Gawain Bolton  <gp.bolton@computer.org>
+
+	PR libstdc++/11504.  
+	* include/bits/stl_tree.h: Replace C-style casts with C++-style
+	casts.  Changes to avoid casting away constness.  Eliminate
+	_Rb_tree_base_iterator class.  Change _Rb_tree_iterator to use
+	initialization lists.  Move out implementation of __black_count()
+	to...
+        * src/stl_tree.cc: ...here and rename _Rb_tree_black_count().
+        Rename_Rb_tree_base_iterator::_M_increment() to
+        _Rb_tree_increment and _Rb_tree_base_iterator::_M_decrement() to
+        _Rb_tree_decrement.
+        * config/linker-map.gnu: Add and change symbols here.
+
 2003-07-30  Jonathan Wakely  <redi@gcc.gnu.org>
 
 	* docs/html/22_locale/howto.html: Use locale::classic() instead
diff --git a/libstdc++-v3/config/linker-map.gnu b/libstdc++-v3/config/linker-map.gnu
index 4f0db8d..fa54dcf 100644
--- a/libstdc++-v3/config/linker-map.gnu
+++ b/libstdc++-v3/config/linker-map.gnu
@@ -76,9 +76,10 @@ GLIBCXX_3.4 {
     _ZSt9has_facet*;
 
     # _Rb_tree
-    _ZNSt22_Rb_tree_base_iterator12_M_decrementEv;
-    _ZNSt22_Rb_tree_base_iterator12_M_incrementEv;
+    _ZSt18_Rb_tree_decrementPSt18_Rb_tree_node_base;
+    _ZSt18_Rb_tree_incrementPSt18_Rb_tree_node_base;
     _ZSt18_Rb_tree_rebalancePSt18_Rb_tree_node_baseRS0_;
+    _ZSt20_Rb_tree_black_countPKSt18_Rb_tree_node_baseS1_;
     _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_;
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 920e591..fd81a67 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -95,6 +95,7 @@ namespace std
   struct _Rb_tree_node_base
   {
     typedef _Rb_tree_node_base* _Base_ptr;
+    typedef const _Rb_tree_node_base* _Const_Base_ptr;
     
     _Rb_tree_color 	_M_color; 
     _Base_ptr 		_M_parent;
@@ -108,12 +109,26 @@ namespace std
       return __x;
     }
 
+    static _Const_Base_ptr
+    _S_minimum(_Const_Base_ptr __x)
+    {
+      while (__x->_M_left != 0) __x = __x->_M_left;
+      return __x;
+    }
+
     static _Base_ptr 
     _S_maximum(_Base_ptr __x)
     {
       while (__x->_M_right != 0) __x = __x->_M_right;
       return __x;
     }
+
+    static _Const_Base_ptr
+    _S_maximum(_Const_Base_ptr __x)
+    {
+      while (__x->_M_right != 0) __x = __x->_M_right;
+      return __x;
+    }
   };
 
   template<typename _Val>
@@ -123,23 +138,14 @@ namespace std
       _Val _M_value_field;
     };
   
-  struct _Rb_tree_base_iterator
-  {
-    typedef _Rb_tree_node_base::_Base_ptr 	_Base_ptr;
-    typedef bidirectional_iterator_tag 		iterator_category;
-    typedef ptrdiff_t 				difference_type;
-
-    _Base_ptr _M_node;
-
-    void 
-    _M_increment();
+  _Rb_tree_node_base*
+  _Rb_tree_increment(_Rb_tree_node_base* __x);
 
-    void 
-    _M_decrement();
-  };
+  _Rb_tree_node_base*
+  _Rb_tree_decrement(_Rb_tree_node_base* __x);
 
   template<typename _Val, typename _Ref, typename _Ptr>
-    struct _Rb_tree_iterator : public _Rb_tree_base_iterator
+    struct _Rb_tree_iterator
     {
       typedef _Val value_type;
       typedef _Ref reference;
@@ -147,23 +153,36 @@ namespace std
       typedef _Rb_tree_iterator<_Val, _Val&, _Val*> iterator;
       typedef _Rb_tree_iterator<_Val, const _Val&, const _Val*> 
       const_iterator;
+      typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
+      typedef bidirectional_iterator_tag iterator_category;
+      typedef ptrdiff_t difference_type;
       typedef _Rb_tree_iterator<_Val, _Ref, _Ptr> _Self;
       typedef _Rb_tree_node<_Val>* _Link_type;
+      typedef const _Rb_tree_node<_Val>* _Const_Link_type;
       
       _Rb_tree_iterator() {}
-      _Rb_tree_iterator(_Rb_tree_node_base* __x) { _M_node = __x; }
-      _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; }
+
+      _Rb_tree_iterator(_Link_type __x)
+      : _M_node(__x) {}
+
+      _Rb_tree_iterator(_Const_Link_type __x)
+      : _M_node(const_cast<_Link_type>(__x)) {}
+
+      _Rb_tree_iterator(const iterator& __it)
+      : _M_node(__it._M_node) {}
 
       reference 
-      operator*() const { return _Link_type(_M_node)->_M_value_field; }
+      operator*() const
+      { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 
       pointer 
-      operator->() const { return &(operator*()); }
+      operator->() const
+      { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
 
       _Self& 
       operator++() 
       { 
-	_M_increment(); 
+	_M_node = _Rb_tree_increment(_M_node);
 	return *this; 
       }
 
@@ -171,20 +190,26 @@ namespace std
       operator++(int) 
       {
 	_Self __tmp = *this;
-	_M_increment();
+	_M_node = _Rb_tree_increment(_M_node);
 	return __tmp;
       }
     
       _Self& 
-      operator--() { _M_decrement(); return *this; }
+      operator--()
+      {
+	_M_node = _Rb_tree_decrement(_M_node);
+	return *this;
+      }
 
       _Self 
       operator--(int) 
       {
 	_Self __tmp = *this;
-	_M_decrement();
+	_M_node = _Rb_tree_decrement(_M_node);
 	return __tmp;
       }
+
+      _Base_ptr _M_node;
   };
 
   template<typename _Val, typename _Ref, typename _Ptr>
@@ -312,6 +337,7 @@ namespace std
       
     protected:
       typedef _Rb_tree_node_base* _Base_ptr;
+      typedef const _Rb_tree_node_base* _Const_Base_ptr;
       typedef _Rb_tree_node<_Val> _Rb_tree_node;
       
     public:
@@ -322,6 +348,7 @@ namespace std
       typedef value_type& reference;
       typedef const value_type& const_reference;
       typedef _Rb_tree_node* _Link_type;
+      typedef const _Rb_tree_node* _Const_Link_type;
       typedef size_t size_type;
       typedef ptrdiff_t difference_type;
       
@@ -348,7 +375,7 @@ namespace std
       }
       
       _Link_type 
-      _M_clone_node(_Link_type __x)
+      _M_clone_node(_Const_Link_type __x)
       {
 	_Link_type __tmp = _M_create_node(__x->_M_value_field);
 	__tmp->_M_color = __x->_M_color;
@@ -367,58 +394,75 @@ namespace std
       size_type _M_node_count; // keeps track of size of tree
       _Compare _M_key_compare;
 
-      _Link_type& 
-      _M_root() const { return (_Link_type&) this->_M_header._M_parent; }
+      _Base_ptr&
+      _M_root() { return this->_M_header._M_parent; }
 
-      _Link_type& 
-      _M_leftmost() const { return (_Link_type&) this->_M_header._M_left; }
+      _Const_Base_ptr
+      _M_root() const { return this->_M_header._M_parent; }
 
-      _Link_type& 
-      _M_rightmost() const { return (_Link_type&) this->_M_header._M_right; }
+      _Base_ptr&
+      _M_leftmost() { return this->_M_header._M_left; }
+
+      _Const_Base_ptr
+      _M_leftmost() const { return this->_M_header._M_left; }
+
+      _Base_ptr&
+      _M_rightmost() { return this->_M_header._M_right; }
+
+      _Const_Base_ptr
+      _M_rightmost() const { return this->_M_header._M_right; }
 
       _Link_type
-      _M_end() const { return (_Link_type) &this->_M_header; }
-      
-      static _Link_type& 
-      _S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); }
+      _M_begin() { return static_cast<_Link_type>(this->_M_header._M_parent); }
+
+      _Const_Link_type
+      _M_begin() const { return static_cast<_Const_Link_type>(this->_M_header._M_parent); }
 
-      static _Link_type& 
-      _S_right(_Link_type __x) { return (_Link_type&)(__x->_M_right); }
+      _Link_type
+      _M_end() { return static_cast<_Link_type>(&this->_M_header); }
 
-      static _Link_type& 
-      _S_parent(_Link_type __x) { return (_Link_type&)(__x->_M_parent); }
+      _Const_Link_type
+      _M_end() const { return static_cast<_Const_Link_type>(&this->_M_header); }
 
-      static reference 
-      _S_value(_Link_type __x) { return __x->_M_value_field; }
+      static const_reference 
+      _S_value(_Const_Link_type __x) { return __x->_M_value_field; }
 
       static const _Key& 
-      _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); }
+      _S_key(_Const_Link_type __x) { return _KeyOfValue()(_S_value(__x)); }
+
+      static _Link_type
+      _S_left(_Base_ptr __x) { return static_cast<_Link_type>(__x->_M_left); }
 
-      static _Link_type& 
-      _S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); }
+      static _Const_Link_type
+      _S_left(_Const_Base_ptr __x) { return static_cast<_Const_Link_type>(__x->_M_left); }
 
-      static _Link_type& 
-      _S_right(_Base_ptr __x) { return (_Link_type&)(__x->_M_right); }
+      static _Link_type
+      _S_right(_Base_ptr __x) { return static_cast<_Link_type>(__x->_M_right); }
 
-      static _Link_type& 
-      _S_parent(_Base_ptr __x) { return (_Link_type&)(__x->_M_parent); }
+      static _Const_Link_type
+      _S_right(_Const_Base_ptr __x) { return static_cast<_Const_Link_type>(__x->_M_right); }
 
-      static reference 
-      _S_value(_Base_ptr __x) { return ((_Link_type)__x)->_M_value_field; }
+      static const_reference
+      _S_value(_Const_Base_ptr __x) { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
 
       static const _Key& 
-      _S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x)));} 
+      _S_key(_Const_Base_ptr __x) { return _KeyOfValue()(_S_value(__x)); }
+
+      static _Base_ptr 
+      _S_minimum(_Base_ptr __x) 
+      { return _Rb_tree_node_base::_S_minimum(__x); }
 
-      static _Rb_tree_color&
-      _S_color(_Base_ptr __x) { return __x->_M_color; }
+      static _Const_Base_ptr
+      _S_minimum(_Const_Base_ptr __x)
+      { return _Rb_tree_node_base::_S_minimum(__x); }
 
-      static _Link_type 
-      _S_minimum(_Link_type __x) 
-      { return (_Link_type)  _Rb_tree_node_base::_S_minimum(__x); }
+      static _Base_ptr
+      _S_maximum(_Base_ptr __x)
+      { return _Rb_tree_node_base::_S_maximum(__x); }
 
-      static _Link_type 
-      _S_maximum(_Link_type __x)
-      { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
+      static _Const_Base_ptr
+      _S_maximum(_Const_Base_ptr __x)
+      { return _Rb_tree_node_base::_S_maximum(__x); }
 
     public:
       typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
@@ -433,7 +477,7 @@ namespace std
       _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
 
       _Link_type 
-      _M_copy(_Link_type __x, _Link_type __p);
+      _M_copy(_Const_Link_type __x, _Link_type __p);
 
       void 
       _M_erase(_Link_type __x);
@@ -460,8 +504,8 @@ namespace std
 	  _M_empty_initialize();
 	else 
 	  {
-	    _S_color(&this->_M_header) = _S_red;
-	    _M_root() = _M_copy(__x._M_root(), _M_end());
+	    this->_M_header._M_color = _S_red;
+	    _M_root() = _M_copy(__x._M_begin(), _M_end());
 	    _M_leftmost() = _S_minimum(_M_root());
 	    _M_rightmost() = _S_maximum(_M_root());
 	  }
@@ -477,7 +521,7 @@ namespace std
       void _M_empty_initialize() 
       {
 	// Used to distinguish header from __root, in iterator.operator++.
-	_S_color(&this->_M_header) = _S_red; 
+	this->_M_header._M_color = _S_red; 
 	_M_root() = 0;
 	_M_leftmost() = _M_end();
 	_M_rightmost() = _M_end();
@@ -489,16 +533,16 @@ namespace std
       key_comp() const { return _M_key_compare; }
 
       iterator 
-      begin() { return _M_leftmost(); }
+      begin() { return static_cast<_Link_type>(this->_M_header._M_left); }
 
       const_iterator 
-      begin() const { return _M_leftmost(); }
+      begin() const { return static_cast<_Const_Link_type>(this->_M_header._M_left); }
 
       iterator 
-      end() { return &this->_M_header; }
+      end() { return static_cast<_Link_type>(&this->_M_header); }
 
       const_iterator
-      end() const { return const_cast<_Base_ptr>(&this->_M_header); }
+      end() const { return static_cast<_Const_Link_type>(&this->_M_header); }
 
       reverse_iterator 
       rbegin() { return reverse_iterator(end()); }
@@ -562,7 +606,7 @@ namespace std
       {
 	if (_M_node_count != 0) 
 	  {
-	    _M_erase(_M_root());
+	    _M_erase(_M_begin());
 	    _M_leftmost() = _M_end();
 	    _M_root() = 0;
 	    _M_rightmost() = _M_end();
@@ -678,7 +722,7 @@ namespace std
 	    }
 	  else 
 	    {
-	      _M_root() = _M_copy(__x._M_root(), _M_end());
+	      _M_root() = _M_copy(__x._M_begin(), _M_end());
 	      _M_leftmost() = _S_minimum(_M_root());
 	      _M_rightmost() = _S_maximum(_M_root());
 	      _M_node_count = __x._M_node_count;
@@ -693,15 +737,15 @@ namespace std
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     _M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Val& __v)
     {
-      _Link_type __x = (_Link_type) __x_;
-      _Link_type __y = (_Link_type) __y_;
+      _Link_type __x = static_cast<_Link_type>(__x_);
+      _Link_type __y = static_cast<_Link_type>(__y_);
       _Link_type __z;
       
       if (__y == &this->_M_header || __x != 0 || 
 	  _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) 
 	{
 	  __z = _M_create_node(__v);
-	  _S_left(__y) = __z;               // also makes _M_leftmost() = __z 
+	  __y->_M_left = __z;               // also makes _M_leftmost() = __z
 	  //    when __y == &_M_header
 	  if (__y == &this->_M_header) 
 	    {
@@ -714,14 +758,14 @@ namespace std
       else 
 	{
 	  __z = _M_create_node(__v);
-	  _S_right(__y) = __z;
+	  __y->_M_right = __z;
 	  // Maintain _M_rightmost() pointing to max node.
 	  if (__y == _M_rightmost())
 	    _M_rightmost() = __z; 
 	}
-      _S_parent(__z) = __y;
-      _S_left(__z) = 0;
-      _S_right(__z) = 0;
+      __z->_M_parent = __y;
+      __z->_M_left = 0;
+      __z->_M_right = 0;
       _Rb_tree_rebalance(__z, this->_M_header._M_parent);
       ++_M_node_count;
       return iterator(__z);
@@ -733,8 +777,8 @@ namespace std
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     insert_equal(const _Val& __v)
     {
+      _Link_type __x = _M_begin();
       _Link_type __y = _M_end();
-      _Link_type __x = _M_root();
       while (__x != 0) 
 	{
 	  __y = __x;
@@ -796,8 +840,8 @@ namespace std
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     insert_unique(const _Val& __v)
     {
+      _Link_type __x = _M_begin();
       _Link_type __y = _M_end();
-      _Link_type __x = _M_root();
       bool __comp = true;
       while (__x != 0) 
 	{
@@ -930,8 +974,8 @@ namespace std
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
     {
       _Link_type __y = 
-	(_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
-						  this->_M_header);
+	static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
+							     this->_M_header));
       destroy_node(__y);
       --_M_node_count;
     }
@@ -951,7 +995,7 @@ namespace std
            typename _Compare, typename _Alloc>
     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type 
     _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>::
-    _M_copy(_Link_type __x, _Link_type __p)
+    _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);
@@ -1025,8 +1069,8 @@ namespace std
     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
     {
-      _Link_type __y = _M_end(); // Last node which is not less than __k. 
-      _Link_type __x = _M_root(); // Current node. 
+      _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_key_compare(_S_key(__x), __k))
@@ -1045,8 +1089,8 @@ namespace std
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     find(const _Key& __k) const
     {
-      _Link_type __y = _M_end(); // Last node which is not less than __k. 
-      _Link_type __x = _M_root(); // Current node. 
+      _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) 
        {
@@ -1077,8 +1121,8 @@ namespace std
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     lower_bound(const _Key& __k)
     {
-      _Link_type __y = _M_end(); // Last node which is not less than __k
-      _Link_type __x = _M_root(); // Current node.
+      _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_key_compare(_S_key(__x), __k))
@@ -1095,8 +1139,8 @@ namespace std
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     lower_bound(const _Key& __k) const
     {
-      _Link_type __y = _M_end(); // Last node which is not less than __k.
-      _Link_type __x = _M_root(); // Current node.
+      _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_key_compare(_S_key(__x), __k))
@@ -1113,8 +1157,8 @@ namespace std
     _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.
-      _Link_type __x = _M_root(); // Current node.
       
       while (__x != 0) 
 	if (_M_key_compare(__k, _S_key(__x)))
@@ -1131,8 +1175,8 @@ namespace std
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     upper_bound(const _Key& __k) const
     {
-      _Link_type __y = _M_end(); // Last node which is greater than __k.
-      _Link_type __x = _M_root(); // Current node.
+      _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_key_compare(__k, _S_key(__x)))
@@ -1164,23 +1208,9 @@ namespace std
 					       upper_bound(__k));
   }
 
-  inline int
-  __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
-  {
-    if (__node == 0)
-      return 0;
-    int __sum = 0;
-    do 
-      {
-	if (__node->_M_color == _S_black) 
-	  ++__sum;
-	if (__node == __root) 
-	  break;
-	__node = __node->_M_parent;
-      } 
-    while (1);
-    return __sum;
-  }
+  unsigned int
+  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
+                       const _Rb_tree_node_base* __root);
 
   template<typename _Key, typename _Val, typename _KeyOfValue, 
            typename _Compare, typename _Alloc>
@@ -1192,12 +1222,12 @@ namespace std
 	this->_M_header._M_left == &this->_M_header &&
 	this->_M_header._M_right == &this->_M_header;
   
-    int __len = __black_count(_M_leftmost(), _M_root());
+    unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
     for (const_iterator __it = begin(); __it != end(); ++__it) 
       {
-	_Link_type __x = (_Link_type) __it._M_node;
-	_Link_type __L = _S_left(__x);
-	_Link_type __R = _S_right(__x);
+	_Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
+	_Const_Link_type __L = _S_left(__x);
+	_Const_Link_type __R = _S_right(__x);
 	
 	if (__x->_M_color == _S_red)
 	  if ((__L && __L->_M_color == _S_red) 
@@ -1209,7 +1239,7 @@ namespace std
 	if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
 	  return false;
 
-	if (!__L && !__R && __black_count(__x, _M_root()) != __len)
+	if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
 	  return false;
       }
     
diff --git a/libstdc++-v3/src/stl_tree.cc b/libstdc++-v3/src/stl_tree.cc
index 99f8143..eac141f 100644
--- a/libstdc++-v3/src/stl_tree.cc
+++ b/libstdc++-v3/src/stl_tree.cc
@@ -59,51 +59,53 @@
 
 namespace std
 {
-  void 
-  _Rb_tree_base_iterator::_M_increment()
+  _Rb_tree_node_base*
+  _Rb_tree_increment(_Rb_tree_node_base* __x)
   {
-    if (_M_node->_M_right != 0) 
+    if (__x->_M_right != 0) 
       {
-        _M_node = _M_node->_M_right;
-        while (_M_node->_M_left != 0)
-          _M_node = _M_node->_M_left;
+        __x = __x->_M_right;
+        while (__x->_M_left != 0)
+          __x = __x->_M_left;
       }
     else 
       {
-        _Base_ptr __y = _M_node->_M_parent;
-        while (_M_node == __y->_M_right) 
+        _Rb_tree_node_base* __y = __x->_M_parent;
+        while (__x == __y->_M_right) 
           {
-            _M_node = __y;
+            __x = __y;
             __y = __y->_M_parent;
           }
-        if (_M_node->_M_right != __y)
-          _M_node = __y;
+        if (__x->_M_right != __y)
+          __x = __y;
       }
+    return __x;
   }
 
-  void 
-  _Rb_tree_base_iterator::_M_decrement()
+  _Rb_tree_node_base*
+  _Rb_tree_decrement(_Rb_tree_node_base* __x)
   {
-    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) 
+    if (__x->_M_color == _S_red 
+        && __x->_M_parent->_M_parent == __x)
+      __x = __x->_M_right;
+    else if (__x->_M_left != 0) 
       {
-        _Base_ptr __y = _M_node->_M_left;
+        _Rb_tree_node_base* __y = __x->_M_left;
         while (__y->_M_right != 0)
           __y = __y->_M_right;
-        _M_node = __y;
+        __x = __y;
       }
     else 
       {
-        _Base_ptr __y = _M_node->_M_parent;
-        while (_M_node == __y->_M_left) 
+        _Rb_tree_node_base* __y = __x->_M_parent;
+        while (__x == __y->_M_left) 
           {
-            _M_node = __y;
+            __x = __y;
             __y = __y->_M_parent;
           }
-        _M_node = __y;
+        __x = __y;
       }
+    return __x;
   }
 
   void 
@@ -362,4 +364,23 @@ namespace std
       }
     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;
+  }
 } // namespace std