Here is the patch to extend DR 526 to forward_list and list remove_if
and unique.
As the adopted pattern is simpler I also applied it to the remove methods.
PR libstdc++/91620
* include/bits/forward_list.tcc (forward_list<>::remove): Collect nodes
to destroy in an intermediate forward_list.
(forward_list<>::remove_if, forward_list<>::unique): Likewise.
* include/bits/list.tcc (list<>::remove, list<>::unique): Likewise.
(list<>::remove_if): Likewise.
* include/debug/forward_list (forward_list<>::_M_erase_after): Remove.
(forward_list<>::erase_after): Adapt.
(forward_list<>::remove, forward_list<>::remove_if): Collect nodes to
destroy in an intermediate forward_list.
(forward_list<>::unique): Likewise.
* include/debug/list (list<>::remove, list<>::unique): Likewise.
(list<>::remove_if): Likewise.
Tested under Linux x86_64 normal and debug modes.
Ok to commit ?
François
diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index 088111e3330..70de7e75a43 100644
--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -290,30 +290,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
remove(const _Tp& __val) -> __remove_return_type
{
size_type __removed __attribute__((__unused__)) = 0;
- _Node_base* __curr = &this->_M_impl._M_head;
- _Node_base* __extra = nullptr;
+ forward_list __to_destroy(get_allocator());
- while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
- {
+ auto __prev_it = cbefore_begin();
+ while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
if (*__tmp->_M_valptr() == __val)
{
- if (__tmp->_M_valptr() != std::__addressof(__val))
- {
- this->_M_erase_after(__curr);
+ __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+ *this, __prev_it);
_GLIBCXX20_ONLY( __removed++ );
- continue;
}
else
- __extra = __curr;
- }
- __curr = __curr->_M_next;
- }
+ ++__prev_it;
- if (__extra)
- {
- this->_M_erase_after(__extra);
- _GLIBCXX20_ONLY( __removed++ );
- }
return _GLIBCXX20_ONLY( __removed );
}
@@ -324,17 +313,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
remove_if(_Pred __pred) -> __remove_return_type
{
size_type __removed __attribute__((__unused__)) = 0;
- _Node_base* __curr = &this->_M_impl._M_head;
- while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
- {
+ forward_list __to_destroy(get_allocator());
+
+ auto __prev_it = cbefore_begin();
+ while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
if (__pred(*__tmp->_M_valptr()))
{
- this->_M_erase_after(__curr);
+ __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+ *this, __prev_it);
_GLIBCXX20_ONLY( __removed++ );
}
else
- __curr = __curr->_M_next;
- }
+ ++__prev_it;
+
return _GLIBCXX20_ONLY( __removed );
}
@@ -348,19 +339,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
iterator __last = end();
if (__first == __last)
return _GLIBCXX20_ONLY(0);
+
+ forward_list __to_destroy(get_allocator());
size_type __removed __attribute__((__unused__)) = 0;
iterator __next = __first;
while (++__next != __last)
{
if (__binary_pred(*__first, *__next))
{
- erase_after(__first);
+ __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+ *this, __first);
_GLIBCXX20_ONLY( __removed++ );
}
else
__first = __next;
__next = __first;
}
+
return _GLIBCXX20_ONLY( __removed );
}
diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
index 0ac6654b079..5a6fd5b0824 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -331,10 +331,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
list<_Tp, _Alloc>::
remove(const value_type& __value)
{
+#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
+#endif
+ list __to_destroy(get_allocator());
iterator __first = begin();
iterator __last = end();
- iterator __extra = __last;
while (__first != __last)
{
iterator __next = __first;
@@ -344,22 +346,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 526. Is it undefined if a function in the standard changes
// in parameters?
- if (std::__addressof(*__first) != std::__addressof(__value))
- {
- _M_erase(__first);
+ __to_destroy.splice(__to_destroy.begin(), *this, __first);
+#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
+#endif
}
- else
- __extra = __first;
- }
+
__first = __next;
}
- if (__extra != __last)
- {
- _M_erase(__extra);
- _GLIBCXX20_ONLY( __removed++ );
- }
+
+#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
+#else
+ return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
}
template<typename _Tp, typename _Alloc>
@@ -371,20 +371,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
iterator __last = end();
if (__first == __last)
return _GLIBCXX20_ONLY( 0 );
+#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
+#endif
+ list __to_destroy(get_allocator());
iterator __next = __first;
while (++__next != __last)
{
if (*__first == *__next)
{
- _M_erase(__next);
+ __to_destroy.splice(__to_destroy.begin(), *this, __next);
+#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
+#endif
}
else
__first = __next;
__next = __first;
}
+
+#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
+#else
+ return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
}
template<typename _Tp, typename _Alloc>
@@ -533,7 +543,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
list<_Tp, _Alloc>::
remove_if(_Predicate __pred)
{
+#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
+#endif
+ list __to_destroy(get_allocator());
iterator __first = begin();
iterator __last = end();
while (__first != __last)
@@ -542,12 +555,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
++__next;
if (__pred(*__first))
{
- _M_erase(__first);
+ __to_destroy.splice(__to_destroy.begin(), *this, __first);
+#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
+#endif
}
__first = __next;
}
+
+#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
+#else
+ return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
}
template<typename _Tp, typename _Alloc>
@@ -560,20 +580,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
iterator __last = end();
if (__first == __last)
return _GLIBCXX20_ONLY(0);
+#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
+#endif
+ list __to_destroy(get_allocator());
iterator __next = __first;
while (++__next != __last)
{
if (__binary_pred(*__first, *__next))
{
- _M_erase(__next);
+ __to_destroy.splice(__to_destroy.begin(), *this, __next);
+#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
+#endif
}
else
__first = __next;
__next = __first;
}
+
+#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
+#else
+ return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
}
#undef _GLIBCXX20_ONLY
diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index f1756ddec9d..9889eb9da83 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -442,21 +442,15 @@ namespace __debug
return { _Base::insert_after(__pos.base(), __il), this };
}
- private:
- _Base_iterator
- _M_erase_after(_Base_const_iterator __pos)
- {
- _Base_const_iterator __next = std::next(__pos);
- this->_M_invalidate_if([__next](_Base_const_iterator __it)
- { return __it == __next; });
- return _Base::erase_after(__pos);
- }
- public:
iterator
erase_after(const_iterator __pos)
{
__glibcxx_check_erase_after(__pos);
- return { _M_erase_after(__pos.base()), this };
+
+ _Base_const_iterator __next = std::next(__pos.base());
+ this->_M_invalidate_if([__next](_Base_const_iterator __it)
+ { return __it == __next; });
+ return { _Base::erase_after(__pos.base()), this };
}
iterator
@@ -681,29 +675,23 @@ namespace __debug
return _Base::remove(__val);
size_type __removed __attribute__((__unused__)) = 0;
- _Base_iterator __x = _Base::before_begin();
- _Base_iterator __old = __x++;
- _Base_iterator __extra = _Base::end();
- while (__x != _Base::end())
+ _Base __to_destroy(get_allocator());
+ _Base_const_iterator __x = _Base::cbefore_begin();
+ _Base_const_iterator __old = __x++;
+ while (__x != _Base::cend())
{
if (*__x == __val)
{
- if (std::__addressof(*__x) != std::__addressof(__val))
- {
- __x = _M_erase_after(__old);
+ _Base_const_iterator __next = std::next(__old);
+ this->_M_invalidate_if([__next](_Base_const_iterator __it)
+ { return __it == __next; });
+ __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+ _M_base(), __old);
+ __x = __old;
_GLIBCXX20_ONLY( __removed++ );
- continue;
- }
- else
- __extra = __old;
- }
- __old = __x++;
}
- if (__extra != _Base::end())
- {
- this->_M_erase_after(__extra);
- _GLIBCXX20_ONLY( __removed++ );
+ __old = __x++;
}
return _GLIBCXX20_ONLY( __removed );
@@ -717,16 +705,23 @@ namespace __debug
return _Base::remove_if(__pred);
size_type __removed __attribute__((__unused__)) = 0;
+ _Base __to_destroy(get_allocator());
_Base_iterator __x = _Base::before_begin();
_Base_iterator __old = __x++;
while (__x != _Base::end())
+ {
if (__pred(*__x))
{
- __x = _M_erase_after(__old);
+ this->_M_invalidate_if([__x](_Base_const_iterator __it)
+ { return __it == __x; });
+ __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+ _M_base(), __old);
+ __x = __old;
_GLIBCXX20_ONLY( __removed++ );
}
- else
+
__old = __x++;
+ }
return _GLIBCXX20_ONLY( __removed );
}
@@ -743,21 +738,26 @@ namespace __debug
if (!this->_M_iterators && !this->_M_const_iterators)
return _Base::unique(__binary_pred);
- _Base_iterator __first = _Base::begin();
- _Base_iterator __last = _Base::end();
+ _Base_const_iterator __first = _Base::cbegin();
+ _Base_const_iterator __last = _Base::cend();
if (__first == __last)
return _GLIBCXX20_ONLY(0);
size_type __removed __attribute__((__unused__)) = 0;
- _Base_iterator __next = std::next(__first);
+ _Base __to_destroy(get_allocator());
+ _Base_const_iterator __next = std::next(__first);
while (__next != __last)
{
if (__binary_pred(*__first, *__next))
{
- __next = _M_erase_after(__first);
+ this->_M_invalidate_if([__next](_Base_const_iterator __it)
+ { return __it == __next; });
+ __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+ _M_base(), __first);
+ __next = __first;
_GLIBCXX20_ONLY( __removed++ );
}
- else
+
__first = __next++;
}
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index 140546a633e..bc4895405d1 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -671,36 +671,36 @@ namespace __debug
if (!this->_M_iterators && !this->_M_const_iterators)
return _Base::remove(__value);
+#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
+#endif
+ _Base __to_destroy(get_allocator());
_Base_iterator __first = _Base::begin();
_Base_iterator __last = _Base::end();
- _Base_iterator __extra = __last;
while (__first != __last)
{
+ _Base_iterator __next = __first;
+ ++__next;
if (*__first == __value)
+ {
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 526. Is it undefined if a function in the standard changes
// in parameters?
- if (std::__addressof(*__first) != std::__addressof(__value))
- {
- __first = _M_erase(__first);
+ this->_M_invalidate_if(_Equal(__first));
+ __to_destroy.splice(__to_destroy.begin(), _M_base(), __first);
+#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
- }
- else
- {
- __extra = __first;
- ++__first;
- }
- else
- ++__first;
+#endif
}
- if (__extra != __last)
- {
- _M_erase(__extra);
- _GLIBCXX20_ONLY( __removed++ );
+ __first = __next;
}
+
+#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
+#else
+ return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
}
template<class _Predicate>
@@ -710,17 +710,31 @@ namespace __debug
if (!this->_M_iterators && !this->_M_const_iterators)
return _Base::remove_if(__pred);
+#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
+#endif
+ _Base __to_destroy(get_allocator());
for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
+ {
+ _Base_iterator __next = __x;
+ ++__next;
if (__pred(*__x))
{
- __x = _M_erase(__x);
+ this->_M_invalidate_if(_Equal(__x));
+ __to_destroy.splice(__to_destroy.begin(), _M_base(), __x);
+#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
+#endif
+ }
+
+ __x = __next;
}
- else
- ++__x;
+#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
+#else
+ return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
}
_GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
@@ -733,21 +747,31 @@ namespace __debug
if (empty())
return _GLIBCXX20_ONLY(0);
+#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
+#endif
+ _Base __to_destroy(get_allocator());
_Base_iterator __first = _Base::begin();
_Base_iterator __last = _Base::end();
_Base_iterator __next = __first;
while (++__next != __last)
if (*__first == *__next)
{
- _M_erase(__next);
+ this->_M_invalidate_if(_Equal(__next));
+ __to_destroy.splice(__to_destroy.begin(), _M_base(), __next);
__next = __first;
+#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
+#endif
}
else
__first = __next;
+#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
+#else
+ return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
}
template<class _BinaryPredicate>
@@ -760,21 +784,32 @@ namespace __debug
if (empty())
return _GLIBCXX20_ONLY(0);
+
+#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
+#endif
+ _Base __to_destroy(get_allocator());
_Base_iterator __first = _Base::begin();
_Base_iterator __last = _Base::end();
- _Base_iterator __next = __first;;
+ _Base_iterator __next = __first;
while (++__next != __last)
if (__binary_pred(*__first, *__next))
{
- _M_erase(__next);
+ this->_M_invalidate_if(_Equal(__next));
+ __to_destroy.splice(__to_destroy.begin(), _M_base(), __next);
__next = __first;
+#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
+#endif
}
else
__first = __next;
+#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
+#else
+ return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
}
#undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG