This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch] Performance and memory usage improvements for stl_tree.h
- From: Gawain Bolton <gp dot bolton at computer dot org>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
- Date: Sat, 22 Feb 2003 15:24:43 +0100
- Subject: [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)