public inbox for libstdc++-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc r12-1021] libstdc++: Limit allocation on iterator insertion in Hashtable [PR 96088]
@ 2021-05-24 19:52 Franथईois Dumont
0 siblings, 0 replies; only message in thread
From: Franथईois Dumont @ 2021-05-24 19:52 UTC (permalink / raw)
To: gcc-cvs, libstdc++-cvs
https://gcc.gnu.org/g:2c43f5ec9db163696de8691eb529df06c4999bcc
commit r12-1021-g2c43f5ec9db163696de8691eb529df06c4999bcc
Author: François Dumont <fdumont@gcc.gnu.org>
Date: Tue Aug 25 21:31:23 2020 +0200
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.
Diff:
---
libstdc++-v3/include/bits/hashtable.h | 59 ++++-
libstdc++-v3/include/bits/hashtable_policy.h | 53 +++-
.../testsuite/23_containers/unordered_map/96088.cc | 269 ++++++++++++++++++++
.../23_containers/unordered_multimap/96088.cc | 65 +++++
.../23_containers/unordered_multiset/96088.cc | 65 +++++
.../testsuite/23_containers/unordered_set/96088.cc | 271 +++++++++++++++++++++
.../testsuite/util/replacement_memory_operators.h | 22 +-
7 files changed, 782 insertions(+), 22 deletions(-)
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>
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2021-05-24 19:52 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-05-24 19:52 [gcc r12-1021] libstdc++: Limit allocation on iterator insertion in Hashtable [PR 96088] Franथईois Dumont
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).