stl_tree.h: Performance and memory usage improvements.

2003-07-04  Gawain Bolton  <gbolton@free.fr>

	* include/bits/stl_tree.h: Performance and memory usage
	improvements.

From-SVN: r68936

2 files changed, 104 insertions, 66 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 469692d56b0..75b511dab87 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,8 @@
+2003-07-04  Gawain Bolton  <gbolton@free.fr>
+
+	* include/bits/stl_tree.h: Performance and memory usage
+	improvements.
+
 2003-07-04  H.J. Lu <hongjiu.lu@intel.com>
 
 	* Makefile.am: Replace PWD with PWD_COMMAND.
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 95482f25de0..33c8ebd7915 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -192,7 +192,7 @@ namespace std
       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 @@ namespace std
       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 @@ namespace std
     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 @@ namespace std
       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,14 +644,17 @@ namespace std
       _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; }
 
+      _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); }
 
@@ -668,9 +670,6 @@ namespace std
       static const _Key& 
       _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); }
 
-      static _Rb_tree_color& 
-      _S_color(_Link_type __x) { return __x->_M_color; }
-
       static _Link_type& 
       _S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); }
 
@@ -687,7 +686,7 @@ namespace std
       _S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x)));} 
 
       static _Rb_tree_color&
-      _S_color(_Base_ptr __x) { return (_Link_type(__x)->_M_color); }
+      _S_color(_Base_ptr __x) { return __x->_M_color; }
 
       static _Link_type 
       _S_minimum(_Link_type __x) 
@@ -737,8 +736,8 @@ namespace std
 	  _M_empty_initialize();
 	else 
 	  {
-	    _S_color(this->_M_header) = _S_red;
-	    _M_root() = _M_copy(__x._M_root(), this->_M_header);
+	    _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());
 	  }
@@ -753,11 +752,11 @@ namespace std
     private:
       void _M_empty_initialize() 
       {
-	_S_color(this->_M_header) = _S_red; // used to distinguish header from 
-	// __root, in iterator.operator++
+	// Used to distinguish header from __root, in iterator.operator++.
+	_S_color(&this->_M_header) = _S_red; 
 	_M_root() = 0;
-	_M_leftmost() = this->_M_header;
-	_M_rightmost() = this->_M_header;
+	_M_leftmost() = _M_end();
+	_M_rightmost() = _M_end();
       }
 
     public:    
@@ -772,10 +771,10 @@ namespace std
       begin() const { return _M_leftmost(); }
 
       iterator 
-      end() { return this->_M_header; }
+      end() { return &this->_M_header; }
 
-      const_iterator 
-      end() const { return this->_M_header; }
+      const_iterator
+      end() const { return const_cast<_Base_ptr>(&this->_M_header); }
 
       reverse_iterator 
       rbegin() { return reverse_iterator(end()); }
@@ -799,12 +798,7 @@ namespace std
       max_size() const { return size_type(-1); }
 
       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);
-      }
+      swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t);
     
       // Insert/erase.
       pair<iterator,bool> 
@@ -845,9 +839,9 @@ namespace std
 	if (_M_node_count != 0) 
 	  {
 	    _M_erase(_M_root());
-	    _M_leftmost() = this->_M_header;
+	    _M_leftmost() = _M_end();
 	    _M_root() = 0;
-	    _M_rightmost() = this->_M_header;
+	    _M_rightmost() = _M_end();
 	    _M_node_count = 0;
 	  }
       }      
@@ -955,12 +949,12 @@ namespace std
 	  if (__x._M_root() == 0) 
 	    {
 	      _M_root() = 0;
-	      _M_leftmost() = this->_M_header;
-	      _M_rightmost() = this->_M_header;
+	      _M_leftmost() = _M_end();
+	      _M_rightmost() = _M_end();
 	    }
 	  else 
 	    {
-	      _M_root() = _M_copy(__x._M_root(), this->_M_header);
+	      _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;
@@ -979,13 +973,13 @@ namespace std
       _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 +998,7 @@ namespace std
       _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 +1009,7 @@ namespace std
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     insert_equal(const _Val& __v)
     {
-      _Link_type __y = this->_M_header;
+      _Link_type __y = _M_end();
       _Link_type __x = _M_root();
       while (__x != 0) 
 	{
@@ -1028,12 +1022,57 @@ namespace std
 
   template<typename _Key, typename _Val, typename _KeyOfValue, 
            typename _Compare, typename _Alloc>
+    void
+    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
+    swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t)
+    {
+      if (_M_root() == 0)
+      {
+	if (__t._M_root() != 0)
+	{
+	  _M_root() = __t._M_root();
+	  _M_leftmost() = __t._M_leftmost();
+	  _M_rightmost() = __t._M_rightmost();
+          _M_root()->_M_parent = _M_end();
+
+	  __t._M_root() = 0;
+	  __t._M_leftmost() = __t._M_end();
+	  __t._M_rightmost() = __t._M_end();
+	}
+      }
+      else if (__t._M_root() == 0)
+      {
+	__t._M_root() = _M_root();
+	__t._M_leftmost() = _M_leftmost();
+	__t._M_rightmost() = _M_rightmost();
+        __t._M_root()->_M_parent = __t._M_end();
+
+	_M_root() = 0;
+	_M_leftmost() = _M_end();
+	_M_rightmost() = _M_end();
+      }
+      else
+      {
+	std::swap(_M_root(),__t._M_root());
+	std::swap(_M_leftmost(),__t._M_leftmost());
+	std::swap(_M_rightmost(),__t._M_rightmost());
+
+	_M_root()->_M_parent = _M_end();
+	__t._M_root()->_M_parent = __t._M_end();
+      }
+      // No need to swap header's color as it does not change.
+      std::swap(this->_M_node_count, __t._M_node_count);
+      std::swap(this->_M_key_compare, __t._M_key_compare);
+    }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue, 
+           typename _Compare, typename _Alloc>
     pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator, 
     bool>
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
     insert_unique(const _Val& __v)
     {
-      _Link_type __y = this->_M_header;
+      _Link_type __y = _M_end();
       _Link_type __x = _M_root();
       bool __comp = true;
       while (__x != 0) 
@@ -1060,7 +1099,7 @@ namespace std
     _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 +1109,7 @@ namespace std
 	  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 +1141,7 @@ namespace std
     _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 +1151,7 @@ namespace std
 	  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 +1207,9 @@ namespace std
     {
       _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 +1303,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
-	= this->_M_header;  // Last node which is not less than __k. 
-      _Link_type __x = _M_root();  // Current node. 
+      _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))
@@ -1285,8 +1323,7 @@ namespace std
     _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 = _M_end(); // Last node which is not less than __k. 
       _Link_type __x = _M_root(); // Current node. 
  
      while (__x != 0) 
@@ -1318,9 +1355,8 @@ namespace std
     _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 = _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))
@@ -1337,9 +1373,8 @@ namespace std
     _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 = _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))
@@ -1356,9 +1391,8 @@ namespace std
     _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 = _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)))
@@ -1375,9 +1409,8 @@ namespace std
     _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 = _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)))
@@ -1434,8 +1467,8 @@ namespace std
     {
     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)