From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-1.mimecast.com (us-smtp-1.mimecast.com [207.211.31.81]) by sourceware.org (Postfix) with ESMTP id 516543857C65 for ; Tue, 11 Aug 2020 09:12:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 516543857C65 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-393--sMwocV2M3S8v6vIGnWnbw-1; Tue, 11 Aug 2020 05:12:20 -0400 X-MC-Unique: -sMwocV2M3S8v6vIGnWnbw-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 0C7F01902EA4; Tue, 11 Aug 2020 09:12:19 +0000 (UTC) Received: from localhost (unknown [10.33.36.145]) by smtp.corp.redhat.com (Postfix) with ESMTP id 95D4B5F9DC; Tue, 11 Aug 2020 09:12:18 +0000 (UTC) Date: Tue, 11 Aug 2020 10:12:17 +0100 From: Jonathan Wakely To: =?iso-8859-1?Q?Fran=E7ois?= Dumont Cc: "libstdc++@gcc.gnu.org" , gcc-patches Subject: Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique Message-ID: <20200811091217.GA3400@redhat.com> References: <24962b65-4e23-2a3b-ea50-2eef3e9c98a8@gmail.com> <20200811091058.GZ3400@redhat.com> MIME-Version: 1.0 In-Reply-To: <20200811091058.GZ3400@redhat.com> X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.16 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=iso-8859-1; format=flowed Content-Transfer-Encoding: 8bit Content-Disposition: inline X-Spam-Status: No, score=-14.1 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=unavailable autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 11 Aug 2020 09:12:25 -0000 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.