This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Updated [Patch]: PR libstdc++/11504 + constness and casting cleanup


Ok, here's to hoping there is some truth in the expression "third time lucky".

This patch is an update of the one posted here:
  http://gcc.gnu.org/ml/libstdc++/2003-07/msg00477.html

The only change made was to ensure that the new typedefs follow the required naming scheme as pointed out by Phil Edwards here:
http://gcc.gnu.org/ml/libstdc++/2003-07/msg00481.html


Here's the suggested change log entry, again adapted following Phil's comments given here:
http://gcc.gnu.org/ml/libstdc++/2003-07/msg00480.html


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

       * include/bits/stl_tree.h: Fix PR libstdc++/11504.  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.

Cheers,


Gawain


--
Gawain Bolton
Coignieres, France
PGP Info: Key server: http://wwwkeys.pgp.net
          Key id: 6EBEDEA6
          Fingerprint: 65C0 0030 21D1 7A01 546A  E7DB D60F 47E0 6EBE DEA6


Index: config/linker-map.gnu
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/config/linker-map.gnu,v
retrieving revision 1.45
diff -c -3 -p -r1.45 linker-map.gnu
*** config/linker-map.gnu	18 Jul 2003 02:27:13 -0000	1.45
--- config/linker-map.gnu	29 Jul 2003 19:55:19 -0000
*************** GLIBCXX_3.4 {
*** 76,84 ****
      _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_;
--- 76,85 ----
      _ZSt9has_facet*;
  
      # _Rb_tree
!     _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_;
Index: include/bits/stl_tree.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_tree.h,v
retrieving revision 1.27
diff -c -3 -p -r1.27 stl_tree.h
*** include/bits/stl_tree.h	14 Jul 2003 02:52:04 -0000	1.27
--- include/bits/stl_tree.h	29 Jul 2003 19:55:20 -0000
*************** namespace std
*** 95,100 ****
--- 95,101 ----
    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;
*************** namespace std
*** 108,119 ****
--- 109,134 ----
        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>
*************** namespace std
*** 123,145 ****
        _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();
  
!     void 
!     _M_decrement();
!   };
  
    template<typename _Val, typename _Ref, typename _Ptr>
!     struct _Rb_tree_iterator : public _Rb_tree_base_iterator
      {
        typedef _Val value_type;
        typedef _Ref reference;
--- 138,151 ----
        _Val _M_value_field;
      };
    
!   _Rb_tree_node_base*
!   _Rb_tree_increment(_Rb_tree_node_base* __x);
  
!   _Rb_tree_node_base*
!   _Rb_tree_decrement(_Rb_tree_node_base* __x);
  
    template<typename _Val, typename _Ref, typename _Ptr>
!     struct _Rb_tree_iterator
      {
        typedef _Val value_type;
        typedef _Ref reference;
*************** namespace std
*** 147,169 ****
        typedef _Rb_tree_iterator<_Val, _Val&, _Val*> iterator;
        typedef _Rb_tree_iterator<_Val, const _Val&, const _Val*> 
        const_iterator;
        typedef _Rb_tree_iterator<_Val, _Ref, _Ptr> _Self;
        typedef _Rb_tree_node<_Val>* _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; }
  
        reference 
!       operator*() const { return _Link_type(_M_node)->_M_value_field; }
  
        pointer 
!       operator->() const { return &(operator*()); }
  
        _Self& 
        operator++() 
        { 
! 	_M_increment(); 
  	return *this; 
        }
  
--- 153,188 ----
        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(_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 static_cast<_Link_type>(_M_node)->_M_value_field; }
  
        pointer 
!       operator->() const
!       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
  
        _Self& 
        operator++() 
        { 
! 	_M_node = _Rb_tree_increment(_M_node);
  	return *this; 
        }
  
*************** namespace std
*** 171,190 ****
        operator++(int) 
        {
  	_Self __tmp = *this;
! 	_M_increment();
  	return __tmp;
        }
      
        _Self& 
!       operator--() { _M_decrement(); return *this; }
  
        _Self 
        operator--(int) 
        {
  	_Self __tmp = *this;
! 	_M_decrement();
  	return __tmp;
        }
    };
  
    template<typename _Val, typename _Ref, typename _Ptr>
--- 190,215 ----
        operator++(int) 
        {
  	_Self __tmp = *this;
! 	_M_node = _Rb_tree_increment(_M_node);
  	return __tmp;
        }
      
        _Self& 
!       operator--()
!       {
! 	_M_node = _Rb_tree_decrement(_M_node);
! 	return *this;
!       }
  
        _Self 
        operator--(int) 
        {
  	_Self __tmp = *this;
! 	_M_node = _Rb_tree_decrement(_M_node);
  	return __tmp;
        }
+ 
+       _Base_ptr _M_node;
    };
  
    template<typename _Val, typename _Ref, typename _Ptr>
*************** namespace std
*** 312,317 ****
--- 337,343 ----
        
      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:
*************** namespace std
*** 322,327 ****
--- 348,354 ----
        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;
        
*************** namespace std
*** 348,354 ****
        }
        
        _Link_type 
!       _M_clone_node(_Link_type __x)
        {
  	_Link_type __tmp = _M_create_node(__x->_M_value_field);
  	__tmp->_M_color = __x->_M_color;
--- 375,381 ----
        }
        
        _Link_type 
!       _M_clone_node(_Const_Link_type __x)
        {
  	_Link_type __tmp = _M_create_node(__x->_M_value_field);
  	__tmp->_M_color = __x->_M_color;
*************** namespace std
*** 367,424 ****
        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; }
  
!       _Link_type& 
!       _M_leftmost() const { return (_Link_type&) this->_M_header._M_left; }
  
!       _Link_type& 
!       _M_rightmost() const { return (_Link_type&) 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); }
  
!       static _Link_type& 
!       _S_right(_Link_type __x) { return (_Link_type&)(__x->_M_right); }
  
!       static _Link_type& 
!       _S_parent(_Link_type __x) { return (_Link_type&)(__x->_M_parent); }
  
!       static reference 
!       _S_value(_Link_type __x) { return __x->_M_value_field; }
  
        static const _Key& 
!       _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); }
  
!       static _Link_type& 
!       _S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); }
  
!       static _Link_type& 
!       _S_right(_Base_ptr __x) { return (_Link_type&)(__x->_M_right); }
  
!       static _Link_type& 
!       _S_parent(_Base_ptr __x) { return (_Link_type&)(__x->_M_parent); }
  
!       static reference 
!       _S_value(_Base_ptr __x) { return ((_Link_type)__x)->_M_value_field; }
  
!       static const _Key& 
!       _S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x)));} 
  
!       static _Rb_tree_color&
!       _S_color(_Base_ptr __x) { return __x->_M_color; }
  
!       static _Link_type 
!       _S_minimum(_Link_type __x) 
!       { return (_Link_type)  _Rb_tree_node_base::_S_minimum(__x); }
! 
!       static _Link_type 
!       _S_maximum(_Link_type __x)
!       { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
  
      public:
        typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
--- 394,468 ----
        size_type _M_node_count; // keeps track of size of tree
        _Compare _M_key_compare;
  
!       _Base_ptr&
!       _M_root() { return this->_M_header._M_parent; }
  
!       _Const_Base_ptr
!       _M_root() const { return this->_M_header._M_parent; }
  
!       _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_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); }
  
!       _Link_type
!       _M_end() { return static_cast<_Link_type>(&this->_M_header); }
  
!       _Const_Link_type
!       _M_end() const { return static_cast<_Const_Link_type>(&this->_M_header); }
  
!       static const_reference 
!       _S_value(_Const_Link_type __x) { return __x->_M_value_field; }
  
        static const _Key& 
!       _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 _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 static_cast<_Link_type>(__x->_M_right); }
  
!       static _Const_Link_type
!       _S_right(_Const_Base_ptr __x) { return static_cast<_Const_Link_type>(__x->_M_right); }
  
!       static const_reference
!       _S_value(_Const_Base_ptr __x) { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
  
!       static const _Key& 
!       _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 _Const_Base_ptr
!       _S_minimum(_Const_Base_ptr __x)
!       { return _Rb_tree_node_base::_S_minimum(__x); }
! 
!       static _Base_ptr
!       _S_maximum(_Base_ptr __x)
!       { return _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;
*************** namespace std
*** 433,439 ****
        _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
  
        _Link_type 
!       _M_copy(_Link_type __x, _Link_type __p);
  
        void 
        _M_erase(_Link_type __x);
--- 477,483 ----
        _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
  
        _Link_type 
!       _M_copy(_Const_Link_type __x, _Link_type __p);
  
        void 
        _M_erase(_Link_type __x);
*************** namespace std
*** 460,467 ****
  	  _M_empty_initialize();
  	else 
  	  {
! 	    _S_color(&this->_M_header) = _S_red;
! 	    _M_root() = _M_copy(__x._M_root(), _M_end());
  	    _M_leftmost() = _S_minimum(_M_root());
  	    _M_rightmost() = _S_maximum(_M_root());
  	  }
--- 504,511 ----
  	  _M_empty_initialize();
  	else 
  	  {
! 	    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());
  	  }
*************** namespace std
*** 477,483 ****
        void _M_empty_initialize() 
        {
  	// Used to distinguish header from __root, in iterator.operator++.
! 	_S_color(&this->_M_header) = _S_red; 
  	_M_root() = 0;
  	_M_leftmost() = _M_end();
  	_M_rightmost() = _M_end();
--- 521,527 ----
        void _M_empty_initialize() 
        {
  	// Used to distinguish header from __root, in iterator.operator++.
! 	this->_M_header._M_color = _S_red; 
  	_M_root() = 0;
  	_M_leftmost() = _M_end();
  	_M_rightmost() = _M_end();
*************** namespace std
*** 489,504 ****
        key_comp() const { return _M_key_compare; }
  
        iterator 
!       begin() { return _M_leftmost(); }
  
        const_iterator 
!       begin() const { return _M_leftmost(); }
  
        iterator 
!       end() { return &this->_M_header; }
  
        const_iterator
!       end() const { return const_cast<_Base_ptr>(&this->_M_header); }
  
        reverse_iterator 
        rbegin() { return reverse_iterator(end()); }
--- 533,548 ----
        key_comp() const { return _M_key_compare; }
  
        iterator 
!       begin() { return static_cast<_Link_type>(this->_M_header._M_left); }
  
        const_iterator 
!       begin() const { return static_cast<_Const_Link_type>(this->_M_header._M_left); }
  
        iterator 
!       end() { return static_cast<_Link_type>(&this->_M_header); }
  
        const_iterator
!       end() const { return static_cast<_Const_Link_type>(&this->_M_header); }
  
        reverse_iterator 
        rbegin() { return reverse_iterator(end()); }
*************** namespace std
*** 562,568 ****
        {
  	if (_M_node_count != 0) 
  	  {
! 	    _M_erase(_M_root());
  	    _M_leftmost() = _M_end();
  	    _M_root() = 0;
  	    _M_rightmost() = _M_end();
--- 606,612 ----
        {
  	if (_M_node_count != 0) 
  	  {
! 	    _M_erase(_M_begin());
  	    _M_leftmost() = _M_end();
  	    _M_root() = 0;
  	    _M_rightmost() = _M_end();
*************** namespace std
*** 678,684 ****
  	    }
  	  else 
  	    {
! 	      _M_root() = _M_copy(__x._M_root(), _M_end());
  	      _M_leftmost() = _S_minimum(_M_root());
  	      _M_rightmost() = _S_maximum(_M_root());
  	      _M_node_count = __x._M_node_count;
--- 722,728 ----
  	    }
  	  else 
  	    {
! 	      _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;
*************** namespace std
*** 693,707 ****
      _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 __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 
  	  //    when __y == &_M_header
  	  if (__y == &this->_M_header) 
  	    {
--- 737,751 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      _M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Val& __v)
      {
!       _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);
! 	  __y->_M_left = __z;               // also makes _M_leftmost() = __z
  	  //    when __y == &_M_header
  	  if (__y == &this->_M_header) 
  	    {
*************** namespace std
*** 714,727 ****
        else 
  	{
  	  __z = _M_create_node(__v);
! 	  _S_right(__y) = __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;
        _Rb_tree_rebalance(__z, this->_M_header._M_parent);
        ++_M_node_count;
        return iterator(__z);
--- 758,771 ----
        else 
  	{
  	  __z = _M_create_node(__v);
! 	  __y->_M_right = __z;
  	  // Maintain _M_rightmost() pointing to max node.
  	  if (__y == _M_rightmost())
  	    _M_rightmost() = __z; 
  	}
!       __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);
*************** namespace std
*** 733,740 ****
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      insert_equal(const _Val& __v)
      {
        _Link_type __y = _M_end();
-       _Link_type __x = _M_root();
        while (__x != 0) 
  	{
  	  __y = __x;
--- 777,784 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      insert_equal(const _Val& __v)
      {
+       _Link_type __x = _M_begin();
        _Link_type __y = _M_end();
        while (__x != 0) 
  	{
  	  __y = __x;
*************** namespace std
*** 796,803 ****
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      insert_unique(const _Val& __v)
      {
        _Link_type __y = _M_end();
-       _Link_type __x = _M_root();
        bool __comp = true;
        while (__x != 0) 
  	{
--- 840,847 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      insert_unique(const _Val& __v)
      {
+       _Link_type __x = _M_begin();
        _Link_type __y = _M_end();
        bool __comp = true;
        while (__x != 0) 
  	{
*************** namespace std
*** 930,937 ****
      _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);
        destroy_node(__y);
        --_M_node_count;
      }
--- 974,981 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
      {
        _Link_type __y = 
! 	static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
! 							     this->_M_header));
        destroy_node(__y);
        --_M_node_count;
      }
*************** namespace std
*** 951,957 ****
             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)
      {
        // Structural copy.  __x and __p must be non-null.
        _Link_type __top = _M_clone_node(__x);
--- 995,1001 ----
             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);
*************** namespace std
*** 1025,1032 ****
      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. 
        
        while (__x != 0) 
  	if (!_M_key_compare(_S_key(__x), __k))
--- 1069,1076 ----
      typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
      _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_key_compare(_S_key(__x), __k))
*************** namespace std
*** 1045,1052 ****
      _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. 
   
       while (__x != 0) 
         {
--- 1089,1096 ----
      _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) 
         {
*************** namespace std
*** 1077,1084 ****
      _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.
        
        while (__x != 0) 
  	if (!_M_key_compare(_S_key(__x), __k))
--- 1121,1128 ----
      _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_key_compare(_S_key(__x), __k))
*************** namespace std
*** 1095,1102 ****
      _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.
        
        while (__x != 0) 
  	if (!_M_key_compare(_S_key(__x), __k))
--- 1139,1146 ----
      _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_key_compare(_S_key(__x), __k))
*************** namespace std
*** 1113,1120 ****
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      upper_bound(const _Key& __k)
      {
        _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)))
--- 1157,1164 ----
      _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_key_compare(__k, _S_key(__x)))
*************** namespace std
*** 1131,1138 ****
      _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.
        
        while (__x != 0) 
  	if (_M_key_compare(__k, _S_key(__x)))
--- 1175,1182 ----
      _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_key_compare(__k, _S_key(__x)))
*************** namespace std
*** 1164,1186 ****
  					       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;
!   }
  
    template<typename _Key, typename _Val, typename _KeyOfValue, 
             typename _Compare, typename _Alloc>
--- 1208,1216 ----
  					       upper_bound(__k));
    }
  
!   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>
*************** namespace std
*** 1192,1203 ****
  	this->_M_header._M_left == &this->_M_header &&
  	this->_M_header._M_right == &this->_M_header;
    
!     int __len = __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);
  	
  	if (__x->_M_color == _S_red)
  	  if ((__L && __L->_M_color == _S_red) 
--- 1222,1233 ----
  	this->_M_header._M_left == &this->_M_header &&
  	this->_M_header._M_right == &this->_M_header;
    
!     unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
      for (const_iterator __it = begin(); __it != end(); ++__it) 
        {
! 	_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) 
*************** namespace std
*** 1209,1215 ****
  	if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
  	  return false;
  
! 	if (!__L && !__R && __black_count(__x, _M_root()) != __len)
  	  return false;
        }
      
--- 1239,1245 ----
  	if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
  	  return false;
  
! 	if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
  	  return false;
        }
      
Index: src/stl_tree.cc
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/src/stl_tree.cc,v
retrieving revision 1.1
diff -c -3 -p -r1.1 stl_tree.cc
*** src/stl_tree.cc	9 Jul 2003 20:58:32 -0000	1.1
--- src/stl_tree.cc	29 Jul 2003 19:55:20 -0000
***************
*** 59,109 ****
  
  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 
--- 59,111 ----
  
  namespace std
  {
!   _Rb_tree_node_base*
!   _Rb_tree_increment(_Rb_tree_node_base* __x)
    {
!     if (__x->_M_right != 0) 
        {
!         __x = __x->_M_right;
!         while (__x->_M_left != 0)
!           __x = __x->_M_left;
        }
      else 
        {
!         _Rb_tree_node_base* __y = __x->_M_parent;
!         while (__x == __y->_M_right) 
            {
!             __x = __y;
              __y = __y->_M_parent;
            }
!         if (__x->_M_right != __y)
!           __x = __y;
        }
+     return __x;
    }
  
!   _Rb_tree_node_base*
!   _Rb_tree_decrement(_Rb_tree_node_base* __x)
    {
!     if (__x->_M_color == _S_red 
!         && __x->_M_parent->_M_parent == __x)
!       __x = __x->_M_right;
!     else if (__x->_M_left != 0) 
        {
!         _Rb_tree_node_base* __y = __x->_M_left;
          while (__y->_M_right != 0)
            __y = __y->_M_right;
!         __x = __y;
        }
      else 
        {
!         _Rb_tree_node_base* __y = __x->_M_parent;
!         while (__x == __y->_M_left) 
            {
!             __x = __y;
              __y = __y->_M_parent;
            }
!         __x = __y;
        }
+     return __x;
    }
  
    void 
*************** namespace std
*** 361,365 ****
--- 363,386 ----
  	if (__x) __x->_M_color = _S_black;
        }
      return __y;
+   }
+ 
+   unsigned int
+   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
+                        const _Rb_tree_node_base* __root)
+   {
+     if (__node == 0)
+       return 0;
+     unsigned int __sum = 0;
+     do 
+       {
+ 	if (__node->_M_color == _S_black) 
+ 	  ++__sum;
+ 	if (__node == __root) 
+ 	  break;
+ 	__node = __node->_M_parent;
+       } 
+     while (1);
+     return __sum;
    }
  } // namespace std 

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]