On 11/08/20 10:11 +0100, Jonathan Wakely wrote:
On 27/12/19 11:57 +0100, François Dumont wrote:
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
The point of the _GLIBCXX20_ONLY macro was to avoid cluttering this
function with #ifdef directives. If it's going to be full of #ifdef
now anyway, there's no real benefit to using _GLIBCXX20_ONLY.
This could now be:
#if __cplusplus > 201703L && ! _GLIBCXX_USE_CXX11_ABI
__removed++;
#endif
and so on.
}
- 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
Although this becomes pretty ugly:
#if __cplusplus > 201703L
# if _GLIBCXX_USE_CXX11_ABI
return __to_destroy.size();
# else
return __removed;
# endif
#endif
So maybe _GLIBCXX20_ONLY is still worthwhile.
The other alternative would be to define a new type right at the start
which keeps count if needed:
#if __cplusplus > 201703L && ! _GLIBCXX_USE_CXX11_ABI
struct _VictimList : list
{
void splice(list::iterator __p, list& __x, list::iterator __i)
{
list::splice(__p, __x, __i);
++_M_size;
}
size_type size() const { return _M_size; }
size_type _M_size = 0;
} __to_destroy;
#else
list __to_destroy;
#endif
// ...
return _GLIBCXX20_ONLY(__to_destroy.size());
With this the only conditional compilation is at the start of the
function and the one use of _GLIBCXX20_ONLY at the end. The rest of
the function body has no #if or macros at all.
Your patch is OK for master. We can revisit it later to tidy it up.
Oops, I meant to reply to the patch with tests of course, not the
original one. Please do commit the tests.
