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]

Suggested improvement to stl_tree.h


Hello again,

Please find attached a patch for stl_tree.h against the version provided
by GCC 3.2.2.

This patch is similar to that provided for stl_list.h and is a
performance improvement patch when creating and destorying _Rb_tree
objects.  This patch affects the std::map, std::multimap, std:set and
std::multiset classes.

The performance of the swap() function is only slightly worse.
Additional benefits are the size of the code generated is decreased and
a reduction in the amount of memory required at execution time.


Gawain

--
-------------------------------------------------------------------------------
Gawain Bolton                     | E-mail: boltong@nortelnetworks.com
UMTS Development                  |
Nortel Networks                   | Voice:  +33 1.39.44.37.63
Guyancourt, France                | FAX:    +33 1.39.44.30.09
-------------------------------------------------------------------------------


*** stl_tree.h.org	Fri Feb  7 12:13:11 2003
--- stl_tree.h	Thu Feb 13 13:48:48 2003
***************
*** 192,198 ****
        typedef _Rb_tree_node<_Val>* _Link_type;
        
        _Rb_tree_iterator() {}
!       _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
        _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; }
  
        reference 
--- 192,198 ----
        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 
***************
*** 528,540 ****
        get_allocator() const { return _M_node_allocator; }
  
        _Rb_tree_alloc_base(const allocator_type& __a)
!       : _M_node_allocator(__a), _M_header(0) {}
  
      protected:
        typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type
        _M_node_allocator;
  
!       _Rb_tree_node<_Tp>* _M_header;
        
        _Rb_tree_node<_Tp>* 
        _M_get_node()  { return _M_node_allocator.allocate(1); }
--- 528,540 ----
        get_allocator() const { return _M_node_allocator; }
  
        _Rb_tree_alloc_base(const allocator_type& __a)
!       : _M_node_allocator(__a) {}
  
      protected:
        typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type
        _M_node_allocator;
  
!       _Rb_tree_node_base _M_header;
        
        _Rb_tree_node<_Tp>* 
        _M_get_node()  { return _M_node_allocator.allocate(1); }
***************
*** 552,561 ****
      typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
        allocator_type get_allocator() const { return allocator_type(); }
  
!       _Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {}
  
      protected:
!       _Rb_tree_node<_Tp>* _M_header;
        
        typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type
        _Alloc_type;
--- 552,561 ----
      typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
        allocator_type get_allocator() const { return allocator_type(); }
  
!       _Rb_tree_alloc_base(const allocator_type&) {}
  
      protected:
!       _Rb_tree_node_base _M_header;
        
        typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type
        _Alloc_type;
***************
*** 576,583 ****
        typedef typename _Base::allocator_type allocator_type;
  
        _Rb_tree_base(const allocator_type& __a) 
!       : _Base(__a) { _M_header = _M_get_node(); }
!       ~_Rb_tree_base() { _M_put_node(_M_header); }
      };
  
  
--- 576,582 ----
        typedef typename _Base::allocator_type allocator_type;
  
        _Rb_tree_base(const allocator_type& __a) 
!       : _Base(__a) {}
      };
  
  
***************
*** 645,657 ****
        _Compare _M_key_compare;
  
        _Link_type& 
!       _M_root() const { return (_Link_type&) _M_header->_M_parent; }
  
        _Link_type& 
!       _M_leftmost() const { return (_Link_type&) _M_header->_M_left; }
  
        _Link_type& 
!       _M_rightmost() const { return (_Link_type&) _M_header->_M_right; }
  
        static _Link_type& 
        _S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); }
--- 644,656 ----
        _Compare _M_key_compare;
  
        _Link_type& 
!       _M_root() const { return (_Link_type&) _M_header._M_parent; }
  
        _Link_type& 
!       _M_leftmost() const { return (_Link_type&) _M_header._M_left; }
  
        _Link_type& 
!       _M_rightmost() const { return (_Link_type&) _M_header._M_right; }
  
        static _Link_type& 
        _S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); }
***************
*** 737,744 ****
  	  _M_empty_initialize();
  	else 
  	  {
! 	    _S_color(_M_header) = _M_red;
! 	    _M_root() = _M_copy(__x._M_root(), _M_header);
  	    _M_leftmost() = _S_minimum(_M_root());
  	    _M_rightmost() = _S_maximum(_M_root());
  	  }
--- 736,743 ----
  	  _M_empty_initialize();
  	else 
  	  {
! 	    _S_color(&_M_header) = _M_red;
! 	    _M_root() = _M_copy(__x._M_root(), &_M_header);
  	    _M_leftmost() = _S_minimum(_M_root());
  	    _M_rightmost() = _S_maximum(_M_root());
  	  }
***************
*** 753,763 ****
      private:
        void _M_empty_initialize() 
        {
! 	_S_color(_M_header) = _M_red; // used to distinguish header from 
  	// __root, in iterator.operator++
  	_M_root() = 0;
! 	_M_leftmost() = _M_header;
! 	_M_rightmost() = _M_header;
        }
  
      public:    
--- 752,762 ----
      private:
        void _M_empty_initialize() 
        {
! 	_S_color(&_M_header) = _M_red; // used to distinguish header from 
  	// __root, in iterator.operator++
  	_M_root() = 0;
! 	_M_header._M_left = &_M_header;
! 	_M_header._M_right = &_M_header;
        }
  
      public:    
***************
*** 772,781 ****
        begin() const { return _M_leftmost(); }
  
        iterator 
!       end() { return _M_header; }
  
        const_iterator 
!       end() const { return _M_header; }
  
        reverse_iterator 
        rbegin() { return reverse_iterator(end()); }
--- 771,780 ----
        begin() const { return _M_leftmost(); }
  
        iterator 
!       end() { return &_M_header; }
  
        const_iterator 
!       end() const { return const_cast<_Rb_tree_node_base *>(&_M_header); }
  
        reverse_iterator 
        rbegin() { return reverse_iterator(end()); }
***************
*** 801,809 ****
        void 
        swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) 
        {
! 	std::swap(_M_header, __t._M_header);
! 	std::swap(_M_node_count, __t._M_node_count);
! 	std::swap(_M_key_compare, __t._M_key_compare);
        }
      
        // Insert/erase.
--- 800,811 ----
        void 
        swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) 
        {
!         std::swap(_M_header._M_parent, __t._M_header._M_parent);
!         std::swap(_M_header._M_left, __t._M_header._M_left);
!         std::swap(_M_header._M_right, __t._M_header._M_right);
!         // No need to swap header's color as it does not change.
!         std::swap(_M_node_count, __t._M_node_count);
!         std::swap(_M_key_compare, __t._M_key_compare);
        }
      
        // Insert/erase.
***************
*** 845,853 ****
  	if (_M_node_count != 0) 
  	  {
  	    _M_erase(_M_root());
! 	    _M_leftmost() = _M_header;
  	    _M_root() = 0;
! 	    _M_rightmost() = _M_header;
  	    _M_node_count = 0;
  	  }
        }      
--- 847,855 ----
  	if (_M_node_count != 0) 
  	  {
  	    _M_erase(_M_root());
! 	    _M_header._M_left = &_M_header;
  	    _M_root() = 0;
! 	    _M_header._M_right = &_M_header;
  	    _M_node_count = 0;
  	  }
        }      
***************
*** 955,966 ****
  	  if (__x._M_root() == 0) 
  	    {
  	      _M_root() = 0;
! 	      _M_leftmost() = _M_header;
! 	      _M_rightmost() = _M_header;
  	    }
  	  else 
  	    {
! 	      _M_root() = _M_copy(__x._M_root(), _M_header);
  	      _M_leftmost() = _S_minimum(_M_root());
  	      _M_rightmost() = _S_maximum(_M_root());
  	      _M_node_count = __x._M_node_count;
--- 957,968 ----
  	  if (__x._M_root() == 0) 
  	    {
  	      _M_root() = 0;
! 	      _M_header._M_left = &_M_header;
! 	      _M_header._M_right = &_M_header;
  	    }
  	  else 
  	    {
! 	      _M_root() = _M_copy(__x._M_root(), &_M_header);
  	      _M_leftmost() = _S_minimum(_M_root());
  	      _M_rightmost() = _S_maximum(_M_root());
  	      _M_node_count = __x._M_node_count;
***************
*** 979,991 ****
        _Link_type __y = (_Link_type) __y_;
        _Link_type __z;
        
!       if (__y == _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 == _M_header) 
  	    {
  	      _M_root() = __z;
  	      _M_rightmost() = __z;
--- 981,993 ----
        _Link_type __y = (_Link_type) __y_;
        _Link_type __z;
        
!       if (__y == &_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 == &_M_header) 
  	    {
  	      _M_root() = __z;
  	      _M_rightmost() = __z;
***************
*** 1004,1010 ****
        _S_parent(__z) = __y;
        _S_left(__z) = 0;
        _S_right(__z) = 0;
!       _Rb_tree_rebalance(__z, _M_header->_M_parent);
        ++_M_node_count;
        return iterator(__z);
      }
--- 1006,1012 ----
        _S_parent(__z) = __y;
        _S_left(__z) = 0;
        _S_right(__z) = 0;
!       _Rb_tree_rebalance(__z, _M_header._M_parent);
        ++_M_node_count;
        return iterator(__z);
      }
***************
*** 1015,1021 ****
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      insert_equal(const _Val& __v)
      {
!       _Link_type __y = _M_header;
        _Link_type __x = _M_root();
        while (__x != 0) 
  	{
--- 1017,1023 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      insert_equal(const _Val& __v)
      {
!       _Link_type __y = static_cast<_Link_type>(&_M_header);
        _Link_type __x = _M_root();
        while (__x != 0) 
  	{
***************
*** 1033,1039 ****
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      insert_unique(const _Val& __v)
      {
!       _Link_type __y = _M_header;
        _Link_type __x = _M_root();
        bool __comp = true;
        while (__x != 0) 
--- 1035,1041 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      insert_unique(const _Val& __v)
      {
!       _Link_type __y = static_cast<_Link_type>(&_M_header);
        _Link_type __x = _M_root();
        bool __comp = true;
        while (__x != 0) 
***************
*** 1060,1066 ****
      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
      insert_unique(iterator __position, const _Val& __v)
      {
!       if (__position._M_node == _M_header->_M_left) 
  	{ 
  	  // begin()
  	  if (size() > 0 && 
--- 1062,1068 ----
      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
      insert_unique(iterator __position, const _Val& __v)
      {
!       if (__position._M_node == _M_header._M_left) 
  	{ 
  	  // begin()
  	  if (size() > 0 && 
***************
*** 1070,1076 ****
  	  else
  	    return insert_unique(__v).first;
  	} 
!       else if (__position._M_node == _M_header) 
  	{ 
  	  // end()
  	  if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
--- 1072,1078 ----
  	  else
  	    return insert_unique(__v).first;
  	} 
!       else if (__position._M_node == &_M_header) 
  	{ 
  	  // end()
  	  if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
***************
*** 1102,1108 ****
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      insert_equal(iterator __position, const _Val& __v)
      {
!       if (__position._M_node == _M_header->_M_left) 
  	{ 
  	  // begin()
  	  if (size() > 0 && 
--- 1104,1110 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      insert_equal(iterator __position, const _Val& __v)
      {
!       if (__position._M_node == _M_header._M_left) 
  	{ 
  	  // begin()
  	  if (size() > 0 && 
***************
*** 1112,1118 ****
  	  else
  	    return insert_equal(__v);
  	} 
!       else if (__position._M_node == _M_header) 
  	{
  	  // end()
  	  if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
--- 1114,1120 ----
  	  else
  	    return insert_equal(__v);
  	} 
!       else if (__position._M_node == &_M_header) 
  	{
  	  // end()
  	  if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
***************
*** 1168,1176 ****
      {
        _Link_type __y = 
  	(_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
! 						  _M_header->_M_parent,
! 						  _M_header->_M_left,
! 						  _M_header->_M_right);
        destroy_node(__y);
        --_M_node_count;
      }
--- 1170,1178 ----
      {
        _Link_type __y = 
  	(_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
! 						  _M_header._M_parent,
! 						  _M_header._M_left,
! 						  _M_header._M_right);
        destroy_node(__y);
        --_M_node_count;
      }
***************
*** 1264,1271 ****
      typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
      {
!       _Link_type __y = _M_header;  // 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))
--- 1266,1273 ----
      typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
      {
!       _Link_type __y = static_cast<_Link_type>(&_M_header); // 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))
***************
*** 1284,1290 ****
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      find(const _Key& __k) const
      {
!       _Link_type __y = _M_header; // Last node which is not less than __k. 
        _Link_type __x = _M_root(); // Current node. 
   
       while (__x != 0) 
--- 1286,1292 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      find(const _Key& __k) const
      {
!       _Link_type __y = static_cast<_Link_type>(&_M_header); // Last node which is not less than __k. 
        _Link_type __x = _M_root(); // Current node. 
   
       while (__x != 0) 
***************
*** 1316,1323 ****
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      lower_bound(const _Key& __k)
      {
!       _Link_type __y = _M_header; /* 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))
--- 1318,1325 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      lower_bound(const _Key& __k)
      {
!         _Link_type __y = static_cast<_Link_type>(&_M_header); // 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))
***************
*** 1334,1341 ****
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      lower_bound(const _Key& __k) const
      {
!       _Link_type __y = _M_header; /* 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))
--- 1336,1343 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      lower_bound(const _Key& __k) const
      {
!         _Link_type __y = static_cast<_Link_type>(&_M_header); // 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))
***************
*** 1352,1359 ****
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      upper_bound(const _Key& __k)
      {
!       _Link_type __y = _M_header; /* 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)))
--- 1354,1361 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      upper_bound(const _Key& __k)
      {
!         _Link_type __y = static_cast<_Link_type>(&_M_header); // 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)))
***************
*** 1370,1377 ****
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      upper_bound(const _Key& __k) const
      {
!       _Link_type __y = _M_header; /* 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)))
--- 1372,1379 ----
      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
      upper_bound(const _Key& __k) const
      {
!         _Link_type __y = static_cast<_Link_type>(&_M_header); // 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)))
***************
*** 1428,1434 ****
      {
      if (_M_node_count == 0 || begin() == end())
        return _M_node_count == 0 && begin() == end() &&
! 	_M_header->_M_left == _M_header && _M_header->_M_right == _M_header;
    
      int __len = __black_count(_M_leftmost(), _M_root());
      for (const_iterator __it = begin(); __it != end(); ++__it) 
--- 1430,1436 ----
      {
      if (_M_node_count == 0 || begin() == end())
        return _M_node_count == 0 && begin() == end() &&
! 	_M_header._M_left == &_M_header && _M_header._M_right == &_M_header;
    
      int __len = __black_count(_M_leftmost(), _M_root());
      for (const_iterator __it = begin(); __it != end(); ++__it) 

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