| Message ID | 23378b8f-b9fa-a263-41fc-457b931a3987@gmail.com |
|---|---|
| State | New |
| Headers | show |
| Series | PR libstdc++/92124 on hashtable | expand |
On 07/11/19 20:28 +0100, François Dumont wrote: >From what I understood from recent fix the unordered containers need >to be updated the same way. > >I hope you'll appreciate the usage of rvalue forwarding. Containers Yes, I think it makes sense. >node values are moved as soon as _M_assign is called with a rvalue >reference to the source container. > >Additionnaly this patch removes usages of lambdas in _Hashtable. > >If you confirm it I'll check for the same on _Rb_tree. > > * include/bits/hashtable.h (_Hashtable<>::__alloc_node_gen_t): New > template alias. > (_Hashtable<>::__mv_if_value_type_mv_noexcept): New. > (_Hashtable<>::__fwd_value): New. > (_Hashtable<>::_M_assign_elements<>): Remove _NodeGenerator template > parameter. > (_Hashtable<>::_M_assign<>): Add _Ht template parameter. > (_Hashtable<>::operator=(const _Hashtable<>&)): Adapt. > (_Hashtable<>::_M_move_assign): Adapt. > (_Hashtable<>::_Hashtable(const _Hashtable&)): Adapt. > (_Hashtable<>::_Hashtable(const _Hashtable&, const allocator_type&)): > Adapt. > (_Hashtable<>::_Hashtable(_Hashtable&&, const allocator_type&)): > Adapt. > * testsuite/23_containers/unordered_set/92124.cc: New. > >Tested under Linux x86_64. > >Ok to commit ? > >François > >diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h >index ab579a7059e..c2b2219d471 100644 >--- a/libstdc++-v3/include/bits/hashtable.h >+++ b/libstdc++-v3/include/bits/hashtable.h >@@ -255,6 +255,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > using __reuse_or_alloc_node_gen_t = > __detail::_ReuseOrAllocNode<__node_alloc_type>; >+ using __alloc_node_gen_t = >+ __detail::_AllocNode<__node_alloc_type>; > > // Simple RAII type for managing a node containing an element > struct _Scoped_node >@@ -280,6 +282,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > __node_type* _M_node; > }; > >+ template<typename _Tp> >+ static constexpr >+ typename conditional<__move_if_noexcept_cond<value_type>::value, >+ const _Tp&, _Tp&&>::type >+ __mv_if_value_type_mv_noexcept(_Tp& __x) noexcept >+ { return std::move(__x); } This is only used in one place. Adding a function doesn't seem worthwhile, you can just do this where you use it: using _Fwd_Ht = typename conditional<__move_if_noexcept_cond<value_type>::value, const _Ht&, _Ht>::type; _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen); >+ template<typename _Ht> >+ static constexpr >+ typename conditional<!std::is_lvalue_reference<_Ht>::value, >+ value_type&&, const value_type&>::type I think I'd prefer to reverse the condition, i.e. typename conditional<is_lvalue_reference<_Ht>::value, const value_type&, value_type&&>::type >+ __fwd_value(_Ht&&, value_type& __val) noexcept >+ { return std::move(__val); } Since this doesn't use the first parameter, it can just be removed: template<typename _Ht> static constexpr typename conditional<std::is_lvalue_reference<_Ht>::value, const value_type&, value_type&&>::type __fwd_value(value_type& __val) noexcept { return std::move(__val); } That simplifies the usage from: __fwd_value(std::forward<_Ht>(__ht), __ht_n->_M_v())) so it becomes: __fwd_value<_Ht>(__ht_n->_M_v())) Maybe __fwd_value<_Ht> should be __fwd_value_for<_Ht> so it's clear how it depends on _Ht (because otherwise it looks like it is forwarding as _Ht&& like std::forward<_Ht> would). What do you think?
On 07/11/19 20:28 +0100, François Dumont wrote: >From what I understood from recent fix the unordered containers need >to be updated the same way. > >I hope you'll appreciate the usage of rvalue forwarding. Containers >node values are moved as soon as _M_assign is called with a rvalue >reference to the source container. > >Additionnaly this patch removes usages of lambdas in _Hashtable. > >If you confirm it I'll check for the same on _Rb_tree. > > * include/bits/hashtable.h (_Hashtable<>::__alloc_node_gen_t): New > template alias. > (_Hashtable<>::__mv_if_value_type_mv_noexcept): New. > (_Hashtable<>::__fwd_value): New. > (_Hashtable<>::_M_assign_elements<>): Remove _NodeGenerator template > parameter. > (_Hashtable<>::_M_assign<>): Add _Ht template parameter. > (_Hashtable<>::operator=(const _Hashtable<>&)): Adapt. > (_Hashtable<>::_M_move_assign): Adapt. > (_Hashtable<>::_Hashtable(const _Hashtable&)): Adapt. > (_Hashtable<>::_Hashtable(const _Hashtable&, const allocator_type&)): > Adapt. > (_Hashtable<>::_Hashtable(_Hashtable&&, const allocator_type&)): > Adapt. > * testsuite/23_containers/unordered_set/92124.cc: New. > >Tested under Linux x86_64. > >Ok to commit ? > >François > >diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h >index ab579a7059e..c2b2219d471 100644 >--- a/libstdc++-v3/include/bits/hashtable.h >+++ b/libstdc++-v3/include/bits/hashtable.h >@@ -255,6 +255,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > using __reuse_or_alloc_node_gen_t = > __detail::_ReuseOrAllocNode<__node_alloc_type>; >+ using __alloc_node_gen_t = >+ __detail::_AllocNode<__node_alloc_type>; > > // Simple RAII type for managing a node containing an element > struct _Scoped_node >@@ -280,6 +282,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > __node_type* _M_node; > }; > >+ template<typename _Tp> >+ static constexpr >+ typename conditional<__move_if_noexcept_cond<value_type>::value, >+ const _Tp&, _Tp&&>::type >+ __mv_if_value_type_mv_noexcept(_Tp& __x) noexcept >+ { return std::move(__x); } >+ >+ template<typename _Ht> >+ static constexpr >+ typename conditional<!std::is_lvalue_reference<_Ht>::value, >+ value_type&&, const value_type&>::type >+ __fwd_value(_Ht&&, value_type& __val) noexcept >+ { return std::move(__val); } >+ > // Metaprogramming for picking apart hash caching. > template<typename _Cond> > using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>; >@@ -406,13 +422,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > // Assign *this using another _Hashtable instance. Either elements > // are copy or move depends on the _NodeGenerator. N.B. I know this comment was already there, but could you please change the second sentence to say: "Whether elements are copied or moved ..." >- template<typename _Ht, typename _NodeGenerator> >+ template<typename _Ht> > void >- _M_assign_elements(_Ht&&, const _NodeGenerator&); >+ _M_assign_elements(_Ht&&); > >- template<typename _NodeGenerator> >+ template<typename _Ht, typename _NodeGenerator> > void >- _M_assign(const _Hashtable&, const _NodeGenerator&); >+ _M_assign(_Ht&&, const _NodeGenerator&); > > void > _M_move_assign(_Hashtable&&, true_type);
On 1/6/20 4:17 PM, Jonathan Wakely wrote: > On 07/11/19 20:28 +0100, François Dumont wrote: >> From what I understood from recent fix the unordered containers need >> to be updated the same way. >> >> I hope you'll appreciate the usage of rvalue forwarding. Containers > > Yes, I think it makes sense. > >> node values are moved as soon as _M_assign is called with a rvalue >> reference to the source container. >> >> Additionnaly this patch removes usages of lambdas in _Hashtable. >> >> If you confirm it I'll check for the same on _Rb_tree. >> >> * include/bits/hashtable.h (_Hashtable<>::__alloc_node_gen_t): New >> template alias. >> (_Hashtable<>::__mv_if_value_type_mv_noexcept): New. >> (_Hashtable<>::__fwd_value): New. >> (_Hashtable<>::_M_assign_elements<>): Remove _NodeGenerator template >> parameter. >> (_Hashtable<>::_M_assign<>): Add _Ht template parameter. >> (_Hashtable<>::operator=(const _Hashtable<>&)): Adapt. >> (_Hashtable<>::_M_move_assign): Adapt. >> (_Hashtable<>::_Hashtable(const _Hashtable&)): Adapt. >> (_Hashtable<>::_Hashtable(const _Hashtable&, const >> allocator_type&)): >> Adapt. >> (_Hashtable<>::_Hashtable(_Hashtable&&, const allocator_type&)): >> Adapt. >> * testsuite/23_containers/unordered_set/92124.cc: New. >> >> Tested under Linux x86_64. >> >> Ok to commit ? >> >> François >> > >> diff --git a/libstdc++-v3/include/bits/hashtable.h >> b/libstdc++-v3/include/bits/hashtable.h >> index ab579a7059e..c2b2219d471 100644 >> --- a/libstdc++-v3/include/bits/hashtable.h >> +++ b/libstdc++-v3/include/bits/hashtable.h >> @@ -255,6 +255,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >> >> using __reuse_or_alloc_node_gen_t = >> __detail::_ReuseOrAllocNode<__node_alloc_type>; >> + using __alloc_node_gen_t = >> + __detail::_AllocNode<__node_alloc_type>; >> >> // Simple RAII type for managing a node containing an element >> struct _Scoped_node >> @@ -280,6 +282,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >> __node_type* _M_node; >> }; >> >> + template<typename _Tp> >> + static constexpr >> + typename conditional<__move_if_noexcept_cond<value_type>::value, >> + const _Tp&, _Tp&&>::type >> + __mv_if_value_type_mv_noexcept(_Tp& __x) noexcept >> + { return std::move(__x); } > > This is only used in one place. Adding a function doesn't seem > worthwhile, you can just do this where you use it: > > using _Fwd_Ht = typename > conditional<__move_if_noexcept_cond<value_type>::value, > const _Ht&, _Ht>::type; > _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen); > > >> + template<typename _Ht> >> + static constexpr >> + typename conditional<!std::is_lvalue_reference<_Ht>::value, >> + value_type&&, const value_type&>::type > > I think I'd prefer to reverse the condition, i.e. > > typename conditional<is_lvalue_reference<_Ht>::value, > const value_type&, value_type&&>::type > >> + __fwd_value(_Ht&&, value_type& __val) noexcept >> + { return std::move(__val); } > > Since this doesn't use the first parameter, it can just be removed: > > template<typename _Ht> > static constexpr > typename conditional<std::is_lvalue_reference<_Ht>::value, > const value_type&, value_type&&>::type > __fwd_value(value_type& __val) noexcept > { return std::move(__val); } > > That simplifies the usage from: > > __fwd_value(std::forward<_Ht>(__ht), __ht_n->_M_v())) > > so it becomes: > > __fwd_value<_Ht>(__ht_n->_M_v())) > > > Maybe __fwd_value<_Ht> should be __fwd_value_for<_Ht> so it's clear > how it depends on _Ht (because otherwise it looks like it is > forwarding as _Ht&& like std::forward<_Ht> would). > > What do you think? The simpler the better. So here is the cleaned patch. Regarding the comment, I also rewrite it a little cause copy/move of elements doesn't depend on _NodeGenerator anymore. PR libstdc++/92124 * include/bits/hashtable.h (_Hashtable<>::__alloc_node_gen_t): New template alias. (_Hashtable<>::__fwd_value_for): New. (_Hashtable<>::_M_assign_elements<>): Remove _NodeGenerator template parameter. (_Hashtable<>::_M_assign<>): Add _Ht template parameter. (_Hashtable<>::operator=(const _Hashtable<>&)): Adapt. (_Hashtable<>::_M_move_assign): Adapt. (_Hashtable<>::_Hashtable(const _Hashtable&)): Adapt. (_Hashtable<>::_Hashtable(const _Hashtable&, const allocator_type&)): Adapt. (_Hashtable<>::_Hashtable(_Hashtable&&, const allocator_type&)): Adapt. * testsuite/23_containers/unordered_set/92124.cc: New. Tested under Linux x86_64. Ok to commit ? François
On 08/01/20 06:43 +0100, François Dumont wrote: >@@ -404,15 +413,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > _M_begin() const > { return static_cast<__node_type*>(_M_before_begin._M_nxt); } > >- // Assign *this using another _Hashtable instance. Either elements >- // are copy or move depends on the _NodeGenerator. >- template<typename _Ht, typename _NodeGenerator> >+ // Assign *this using another _Hashtable instance. Whether elements >+ // are copy or move depends on the _Ht reference. Should be "are copied or moved". OK for trunk with that change, thanks!
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index ab579a7059e..c2b2219d471 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -255,6 +255,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __reuse_or_alloc_node_gen_t = __detail::_ReuseOrAllocNode<__node_alloc_type>; + using __alloc_node_gen_t = + __detail::_AllocNode<__node_alloc_type>; // Simple RAII type for managing a node containing an element struct _Scoped_node @@ -280,6 +282,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_type* _M_node; }; + template<typename _Tp> + static constexpr + typename conditional<__move_if_noexcept_cond<value_type>::value, + const _Tp&, _Tp&&>::type + __mv_if_value_type_mv_noexcept(_Tp& __x) noexcept + { return std::move(__x); } + + template<typename _Ht> + static constexpr + typename conditional<!std::is_lvalue_reference<_Ht>::value, + value_type&&, const value_type&>::type + __fwd_value(_Ht&&, value_type& __val) noexcept + { return std::move(__val); } + // Metaprogramming for picking apart hash caching. template<typename _Cond> using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>; @@ -406,13 +422,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Assign *this using another _Hashtable instance. Either elements // are copy or move depends on the _NodeGenerator. - template<typename _Ht, typename _NodeGenerator> + template<typename _Ht> void - _M_assign_elements(_Ht&&, const _NodeGenerator&); + _M_assign_elements(_Ht&&); - template<typename _NodeGenerator> + template<typename _Ht, typename _NodeGenerator> void - _M_assign(const _Hashtable&, const _NodeGenerator&); + _M_assign(_Ht&&, const _NodeGenerator&); void _M_move_assign(_Hashtable&&, true_type); @@ -1051,11 +1067,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bucket_count = __ht._M_bucket_count; _M_element_count = __ht._M_element_count; _M_rehash_policy = __ht._M_rehash_policy; + __alloc_node_gen_t __alloc_node_gen(*this); __try { - _M_assign(__ht, - [this](const __node_type* __n) - { return this->_M_allocate_node(__n->_M_v()); }); + _M_assign(__ht, __alloc_node_gen); } __catch(...) { @@ -1070,9 +1085,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } // Reuse allocated buckets and nodes. - _M_assign_elements(__ht, - [](const __reuse_or_alloc_node_gen_t& __roan, const __node_type* __n) - { return __roan(__n->_M_v()); }); + _M_assign_elements(__ht); return *this; } @@ -1080,11 +1093,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, typename _Traits> - template<typename _Ht, typename _NodeGenerator> + template<typename _Ht> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_assign_elements(_Ht&& __ht, const _NodeGenerator& __node_gen) + _M_assign_elements(_Ht&& __ht) { __bucket_type* __former_buckets = nullptr; std::size_t __former_bucket_count = _M_bucket_count; @@ -1107,9 +1120,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_rehash_policy = __ht._M_rehash_policy; __reuse_or_alloc_node_gen_t __roan(_M_begin(), *this); _M_before_begin._M_nxt = nullptr; - _M_assign(__ht, - [&__node_gen, &__roan](__node_type* __n) - { return __node_gen(__roan, __n); }); + _M_assign(std::forward<_Ht>(__ht), __roan); if (__former_buckets) _M_deallocate_buckets(__former_buckets, __former_bucket_count); } @@ -1133,11 +1144,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, typename _Traits> - template<typename _NodeGenerator> + template<typename _Ht, typename _NodeGenerator> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen) + _M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen) { __bucket_type* __buckets = nullptr; if (!_M_buckets) @@ -1151,7 +1162,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // First deal with the special first node pointed to by // _M_before_begin. __node_type* __ht_n = __ht._M_begin(); - __node_type* __this_n = __node_gen(__ht_n); + __node_type* __this_n + = __node_gen(__fwd_value(std::forward<_Ht>(__ht), + __ht_n->_M_v())); this->_M_copy_code(__this_n, __ht_n); _M_before_begin._M_nxt = __this_n; _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin; @@ -1160,7 +1173,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base* __prev_n = __this_n; for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) { - __this_n = __node_gen(__ht_n); + __this_n = __node_gen(__fwd_value(std::forward<_Ht>(__ht), + __ht_n->_M_v())); __prev_n->_M_nxt = __this_n; this->_M_copy_code(__this_n, __ht_n); size_type __bkt = _M_bucket_index(__this_n); @@ -1241,9 +1255,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION else { // Can't move memory, move elements then. - _M_assign_elements(std::move(__ht), - [](const __reuse_or_alloc_node_gen_t& __roan, __node_type* __n) - { return __roan(std::move_if_noexcept(__n->_M_v())); }); + _M_assign_elements(std::move(__ht)); __ht.clear(); } } @@ -1265,9 +1277,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_element_count(__ht._M_element_count), _M_rehash_policy(__ht._M_rehash_policy) { - _M_assign(__ht, - [this](const __node_type* __n) - { return this->_M_allocate_node(__n->_M_v()); }); + __alloc_node_gen_t __alloc_node_gen(*this); + _M_assign(__ht, __alloc_node_gen); } template<typename _Key, typename _Value, @@ -1318,9 +1329,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_element_count(__ht._M_element_count), _M_rehash_policy(__ht._M_rehash_policy) { - _M_assign(__ht, - [this](const __node_type* __n) - { return this->_M_allocate_node(__n->_M_v()); }); + __alloc_node_gen_t __alloc_node_gen(*this); + _M_assign(__ht, __alloc_node_gen); } template<typename _Key, typename _Value, @@ -1358,12 +1368,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } else { - _M_assign(__ht, - [this](__node_type* __n) - { - return this->_M_allocate_node( - std::move_if_noexcept(__n->_M_v())); - }); + __alloc_node_gen_t __alloc_gen(*this); + _M_assign(__mv_if_value_type_mv_noexcept(__ht), __alloc_gen); __ht.clear(); } } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/92124.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/92124.cc new file mode 100644 index 00000000000..a3b41bbb687 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/92124.cc @@ -0,0 +1,79 @@ +// Copyright (C) 2019 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 <unordered_set> + +#include <testsuite_allocator.h> +#include <testsuite_hooks.h> + +int moves = 0; + +struct X +{ + X() = default; + X(const X&) = default; + X(int i) : _i(i) {} + + // Move constructor might throw + X(X&& x) noexcept(false) + { + this->_i = x._i; + x._i = -1; + ++moves; + } + + int _i; +}; + +struct XHasher +{ + std::size_t + operator()(const X& x) const noexcept + { return x._i; } +}; + +struct XEqualTo +{ + bool + operator()(const X& lhs, const X& rhs) const noexcept + { return lhs._i == rhs._i; } +}; + +void +test01() +{ + using A = __gnu_test::propagating_allocator<X, false>; + A a1(1), a2(2); + std::unordered_set<X, XHasher, XEqualTo, A> u1(a1), u2(a2); + u1 = { X(0), X(1), X(2) }; + u2 = { X(3), X(4), X(5) }; + + moves = 0; + u1 = std::move(u2); + + VERIFY( moves == 3 ); + VERIFY( u1.count(X(1)) == 0 ); + VERIFY( u1.count(X(3)) == 1 ); +} + +int +main() +{ + test01(); +}