* [PATCH] PR libstdc++/92124 on hashtable
@ 2019-11-07 19:28 François Dumont
2020-01-06 15:17 ` Jonathan Wakely
2020-01-06 15:18 ` Jonathan Wakely
0 siblings, 2 replies; 5+ messages in thread
From: François Dumont @ 2019-11-07 19:28 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1322 bytes --]
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
[-- Attachment #2: hashtable_92124.patch --]
[-- Type: text/x-patch, Size: 8927 bytes --]
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();
+}
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] PR libstdc++/92124 on hashtable
2019-11-07 19:28 [PATCH] PR libstdc++/92124 on hashtable François Dumont
@ 2020-01-06 15:17 ` Jonathan Wakely
2020-01-08 5:43 ` François Dumont
2020-01-06 15:18 ` Jonathan Wakely
1 sibling, 1 reply; 5+ messages in thread
From: Jonathan Wakely @ 2020-01-06 15:17 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
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?
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] PR libstdc++/92124 on hashtable
2019-11-07 19:28 [PATCH] PR libstdc++/92124 on hashtable François Dumont
2020-01-06 15:17 ` Jonathan Wakely
@ 2020-01-06 15:18 ` Jonathan Wakely
1 sibling, 0 replies; 5+ messages in thread
From: Jonathan Wakely @ 2020-01-06 15:18 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
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);
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] PR libstdc++/92124 on hashtable
2020-01-06 15:17 ` Jonathan Wakely
@ 2020-01-08 5:43 ` François Dumont
2020-01-08 13:28 ` Jonathan Wakely
0 siblings, 1 reply; 5+ messages in thread
From: François Dumont @ 2020-01-08 5:43 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 5578 bytes --]
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
[-- Attachment #2: hashtable_92124.patch --]
[-- Type: text/x-patch, Size: 8986 bytes --]
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();
+}
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] PR libstdc++/92124 on hashtable
2020-01-08 5:43 ` François Dumont
@ 2020-01-08 13:28 ` Jonathan Wakely
0 siblings, 0 replies; 5+ messages in thread
From: Jonathan Wakely @ 2020-01-08 13:28 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
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!
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2020-01-08 13:28 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-11-07 19:28 [PATCH] PR libstdc++/92124 on hashtable François Dumont
2020-01-06 15:17 ` Jonathan Wakely
2020-01-08 5:43 ` François Dumont
2020-01-08 13:28 ` Jonathan Wakely
2020-01-06 15:18 ` Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).