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]

[Patch] Performance and memory usage improvements for stl_tree.h


This is an updated patch to improve stl_tree.h. It affects the std::map, std::multimap, std::set and std::multiset container types. This patch has been updated to show the differences with respect to what ( I hope) is the latest version in CVS. I'm hoping that this will help these changes get in.

This patch improves performance when creating and destorying containers, as well as reducing the amount of memory required since the header no longer allocates storage for the container's type.

This has been tested on i686-pc-linux-gnu using GCC 3.2.2.

Cheers


Gawain


Index: stl_tree.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_tree.h,v
retrieving revision 1.19
diff -u -r1.19 stl_tree.h
--- stl_tree.h	16 Jan 2003 20:30:24 -0000	1.19
+++ stl_tree.h	22 Feb 2003 14:08:17 -0000
@@ -192,7 +192,7 @@
       typedef _Rb_tree_node<_Val>* _Link_type;
       
       _Rb_tree_iterator() {}
-      _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
+      _Rb_tree_iterator(_Rb_tree_node_base * __x) { _M_node = __x; }
       _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; }
 
       reference 
@@ -528,13 +528,13 @@
       get_allocator() const { return _M_node_allocator; }
 
       _Rb_tree_alloc_base(const allocator_type& __a)
-      : _M_node_allocator(__a), _M_header(0) {}
+      : _M_node_allocator(__a) {}
 
     protected:
       typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type
       _M_node_allocator;
 
-      _Rb_tree_node<_Tp>* _M_header;
+      _Rb_tree_node_base _M_header;
       
       _Rb_tree_node<_Tp>* 
       _M_get_node()  { return _M_node_allocator.allocate(1); }
@@ -552,10 +552,10 @@
     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) {}
+      _Rb_tree_alloc_base(const allocator_type&) {}
 
     protected:
-      _Rb_tree_node<_Tp>* _M_header;
+      _Rb_tree_node_base _M_header;
       
       typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type
       _Alloc_type;
@@ -576,8 +576,7 @@
       typedef typename _Base::allocator_type allocator_type;
 
       _Rb_tree_base(const allocator_type& __a) 
-      : _Base(__a) { this->_M_header = _M_get_node(); }
-      ~_Rb_tree_base() { _M_put_node(this->_M_header); }
+      : _Base(__a) {}
     };
 
 
@@ -645,13 +644,13 @@
       _Compare _M_key_compare;
 
       _Link_type& 
-      _M_root() const { return (_Link_type&) this->_M_header->_M_parent; }
+      _M_root() const { return (_Link_type&) this->_M_header._M_parent; }
 
       _Link_type& 
-      _M_leftmost() const { return (_Link_type&) this->_M_header->_M_left; }
+      _M_leftmost() const { return (_Link_type&) this->_M_header._M_left; }
 
       _Link_type& 
-      _M_rightmost() const { return (_Link_type&) this->_M_header->_M_right; }
+      _M_rightmost() const { return (_Link_type&) this->_M_header._M_right; }
 
       static _Link_type& 
       _S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); }
@@ -737,8 +736,8 @@
 	  _M_empty_initialize();
 	else 
 	  {
-	    _S_color(this->_M_header) = _M_red;
-	    _M_root() = _M_copy(__x._M_root(), this->_M_header);
+	    _S_color(&this->_M_header) = _M_red;
+	    _M_root() = _M_copy(__x._M_root(), &this->_M_header);
 	    _M_leftmost() = _S_minimum(_M_root());
 	    _M_rightmost() = _S_maximum(_M_root());
 	  }
@@ -753,11 +752,11 @@
     private:
       void _M_empty_initialize() 
       {
-	_S_color(this->_M_header) = _M_red; // used to distinguish header from 
+	_S_color(&this->_M_header) = _M_red; // used to distinguish header from 
 	// __root, in iterator.operator++
 	_M_root() = 0;
-	_M_leftmost() = this->_M_header;
-	_M_rightmost() = this->_M_header;
+	this->_M_header._M_left = &this->_M_header;
+	this->_M_header._M_right = &this->_M_header;
       }
 
     public:    
@@ -772,10 +771,10 @@
       begin() const { return _M_leftmost(); }
 
       iterator 
-      end() { return this->_M_header; }
+      end() { return &this->_M_header; }
 
       const_iterator 
-      end() const { return this->_M_header; }
+      end() const { return const_cast<_Rb_tree_node_base *>(&this->_M_header); }
 
       reverse_iterator 
       rbegin() { return reverse_iterator(end()); }
@@ -801,9 +800,12 @@
       void 
       swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) 
       {
-	std::swap(this->_M_header, __t._M_header);
-	std::swap(_M_node_count, __t._M_node_count);
-	std::swap(_M_key_compare, __t._M_key_compare);
+        std::swap(this->_M_header._M_parent, __t._M_header._M_parent);
+        std::swap(this->_M_header._M_left, __t._M_header._M_left);
+        std::swap(this->_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,9 +847,9 @@
 	if (_M_node_count != 0) 
 	  {
 	    _M_erase(_M_root());
-	    _M_leftmost() = this->_M_header;
+	    this->_M_header._M_left = &this->_M_header;
 	    _M_root() = 0;
-	    _M_rightmost() = this->_M_header;
+	    this->_M_header._M_right = &this->_M_header;
 	    _M_node_count = 0;
 	  }
       }      
@@ -955,12 +957,12 @@
 	  if (__x._M_root() == 0) 
 	    {
 	      _M_root() = 0;
-	      _M_leftmost() = this->_M_header;
-	      _M_rightmost() = this->_M_header;
+	      this->_M_header._M_left = &this->_M_header;
+	      this->_M_header._M_right = &this->_M_header;
 	    }
 	  else 
 	    {
-	      _M_root() = _M_copy(__x._M_root(), this->_M_header);
+	      _M_root() = _M_copy(__x._M_root(), &this->_M_header);
 	      _M_leftmost() = _S_minimum(_M_root());
 	      _M_rightmost() = _S_maximum(_M_root());
 	      _M_node_count = __x._M_node_count;
@@ -979,13 +981,13 @@
       _Link_type __y = (_Link_type) __y_;
       _Link_type __z;
       
-      if (__y == this->_M_header || __x != 0 || 
+      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) 
+	  //    when __y == &_M_header
+	  if (__y == &this->_M_header) 
 	    {
 	      _M_root() = __z;
 	      _M_rightmost() = __z;
@@ -1004,7 +1006,7 @@
       _S_parent(__z) = __y;
       _S_left(__z) = 0;
       _S_right(__z) = 0;
-      _Rb_tree_rebalance(__z, this->_M_header->_M_parent);
+      _Rb_tree_rebalance(__z, this->_M_header._M_parent);
       ++_M_node_count;
       return iterator(__z);
     }
@@ -1015,7 +1017,7 @@
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     insert_equal(const _Val& __v)
     {
-      _Link_type __y = this->_M_header;
+      _Link_type __y = static_cast<_Link_type>(&this->_M_header);
       _Link_type __x = _M_root();
       while (__x != 0) 
 	{
@@ -1033,7 +1035,7 @@
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     insert_unique(const _Val& __v)
     {
-      _Link_type __y = this->_M_header;
+      _Link_type __y = static_cast<_Link_type>(&this->_M_header);
       _Link_type __x = _M_root();
       bool __comp = true;
       while (__x != 0) 
@@ -1060,7 +1062,7 @@
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     insert_unique(iterator __position, const _Val& __v)
     {
-      if (__position._M_node == this->_M_header->_M_left) 
+      if (__position._M_node == this->_M_header._M_left) 
 	{ 
 	  // begin()
 	  if (size() > 0 && 
@@ -1070,7 +1072,7 @@
 	  else
 	    return insert_unique(__v).first;
 	} 
-      else if (__position._M_node == this->_M_header) 
+      else if (__position._M_node == &this->_M_header) 
 	{ 
 	  // end()
 	  if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
@@ -1102,7 +1104,7 @@
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     insert_equal(iterator __position, const _Val& __v)
     {
-      if (__position._M_node == this->_M_header->_M_left) 
+      if (__position._M_node == this->_M_header._M_left) 
 	{ 
 	  // begin()
 	  if (size() > 0 && 
@@ -1112,7 +1114,7 @@
 	  else
 	    return insert_equal(__v);
 	} 
-      else if (__position._M_node == this->_M_header) 
+      else if (__position._M_node == &this->_M_header) 
 	{
 	  // end()
 	  if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
@@ -1168,9 +1170,9 @@
     {
       _Link_type __y = 
 	(_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
-						  this->_M_header->_M_parent,
-						  this->_M_header->_M_left,
-						  this->_M_header->_M_right);
+						  this->_M_header._M_parent,
+						  this->_M_header._M_left,
+						  this->_M_header._M_right);
       destroy_node(__y);
       --_M_node_count;
     }
@@ -1264,9 +1266,8 @@
     typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator 
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
     {
-      _Link_type __y
-	= this->_M_header;  // Last node which is not less than __k. 
-      _Link_type __x = _M_root();  // Current node. 
+      _Link_type __y = static_cast<_Link_type>(&this->_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))
@@ -1285,8 +1286,7 @@
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     find(const _Key& __k) const
     {
-      _Link_type __y
-	= this->_M_header; // Last node which is not less than __k. 
+      _Link_type __y = static_cast<_Link_type>(&this->_M_header); // Last node which is not less than __k. 
       _Link_type __x = _M_root(); // Current node. 
  
      while (__x != 0) 
@@ -1318,9 +1318,8 @@
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     lower_bound(const _Key& __k)
     {
-      _Link_type __y
-	= this->_M_header; /* Last node which is not less than __k. */
-      _Link_type __x = _M_root(); /* Current node. */
+      _Link_type __y = static_cast<_Link_type>(&this->_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))
@@ -1337,9 +1336,8 @@
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     lower_bound(const _Key& __k) const
     {
-      _Link_type __y
-	= this->_M_header; /* Last node which is not less than __k. */
-      _Link_type __x = _M_root(); /* Current node. */
+      _Link_type __y = static_cast<_Link_type>(&this->_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))
@@ -1356,9 +1354,8 @@
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     upper_bound(const _Key& __k)
     {
-      _Link_type __y
-	= this->_M_header; /* Last node which is greater than __k. */
-      _Link_type __x = _M_root(); /* Current node. */
+      _Link_type __y = static_cast<_Link_type>(&this->_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)))
@@ -1375,9 +1372,8 @@
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     upper_bound(const _Key& __k) const
     {
-      _Link_type __y
-	= this->_M_header; /* Last node which is greater than __k. */
-      _Link_type __x = _M_root(); /* Current node. */
+      _Link_type __y = static_cast<_Link_type>(&this->_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)))
@@ -1434,8 +1430,8 @@
     {
     if (_M_node_count == 0 || begin() == end())
       return _M_node_count == 0 && begin() == end() &&
-	this->_M_header->_M_left == this->_M_header
-	&& this->_M_header->_M_right == this->_M_header;
+	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) 

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