This was indeed the right approach.
The only minor drawback is that __is_noexcept_invocable<> combines
noexcept qualification of the conversion and of the hash functor. So if
the hash functor is not noexcept we could end up creating temporaries
for nothing.
So I've eventually used this condition:
__and_<__is_nothrow_invocable<_Hash&, const key_type&>,
__not_<__is_nothrow_invocable<_Hash&, _Kt>>>::value,
so that we do not create a temporary key_type if invoking _Hash
with it can still throw.
libstdc++: Limit allocation on iterator insertion in Hashtable [PR
96088]
When inserting into unordered_multiset or unordered_multimap first
instantiate
the node to store and compute the hash code from it to avoid a
potential
intermediate key_type instantiation.
When inserting into unordered_set or unordered_map check if
invoking the hash
functor with container key_type is noexcept and invoking the same
hash functor
with key part of the iterator value_type can throw. In this case
create a
temporary key_type instance at Hashtable level and use it to
compute the hash
code. This temporary instance is moved to the final storage
location if needed.
libstdc++-v3/ChangeLog:
PR libstdc++/96088
* include/bits/hashtable_policy.h (_Select2nd): New.
(_NodeBuilder<>): New.
(_ReuseOrAllocNode<>::operator()): Use variadic template args.
(_AllocNode<>::operator()): Likewise.
* include/bits/hashtable.h
(_Hashtable<>::__node_builder_t): New.
(_Hashtable<>::_M_insert_unique<>(_Kt&&, _Arg&&, const _NodeGenerator&)):
New.
(_Hashtable<>::_S_forward_key): New.
(_Hashtable<>::_M_insert): Use latter.
(_Hashtable<>::_M_insert(const_iterator, _Arg&&, const
_NodeGenerator&, false_type)):
Instantiate node first, compute hash code second.
* testsuite/23_containers/unordered_map/96088.cc: New test.
* testsuite/23_containers/unordered_multimap/96088.cc: New
test.
* testsuite/23_containers/unordered_multiset/96088.cc: New
test.
* testsuite/23_containers/unordered_set/96088.cc: New test.
* testsuite/util/replacement_memory_operators.h
(counter::_M_increment): New.
(counter::_M_decrement): New.
(counter::reset()): New.
Tested under Linux x64.
Ok to commit ?
François
On 21/05/21 8:55 am, Jonathan Wakely wrote:
On Fri, 21 May 2021, 07:48 Jonathan Wakely, <jwakely....@gmail.com
<mailto:jwakely....@gmail.com>> wrote:
On Fri, 21 May 2021, 07:31 François Dumont via Libstdc++,
<libstd...@gcc.gnu.org <mailto:libstdc%2b...@gcc.gnu.org>> wrote:
On 20/05/21 6:44 pm, Jonathan Wakely wrote:
> On 06/05/21 22:03 +0200, François Dumont via Libstdc++ wrote:
>> Hi
>>
>> Considering your feedback on backtrace in debug mode is
going to
>> take me some time so here is another one.
>>
>> Compared to latest submission I've added a _Hash_arg_t
partial
>> specialization for std::hash<>. It is not strictly
necessary for the
>> moment but when we will eventually remove its nested
argument_type it
>> will be. I also wonder if it is not easier to handle for the
>> compiler, not sure about that thought.
>
> The std::hash specializations in libstdc++ define
argument_type, but
> I'm already working on one that doesn't (forstd::stacktrace).
>
> And std::hash<acme::ProgramDefinedType> can be specialized
by users,
> and is not required to provide argument_type.
>
> So it's already not valid to assume that
std::hash<T>::argument_type
> exists.
Yes, I know that the plan is to get rid of argument_type. But
as long as
it is there we can still use it even if I didn't realize that
you were
already in the process of removing it so soon.
I'm adding a new specialization for a C++23 type, and not adding
the nested types.
>
>> @@ -850,9 +852,56 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>> iterator
>> _M_emplace(const_iterator, false_type __uks, _Args&&...
__args);
>>
>> + template<typename _Kt, typename _Arg, typename
_NodeGenerator>
>> + std::pair<iterator, bool>
>> + _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&);
>> +
>> + // Detect nested argument_type.
>> + template<typename _Kt, typename _Ht, typename =
__void_t<>>
>> + struct _Hash_arg_t
>> + { typedef _Kt argument_type; };
>> +
>> + // std::hash
>> + template<typename _Kt, typename _Arg>
>> + struct _Hash_arg_t<_Kt, std::hash<_Arg>>
>> + { typedef _Arg argument_type; };
>> +
>> + // Nested argument_type.
>> + template<typename _Kt, typename _Ht>
>> + struct _Hash_arg_t<_Kt, _Ht,
>> + __void_t<typename _Ht::argument_type>>
>> + { typedef typename _Ht::argument_type argument_type; };
>> +
>> + // Function pointer.
>> + template<typename _Kt, typename _Arg>
>> + struct _Hash_arg_t<_Kt, std::size_t(*)(const _Arg&)>
>> + { typedef _Arg argument_type; };
>> +
>> + template<typename _Kt,
>> + typename _ArgType
>> + = typename _Hash_arg_t<_Kt, _Hash>::argument_type>
>> + static typename conditional<
>> + __is_nothrow_convertible<_Kt, _ArgType>::value, _Kt&&,
>> key_type>::type
>
> Please use __conditional_t<...> here instead of
> typename conditional<...>::type.
>
> The purpose of the _Hash_arg_t type is to determine whether
invoking
> the hash function with _Kt&& can throw, right?
No, the purpose of _Hash_arg_t is to find out what is the
argument type
of the _Hash functor. With this info I can check if invoking that
functor is going to instantiate a temporary using a throwing
operation.
Right, that's what I mean.
If so, I create a temporary at _Hashtable code level and move
it to its
final storage place when needed.
The tricky part is that _Hash can accept different argument
types, for
the moment I just do not create a temporary in this case.
>
> And if it can throw, you force a conversion early, and if it
can't,
> you don't do the conversion.
>
> Can't you use __is_nothrow_invocable<_Hash&, _Kt> for that,
instead of
> this fragile approach?
>
I think I already try but I'll check.
I fear that __is_nothrow_invocable<_Hash&, _Kt> tells if the
chosen
operator()(const _Arg&) is noexcept qualified.
No.
Not if the conversion
from _Kt to _Arg is noexcept.
It does exactly what you need.
And even if it didn't, you could do it yourself with the noexcept
operator:
noexcept(std::declval<_Hash&>()(std::declval<_Kt>()));
This is what the trait uses, and it tells you if invoking Hash with a
Kt will throw. If a conversion to the argument type is needed, the
compiler will consider whether that can throw.
You don't need to know the argument type, you only need to know if the
expression can throw, and C++11 provides the tools to check that
accurately.
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 6711d08e6b8..4bdbe7dd9cc 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -274,6 +274,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__detail::_ReuseOrAllocNode<__node_alloc_type>;
using __alloc_node_gen_t =
__detail::_AllocNode<__node_alloc_type>;
+ using __node_builder_t =
+ __detail::_NodeBuilder<_ExtractKey>;
// Simple RAII type for managing a node containing an element
struct _Scoped_node
@@ -850,9 +852,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
_M_emplace(const_iterator, false_type __uks, _Args&&... __args);
+ template<typename _Kt, typename _Arg, typename _NodeGenerator>
+ std::pair<iterator, bool>
+ _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&);
+
+ template<typename _Kt>
+ static typename conditional<
+ __and_<__is_nothrow_invocable<_Hash&, const key_type&>,
+ __not_<__is_nothrow_invocable<_Hash&, _Kt>>>::value,
+ key_type, _Kt&&>::type
+ _S_forward_key(_Kt&& __k)
+ { return std::forward<_Kt>(__k); }
+
+ static const key_type&
+ _S_forward_key(const key_type& __k)
+ { return __k; }
+
+ static key_type&&
+ _S_forward_key(key_type&& __k)
+ { return std::move(__k); }
+
template<typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert(_Arg&&, const _NodeGenerator&, true_type __uks);
+ _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
+ true_type /* __uks */)
+ {
+ return _M_insert_unique(
+ _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
+ std::forward<_Arg>(__arg), __node_gen);
+ }
template<typename _Arg, typename _NodeGenerator>
iterator
@@ -2067,22 +2095,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
- template<typename _Arg, typename _NodeGenerator>
+ template<typename _Kt, typename _Arg, typename _NodeGenerator>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen,
- true_type /* __uks */)
+ _M_insert_unique(_Kt&& __k, _Arg&& __v,
+ const _NodeGenerator& __node_gen)
-> pair<iterator, bool>
{
- const key_type& __k = _ExtractKey{}(__v);
- __hash_code __code = this->_M_hash_code(__k);
+ __hash_code __code = this->_M_hash_code_tr(__k);
size_type __bkt = _M_bucket_index(__code);
- if (__node_ptr __node = _M_find_node(__bkt, __k, __code))
+ if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code))
return { iterator(__node), false };
- _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
+ _Scoped_node __node {
+ __node_builder_t::_S_build(std::forward<_Kt>(__k),
+ std::forward<_Arg>(__v),
+ __node_gen),
+ this
+ };
auto __pos
= _M_insert_unique_node(__bkt, __code, __node._M_node);
__node._M_node = nullptr;
@@ -2103,12 +2135,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
false_type /* __uks */)
-> iterator
{
- // First compute the hash code so that we don't do anything if it
- // throws.
- __hash_code __code = this->_M_hash_code(_ExtractKey{}(__v));
-
- // Second allocate new node so that we don't rehash if it throws.
+ // First allocate new node so that we don't do anything if it throws.
_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
+
+ // Second compute the hash code so that we don't rehash if it throws.
+ __hash_code __code
+ = this->_M_hash_code(_ExtractKey{}(__node._M_node->_M_v()));
+
auto __pos
= _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
__node._M_node = nullptr;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index ad8a4ec5f07..1090a398e1e 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -94,6 +94,45 @@ namespace __detail
{ return std::get<0>(std::forward<_Tp>(__x)); }
};
+ struct _Select2nd
+ {
+ template<typename _Tp>
+ auto
+ operator()(_Tp&& __x) const noexcept
+ -> decltype(std::get<1>(std::forward<_Tp>(__x)))
+ { return std::get<1>(std::forward<_Tp>(__x)); }
+ };
+
+ template<typename _ExKey>
+ struct _NodeBuilder;
+
+ template<>
+ struct _NodeBuilder<_Select1st>
+ {
+ template<typename _Kt, typename _Arg, typename _NodeGenerator>
+ static auto
+ _S_build(_Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen)
+ -> decltype(__node_gen(std::piecewise_construct,
+ std::forward_as_tuple(std::forward<_Kt>(__k)),
+ std::forward_as_tuple(_Select2nd{}(
+ std::forward<_Arg>(__arg)))))
+ {
+ return __node_gen(std::piecewise_construct,
+ std::forward_as_tuple(std::forward<_Kt>(__k)),
+ std::forward_as_tuple(_Select2nd{}(std::forward<_Arg>(__arg))));
+ }
+ };
+
+ template<>
+ struct _NodeBuilder<_Identity>
+ {
+ template<typename _Kt, typename _Arg, typename _NodeGenerator>
+ static auto
+ _S_build(_Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen)
+ -> decltype(__node_gen(std::forward<_Kt>(__k)))
+ { return __node_gen(std::forward<_Kt>(__k)); }
+ };
+
template<typename _NodeAlloc>
struct _Hashtable_alloc;
@@ -117,9 +156,9 @@ namespace __detail
~_ReuseOrAllocNode()
{ _M_h._M_deallocate_nodes(_M_nodes); }
- template<typename _Arg>
+ template<typename... _Args>
__node_type*
- operator()(_Arg&& __arg) const
+ operator()(_Args&&... __args) const
{
if (_M_nodes)
{
@@ -131,7 +170,7 @@ namespace __detail
__try
{
__node_alloc_traits::construct(__a, __node->_M_valptr(),
- std::forward<_Arg>(__arg));
+ std::forward<_Args>(__args)...);
}
__catch(...)
{
@@ -140,7 +179,7 @@ namespace __detail
}
return __node;
}
- return _M_h._M_allocate_node(std::forward<_Arg>(__arg));
+ return _M_h._M_allocate_node(std::forward<_Args>(__args)...);
}
private:
@@ -161,10 +200,10 @@ namespace __detail
_AllocNode(__hashtable_alloc& __h)
: _M_h(__h) { }
- template<typename _Arg>
+ template<typename... _Args>
__node_type*
- operator()(_Arg&& __arg) const
- { return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
+ operator()(_Args&&... __args) const
+ { return _M_h._M_allocate_node(std::forward<_Args>(__args)...); }
private:
__hashtable_alloc& _M_h;
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc
new file mode 100644
index 00000000000..062c8316a9e
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc
@@ -0,0 +1,269 @@
+// { dg-do run { target c++11 } }
+
+// Copyright (C) 2021 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/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<std::pair<const char*, int>> lst = {
+ {"long_str_for_dynamic_allocating", 1}
+};
+
+void
+test01()
+{
+ __gnu_test::counter::reset();
+ std::unordered_map<std::string, int> um;
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+void
+test02()
+{
+ __gnu_test::counter::reset();
+ std::unordered_map<std::string, int,
+ std::hash<std::string_view>,
+ std::equal_to<std::string_view>> um;
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+std::size_t
+hash_string_f(const std::string& str) noexcept
+{
+ std::hash<std::string> h;
+ return h(str);
+}
+
+void
+test11()
+{
+ typedef std::size_t (*hash_string_t)(const std::string&) noexcept;
+ __gnu_test::counter::reset();
+ hash_string_t hasher = &hash_string_f;
+ std::unordered_map<std::string, int,
+ hash_string_t,
+ std::equal_to<std::string>> um(0, hasher);
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+std::size_t
+hash_string_view_f(const std::string_view& str) noexcept
+{
+ std::hash<std::string_view> h;
+ return h(str);
+}
+
+void
+test12()
+{
+ typedef std::size_t (*hash_stringview_t) (const std::string_view&) noexcept;
+ __gnu_test::counter::reset();
+ hash_stringview_t hasher = &hash_string_view_f;
+ std::unordered_map<std::string, int, hash_stringview_t,
+ std::equal_to<std::string_view>> um(0, hasher);
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct hash_string_functor
+{
+ std::size_t
+ operator()(const std::string& str) const noexcept
+ {
+ std::hash<std::string> h;
+ return h(str);
+ }
+};
+
+void
+test21()
+{
+ __gnu_test::counter::reset();
+ std::unordered_map<std::string, int,
+ hash_string_functor,
+ std::equal_to<std::string>> um;
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+struct hash_string_view_noexcept_functor
+{
+ std::size_t
+ operator()(const std::string_view& str) const noexcept
+ {
+ std::hash<std::string_view> h;
+ return h(str);
+ }
+};
+
+void
+test22()
+{
+ __gnu_test::counter::reset();
+ std::unordered_map<std::string, int,
+ hash_string_view_noexcept_functor,
+ std::equal_to<std::string_view>> um;
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct hash_string_view_functor
+{
+ std::size_t
+ operator()(const std::string_view& str) const
+ {
+ std::hash<std::string_view> h;
+ return h(str);
+ }
+};
+
+void
+test23()
+{
+ __gnu_test::counter::reset();
+ std::unordered_map<std::string, int,
+ hash_string_view_functor,
+ std::equal_to<std::string_view>> um;
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ um.insert(lst.begin(), lst.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+void
+test03()
+{
+ std::vector<std::pair<std::string, int>> v;
+ v.insert(v.end(), lst.begin(), lst.end());
+
+ auto __offset = __gnu_test::counter::count();
+ {
+ __gnu_test::counter::reset();
+ std::unordered_map<std::string, int,
+ std::hash<std::string_view>,
+ std::equal_to<std::string_view>> um;
+ um.insert(v.begin(), v.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() - __offset == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ um.insert(v.begin(), v.end());
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() - __offset == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+ }
+
+ {
+ __gnu_test::counter::reset();
+ std::unordered_map<std::string, int,
+ std::hash<std::string_view>,
+ std::equal_to<std::string_view>> um;
+ um.insert(std::make_move_iterator(v.begin()),
+ std::make_move_iterator(v.end()));
+ VERIFY( um.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() - __offset == 2 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+ }
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test11();
+ test12();
+ test21();
+ test22();
+ test03();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc
new file mode 100644
index 00000000000..de7f009dadc
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc
@@ -0,0 +1,65 @@
+// { dg-do run { target c++17 } }
+
+// Copyright (C) 2021 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/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <unordered_map>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<std::pair<const char*, int>> lst = {
+ {"long_str_for_dynamic_allocating", 1}
+};
+
+void
+test01()
+{
+ __gnu_test::counter::reset();
+ std::unordered_multimap<std::string, int,
+ std::hash<std::string_view>,
+ std::equal_to<std::string_view>> foo;
+ foo.insert(lst.begin(), lst.end());
+ VERIFY( foo.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+void
+test02()
+{
+ __gnu_test::counter::reset();
+ std::unordered_multimap<std::string, int> foo;
+ foo.insert(lst.begin(), lst.end());
+ VERIFY( foo.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc
new file mode 100644
index 00000000000..b9bbf63b863
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc
@@ -0,0 +1,65 @@
+// { dg-do run { target c++17 } }
+
+// Copyright (C) 2021 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/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<const char*> lst = {
+ "long_str_for_dynamic_allocating"
+};
+
+void
+test01()
+{
+ __gnu_test::counter::reset();
+ std::unordered_multiset<std::string,
+ std::hash<std::string_view>,
+ std::equal_to<std::string_view>> foo;
+ foo.insert(lst.begin(), lst.end());
+ VERIFY( foo.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+void
+test02()
+{
+ __gnu_test::counter::reset();
+ std::unordered_multiset<std::string> foo;
+ foo.insert(lst.begin(), lst.end());
+ VERIFY( foo.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
new file mode 100644
index 00000000000..53bb754dab6
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
@@ -0,0 +1,271 @@
+// { dg-do run { target c++11 } }
+
+// Copyright (C) 2021 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/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <unordered_set>
+#include <vector>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<const char*> lst = {
+ "long_str_for_dynamic_allocating"
+};
+
+void
+test01()
+{
+ __gnu_test::counter::reset();
+ std::unordered_set<std::string> us;
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+void
+test02()
+{
+ __gnu_test::counter::reset();
+ std::unordered_set<std::string,
+ std::hash<std::string_view>,
+ std::equal_to<std::string_view>> us;
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+std::size_t
+hash_string_f(const std::string& str) noexcept
+{
+ std::hash<std::string> h;
+ return h(str);
+}
+
+void
+test11()
+{
+ typedef std::size_t (*hash_string_t)(const std::string&) noexcept;
+ __gnu_test::counter::reset();
+ hash_string_t hasher = &hash_string_f;
+ std::unordered_set<std::string,
+ hash_string_t,
+ std::equal_to<std::string>> us(0, hasher);
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+std::size_t
+hash_string_view_f(const std::string_view& str) noexcept
+{
+ std::hash<std::string_view> h;
+ return h(str);
+}
+
+void
+test12()
+{
+ typedef std::size_t (*hash_stringview_t)(const std::string_view&) noexcept;
+ __gnu_test::counter::reset();
+ hash_stringview_t hasher = &hash_string_view_f;
+ std::unordered_set<std::string,
+ hash_stringview_t,
+ std::equal_to<std::string_view>> us(0, hasher);
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct hash_string_functor
+{
+ std::size_t
+ operator()(const std::string& str) const noexcept
+ {
+ std::hash<std::string> h;
+ return h(str);
+ }
+};
+
+void
+test21()
+{
+ __gnu_test::counter::reset();
+ std::unordered_set<std::string,
+ hash_string_functor,
+ std::equal_to<std::string>> us;
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+struct hash_string_view_noexcept_functor
+{
+ std::size_t
+ operator()(const std::string_view& str) const noexcept
+ {
+ std::hash<std::string_view> h;
+ return h(str);
+ }
+};
+
+void
+test22()
+{
+ __gnu_test::counter::reset();
+ std::unordered_set<std::string,
+ hash_string_view_noexcept_functor,
+ std::equal_to<std::string_view>> us;
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct hash_string_view_functor
+{
+ std::size_t
+ operator()(const std::string_view& str) const
+ {
+ std::hash<std::string_view> h;
+ return h(str);
+ }
+};
+
+void
+test23()
+{
+ __gnu_test::counter::reset();
+ std::unordered_set<std::string,
+ hash_string_view_functor,
+ std::equal_to<std::string_view>> us;
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ us.insert(lst.begin(), lst.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+void
+test03()
+{
+ std::vector<std::string> v;
+ v.insert(v.end(), lst.begin(), lst.end());
+
+ auto __offset = __gnu_test::counter::count();
+ {
+ __gnu_test::counter::reset();
+ std::unordered_set<std::string,
+ std::hash<std::string_view>,
+ std::equal_to<std::string_view>> us;
+ us.insert(v.begin(), v.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() - __offset == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+ us.insert(v.begin(), v.end());
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() - __offset == 3 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+ }
+
+ {
+ __gnu_test::counter::reset();
+ std::unordered_set<std::string,
+ std::hash<std::string_view>,
+ std::equal_to<std::string_view>> us;
+ us.insert(std::make_move_iterator(v.begin()),
+ std::make_move_iterator(v.end()));
+ VERIFY( us.size() == 1 );
+
+ VERIFY( __gnu_test::counter::count() - __offset == 2 );
+ VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+ }
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test11();
+ test12();
+ test21();
+ test22();
+ test23();
+ test03();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/util/replacement_memory_operators.h b/libstdc++-v3/testsuite/util/replacement_memory_operators.h
index 7e421dbc87c..e460c419ff2 100644
--- a/libstdc++-v3/testsuite/util/replacement_memory_operators.h
+++ b/libstdc++-v3/testsuite/util/replacement_memory_operators.h
@@ -29,6 +29,7 @@ namespace __gnu_test
struct counter
{
std::size_t _M_count;
+ std::size_t _M_increments, _M_decrements;
bool _M_throw;
counter() : _M_count(0), _M_throw(true) { }
@@ -40,10 +41,20 @@ namespace __gnu_test
}
static void
- increment() { get()._M_count++; }
+ increment()
+ {
+ counter& cntr = get();
+ cntr._M_count++;
+ cntr._M_increments++;
+ }
static void
- decrement() { get()._M_count--; }
+ decrement()
+ {
+ counter& cntr = get();
+ cntr._M_count--;
+ cntr._M_decrements++;
+ }
static counter&
get()
@@ -57,6 +68,13 @@ namespace __gnu_test
static void
exceptions(bool __b) { get()._M_throw = __b; }
+
+ static void
+ reset()
+ {
+ counter& cntr = get();
+ cntr._M_increments = cntr._M_decrements = 0;
+ }
};
template<typename Alloc, bool uses_global_new>
