This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Slightly less trivial clean-up patch for stl_tree
Hi Paolo,
Ok well here's a patch which attempts to clean things up a bit and which
I think does not change the ABI.
The patch attached has the following changes:
* Removal of declarations of _Rb_tree_rotate_left() and
_Rb_tree_rotate_right() functions, as before.
* iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type&
__v) and
const_iterator _M_insert(_Const_Base_ptr __x, _Const_Base_ptr
__y,const value_type& __v) replaced with
iterator _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,const
value_type& __v)
* iterator _M_insert_unique(iterator __position, const value_type&
__x) and
const_iterator _M_insert_unique(const_iterator __position, const
value_type& __x) replaced with
iterator _M_insert_unique(const_iterator __position, const
value_type& __x)
* iterator _M_insert_equal(iterator __position, const value_type&
__x) and
const_iterator _M_insert_equal(const_iterator __position, const
value_type& __x) replaced with
iterator _M_insert_equal(const_iterator __position, const
value_type& __x)
This patch uses the fact that non-const parameters and return values can
be automatically converted to const versions to avoid having two
different versions of the functions.
There is only one disgusting thing about this patch, and that's the
following change:
- return __position; // Equivalent keys.
+ // Equivalent keys.
+ return iterator(static_cast<_Link_type>
+ (const_cast<_Base_ptr>
+ (__position._M_node)));
This change comes about from the fact that a constant input parameter
(__position) needs to be passed back as a non-constant return value.
Although I admit it's not nice to have to do this, I've thought about
the alternatives and they add complexity and would need changes to
stl_set.h, stl_multiset.h, stl_map.h and stl_multimap.h.
This patch removes a total of 135 lines from stl_tree.h.
Cheers,
Gawain
Paolo Carlini wrote:
As you may have noticed, at some point, very close to a release, we
had a wrong code bug due to an incorrect, very hacky cast in the SGI
code. I fixed it quickly introducing duplication in the various insert
with hint taking iterator and const_iterator. That should be be
definitely improved. Also, when I fixed 22102 (i.e., implemented DR
233) on top of that suboptimal infrastructure, probably I made the
situation slightly worse.
Index: stl_tree.h
===================================================================
--- stl_tree.h (revision 115800)
+++ stl_tree.h (working copy)
@@ -306,14 +306,6 @@
{ return __x._M_node != __y._M_node; }
void
- _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
- _Rb_tree_node_base*& __root);
-
- void
- _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
- _Rb_tree_node_base*& __root);
-
- void
_Rb_tree_insert_and_rebalance(const bool __insert_left,
_Rb_tree_node_base* __x,
_Rb_tree_node_base* __p,
@@ -545,15 +537,12 @@
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
private:
- iterator
- _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
-
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 233. Insertion hints in associative containers.
iterator
_M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
- const_iterator
+ iterator
_M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,
const value_type& __v);
@@ -668,15 +657,9 @@
_M_insert_equal_lower(const value_type& __x);
iterator
- _M_insert_unique(iterator __position, const value_type& __x);
-
- const_iterator
_M_insert_unique(const_iterator __position, const value_type& __x);
iterator
- _M_insert_equal(iterator __position, const value_type& __x);
-
- const_iterator
_M_insert_equal(const_iterator __position, const value_type& __x);
template<typename _InputIterator>
@@ -829,24 +812,6 @@
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
- {
- bool __insert_left = (__x != 0 || __p == _M_end()
- || _M_impl._M_key_compare(_KeyOfValue()(__v),
- _S_key(__p)));
-
- _Link_type __z = _M_create_node(__v);
-
- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
- this->_M_impl._M_header);
- ++_M_impl._M_node_count;
- return iterator(__z);
- }
-
- template<typename _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
{
bool __insert_left = (__x != 0 || __p == _M_end()
@@ -863,7 +828,7 @@
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
{
@@ -877,7 +842,7 @@
const_cast<_Base_ptr>(__p),
this->_M_impl._M_header);
++_M_impl._M_node_count;
- return const_iterator(__z);
+ return iterator(__z);
}
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -995,7 +960,7 @@
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_insert_unique(iterator __position, const _Val& __v)
+ _M_insert_unique(const_iterator __position, const _Val& __v)
{
// end()
if (__position._M_node == _M_end())
@@ -1011,7 +976,7 @@
_S_key(__position._M_node)))
{
// First, try before...
- iterator __before = __position;
+ 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),
@@ -1030,7 +995,7 @@
_KeyOfValue()(__v)))
{
// ... then try after.
- iterator __after = __position;
+ 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),
@@ -1045,71 +1010,17 @@
return _M_insert_unique(__v).first;
}
else
- return __position; // Equivalent keys.
+ // Equivalent keys.
+ return iterator(static_cast<_Link_type>
+ (const_cast<_Base_ptr>
+ (__position._M_node)));
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_insert_unique(const_iterator __position, const _Val& __v)
- {
- // end()
- if (__position._M_node == _M_end())
- {
- if (size() > 0
- && _M_impl._M_key_compare(_S_key(_M_rightmost()),
- _KeyOfValue()(__v)))
- return _M_insert(0, _M_rightmost(), __v);
- else
- return const_iterator(_M_insert_unique(__v).first);
- }
- else if (_M_impl._M_key_compare(_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),
- _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 const_iterator(_M_insert_unique(__v).first);
- }
- else if (_M_impl._M_key_compare(_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),
- _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 const_iterator(_M_insert_unique(__v).first);
- }
- else
- return __position; // Equivalent keys.
- }
-
- template<typename _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_insert_equal(iterator __position, const _Val& __v)
+ _M_insert_equal(const_iterator __position, const _Val& __v)
{
// end()
if (__position._M_node == _M_end())
@@ -1125,7 +1036,7 @@
_KeyOfValue()(__v)))
{
// First, try before...
- iterator __before = __position;
+ 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),
@@ -1143,7 +1054,7 @@
else
{
// ... then try after.
- iterator __after = __position;
+ 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),
@@ -1159,60 +1070,6 @@
}
}
- template<typename _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_insert_equal(const_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 const_iterator(_M_insert_equal(__v));
- }
- else if (!_M_impl._M_key_compare(_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),
- _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 const_iterator(_M_insert_equal(__v));
- }
- else
- {
- // ... 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(_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 const_iterator(_M_insert_equal_lower(__v));
- }
- }
-
template<typename _Key, typename _Val, typename _KoV,
typename _Cmp, typename _Alloc>
template<class _II>