| Message ID | 696186d1-b00c-4c42-6228-f00bba8e40ff@gmail.com |
|---|---|
| State | New |
| Headers | show |
| Series | Fix move_if_noexcept usages in _Hashtable | expand |
On 04/12/18 07:45 +0100, François Dumont wrote: >Hi > > This patch fix a minor problem with usage of std::move_if_noexcept. >We use it to move node content if move construtor is noexcept but we >eventually use the allocator_type::construct method which might be >slightly different. I think it is better to check for this method >noexcept qualification. This is likely to pessimize some code, since most allocators do not have an exception-specification on their construct members. > Moreover I have added a special overload for nodes containing a >std::pair. It is supposed to allow move semantic in associative >containers where Key is stored as const deleting std::pair move >constructor. In this case we should still move the Value part. > > It doesn't work for the moment because the std::pair piecewise >constructor has no noexcept qualification. Is there any plan to add it >? I think adding it will force including <tuple> in stl_pair.h, is it >fine ? > > If this evolution is accepted I'll adapt it for _Rb_tree that has >the same problem. > > Working on this I also notice that content of initialization_list is >not moved. Is there a plan to make initialization_list iterator type >like move_iterator ? Should containers use >__make_move_iterator_if_noexcept ? No. Whether to allow moving from std::initializer_list is an active topic, see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1249r0.html > Tested under Linux x86_64 normal mode. > > Ok to commit this first step ? No, this is not suitable for stage 3. It seems too risky. We can reconsider it during stage 1, but I'd like to see (at least) a new test showing a bug with the current code. For example, a type with a move constructor that is noexcept, but when used with a scoped_allocator_adaptor (which calls something other than the move constructor) we incorrectly move elements, and lose data when an exception happens.
On 12/4/18 3:38 PM, Jonathan Wakely wrote: > On 04/12/18 07:45 +0100, François Dumont wrote: >> Hi >> >> This patch fix a minor problem with usage of std::move_if_noexcept. >> We use it to move node content if move construtor is noexcept but we >> eventually use the allocator_type::construct method which might be >> slightly different. I think it is better to check for this method >> noexcept qualification. > > This is likely to pessimize some code, since most allocators do not > have an exception-specification on their construct members. > Perhaps but the Standard mandates to call allocator construct so we don't have choice. It is surprising to consider value_type move constructor when we don't know what allocator construct does. Most users do not change from std::allocator or, even if they do, do not implement construct so impact should be limited. >> Moreover I have added a special overload for nodes containing a >> std::pair. It is supposed to allow move semantic in associative >> containers where Key is stored as const deleting std::pair move >> constructor. In this case we should still move the Value part. >> >> It doesn't work for the moment because the std::pair piecewise >> constructor has no noexcept qualification. Is there any plan to add >> it ? I think adding it will force including <tuple> in stl_pair.h, is >> it fine ? No feedback on this point ? Is using std::pair piecewise constructor ok ? >> >> If this evolution is accepted I'll adapt it for _Rb_tree that has >> the same problem. >> >> Working on this I also notice that content of initialization_list >> is not moved. Is there a plan to make initialization_list iterator >> type like move_iterator ? Should containers use >> __make_move_iterator_if_noexcept ? > > No. > > Whether to allow moving from std::initializer_list is an active topic, > see > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1249r0.html > Ok, nice, allowing emplace build of values would be even better, I'll have a closer look. >> Tested under Linux x86_64 normal mode. >> >> Ok to commit this first step ? > > No, this is not suitable for stage 3. It seems too risky. > > We can reconsider it during stage 1, but I'd like to see (at least) a > new test showing a bug with the current code. For example, a type with > a move constructor that is noexcept, but when used with a > scoped_allocator_adaptor (which calls something other than the move > constructor) we incorrectly move elements, and lose data when an > exception happens. > > Ok, I'll try.
I reviewed this patch following result of making std::pair piecewise constructor noexcept: https://gcc.gnu.org/ml/libstdc++/2018-12/msg00052.html I restore check of noexcept qualification on move constructor rather than alloc::construct cause when dealing with std::pair<const Key, Value> I want to check for noexcept qualification of Value type move constructor and it doesn't really make sens to check for alloc<Value>::construct when we eventually call alloc<pair<const Key, Value>::construct. I'll submit this officially once back in stage 1. François On 12/4/18 10:43 PM, François Dumont wrote: > On 12/4/18 3:38 PM, Jonathan Wakely wrote: >> On 04/12/18 07:45 +0100, François Dumont wrote: >>> Hi >>> >>> This patch fix a minor problem with usage of >>> std::move_if_noexcept. We use it to move node content if move >>> construtor is noexcept but we eventually use the >>> allocator_type::construct method which might be slightly different. >>> I think it is better to check for this method noexcept qualification. >> >> This is likely to pessimize some code, since most allocators do not >> have an exception-specification on their construct members. >> > Perhaps but the Standard mandates to call allocator construct so we > don't have choice. It is surprising to consider value_type move > constructor when we don't know what allocator construct does. > > Most users do not change from std::allocator or, even if they do, do > not implement construct so impact should be limited. > >>> Moreover I have added a special overload for nodes containing a >>> std::pair. It is supposed to allow move semantic in associative >>> containers where Key is stored as const deleting std::pair move >>> constructor. In this case we should still move the Value part. >>> >>> It doesn't work for the moment because the std::pair piecewise >>> constructor has no noexcept qualification. Is there any plan to add >>> it ? I think adding it will force including <tuple> in stl_pair.h, >>> is it fine ? > > No feedback on this point ? Is using std::pair piecewise constructor ok ? > >>> >>> If this evolution is accepted I'll adapt it for _Rb_tree that has >>> the same problem. >>> >>> Working on this I also notice that content of initialization_list >>> is not moved. Is there a plan to make initialization_list iterator >>> type like move_iterator ? Should containers use >>> __make_move_iterator_if_noexcept ? >> >> No. >> >> Whether to allow moving from std::initializer_list is an active topic, >> see >> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1249r0.html >> > Ok, nice, allowing emplace build of values would be even better, I'll > have a closer look. > >>> Tested under Linux x86_64 normal mode. >>> >>> Ok to commit this first step ? >> >> No, this is not suitable for stage 3. It seems too risky. >> >> We can reconsider it during stage 1, but I'd like to see (at least) a >> new test showing a bug with the current code. For example, a type with >> a move constructor that is noexcept, but when used with a >> scoped_allocator_adaptor (which calls something other than the move >> constructor) we incorrectly move elements, and lose data when an >> exception happens. >> >> > Ok, I'll try. > diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 9a12ad399dc..dfb756cec07 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -266,8 +266,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>; - using __reuse_or_alloc_node_type = - __detail::_ReuseOrAllocNode<__node_alloc_type>; + template<typename _ConstructF> + using __alloc_node_gen_t = + __detail::_AllocNode<__node_alloc_type, _ConstructF>; + + template<typename _ConstructF> + using __reuse_or_alloc_node_gen_t = + __detail::_ReuseOrAllocNode<__node_alloc_type, _ConstructF>; // Metaprogramming for picking apart hash caching. template<typename _Cond> @@ -400,9 +405,9 @@ _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 _NodeGen, typename _Ht> void - _M_assign_elements(_Ht&&, const _NodeGenerator&); + _M_assign_elements(_Ht&&); template<typename _NodeGenerator> void @@ -500,7 +505,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable& operator=(initializer_list<value_type> __l) { - __reuse_or_alloc_node_type __roan(_M_begin(), *this); + __reuse_or_alloc_node_gen_t<_Construct_object_a> + __roan(*this, _M_begin()); _M_before_begin._M_nxt = nullptr; clear(); this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys()); @@ -1047,9 +1053,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_rehash_policy = __ht._M_rehash_policy; __try { - _M_assign(__ht, - [this](const __node_type* __n) - { return this->_M_allocate_node(__n->_M_v()); }); + __alloc_node_gen_t<_Construct_object_a> __ang(*this); + _M_assign(__ht, __ang); } __catch(...) { @@ -1064,9 +1069,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } // Reuse allocated buckets and nodes. - _M_assign_elements(__ht, - [](const __reuse_or_alloc_node_type& __roan, const __node_type* __n) - { return __roan(__n->_M_v()); }); + using __node_gen_t + = __reuse_or_alloc_node_gen_t<_Construct_object_a>; + _M_assign_elements<__node_gen_t>(__ht); return *this; } @@ -1074,11 +1079,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 _NodeGenT, 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; @@ -1099,11 +1104,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __hashtable_base::operator=(std::forward<_Ht>(__ht)); _M_element_count = __ht._M_element_count; _M_rehash_policy = __ht._M_rehash_policy; - __reuse_or_alloc_node_type __roan(_M_begin(), *this); + _NodeGenT __roan(*this, _M_begin()); _M_before_begin._M_nxt = nullptr; - _M_assign(__ht, - [&__node_gen, &__roan](__node_type* __n) - { return __node_gen(__roan, __n); }); + _M_assign(__ht, __roan); if (__former_buckets) _M_deallocate_buckets(__former_buckets, __former_bucket_count); } @@ -1145,7 +1148,7 @@ _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(__ht_n->_M_v()); this->_M_copy_code(__this_n, __ht_n); _M_before_begin._M_nxt = __this_n; #if _GLIBCXX_INLINE_VERSION @@ -1159,7 +1162,7 @@ _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(__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); @@ -1248,9 +1251,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION else { // Can't move memory, move elements then. - _M_assign_elements(std::move(__ht), - [](const __reuse_or_alloc_node_type& __roan, __node_type* __n) - { return __roan(std::move_if_noexcept(__n->_M_v())); }); + using __node_gen_t + = __reuse_or_alloc_node_gen_t<_Move_construct_if_noexcept_object_a>; + _M_assign_elements<__node_gen_t>(std::move(__ht)); __ht.clear(); } } @@ -1272,9 +1275,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<_Construct_object_a> __ang(*this); + _M_assign(__ht, __ang); } template<typename _Key, typename _Value, @@ -1332,9 +1334,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<_Construct_object_a> __ang(*this); + _M_assign(__ht, __ang); } template<typename _Key, typename _Value, @@ -1379,12 +1380,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<_Move_construct_if_noexcept_object_a> __ang(*this); + _M_assign(__ht, __ang); __ht.clear(); } } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index aa4808eab31..fa5c9cc31ed 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -34,6 +34,7 @@ #include <tuple> // for std::tuple, std::forward_as_tuple #include <limits> // for std::numeric_limits #include <bits/stl_algobase.h> // for std::min. +#include <bits/stl_construct.h> // for __construct_object_a. namespace std _GLIBCXX_VISIBILITY(default) { @@ -110,25 +111,53 @@ namespace __detail template<typename _NodeAlloc> struct _Hashtable_alloc; - // Functor recycling a pool of nodes and using allocation once the pool is - // empty. - template<typename _NodeAlloc> - struct _ReuseOrAllocNode + // Functor allocating nodes on demand. + template<typename _NodeAlloc, typename _ConstructF> + struct _AllocNode : public _ConstructF + { + protected: + using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>; + using __node_type = typename __hashtable_alloc::__node_type; + + const _ConstructF& + _M_construct_f() const { return *this; } + + public: + _AllocNode(__hashtable_alloc& __h) + : _M_h(__h) { } + + template<typename _Arg> + __node_type* + operator()(_Arg&& __arg) const + { + return _M_h._M_allocate_node_f(_M_construct_f(), + std::forward<_Arg>(__arg)); + } + + protected: + __hashtable_alloc& _M_h; + }; + + // Functor similar to the previous one but recycling a pool of nodes and using + // allocation once the pool is empty. + template<typename _NodeAlloc, typename _ConstructF> + struct _ReuseOrAllocNode : private _AllocNode<_NodeAlloc, _ConstructF> { private: - using __node_alloc_type = _NodeAlloc; - using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>; + typedef _AllocNode<_NodeAlloc, _ConstructF> _Base; + using __node_type = typename _Base::__node_type; + using __hashtable_alloc = typename _Base::__hashtable_alloc; using __node_alloc_traits = typename __hashtable_alloc::__node_alloc_traits; - using __node_type = typename __hashtable_alloc::__node_type; public: - _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h) - : _M_nodes(__nodes), _M_h(__h) { } + _ReuseOrAllocNode(__hashtable_alloc& __h, __node_type* __nodes) + : _Base(__h), _M_nodes(__nodes) { } + _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete; ~_ReuseOrAllocNode() - { _M_h._M_deallocate_nodes(_M_nodes); } + { this->_M_h._M_deallocate_nodes(_M_nodes); } template<typename _Arg> __node_type* @@ -139,48 +168,27 @@ namespace __detail __node_type* __node = _M_nodes; _M_nodes = _M_nodes->_M_next(); __node->_M_nxt = nullptr; - auto& __a = _M_h._M_node_allocator(); - __node_alloc_traits::destroy(__a, __node->_M_valptr()); + auto& __alloc = this->_M_h._M_node_allocator(); + __node_alloc_traits::destroy(__alloc, __node->_M_valptr()); __try { - __node_alloc_traits::construct(__a, __node->_M_valptr(), - std::forward<_Arg>(__arg)); + this->_M_construct_f()(__alloc, __node->_M_valptr(), + std::forward<_Arg>(__arg)); } __catch(...) { - _M_h._M_deallocate_node_ptr(__node); + this->_M_h._M_deallocate_node_ptr(__node); __throw_exception_again; } + return __node; } - return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); + + return _Base::operator()(std::forward<_Arg>(__arg)); } private: mutable __node_type* _M_nodes; - __hashtable_alloc& _M_h; - }; - - // Functor similar to the previous one but without any pool of nodes to - // recycle. - template<typename _NodeAlloc> - struct _AllocNode - { - private: - using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>; - using __node_type = typename __hashtable_alloc::__node_type; - - public: - _AllocNode(__hashtable_alloc& __h) - : _M_h(__h) { } - - template<typename _Arg> - __node_type* - operator()(_Arg&& __arg) const - { return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); } - - private: - __hashtable_alloc& _M_h; }; // Auxiliary types used for all instantiations of _Hashtable nodes @@ -828,7 +836,8 @@ namespace __detail using __ireturn_type = typename __hashtable_base::__ireturn_type; using __node_type = _Hash_node<_Value, _Traits::__hash_cached::value>; using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>; - using __node_gen_type = _AllocNode<__node_alloc_type>; + using __node_gen_type = _AllocNode<__node_alloc_type, + _Construct_object_a>; __hashtable& _M_conjure_hashtable() @@ -2112,6 +2121,11 @@ namespace __detail __node_type* _M_allocate_node(_Args&&... __args); + template<typename _ConstF, typename... _Args> + __node_type* + _M_allocate_node_f(const _ConstF& __construct_f, + _Args&&... __args); + void _M_deallocate_node(__node_type* __n); @@ -2136,19 +2150,29 @@ namespace __detail typename _Hashtable_alloc<_NodeAlloc>::__node_type* _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args) { - auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1); + return _M_allocate_node_f(_Construct_object_a{}, + std::forward<_Args>(__args)...); + } + + template<typename _NodeAlloc> + template<typename _ConstructF, typename... _Args> + typename _Hashtable_alloc<_NodeAlloc>::__node_type* + _Hashtable_alloc<_NodeAlloc>:: + _M_allocate_node_f(const _ConstructF& __construct_f, _Args&&... __args) + { + auto& __alloc = _M_node_allocator(); + auto __nptr = __node_alloc_traits::allocate(__alloc, 1); __node_type* __n = std::__to_address(__nptr); __try { ::new ((void*)__n) __node_type; - __node_alloc_traits::construct(_M_node_allocator(), - __n->_M_valptr(), - std::forward<_Args>(__args)...); + __construct_f(__alloc, __n->_M_valptr(), + std::forward<_Args>(__args)...); return __n; } __catch(...) { - __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1); + __node_alloc_traits::deallocate(__alloc, __nptr, 1); __throw_exception_again; } } diff --git a/libstdc++-v3/include/bits/stl_construct.h b/libstdc++-v3/include/bits/stl_construct.h index e696ec8b2eb..52d95de28c0 100644 --- a/libstdc++-v3/include/bits/stl_construct.h +++ b/libstdc++-v3/include/bits/stl_construct.h @@ -229,6 +229,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } #endif +#if __cplusplus >= 201103L + template<typename _Allocator, typename _Tp, typename... _Args> + inline void + __construct_object_a(_Allocator& __alloc, _Tp* __dest, _Args&&... __args) + { + typedef allocator_traits<_Allocator> __traits; + __traits::construct(__alloc, __dest, std::forward<_Args>(__args)...); + } + + struct _Construct_object_a + { + template<typename _Allocator, typename _Tp, typename... _Args> + inline void + operator()(_Allocator& __alloc, _Tp* __dest, _Args&&... __args) const + { + __construct_object_a(__alloc, __dest, + std::forward<_Args>(__args)...); + } + }; + + template<typename _Allocator, typename _Tp, typename _Up> + inline void + __move_construct_object_a(_Allocator& __alloc, _Tp* __dest, _Up& __orig) + noexcept( is_nothrow_constructible<_Tp, _Up&&>::value ) + { + typedef allocator_traits<_Allocator> __traits; + __traits::construct(__alloc, __dest, std::move(__orig)); + } + + struct _Move_construct_if_noexcept_object_a + { + template<typename _Allocator, typename _Tp, typename _Up> + inline void + operator()(_Allocator& __alloc, _Tp* __dest, _Up& __orig) const + { + constexpr bool __mv + = noexcept(__move_construct_object_a(__alloc, __dest, __orig)); + + if (__mv) + __move_construct_object_a(__alloc, __dest, __orig); + else + __construct_object_a(__alloc, __dest, __orig); + } + }; +#endif + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/include/std/tuple b/libstdc++-v3/include/std/tuple index 56b97c25eed..60dc7738468 100644 --- a/libstdc++-v3/include/std/tuple +++ b/libstdc++-v3/include/std/tuple @@ -1714,6 +1714,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// @} + // Special overload for pairs with const key to help move semantic in + // associative containers. Note that noexcept qualification decides either + // we will use move or copy semantic. + template<typename _Allocator, + typename _Tp1, typename _Tp2, typename _Up1, typename _Up2> + inline void + __move_construct_object_a(_Allocator& __alloc, + pair<_Tp1, _Tp2>* __dest, + pair<const _Up1, _Up2>& __orig) + noexcept( std::is_nothrow_constructible<_Tp2, _Up2&&>::value ) + { + typedef allocator_traits<_Allocator> __traits; + __traits::construct(__alloc, __dest, std::piecewise_construct, + std::tuple<const _Up1&>(__orig.first), + std::forward_as_tuple(std::move(__orig.second))); + } + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/allocator/move_assign.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/allocator/move_assign.cc index b27269e607a..6e0bbf2d297 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_map/allocator/move_assign.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/allocator/move_assign.cc @@ -49,8 +49,10 @@ void test01() VERIFY( 1 == v1.get_allocator().get_personality() ); VERIFY( 2 == v2.get_allocator().get_personality() ); - // No move because key is const. - VERIFY( counter_type::move_assign_count == 0 ); + // Key copied, value moved. + VERIFY( counter_type::copy_count == 1 ); + VERIFY( counter_type::move_count == 1 ); + VERIFY( counter_type::destructor_count == 4 ); } void test02() @@ -79,7 +81,8 @@ void test02() VERIFY(0 == v1.get_allocator().get_personality()); VERIFY(1 == v2.get_allocator().get_personality()); - VERIFY( counter_type::move_assign_count == 0 ); + VERIFY( counter_type::copy_count == 0 ); + VERIFY( counter_type::move_count == 0 ); VERIFY( counter_type::destructor_count == 2 ); VERIFY( it == v2.begin() );
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 9a12ad399dc..dfb756cec07 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -266,8 +266,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>; - using __reuse_or_alloc_node_type = - __detail::_ReuseOrAllocNode<__node_alloc_type>; + template<typename _ConstructF> + using __alloc_node_gen_t = + __detail::_AllocNode<__node_alloc_type, _ConstructF>; + + template<typename _ConstructF> + using __reuse_or_alloc_node_gen_t = + __detail::_ReuseOrAllocNode<__node_alloc_type, _ConstructF>; // Metaprogramming for picking apart hash caching. template<typename _Cond> @@ -400,9 +405,9 @@ _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 _NodeGen, typename _Ht> void - _M_assign_elements(_Ht&&, const _NodeGenerator&); + _M_assign_elements(_Ht&&); template<typename _NodeGenerator> void @@ -500,7 +505,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable& operator=(initializer_list<value_type> __l) { - __reuse_or_alloc_node_type __roan(_M_begin(), *this); + __reuse_or_alloc_node_gen_t<_Construct_object_a> + __roan(*this, _M_begin()); _M_before_begin._M_nxt = nullptr; clear(); this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys()); @@ -1047,9 +1053,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_rehash_policy = __ht._M_rehash_policy; __try { - _M_assign(__ht, - [this](const __node_type* __n) - { return this->_M_allocate_node(__n->_M_v()); }); + __alloc_node_gen_t<_Construct_object_a> __ang(*this); + _M_assign(__ht, __ang); } __catch(...) { @@ -1064,9 +1069,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } // Reuse allocated buckets and nodes. - _M_assign_elements(__ht, - [](const __reuse_or_alloc_node_type& __roan, const __node_type* __n) - { return __roan(__n->_M_v()); }); + using __node_gen_t + = __reuse_or_alloc_node_gen_t<_Construct_object_a>; + _M_assign_elements<__node_gen_t>(__ht); return *this; } @@ -1074,11 +1079,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 _NodeGenT, 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; @@ -1099,11 +1104,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __hashtable_base::operator=(std::forward<_Ht>(__ht)); _M_element_count = __ht._M_element_count; _M_rehash_policy = __ht._M_rehash_policy; - __reuse_or_alloc_node_type __roan(_M_begin(), *this); + _NodeGenT __roan(*this, _M_begin()); _M_before_begin._M_nxt = nullptr; - _M_assign(__ht, - [&__node_gen, &__roan](__node_type* __n) - { return __node_gen(__roan, __n); }); + _M_assign(__ht, __roan); if (__former_buckets) _M_deallocate_buckets(__former_buckets, __former_bucket_count); } @@ -1145,7 +1148,7 @@ _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(__ht_n->_M_v()); this->_M_copy_code(__this_n, __ht_n); _M_before_begin._M_nxt = __this_n; #if _GLIBCXX_INLINE_VERSION @@ -1159,7 +1162,7 @@ _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(__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); @@ -1248,9 +1251,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION else { // Can't move memory, move elements then. - _M_assign_elements(std::move(__ht), - [](const __reuse_or_alloc_node_type& __roan, __node_type* __n) - { return __roan(std::move_if_noexcept(__n->_M_v())); }); + using __node_gen_t + = __reuse_or_alloc_node_gen_t<_Move_construct_if_noexcept_object_a>; + _M_assign_elements<__node_gen_t>(std::move(__ht)); __ht.clear(); } } @@ -1272,9 +1275,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<_Construct_object_a> __ang(*this); + _M_assign(__ht, __ang); } template<typename _Key, typename _Value, @@ -1332,9 +1334,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<_Construct_object_a> __ang(*this); + _M_assign(__ht, __ang); } template<typename _Key, typename _Value, @@ -1379,12 +1380,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<_Move_construct_if_noexcept_object_a> __ang(*this); + _M_assign(__ht, __ang); __ht.clear(); } } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index aa4808eab31..fa5c9cc31ed 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -34,6 +34,7 @@ #include <tuple> // for std::tuple, std::forward_as_tuple #include <limits> // for std::numeric_limits #include <bits/stl_algobase.h> // for std::min. +#include <bits/stl_construct.h> // for __construct_object_a. namespace std _GLIBCXX_VISIBILITY(default) { @@ -110,25 +111,53 @@ namespace __detail template<typename _NodeAlloc> struct _Hashtable_alloc; - // Functor recycling a pool of nodes and using allocation once the pool is - // empty. - template<typename _NodeAlloc> - struct _ReuseOrAllocNode + // Functor allocating nodes on demand. + template<typename _NodeAlloc, typename _ConstructF> + struct _AllocNode : public _ConstructF + { + protected: + using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>; + using __node_type = typename __hashtable_alloc::__node_type; + + const _ConstructF& + _M_construct_f() const { return *this; } + + public: + _AllocNode(__hashtable_alloc& __h) + : _M_h(__h) { } + + template<typename _Arg> + __node_type* + operator()(_Arg&& __arg) const + { + return _M_h._M_allocate_node_f(_M_construct_f(), + std::forward<_Arg>(__arg)); + } + + protected: + __hashtable_alloc& _M_h; + }; + + // Functor similar to the previous one but recycling a pool of nodes and using + // allocation once the pool is empty. + template<typename _NodeAlloc, typename _ConstructF> + struct _ReuseOrAllocNode : private _AllocNode<_NodeAlloc, _ConstructF> { private: - using __node_alloc_type = _NodeAlloc; - using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>; + typedef _AllocNode<_NodeAlloc, _ConstructF> _Base; + using __node_type = typename _Base::__node_type; + using __hashtable_alloc = typename _Base::__hashtable_alloc; using __node_alloc_traits = typename __hashtable_alloc::__node_alloc_traits; - using __node_type = typename __hashtable_alloc::__node_type; public: - _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h) - : _M_nodes(__nodes), _M_h(__h) { } + _ReuseOrAllocNode(__hashtable_alloc& __h, __node_type* __nodes) + : _Base(__h), _M_nodes(__nodes) { } + _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete; ~_ReuseOrAllocNode() - { _M_h._M_deallocate_nodes(_M_nodes); } + { this->_M_h._M_deallocate_nodes(_M_nodes); } template<typename _Arg> __node_type* @@ -139,48 +168,27 @@ namespace __detail __node_type* __node = _M_nodes; _M_nodes = _M_nodes->_M_next(); __node->_M_nxt = nullptr; - auto& __a = _M_h._M_node_allocator(); - __node_alloc_traits::destroy(__a, __node->_M_valptr()); + auto& __alloc = this->_M_h._M_node_allocator(); + __node_alloc_traits::destroy(__alloc, __node->_M_valptr()); __try { - __node_alloc_traits::construct(__a, __node->_M_valptr(), + this->_M_construct_f()(__alloc, __node->_M_valptr(), std::forward<_Arg>(__arg)); } __catch(...) { - _M_h._M_deallocate_node_ptr(__node); + this->_M_h._M_deallocate_node_ptr(__node); __throw_exception_again; } + return __node; } - return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); + + return _Base::operator()(std::forward<_Arg>(__arg)); } private: mutable __node_type* _M_nodes; - __hashtable_alloc& _M_h; - }; - - // Functor similar to the previous one but without any pool of nodes to - // recycle. - template<typename _NodeAlloc> - struct _AllocNode - { - private: - using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>; - using __node_type = typename __hashtable_alloc::__node_type; - - public: - _AllocNode(__hashtable_alloc& __h) - : _M_h(__h) { } - - template<typename _Arg> - __node_type* - operator()(_Arg&& __arg) const - { return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); } - - private: - __hashtable_alloc& _M_h; }; // Auxiliary types used for all instantiations of _Hashtable nodes @@ -828,7 +836,8 @@ namespace __detail using __ireturn_type = typename __hashtable_base::__ireturn_type; using __node_type = _Hash_node<_Value, _Traits::__hash_cached::value>; using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>; - using __node_gen_type = _AllocNode<__node_alloc_type>; + using __node_gen_type = _AllocNode<__node_alloc_type, + _Construct_object_a>; __hashtable& _M_conjure_hashtable() @@ -2112,6 +2121,11 @@ namespace __detail __node_type* _M_allocate_node(_Args&&... __args); + template<typename _ConstF, typename... _Args> + __node_type* + _M_allocate_node_f(const _ConstF& __construct_f, + _Args&&... __args); + void _M_deallocate_node(__node_type* __n); @@ -2136,19 +2150,29 @@ namespace __detail typename _Hashtable_alloc<_NodeAlloc>::__node_type* _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args) { - auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1); + return _M_allocate_node_f(_Construct_object_a{}, + std::forward<_Args>(__args)...); + } + + template<typename _NodeAlloc> + template<typename _ConstructF, typename... _Args> + typename _Hashtable_alloc<_NodeAlloc>::__node_type* + _Hashtable_alloc<_NodeAlloc>:: + _M_allocate_node_f(const _ConstructF& __construct_f, _Args&&... __args) + { + auto& __alloc = _M_node_allocator(); + auto __nptr = __node_alloc_traits::allocate(__alloc, 1); __node_type* __n = std::__to_address(__nptr); __try { ::new ((void*)__n) __node_type; - __node_alloc_traits::construct(_M_node_allocator(), - __n->_M_valptr(), + __construct_f(__alloc, __n->_M_valptr(), std::forward<_Args>(__args)...); return __n; } __catch(...) { - __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1); + __node_alloc_traits::deallocate(__alloc, __nptr, 1); __throw_exception_again; } } diff --git a/libstdc++-v3/include/bits/stl_construct.h b/libstdc++-v3/include/bits/stl_construct.h index e696ec8b2eb..92a71de4d55 100644 --- a/libstdc++-v3/include/bits/stl_construct.h +++ b/libstdc++-v3/include/bits/stl_construct.h @@ -229,6 +229,61 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } #endif +#if __cplusplus >= 201103L + template<typename _Allocator, typename _Tp, typename... _Args> + inline void + __construct_object_a(_Allocator& __alloc, _Tp* __dest, _Args&&... __args) + { + typedef allocator_traits<_Allocator> __traits; + __traits::construct(__alloc, __dest, std::forward<_Args>(__args)...); + } + + struct _Construct_object_a + { + template<typename _Allocator, typename _Tp, typename... _Args> + inline void + operator()(_Allocator& __alloc, _Tp* __dest, _Args&&... __args) const + { + __construct_object_a(__alloc, __dest, + std::forward<_Args>(__args)...); + } + }; + + template<typename _Allocator, typename _Tp, typename _Up> + inline void + __move_construct_object_a(_Allocator& __alloc, _Tp* __dest, _Up& __orig) + noexcept( noexcept(allocator_traits<_Allocator>::construct(__alloc, + __dest, std::move(__orig))) ) + { + typedef allocator_traits<_Allocator> __traits; + __traits::construct(__alloc, __dest, std::move(__orig)); + } + + struct _Move_construct_object_a + { + template<typename _Allocator, typename _Tp, typename _Up> + inline void + operator()(_Allocator& __alloc, _Tp* __dest, _Up& __orig) const + { __move_construct_object_a(__alloc, __dest, __orig); } + }; + + struct _Move_construct_if_noexcept_object_a + { + template<typename _Allocator, typename _Tp, typename _Up> + inline void + operator()(_Allocator& __alloc, _Tp* __dest, _Up& __orig) const + { + constexpr bool __mv + = noexcept(__move_construct_object_a(__alloc, __dest, __orig)); + + if (__mv) + __move_construct_object_a(__alloc, __dest, __orig); + else + __construct_object_a(__alloc, __dest, __orig); + } + }; +#endif + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/include/ext/throw_allocator.h b/libstdc++-v3/include/ext/throw_allocator.h index 3a5670e3454..8a38f5a08b0 100644 --- a/libstdc++-v3/include/ext/throw_allocator.h +++ b/libstdc++-v3/include/ext/throw_allocator.h @@ -845,6 +845,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Up, typename... _Args> void construct(_Up* __p, _Args&&... __args) + noexcept( + noexcept(_M_allocator.construct(__p, + std::forward<_Args>(__args)...)) ) { _M_allocator.construct(__p, std::forward<_Args>(__args)...); insert_construct(__p); diff --git a/libstdc++-v3/include/std/tuple b/libstdc++-v3/include/std/tuple index 56b97c25eed..b95449bf199 100644 --- a/libstdc++-v3/include/std/tuple +++ b/libstdc++-v3/include/std/tuple @@ -1714,6 +1714,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// @} + // Special overload for pairs with const key to help move semantic in + // associative containers. + template<typename _Allocator, + typename _Tp1, typename _Tp2, typename _Up1, typename _Up2> + inline void + __move_construct_object_a(_Allocator& __alloc, + pair<_Tp1, _Tp2>* __dest, + pair<const _Up1, _Up2>& __orig) + noexcept( noexcept(allocator_traits<_Allocator>::construct(__alloc, + __dest, + std::piecewise_construct, + std::tuple<const _Up1&>(__orig.first), + std::forward_as_tuple(std::move(__orig.second)))) ) + { + typedef allocator_traits<_Allocator> __traits; + __traits::construct(__alloc, __dest, std::piecewise_construct, + std::tuple<const _Up1&>(__orig.first), + std::forward_as_tuple(std::move(__orig.second))); + } + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/allocator/move_assign.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/allocator/move_assign.cc index b27269e607a..31f5accdffe 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_map/allocator/move_assign.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/allocator/move_assign.cc @@ -49,8 +49,11 @@ void test01() VERIFY( 1 == v1.get_allocator().get_personality() ); VERIFY( 2 == v2.get_allocator().get_personality() ); - // No move because key is const. - VERIFY( counter_type::move_assign_count == 0 ); + // No noexcept qualification on std::pair piecewise constructor so no + // move for the moment. + VERIFY( counter_type::copy_count == 2 ); + VERIFY( counter_type::move_count == 0 ); + VERIFY( counter_type::destructor_count == 4 ); } void test02() @@ -79,7 +82,8 @@ void test02() VERIFY(0 == v1.get_allocator().get_personality()); VERIFY(1 == v2.get_allocator().get_personality()); - VERIFY( counter_type::move_assign_count == 0 ); + VERIFY( counter_type::copy_count == 0 ); + VERIFY( counter_type::move_count == 0 ); VERIFY( counter_type::destructor_count == 2 ); VERIFY( it == v2.begin() ); diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/move_assign.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/move_assign.cc index 3a553897581..6fd50b838eb 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/move_assign.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/move_assign.cc @@ -141,10 +141,29 @@ void test03() == tracker_allocator_counter::get_deallocation_count() ); } +void test04() +{ + typedef __gnu_test::counter_type_hasher hash; + typedef std::unordered_set<counter_type, hash, + std::equal_to<counter_type>> test_type; + + counter_type::reset(); + + test_type v1; + v1 = { { 1 }, { 2 }, { 3 } }; + + VERIFY( v1.size() == 3 ); + + VERIFY( counter_type::copy_count == 3 ); + VERIFY( counter_type::move_count == 0 ); + VERIFY( counter_type::destructor_count == 3 ); +} + int main() { test01(); test02(); test03(); + test04(); return 0; } diff --git a/libstdc++-v3/testsuite/util/testsuite_allocator.h b/libstdc++-v3/testsuite/util/testsuite_allocator.h index c18223475c9..42ed460cf6d 100644 --- a/libstdc++-v3/testsuite/util/testsuite_allocator.h +++ b/libstdc++-v3/testsuite/util/testsuite_allocator.h @@ -161,6 +161,9 @@ namespace __gnu_test template<typename U, typename... Args> void construct(U* p, Args&&... args) + noexcept( + noexcept(AllocTraits::construct(*this, + p, std::forward<Args>(args)...)) ) { AllocTraits::construct(*this, p, std::forward<Args>(args)...); counter_type::construct();