diff options
author | François Dumont <fdumont@gcc.gnu.org> | 2020-08-25 21:31:23 +0200 |
---|---|---|
committer | François Dumont <fdumont@gcc.gnu.org> | 2021-05-24 21:51:06 +0200 |
commit | 2c43f5ec9db163696de8691eb529df06c4999bcc (patch) | |
tree | 43b6f57544634afafbdca1e491e1b58f4c6bd89a /libstdc++-v3/include/bits/hashtable.h | |
parent | a8764071f2eb6b4cdc9ecb788dfaa2b095b52598 (diff) | |
download | gcc-2c43f5ec9db163696de8691eb529df06c4999bcc.zip gcc-2c43f5ec9db163696de8691eb529df06c4999bcc.tar.gz gcc-2c43f5ec9db163696de8691eb529df06c4999bcc.tar.bz2 |
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.
Diffstat (limited to 'libstdc++-v3/include/bits/hashtable.h')
-rw-r--r-- | libstdc++-v3/include/bits/hashtable.h | 59 |
1 files changed, 46 insertions, 13 deletions
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 6711d08..4bdbe7d 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; |