This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [Patch] libstdc++/22102 (Re: Hunting for performance...)
Paolo Carlini wrote:
>2005-06-XX Paolo Carlini <pcarlini@suse.de>
>
> PR libstdc++/22102
> * include/bits/stl_tree.h (insert_unique(iterator, const _Val&),
> insert_equal((iterator, const _Val&)): Reimplement to check both
> before and after, as per the algorithm "ignore hint if wrong" of
> ISO paper N1780.
>
>
Actually, the below slightly simpler variant is also ok, because, when
the tree is empty, _M_rightmost() == _M_leftmost() == _M_end().
Tested x86-linux.
Paolo.
//////////////
Index: stl_tree.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_tree.h,v
retrieving revision 1.45
diff -p -r1.45 stl_tree.h
*** stl_tree.h 26 Feb 2005 23:33:44 -0000 1.45
--- stl_tree.h 19 Jun 2005 12:37:02 -0000
*************** namespace std
*** 893,900 ****
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_unique(iterator __position, const _Val& __v)
{
! if (__position._M_node == _M_end()
! || __position._M_node == _M_rightmost())
{
if (size() > 0
&& _M_impl._M_key_compare(_S_key(_M_rightmost()),
--- 893,900 ----
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_unique(iterator __position, const _Val& __v)
{
! // end()
! if (__position._M_node == _M_end())
{
if (size() > 0
&& _M_impl._M_key_compare(_S_key(_M_rightmost()),
*************** namespace std
*** 903,926 ****
else
return insert_unique(__v).first;
}
! else
{
iterator __after = __position;
! ++__after;
! if (_M_impl._M_key_compare(_S_key(__position._M_node),
! _KeyOfValue()(__v))
! && _M_impl._M_key_compare(_KeyOfValue()(__v),
! _S_key(__after._M_node)))
{
if (_S_right(__position._M_node) == 0)
return _M_insert(0, __position._M_node, __v);
else
return _M_insert(__after._M_node, __after._M_node, __v);
- // First argument just needs to be non-null.
}
else
return insert_unique(__v).first;
}
}
template<typename _Key, typename _Val, typename _KeyOfValue,
--- 903,947 ----
else
return insert_unique(__v).first;
}
! else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
! _S_key(__position._M_node)))
{
+ // First, try before...
+ 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),
+ _KeyOfValue()(__v)))
+ {
+ if (_S_right(__before._M_node) == 0)
+ return _M_insert(0, __before._M_node, __v);
+ else
+ return _M_insert(__position._M_node,
+ __position._M_node, __v);
+ }
+ else
+ return insert_unique(__v).first;
+ }
+ else if (_M_impl._M_key_compare(_S_key(__position._M_node),
+ _KeyOfValue()(__v)))
+ {
+ // ... then try after.
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),
! _S_key((++__after)._M_node)))
{
if (_S_right(__position._M_node) == 0)
return _M_insert(0, __position._M_node, __v);
else
return _M_insert(__after._M_node, __after._M_node, __v);
}
else
return insert_unique(__v).first;
}
+ else
+ return __position; // Equivalent keys.
}
template<typename _Key, typename _Val, typename _KeyOfValue,
*************** namespace std
*** 929,958 ****
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_equal(iterator __position, const _Val& __v)
{
! if (__position._M_node == _M_end()
! || __position._M_node == _M_rightmost())
{
if (size() > 0
! && !_M_impl._M_key_compare(_KeyOfValue()(__v),
_S_key(_M_rightmost())))
return _M_insert(0, _M_rightmost(), __v);
else
return insert_equal(__v);
}
else
{
iterator __after = __position;
! ++__after;
! if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
! _S_key(__position._M_node))
! && !_M_impl._M_key_compare(_S_key(__after._M_node),
! _KeyOfValue()(__v)))
{
if (_S_right(__position._M_node) == 0)
return _M_insert(0, __position._M_node, __v);
else
return _M_insert(__after._M_node, __after._M_node, __v);
- // First argument just needs to be non-null.
}
else
return insert_equal(__v);
--- 950,997 ----
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_equal(iterator __position, const _Val& __v)
{
! // end()
! if (__position._M_node == _M_end())
{
if (size() > 0
! && !_M_impl._M_key_compare(_KeyOfValue()(__v),
_S_key(_M_rightmost())))
return _M_insert(0, _M_rightmost(), __v);
else
return insert_equal(__v);
}
+ else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
+ _KeyOfValue()(__v)))
+ {
+ // First, try before...
+ 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),
+ _S_key((--__before)._M_node)))
+ {
+ if (_S_right(__before._M_node) == 0)
+ return _M_insert(0, __before._M_node, __v);
+ else
+ return _M_insert(__position._M_node,
+ __position._M_node, __v);
+ }
+ else
+ return insert_equal(__v);
+ }
else
{
+ // ... then try after.
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),
! _KeyOfValue()(__v)))
{
if (_S_right(__position._M_node) == 0)
return _M_insert(0, __position._M_node, __v);
else
return _M_insert(__after._M_node, __after._M_node, __v);
}
else
return insert_equal(__v);