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. 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); >>           } >