From patchwork Fri Dec 3 22:53:42 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 48484 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 49813385841A for ; Fri, 3 Dec 2021 22:54:48 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 49813385841A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638572088; bh=zkDPDpmgT8qmcCCILVR87Fo2uKlgoyINkP+kilrinRQ=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=iITOz/0kIRtnq+zg2K2Lf6986uhcSyZQtfsx3NpdqjGx/E2m2vqkRiwEXgLX1wIu+ TP182isdvX2n8A/XRcCO0JsCt23MdI4XPAVBE/SI/0Luu2CsswWlmN6E86K1IP4DZh ZZ5NQiG1sOXcIEpexARaGMWlkKUtzSqu95wdNvUg= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id E39E03858D35 for ; Fri, 3 Dec 2021 22:53:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E39E03858D35 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-534-ju69KvxtNR276a4MaaQ9MA-1; Fri, 03 Dec 2021 17:53:44 -0500 X-MC-Unique: ju69KvxtNR276a4MaaQ9MA-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 8B6A839382; Fri, 3 Dec 2021 22:53:43 +0000 (UTC) Received: from localhost (unknown [10.33.36.16]) by smtp.corp.redhat.com (Postfix) with ESMTP id 3B0D35DAA5; Fri, 3 Dec 2021 22:53:43 +0000 (UTC) To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [committed] libstdc++: Simplify emplace member functions in _Rb_tree Date: Fri, 3 Dec 2021 22:53:42 +0000 Message-Id: <20211203225342.577258-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-14.0 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_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=unavailable autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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-Patchwork-Original-From: Jonathan Wakely via Gcc-patches From: Jonathan Wakely Reply-To: Jonathan Wakely Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Tested powerpc64le-linux, pushed to trunk. This introduces a new RAII type to simplify the emplace members which currently use try-catch blocks to deallocate a node if an exception is thrown by the comparisons done during insertion. The new type is created on the stack and manages the allocation of a new node and deallocates it in the destructor if it wasn't inserted into the tree. It also provides helper functions for doing the insertion, releasing ownership of the node to the tree. Also, we don't need to use long qualified names if we put the return type after the nested-name-specifier. libstdc++-v3/ChangeLog: * include/bits/stl_tree.h (_Rb_tree::_Auto_node): Define new RAII helper for creating and inserting new nodes. (_Rb_tree::_M_insert_node): Use trailing-return-type to simplify out-of-line definition. (_Rb_tree::_M_insert_lower_node): Likewise. (_Rb_tree::_M_insert_equal_lower_node): Likewise. (_Rb_tree::_M_emplace_unique): Likewise. Use _Auto_node. (_Rb_tree::_M_emplace_equal): Likewise. (_Rb_tree::_M_emplace_hint_unique): Likewise. (_Rb_tree::_M_emplace_hint_equal): Likewise. --- libstdc++-v3/include/bits/stl_tree.h | 148 ++++++++++++++------------- 1 file changed, 78 insertions(+), 70 deletions(-) diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 55b8c9c7cb2..336f4ed97b7 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -1624,6 +1624,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __y.begin(), __y.end()); } #endif + + private: +#if __cplusplus >= 201103L + // An RAII _Node handle + struct _Auto_node + { + template + _Auto_node(_Rb_tree& __t, _Args&&... __args) + : _M_t(__t), + _M_node(__t._M_create_node(std::forward<_Args>(__args)...)) + { } + + ~_Auto_node() + { + if (_M_node) + _M_t._M_drop_node(_M_node); + } + + _Auto_node(_Auto_node&& __n) + : _M_t(__n._M_t), _M_node(__n._M_node) + { __n._M_node = nullptr; } + + const _Key& + _M_key() const + { return _S_key(_M_node); } + + iterator + _M_insert(pair<_Base_ptr, _Base_ptr> __p) + { + auto __it = _M_t._M_insert_node(__p.first, __p.second, _M_node); + _M_node = nullptr; + return __it; + } + + iterator + _M_insert_equal_lower() + { + auto __it = _M_t._M_insert_equal_lower_node(_M_node); + _M_node = nullptr; + return __it; + } + + _Rb_tree& _M_t; + _Link_type _M_node; + }; +#endif // C++11 }; template= 201103L template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + auto _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) + -> iterator { bool __insert_left = (__x != 0 || __p == _M_end() || _M_impl._M_key_compare(_S_key(__z), @@ -2342,9 +2389,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + auto _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: _M_insert_lower_node(_Base_ptr __p, _Link_type __z) + -> iterator { bool __insert_left = (__p == _M_end() || !_M_impl._M_key_compare(_S_key(__p), @@ -2358,9 +2406,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + auto _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: _M_insert_equal_lower_node(_Link_type __z) + -> iterator { _Link_type __x = _M_begin(); _Base_ptr __y = _M_end(); @@ -2376,100 +2425,59 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template template - pair::iterator, bool> + auto _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: _M_emplace_unique(_Args&&... __args) + -> pair { - _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); - - __try - { - typedef pair _Res; - auto __res = _M_get_insert_unique_pos(_S_key(__z)); - if (__res.second) - return _Res(_M_insert_node(__res.first, __res.second, __z), true); - - _M_drop_node(__z); - return _Res(iterator(__res.first), false); - } - __catch(...) - { - _M_drop_node(__z); - __throw_exception_again; - } + _Auto_node __z(*this, std::forward<_Args>(__args)...); + auto __res = _M_get_insert_unique_pos(__z._M_key()); + if (__res.second) + return {__z._M_insert(__res), true}; + return {iterator(__res.first), false}; } template template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + auto _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: _M_emplace_equal(_Args&&... __args) + -> iterator { - _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); - - __try - { - auto __res = _M_get_insert_equal_pos(_S_key(__z)); - return _M_insert_node(__res.first, __res.second, __z); - } - __catch(...) - { - _M_drop_node(__z); - __throw_exception_again; - } + _Auto_node __z(*this, std::forward<_Args>(__args)...); + auto __res = _M_get_insert_equal_pos(__z._M_key()); + return __z._M_insert(__res); } template template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + auto _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) + -> iterator { - _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); - - __try - { - auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); - - if (__res.second) - return _M_insert_node(__res.first, __res.second, __z); - - _M_drop_node(__z); - return iterator(__res.first); - } - __catch(...) - { - _M_drop_node(__z); - __throw_exception_again; - } + _Auto_node __z(*this, std::forward<_Args>(__args)...); + auto __res = _M_get_insert_hint_unique_pos(__pos, __z._M_key()); + if (__res.second) + return __z._M_insert(__res); + return iterator(__res.first); } template template - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + auto _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) + -> iterator { - _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); - - __try - { - auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); - - if (__res.second) - return _M_insert_node(__res.first, __res.second, __z); - - return _M_insert_equal_lower_node(__z); - } - __catch(...) - { - _M_drop_node(__z); - __throw_exception_again; - } + _Auto_node __z(*this, std::forward<_Args>(__args)...); + auto __res = _M_get_insert_hint_equal_pos(__pos, __z._M_key()); + if (__res.second) + return __z._M_insert(__res); + return __z._M_insert_equal_lower(); } #endif