From: "François Dumont" <frs.dumont@gmail.com>
To: Jonathan Wakely <jwakely@redhat.com>
Cc: "libstdc++@gcc.gnu.org" <libstdc++@gcc.gnu.org>,
gcc-patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH] Remove lambdas from _Rb_tree
Date: Thu, 19 Nov 2020 14:20:09 +0100 [thread overview]
Message-ID: <cb20a180-a3d4-80b8-1400-04bf4077b24a@gmail.com> (raw)
In-Reply-To: <20201119113127.GC1312820@redhat.com>
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<typename _Arg>
>>>> Â Â Â Â Â _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<typename _Arg>
>>>> Â Â Â Â Â _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<typename _NodeGen>
>>>> +#if __cplusplus >= 201103L
>>>> +Â Â Â Â Â template<typename _Tree>
>>>> +Â Â Â static constexpr
>>>> +Â Â Â typename conditional<std::is_lvalue_reference<_Tree>::value,
>>>> +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â const value_type&,
>>>> value_type&&>::type
>>>> +Â Â Â _S_fwd_value_for(value_type& __val) noexcept
>>>> +Â Â Â { return std::move(__val); }
>>>> +#else
>>>> +Â Â Â Â Â template<typename _Tree>
>>>> +Â Â Â static const value_type&
>>>> +Â Â Â _S_fwd_value_for(value_type& __val)
>>>> +Â Â Â { return __val; }
>>>> +#endif
>>>> +
>>>> +Â Â Â Â Â template<typename _Tree, typename _NodeGen>
>>>> Â Â Â Â _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<bool _Move, typename _NodeGen>
>>> Â Â Â Â _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<is_lvalue_reference<_Tree>::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<typename _NodeGen>
>>>> +Â Â Â Â Â template<typename _Tree, typename _NodeGen>
>>>> Â Â Â Â _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<typename _NodeGen>
>>>> +Â Â Â Â Â template<typename _Tree, typename _NodeGen>
>>>> Â Â Â Â _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 _Key, typename _Val, typename _KoV,
>>>> Â Â Â Â Â Â typename _Compare, typename _Alloc>
>>>> -Â Â Â template<typename _NodeGen>
>>>> +Â Â Â template<typename _Tree, typename _NodeGen>
>>>> Â Â Â Â Â 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<typename _Arg>
>> _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<typename _Arg>
>> _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<typename _NodeGen>
>> + template<bool _Move, typename _NodeGen>
>> _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<typename _NodeGen>
>> + template<bool _Move, typename _NodeGen>
>> _Link_type
>> - _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
>> + _M_copy(_Link_type, _Base_ptr, _NodeGen&);
>>
>> - template<typename _NodeGen>
>> + template<bool _Move, typename _NodeGen>
>> _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<false>(__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<value_type&>(__cval);
>> - return __an(std::move_if_noexcept(__val));
>> - };
>> - _M_root() = _M_copy(__x, __lbd);
>> + _M_root() =
>> + _M_copy<__move_if_noexcept_cond<value_type>::value>(__x, __an);
>
> Should this be !__move_if_noexcept_cond<value_type>::value ?
Yes, this is why I was not confident about this patch for the moment. I
knew I had to check this and at the same time check if a test is
catching this.
>
> 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<typename _Tp>
> using __use_copy_for_exception_safety
> = typename __and_<__not_<is_nothrow_move_constructible<_Tp>>,
> is_copy_constructible<_Tp>>::type;
Indeed, I find it confusing too. I'll try that.
>
>
>
>> }
>> }
>>
>> @@ -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<value_type&>(__cval);
>> - return __roan(std::move(__val));
>> - };
>> - _M_root() = _M_copy(__x, __lbd);
>> + _M_root() = _M_copy<true>(__x, __roan);
>
> I've realised the downside of my suggestion: _M_copy<true> does a move
> and _M_copy<false> 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.
>
I was thinking to simply rename _Move with a clearer name like: _MoveValues.
But your proposal makes the code clearer even at call site so I'll do it.
>
>> __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<false>(__x, __roan);
>> }
>>
>> return *this;
>> @@ -1859,29 +1849,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>
>> template<typename _Key, typename _Val, typename _KoV,
>> typename _Compare, typename _Alloc>
>> - template<typename _NodeGen>
>> + template<bool _Move, typename _NodeGen>
>> 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);
>> }
>
next prev parent reply other threads:[~2020-11-19 13:20 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-11-17 20:51 François Dumont
2020-11-17 23:50 ` Jonathan Wakely
2020-11-19 6:46 ` François Dumont
2020-11-19 11:31 ` Jonathan Wakely
2020-11-19 13:20 ` François Dumont [this message]
2020-11-20 7:17 ` François Dumont
2020-11-20 10:22 ` Jonathan Wakely
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=cb20a180-a3d4-80b8-1400-04bf4077b24a@gmail.com \
--to=frs.dumont@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=jwakely@redhat.com \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).