This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[patch] empty base class optimization completed in stl_tree.h
- From: "Maxim Yegorushkin" <maxim dot yegorushkin at gmail dot com>
- To: gcc-patches at gcc dot gnu dot org, libstdc++ at gcc dot gnu dot org
- Date: Wed, 10 Jan 2007 10:04:58 +0000
- Subject: [patch] empty base class optimization completed in stl_tree.h
Hi,
It looks like an intended empty base class optimization has not been
finished for struct _Rb_tree_impl in stl_tree.h. If it is so indeed,
this patch completes it.
main trunk:
sizeof(std::set<int>) == 72
sizeof(std::set<int, bool(*)(int, int)>) == 72
with patch applied:
sizeof(std::set<int>) == 64
sizeof(std::set<int, bool(*)(int, int)>) == 72
Compile tested only.
--- libstdc++-v3/include/bits/stl_tree.h 2007-01-07 22:20:10.000000000 +0000
+++ libstdc++-v3/include/bits/stl_tree.h 2007-01-09 21:35:49.000000000 +0000
@@ -395,15 +395,14 @@
protected:
template<typename _Key_compare,
bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
- struct _Rb_tree_impl : public _Node_allocator
+ struct _Rb_tree_impl : _Node_allocator, _Key_compare
{
- _Key_compare _M_key_compare;
_Rb_tree_node_base _M_header;
size_type _M_node_count; // Keeps track of size of tree.
_Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
const _Key_compare& __comp = _Key_compare())
- : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
+ : _Node_allocator(__a), _Key_compare(__comp), _M_header(),
_M_node_count(0)
{
this->_M_header._M_color = _S_red;
@@ -411,12 +410,15 @@
this->_M_header._M_left = &this->_M_header;
this->_M_header._M_right = &this->_M_header;
}
+
+ _Key_compare& _M_comp() { return *this; }
+ _Key_compare const& _M_comp() const { return *this; }
};
// Specialization for _Comparison types that are not capable of
// being base classes / super classes.
template<typename _Key_compare>
- struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
+ struct _Rb_tree_impl<_Key_compare, true> : _Node_allocator
{
_Key_compare _M_key_compare;
_Rb_tree_node_base _M_header;
@@ -432,6 +434,9 @@
this->_M_header._M_left = &this->_M_header;
this->_M_header._M_right = &this->_M_header;
}
+
+ _Key_compare& _M_comp() { return _M_key_compare; }
+ _Key_compare const& _M_comp() const { return _M_key_compare; }
};
_Rb_tree_impl<_Compare> _M_impl;
@@ -579,7 +584,7 @@
{ }
_Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
- : _M_impl(__x._M_get_Node_allocator(), __x._M_impl._M_key_compare)
+ : _M_impl(__x._M_get_Node_allocator(), __x._M_impl._M_comp())
{
if (__x._M_root() != 0)
{
@@ -599,7 +604,7 @@
// Accessors.
_Compare
key_comp() const
- { return _M_impl._M_key_compare; }
+ { return _M_impl._M_comp(); }
iterator
begin()
@@ -810,7 +815,7 @@
{
// Note that _Key may be a constant type.
clear();
- _M_impl._M_key_compare = __x._M_impl._M_key_compare;
+ _M_impl._M_comp() = __x._M_impl._M_comp();
if (__x._M_root() != 0)
{
_M_root() = _M_copy(__x._M_begin(), _M_end());
@@ -829,7 +834,7 @@
_M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
{
bool __insert_left = (__x != 0 || __p == _M_end()
- || _M_impl._M_key_compare(_KeyOfValue()(__v),
+ || _M_impl._M_comp()(_KeyOfValue()(__v),
_S_key(__p)));
_Link_type __z = _M_create_node(__v);
@@ -848,7 +853,7 @@
_M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
{
bool __insert_left = (__x != 0 || __p == _M_end()
- || !_M_impl._M_key_compare(_S_key(__p),
+ || !_M_impl._M_comp()(_S_key(__p),
_KeyOfValue()(__v)));
_Link_type __z = _M_create_node(__v);
@@ -870,7 +875,7 @@
while (__x != 0)
{
__y = __x;
- __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
+ __x = !_M_impl._M_comp()(_S_key(__x), _KeyOfValue()(__v)) ?
_S_left(__x) : _S_right(__x);
}
return _M_insert_lower(__x, __y, __v);
@@ -936,7 +941,7 @@
const _Key& __k) const
{
while (__x != 0)
- if (!_M_impl._M_key_compare(_S_key(__x), __k))
+ if (!_M_impl._M_comp()(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
@@ -951,7 +956,7 @@
const _Key& __k) const
{
while (__x != 0)
- if (_M_impl._M_key_compare(__k, _S_key(__x)))
+ if (_M_impl._M_comp()(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
@@ -970,9 +975,9 @@
_Const_Link_type __y = _M_end();
while (__x != 0)
{
- if (_M_impl._M_key_compare(_S_key(__x), __k))
+ if (_M_impl._M_comp()(_S_key(__x), __k))
__x = _S_right(__x);
- else if (_M_impl._M_key_compare(__k, _S_key(__x)))
+ else if (_M_impl._M_comp()(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
{
@@ -1029,7 +1034,7 @@
}
// No need to swap header's color as it does not change.
std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
- std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
+ std::swap(this->_M_impl._M_comp(), __t._M_impl._M_comp());
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 431. Swapping containers with unequal allocators.
@@ -1050,7 +1055,7 @@
while (__x != 0)
{
__y = __x;
- __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
+ __comp = _M_impl._M_comp()(_KeyOfValue()(__v), _S_key(__x));
__x = __comp ? _S_left(__x) : _S_right(__x);
}
iterator __j = iterator(__y);
@@ -1061,7 +1066,7 @@
else
--__j;
}
- if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
+ if (_M_impl._M_comp()(_S_key(__j._M_node), _KeyOfValue()(__v)))
return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
return pair<iterator, bool>(__j, false);
}
@@ -1077,7 +1082,7 @@
while (__x != 0)
{
__y = __x;
- __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
+ __x = _M_impl._M_comp()(_KeyOfValue()(__v), _S_key(__x)) ?
_S_left(__x) : _S_right(__x);
}
return _M_insert_(__x, __y, __v);
@@ -1093,20 +1098,20 @@
if (__position._M_node == _M_end())
{
if (size() > 0
- && _M_impl._M_key_compare(_S_key(_M_rightmost()),
+ && _M_impl._M_comp()(_S_key(_M_rightmost()),
_KeyOfValue()(__v)))
return _M_insert_(0, _M_rightmost(), __v);
else
return _M_insert_unique(__v).first;
}
- else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
+ else if (_M_impl._M_comp()(_KeyOfValue()(__v),
_S_key(__position._M_node)))
{
// First, try before...
const_iterator __before = __position;
if (__position._M_node == _M_leftmost()) // begin()
return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
- else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
+ else if (_M_impl._M_comp()(_S_key((--__before)._M_node),
_KeyOfValue()(__v)))
{
if (_S_right(__before._M_node) == 0)
@@ -1118,14 +1123,14 @@
else
return _M_insert_unique(__v).first;
}
- else if (_M_impl._M_key_compare(_S_key(__position._M_node),
+ else if (_M_impl._M_comp()(_S_key(__position._M_node),
_KeyOfValue()(__v)))
{
// ... then try after.
const_iterator __after = __position;
if (__position._M_node == _M_rightmost())
return _M_insert_(0, _M_rightmost(), __v);
- else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
+ else if (_M_impl._M_comp()(_KeyOfValue()(__v),
_S_key((++__after)._M_node)))
{
if (_S_right(__position._M_node) == 0)
@@ -1152,20 +1157,20 @@
if (__position._M_node == _M_end())
{
if (size() > 0
- && !_M_impl._M_key_compare(_KeyOfValue()(__v),
+ && !_M_impl._M_comp()(_KeyOfValue()(__v),
_S_key(_M_rightmost())))
return _M_insert_(0, _M_rightmost(), __v);
else
return _M_insert_equal(__v);
}
- else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
+ else if (!_M_impl._M_comp()(_S_key(__position._M_node),
_KeyOfValue()(__v)))
{
// First, try before...
const_iterator __before = __position;
if (__position._M_node == _M_leftmost()) // begin()
return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
- else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
+ else if (!_M_impl._M_comp()(_KeyOfValue()(__v),
_S_key((--__before)._M_node)))
{
if (_S_right(__before._M_node) == 0)
@@ -1183,7 +1188,7 @@
const_iterator __after = __position;
if (__position._M_node == _M_rightmost())
return _M_insert_(0, _M_rightmost(), __v);
- else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
+ else if (!_M_impl._M_comp()(_S_key((++__after)._M_node),
_KeyOfValue()(__v)))
{
if (_S_right(__position._M_node) == 0)
@@ -1302,7 +1307,7 @@
{
iterator __j = iterator(_M_lower_bound(_M_begin(), _M_end(), __k));
return (__j == end()
- || _M_impl._M_key_compare(__k,
+ || _M_impl._M_comp()(__k,
_S_key(__j._M_node))) ? end() : __j;
}
@@ -1315,7 +1320,7 @@
const_iterator __j = const_iterator(_M_lower_bound(_M_begin(),
_M_end(), __k));
return (__j == end()
- || _M_impl._M_key_compare(__k,
+ || _M_impl._M_comp()(__k,
_S_key(__j._M_node))) ? end() : __j;
}
@@ -1356,9 +1361,9 @@
|| (__R && __R->_M_color == _S_red))
return false;
- if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
+ if (__L && _M_impl._M_comp()(_S_key(__x), _S_key(__L)))
return false;
- if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
+ if (__R && _M_impl._M_comp()(_S_key(__R), _S_key(__x)))
return false;
if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)