This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [Patch] Performance and memory usage improvements for stl_tree.h
Nathan Myers wrote:
On Wed, Feb 26, 2003 at 06:05:13PM +0100, Gawain Bolton wrote:
Nathan Myers wrote:
On Sat, Feb 22, 2003 at 03:24:43PM +0100, Gawain Bolton wrote:
This is an updated patch to improve stl_tree.h. It affects the
std::map, std::multimap, std::set and std::multiset container types.
I vote to put this one in immediately. The only think I'd fix along
the way is some of the comments that go beyond 80 columns.
Thanks for your comments Nathan. I have fixed the problem concerning
comments beyond 80 columns and removed the use of static_cast<> as this
increased the size of generated code bloat and is therefore probably
less efficient than a C style cast.
If a C-style cast produced different object code than the static_cast<>,
that probably indicates an error. We like static_cast<> because it's
easier to find with grep, and ugly enough that you try to avoid a need
to do it at all.
Nathan Myers
ncm at cantrip dot org
Ok I checked this out and it turns out the code size was indeed reduced
in the last patch, but it had nothing to do with static_cast<> vs. C
style cast. Strange.
So here is yet another patch using static_cast<> for the new code. The
existing code could be cleaned up in several ways, such as using
static_cast<> elsewhere rather than C style casts. I have tried to
refrain from doing this to keep the purppose of this patch focused. I
am also trying to figure out how to contribute improvements to libstdc++
and so want to start with something simple.
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 26 Feb 2003 21:42:27 -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,14 +644,17 @@
_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() { return static_cast<_Link_type>(&this->_M_header); }
+
static _Link_type&
_S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); }
@@ -668,9 +670,6 @@
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 @@
_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 @@
_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
- // __root, in iterator.operator++
+ // Used to distinguish header from __root, in iterator.operator++
+ _S_color(&this->_M_header) = _M_red;
_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; }
+ const_iterator
+ end() const { return const_cast<_Base_ptr>(&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 = _M_end();
_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 = _M_end();
_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 = _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 +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 = _M_end(); // 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 = _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 +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 = _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 +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 = _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 +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 = _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 +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)