* [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique
@ 2019-12-27 15:54 François Dumont
2020-03-03 5:42 ` François Dumont
` (2 more replies)
0 siblings, 3 replies; 7+ messages in thread
From: François Dumont @ 2019-12-27 15:54 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1072 bytes --]
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
[-- Attachment #2: 91620.patch --]
[-- Type: text/x-patch, Size: 14757 bytes --]
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
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique 2019-12-27 15:54 [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique François Dumont @ 2020-03-03 5:42 ` François Dumont 2020-03-03 21:33 ` Jonathan Wakely 2020-08-10 19:07 ` François Dumont 2020-08-11 9:10 ` Jonathan Wakely 2 siblings, 1 reply; 7+ messages in thread From: François Dumont @ 2020-03-03 5:42 UTC (permalink / raw) To: libstdc++, gcc-patches Hi Isn't it something to fix before gcc 10 release ? François On 12/27/19 11:57 AM, 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 > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique 2020-03-03 5:42 ` François Dumont @ 2020-03-03 21:33 ` Jonathan Wakely 2020-03-03 21:37 ` Jonathan Wakely 0 siblings, 1 reply; 7+ messages in thread From: Jonathan Wakely @ 2020-03-03 21:33 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 03/03/20 06:42 +0100, François Dumont wrote: >Hi > > Isn't it something to fix before gcc 10 release ? No, I don't think so. It's not a regression. ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique 2020-03-03 21:33 ` Jonathan Wakely @ 2020-03-03 21:37 ` Jonathan Wakely 0 siblings, 0 replies; 7+ messages in thread From: Jonathan Wakely @ 2020-03-03 21:37 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 03/03/20 21:32 +0000, Jonathan Wakely wrote: >On 03/03/20 06:42 +0100, François Dumont wrote: >>Hi >> >> Isn't it something to fix before gcc 10 release ? > >No, I don't think so. It's not a regression. (And is not experimental C++20 stuff, and is not just changing tests or docs). ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique 2019-12-27 15:54 [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique François Dumont 2020-03-03 5:42 ` François Dumont @ 2020-08-10 19:07 ` François Dumont 2020-08-11 9:10 ` Jonathan Wakely 2 siblings, 0 replies; 7+ messages in thread From: François Dumont @ 2020-08-10 19:07 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 1522 bytes --] Gentle reminder, this time with tests. I've added one for list::remove cause I think there was none, for forward_list we had remove_freed.cc. I added // { dg-options "-g -O0" } in the new tests otherwise it doesn't fail, that's life with UB. I know that it can pass also with those options. If you prefer we can go without it and let Valgrind detect the issue. Whatever, once the patch is in place it doesn't fail anymore. François On 27/12/19 11:57 am, 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 > [-- Attachment #2: 91620.patch --] [-- Type: text/x-patch, Size: 21099 bytes --] diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc index c42bdc0fd13..3f94066bd55 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)) - { - if (*__tmp->_M_valptr() == __val) - { - if (__tmp->_M_valptr() != std::__addressof(__val)) - { - this->_M_erase_after(__curr); - _GLIBCXX20_ONLY( __removed++ ); - continue; - } - else - __extra = __curr; - } - __curr = __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) + { + __to_destroy.splice_after(__to_destroy.cbefore_begin(), + *this, __prev_it); + _GLIBCXX20_ONLY( __removed++ ); + } + else + ++__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)) - { - if (__pred(*__tmp->_M_valptr())) - { - this->_M_erase_after(__curr); - _GLIBCXX20_ONLY( __removed++ ); - } - else - __curr = __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())) + { + __to_destroy.splice_after(__to_destroy.cbefore_begin(), + *this, __prev_it); + _GLIBCXX20_ONLY( __removed++ ); + } + else + ++__prev_it; + return _GLIBCXX20_ONLY( __removed ); } @@ -348,20 +339,24 @@ _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 ); + + return _GLIBCXX20_ONLY( __removed ); } #undef _GLIBCXX20_ONLY diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index ce9e983c539..9b664f11454 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); - _GLIBCXX20_ONLY( __removed++ ); - } - else - __extra = __first; + __to_destroy.splice(__to_destroy.begin(), *this, __first); +#if !_GLIBCXX_USE_CXX11_ABI + _GLIBCXX20_ONLY( __removed++ ); +#endif } + __first = __next; } - if (__extra != __last) - { - _M_erase(__extra); - _GLIBCXX20_ONLY( __removed++ ); - } - return _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,21 +543,31 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER list<_Tp, _Alloc>:: remove_if(_Predicate __pred) { +#if !_GLIBCXX_USE_CXX11_ABI size_type __removed __attribute__((__unused__)) = 0; - iterator __first = begin(); - iterator __last = end(); - while (__first != __last) +#endif + list __to_destroy(get_allocator()); + iterator __first = begin(); + iterator __last = end(); + while (__first != __last) { iterator __next = __first; ++__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 fc6bf6359e9..7a00417ccb2 100644 --- a/libstdc++-v3/include/debug/forward_list +++ b/libstdc++-v3/include/debug/forward_list @@ -452,21 +452,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 @@ -691,29 +685,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); - _GLIBCXX20_ONLY( __removed++ ); - continue; - } - else - __extra = __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++ ); } - __old = __x++; - } - if (__extra != _Base::end()) - { - this->_M_erase_after(__extra); - _GLIBCXX20_ONLY( __removed++ ); + __old = __x++; } return _GLIBCXX20_ONLY( __removed ); @@ -727,16 +715,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); - _GLIBCXX20_ONLY( __removed++ ); - } - else + { + if (__pred(*__x)) + { + 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++ ); + } + __old = __x++; + } return _GLIBCXX20_ONLY( __removed ); } @@ -753,22 +748,27 @@ 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++; + + __first = __next++; } return _GLIBCXX20_ONLY( __removed ); diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list index 8f2a8cb0f01..b5652fd9fdc 100644 --- a/libstdc++-v3/include/debug/list +++ b/libstdc++-v3/include/debug/list @@ -681,36 +681,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); - _GLIBCXX20_ONLY( __removed++ ); - } - else - { - __extra = __first; - ++__first; - } - else - ++__first; - } + { + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 526. Is it undefined if a function in the standard changes + // in parameters? + this->_M_invalidate_if(_Equal(__first)); + __to_destroy.splice(__to_destroy.begin(), _M_base(), __first); +#if !_GLIBCXX_USE_CXX11_ABI + _GLIBCXX20_ONLY( __removed++ ); +#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> @@ -720,17 +720,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 } - else - ++__x; + __x = __next; + } + +#if !_GLIBCXX_USE_CXX11_ABI return _GLIBCXX20_ONLY( __removed ); +#else + return _GLIBCXX20_ONLY( __to_destroy.size() ); +#endif } _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG @@ -743,21 +757,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> @@ -770,21 +794,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; - return _GLIBCXX20_ONLY( __removed ); +#if !_GLIBCXX_USE_CXX11_ABI + return _GLIBCXX20_ONLY( __removed ); +#else + return _GLIBCXX20_ONLY( __to_destroy.size() ); +#endif } #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/operations/91620.cc b/libstdc++-v3/testsuite/23_containers/forward_list/operations/91620.cc new file mode 100644 index 00000000000..a3127f6ee68 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/operations/91620.cc @@ -0,0 +1,88 @@ +// { dg-do run { target c++11 } } +// { dg-options "-g -O0" } + +// +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +#include <forward_list> +#include <memory> +#include <testsuite_hooks.h> + +struct PredLWG526 +{ + PredLWG526(int i) : i_(i) {}; + ~PredLWG526() { i_ = -32767; } + + bool + operator() (const PredLWG526& p) const { return p.i_ == i_; } + + bool + operator==(int i) const { return i == i_; } + + bool + operator() (const PredLWG526& lhs, const PredLWG526& rhs) const + { + VERIFY( i_ != -32767 ); + return lhs.i_ == rhs.i_; + } + + int i_; +}; + +void test01() +{ + int a1[] = {1, 2, 1, 3, 5, 8, 11}; + int a2[] = {2, 3, 5, 8, 11}; + std::forward_list<PredLWG526> fl(a1, a1 + 7); + + VERIFY( std::distance(fl.begin(), fl.end()) == 7 ); + + fl.remove_if(std::cref(fl.front())); + VERIFY( std::distance(fl.begin(), fl.end()) == 5 ); + for (size_t i = 0; !fl.empty(); ++i) + { + VERIFY( fl.front() == a2[i] ); + fl.pop_front(); + } +} + +void test02() +{ + int a1[] = {1, 1, 1, 2, 3, 5, 8, 11}; + int a2[] = {1, 2, 3, 5, 8, 11}; + std::forward_list<PredLWG526> fl(a1, a1 + 8); + + VERIFY( std::distance(fl.begin(), fl.end()) == 8 ); + + auto it = fl.begin(); + ++it; + fl.unique(std::cref(*it)); + VERIFY( std::distance(fl.begin(), fl.end()) == 6 ); + for (size_t i = 0; !fl.empty(); ++i) + { + VERIFY( fl.front() == a2[i] ); + fl.pop_front(); + } +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/91620.cc b/libstdc++-v3/testsuite/23_containers/list/operations/91620.cc new file mode 100644 index 00000000000..64c0998082d --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/operations/91620.cc @@ -0,0 +1,110 @@ +// { dg-do run { target c++11 } } +// { dg-options "-g -O0" } + +// +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +#include <list> +#include <memory> +#include <testsuite_hooks.h> + +struct PredLWG526 +{ + PredLWG526(int i) : i_(i) {}; + ~PredLWG526() { i_ = -32767; } + + bool + operator() (const PredLWG526& p) const { return p.i_ == i_; } + + bool + operator==(int i) const { return i == i_; } + + bool + operator()(const PredLWG526& lhs, const PredLWG526& rhs) const + { + VERIFY( i_ != -32767 ); + return lhs.i_ == rhs.i_; + } + + friend bool + operator==(const PredLWG526& lhs, const PredLWG526& rhs) + { return lhs.i_ == rhs.i_; } + + int i_; +}; + +void test01() +{ + int a1[] = {1, 2, 1, 3, 5, 8, 11}; + int a2[] = {2, 3, 5, 8, 11}; + std::list<PredLWG526> l(a1, a1 + 7); + + VERIFY( std::distance(l.begin(), l.end()) == 7 ); + + l.remove(l.front()); + VERIFY( std::distance(l.begin(), l.end()) == 5 ); + for (size_t i = 0; !l.empty(); ++i) + { + VERIFY( l.front() == a2[i] ); + l.pop_front(); + } +} + +void test02() +{ + int a1[] = {1, 2, 1, 3, 5, 8, 11}; + int a2[] = {2, 3, 5, 8, 11}; + std::list<PredLWG526> l(a1, a1 + 7); + + VERIFY( std::distance(l.begin(), l.end()) == 7 ); + + l.remove_if(std::cref(l.front())); + VERIFY( std::distance(l.begin(), l.end()) == 5 ); + for (size_t i = 0; !l.empty(); ++i) + { + VERIFY( l.front() == a2[i] ); + l.pop_front(); + } +} + +void test03() +{ + int a1[] = {1, 1, 1, 2, 3, 5, 8, 11}; + int a2[] = {1, 2, 3, 5, 8, 11}; + std::list<PredLWG526> l(a1, a1 + 8); + + VERIFY( std::distance(l.begin(), l.end()) == 8 ); + + auto it = l.begin(); + ++it; + l.unique(std::cref(*it)); + VERIFY( std::distance(l.begin(), l.end()) == 6 ); + for (size_t i = 0; !l.empty(); ++i) + { + VERIFY( l.front() == a2[i] ); + l.pop_front(); + } +} + +int main() +{ + test01(); + test02(); + test03(); + return 0; +} ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique 2019-12-27 15:54 [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique François Dumont 2020-03-03 5:42 ` François Dumont 2020-08-10 19:07 ` François Dumont @ 2020-08-11 9:10 ` Jonathan Wakely 2020-08-11 9:12 ` Jonathan Wakely 2 siblings, 1 reply; 7+ messages in thread From: Jonathan Wakely @ 2020-08-11 9:10 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches 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. Thanks. ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique 2020-08-11 9:10 ` Jonathan Wakely @ 2020-08-11 9:12 ` Jonathan Wakely 0 siblings, 0 replies; 7+ messages in thread From: Jonathan Wakely @ 2020-08-11 9:12 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches 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. ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2020-08-11 9:12 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-12-27 15:54 [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique François Dumont 2020-03-03 5:42 ` François Dumont 2020-03-03 21:33 ` Jonathan Wakely 2020-03-03 21:37 ` Jonathan Wakely 2020-08-10 19:07 ` François Dumont 2020-08-11 9:10 ` Jonathan Wakely 2020-08-11 9:12 ` Jonathan Wakely
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).