This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Suggested improvement to stl_tree.h
- From: "Gawain Bolton" <boltong at nortelnetworks dot com>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Thu, 13 Feb 2003 15:26:45 +0100
- Subject: Suggested improvement to stl_tree.h
- Organization: Nortel Networks
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)