public inbox for libstdc++-cvs@sourceware.org help / color / mirror / Atom feed
From: "Franथईois Dumont" <fdumont@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r12-1021] libstdc++: Limit allocation on iterator insertion in Hashtable [PR 96088] Date: Mon, 24 May 2021 19:52:59 +0000 (GMT) [thread overview] Message-ID: <20210524195259.C2D263892464@sourceware.org> (raw) 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>
reply other threads:[~2021-05-24 19:52 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20210524195259.C2D263892464@sourceware.org \ --to=fdumont@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ --cc=libstdc++-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
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).