From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x442.google.com (mail-wr1-x442.google.com [IPv6:2a00:1450:4864:20::442]) by sourceware.org (Postfix) with ESMTPS id BCE5E388702F; Fri, 20 Nov 2020 07:17:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org BCE5E388702F Received: by mail-wr1-x442.google.com with SMTP id p8so8962214wrx.5; Thu, 19 Nov 2020 23:17:45 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=DrVJTiKRAjtgRcyvsNUSjOgfXISojNxZNkQOtd4LKzI=; b=pK6GeR4xe1mJvBMbRgFAZzCGGVokCa3unHNQDV4i3InLRb/0SkfMqg4xcn1aFUScgb JAtH73Q0PEV/+FUCEcGVYGcVlwAOI3UiVmHPkp81Vj+hXdhesJ31Q9iMWptVS2oua4Ti LACSgOXlkLs7e9i220BWpgMyf/AO5ja5RD8ws0bwwMUrCBslTNcHiaHJSo8f1sEgjIDt L4FvsWNvI2RQ2JFH6THN3GpgPoQrM8fmM9rqaNVFT9Rz3uKsoTLhOHDz4CdD9ayENNgP niUVJmRmXDuOEWGNN4gmRi6M8evhA4MFCy+pKKio5dVA3TJQi60wRqIKhiK6VKEsfGi7 cAMA== X-Gm-Message-State: AOAM531buc94bcIUQkDF2JhJm1S9Gwtw291h1njSwd8CKo6koa8igdXn N02lE6DWb5f6NR/VaDGjFiofl/V5dhaXLg== X-Google-Smtp-Source: ABdhPJwqRvt5LUPPxZNuhSbPR8SwV9HdJmrFXwf/P7tzb8d+dhCzQLcuvnz/ECZz688Stt1hcVUZEQ== X-Received: by 2002:adf:a198:: with SMTP id u24mr13445201wru.219.1605856664118; Thu, 19 Nov 2020 23:17:44 -0800 (PST) Received: from ?IPv6:2a01:e0a:1dc:b1c0:e4fb:ee39:46d2:f4b6? ([2a01:e0a:1dc:b1c0:e4fb:ee39:46d2:f4b6]) by smtp.googlemail.com with ESMTPSA id p4sm4030350wrm.51.2020.11.19.23.17.41 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 19 Nov 2020 23:17:41 -0800 (PST) Subject: Re: [PATCH] Remove lambdas from _Rb_tree To: Jonathan Wakely Cc: "libstdc++@gcc.gnu.org" , gcc-patches References: <7c66cd1c-3f62-5f2c-fb75-2641d672a3d2@gmail.com> <20201117235031.GC503596@redhat.com> <20201119113127.GC1312820@redhat.com> From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Message-ID: <616cd512-76cd-5d7c-0a9b-7224816bc245@gmail.com> Date: Fri, 20 Nov 2020 08:17:40 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0 MIME-Version: 1.0 In-Reply-To: <20201119113127.GC1312820@redhat.com> Content-Type: multipart/mixed; boundary="------------871529B705217F03A6A2F1B0" Content-Language: fr X-Spam-Status: No, score=-10.3 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham 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: Fri, 20 Nov 2020 07:17:50 -0000 This is a multi-part message in MIME format. --------------871529B705217F03A6A2F1B0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Here is what I am testing. I use your enum proposal as an alias for the bool type. I cannot use it as template parameter on _M_copy unless I put it at std namespace level to use it in definition of the outline _M_copy overload. I also added some tests checking correct usage of __move_if_noexcept_cond. I prefer not to change this condition as proposed in this patch. I wonder if I am right to check moved values in those tests ? I also wonder after writing those tests if we shouldn't clear the moved instance, especially when values are moved ? I remember seeing some discussion about this but I don't know the conclusion.     libstdc++: _Rb_tree code cleanup, remove lambdas     Use new template parameters to replace usage of lambdas to move or not     tree values on copy.     libstdc++-v3/ChangeLog:             * include/bits/move.h (_GLIBCXX_FWDREF): New.             * include/bits/stl_tree.h: Adapt to use latter.             (_Rb_tree<>::_M_clone_node): Add _MoveValue template parameter.             (_Rb_tree<>::_M_mbegin): New.             (_Rb_tree<>::_M_begin): Use latter.             (_Rb_tree<>::_M_copy): Add _MoveValues template parameter.             * testsuite/23_containers/map/allocator/move_cons.cc: New test.             * testsuite/23_containers/multimap/allocator/move_cons.cc: New test.             * testsuite/23_containers/multiset/allocator/move_cons.cc: New test.             * testsuite/23_containers/set/allocator/move_cons.cc: New test. Ok to commit once all tests have complete ? François On 19/11/20 12:31 pm, Jonathan Wakely wrote: > On 19/11/20 07:46 +0100, François Dumont via Libstdc++ wrote: >> On 18/11/20 12:50 am, Jonathan Wakely wrote: >>> On 17/11/20 21:51 +0100, François Dumont via Libstdc++ wrote: >>>> This is a change that has been done to _Hashtable and that I forgot >>>> to propose for _Rb_tree. >>>> >>>> The _GLIBCXX_XREF macro can be easily removed of course. >>>> >>>>     libstdc++: _Rb_tree code cleanup, remove lambdas. >>>> >>>>     Use an additional template parameter on the clone >>>> method to propagate if the values must be >>>>     copy or move rather than lambdas. >>>> >>>>     libstdc++-v3/ChangeLog: >>>> >>>>             * include/bits/move.h >>>> (_GLIBCXX_XREF): New. >>>>             * >>>> include/bits/stl_tree.h: Adapt to use latter. >>>>            >>>> (_Rb_tree<>::_S_fwd_value_for): New. >>>>            >>>> (_Rb_tree<>::_M_clone_node): Add _Tree template parameter. >>>>             Use _S_fwd_value_for. >>>>            >>>> (_Rb_tree<>::_M_cbegin): New. >>>>            (_Rb_tree<>::_M_begin): >>>> Use latter. >>>>            (_Rb_tree<>::_M_copy): >>>> Add _Tree template parameter. >>>>            >>>> (_Rb_tree<>::_M_move_data): Use rvalue reference for _Rb_tree >>>> parameter. >>>>            >>>> (_Rb_tree<>::_M_move_assign): Likewise. >>>> >>>> Tested under Linux x86_64. >>>> >>>> Ok to commit ? >>> >>> GCC is in stage 3 now, so this should have been posted last week >>> really. >> >> Ok, no problem, it can wait. >> >> Still, following your advises here is what I come up with, much >> simpler indeed. > > Yes, this simpler patch looks promising even though it's stage 3. > >> I just run a few tests for the moment but so far so good. >> >> Thanks >> >>> >>> >>>> diff --git a/libstdc++-v3/include/bits/move.h >>>> b/libstdc++-v3/include/bits/move.h >>>> index 5a4dbdc823c..e0d68ca9108 100644 >>>> --- a/libstdc++-v3/include/bits/move.h >>>> +++ b/libstdc++-v3/include/bits/move.h >>>> @@ -158,9 +158,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>>> >>>>   /// @} group utilities >>>> >>>> +#define _GLIBCXX_XREF(_Tp) _Tp&& >>> >>> I think this does improve the code that uses this. But the correct >>> name for this is forwarding reference, so I think FWDREF would be >>> better than XREF. XREF doesn't tell me anything about what it's for. >>> >>>> #define _GLIBCXX_MOVE(__val) std::move(__val) >>>> #define _GLIBCXX_FORWARD(_Tp, __val) std::forward<_Tp>(__val) >>>> #else >>>> +#define _GLIBCXX_XREF(_Tp) const _Tp& >>>> #define _GLIBCXX_MOVE(__val) (__val) >>>> #define _GLIBCXX_FORWARD(_Tp, __val) (__val) >>>> #endif >>>> diff --git a/libstdc++-v3/include/bits/stl_tree.h >>>> b/libstdc++-v3/include/bits/stl_tree.h >>>> index ec141ea01c7..128c7e2c892 100644 >>>> --- a/libstdc++-v3/include/bits/stl_tree.h >>>> +++ b/libstdc++-v3/include/bits/stl_tree.h >>>> @@ -478,11 +478,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>>> >>>>     template >>>>       _Link_type >>>> -#if __cplusplus < 201103L >>>> -      operator()(const _Arg& __arg) >>>> -#else >>>> -      operator()(_Arg&& __arg) >>>> -#endif >>>> +      operator()(_GLIBCXX_XREF(_Arg) __arg) >>>>       { >>>>         _Link_type __node = >>>> static_cast<_Link_type>(_M_extract()); >>>>         if (__node) >>>> @@ -544,11 +540,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>>> >>>>     template >>>>       _Link_type >>>> -#if __cplusplus < 201103L >>>> -      operator()(const _Arg& __arg) const >>>> -#else >>>> -      operator()(_Arg&& __arg) const >>>> -#endif >>>> +      operator()(_GLIBCXX_XREF(_Arg) __arg) const >>>>       { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, >>>> __arg)); } >>>> >>>>       private: >>>> @@ -655,11 +647,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>>>     _M_put_node(__p); >>>>       } >>>> >>>> -      template >>>> +#if __cplusplus >= 201103L >>>> +      template >>>> +    static constexpr >>>> +    typename conditional::value, >>>> +                 const value_type&, >>>> value_type&&>::type >>>> +    _S_fwd_value_for(value_type& __val) noexcept >>>> +    { return std::move(__val); } >>>> +#else >>>> +      template >>>> +    static const value_type& >>>> +    _S_fwd_value_for(value_type& __val) >>>> +    { return __val; } >>>> +#endif >>>> + >>>> +      template >>>>     _Link_type >>>> -    _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen) >>>> +    _M_clone_node(_GLIBCXX_XREF(_Tree), >>> >>> Since the _Tree type is only used to decide whether to copy or move, >>> could it just be a bool instead? >>> >>>       template >>>      _Link_type >>>     _M_clone_node(_Link_type __x, _NodeGen& __node_gen) >>> >>> Then it would be called as _M_clone_node<_Move>(__x, __node_gen) >>> instead of _M_clone_node(_GLIBCXX_FORWARD(_Tree, __t), __x, >>> __node_gen). >>> That seems easier to read. >>> >>>> +              _Link_type __x, _NodeGen& __node_gen) >>>>     { >>>> -      _Link_type __tmp = __node_gen(*__x->_M_valptr()); >>>> +      _Link_type __tmp >>>> +        = >>>> __node_gen(_S_fwd_value_for<_Tree>(*__x->_M_valptr())); >>> >>> Is _S_fwd_value_for necessary? This would work: >>> >>> #if __cplusplus >= 201103L >>>           using _Vp = typename >>> conditional::value, >>>                                           >>> const value_type&, >>> value_type&&>::type; >>> #else >>>           typedef const value_type& _Vp; >>> #endif >>>           _Link_type __tmp >>>             = __node_gen(_GLIBCXX_FORWARD(_Vp, >>> *__x->_M_valptr())); >>> >>> Or with the suggestion above, the typedef would be: >>> >>>           using _Vp = typename conditional<_Move, >>> value_type&&, >>>                                           >>> const value_type&>::type; >>> >>> >>>>       __tmp->_M_color = __x->_M_color; >>>>       __tmp->_M_left = 0; >>>>       __tmp->_M_right = 0; >>>> @@ -748,9 +756,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>>>       { return this->_M_impl._M_header._M_right; } >>>> >>>>       _Link_type >>>> -      _M_begin() _GLIBCXX_NOEXCEPT >>>> +      _M_cbegin() const _GLIBCXX_NOEXCEPT >>> >>> It's confusing that this is called cbegin but returns a non-const >>> link. The standard cbegin() functions return a const_iterator. I would >>> expect this to return a _Const_Link_type, based on the name. >>> >>> >>>>       { return >>>> static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } >>>> >>>> +      _Link_type >>>> +      _M_begin() _GLIBCXX_NOEXCEPT >>>> +      { return _M_cbegin(); } >>>> + >>>>       _Const_Link_type >>>>       _M_begin() const _GLIBCXX_NOEXCEPT >>>>       { >>>> @@ -889,15 +901,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>>>       _M_insert_equal_lower(const value_type& __x); >>>> #endif >>>> >>>> -      template >>>> +      template >>>>     _Link_type >>>> -    _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&); >>>> +    _M_copy(_GLIBCXX_XREF(_Tree), _Link_type, _Base_ptr, >>>> _NodeGen&); >>> >>> This could use 'bool _Move' instead of 'typename _Tree'. >>> >>>> -      template >>>> +      template >>>>     _Link_type >>>> -    _M_copy(const _Rb_tree& __x, _NodeGen& __gen) >>>> +    _M_copy(_GLIBCXX_XREF(_Tree) __x, _NodeGen& __gen) >>> >>> This one gets called from _M_copy(const _Rb_tree&) with const _Rb_tree >>> argument, so I think using the XREF macro (or FWDREF) does make sense >>> here. >>> >>>>     { >>>> -      _Link_type __root = _M_copy(__x._M_begin(), _M_end(), >>>> __gen); >>>> +      _Link_type __root = _M_copy(_GLIBCXX_FORWARD(_Tree, __x), >>>> +                      __x._M_cbegin(), >>>> _M_end(), __gen); >>> >>> This would have to be: >>> >>> #if __cplusplus >= 201103L >>>           constexpr bool __move = !is_reference<_Tree>::value; >>> #else >>>           const bool __move = false; >>> #endif >>>           _Link_type __root = >>> _M_copy<__move>(__x._M_cbegin(), _M_end(), __gen); >>> >>> Would doing it this way make sense? >>> >>> >>>>       _M_leftmost() = _S_minimum(__root); >>>>       _M_rightmost() = _S_maximum(__root); >>>>       _M_impl._M_node_count = __x._M_impl._M_node_count; >>>> @@ -1426,22 +1439,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>>>     private: >>>>       // Move elements from container with equal allocator. >>>>       void >>>> -      _M_move_data(_Rb_tree& __x, true_type) >>>> +      _M_move_data(_Rb_tree&& __x, true_type) >>>>       { _M_impl._M_move_data(__x._M_impl); } >>>> >>>>       // Move elements from container with possibly non-equal >>>> allocator, >>>>       // which might result in a copy not a move. >>>>       void >>>> -      _M_move_data(_Rb_tree&, false_type); >>>> +      _M_move_data(_Rb_tree&&, false_type); >>>> >>>>       // Move assignment from container with equal allocator. >>>>       void >>>> -      _M_move_assign(_Rb_tree&, true_type); >>>> +      _M_move_assign(_Rb_tree&&, true_type); >>>> >>>>       // Move assignment from container with possibly >>>> non-equal allocator, >>>>       // which might result in a copy not a move. >>>>       void >>>> -      _M_move_assign(_Rb_tree&, false_type); >>>> +      _M_move_assign(_Rb_tree&&, false_type); >>> >>> These changes don't seem necessary. While they might be preferable if >>> we were writing this from scratch, changing them now means that >>> binaries built with more than one version of GCC will be larger. >>> Objects built with older versions of GCC will have instantiations of >>> the old versions and objects built with newer versions will have >>> instantiations of the new versions. The increase in executable size >>> (and icache pressure) doesn't seem worthwhile. >>> >>> The other changes (to remove the lambdas) also have this consequence, >>> but the benefits of simplifying the code do seem worthwhile. Just >>> changing _Rb_tree& to _Rb_tree&& (and having to use std::move to call >>> those functions) doesn't simplify anything. The functions already have >>> "move" in the name, so it's pretty obvious they perform moves. >>> >>> >>> >>> >>>> @@ -1859,29 +1864,34 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>>> >>>>   template>>>        typename _Compare, typename _Alloc> >>>> -    template >>>> +    template >>>>       typename _Rb_tree<_Key, _Val, _KoV, _Compare, >>>> _Alloc>::_Link_type >>>>       _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: >>>> -      _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& >>>> __node_gen) >>>> +      _M_copy(_GLIBCXX_XREF(_Tree) __t, >>> >>> The __t parameter is only needed below to be forwarded, so its type >>> can be checked later on. Using bool _Move instead would work fine, and >>> avoid having to pass an extra parameter on the stack which never gets >>> used (only its type). >>> >>>> +          _Link_type __x, _Base_ptr __p, _NodeGen& >>>> __node_gen) >>>>       { >>>>     // Structural copy. __x and __p must be non-null. >>>> -    _Link_type __top = _M_clone_node(__x, __node_gen); >>>> +    _Link_type __top = _M_clone_node(_GLIBCXX_FORWARD(_Tree, __t), >>>> +                     __x, __node_gen); >>>>     __top->_M_parent = __p; >>>> >>>>     __try >>>>       { >>>>         if (__x->_M_right) >>>> -          __top->_M_right = _M_copy(_S_right(__x), __top, >>>> __node_gen); >>>> +          __top->_M_right = >>>> _M_copy(_GLIBCXX_FORWARD(_Tree, __t), >>>> +                    _S_right(__x), __top, >>>> __node_gen); >>>>         __p = __top; >>>>         __x = _S_left(__x); >>>> >>>>         while (__x != 0) >>>>           { >>>> -        _Link_type __y = _M_clone_node(__x, __node_gen); >>>> +        _Link_type __y = >>>> _M_clone_node(_GLIBCXX_FORWARD(_Tree, __t), >>>> +                           __x, >>>> __node_gen); >>>>         __p->_M_left = __y; >>>>         __y->_M_parent = __p; >>>>         if (__x->_M_right) >>>> -          __y->_M_right = _M_copy(_S_right(__x), __y, >>>> __node_gen); >>>> +          __y->_M_right = _M_copy(_GLIBCXX_FORWARD(_Tree, >>>> __t), >>>> +                      _S_right(__x), __y, >>>> __node_gen); >>>>         __p = __y; >>>>         __x = _S_left(__x); >>>>           } >>> >> > >> diff --git a/libstdc++-v3/include/bits/move.h >> b/libstdc++-v3/include/bits/move.h >> index 5a4dbdc823c..b33c22a4374 100644 >> --- a/libstdc++-v3/include/bits/move.h >> +++ b/libstdc++-v3/include/bits/move.h >> @@ -158,9 +158,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >> >>   /// @} group utilities >> >> +#define _GLIBCXX_FWDREF(_Tp) _Tp&& >> #define _GLIBCXX_MOVE(__val) std::move(__val) >> #define _GLIBCXX_FORWARD(_Tp, __val) std::forward<_Tp>(__val) >> #else >> +#define _GLIBCXX_FWDREF(_Tp) const _Tp& >> #define _GLIBCXX_MOVE(__val) (__val) >> #define _GLIBCXX_FORWARD(_Tp, __val) (__val) >> #endif >> diff --git a/libstdc++-v3/include/bits/stl_tree.h >> b/libstdc++-v3/include/bits/stl_tree.h >> index ec141ea01c7..baa4c81a7ed 100644 >> --- a/libstdc++-v3/include/bits/stl_tree.h >> +++ b/libstdc++-v3/include/bits/stl_tree.h >> @@ -478,11 +478,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >> >>     template >>       _Link_type >> -#if __cplusplus < 201103L >> -      operator()(const _Arg& __arg) >> -#else >> -      operator()(_Arg&& __arg) >> -#endif >> +      operator()(_GLIBCXX_FWDREF(_Arg) __arg) >>       { >>         _Link_type __node = static_cast<_Link_type>(_M_extract()); >>         if (__node) >> @@ -544,11 +540,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >> >>     template >>       _Link_type >> -#if __cplusplus < 201103L >> -      operator()(const _Arg& __arg) const >> -#else >> -      operator()(_Arg&& __arg) const >> -#endif >> +      operator()(_GLIBCXX_FWDREF(_Arg) __arg) const >>       { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); } >> >>       private: >> @@ -655,11 +647,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>     _M_put_node(__p); >>       } >> >> -      template >> +      template >>     _Link_type >> -    _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen) >> +    _M_clone_node(_Link_type __x, _NodeGen& __node_gen) >>     { >> -      _Link_type __tmp = __node_gen(*__x->_M_valptr()); >> +#if __cplusplus >= 201103L >> +      using _Vp = >> +        typename conditional<_Move, value_type&&, const >> value_type&>::type; >> +#endif >> +      _Link_type __tmp >> +        = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr())); > > Oh this is nice, I forgot that _GLIBCXX_FORWARD doesn't use the first > argument at all for C++98, so we don't need _Vp. > >>       __tmp->_M_color = __x->_M_color; >>       __tmp->_M_left = 0; >>       __tmp->_M_right = 0; >> @@ -748,9 +745,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>       { return this->_M_impl._M_header._M_right; } >> >>       _Link_type >> -      _M_begin() _GLIBCXX_NOEXCEPT >> +      _M_mbegin() const _GLIBCXX_NOEXCEPT > > Nice. > >>       { return >> static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } >> >> +      _Link_type >> +      _M_begin() _GLIBCXX_NOEXCEPT >> +      { return _M_mbegin(); } >> + >>       _Const_Link_type >>       _M_begin() const _GLIBCXX_NOEXCEPT >>       { >> @@ -889,15 +890,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>       _M_insert_equal_lower(const value_type& __x); >> #endif >> >> -      template >> +      template >>     _Link_type >> -    _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&); >> +    _M_copy(_Link_type, _Base_ptr, _NodeGen&); >> >> -      template >> +      template >>     _Link_type >>     _M_copy(const _Rb_tree& __x, _NodeGen& __gen) >>     { >> -      _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen); >> +      _Link_type __root = _M_copy<_Move>(__x._M_mbegin(), _M_end(), >> __gen); >>       _M_leftmost() = _S_minimum(__root); >>       _M_rightmost() = _S_maximum(__root); >>       _M_impl._M_node_count = __x._M_impl._M_node_count; >> @@ -908,7 +909,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>       _M_copy(const _Rb_tree& __x) >>       { >>     _Alloc_node __an(*this); >> -    return _M_copy(__x, __an); >> +    return _M_copy(__x, __an); >>       } >> >>       void >> @@ -1655,13 +1656,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>       else >>     { >>       _Alloc_node __an(*this); >> -      auto __lbd = >> -        [&__an](const value_type& __cval) >> -        { >> -          auto& __val = const_cast(__cval); >> -          return __an(std::move_if_noexcept(__val)); >> -        }; >> -      _M_root() = _M_copy(__x, __lbd); >> +      _M_root() = >> + _M_copy<__move_if_noexcept_cond::value>(__x, __an); > > Should this be !__move_if_noexcept_cond::value ? > > The condition is confusing. Maybe we should replace > __move_if_noexcept_cond with something like: > >   // True if copying should be used for strong exception-safety > guarantee. >   // False if the type has nothrow move, or isn't copyable. >   template >     using __use_copy_for_exception_safety >       = typename __and_<__not_>, >             is_copy_constructible<_Tp>>::type; > > > >>     } >>     } >> >> @@ -1693,13 +1689,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >>       _M_impl._M_reset(); >>       if (__x._M_root() != nullptr) >>     { >> -      auto __lbd = >> -        [&__roan](const value_type& __cval) >> -        { >> -          auto& __val = const_cast(__cval); >> -          return __roan(std::move(__val)); >> -        }; >> -      _M_root() = _M_copy(__x, __lbd); >> +      _M_root() = _M_copy(__x, __roan); > > I've realised the downside of my suggestion: _M_copy does a move > and _M_copy does a copy. Maybe we should do: > >   enum _CopyType { __as_lvalue, __as_rvalue }; > > And then _M_copy<__as_rvalue> or _M_copy<__as_lvalue> > > We can't use typedefs for true_type and false_type here because the > code needs to be valid in C++98. > > >>       __x.clear(); >>     } >>     } >> @@ -1773,7 +1763,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, __roan); >> +        _M_root() = _M_copy(__x, __roan); >>     } >> >>       return *this; >> @@ -1859,29 +1849,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >> >>   template>        typename _Compare, typename _Alloc> >> -    template >> +    template >>       typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type >>       _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: >> -      _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& >> __node_gen) >> +      _M_copy(_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen) >>       { >>     // Structural copy. __x and __p must be non-null. >> -    _Link_type __top = _M_clone_node(__x, __node_gen); >> +    _Link_type __top = _M_clone_node<_Move>(__x, __node_gen); >>     __top->_M_parent = __p; >> >>     __try >>       { >>         if (__x->_M_right) >> -          __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen); >> +          __top->_M_right = >> +        _M_copy<_Move>(_S_right(__x), __top, __node_gen); >>         __p = __top; >>         __x = _S_left(__x); >> >>         while (__x != 0) >>           { >> -        _Link_type __y = _M_clone_node(__x, __node_gen); >> +        _Link_type __y = _M_clone_node<_Move>(__x, __node_gen); >>         __p->_M_left = __y; >>         __y->_M_parent = __p; >>         if (__x->_M_right) >> -          __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen); >> +          __y->_M_right = _M_copy<_Move>(_S_right(__x), __y, >> __node_gen); >>         __p = __y; >>         __x = _S_left(__x); >>           } > --------------871529B705217F03A6A2F1B0 Content-Type: text/x-patch; charset=UTF-8; name="tree.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="tree.patch" diff --git a/libstdc++-v3/include/bits/move.h b/libstdc++-v3/include/bits/move.h index 5a4dbdc823c..b33c22a4374 100644 --- a/libstdc++-v3/include/bits/move.h +++ b/libstdc++-v3/include/bits/move.h @@ -158,9 +158,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// @} group utilities +#define _GLIBCXX_FWDREF(_Tp) _Tp&& #define _GLIBCXX_MOVE(__val) std::move(__val) #define _GLIBCXX_FORWARD(_Tp, __val) std::forward<_Tp>(__val) #else +#define _GLIBCXX_FWDREF(_Tp) const _Tp& #define _GLIBCXX_MOVE(__val) (__val) #define _GLIBCXX_FORWARD(_Tp, __val) (__val) #endif diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index ec141ea01c7..a51d6da4ae8 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -478,11 +478,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template _Link_type -#if __cplusplus < 201103L - operator()(const _Arg& __arg) -#else - operator()(_Arg&& __arg) -#endif + operator()(_GLIBCXX_FWDREF(_Arg) __arg) { _Link_type __node = static_cast<_Link_type>(_M_extract()); if (__node) @@ -544,11 +540,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template _Link_type -#if __cplusplus < 201103L - operator()(const _Arg& __arg) const -#else - operator()(_Arg&& __arg) const -#endif + operator()(_GLIBCXX_FWDREF(_Arg) __arg) const { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); } private: @@ -655,11 +647,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_put_node(__p); } - template + template _Link_type - _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen) + _M_clone_node(_Link_type __x, _NodeGen& __node_gen) { - _Link_type __tmp = __node_gen(*__x->_M_valptr()); +#if __cplusplus >= 201103L + using _Vp = typename conditional<_MoveValue, + value_type&&, + const value_type&>::type; +#endif + _Link_type __tmp + = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr())); __tmp->_M_color = __x->_M_color; __tmp->_M_left = 0; __tmp->_M_right = 0; @@ -748,9 +746,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return this->_M_impl._M_header._M_right; } _Link_type - _M_begin() _GLIBCXX_NOEXCEPT + _M_mbegin() const _GLIBCXX_NOEXCEPT { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } + _Link_type + _M_begin() _GLIBCXX_NOEXCEPT + { return _M_mbegin(); } + _Const_Link_type _M_begin() const _GLIBCXX_NOEXCEPT { @@ -889,15 +891,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert_equal_lower(const value_type& __x); #endif - template + enum { __as_lvalue, __as_rvalue }; + + template _Link_type - _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&); + _M_copy(_Link_type, _Base_ptr, _NodeGen&); - template + template _Link_type _M_copy(const _Rb_tree& __x, _NodeGen& __gen) { - _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen); + _Link_type __root = + _M_copy<_MoveValues>(__x._M_mbegin(), _M_end(), __gen); _M_leftmost() = _S_minimum(__root); _M_rightmost() = _S_maximum(__root); _M_impl._M_node_count = __x._M_impl._M_node_count; @@ -908,7 +913,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_copy(const _Rb_tree& __x) { _Alloc_node __an(*this); - return _M_copy(__x, __an); + return _M_copy<__as_lvalue>(__x, __an); } void @@ -1655,13 +1660,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION else { _Alloc_node __an(*this); - auto __lbd = - [&__an](const value_type& __cval) - { - auto& __val = const_cast(__cval); - return __an(std::move_if_noexcept(__val)); - }; - _M_root() = _M_copy(__x, __lbd); + _M_root() = + _M_copy::value>(__x, __an); } } @@ -1693,13 +1693,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_impl._M_reset(); if (__x._M_root() != nullptr) { - auto __lbd = - [&__roan](const value_type& __cval) - { - auto& __val = const_cast(__cval); - return __roan(std::move(__val)); - }; - _M_root() = _M_copy(__x, __lbd); + _M_root() = _M_copy<__as_rvalue>(__x, __roan); __x.clear(); } } @@ -1773,7 +1767,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, __roan); + _M_root() = _M_copy<__as_lvalue>(__x, __roan); } return *this; @@ -1859,29 +1853,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template - template + template typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: - _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen) + _M_copy(_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen) { // Structural copy. __x and __p must be non-null. - _Link_type __top = _M_clone_node(__x, __node_gen); + _Link_type __top = _M_clone_node<_MoveValues>(__x, __node_gen); __top->_M_parent = __p; __try { if (__x->_M_right) - __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen); + __top->_M_right = + _M_copy<_MoveValues>(_S_right(__x), __top, __node_gen); __p = __top; __x = _S_left(__x); while (__x != 0) { - _Link_type __y = _M_clone_node(__x, __node_gen); + _Link_type __y = _M_clone_node<_MoveValues>(__x, __node_gen); __p->_M_left = __y; __y->_M_parent = __p; if (__x->_M_right) - __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen); + __y->_M_right = _M_copy<_MoveValues>(_S_right(__x), + __y, __node_gen); __p = __y; __x = _S_left(__x); } diff --git a/libstdc++-v3/testsuite/23_containers/map/allocator/move_cons.cc b/libstdc++-v3/testsuite/23_containers/map/allocator/move_cons.cc new file mode 100644 index 00000000000..08a14a42d6a --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/map/allocator/move_cons.cc @@ -0,0 +1,53 @@ +// 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 +// . + +// { dg-do run { target c++11 } } + +#include +#include + +#include +#include + +using Cmp = std::less; + +using __gnu_test::uneq_allocator; + +void test01() +{ + typedef uneq_allocator> alloc_type; + typedef std::map test_type; + test_type v1(alloc_type(1)); + const char* str = "A long enough string to require dynamic allocation"; + v1 = { { 1, str } }; + + alloc_type a2(2); + test_type v2(std::move(v1), a2); + + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(2 == v2.get_allocator().get_personality()); + + VERIFY( v1[1].empty() ); + VERIFY( v2[1] == str ); +} + + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_cons.cc b/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_cons.cc new file mode 100644 index 00000000000..4fbd85d665c --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multimap/allocator/move_cons.cc @@ -0,0 +1,53 @@ +// 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 +// . + +// { dg-do run { target c++11 } } + +#include +#include + +#include +#include + +using Cmp = std::less; + +using __gnu_test::uneq_allocator; + +void test01() +{ + typedef uneq_allocator> alloc_type; + typedef std::multimap test_type; + test_type v1(alloc_type(1)); + const char* str = "A long enough string to require dynamic allocation"; + v1 = { { 1, str } }; + + alloc_type a2(2); + test_type v2(std::move(v1), a2); + + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(2 == v2.get_allocator().get_personality()); + + VERIFY( v1.begin()->second.empty() ); + VERIFY( v2.begin()->second == str ); +} + + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/multiset/allocator/move_cons.cc b/libstdc++-v3/testsuite/23_containers/multiset/allocator/move_cons.cc new file mode 100644 index 00000000000..bc7356be0ae --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/multiset/allocator/move_cons.cc @@ -0,0 +1,53 @@ +// 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 +// . + +// { dg-do run { target c++11 } } + +#include +#include + +#include +#include + +using Cmp = std::less; + +using __gnu_test::uneq_allocator; + +void test01() +{ + typedef uneq_allocator alloc_type; + typedef std::multiset test_type; + test_type v1(alloc_type(1)); + const char* str = "A long enough string to require dynamic allocation"; + v1 = { str }; + + alloc_type a2(2); + test_type v2(std::move(v1), a2); + + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(2 == v2.get_allocator().get_personality()); + + VERIFY( v1.count(str) == 0 ); + VERIFY( v2.count(str) == 1 ); +} + + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/set/allocator/move_cons.cc b/libstdc++-v3/testsuite/23_containers/set/allocator/move_cons.cc new file mode 100644 index 00000000000..137d50d4ee8 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/set/allocator/move_cons.cc @@ -0,0 +1,53 @@ +// 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 +// . + +// { dg-do run { target c++11 } } + +#include +#include + +#include +#include + +using Cmp = std::less; + +using __gnu_test::uneq_allocator; + +void test01() +{ + typedef uneq_allocator alloc_type; + typedef std::set test_type; + test_type v1(alloc_type(1)); + const char* str = "A long enough string to require dynamic allocation"; + v1 = { str }; + + alloc_type a2(2); + test_type v2(std::move(v1), a2); + + VERIFY(1 == v1.get_allocator().get_personality()); + VERIFY(2 == v2.get_allocator().get_personality()); + + VERIFY( v1.count(str) == 0 ); + VERIFY( v2.count(str) == 1 ); +} + + +int main() +{ + test01(); + return 0; +} --------------871529B705217F03A6A2F1B0--