aboutsummaryrefslogtreecommitdiff
path: root/libstdc++-v3/include/bits/hashtable.h
diff options
context:
space:
mode:
authorFrançois Dumont <fdumont@gcc.gnu.org>2020-08-25 21:31:23 +0200
committerFrançois Dumont <fdumont@gcc.gnu.org>2021-05-24 21:51:06 +0200
commit2c43f5ec9db163696de8691eb529df06c4999bcc (patch)
tree43b6f57544634afafbdca1e491e1b58f4c6bd89a /libstdc++-v3/include/bits/hashtable.h
parenta8764071f2eb6b4cdc9ecb788dfaa2b095b52598 (diff)
downloadgcc-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.h59
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;