PR libstdc++/92124 on hashtable

Message ID 23378b8f-b9fa-a263-41fc-457b931a3987@gmail.com
State New
Headers show
Series
  • PR libstdc++/92124 on hashtable
Related show

Commit Message

François Dumont Nov. 7, 2019, 7:28 p.m.
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

Comments

Jonathan Wakely Jan. 6, 2020, 3:17 p.m. | #1
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?
Jonathan Wakely Jan. 6, 2020, 3:18 p.m. | #2
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);
François Dumont Jan. 8, 2020, 5:43 a.m. | #3
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
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 06b3cca6437..48eaa7600f3 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,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__node_type* _M_node;
       };
 
+      template<typename _Ht>
+	static constexpr
+	typename conditional<std::is_lvalue_reference<_Ht>::value,
+			     const value_type&, value_type&&>::type
+	__fwd_value_for(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>;
@@ -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.
+      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 +1060,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 +1078,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 +1086,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 +1113,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 +1137,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 +1155,8 @@ _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_for<_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 +1165,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(__fwd_value_for<_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 +1246,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 +1268,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 +1320,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 +1359,12 @@ _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);
+
+	  using _Fwd_Ht = typename
+	    conditional<__move_if_noexcept_cond<value_type>::value,
+			const _Hashtable&, _Hashtable&&>::type;
+	  _M_assign(forward<_Fwd_Ht>(__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..6dd1ef8701e
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/92124.cc
@@ -0,0 +1,79 @@
+// 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 <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();
+}
Jonathan Wakely Jan. 8, 2020, 1:28 p.m. | #4
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!

Patch

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