* [PATCH] Extend usage of user hint in _Hashtable
@ 2021-11-28 21:27 François Dumont
0 siblings, 0 replies; only message in thread
From: François Dumont @ 2021-11-28 21:27 UTC (permalink / raw)
To: libstdc++; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 3285 bytes --]
libstdc++: In _Hashtable, use insertion hint as much as possible.
Make use in unordered containers of the user provided hint iterator
as much as possible.
Hint is now used:
- As a hint for allocation, in order to limit memory fragmentation when
allocator is making use of it.
- For unordered_set/unordered_map we check if it does not match the
key of the
element to insert, before computing the hash code.
- For unordered_multiset/unordered_multimap, if equals to the key
of the element
to insert, the hash code is taken from the hint so that we can take
advantage of
the potential hash code cache.
Moreover, in _M_count_tr and _M_equal_range_tr reuse the first
matching node key
to check for other matching nodes to avoid any temporary
instantiations.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h
(_NodeBuilder<>::_S_build): Add _NodePtr template
parameter.
(_ReuseOrAllocNode::operator()): Add __node_ptr parameter.
(_AllocNode::operator()): Likewise.
(_Insert_base::try_emplace): Adapt to use hint.
(_Hash_code_base<>::_M_hash_code(const
_Hash_node_value<>&)): New.
(_Hashtable_base<>::_M_equals<>(const _Kt&, const
_Hash_node_value<>&)): New.
(_Hashtable_base<>::_M_equals<>(const _Kt&, __hash_code,
const _Hash_node_value<>&)):
Adapt, use latter.
(_Hashtable_base<>::_M_equals_tr<>(const _Kt&, const
_Hash_node_value<>&)): New.
(_Hashtable_base<>::_M_equals_tr<>(const _Kt&, __hash_code,
const _Hash_node_value<>&)):
Adapt, use latter.
(_Hashtable_alloc<>::_M_allocate_node(__node_ptr, _Args&&...)): Add
__node_ptr parameter.
* include/bits/hashtable.h
(_Hashtable<>::_Scope_node<>(__hashtable_alloc*, __node_ptr, _Args&&...)):
Add __node_ptr parameter.
(_Hashtable<>::_M_get_node_hint(size_type, __node_ptr)): New.
(_Hashtable<>::_M_emplace_unique(const_iterator,
_Args&&...)): New.
(_Hashtable<>::_M_emplace_multi(const_iterator,
_Args&&...)): New.
(_Hashtable<>::_M_emplace()): Adapt to use latter.
(_Hashtable<>::_M_insert_unique(const_iterator, _Kt&&,
_Arg&&, const _NodeGenerator&)):
(_Hashtable<>::_M_reinsert_node(const_iterator,
node_type&&)): Add const_iterator.
Add const_iterator parameter.
* include/bits/unordered_map.h
(unordered_map<>::insert(node_type&&)): Pass cend as
hint.
(unordered_map<>::insert(const_iterator, node_type&&)):
Adapt to use hint.
* include/bits/unordered_set.h
(unordered_set<>::insert(node_type&&)): Pass cend as
hint.
(unordered_set<>::insert(const_iterator, node_type&&)):
Adapt to use hint.
Tested under Linux x86_64.
Ok to commit ?
François
[-- Attachment #2: hashtable_hint.patch --]
[-- Type: text/x-patch, Size: 22574 bytes --]
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 6e2d4c10cfe..5010cefcd77 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -301,9 +301,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Allocate a node and construct an element within it.
template<typename... _Args>
- _Scoped_node(__hashtable_alloc* __h, _Args&&... __args)
+ _Scoped_node(__hashtable_alloc* __h,
+ __node_ptr __hint, _Args&&... __args)
: _M_h(__h),
- _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...))
+ _M_node(__h->_M_allocate_node(__hint,
+ std::forward<_Args>(__args)...))
{ }
// Destroy element and deallocate node.
@@ -818,6 +820,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return nullptr;
}
+ // Gets a hint after which a node should be allocated given a bucket.
+ __node_ptr
+ _M_get_node_hint(size_type __bkt, __node_ptr __hint = nullptr) const
+ {
+ __node_base_ptr __node;
+ if (__node = _M_buckets[__bkt])
+ return __node != &_M_before_begin
+ ? static_cast<__node_ptr>(__node) : __hint;
+
+ return __hint;
+ }
+
// Insert a node at the beginning of a bucket.
void
_M_insert_bucket_begin(size_type, __node_ptr);
@@ -846,26 +860,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename... _Args>
std::pair<iterator, bool>
- _M_emplace(true_type __uks, _Args&&... __args);
+ _M_emplace_unique(const_iterator, _Args&&... __args);
template<typename... _Args>
iterator
- _M_emplace(false_type __uks, _Args&&... __args)
- { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); }
+ _M_emplace_multi(const_iterator, _Args&&... __args);
+
+ template<typename... _Args>
+ std::pair<iterator, bool>
+ _M_emplace(true_type /*__uks*/, _Args&&... __args)
+ { return _M_emplace_unique(cend(), std::forward<_Args>(__args)...); }
- // Emplace with hint, useless when keys are unique.
template<typename... _Args>
iterator
- _M_emplace(const_iterator, true_type __uks, _Args&&... __args)
- { return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
+ _M_emplace(false_type /*__uks*/, _Args&&... __args)
+ { return _M_emplace_multi(cend(), std::forward<_Args>(__args)...); }
template<typename... _Args>
iterator
- _M_emplace(const_iterator, false_type __uks, _Args&&... __args);
+ _M_emplace(const_iterator __hint, true_type /*__uks*/,
+ _Args&&... __args)
+ {
+ return _M_emplace_unique(__hint,
+ std::forward<_Args>(__args)...).first;
+ }
+
+ template<typename... _Args>
+ iterator
+ _M_emplace(const_iterator __hint, false_type /*__uks*/,
+ _Args&&... __args)
+ { return _M_emplace_multi(__hint, std::forward<_Args>(__args)...); }
template<typename _Kt, typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&);
+ _M_insert_unique(const_iterator, _Kt&&, _Arg&&, const _NodeGenerator&);
template<typename _Kt>
static __conditional_t<
@@ -888,7 +916,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
true_type /* __uks */)
{
- return _M_insert_unique(
+ return _M_insert_unique(cend(),
_S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
std::forward<_Arg>(__arg), __node_gen);
}
@@ -902,14 +930,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__uks);
}
- // Insert with hint, not used when keys are unique.
+ // Insert with hint when keys are unique.
template<typename _Arg, typename _NodeGenerator>
iterator
- _M_insert(const_iterator, _Arg&& __arg,
+ _M_insert(const_iterator __hint, _Arg&& __arg,
const _NodeGenerator& __node_gen, true_type __uks)
{
- return
- _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
+ return _M_insert_unique(__hint,
+ _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
+ std::forward<_Arg>(__arg), __node_gen).first;
}
// Insert with hint when keys are not unique.
@@ -973,7 +1002,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#if __cplusplus > 201402L
/// Re-insert an extracted node into a container with unique keys.
insert_return_type
- _M_reinsert_node(node_type&& __nh)
+ _M_reinsert_node(const_iterator __hint, node_type&& __nh)
{
insert_return_type __ret;
if (__nh.empty())
@@ -983,6 +1012,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_assert(get_allocator() == __nh.get_allocator());
const key_type& __k = __nh._M_key();
+ if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur))
+ {
+ __ret.node = std::move(__nh);
+ __ret.position = iterator(__hint._M_cur);
+ __ret.inserted = false;
+ }
+ else
+ {
__hash_code __code = this->_M_hash_code(__k);
size_type __bkt = _M_bucket_index(__code);
if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
@@ -999,6 +1036,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__ret.inserted = true;
}
}
+ }
return __ret;
}
@@ -1012,7 +1050,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_assert(get_allocator() == __nh.get_allocator());
const key_type& __k = __nh._M_key();
- auto __code = this->_M_hash_code(__k);
+ __hash_code __code;
+ if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur))
+ __code = this->_M_hash_code(*__hint._M_cur);
+ else
+ __code = this->_M_hash_code(__k);
auto __ret
= _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
__nh._M_ptr = nullptr;
@@ -1105,8 +1147,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
{
auto __pos = __i++;
- __hash_code __code
- = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
+ const key_type& __k = _ExtractKey{}(*__pos);
+ __hash_code __code;
+ if (__hint && this->_M_equals(__k, *__hint))
+ __code = this->_M_hash_code(*__hint);
+ else
+ __code = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
auto __nh = __src.extract(__pos);
__hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
__nh._M_ptr = nullptr;
@@ -1332,7 +1378,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// _M_before_begin.
__node_ptr __ht_n = __ht._M_begin();
__node_ptr __this_n
- = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
+ = __node_gen(nullptr, __fwd_value_for<_Ht>(__ht_n->_M_v()));
this->_M_copy_code(*__this_n, *__ht_n);
_M_update_bbegin(__this_n);
@@ -1340,7 +1386,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__node_ptr __prev_n = __this_n;
for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
{
- __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
+ __this_n
+ = __node_gen(__prev_n, __fwd_value_for<_Ht>(__ht_n->_M_v()));
__prev_n->_M_nxt = __this_n;
this->_M_copy_code(*__this_n, *__ht_n);
size_type __bkt = _M_bucket_index(*__this_n);
@@ -1732,10 +1779,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// All equivalent values are next to each other, if we find a
// non-equivalent value after an equivalent one it means that we won't
// find any new equivalent value.
+ const key_type& __nk = _ExtractKey{}(__n->_M_v());
iterator __it(__n);
size_type __result = 1;
for (++__it;
- __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
+ __it._M_cur && this->_M_equals(__nk, __code, *__it._M_cur);
++__it)
++__result;
@@ -1819,8 +1867,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// All equivalent values are next to each other, if we find a
// non-equivalent value after an equivalent one it means that we won't
// find any new equivalent value.
+ const key_type& __nk = _ExtractKey{}(__n->_M_v());
auto __beg = __ite++;
- while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
+ while (__ite._M_cur && this->_M_equals(__nk, __code, *__ite._M_cur))
++__ite;
return { __beg, __ite };
@@ -1847,8 +1896,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// All equivalent values are next to each other, if we find a
// non-equivalent value after an equivalent one it means that we won't
// find any new equivalent value.
+ const key_type& __nk = _ExtractKey{}(__n->_M_v());
auto __beg = __ite++;
- while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
+ while (__ite._M_cur && this->_M_equals(__nk, __code, *__ite._M_cur))
++__ite;
return { __beg, __ite };
@@ -1997,17 +2047,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_emplace(true_type /* __uks */, _Args&&... __args)
+ _M_emplace_unique(const_iterator __hint, _Args&&... __args)
-> pair<iterator, bool>
{
// First build the node to get access to the hash code
- _Scoped_node __node { this, std::forward<_Args>(__args)... };
+ _Scoped_node __node { this, __hint._M_cur, std::forward<_Args>(__args)... };
const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
+ if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur))
+ return { iterator(__hint._M_cur), false };
+
__hash_code __code = this->_M_hash_code(__k);
size_type __bkt = _M_bucket_index(__code);
if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
// There is already an equivalent node, no insertion
- return std::make_pair(iterator(__p), false);
+ return { iterator(__p), false };
// Insert the node
auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
@@ -2023,15 +2076,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_emplace(const_iterator __hint, false_type /* __uks */,
- _Args&&... __args)
+ _M_emplace_multi(const_iterator __hint, _Args&&... __args)
-> iterator
{
// First build the node to get its hash code.
- _Scoped_node __node { this, std::forward<_Args>(__args)... };
+ _Scoped_node __node
+ { this, __hint._M_cur, std::forward<_Args>(__args)... };
+
const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
+ __hash_code __code;
+ if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur))
+ __code = this->_M_hash_code(*__hint._M_cur);
+ else
+ __code = this->_M_hash_code(__k);
- __hash_code __code = this->_M_hash_code(__k);
auto __pos
= _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
__node._M_node = nullptr;
@@ -2132,10 +2190,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert_unique(_Kt&& __k, _Arg&& __v,
+ _M_insert_unique(const_iterator __hint,
+ _Kt&& __k, _Arg&& __v,
const _NodeGenerator& __node_gen)
-> pair<iterator, bool>
{
+ if (__hint._M_cur && this->_M_equals_tr(__k, *__hint._M_cur))
+ return { iterator(__hint._M_cur), false };
+
__hash_code __code = this->_M_hash_code_tr(__k);
size_type __bkt = _M_bucket_index(__code);
@@ -2143,11 +2205,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return { iterator(__node), false };
_Scoped_node __node {
- __node_builder_t::_S_build(std::forward<_Kt>(__k),
+ __node_builder_t::_S_build(_M_get_node_hint(__bkt, __hint._M_cur),
+ 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;
@@ -2169,11 +2233,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
-> iterator
{
// First allocate new node so that we don't do anything if it throws.
- _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
+ _Scoped_node __node
+ { __node_gen(__hint._M_cur, 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()));
+ const auto& __k = _ExtractKey{}(__node._M_node->_M_v());
+ __hash_code __code;
+ if (__hint._M_cur && this->_M_equals(__k, *__hint._M_cur))
+ __code = this->_M_hash_code(*__hint._M_cur);
+ else
+ __code = this->_M_hash_code(__k);
auto __pos
= _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 0b5443fc187..7b9e0476159 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -115,12 +115,14 @@ namespace __detail
template<>
struct _NodeBuilder<_Select1st>
{
- template<typename _Kt, typename _Arg, typename _NodeGenerator>
- static auto
- _S_build(_Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen)
- -> typename _NodeGenerator::__node_type*
- {
- return __node_gen(std::forward<_Kt>(__k),
+ template<typename _NodePtr,
+ typename _Kt, typename _Arg, typename _NodeGenerator>
+ static _NodePtr
+ _S_build(_NodePtr __hint,
+ _Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen)
+ {
+ return __node_gen(__hint,
+ std::forward<_Kt>(__k),
std::forward<_Arg>(__arg).second);
}
};
@@ -128,11 +130,12 @@ namespace __detail
template<>
struct _NodeBuilder<_Identity>
{
- template<typename _Kt, typename _Arg, typename _NodeGenerator>
- static auto
- _S_build(_Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen)
- -> typename _NodeGenerator::__node_type*
- { return __node_gen(std::forward<_Kt>(__k)); }
+ template<typename _NodePtr,
+ typename _Kt, typename _Arg, typename _NodeGenerator>
+ static _NodePtr
+ _S_build(_NodePtr __hint,
+ _Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen)
+ { return __node_gen(__hint, std::forward<_Kt>(__k)); }
};
template<typename _NodeAlloc>
@@ -150,22 +153,23 @@ namespace __detail
typename __hashtable_alloc::__node_alloc_traits;
public:
- using __node_type = typename __hashtable_alloc::__node_type;
+ using __node_ptr = typename __hashtable_alloc::__node_ptr;
- _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
+ _ReuseOrAllocNode(__node_ptr __nodes, __hashtable_alloc& __h)
: _M_nodes(__nodes), _M_h(__h) { }
+
_ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
~_ReuseOrAllocNode()
{ _M_h._M_deallocate_nodes(_M_nodes); }
template<typename... _Args>
- __node_type*
- operator()(_Args&&... __args) const
+ __node_ptr
+ operator()(__node_ptr __hint, _Args&&... __args) const
{
if (_M_nodes)
{
- __node_type* __node = _M_nodes;
+ __node_ptr __node = _M_nodes;
_M_nodes = _M_nodes->_M_next();
__node->_M_nxt = nullptr;
auto& __a = _M_h._M_node_allocator();
@@ -180,13 +184,15 @@ namespace __detail
_M_h._M_deallocate_node_ptr(__node);
__throw_exception_again;
}
+
return __node;
}
- return _M_h._M_allocate_node(std::forward<_Args>(__args)...);
+
+ return _M_h._M_allocate_node(__hint, std::forward<_Args>(__args)...);
}
private:
- mutable __node_type* _M_nodes;
+ mutable __node_ptr _M_nodes;
__hashtable_alloc& _M_h;
};
@@ -199,15 +205,15 @@ namespace __detail
using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
public:
- using __node_type = typename __hashtable_alloc::__node_type;
+ using __node_ptr = typename __hashtable_alloc::__node_ptr;
_AllocNode(__hashtable_alloc& __h)
: _M_h(__h) { }
template<typename... _Args>
- __node_type*
- operator()(_Args&&... __args) const
- { return _M_h._M_allocate_node(std::forward<_Args>(__args)...); }
+ __node_ptr
+ operator()(__node_ptr __hint, _Args&&... __args) const
+ { return _M_h._M_allocate_node(__hint, std::forward<_Args>(__args)...); }
private:
__hashtable_alloc& _M_h;
@@ -761,6 +767,7 @@ namespace __detail
typename __hashtable::_Scoped_node __node {
__h,
+ __h->_M_get_node_hint(__bkt),
std::piecewise_construct,
std::tuple<const key_type&>(__k),
std::tuple<>()
@@ -788,6 +795,7 @@ namespace __detail
typename __hashtable::_Scoped_node __node {
__h,
+ __h->_M_get_node_hint(__bkt),
std::piecewise_construct,
std::forward_as_tuple(std::move(__k)),
std::tuple<>()
@@ -876,7 +884,7 @@ namespace __detail
template<typename _KType, typename... _Args>
std::pair<iterator, bool>
- try_emplace(const_iterator, _KType&& __k, _Args&&... __args)
+ try_emplace(const_iterator __hint, _KType&& __k, _Args&&... __args)
{
__hashtable& __h = _M_conjure_hashtable();
auto __code = __h._M_hash_code(__k);
@@ -885,7 +893,7 @@ namespace __detail
return { iterator(__node), false };
typename __hashtable::_Scoped_node __node {
- &__h,
+ &__h, __hint._M_cur,
std::piecewise_construct,
std::forward_as_tuple(std::forward<_KType>(__k)),
std::forward_as_tuple(std::forward<_Args>(__args)...)
@@ -1250,6 +1258,14 @@ namespace __detail
return _M_hash()(__k);
}
+ __hash_code
+ _M_hash_code(const _Hash_node_value<_Value, true>& __n) const
+ { return __n._M_hash_code; }
+
+ __hash_code
+ _M_hash_code(const _Hash_node_value<_Value, false>& __n) const
+ { return _M_hash_code(_ExtractKey{}(__n._M_v())); }
+
__hash_code
_M_hash_code(const _Hash&,
const _Hash_node_value<_Value, true>& __n) const
@@ -1641,18 +1657,23 @@ namespace __detail
{ }
bool
- _M_equals(const _Key& __k, __hash_code __c,
+ _M_equals(const _Key& __k,
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()));
+ return _M_eq()(__k, _ExtractKey{}(__n._M_v()));
}
+ bool
+ _M_equals(const _Key& __k, __hash_code __c,
+ const _Hash_node_value<_Value, __hash_cached::value>& __n) const
+ { return _S_equals(__c, __n) && _M_equals(__k, __n); }
+
template<typename _Kt>
bool
- _M_equals_tr(const _Kt& __k, __hash_code __c,
+ _M_equals_tr(const _Kt& __k,
const _Hash_node_value<_Value,
__hash_cached::value>& __n) const
{
@@ -1660,9 +1681,16 @@ namespace __detail
__is_invocable<const _Equal&, const _Kt&, 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()));
+ return _M_eq()(__k, _ExtractKey{}(__n._M_v()));
}
+ template<typename _Kt>
+ bool
+ _M_equals_tr(const _Kt& __k, __hash_code __c,
+ const _Hash_node_value<_Value,
+ __hash_cached::value>& __n) const
+ { return _S_equals(__c, __n) && _M_equals_tr(__k, __n); }
+
bool
_M_node_equals(
const _Hash_node_value<_Value, __hash_cached::value>& __lhn,
@@ -1880,7 +1908,7 @@ namespace __detail
// Allocate a node and construct an element within it.
template<typename... _Args>
__node_ptr
- _M_allocate_node(_Args&&... __args);
+ _M_allocate_node(__node_ptr __hint, _Args&&... __args);
// Destroy the element within a node and deallocate the node.
void
@@ -1907,22 +1935,32 @@ namespace __detail
template<typename _NodeAlloc>
template<typename... _Args>
auto
- _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
+ _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(__node_ptr __hint,
+ _Args&&... __args)
-> __node_ptr
{
- auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
+ auto& __alloc = _M_node_allocator();
+ typename __node_alloc_traits::pointer __nptr;
+ if (__hint)
+ {
+ typedef typename __node_alloc_traits::const_pointer _CPtr;
+ auto __hptr = std::pointer_traits<_CPtr>::pointer_to(*__hint);
+ __nptr = __node_alloc_traits::allocate(__alloc, 1, __hptr);
+ }
+ else
+ __nptr = __node_alloc_traits::allocate(__alloc, 1);
+
__node_ptr __n = std::__to_address(__nptr);
__try
{
::new ((void*)__n) __node_type;
- __node_alloc_traits::construct(_M_node_allocator(),
- __n->_M_valptr(),
+ __node_alloc_traits::construct(__alloc, __n->_M_valptr(),
std::forward<_Args>(__args)...);
return __n;
}
__catch(...)
{
- __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
+ __node_alloc_traits::deallocate(__alloc, __nptr, 1);
__throw_exception_again;
}
}
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index 2261e6685ea..9f621cdbaeb 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -436,12 +436,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)); }
+ { return _M_h._M_reinsert_node(cend(), std::move(__nh)); }
/// Re-insert an extracted node.
iterator
- insert(const_iterator, node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+ insert(const_iterator __hint, node_type&& __nh)
+ { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
#define __cpp_lib_unordered_map_try_emplace 201411
/**
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index ac4a890d25a..10d81905acb 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -497,12 +497,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)); }
+ { return _M_h._M_reinsert_node(cend(), std::move(__nh)); }
/// Re-insert an extracted node.
iterator
- insert(const_iterator, node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+ insert(const_iterator __hint, node_type&& __nh)
+ { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
#endif // C++17
///@{
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2021-11-28 21:27 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-11-28 21:27 [PATCH] Extend usage of user hint in _Hashtable François Dumont
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).