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