From patchwork Sun Nov 20 18:14:04 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 83159 Delivered-To: patch@linaro.org Received: by 10.140.97.165 with SMTP id m34csp1105829qge; Sun, 20 Nov 2016 10:14:28 -0800 (PST) X-Received: by 10.129.84.70 with SMTP id i67mr9676108ywb.306.1479665668886; Sun, 20 Nov 2016 10:14:28 -0800 (PST) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id w72si3819936ybe.336.2016.11.20.10.14.28 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 20 Nov 2016 10:14:28 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-return-442079-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org; spf=pass (google.com: domain of gcc-patches-return-442079-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-442079-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE dis=NONE) header.from=gmail.com DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :subject:to:references:cc:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=dBYAcQ3h8ExLYUbV2 IJxvbUsNP256o+q3UWUacPB/sfnPTcUQu2VQdrzyGvYKuFZ/frTThZPeCAYtvsEg g6f2Lup4MHHyOei7fODyvCXM4yYn1FmPQ0w9SgvGs3dbMkKA+h0g2PomO89F4yIM dArp8ZLFW64WQS0E/H98zLkUMg= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :subject:to:references:cc:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=lNSIN6JNlGYAZItzZMD2LH9 yL78=; b=iHs5FTDaRsGvTe1pfFGZ9dQRJWcy2ReX05y8hNBsXIuKxvVgknNEtt5 yaNFUUKKb+yX8U7HXnQnMUd9m4LVI2RC5ud+EMZz8JFa4N0gLLMQmXAcQZzZ1qz4 R6Ppg9rA4IHdPdV9bHjP4P2A9r22IFK5G57Mx6XJHwFdeSRtDTpI= Received: (qmail 48298 invoked by alias); 20 Nov 2016 18:14:13 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 48258 invoked by uid 89); 20 Nov 2016 18:14:12 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: =?ISO-8859-1?Q?No, score=-1.4 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_SORBS_SPAM, SPF_PASS autolearn=no version=3.3.2 spammy=coupling, fran=e7ois, uncomfortable, franois?= X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-wj0-f178.google.com Received: from mail-wj0-f178.google.com (HELO mail-wj0-f178.google.com) (209.85.210.178) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 20 Nov 2016 18:14:08 +0000 Received: by mail-wj0-f178.google.com with SMTP id mp19so17825951wjc.1; Sun, 20 Nov 2016 10:14:08 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:subject:to:references:cc:message-id:date :user-agent:mime-version:in-reply-to; bh=KnirWivtYsVFUho+tgoxH+n0aukgbSiAnHa/ohbeFg0=; b=bxuLwanoDdtijzPh4mShM7NhtYwE1AsU6VWDQLFGlRUCzH69wHZVwz5OJhkhbFijsv DGKAnTt6dzjor2U/4YGk1A0S77HpWlaI88LZQBhzzw9WJfARudb69TwzqPNZCQJhjzkB c00m8I/KmO16DHaVyTeaL59DOeVXKzm1I4uSJIdfCAgYzQ2c2bS+OEQcJ4DR+0T+/z73 rN9gYzG2wZ6QorPVBr2agsta9ZnCORkB/rwxOPMGqLlvGseyoE63VzZgfzEiOKZQjMCF oQO9urmCwFXWpOBZZaP7BTZ6R3A7T2SdVpyofnMX4dS9WhyEVs95cgWNBkfS/NXthumN 7Gww== X-Gm-Message-State: AKaTC03BDG+UqoEuYO9/nYkaHYBoythqy3mtx3AQ6HMhpN7O2rGEi9Tqn1iJn+Qc4PoksA== X-Received: by 10.194.39.7 with SMTP id l7mr6188109wjk.182.1479665646317; Sun, 20 Nov 2016 10:14:06 -0800 (PST) Received: from [192.168.0.23] (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by smtp.googlemail.com with ESMTPSA id d10sm20518566wja.20.2016.11.20.10.14.04 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 20 Nov 2016 10:14:05 -0800 (PST) From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: Re: Default associative containers constructors/destructor/assignment To: Jonathan Wakely References: <87049605-cb4e-a451-01f7-4cf106dd0633@gmail.com> <20161117175241.GQ3145@redhat.com> Cc: "libstdc++@gcc.gnu.org" , gcc-patches Message-ID: <22ae1824-80d7-0875-7693-67660414b428@gmail.com> Date: Sun, 20 Nov 2016 19:14:04 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.4.0 MIME-Version: 1.0 In-Reply-To: <20161117175241.GQ3145@redhat.com> On 17/11/2016 18:52, Jonathan Wakely wrote: > > On 28/10/16 21:42 +0200, François Dumont wrote: > >> + template >> + struct _Rb_tree_key_compare >> + { >> + _Key_compare _M_key_compare; >> + >> + _Rb_tree_key_compare() >> + _GLIBCXX_NOEXCEPT_IF( >> + is_nothrow_default_constructible<_Key_compare>::value) >> + : _M_key_compare() >> + { } >> + >> + _Rb_tree_key_compare(const _Key_compare& __comp) >> + : _M_key_compare(__comp) >> + { } >> + >> +#if __cplusplus >= 201103L >> + _Rb_tree_key_compare(_Rb_tree_key_compare&& __x) >> + noexcept(is_nothrow_copy_constructible<_Key_compare>::value) >> + : _M_key_compare(__x._M_key_compare) >> + { } >> +#endif > > This constructor makes the type move-only (i.e. non-copyable) in > C++11 and later. It's copyable in C++98. Is that what you want? I simply consider it was not a problem as, as you noticed, it is not used. > > Adding defaulted copy operations would fix that. Even if we don't > actually need those copy operations, I'm uncomfortable with it being > copyable in C++98 and non-copyable otherwise. Ok, I'll add a default copy constructor for consistency like this: // Copy constructor added for consistency with C++98 mode. _Rb_tree_key_compare(const _Rb_tree_compare&) = default; > >> + void >> + _M_reset() >> + { >> + _M_initialize(); >> + _M_node_count = 0; >> + } > > This introduces a small change in behaviour, because _M_reset() now > does _M_header._M_color = _S_red, which it didn't do before. That > store is redundant. It could be avoided by just doing the three > assignments in _M_reset() instead of calling _M_initialize(). I thought it was ok to do this additional operation for the sake of reusing _M_initialize(). I was compenciating it by avoiding default initialization when there is something to move. > > And we could remove _M_initialize() entirely, and remove the redundant > mem-initializers for _M_node_count (because it's set my _M_reset and > _M_move_data anyway): > > _Rb_tree_header() _GLIBCXX_NOEXCEPT > { > _M_reset(); > _M_header._M_color = _S_red; > } > > #if __cplusplus >= 201103L > _Rb_tree_header(_Rb_tree_header&& __x) noexcept > { > if (__x._M_header._M_parent != nullptr) > _M_move_data(__x); > else > { > _M_reset(); > _M_header._M_color = _S_red; > } > } > > void > _M_move_data(_Rb_tree_header& __x) > { > _M_header._M_parent = __x._M_header._M_parent; > _M_header._M_left = __x._M_header._M_left; > _M_header._M_right = __x._M_header._M_right; > _M_header._M_parent->_M_parent = &_M_header; > _M_node_count = __x._M_node_count; > > __x._M_reset(); > } > #endif > > void > _M_reset() > { > _M_header._M_parent = 0; > _M_header._M_left = &_M_header; > _M_header._M_right = &_M_header; > _M_node_count = 0; > } > Yes, looks nice, adopted. Talking about _M_color I just realize that move semantic doesn't copy _M_color. Shouldn't we capture it along with all the other _M_header information ? > >> @@ -599,50 +674,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >> // Unused _Is_pod_comparator is kept as it is part of mangled >> name. >> template> bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)> >> - struct _Rb_tree_impl : public _Node_allocator >> + struct _Rb_tree_impl >> + : public _Node_allocator >> + , public _Rb_tree_key_compare<_Key_compare> >> + , public _Rb_tree_header > > Do these need to be base classes, rather than data members? > > We derive from the allocator to benefit from the empty base-class > optimization, but that isn't relevant for the _Rb_tree_key_compare and > _Rb_tree_header types. It *could* be relevant for the comparison > function, but would be an ABI change. We could do that ABI change > conditionally, for gnu-versioned-namespace builds, but that's still > possible using data members (e.g. have a data member that derives from > the comparison function and contains the header node and/or node count > members). > > Making them data members would simply mean restoring the function > _Rb_tree_impl::_M_reset() and making it call reset on the member: > > void > _M_reset() { _M_header._M_reset(); } > > The minor convenience of inheriting this function from a base class > doesn't seem worth the stronger coupling that comes from using > inheritance. > > Am I missing some other reason that inheritance is used here? The purpose of this patch is to rely more on compiler especially in regards to the noexcept qualifications. This is why I started isolating each ressource in its own class in charge of its specificities. And I leave to the compiler the work of combining those types. However I also wanted to limit the impact of this patch on the _Rb_tree and still be able to use things like this->_M_impl._M_node_count or this->_M_impl._M_header. So the usage of inheritance. > >> - _Rb_tree_impl(const _Key_compare& __comp, const >> _Node_allocator& __a) >> - : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), >> - _M_node_count(0) >> - { _M_initialize(); } > > Please mention the removal of this constructor in the changelog. > >> @@ -1534,19 +1583,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >> void >> _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: >> _M_move_data(_Rb_tree& __x, std::true_type) >> - { >> - _M_root() = __x._M_root(); >> - _M_leftmost() = __x._M_leftmost(); >> - _M_rightmost() = __x._M_rightmost(); >> - _M_root()->_M_parent = _M_end(); >> - >> - __x._M_root() = 0; >> - __x._M_leftmost() = __x._M_end(); >> - __x._M_rightmost() = __x._M_end(); >> - >> - this->_M_impl._M_node_count = __x._M_impl._M_node_count; >> - __x._M_impl._M_node_count = 0; >> - } >> + { _M_impl._M_move_data(__x._M_impl); } > > This function could be moved into the class body, or just have > 'inline' added to its definition. > Ok, adopted in the attached new version of the patch. Tested under x86_64 Linux, ok to commit ? For info, I would like to propose another bunch of simplifications of _Rb_tree, see other patch attached. Do you want me to propose it in another mail ? François diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 8de5e31..1bfbfa7 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -861,11 +861,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Link_type _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&); + template + _Link_type + _M_copy(const _Rb_tree& __x, _NodeGen& __gen) + { + _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen); + _M_leftmost() = _S_minimum(__root); + _M_rightmost() = _S_maximum(__root); + _M_impl._M_node_count = __x._M_impl._M_node_count; + return __root; + } + _Link_type - _M_copy(_Const_Link_type __x, _Base_ptr __p) + _M_copy(const _Rb_tree& __x) { _Alloc_node __an(*this); - return _M_copy(__x, __p, __an); + return _M_copy(__x, __an); } void @@ -903,12 +914,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : _M_impl(__x._M_impl) { if (__x._M_root() != 0) - { - _M_root() = _M_copy(__x._M_begin(), _M_end()); - _M_leftmost() = _S_minimum(_M_root()); - _M_rightmost() = _S_maximum(_M_root()); - _M_impl._M_node_count = __x._M_impl._M_node_count; - } + _M_root() = _M_copy(__x); } #if __cplusplus >= 201103L @@ -920,12 +926,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a)) { if (__x._M_root() != nullptr) - { - _M_root() = _M_copy(__x._M_begin(), _M_end()); - _M_leftmost() = _S_minimum(_M_root()); - _M_rightmost() = _S_maximum(_M_root()); - _M_impl._M_node_count = __x._M_impl._M_node_count; - } + _M_root() = _M_copy(__x); } _Rb_tree(_Rb_tree&&) = default; @@ -1595,10 +1596,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto& __val = const_cast(__cval); return __an(std::move_if_noexcept(__val)); }; - _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); - _M_leftmost() = _S_minimum(_M_root()); - _M_rightmost() = _S_maximum(_M_root()); - _M_impl._M_node_count = __x._M_impl._M_node_count; + _M_root() = _M_copy(__x, __lbd); } } @@ -1636,10 +1634,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto& __val = const_cast(__cval); return __roan(std::move_if_noexcept(__val)); }; - _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd); - _M_leftmost() = _S_minimum(_M_root()); - _M_rightmost() = _S_maximum(_M_root()); - _M_impl._M_node_count = __x._M_impl._M_node_count; + _M_root() = _M_copy(__x, __lbd); __x.clear(); } } @@ -1653,10 +1648,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION && is_nothrow_move_assignable<_Compare>::value) { _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare); - constexpr bool __move_storage = - _Alloc_traits::_S_propagate_on_move_assign() - || _Alloc_traits::_S_always_equal(); - _M_move_assign(__x, __bool_constant<__move_storage>()); + _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>()); return *this; } @@ -1716,12 +1708,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_impl._M_reset(); _M_impl._M_key_compare = __x._M_impl._M_key_compare; if (__x._M_root() != 0) - { - _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan); - _M_leftmost() = _S_minimum(_M_root()); - _M_rightmost() = _S_maximum(_M_root()); - _M_impl._M_node_count = __x._M_impl._M_node_count; - } + _M_root() = _M_copy(__x, __roan); } return *this;