* Hashtable PR96088 Work in Progress @ 2020-09-01 12:36 François Dumont 2020-10-17 16:21 ` [PATCH] Hashtable PR96088 François Dumont 0 siblings, 1 reply; 19+ messages in thread From: François Dumont @ 2020-09-01 12:36 UTC (permalink / raw) To: libstdc++ [-- Attachment #1: Type: text/plain, Size: 1427 bytes --] Hi I started working on PR96088 problem in Hashtable implementation. In the case of multi-key containers the problem is easy to manage. Now that we have _Scoped_node we can easily allocate the node first and then extract the key from it to compute hash code. It is quite safe as computating a hash code is rarely going to throw especially if there is no allocation anymore to invoke the hasher. In the unique-key case it is more tricky. First I only consider the hasher invocation, the equal_to shall be consistent with it. My approach is to consider that if the operation needed transform the inserted element key part into the hasher argument can throw then I better generate a key_type instance myself and move it to the node if it is eventually to be inserted. Note that any allocation needed to call the hasher from the key_type is user fault. Of course the tricky part here is to find out what is the hasher argument_type. For the moment I support hasher with a nested argument_type typedef and function pointer. But, as pointed out by the tests which are failing for the moment I am missing the support for a classic functor. I am pretty sure that if I support it I will still be missing some use cases (like std::function). So I am looking for help on how to determine it. Or maybe the whole approach it wrong ? For now I am still working on it, thanks, François [-- Attachment #2: pr96088.patch --] [-- Type: text/x-patch, Size: 19300 bytes --] diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 07a4abe5c33..8496c5eb621 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -718,13 +718,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bucket_index(__hash_code __c) const { return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); } + template<typename _KType, typename _Arg, typename _NodeGenerator> + static __node_type* + _S_build_node(__detail::_Select1st, _KType&& __k, _Arg&& __arg, + const _NodeGenerator& __node_gen) + { + return __node_gen(piecewise_construct, + forward_as_tuple(std::forward<_KType>(__k)), + forward_as_tuple(__detail::_Select2nd{}(std::forward<_Arg>(__arg)))); + } + + template<typename _KType, typename _Arg, typename _NodeGenerator> + static __node_type* + _S_build_node(__detail::_Identity, _KType&& __k, _Arg&&, + const _NodeGenerator& __node_gen) + { return __node_gen(std::forward<_KType>(__k)); } + // Find and insert helper functions and types // Find the node before the one matching the criteria. + template<typename _KType> __node_base* - _M_find_before_node(size_type, const key_type&, __hash_code) const; + _M_find_before_node(size_type, const _KType&, __hash_code) const; + template<typename _KType> __node_type* - _M_find_node(size_type __bkt, const key_type& __key, + _M_find_node(size_type __bkt, const _KType& __key, __hash_code __c) const { __node_base* __before_n = _M_find_before_node(__bkt, __key, __c); @@ -778,9 +796,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator _M_emplace(const_iterator, false_type __uks, _Args&&... __args); + template<typename _KType, typename _Arg, typename _NodeGenerator> + std::pair<iterator, bool> + _M_insert_unique(_KType&&, _Arg&&, const _NodeGenerator&); + + // Detect nested argument_type. + template<typename _Tp, typename = __void_t<>> + struct _Hash_arg_t + { typedef key_type argument_type; }; + + // Nested argument_type. + template<typename _Tp> + struct _Hash_arg_t<_Tp, + __void_t<typename _Tp::argument_type>> + { typedef typename _Tp::argument_type argument_type; }; + + // Function pointer. + template<typename _Arg> + struct _Hash_arg_t<std::size_t(*)(const _Arg&)> + { typedef _Arg argument_type; }; + + template<typename _KType, + typename _ArgType = typename _Hash_arg_t<_Hash>::argument_type> + static typename conditional< + std::is_nothrow_constructible<_ArgType, _KType>::value, + _KType&&, + key_type>::type + _S_forward_key(_KType&& __k) + { return std::forward<_KType>(__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 @@ -1605,10 +1666,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> + template<typename _KType> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_find_before_node(size_type __bkt, const key_type& __k, + _M_find_before_node(size_type __bkt, const _KType& __k, __hash_code __code) const -> __node_base* { @@ -1841,22 +1903,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 _KType, 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(_KType&& __k, _Arg&& __v, + const _NodeGenerator& __node_gen) -> pair<iterator, bool> { - const key_type& __k = _ExtractKey{}(__v); __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); if (__node_type* __node = _M_find_node(__bkt, __k, __code)) return { iterator(__node), false }; - _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; + _Scoped_node __node { + _S_build_node(_ExtractKey{}, + std::forward<_KType>(__k), std::forward<_Arg>(__v), + __node_gen), + this + }; auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node); __node._M_node = nullptr; @@ -1877,12 +1943,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 0109ef86a7b..400827412f7 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -94,6 +94,15 @@ 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 _NodeAlloc> struct _Hashtable_alloc; @@ -117,9 +126,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 +140,7 @@ namespace __detail __try { __node_alloc_traits::construct(__a, __node->_M_valptr(), - std::forward<_Arg>(__arg)); + std::forward<_Args>(__args)...); } __catch(...) { @@ -140,7 +149,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 +170,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; @@ -1215,10 +1224,11 @@ namespace __detail _Hash_code_base() = default; _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } + template<typename _KType> __hash_code - _M_hash_code(const _Key& __k) const + _M_hash_code(const _KType& __k) const { - static_assert(__is_invocable<const _Hash&, const _Key&>{}, + static_assert(__is_invocable<const _Hash&, const _KType&>{}, "hash function must be invocable with an argument of key type"); return _M_hash()(__k); } @@ -1280,10 +1290,11 @@ namespace __detail _Hash_code_base() = default; _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } + template<typename _KType> __hash_code - _M_hash_code(const _Key& __k) const + _M_hash_code(const _KType& __k) const { - static_assert(__is_invocable<const _Hash&, const _Key&>{}, + static_assert(__is_invocable<const _Hash&, const _KType&>{}, "hash function must be invocable with an argument of key type"); return _M_hash()(__k); } @@ -1675,10 +1686,11 @@ namespace __detail : __hash_code_base(__hash), _EqualEBO(__eq) { } + template<typename _KType> bool - _M_equals(const _Key& __k, __hash_code __c, const __node_type* __n) const + _M_equals(const _KType& __k, __hash_code __c, const __node_type* __n) const { - static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{}, + static_assert(__is_invocable<const _Equal&, const _KType&, const _Key&>{}, "key equality predicate must be invocable with two arguments of " "key type"); return _Equal_hash_code<__node_type>::_S_equals(__c, *__n) 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..87b1da265b9 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc @@ -0,0 +1,240 @@ +// { dg-do run { target c++11 } } + +// 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/>. + +// 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) +{ + std::hash<std::string> h; + return h(str); +} + +void +test11() +{ + typedef std::size_t (*hash_string_t)(const std::string&); + __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) +{ + std::hash<std::string_view> h; + return h(str); +} + +void +test12() +{ + typedef std::size_t (*hash_stringview_t)(const std::string_view&); + __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_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_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..ffc98e25540 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc @@ -0,0 +1,65 @@ +// { dg-do run { target c++17 } } + +// 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/>. + +// 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/util/replacement_memory_operators.h b/libstdc++-v3/testsuite/util/replacement_memory_operators.h index a90ffd47524..a76962ebedd 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] 19+ messages in thread
* [PATCH] Hashtable PR96088 2020-09-01 12:36 Hashtable PR96088 Work in Progress François Dumont @ 2020-10-17 16:21 ` François Dumont 2020-10-24 14:25 ` François Dumont 0 siblings, 1 reply; 19+ messages in thread From: François Dumont @ 2020-10-17 16:21 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 4292 bytes --] I eventually would like to propose the following resolution. For multi-key containers I kept the same resolution build the node first and compute has code from the node key. For unique-key ones I change behavior when I can't find out hash functor argument type. I am rather using the iterator key type and just hope that the user's functors are prepared for it. For now I am using functor argument_type which is deprecated. I just hope that the day we remove it we will have a compiler built-in to get any functor argument type given an input type. libstdc++: Limit allocation on iterator insertion in Hashtable [PR 96088] Detect Hash functor argument type to find out if it is different to the container key_type and if a temporary instance needs to be generated to invoke the functor from the iterator value_type key part. If this temporary generation can throw a key_type instance is generated at Hashtable level and use to call the functors and, if needed, move it to the storage. libstdc++-v3/ChangeLog: PR libstdc++/96088 * include/bits/hashtable_policy.h (_Select2nd): New. (_NodeBuilder<>): New. (_ReuseOrAllocNode<>::operator()): Use varriadic template args. (_AllocNode<>::operator()): Likewise. (_Hash_code_base<>::_M_hash_code): Add _KType template parameter. (_Hashtable_base<>::_M_equals): Add _KType template parameter. * include/bits/hashtable.h (_Hashtable<>::__node_builder_t): New. (_Hashtable<>::_M_find_before_node): Add _KType template parameter. (_Hashtable<>::_M_find_node): Likewise. (_Hashtable<>::_Hash_arg_t): New. (_Hashtable<>::_S_forward_key): New. (_Hashtable<>::_M_insert_unique<>(_KType&&, _Arg&&, const _NodeGenerator&)): New. (_Hashtable<>::_M_insert): Use latter. * 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 x86_64. Ok to commit ? François On 01/09/20 2:36 pm, François Dumont wrote: > Hi > > I started working on PR96088 problem in Hashtable implementation. > > In the case of multi-key containers the problem is easy to manage. > Now that we have _Scoped_node we can easily allocate the node first > and then extract the key from it to compute hash code. It is quite > safe as computating a hash code is rarely going to throw especially if > there is no allocation anymore to invoke the hasher. > > In the unique-key case it is more tricky. First I only consider > the hasher invocation, the equal_to shall be consistent with it. My > approach is to consider that if the operation needed transform the > inserted element key part into the hasher argument can throw then I > better generate a key_type instance myself and move it to the node if > it is eventually to be inserted. Note that any allocation needed to > call the hasher from the key_type is user fault. > > Of course the tricky part here is to find out what is the hasher > argument_type. For the moment I support hasher with a nested > argument_type typedef and function pointer. But, as pointed out by the > tests which are failing for the moment I am missing the support for a > classic functor. I am pretty sure that if I support it I will still be > missing some use cases (like std::function). So I am looking for help > on how to determine it. Or maybe the whole approach it wrong ? > > For now I am still working on it, thanks, > > François > [-- Attachment #2: pr96088.patch --] [-- Type: text/x-patch, Size: 28586 bytes --] diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 07a4abe5c33..e777004442a 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -251,6 +251,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 @@ -720,11 +722,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Find and insert helper functions and types // Find the node before the one matching the criteria. + template<typename _KType> __node_base* - _M_find_before_node(size_type, const key_type&, __hash_code) const; + _M_find_before_node(size_type, const _KType&, __hash_code) const; + template<typename _KType> __node_type* - _M_find_node(size_type __bkt, const key_type& __key, + _M_find_node(size_type __bkt, const _KType& __key, __hash_code __c) const { __node_base* __before_n = _M_find_before_node(__bkt, __key, __c); @@ -778,9 +782,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator _M_emplace(const_iterator, false_type __uks, _Args&&... __args); + template<typename _KType, typename _Arg, typename _NodeGenerator> + std::pair<iterator, bool> + _M_insert_unique(_KType&&, _Arg&&, const _NodeGenerator&); + + // Detect nested argument_type. + template<typename _KType, typename _Tp, typename = __void_t<>> + struct _Hash_arg_t + { typedef _KType argument_type; }; + + // Nested argument_type. + template<typename _KType, typename _Tp> + struct _Hash_arg_t<_KType, _Tp, + __void_t<typename _Tp::argument_type>> + { typedef typename _Tp::argument_type argument_type; }; + + // Function pointer. + template<typename _KType, typename _Arg> + struct _Hash_arg_t<_KType, std::size_t(*)(const _Arg&)> + { typedef _Arg argument_type; }; + + template<typename _KType, + typename _ArgType + = typename _Hash_arg_t<_KType, _Hash>::argument_type> + static typename conditional< + __is_nothrow_convertible<_KType, _ArgType>::value, + _KType&&, + key_type>::type + _S_forward_key(_KType&& __k) + { return std::forward<_KType>(__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 @@ -1605,10 +1653,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> + template<typename _KType> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_find_before_node(size_type __bkt, const key_type& __k, + _M_find_before_node(size_type __bkt, const _KType& __k, __hash_code __code) const -> __node_base* { @@ -1841,22 +1890,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 _KType, 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(_KType&& __k, _Arg&& __v, + const _NodeGenerator& __node_gen) -> pair<iterator, bool> { - const key_type& __k = _ExtractKey{}(__v); __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); if (__node_type* __node = _M_find_node(__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<_KType>(__k), + std::forward<_Arg>(__v), + __node_gen), + this + }; auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node); __node._M_node = nullptr; @@ -1877,12 +1930,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 31ff4f16579..da0e7897e31 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -94,6 +94,48 @@ 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 _KType, typename _Arg, typename _NodeGenerator> + static auto + _S_build(_KType&& __k, _Arg&& __arg, + const _NodeGenerator& __node_gen) + -> decltype(__node_gen(std::piecewise_construct, + std::forward_as_tuple(std::forward<_KType>(__k)), + std::forward_as_tuple(_Select2nd{}( + std::forward<_Arg>(__arg))))) + { + return __node_gen(std::piecewise_construct, + std::forward_as_tuple(std::forward<_KType>(__k)), + std::forward_as_tuple(_Select2nd{}( + std::forward<_Arg>(__arg)))); + } + }; + + template<> + struct _NodeBuilder<_Identity> + { + template<typename _KType, typename _Arg, typename _NodeGenerator> + static auto + _S_build(_KType&& __k, _Arg&&, + const _NodeGenerator& __node_gen) + -> decltype(__node_gen(std::forward<_KType>(__k))) + { return __node_gen(std::forward<_KType>(__k)); } + }; + template<typename _NodeAlloc> struct _Hashtable_alloc; @@ -117,9 +159,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 +173,7 @@ namespace __detail __try { __node_alloc_traits::construct(__a, __node->_M_valptr(), - std::forward<_Arg>(__arg)); + std::forward<_Args>(__args)...); } __catch(...) { @@ -140,7 +182,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 +203,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; @@ -1216,10 +1258,11 @@ namespace __detail _Hash_code_base() = default; _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } + template<typename _KType> __hash_code - _M_hash_code(const _Key& __k) const + _M_hash_code(const _KType& __k) const { - static_assert(__is_invocable<const _Hash&, const _Key&>{}, + static_assert(__is_invocable<const _Hash&, const _KType&>{}, "hash function must be invocable with an argument of key type"); return _M_hash()(__k); } @@ -1281,10 +1324,11 @@ namespace __detail _Hash_code_base() = default; _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } + template<typename _KType> __hash_code - _M_hash_code(const _Key& __k) const + _M_hash_code(const _KType& __k) const { - static_assert(__is_invocable<const _Hash&, const _Key&>{}, + static_assert(__is_invocable<const _Hash&, const _KType&>{}, "hash function must be invocable with an argument of key type"); return _M_hash()(__k); } @@ -1676,10 +1720,13 @@ namespace __detail : __hash_code_base(__hash), _EqualEBO(__eq) { } + template<typename _KType> bool - _M_equals(const _Key& __k, __hash_code __c, const __node_type* __n) const + _M_equals(const _KType& __k, __hash_code __c, + const __node_type* __n) const { - static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{}, + static_assert( + __is_invocable<const _Equal&, const _KType&, const _Key&>{}, "key equality predicate must be invocable with two arguments of " "key type"); return _Equal_hash_code<__node_type>::_S_equals(__c, *__n) 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..4d399353120 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc @@ -0,0 +1,240 @@ +// { dg-do run { target c++11 } } + +// 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/>. + +// 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) +{ + std::hash<std::string> h; + return h(str); +} + +void +test11() +{ + typedef std::size_t (*hash_string_t)(const std::string&); + __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) +{ + std::hash<std::string_view> h; + return h(str); +} + +void +test12() +{ + typedef std::size_t (*hash_stringview_t)(const std::string_view&); + __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 == 4 ); + + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 6 ); +} + +struct hash_string_view_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_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..ffc98e25540 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc @@ -0,0 +1,65 @@ +// { dg-do run { target c++17 } } + +// 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/>. + +// 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..4951b100a54 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc @@ -0,0 +1,65 @@ +// { dg-do run { target c++17 } } + +// 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/>. + +// 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..da4794cfb22 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc @@ -0,0 +1,240 @@ +// { dg-do run { target c++11 } } + +// 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/>. + +// 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) +{ + std::hash<std::string> h; + return h(str); +} + +void +test11() +{ + typedef std::size_t (*hash_string_t)(const std::string&); + __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) +{ + std::hash<std::string_view> h; + return h(str); +} + +void +test12() +{ + typedef std::size_t (*hash_stringview_t)(const std::string_view&); + __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 == 4 ); + + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 6 ); +} + +struct hash_string_view_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_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(); + test03(); + return 0; +} diff --git a/libstdc++-v3/testsuite/util/replacement_memory_operators.h b/libstdc++-v3/testsuite/util/replacement_memory_operators.h index a90ffd47524..a76962ebedd 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] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2020-10-17 16:21 ` [PATCH] Hashtable PR96088 François Dumont @ 2020-10-24 14:25 ` François Dumont 2020-12-04 9:10 ` François Dumont 0 siblings, 1 reply; 19+ messages in thread From: François Dumont @ 2020-10-24 14:25 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 4519 bytes --] Hi Just a rebase of this patch. François On 17/10/20 6:21 pm, François Dumont wrote: > I eventually would like to propose the following resolution. > > For multi-key containers I kept the same resolution build the node > first and compute has code from the node key. > > For unique-key ones I change behavior when I can't find out hash > functor argument type. I am rather using the iterator key type and > just hope that the user's functors are prepared for it. > > For now I am using functor argument_type which is deprecated. I just > hope that the day we remove it we will have a compiler built-in to get > any functor argument type given an input type. > > libstdc++: Limit allocation on iterator insertion in Hashtable [PR > 96088] > > Detect Hash functor argument type to find out if it is different > to the > container key_type and if a temporary instance needs to be > generated to invoke > the functor from the iterator value_type key part. If this > temporary generation > can throw a key_type instance is generated at Hashtable level and > use to call > the functors and, if needed, move it to the storage. > > libstdc++-v3/ChangeLog: > > PR libstdc++/96088 > * include/bits/hashtable_policy.h (_Select2nd): New. > (_NodeBuilder<>): New. > (_ReuseOrAllocNode<>::operator()): Use varriadic template > args. > (_AllocNode<>::operator()): Likewise. > (_Hash_code_base<>::_M_hash_code): Add _KType template > parameter. > (_Hashtable_base<>::_M_equals): Add _KType template > parameter. > * include/bits/hashtable.h > (_Hashtable<>::__node_builder_t): New. > (_Hashtable<>::_M_find_before_node): Add _KType template > parameter. > (_Hashtable<>::_M_find_node): Likewise. > (_Hashtable<>::_Hash_arg_t): New. > (_Hashtable<>::_S_forward_key): New. > (_Hashtable<>::_M_insert_unique<>(_KType&&, _Arg&&, const > _NodeGenerator&)): > New. > (_Hashtable<>::_M_insert): Use latter. > * 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 x86_64. > > Ok to commit ? > > François > > On 01/09/20 2:36 pm, François Dumont wrote: >> Hi >> >> I started working on PR96088 problem in Hashtable implementation. >> >> In the case of multi-key containers the problem is easy to >> manage. Now that we have _Scoped_node we can easily allocate the node >> first and then extract the key from it to compute hash code. It is >> quite safe as computating a hash code is rarely going to throw >> especially if there is no allocation anymore to invoke the hasher. >> >> In the unique-key case it is more tricky. First I only consider >> the hasher invocation, the equal_to shall be consistent with it. My >> approach is to consider that if the operation needed transform the >> inserted element key part into the hasher argument can throw then I >> better generate a key_type instance myself and move it to the node if >> it is eventually to be inserted. Note that any allocation needed to >> call the hasher from the key_type is user fault. >> >> Of course the tricky part here is to find out what is the hasher >> argument_type. For the moment I support hasher with a nested >> argument_type typedef and function pointer. But, as pointed out by >> the tests which are failing for the moment I am missing the support >> for a classic functor. I am pretty sure that if I support it I will >> still be missing some use cases (like std::function). So I am looking >> for help on how to determine it. Or maybe the whole approach it wrong ? >> >> For now I am still working on it, thanks, >> >> François >> > [-- Attachment #2: pr96088.patch --] [-- Type: text/x-patch, Size: 30078 bytes --] diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 6c6c5edde0b..234b40c13b7 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 @@ -736,18 +738,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Find and insert helper functions and types // Find the node before the one matching the criteria. - __node_base_ptr - _M_find_before_node(size_type, const key_type&, __hash_code) const; - - __node_ptr - _M_find_node(size_type __bkt, const key_type& __key, - __hash_code __c) const - { - __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c); - if (__before_n) - return static_cast<__node_ptr>(__before_n->_M_nxt); - return nullptr; - } + template<typename _KType> + __node_base_ptr + _M_find_before_node(size_type, const _KType&, __hash_code) const; + + template<typename _KType> + __node_ptr + _M_find_node(size_type __bkt, const _KType& __key, + __hash_code __c) const + { + __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c); + if (__before_n) + return static_cast<__node_ptr>(__before_n->_M_nxt); + return nullptr; + } // Insert a node at the beginning of a bucket. void @@ -794,9 +798,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator _M_emplace(const_iterator, false_type __uks, _Args&&... __args); + template<typename _KType, typename _Arg, typename _NodeGenerator> + std::pair<iterator, bool> + _M_insert_unique(_KType&&, _Arg&&, const _NodeGenerator&); + + // Detect nested argument_type. + template<typename _KType, typename _Tp, typename = __void_t<>> + struct _Hash_arg_t + { typedef _KType argument_type; }; + + // Nested argument_type. + template<typename _KType, typename _Tp> + struct _Hash_arg_t<_KType, _Tp, + __void_t<typename _Tp::argument_type>> + { typedef typename _Tp::argument_type argument_type; }; + + // Function pointer. + template<typename _KType, typename _Arg> + struct _Hash_arg_t<_KType, std::size_t(*)(const _Arg&)> + { typedef _Arg argument_type; }; + + template<typename _KType, + typename _ArgType + = typename _Hash_arg_t<_KType, _Hash>::argument_type> + static typename conditional< + __is_nothrow_convertible<_KType, _ArgType>::value, + _KType&&, + key_type>::type + _S_forward_key(_KType&& __k) + { return std::forward<_KType>(__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 @@ -1621,30 +1669,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> - auto - _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_find_before_node(size_type __bkt, const key_type& __k, - __hash_code __code) const - -> __node_base_ptr - { - __node_base_ptr __prev_p = _M_buckets[__bkt]; - if (!__prev_p) - return nullptr; + template<typename _KType> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_find_before_node(size_type __bkt, const _KType& __k, + __hash_code __code) const + -> __node_base_ptr + { + __node_base_ptr __prev_p = _M_buckets[__bkt]; + if (!__prev_p) + return nullptr; - for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);; - __p = __p->_M_next()) - { - if (this->_M_equals(__k, __code, *__p)) - return __prev_p; + for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);; + __p = __p->_M_next()) + { + if (this->_M_equals(__k, __code, *__p)) + return __prev_p; - if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt) - break; - __prev_p = __p; - } + if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt) + break; + __prev_p = __p; + } - return nullptr; - } + return nullptr; + } template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, @@ -1858,22 +1907,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 _KType, 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(_KType&& __k, _Arg&& __v, + const _NodeGenerator& __node_gen) -> pair<iterator, bool> { - const key_type& __k = _ExtractKey{}(__v); __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); if (__node_ptr __node = _M_find_node(__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<_KType>(__k), + std::forward<_Arg>(__v), + __node_gen), + this + }; auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node); __node._M_node = nullptr; @@ -1894,12 +1947,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 f5ce7209957..378f800ab9e 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -94,6 +94,48 @@ 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 _KType, typename _Arg, typename _NodeGenerator> + static auto + _S_build(_KType&& __k, _Arg&& __arg, + const _NodeGenerator& __node_gen) + -> decltype(__node_gen(std::piecewise_construct, + std::forward_as_tuple(std::forward<_KType>(__k)), + std::forward_as_tuple(_Select2nd{}( + std::forward<_Arg>(__arg))))) + { + return __node_gen(std::piecewise_construct, + std::forward_as_tuple(std::forward<_KType>(__k)), + std::forward_as_tuple(_Select2nd{}( + std::forward<_Arg>(__arg)))); + } + }; + + template<> + struct _NodeBuilder<_Identity> + { + template<typename _KType, typename _Arg, typename _NodeGenerator> + static auto + _S_build(_KType&& __k, _Arg&&, + const _NodeGenerator& __node_gen) + -> decltype(__node_gen(std::forward<_KType>(__k))) + { return __node_gen(std::forward<_KType>(__k)); } + }; + template<typename _NodeAlloc> struct _Hashtable_alloc; @@ -117,9 +159,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 +173,7 @@ namespace __detail __try { __node_alloc_traits::construct(__a, __node->_M_valptr(), - std::forward<_Arg>(__arg)); + std::forward<_Args>(__args)...); } __catch(...) { @@ -140,7 +182,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 +203,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; @@ -1211,13 +1253,14 @@ namespace __detail _Hash_code_base() = default; _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } - __hash_code - _M_hash_code(const _Key& __k) const - { - static_assert(__is_invocable<const _Hash&, const _Key&>{}, + template<typename _KType> + __hash_code + _M_hash_code(const _KType& __k) const + { + static_assert(__is_invocable<const _Hash&, const _KType&>{}, "hash function must be invocable with an argument of key type"); - return _M_hash()(__k); - } + return _M_hash()(__k); + } std::size_t _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const @@ -1597,15 +1640,18 @@ namespace __detail : __hash_code_base(__hash), _EqualEBO(__eq) { } - bool - _M_equals(const _Key& __k, __hash_code __c, - const _Hash_node_value<_Value, __hash_cached::value>& __n) const - { - static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{}, - "key equality predicate must be invocable with two arguments of " - "key type"); - return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); - } + template<typename _KType> + bool + _M_equals(const _KType& __k, __hash_code __c, + const _Hash_node_value<_Value, + __hash_cached::value>& __n) const + { + static_assert( + __is_invocable<const _Equal&, const _KType&, const _Key&>{}, + "key equality predicate must be invocable with two arguments of " + "key type"); + return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); + } bool _M_node_equals( 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..4d399353120 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc @@ -0,0 +1,240 @@ +// { dg-do run { target c++11 } } + +// 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/>. + +// 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) +{ + std::hash<std::string> h; + return h(str); +} + +void +test11() +{ + typedef std::size_t (*hash_string_t)(const std::string&); + __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) +{ + std::hash<std::string_view> h; + return h(str); +} + +void +test12() +{ + typedef std::size_t (*hash_stringview_t)(const std::string_view&); + __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 == 4 ); + + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 6 ); +} + +struct hash_string_view_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_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..ffc98e25540 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc @@ -0,0 +1,65 @@ +// { dg-do run { target c++17 } } + +// 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/>. + +// 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..4951b100a54 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc @@ -0,0 +1,65 @@ +// { dg-do run { target c++17 } } + +// 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/>. + +// 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..da4794cfb22 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc @@ -0,0 +1,240 @@ +// { dg-do run { target c++11 } } + +// 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/>. + +// 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) +{ + std::hash<std::string> h; + return h(str); +} + +void +test11() +{ + typedef std::size_t (*hash_string_t)(const std::string&); + __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) +{ + std::hash<std::string_view> h; + return h(str); +} + +void +test12() +{ + typedef std::size_t (*hash_stringview_t)(const std::string_view&); + __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 == 4 ); + + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 6 ); +} + +struct hash_string_view_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_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(); + test03(); + return 0; +} diff --git a/libstdc++-v3/testsuite/util/replacement_memory_operators.h b/libstdc++-v3/testsuite/util/replacement_memory_operators.h index a90ffd47524..a76962ebedd 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] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2020-10-24 14:25 ` François Dumont @ 2020-12-04 9:10 ` François Dumont 2021-05-06 20:03 ` François Dumont 0 siblings, 1 reply; 19+ messages in thread From: François Dumont @ 2020-12-04 9:10 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 7341 bytes --] Following submission of the heterogeneous lookup in unordered containers I rebased this patch on top of it. Appart from reducing its size because of some code reuse the heterogeneous lookup had no impact on this one. This is because when I cannot find out if conversion from inserted element type to hash functor can throw then I pass the element as-is, like if hash functor was transparent. libstdc++: Limit allocation on iterator insertion in Hashtable [PR 96088] Detect Hash functor argument type to find out if it is different to the container key_type and if a temporary instance needs to be generated to invoke the functor from the iterator value_type key part. If this temporary generation can throw a key_type instance is generated at Hashtable level and used to call the functors and, if necessary, moved to the storage. libstdc++-v3/ChangeLog: PR libstdc++/96088 * include/bits/hashtable_policy.h (_Select2nd): New. (_NodeBuilder<>): New. (_ReuseOrAllocNode<>::operator()): Use variadic template args. (_AllocNode<>::operator()): Likewise. (_Hash_code_base<>::_M_hash_code): Add _Kt template parameter. (_Hashtable_base<>::_M_equals): Add _Kt template parameter. * include/bits/hashtable.h (_Hashtable<>::__node_builder_t): New. (_Hashtable<>::_M_find_before_node): Add _Kt template parameter. (_Hashtable<>::_M_find_node): Likewise. (_Hashtable<>::_Hash_arg_t): New. (_Hashtable<>::_S_forward_key): New. (_Hashtable<>::_M_insert_unique<>(_Kt&&, _Arg&&, const _NodeGenerator&)): New. (_Hashtable<>::_M_insert): Use latter. * 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. Note that I plan to change counter type name to something more meaningful but only when back to stage 1. François On 24/10/20 4:25 pm, François Dumont wrote: > Hi > > Just a rebase of this patch. > > François > > On 17/10/20 6:21 pm, François Dumont wrote: >> I eventually would like to propose the following resolution. >> >> For multi-key containers I kept the same resolution build the node >> first and compute has code from the node key. >> >> For unique-key ones I change behavior when I can't find out hash >> functor argument type. I am rather using the iterator key type and >> just hope that the user's functors are prepared for it. >> >> For now I am using functor argument_type which is deprecated. I just >> hope that the day we remove it we will have a compiler built-in to >> get any functor argument type given an input type. >> >> libstdc++: Limit allocation on iterator insertion in Hashtable >> [PR 96088] >> >> Detect Hash functor argument type to find out if it is different >> to the >> container key_type and if a temporary instance needs to be >> generated to invoke >> the functor from the iterator value_type key part. If this >> temporary generation >> can throw a key_type instance is generated at Hashtable level and >> use to call >> the functors and, if needed, move it to the storage. >> >> libstdc++-v3/ChangeLog: >> >> PR libstdc++/96088 >> * include/bits/hashtable_policy.h (_Select2nd): New. >> (_NodeBuilder<>): New. >> (_ReuseOrAllocNode<>::operator()): Use varriadic template >> args. >> (_AllocNode<>::operator()): Likewise. >> (_Hash_code_base<>::_M_hash_code): Add _KType template >> parameter. >> (_Hashtable_base<>::_M_equals): Add _KType template >> parameter. >> * include/bits/hashtable.h >> (_Hashtable<>::__node_builder_t): New. >> (_Hashtable<>::_M_find_before_node): Add _KType template >> parameter. >> (_Hashtable<>::_M_find_node): Likewise. >> (_Hashtable<>::_Hash_arg_t): New. >> (_Hashtable<>::_S_forward_key): New. >> (_Hashtable<>::_M_insert_unique<>(_KType&&, _Arg&&, const >> _NodeGenerator&)): >> New. >> (_Hashtable<>::_M_insert): Use latter. >> * 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 x86_64. >> >> Ok to commit ? >> >> François >> >> On 01/09/20 2:36 pm, François Dumont wrote: >>> Hi >>> >>> I started working on PR96088 problem in Hashtable implementation. >>> >>> In the case of multi-key containers the problem is easy to >>> manage. Now that we have _Scoped_node we can easily allocate the >>> node first and then extract the key from it to compute hash code. It >>> is quite safe as computating a hash code is rarely going to throw >>> especially if there is no allocation anymore to invoke the hasher. >>> >>> In the unique-key case it is more tricky. First I only consider >>> the hasher invocation, the equal_to shall be consistent with it. My >>> approach is to consider that if the operation needed transform the >>> inserted element key part into the hasher argument can throw then I >>> better generate a key_type instance myself and move it to the node >>> if it is eventually to be inserted. Note that any allocation needed >>> to call the hasher from the key_type is user fault. >>> >>> Of course the tricky part here is to find out what is the hasher >>> argument_type. For the moment I support hasher with a nested >>> argument_type typedef and function pointer. But, as pointed out by >>> the tests which are failing for the moment I am missing the support >>> for a classic functor. I am pretty sure that if I support it I will >>> still be missing some use cases (like std::function). So I am >>> looking for help on how to determine it. Or maybe the whole approach >>> it wrong ? >>> >>> For now I am still working on it, thanks, >>> >>> François >>> >> > [-- Attachment #2: pr96088.patch --] [-- Type: text/x-patch, Size: 25641 bytes --] diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 30d4ee58100..57e3fdd33b2 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 @@ -827,9 +829,53 @@ _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 _Tp, typename = __void_t<>> + struct _Hash_arg_t + { typedef _Kt argument_type; }; + + // Nested argument_type. + template<typename _Kt, typename _Tp> + struct _Hash_arg_t<_Kt, _Tp, + __void_t<typename _Tp::argument_type>> + { typedef typename _Tp::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 + _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 @@ -2015,22 +2061,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); size_type __bkt = _M_bucket_index(__code); if (__node_ptr __node = _M_find_node(__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; @@ -2051,12 +2101,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 340aaede50c..131c75c7ecb 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..4d399353120 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc @@ -0,0 +1,240 @@ +// { dg-do run { target c++11 } } + +// 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/>. + +// 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) +{ + std::hash<std::string> h; + return h(str); +} + +void +test11() +{ + typedef std::size_t (*hash_string_t)(const std::string&); + __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) +{ + std::hash<std::string_view> h; + return h(str); +} + +void +test12() +{ + typedef std::size_t (*hash_stringview_t)(const std::string_view&); + __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 == 4 ); + + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 6 ); +} + +struct hash_string_view_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_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..ffc98e25540 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc @@ -0,0 +1,65 @@ +// { dg-do run { target c++17 } } + +// 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/>. + +// 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..4951b100a54 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc @@ -0,0 +1,65 @@ +// { dg-do run { target c++17 } } + +// 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/>. + +// 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..da4794cfb22 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc @@ -0,0 +1,240 @@ +// { dg-do run { target c++11 } } + +// 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/>. + +// 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) +{ + std::hash<std::string> h; + return h(str); +} + +void +test11() +{ + typedef std::size_t (*hash_string_t)(const std::string&); + __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) +{ + std::hash<std::string_view> h; + return h(str); +} + +void +test12() +{ + typedef std::size_t (*hash_stringview_t)(const std::string_view&); + __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 == 4 ); + + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 6 ); +} + +struct hash_string_view_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_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(); + test03(); + return 0; +} diff --git a/libstdc++-v3/testsuite/util/replacement_memory_operators.h b/libstdc++-v3/testsuite/util/replacement_memory_operators.h index 34c6e1b1a8b..6576fcf9a7a 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] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2020-12-04 9:10 ` François Dumont @ 2021-05-06 20:03 ` François Dumont 2021-05-17 19:24 ` François Dumont 2021-05-20 16:44 ` Jonathan Wakely 0 siblings, 2 replies; 19+ messages in thread From: François Dumont @ 2021-05-06 20:03 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 8078 bytes --] 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. Tested under Linux x86_64, ok to commit ? François On 04/12/20 10:10 am, François Dumont wrote: > Following submission of the heterogeneous lookup in unordered > containers I rebased this patch on top of it. > > Appart from reducing its size because of some code reuse the > heterogeneous lookup had no impact on this one. This is because when I > cannot find out if conversion from inserted element type to hash > functor can throw then I pass the element as-is, like if hash functor > was transparent. > > libstdc++: Limit allocation on iterator insertion in Hashtable [PR > 96088] > > Detect Hash functor argument type to find out if it is different > to the > container key_type and if a temporary instance needs to be > generated to invoke > the functor from the iterator value_type key part. If this > temporary generation > can throw a key_type instance is generated at Hashtable level and > used to call > the functors and, if necessary, moved to the storage. > > libstdc++-v3/ChangeLog: > > PR libstdc++/96088 > * include/bits/hashtable_policy.h (_Select2nd): New. > (_NodeBuilder<>): New. > (_ReuseOrAllocNode<>::operator()): Use variadic template > args. > (_AllocNode<>::operator()): Likewise. > (_Hash_code_base<>::_M_hash_code): Add _Kt template > parameter. > (_Hashtable_base<>::_M_equals): Add _Kt template parameter. > * include/bits/hashtable.h > (_Hashtable<>::__node_builder_t): New. > (_Hashtable<>::_M_find_before_node): Add _Kt template > parameter. > (_Hashtable<>::_M_find_node): Likewise. > (_Hashtable<>::_Hash_arg_t): New. > (_Hashtable<>::_S_forward_key): New. > (_Hashtable<>::_M_insert_unique<>(_Kt&&, _Arg&&, const _NodeGenerator&)): > New. > (_Hashtable<>::_M_insert): Use latter. > * 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. > > Note that I plan to change counter type name to something more > meaningful but only when back to stage 1. > > François > > On 24/10/20 4:25 pm, François Dumont wrote: >> Hi >> >> Just a rebase of this patch. >> >> François >> >> On 17/10/20 6:21 pm, François Dumont wrote: >>> I eventually would like to propose the following resolution. >>> >>> For multi-key containers I kept the same resolution build the node >>> first and compute has code from the node key. >>> >>> For unique-key ones I change behavior when I can't find out hash >>> functor argument type. I am rather using the iterator key type and >>> just hope that the user's functors are prepared for it. >>> >>> For now I am using functor argument_type which is deprecated. I just >>> hope that the day we remove it we will have a compiler built-in to >>> get any functor argument type given an input type. >>> >>> libstdc++: Limit allocation on iterator insertion in Hashtable >>> [PR 96088] >>> >>> Detect Hash functor argument type to find out if it is different >>> to the >>> container key_type and if a temporary instance needs to be >>> generated to invoke >>> the functor from the iterator value_type key part. If this >>> temporary generation >>> can throw a key_type instance is generated at Hashtable level >>> and use to call >>> the functors and, if needed, move it to the storage. >>> >>> libstdc++-v3/ChangeLog: >>> >>> PR libstdc++/96088 >>> * include/bits/hashtable_policy.h (_Select2nd): New. >>> (_NodeBuilder<>): New. >>> (_ReuseOrAllocNode<>::operator()): Use varriadic >>> template args. >>> (_AllocNode<>::operator()): Likewise. >>> (_Hash_code_base<>::_M_hash_code): Add _KType template >>> parameter. >>> (_Hashtable_base<>::_M_equals): Add _KType template >>> parameter. >>> * include/bits/hashtable.h >>> (_Hashtable<>::__node_builder_t): New. >>> (_Hashtable<>::_M_find_before_node): Add _KType template >>> parameter. >>> (_Hashtable<>::_M_find_node): Likewise. >>> (_Hashtable<>::_Hash_arg_t): New. >>> (_Hashtable<>::_S_forward_key): New. >>> (_Hashtable<>::_M_insert_unique<>(_KType&&, _Arg&&, const >>> _NodeGenerator&)): >>> New. >>> (_Hashtable<>::_M_insert): Use latter. >>> * 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 x86_64. >>> >>> Ok to commit ? >>> >>> François >>> >>> On 01/09/20 2:36 pm, François Dumont wrote: >>>> Hi >>>> >>>> I started working on PR96088 problem in Hashtable implementation. >>>> >>>> In the case of multi-key containers the problem is easy to >>>> manage. Now that we have _Scoped_node we can easily allocate the >>>> node first and then extract the key from it to compute hash code. >>>> It is quite safe as computating a hash code is rarely going to >>>> throw especially if there is no allocation anymore to invoke the >>>> hasher. >>>> >>>> In the unique-key case it is more tricky. First I only consider >>>> the hasher invocation, the equal_to shall be consistent with it. My >>>> approach is to consider that if the operation needed transform the >>>> inserted element key part into the hasher argument can throw then I >>>> better generate a key_type instance myself and move it to the node >>>> if it is eventually to be inserted. Note that any allocation needed >>>> to call the hasher from the key_type is user fault. >>>> >>>> Of course the tricky part here is to find out what is the >>>> hasher argument_type. For the moment I support hasher with a nested >>>> argument_type typedef and function pointer. But, as pointed out by >>>> the tests which are failing for the moment I am missing the support >>>> for a classic functor. I am pretty sure that if I support it I will >>>> still be missing some use cases (like std::function). So I am >>>> looking for help on how to determine it. Or maybe the whole >>>> approach it wrong ? >>>> >>>> For now I am still working on it, thanks, >>>> >>>> François >>>> >>> >> > [-- Attachment #2: hashtable.patch --] [-- Type: text/x-patch, Size: 25892 bytes --] diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 6711d08e6b8..c19c4a0f155 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,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 + _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 +2116,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 +2156,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..a9c27402c2d --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc @@ -0,0 +1,240 @@ +// { 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) +{ + std::hash<std::string> h; + return h(str); +} + +void +test11() +{ + typedef std::size_t (*hash_string_t)(const std::string&); + __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) +{ + std::hash<std::string_view> h; + return h(str); +} + +void +test12() +{ + typedef std::size_t (*hash_stringview_t)(const std::string_view&); + __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 == 4 ); + + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 6 ); +} + +struct hash_string_view_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_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..8517bc9b928 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc @@ -0,0 +1,240 @@ +// { 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) +{ + std::hash<std::string> h; + return h(str); +} + +void +test11() +{ + typedef std::size_t (*hash_string_t)(const std::string&); + __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) +{ + std::hash<std::string_view> h; + return h(str); +} + +void +test12() +{ + typedef std::size_t (*hash_stringview_t)(const std::string_view&); + __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 == 4 ); + + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 6 ); +} + +struct hash_string_view_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_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(); + 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] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-05-06 20:03 ` François Dumont @ 2021-05-17 19:24 ` François Dumont 2021-05-20 16:44 ` Jonathan Wakely 1 sibling, 0 replies; 19+ messages in thread From: François Dumont @ 2021-05-17 19:24 UTC (permalink / raw) To: libstdc++, gcc-patches Hi No chance yet to review this proposal ? François On 06/05/21 10:03 pm, François Dumont 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. > > Tested under Linux x86_64, ok to commit ? > > François > > > On 04/12/20 10:10 am, François Dumont wrote: >> Following submission of the heterogeneous lookup in unordered >> containers I rebased this patch on top of it. >> >> Appart from reducing its size because of some code reuse the >> heterogeneous lookup had no impact on this one. This is because when >> I cannot find out if conversion from inserted element type to hash >> functor can throw then I pass the element as-is, like if hash functor >> was transparent. >> >> libstdc++: Limit allocation on iterator insertion in Hashtable >> [PR 96088] >> >> Detect Hash functor argument type to find out if it is different >> to the >> container key_type and if a temporary instance needs to be >> generated to invoke >> the functor from the iterator value_type key part. If this >> temporary generation >> can throw a key_type instance is generated at Hashtable level and >> used to call >> the functors and, if necessary, moved to the storage. >> >> libstdc++-v3/ChangeLog: >> >> PR libstdc++/96088 >> * include/bits/hashtable_policy.h (_Select2nd): New. >> (_NodeBuilder<>): New. >> (_ReuseOrAllocNode<>::operator()): Use variadic template >> args. >> (_AllocNode<>::operator()): Likewise. >> (_Hash_code_base<>::_M_hash_code): Add _Kt template >> parameter. >> (_Hashtable_base<>::_M_equals): Add _Kt template parameter. >> * include/bits/hashtable.h >> (_Hashtable<>::__node_builder_t): New. >> (_Hashtable<>::_M_find_before_node): Add _Kt template >> parameter. >> (_Hashtable<>::_M_find_node): Likewise. >> (_Hashtable<>::_Hash_arg_t): New. >> (_Hashtable<>::_S_forward_key): New. >> (_Hashtable<>::_M_insert_unique<>(_Kt&&, _Arg&&, const >> _NodeGenerator&)): >> New. >> (_Hashtable<>::_M_insert): Use latter. >> * 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. >> >> Note that I plan to change counter type name to something more >> meaningful but only when back to stage 1. >> >> François >> >> On 24/10/20 4:25 pm, François Dumont wrote: >>> Hi >>> >>> Just a rebase of this patch. >>> >>> François >>> >>> On 17/10/20 6:21 pm, François Dumont wrote: >>>> I eventually would like to propose the following resolution. >>>> >>>> For multi-key containers I kept the same resolution build the node >>>> first and compute has code from the node key. >>>> >>>> For unique-key ones I change behavior when I can't find out hash >>>> functor argument type. I am rather using the iterator key type and >>>> just hope that the user's functors are prepared for it. >>>> >>>> For now I am using functor argument_type which is deprecated. I >>>> just hope that the day we remove it we will have a compiler >>>> built-in to get any functor argument type given an input type. >>>> >>>> libstdc++: Limit allocation on iterator insertion in Hashtable >>>> [PR 96088] >>>> >>>> Detect Hash functor argument type to find out if it is >>>> different to the >>>> container key_type and if a temporary instance needs to be >>>> generated to invoke >>>> the functor from the iterator value_type key part. If this >>>> temporary generation >>>> can throw a key_type instance is generated at Hashtable level >>>> and use to call >>>> the functors and, if needed, move it to the storage. >>>> >>>> libstdc++-v3/ChangeLog: >>>> >>>> PR libstdc++/96088 >>>> * include/bits/hashtable_policy.h (_Select2nd): New. >>>> (_NodeBuilder<>): New. >>>> (_ReuseOrAllocNode<>::operator()): Use varriadic >>>> template args. >>>> (_AllocNode<>::operator()): Likewise. >>>> (_Hash_code_base<>::_M_hash_code): Add _KType template >>>> parameter. >>>> (_Hashtable_base<>::_M_equals): Add _KType template >>>> parameter. >>>> * include/bits/hashtable.h >>>> (_Hashtable<>::__node_builder_t): New. >>>> (_Hashtable<>::_M_find_before_node): Add _KType >>>> template parameter. >>>> (_Hashtable<>::_M_find_node): Likewise. >>>> (_Hashtable<>::_Hash_arg_t): New. >>>> (_Hashtable<>::_S_forward_key): New. >>>> (_Hashtable<>::_M_insert_unique<>(_KType&&, _Arg&&, const >>>> _NodeGenerator&)): >>>> New. >>>> (_Hashtable<>::_M_insert): Use latter. >>>> * 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 x86_64. >>>> >>>> Ok to commit ? >>>> >>>> François >>>> >>>> On 01/09/20 2:36 pm, François Dumont wrote: >>>>> Hi >>>>> >>>>> I started working on PR96088 problem in Hashtable implementation. >>>>> >>>>> In the case of multi-key containers the problem is easy to >>>>> manage. Now that we have _Scoped_node we can easily allocate the >>>>> node first and then extract the key from it to compute hash code. >>>>> It is quite safe as computating a hash code is rarely going to >>>>> throw especially if there is no allocation anymore to invoke the >>>>> hasher. >>>>> >>>>> In the unique-key case it is more tricky. First I only >>>>> consider the hasher invocation, the equal_to shall be consistent >>>>> with it. My approach is to consider that if the operation needed >>>>> transform the inserted element key part into the hasher argument >>>>> can throw then I better generate a key_type instance myself and >>>>> move it to the node if it is eventually to be inserted. Note that >>>>> any allocation needed to call the hasher from the key_type is user >>>>> fault. >>>>> >>>>> Of course the tricky part here is to find out what is the >>>>> hasher argument_type. For the moment I support hasher with a >>>>> nested argument_type typedef and function pointer. But, as pointed >>>>> out by the tests which are failing for the moment I am missing the >>>>> support for a classic functor. I am pretty sure that if I support >>>>> it I will still be missing some use cases (like std::function). So >>>>> I am looking for help on how to determine it. Or maybe the whole >>>>> approach it wrong ? >>>>> >>>>> For now I am still working on it, thanks, >>>>> >>>>> François >>>>> >>>> >>> >> > ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-05-06 20:03 ` François Dumont 2021-05-17 19:24 ` François Dumont @ 2021-05-20 16:44 ` Jonathan Wakely 2021-05-21 5:55 ` François Dumont 2021-05-24 9:31 ` François Dumont 1 sibling, 2 replies; 19+ messages in thread From: Jonathan Wakely @ 2021-05-20 16:44 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches 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. >@@ -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? 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? ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-05-20 16:44 ` Jonathan Wakely @ 2021-05-21 5:55 ` François Dumont 2021-05-21 6:48 ` Jonathan Wakely 2021-05-24 9:31 ` François Dumont 1 sibling, 1 reply; 19+ messages in thread From: François Dumont @ 2021-05-21 5:55 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches 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. > >> @@ -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. 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. Not if the conversion from _Kt to _Arg is noexcept. ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-05-21 5:55 ` François Dumont @ 2021-05-21 6:48 ` Jonathan Wakely 2021-05-21 6:55 ` Jonathan Wakely 0 siblings, 1 reply; 19+ messages in thread From: Jonathan Wakely @ 2021-05-21 6:48 UTC (permalink / raw) To: François Dumont; +Cc: Jonathan Wakely, libstdc++, gcc-patches On Fri, 21 May 2021, 07:31 François Dumont via Libstdc++, < libstdc++@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. > > ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-05-21 6:48 ` Jonathan Wakely @ 2021-05-21 6:55 ` Jonathan Wakely 2021-05-22 16:35 ` François Dumont 0 siblings, 1 reply; 19+ messages in thread From: Jonathan Wakely @ 2021-05-21 6:55 UTC (permalink / raw) To: François Dumont; +Cc: Jonathan Wakely, libstdc++, gcc-patches On Fri, 21 May 2021, 07:48 Jonathan Wakely, <jwakely.gcc@gmail.com> wrote: > > > On Fri, 21 May 2021, 07:31 François Dumont via Libstdc++, < > libstdc++@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. ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-05-21 6:55 ` Jonathan Wakely @ 2021-05-22 16:35 ` François Dumont 2021-05-24 11:19 ` Jonathan Wakely 2021-06-01 17:45 ` Jonathan Wakely 0 siblings, 2 replies; 19+ messages in thread From: François Dumont @ 2021-05-22 16:35 UTC (permalink / raw) To: Jonathan Wakely; +Cc: Jonathan Wakely, libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 8504 bytes --] 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.gcc@gmail.com > <mailto:jwakely.gcc@gmail.com>> wrote: > > > > On Fri, 21 May 2021, 07:31 François Dumont via Libstdc++, > <libstdc++@gcc.gnu.org <mailto:libstdc%2B%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. [-- Attachment #2: pr96088.patch --] [-- Type: text/x-patch, Size: 26711 bytes --] 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] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-05-22 16:35 ` François Dumont @ 2021-05-24 11:19 ` Jonathan Wakely 2021-06-01 17:45 ` Jonathan Wakely 1 sibling, 0 replies; 19+ messages in thread From: Jonathan Wakely @ 2021-05-24 11:19 UTC (permalink / raw) To: François Dumont; +Cc: Jonathan Wakely, libstdc++, gcc-patches On 22/05/21 18:35 +0200, François Dumont wrote: >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 ? OK for trunk, thanks. ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-05-22 16:35 ` François Dumont 2021-05-24 11:19 ` Jonathan Wakely @ 2021-06-01 17:45 ` Jonathan Wakely 2021-06-01 17:47 ` Jonathan Wakely 1 sibling, 1 reply; 19+ messages in thread From: Jonathan Wakely @ 2021-06-01 17:45 UTC (permalink / raw) To: François Dumont; +Cc: Jonathan Wakely, libstdc++, gcc-patches On 22/05/21 18:35 +0200, François Dumont wrote: >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> This is a c++11 test, but it uses <string_view>. The test fails for make check RUNTESTFLAGS=--target_board=unix/-std=gnu++11 I assume it should use { target c++17 } instead? ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-06-01 17:45 ` Jonathan Wakely @ 2021-06-01 17:47 ` Jonathan Wakely 2021-06-01 18:10 ` Jonathan Wakely 0 siblings, 1 reply; 19+ messages in thread From: Jonathan Wakely @ 2021-06-01 17:47 UTC (permalink / raw) To: François Dumont; +Cc: Jonathan Wakely, libstdc++, gcc-patches On 01/06/21 18:45 +0100, Jonathan Wakely wrote: >On 22/05/21 18:35 +0200, François Dumont wrote: >>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> > >This is a c++11 test, but it uses <string_view>. > >The test fails for make check RUNTESTFLAGS=--target_board=unix/-std=gnu++11 > >I assume it should use { target c++17 } instead? Same for 23_containers/unordered_map/96088.cc ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-06-01 17:47 ` Jonathan Wakely @ 2021-06-01 18:10 ` Jonathan Wakely 2021-06-01 20:00 ` François Dumont 2021-06-02 12:35 ` Jonathan Wakely 0 siblings, 2 replies; 19+ messages in thread From: Jonathan Wakely @ 2021-06-01 18:10 UTC (permalink / raw) To: François Dumont; +Cc: Jonathan Wakely, libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 1660 bytes --] On 01/06/21 18:47 +0100, Jonathan Wakely wrote: >On 01/06/21 18:45 +0100, Jonathan Wakely wrote: >>On 22/05/21 18:35 +0200, François Dumont wrote: >>>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> >> >>This is a c++11 test, but it uses <string_view>. >> >>The test fails for make check RUNTESTFLAGS=--target_board=unix/-std=gnu++11 >> >>I assume it should use { target c++17 } instead? > >Same for 23_containers/unordered_map/96088.cc I've pushed this fix. Tested x86_64-linux. [-- Attachment #2: patch.txt --] [-- Type: text/x-patch, Size: 1459 bytes --] commit 833d348aec154f231525ad2bf4c8a51c8d16b213 Author: Jonathan Wakely <jwakely@redhat.com> Date: Tue Jun 1 19:05:03 2021 libstdc++: Fix effective target for new tests [PR 96088] These tests use <string_view> so must not run for anything older than C++17. Signed-off-by: Jonathan Wakely <jwakely@redhat.com> libstdc++-v3/ChangeLog: * testsuite/23_containers/unordered_map/96088.cc: Change effective target to c++17. * testsuite/23_containers/unordered_set/96088.cc: Likewise. diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc index 062c8316a9e..e552b04f8c8 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc @@ -1,4 +1,4 @@ -// { dg-do run { target c++11 } } +// { dg-do run { target c++17 } } // Copyright (C) 2021 Free Software Foundation, Inc. // diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc index 53bb754dab6..efb2f9eb6b1 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc @@ -1,4 +1,4 @@ -// { dg-do run { target c++11 } } +// { dg-do run { target c++17 } } // Copyright (C) 2021 Free Software Foundation, Inc. // ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-06-01 18:10 ` Jonathan Wakely @ 2021-06-01 20:00 ` François Dumont 2021-06-02 12:35 ` Jonathan Wakely 1 sibling, 0 replies; 19+ messages in thread From: François Dumont @ 2021-06-01 20:00 UTC (permalink / raw) To: Jonathan Wakely; +Cc: Jonathan Wakely, libstdc++, gcc-patches On 01/06/21 8:10 pm, Jonathan Wakely wrote: > On 01/06/21 18:47 +0100, Jonathan Wakely wrote: >> On 01/06/21 18:45 +0100, Jonathan Wakely wrote: >>> On 22/05/21 18:35 +0200, François Dumont wrote: >>>> 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> >>> >>> This is a c++11 test, but it uses <string_view>. >>> >>> The test fails for make check >>> RUNTESTFLAGS=--target_board=unix/-std=gnu++11 >>> >>> I assume it should use { target c++17 } instead? >> >> Same for 23_containers/unordered_map/96088.cc > > I've pushed this fix. > > Tested x86_64-linux. > > I wonder why the same in unordered_multimap/unordered_multiset are not wrong too. Thanks ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-06-01 18:10 ` Jonathan Wakely 2021-06-01 20:00 ` François Dumont @ 2021-06-02 12:35 ` Jonathan Wakely 1 sibling, 0 replies; 19+ messages in thread From: Jonathan Wakely @ 2021-06-02 12:35 UTC (permalink / raw) To: François Dumont; +Cc: Jonathan Wakely, libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 1768 bytes --] On 01/06/21 19:10 +0100, Jonathan Wakely wrote: >On 01/06/21 18:47 +0100, Jonathan Wakely wrote: >>On 01/06/21 18:45 +0100, Jonathan Wakely wrote: >>>On 22/05/21 18:35 +0200, François Dumont wrote: >>>>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> >>> >>>This is a c++11 test, but it uses <string_view>. >>> >>>The test fails for make check RUNTESTFLAGS=--target_board=unix/-std=gnu++11 >>> >>>I assume it should use { target c++17 } instead? >> >>Same for 23_containers/unordered_map/96088.cc > >I've pushed this fix. And this one too. Tested x86_64-linux. [-- Attachment #2: patch.txt --] [-- Type: text/x-patch, Size: 4658 bytes --] commit 81eab204a56dcd8acb1ca5d7df277437ca07b51a Author: Jonathan Wakely <jwakely@redhat.com> Date: Wed Jun 2 12:33:38 2021 libstdc++: Fix tests for COW std::string [PR 96088] The expected number of allocations is different when copying COW strings. Signed-off-by: Jonathan Wakely <jwakely@redhat.com> libstdc++-v3/ChangeLog: PR libstdc++/96088 * testsuite/23_containers/unordered_map/96088.cc: Adjust expected number of allocations. * testsuite/23_containers/unordered_set/96088.cc: Likewise. diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc index e552b04f8c8..83ca1c0afd6 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc @@ -222,7 +222,8 @@ test03() std::vector<std::pair<std::string, int>> v; v.insert(v.end(), lst.begin(), lst.end()); - auto __offset = __gnu_test::counter::count(); + const auto origin = __gnu_test::counter::count(); + { __gnu_test::counter::reset(); std::unordered_map<std::string, int, @@ -231,15 +232,19 @@ test03() 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 ); + // Allocate array of buckets, a node, and the std::string (unless COW). + constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 3 : 2; + + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); 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 ); + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); } + VERIFY( __gnu_test::counter::count() == origin ); { __gnu_test::counter::reset(); @@ -250,8 +255,11 @@ test03() 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 ); + // Allocate array of buckets and a node. String is moved. + constexpr std::size_t increments = 2; + + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); } } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc index efb2f9eb6b1..83d5475c677 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc @@ -223,7 +223,8 @@ test03() std::vector<std::string> v; v.insert(v.end(), lst.begin(), lst.end()); - auto __offset = __gnu_test::counter::count(); + const auto origin = __gnu_test::counter::count(); + { __gnu_test::counter::reset(); std::unordered_set<std::string, @@ -232,15 +233,19 @@ test03() 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 ); + // Allocate array of buckets, a node, and the std::string (unless COW). + constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 3 : 2; + + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); 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 ); + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); } + VERIFY( __gnu_test::counter::count() == origin ); { __gnu_test::counter::reset(); @@ -251,8 +256,11 @@ test03() 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 ); + // Allocate array of buckets and a node. String is moved. + constexpr std::size_t increments = 2; + + VERIFY( __gnu_test::counter::count() == origin + increments ); + VERIFY( __gnu_test::counter::get()._M_increments == increments ); } } ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-05-20 16:44 ` Jonathan Wakely 2021-05-21 5:55 ` François Dumont @ 2021-05-24 9:31 ` François Dumont 2021-05-24 11:18 ` Jonathan Wakely 1 sibling, 1 reply; 19+ messages in thread From: François Dumont @ 2021-05-24 9:31 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches 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. > >> @@ -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. I forgot to say in my new proposal that I didn't find the __conditional_t. I can see a std::condition_t but only in C++14. Do you want to add a __conditional_t for C++11 ? ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [PATCH] Hashtable PR96088 2021-05-24 9:31 ` François Dumont @ 2021-05-24 11:18 ` Jonathan Wakely 0 siblings, 0 replies; 19+ messages in thread From: Jonathan Wakely @ 2021-05-24 11:18 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 24/05/21 11:31 +0200, François Dumont 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. >> >>>@@ -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. > >I forgot to say in my new proposal that I didn't find the >__conditional_t. I can see a std::condition_t but only in C++14. > >Do you want to add a __conditional_t for C++11 ? Doh, I forgot that's only in my fork not in the gcc.gnu.org repo. No need to add it, using typename conditional<>::type is fine here. ^ permalink raw reply [flat|nested] 19+ messages in thread
end of thread, other threads:[~2021-06-02 12:35 UTC | newest] Thread overview: 19+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-09-01 12:36 Hashtable PR96088 Work in Progress François Dumont 2020-10-17 16:21 ` [PATCH] Hashtable PR96088 François Dumont 2020-10-24 14:25 ` François Dumont 2020-12-04 9:10 ` François Dumont 2021-05-06 20:03 ` François Dumont 2021-05-17 19:24 ` François Dumont 2021-05-20 16:44 ` Jonathan Wakely 2021-05-21 5:55 ` François Dumont 2021-05-21 6:48 ` Jonathan Wakely 2021-05-21 6:55 ` Jonathan Wakely 2021-05-22 16:35 ` François Dumont 2021-05-24 11:19 ` Jonathan Wakely 2021-06-01 17:45 ` Jonathan Wakely 2021-06-01 17:47 ` Jonathan Wakely 2021-06-01 18:10 ` Jonathan Wakely 2021-06-01 20:00 ` François Dumont 2021-06-02 12:35 ` Jonathan Wakely 2021-05-24 9:31 ` François Dumont 2021-05-24 11: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).