Message ID | 24962b65-4e23-2a3b-ea50-2eef3e9c98a8@gmail.com |
---|---|
State | New |
Headers | show |
Series | PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique | expand |
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 >
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.
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).
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 >
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.
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.
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