* [PATCH] Remove lambdas from _Rb_tree @ 2020-11-17 20:51 François Dumont 2020-11-17 23:50 ` Jonathan Wakely 0 siblings, 1 reply; 7+ messages in thread From: François Dumont @ 2020-11-17 20:51 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 1128 bytes --] 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 ? François [-- Attachment #2: tree.patch --] [-- Type: text/x-patch, Size: 9153 bytes --] 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&& #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), + _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())); __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 { 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&); - 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) { - _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); _M_leftmost() = _S_minimum(__root); _M_rightmost() = _S_maximum(__root); _M_impl._M_node_count = __x._M_impl._M_node_count; @@ -977,7 +990,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) { if (__x._M_root() != nullptr) - _M_move_data(__x, false_type{}); + _M_move_data(std::move(__x), false_type{}); } public: @@ -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); #endif #if __cplusplus > 201402L @@ -1648,20 +1661,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Compare, typename _Alloc> void _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_move_data(_Rb_tree& __x, false_type) + _M_move_data(_Rb_tree&& __x, false_type) { if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) - _M_move_data(__x, true_type()); + _M_move_data(std::move(__x), true_type()); else { + using _Fwd_Rbt = typename + conditional<__move_if_noexcept_cond<value_type>::value, + const _Rb_tree&, _Rb_tree&&>::type; _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(std::forward<_Fwd_Rbt>(__x), __an); } } @@ -1669,11 +1679,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Compare, typename _Alloc> inline void _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_move_assign(_Rb_tree& __x, true_type) + _M_move_assign(_Rb_tree&& __x, true_type) { clear(); if (__x._M_root() != nullptr) - _M_move_data(__x, true_type()); + _M_move_data(std::move(__x), true_type()); std::__alloc_on_move(_M_get_Node_allocator(), __x._M_get_Node_allocator()); } @@ -1682,10 +1692,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Compare, typename _Alloc> void _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_move_assign(_Rb_tree& __x, false_type) + _M_move_assign(_Rb_tree&& __x, false_type) { if (_M_get_Node_allocator() == __x._M_get_Node_allocator()) - return _M_move_assign(__x, true_type{}); + return _M_move_assign(std::move(__x), true_type{}); // Try to move each node reusing existing nodes and copying __x nodes // structure. @@ -1693,13 +1703,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(std::move(__x), __roan); __x.clear(); } } @@ -1713,7 +1717,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION && is_nothrow_move_assignable<_Compare>::value) { _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare); - _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>()); + _M_move_assign(std::move(__x), + __bool_constant<_Alloc_traits::_S_nothrow_move()>()); return *this; } @@ -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, + _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); } ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Remove lambdas from _Rb_tree 2020-11-17 20:51 [PATCH] Remove lambdas from _Rb_tree François Dumont @ 2020-11-17 23:50 ` Jonathan Wakely 2020-11-19 6:46 ` François Dumont 0 siblings, 1 reply; 7+ messages in thread From: Jonathan Wakely @ 2020-11-17 23:50 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches 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. >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); > } ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Remove lambdas from _Rb_tree 2020-11-17 23:50 ` Jonathan Wakely @ 2020-11-19 6:46 ` François Dumont 2020-11-19 11:31 ` Jonathan Wakely 0 siblings, 1 reply; 7+ messages in thread From: François Dumont @ 2020-11-19 6:46 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 12659 bytes --] 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<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); >> } > [-- Attachment #2: tree.patch --] [-- Type: text/x-patch, Size: 5946 bytes --] 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())); __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 { 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); } } @@ -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); __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); } ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Remove lambdas from _Rb_tree 2020-11-19 6:46 ` François Dumont @ 2020-11-19 11:31 ` Jonathan Wakely 2020-11-19 13:20 ` François Dumont 2020-11-20 7:17 ` François Dumont 0 siblings, 2 replies; 7+ messages in thread From: Jonathan Wakely @ 2020-11-19 11:31 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches 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 ? 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; > } > } > >@@ -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. > __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); > } ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Remove lambdas from _Rb_tree 2020-11-19 11:31 ` Jonathan Wakely @ 2020-11-19 13:20 ` François Dumont 2020-11-20 7:17 ` François Dumont 1 sibling, 0 replies; 7+ messages in thread From: François Dumont @ 2020-11-19 13:20 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches 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); >> } > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Remove lambdas from _Rb_tree 2020-11-19 11:31 ` Jonathan Wakely 2020-11-19 13:20 ` François Dumont @ 2020-11-20 7:17 ` François Dumont 2020-11-20 10:22 ` Jonathan Wakely 1 sibling, 1 reply; 7+ messages in thread From: François Dumont @ 2020-11-20 7:17 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 26221 bytes --] 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<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 ? > > 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; > > > >> } >> } >> >> @@ -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. > > >> __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); >> } > [-- Attachment #2: tree.patch --] [-- Type: text/x-patch, Size: 13516 bytes --] 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<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,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_put_node(__p); } - template<typename _NodeGen> + template<bool _MoveValue, 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<_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<typename _NodeGen> + enum { __as_lvalue, __as_rvalue }; + + template<bool _MoveValues, 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 _MoveValues, 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<_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<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); } } @@ -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<value_type&>(__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<typename _Key, typename _Val, typename _KoV, typename _Compare, typename _Alloc> - template<typename _NodeGen> + template<bool _MoveValues, 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<_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 +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++11 } } + +#include <map> +#include <string> + +#include <testsuite_hooks.h> +#include <testsuite_allocator.h> + +using Cmp = std::less<int>; + +using __gnu_test::uneq_allocator; + +void test01() +{ + typedef uneq_allocator<std::pair<const int, std::string>> alloc_type; + typedef std::map<int, std::string, Cmp, alloc_type> 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 +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++11 } } + +#include <map> +#include <string> + +#include <testsuite_hooks.h> +#include <testsuite_allocator.h> + +using Cmp = std::less<int>; + +using __gnu_test::uneq_allocator; + +void test01() +{ + typedef uneq_allocator<std::pair<const int, std::string>> alloc_type; + typedef std::multimap<int, std::string, Cmp, alloc_type> 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 +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++11 } } + +#include <set> +#include <string> + +#include <testsuite_hooks.h> +#include <testsuite_allocator.h> + +using Cmp = std::less<std::string>; + +using __gnu_test::uneq_allocator; + +void test01() +{ + typedef uneq_allocator<std::string> alloc_type; + typedef std::multiset<std::string, Cmp, alloc_type> 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 +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++11 } } + +#include <set> +#include <string> + +#include <testsuite_hooks.h> +#include <testsuite_allocator.h> + +using Cmp = std::less<std::string>; + +using __gnu_test::uneq_allocator; + +void test01() +{ + typedef uneq_allocator<std::string> alloc_type; + typedef std::set<std::string, Cmp, alloc_type> 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; +} ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Remove lambdas from _Rb_tree 2020-11-20 7:17 ` François Dumont @ 2020-11-20 10:22 ` Jonathan Wakely 0 siblings, 0 replies; 7+ messages in thread From: Jonathan Wakely @ 2020-11-20 10:22 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 20/11/20 08:17 +0100, François Dumont via Libstdc++ wrote: >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. You can do it as a member, but the syntax is ugly: template<typename _Key, typename _Val, typename _KoV, typename _Compare, typename _Alloc> template<typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_CopyType _MoveValues, typename _NodeGen> typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: _M_copy(_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen) >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. Yes, we can do that later if needed. >I wonder if I am right to check moved values in those tests ? Yes, I think that's good. >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. It's not required to clear them. Leaving them with moved-from values means the memory isn't deallocated, and those nodes can be reused if the container gets assigned new values. >   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 ? Yes, OK for trunk, thanks! ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2020-11-20 10:23 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-11-17 20:51 [PATCH] Remove lambdas from _Rb_tree 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 2020-11-20 7:17 ` François Dumont 2020-11-20 10:22 ` Jonathan Wakely
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).