Here is a new version of this patch.
The previous one had some flaws that were unnoticed by testsuite tests,
only the performance tests were spotting it. So I'm adding checks on the
consistency of the unordered containers in this patch.
I also forget to signal that after this patch gnu versioned namespace
version is supposed to be bump. But I hope it's already the plan because
of the move to the cxx11 abi in this mode.
Note for reviewer, after application of the patch, a 'git diff -b' is
much more readable.
And some benches results:
before:
unordered_set_range_insert.cc-thread hash code NOT cached 2 X 1000000
inserts individually 19999990 calls 44r 44u 0s 95999760mem 0pf
unordered_set_range_insert.cc-thread hash code NOT cached 2 X 1000000
inserts in range 20000000 calls 43r 43u 0s 95999760mem 0pf
unordered_set_range_insert.cc-thread hash code NOT cached 1000000 X
inserts individually 19999990 calls 44r 44u 0s 95999760mem 0pf
unordered_set_range_insert.cc-thread hash code NOT cached 1000000 X
inserts in range 20000000 calls 43r 43u 0s 95999760mem 0pf
unordered_set_range_insert.cc-thread hash code cached 2 X 1000000
inserts individually 10000000 calls 30r 30u 0s 111999328mem
0pf
unordered_set_range_insert.cc-thread hash code cached 2 X 1000000
inserts in range 10000010 calls 33r 32u 0s 111999328mem 0pf
unordered_set_range_insert.cc-thread hash code cached 1000000 X
inserts individually 10000000 calls 30r 31u 0s 111999328mem
0pf
unordered_set_range_insert.cc-thread hash code cached 1000000 X
inserts in range 10000010 calls 32r 32u 0s 111999328mem 0pf
after:
unordered_set_range_insert.cc-thread hash code NOT cached 2 X 1000000
inserts individually 19999990 calls 44r 44u 0s 95999760mem 0pf
unordered_set_range_insert.cc-thread hash code NOT cached 2 X 1000000
inserts in range 10000020 calls 26r 25u 0s 95999760mem 0pf
unordered_set_range_insert.cc-thread hash code NOT cached 1000000 X
inserts individually 19999990 calls 43r 44u 0s 95999760mem 0pf
unordered_set_range_insert.cc-thread hash code NOT cached 1000000 X
inserts in range 10000020 calls 26r 26u 0s 95999760mem 0pf
unordered_set_range_insert.cc-thread hash code cached 2 X 1000000
inserts individually 10000000 calls 35r 35u 0s 111999328mem
0pf
unordered_set_range_insert.cc-thread hash code cached 2 X 1000000
inserts in range 10000010 calls 32r 33u 0s 111999328mem 0pf
unordered_set_range_insert.cc-thread hash code cached 1000000 X
inserts individually 10000000 calls 31r 32u 0s 111999328mem
0pf
unordered_set_range_insert.cc-thread hash code cached 1000000 X
inserts in range 10000010 calls 31r 31u 0s 111999328mem 0pf
libstdc++: [_Hashtable] Prefer to insert after last node
When inserting an element into an empty bucket we currently insert
the new node
after the before-begin node so in first position. The drawback of
doing this is
that we are forced to update the bucket that was containing this
before-begin
node to point to the newly inserted node. To do so we need at best
to do a modulo
to find this bucket and at worst, when hash code is not cached,
also compute it.
To avoid this side effect it is better to insert after the last
node. To do so
we are introducing a helper type _HintPolicy that has 3
resposibilities.
1. When the gnu versioned namespace is used we add a _M_last member
to _Hashtable,
_HintPolicy is then in charge of maintaining it. For this purpose
_HintPolicy is
using the RAII pattern, it resets the _M_last at destruction level.
It also maintain
its own _M_last, all mutable operations are updating it when needed.
2. When the gnu versioned namespace is not used _HintPolicy will
still maintain its
_M_last member using initially the user provided hint if any and if
it is actually
the container last node that is to say a dereferenceable node with
its next node being
null. All mutable operations can also update the contextual
_HintPolicy instance
whenever they detect the last node during their process.
3. As long as we haven't been able to detect the container last
node, _HintPolicy
is used to keep a cache of the before-begin bucket index so that we
do not need to
compute it afterward for example in the context of range insertion.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h
[_GLIBCXX_INLINE_VERSION](_Hashtable<>::_M_last): New, the container
last node.
(_Hashtable<>::_LastNodeManager): New.
(_Hashtable<>::_M_get_last(__node_ptr)): New.
(_Hashtable<>::_M_get_last_node_mgr(__node_ptr)): New.
(_Hashtable<>::_M_check_for_last(__node_base_ptr)): New.
(_Hashtable<>::_M_set_last(__node_ptr)): New.
(_Hashtable<>::_M_compute_hash_code(__node_ptr, const
key_type&)): Remove.
(_Hashtable<>::operator=(initializer_list<>)): Adapt to instantiate a
_HintPolicy.
(_Hashtable<>::_M_insert_bucket_begin): Add _HintPolicy&
parameter and use it
to optimize insertion in an empty bucket.
(_Hashtable<>::_M_insert_unique_node): Add _HintPolicy&
parameter.
(_Hashtable<>::_M_insert_multi_node(__node_ptr,
__hash_code, __node_ptr)): Replace by...
(_Hashtable<>::_M_insert_multi_node(_HintPolicy&, const key_type&,
__node_ptr, __node_ptr)): ... this.
(_Hashtable<>::_M_emplace_unique(_HintPolicy&, _Args&&...)): New.
(_Hashtable<>::_M_emplace_multi(_HintPolicy&, _Args&&...)): New.
(_Hashtable<>::_M_emplace): Adapt to use latters.
(_Hashtable<>::_M_insert_unique): Add _HintPolicy& parameter.
(_Hashtable<>::_M_insert_unique_aux): Add _HintPolicy&
parameter.
(_Hashtable<>::_M_insert): Adapt to use latter.
(_Hashtable<>::emplace_hint(const_iterator, _Args&&...)):
Adapt.
(_hashtable<>::rehash(size_type)): Adapt.
(_Hashtable<>::_M_reinsert_node(const_iterator, node_type&&)):
Add hint parameter, adapt to use it for _HintPolicy
instantiation.
(_Hashtable<>::_M_reinsert_node_multi): Likewise.
(_Hashtable<>::_M_merge_unique): Adapt.
(_Hashtable<>::_M_rehash): Add _HintPolicy& parameter.
(_Hashtable<>::_Hashtable<_InputIte>()): Adapt.
(_Hashtable<>::_M_assign): Call _M_set_last.
(_Hashtable<>::_M_reset()): Reset _M_last.
(_Hashtable<>::_M_move_assign(_Hashtable&&, true_type)): Move _M_last.
(_Hashtable<>(_Hashtable&&, __node_alloc_type&&,
true_type)): Copy _M_last.
(_Hashtable<>(_Hashtable&&, __node_alloc_type&&,
false_type)): Copy _M_last.
(_Hashtable<>::_M_insert_range): Adapt.
(_Hashtable<>::_M_erase): Call _M_check_for_last.
(_Hashtable<>::erase): Likewise.
* include/bits/hashtable_policy.h:
(_Map_base<>::operator[](const key_type&)): Use hint policy.
(_Map_base<>::operator[](key_type&&)): Likewise.
(_Insert_base<>::insert(const_iterator, const
value_type&)): Likewise using hint.
(_Insert_base<>::try_emplace): Likewise.
(_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, true_type)):
Use hint policy.
(_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, false_type)):
Use hint policy.
(_Insert<>::insert(const_iterator, value_type&&)): Likewise.
* 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.
*
testsuite/23_containers/unordered_multimap/insert/hint.cc: Adapt
implementation
specific tests.
*
testsuite/23_containers/unordered_map/consistency_check.cc: New test case.
*
testsuite/23_containers/unordered_multimap/consistency_check.cc: New
test case.
*
testsuite/23_containers/unordered_multiset/consistency_check.cc: New
test case.
*
testsuite/23_containers/unordered_set/consistency_check.cc: New test case.
* testsuite/libstdc++-prettyprinters/cxx11.cc (main): Adapt
expectations on element
order in unordered_map instance.
diff --git a/libstdc++-v3/include/bits/hashtable.h
b/libstdc++-v3/include/bits/hashtable.h
index aec77c34a58..f92ff196679 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -403,6 +403,59 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// numerous checks in the code to avoid 0 modulus.
__node_base_ptr _M_single_bucket = nullptr;
+#if _GLIBCXX_INLINE_VERSION
+ // The last container node to optimize insertion in empty buckets.
+ __node_ptr _M_last = nullptr;
+#endif
+
+ class _LastNodeManager
+ {
+ _Hashtable& _M_htb;
+ __node_ptr _M_last;
+ std::size_t _M_bbegin_index;
+ bool _M_initialized = false;
+
+ public:
+ _LastNodeManager(_Hashtable& __htbl, __node_ptr __last)
+ : _M_htb(__htbl), _M_last(__last)
+ { }
+
+#if _GLIBCXX_INLINE_VERSION
+ ~_LastNodeManager()
+ { _M_htb._M_last = _M_last; }
+#endif
+
+ void
+ _M_reset()
+ {
+ _M_last = nullptr;
+ _M_initialized = false;
+ }
+
+ std::size_t
+ _M_get_bbegin_bkt(__node_ptr __n) const
+ {
+ if (!_M_initialized)
+ return _M_htb._M_bucket_index(*__n);
+ return _M_bbegin_index;
+ }
+
+ void
+ _M_store_bbegin_bkt(std::size_t __bkt)
+ {
+ _M_bbegin_index = __bkt;
+ _M_initialized = true;
+ }
+
+ constexpr __node_ptr
+ _M_get()
+ { return _M_last; }
+
+ void
+ _M_set(__node_ptr __n)
+ { _M_last = __n; }
+ };
+
void
_M_update_bbegin()
{
@@ -425,6 +478,41 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_uses_single_bucket() const
{ return _M_uses_single_bucket(_M_buckets); }
+ __node_ptr
+ _M_get_last([[maybe_unused]] __node_ptr __usr_hint = nullptr) const
+ {
+#if _GLIBCXX_INLINE_VERSION
+ return _M_last;
+#else
+ return __usr_hint && !__usr_hint->_M_nxt ? __usr_hint : nullptr;
+#endif
+ }
+
+ _LastNodeManager
+ _M_get_last_node_mgr(__node_ptr __usr_hint = nullptr)
+ { return _LastNodeManager(*this, _M_get_last(__usr_hint)); }
+
+ void
+ _M_check_for_last([[maybe_unused]] __node_base_ptr __prev_n)
+ {
+#if _GLIBCXX_INLINE_VERSION
+ if (!__prev_n->_M_nxt)
+ {
+ _M_last = __prev_n == &_M_before_begin
+ ? nullptr
+ : static_cast<__node_ptr>(__prev_n);
+ }
+#endif
+ }
+
+ void
+ _M_set_last([[maybe_unused]] __node_ptr __n)
+ {
+#if _GLIBCXX_INLINE_VERSION
+ _M_last = __n;
+#endif
+ }
+
static constexpr size_t
__small_size_threshold() noexcept
{
@@ -612,11 +700,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// We consider that all elements of __l are going to be inserted.
auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
+ auto __last_mgr = _M_get_last_node_mgr();
+
// Do not shrink to keep potential user reservation.
if (_M_bucket_count < __l_bkt_count)
- rehash(__l_bkt_count);
+ _M_rehash(__last_mgr, __l_bkt_count);
- _M_insert_range(__l.begin(), __l.end(), __roan);
+ _M_insert_range(__l.begin(), __l.end(), __last_mgr, __roan);
return *this;
}
@@ -837,31 +927,61 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
// Insert a node at the beginning of a bucket.
- void
- _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
+ static void
+ _S_insert_bucket_begin(_LastNodeManager& __last_mgr,
+ __node_base_ptr __bbegin_n, __buckets_ptr
__buckets,
+ size_type __bkt, __node_ptr __node)
{
- if (_M_buckets[__bkt])
+ __node_base_ptr __prev;
+ if (__buckets[__bkt])
{
// Bucket is not empty, we just need to insert the new node
// after the bucket before begin.
- __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
- _M_buckets[__bkt]->_M_nxt = __node;
+ __prev = __buckets[__bkt];
}
else
{
- // The bucket is empty, the new node is inserted at the
- // beginning of the singly-linked list and the bucket will
- // contain _M_before_begin pointer.
- __node->_M_nxt = _M_before_begin._M_nxt;
- _M_before_begin._M_nxt = __node;
-
- if (__node->_M_nxt)
- // We must update former begin bucket that is pointing to
- // _M_before_begin.
- _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
-
- _M_buckets[__bkt] = &_M_before_begin;
+ // If we have the last container node, insert after it.
+ __node_ptr __last = __last_mgr._M_get();
+ if (__last)
+ {
+ __prev = __last;
+ __last_mgr._M_set(__node);
+ }
+ else
+ {
+ // The bucket is empty, the new node is inserted at the
+ // beginning of the singly-linked list and the bucket will
+ // contain the before begin node.
+ __prev = __bbegin_n;
+
+ if (__prev->_M_nxt)
+ {
+ // We must update former begin bucket that is pointing to
+ // _M_before_begin.
+ size_type __bb_bkt = __last_mgr._M_get_bbegin_bkt(
+ static_cast<__node_ptr>(__prev->_M_nxt));
+ __buckets[__bb_bkt] = __node;
+ }
+ else
+ __last_mgr._M_set(__node);
+
+ __last_mgr._M_store_bbegin_bkt(__bkt);
+ }
+
+ __buckets[__bkt] = __prev;
}
+
+ __node->_M_nxt = __prev->_M_nxt;
+ __prev->_M_nxt = __node;
+ }
+
+ void
+ _M_insert_bucket_begin(_LastNodeManager& __last_mgr,
+ size_type __bkt, __node_ptr __node)
+ {
+ _S_insert_bucket_begin(__last_mgr, &_M_before_begin, _M_buckets,
+ __bkt, __node);
}
// Remove the bucket first node
@@ -887,44 +1007,62 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__node_base_ptr
_M_get_previous_node(size_type __bkt, __node_ptr __n);
- pair<__node_ptr, __hash_code>
- _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const;
-
// Insert node __n with hash code __code, in bucket __bkt if no
// rehash (assumes no element with same key already present).
// Takes ownership of __n if insertion succeeds, throws otherwise.
iterator
- _M_insert_unique_node(size_type __bkt, __hash_code,
+ _M_insert_unique_node(_LastNodeManager& __last_mgr,
+ size_type __bkt, __hash_code,
__node_ptr __n, size_type __n_elt = 1);
- // Insert node __n with key __k and hash code __code.
+ // Insert node __n after __prev if any.
// Takes ownership of __n if insertion succeeds, throws otherwise.
iterator
- _M_insert_multi_node(__node_ptr __hint,
- __hash_code __code, __node_ptr __n);
+ _M_insert_multi_node(_LastNodeManager& __last_mgr, const key_type& __k,
+ __node_ptr __n, __node_ptr __hash_code_n = nullptr);
template<typename... _Args>
std::pair<iterator, bool>
- _M_emplace(true_type __uks, _Args&&... __args);
+ _M_emplace_unique(_LastNodeManager&, _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(_LastNodeManager&, _Args&&... __args);
+
+ template<typename... _Args>
+ std::pair<iterator, bool>
+ _M_emplace(true_type /*__uks*/, _Args&&... __args)
+ {
+ auto __last_mgr = _M_get_last_node_mgr();
+ return _M_emplace_unique(__last_mgr, std::forward<_Args>(__args)...);
+ }
+
+ template<typename... _Args>
+ iterator
+ _M_emplace(false_type /*__uks*/, _Args&&... __args)
+ {
+ auto __last_mgr = _M_get_last_node_mgr();
+ return _M_emplace_multi(__last_mgr, 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(_LastNodeManager& __last_mgr,
+ true_type /*__uks*/, _Args&&... __args)
+ {
+ return _M_emplace_unique(__last_mgr,
+ std::forward<_Args>(__args)...).first;
+ }
template<typename... _Args>
iterator
- _M_emplace(const_iterator, false_type __uks, _Args&&... __args);
+ _M_emplace(_LastNodeManager& __last_mgr,
+ false_type /*__uks*/, _Args&&... __args)
+ { return _M_emplace_multi(__last_mgr, std::forward<_Args>(__args)...); }
template<typename _Kt, typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
+ _M_insert_unique(_LastNodeManager&, _Kt&&, _Arg&&, _NodeGenerator&);
template<typename _Kt>
static __conditional_t<
@@ -944,9 +1082,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen)
+ _M_insert_unique_aux(_LastNodeManager& __last_mgr,
+ _Arg&& __arg, _NodeGenerator& __node_gen)
{
- return _M_insert_unique(
+ return _M_insert_unique(__last_mgr,
_S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
std::forward<_Arg>(__arg), __node_gen);
}
@@ -956,9 +1095,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
true_type /* __uks */)
{
+ auto __last_mgr = _M_get_last_node_mgr();
using __to_value
= __detail::_ConvertToValueType<_ExtractKey, value_type>;
- return _M_insert_unique_aux(
+ return _M_insert_unique_aux(__last_mgr,
__to_value{}(std::forward<_Arg>(__arg)), __node_gen);
}
@@ -967,32 +1107,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
false_type __uks)
{
+ auto __last_mgr = _M_get_last_node_mgr();
using __to_value
= __detail::_ConvertToValueType<_ExtractKey, value_type>;
- return _M_insert(cend(),
+ return _M_insert(__last_mgr,
__to_value{}(std::forward<_Arg>(__arg)), __node_gen, __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,
- _NodeGenerator& __node_gen, true_type __uks)
+ _M_insert(_LastNodeManager& __last_mgr, _Arg&& __arg,
+ _NodeGenerator& __node_gen, true_type /* __uks */)
{
- return
- _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
+ using __to_value
+ = __detail::_ConvertToValueType<_ExtractKey, value_type>;
+ return _M_insert_unique_aux(__last_mgr,
+ __to_value{}(std::forward<_Arg>(__arg)), __node_gen).first;
}
// Insert with hint when keys are not unique.
template<typename _Arg, typename _NodeGenerator>
iterator
- _M_insert(const_iterator, _Arg&&,
+ _M_insert(_LastNodeManager& __last_mgr, _Arg&& __arg,
_NodeGenerator&, false_type __uks);
template<typename _InputIterator, typename _NodeGenerator>
void
_M_insert_range(_InputIterator __first, _InputIterator __last,
- _NodeGenerator&);
+ _LastNodeManager&, _NodeGenerator&);
size_type
_M_erase(true_type __uks, const key_type&);
@@ -1014,7 +1157,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
emplace_hint(const_iterator __hint, _Args&&... __args)
{
- return _M_emplace(__hint, __unique_keys{},
+ auto __last_mgr = _M_get_last_node_mgr(__hint._M_cur);
+ return _M_emplace(__last_mgr, __unique_keys{},
std::forward<_Args>(__args)...);
}
@@ -1041,7 +1185,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Set number of buckets keeping it appropriate for container's number
// of elements.
- void rehash(size_type __bkt_count);
+ void rehash(size_type __bkt_count)
+ {
+ auto __last_mgr = _M_get_last_node_mgr();
+ _M_rehash(__last_mgr, __bkt_count);
+ }
// DR 1189.
// reserve, if present, comes from _Rehash_base.
@@ -1049,7 +1197,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())
@@ -1058,14 +1206,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__glibcxx_assert(get_allocator() == __nh.get_allocator());
+ auto __last_mgr = _M_get_last_node_mgr(__hint._M_cur);
__node_ptr __n = nullptr;
const key_type& __k = __nh._M_key();
const size_type __size = size();
if (__size <= __small_size_threshold())
{
- for (__n = _M_begin(); __n; __n = __n->_M_next())
- if (this->_M_key_equals(__k, *__n))
- break;
+ __node_ptr __last_n = nullptr;
+ for (__n = _M_begin(); __n;
+ __last_n = __n, __n = __n->_M_next())
+ {
+ if (this->_M_key_equals(__k, *__n))
+ break;
+ }
+
+ if (!__n)
+ __last_mgr._M_set(__last_n);
}
__hash_code __code;
@@ -1086,8 +1242,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
{
- __ret.position
- = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
+ __ret.position = _M_insert_unique_node(
+ __last_mgr, __bkt, __code, __nh._M_ptr);
__nh._M_ptr = nullptr;
__ret.inserted = true;
}
@@ -1104,10 +1260,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_assert(get_allocator() == __nh.get_allocator());
+ auto __last_mgr = _M_get_last_node_mgr(__hint._M_cur);
const key_type& __k = __nh._M_key();
- auto __code = this->_M_hash_code(__k);
- auto __ret
- = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
+ auto __ret = _M_insert_multi_node(__last_mgr, __k, __nh._M_ptr);
__nh._M_ptr = nullptr;
return __ret;
}
@@ -1147,6 +1302,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return this->_M_hash_code(__k);
}
+ template<typename _H2>
+ iterator
+ _M_insert_multi_node(const _H2&, _LastNodeManager& __last_mgr,
+ const key_type& __k, __node_ptr __equi_n,
+ __node_ptr __n)
+ {
+ if constexpr (std::is_same_v<_H2, _Hash>)
+ if constexpr (std::is_empty_v<_Hash>)
+ return _M_insert_multi_node(__last_mgr, __k, __n, __equi_n);
+
+ return _M_insert_multi_node(__last_mgr, __k, __n);
+ }
+
public:
// Extract a node.
node_type
@@ -1178,6 +1346,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type>, "Node types are compatible");
__glibcxx_assert(get_allocator() == __src.get_allocator());
+ auto __last_mgr = _M_get_last_node_mgr();
auto __n_elt = __src.size();
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
{
@@ -1186,8 +1355,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const key_type& __k = _ExtractKey{}(*__pos);
if (__size <= __small_size_threshold())
{
+ __node_ptr __last_n = nullptr;
bool __found = false;
- for (auto __n = _M_begin(); __n; __n = __n->_M_next())
+ for (auto __n = _M_begin(); __n;
+ __last_n = __n, __n = __n->_M_next())
if (this->_M_key_equals(__k, *__n))
{
__found = true;
@@ -1200,6 +1371,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
--__n_elt;
continue;
}
+ else
+ __last_mgr._M_set(__last_n);
}
__hash_code __code
@@ -1209,7 +1382,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
|| _M_find_node(__bkt, __k, __code) == nullptr)
{
auto __nh = __src.extract(__pos);
- _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
+ _M_insert_unique_node(
+ __last_mgr, __bkt, __code, __nh._M_ptr, __n_elt);
__nh._M_ptr = nullptr;
__n_elt = 1;
}
@@ -1227,27 +1401,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type>, "Node types are compatible");
__glibcxx_assert(get_allocator() == __src.get_allocator());
- __node_ptr __hint = nullptr;
+ auto __last_mgr = _M_get_last_node_mgr();
this->reserve(size() + __src.size());
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
{
auto __pos = __i++;
const key_type& __k = _ExtractKey{}(*__pos);
- __hash_code __code
- = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
auto __nh = __src.extract(__pos);
- __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
+ _M_insert_multi_node(__src.hash_function(),
+ __last_mgr, __k, __pos._M_cur, __nh._M_ptr);
__nh._M_ptr = nullptr;
}
}
#endif // C++17
private:
+ void _M_rehash(_LastNodeManager&, size_type __bkt_count);
+
// Helper rehash method used when keys are unique.
- void _M_rehash(size_type __bkt_count, true_type __uks);
+ void _M_rehash(_LastNodeManager&, size_type __bkt_count, true_type
__uks);
// Helper rehash method used when keys can be non-unique.
- void _M_rehash(size_type __bkt_count, false_type __uks);
+ void _M_rehash(_LastNodeManager&, size_type __bkt_count, false_type
__uks);
};
// Definitions of class template _Hashtable's out-of-line member functions.
@@ -1308,8 +1483,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_bucket_count = __bkt_count;
}
+ auto __last_mgr = _M_get_last_node_mgr();
__alloc_node_gen_t __node_gen(*this);
- _M_insert_range(__f, __l, __node_gen);
+ _M_insert_range(__f, __l, __last_mgr, __node_gen);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -1454,6 +1630,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_buckets[__bkt] = __prev_n;
__prev_n = __this_n;
}
+
+ _M_set_last(__prev_n);
}
__catch(...)
{
@@ -1479,6 +1657,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_buckets = &_M_single_bucket;
_M_before_begin._M_nxt = nullptr;
_M_element_count = 0;
+ _M_set_last(nullptr);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -1509,9 +1688,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
_M_element_count = __ht._M_element_count;
std::__alloc_on_move(this->_M_node_allocator(),
__ht._M_node_allocator());
+ _M_set_last(__ht._M_get_last());
// Fix bucket containing the _M_before_begin pointer that can't be moved.
_M_update_bbegin();
+
__ht._M_reset();
}
@@ -1575,6 +1756,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_before_begin(__ht._M_before_begin._M_nxt),
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
+#if _GLIBCXX_INLINE_VERSION
+ , _M_last(__ht._M_last)
+#endif
{
// Update buckets if __ht is using its single bucket.
if (__ht._M_uses_single_bucket())
@@ -1638,6 +1822,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else
_M_buckets = __ht._M_buckets;
+ _M_set_last(__ht._M_get_last());
+
// Fix bucket containing the _M_before_begin pointer that can't be
// moved.
_M_update_bbegin(__ht._M_begin());
@@ -2147,7 +2333,7 @@ _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(_LastNodeManager& __last_mgr, _Args&&... __args)
-> pair<iterator, bool>
{
// First build the node to get access to the hash code
@@ -2156,10 +2342,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const size_type __size = size();
if (__size <= __small_size_threshold())
{
- for (auto __it = _M_begin(); __it; __it = __it->_M_next())
- if (this->_M_key_equals(__k, *__it))
+ __node_ptr __last_n = nullptr;
+ for (auto __n = _M_begin(); __n;
+ __last_n = __n, __n = __n->_M_next())
+ if (this->_M_key_equals(__k, *__n))
// There is already an equivalent node, no insertion
- return { iterator(__it), false };
+ return { iterator(__n), false };
+
+ __last_mgr._M_set(__last_n);
}
__hash_code __code = this->_M_hash_code(__k);
@@ -2170,7 +2360,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return { iterator(__p), false };
// Insert the node
- auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
+ auto __pos = _M_insert_unique_node(__last_mgr, __bkt, __code,
+ __node._M_node);
__node._M_node = nullptr;
return { __pos, true };
}
@@ -2183,17 +2374,15 @@ _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(_LastNodeManager& __last_mgr, _Args&&... __args)
-> iterator
{
- // First build the node to get its hash code.
+ // First build the node to get its key and hash code.
_Scoped_node __node { this, std::forward<_Args>(__args)... };
+
const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
+ auto __pos = _M_insert_multi_node(__last_mgr, __k, __node._M_node);
- auto __res = this->_M_compute_hash_code(__hint._M_cur, __k);
- auto __pos
- = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
__node._M_node = nullptr;
return __pos;
}
@@ -2205,36 +2394,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const
- -> pair<__node_ptr, __hash_code>
- {
- if (size() <= __small_size_threshold())
- {
- if (__hint)
- {
- for (auto __it = __hint; __it; __it = __it->_M_next())
- if (this->_M_key_equals(__k, *__it))
- return { __it, this->_M_hash_code(*__it) };
- }
-
- for (auto __it = _M_begin(); __it != __hint; __it = __it->_M_next())
- if (this->_M_key_equals(__k, *__it))
- return { __it, this->_M_hash_code(*__it) };
-
- __hint = nullptr;
- }
-
- return { __hint, this->_M_hash_code(__k) };
- }
-
- template<typename _Key, typename _Value, typename _Alloc,
- 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_insert_unique_node(size_type __bkt, __hash_code __code,
+ _M_insert_unique_node(_LastNodeManager& __last_mgr,
+ size_type __bkt, __hash_code __code,
__node_ptr __node, size_type __n_elt)
-> iterator
{
@@ -2245,7 +2406,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__do_rehash.first)
{
- _M_rehash(__do_rehash.second, true_type{});
+ _M_rehash(__last_mgr, __do_rehash.second, true_type{});
__bkt = _M_bucket_index(__code);
}
@@ -2253,7 +2414,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
this->_M_store_code(*__node, __code);
// Always insert at the beginning of the bucket.
- _M_insert_bucket_begin(__bkt, __node);
+ _M_insert_bucket_begin(__last_mgr, __bkt, __node);
++_M_element_count;
return iterator(__node);
}
@@ -2265,51 +2426,74 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert_multi_node(__node_ptr __hint,
- __hash_code __code, __node_ptr __node)
+ _M_insert_multi_node(_LastNodeManager& __last_mgr, const key_type& __k,
+ __node_ptr __node, __node_ptr __equi_n)
-> iterator
{
+ // Compute hash code, if needed, so that we do not rehash if it throws.
+ __hash_code __code;
+ __node_base_ptr __prev = nullptr;
+ const size_type __size = size();
+ if (__size <= __small_size_threshold())
+ {
+ __node_ptr __last_n = nullptr;
+ __prev = &_M_before_begin;
+ __node_ptr __n = static_cast<__node_ptr>(__prev->_M_nxt);
+ for (; __n; __prev = __last_n = __n, __n = __n->_M_next())
+ {
+ if (this->_M_key_equals(__k, *__n))
+ {
+ if (__hash_cached::value)
+ __code = this->_M_hash_code(*__n);
+
+ break;
+ }
+ }
+
+ if (!__n)
+ {
+ __prev = nullptr;
+ __last_mgr._M_set(__last_n);
+ }
+ }
+
+ if (!__prev)
+ {
+ __code = __equi_n
+ ? this->_M_hash_code(*__equi_n)
+ : this->_M_hash_code(__k);
+ }
+
__rehash_guard_t __rehash_guard(_M_rehash_policy);
std::pair<bool, std::size_t> __do_rehash
= _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
if (__do_rehash.first)
- _M_rehash(__do_rehash.second, false_type{});
+ _M_rehash(__last_mgr, __do_rehash.second, false_type{});
__rehash_guard._M_guarded_obj = nullptr;
this->_M_store_code(*__node, __code);
- const key_type& __k = _ExtractKey{}(__node->_M_v());
- size_type __bkt = _M_bucket_index(__code);
- // Find the node before an equivalent one or use hint if it exists and
- // if it is equivalent.
- __node_base_ptr __prev
- = __builtin_expect(__hint != nullptr, false)
- && this->_M_equals(__k, __code, *__hint)
- ? __hint
- : _M_find_before_node(__bkt, __k, __code);
+ size_type __bkt;
+ if (!__prev)
+ {
+ __bkt = _M_bucket_index(__code);
+ if (__size > __small_size_threshold())
+ __prev = _M_find_before_node(__bkt, __k, __code);
+ }
if (__prev)
{
// Insert after the node before the equivalent one.
__node->_M_nxt = __prev->_M_nxt;
__prev->_M_nxt = __node;
- if (__builtin_expect(__prev == __hint, false))
- // hint might be the last bucket node, in this case we need to
- // update next bucket.
- if (__node->_M_nxt
- && !this->_M_equals(__k, __code, *__node->_M_next()))
- {
- size_type __next_bkt = _M_bucket_index(*__node->_M_next());
- if (__next_bkt != __bkt)
- _M_buckets[__next_bkt] = __node;
- }
}
else
// The inserted node has no equivalent in the hashtable. We must
// insert the new node at the beginning of the bucket to preserve
// equivalent elements' relative positions.
- _M_insert_bucket_begin(__bkt, __node);
+ _M_insert_bucket_begin(__last_mgr, __bkt, __node);
+
++_M_element_count;
return iterator(__node);
}
@@ -2323,15 +2507,21 @@ _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(_LastNodeManager& __last_mgr, _Kt&& __k, _Arg&& __v,
_NodeGenerator& __node_gen)
-> pair<iterator, bool>
{
const size_type __size = size();
if (__size <= __small_size_threshold())
- for (auto __it = _M_begin(); __it; __it = __it->_M_next())
- if (this->_M_key_equals_tr(__k, *__it))
- return { iterator(__it), false };
+ {
+ __node_ptr __last_n = nullptr;
+ for (auto __n = _M_begin(); __n;
+ __last_n = __n, __n = __n->_M_next())
+ if (this->_M_key_equals_tr(__k, *__n))
+ return { iterator(__n), false };
+
+ __last_mgr._M_set(__last_n);
+ }
__hash_code __code = this->_M_hash_code_tr(__k);
size_type __bkt = _M_bucket_index(__code);
@@ -2346,8 +2536,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__node_gen),
this
};
+
auto __pos
- = _M_insert_unique_node(__bkt, __code, __node._M_node);
+ = _M_insert_unique_node(__last_mgr, __bkt, __code, __node._M_node);
__node._M_node = nullptr;
return { __pos, true };
}
@@ -2361,20 +2552,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert(const_iterator __hint, _Arg&& __v,
- _NodeGenerator& __node_gen,
- false_type /* __uks */)
+ _M_insert(_LastNodeManager& __last_mgr, _Arg&& __v,
+ _NodeGenerator& __node_gen, false_type /* __uks */)
-> 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 };
-
- // Second compute the hash code so that we don't rehash if it throws.
- auto __res = this->_M_compute_hash_code(
- __hint._M_cur, _ExtractKey{}(__node._M_node->_M_v()));
+ _Scoped_node __node { __node_gen(std::forward<_Arg>(__v)), this };
- auto __pos
- = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
+ auto __pos = _M_insert_multi_node(
+ __last_mgr, _ExtractKey{}(__node._M_node->_M_v()), __node._M_node);
__node._M_node = nullptr;
return __pos;
}
@@ -2388,10 +2574,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert_range(_InputIterator __first, _InputIterator __last,
- _NodeGenerator& __node_gen)
+ _LastNodeManager& __last_mgr, _NodeGenerator& __node_gen)
{
for (; __first != __last; ++__first)
- _M_insert(*__first, __node_gen, __unique_keys{});
+ _M_insert(__last_mgr, *__first, __node_gen, __unique_keys{});
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2438,7 +2624,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator __result(__n->_M_next());
this->_M_deallocate_node(__n);
--_M_element_count;
-
+ _M_check_for_last(__prev_n);
return __result;
}
@@ -2547,7 +2733,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
else if (__n_last_bkt != __bkt)
_M_buckets[__n_last_bkt] = __prev_n;
+
__prev_n->_M_nxt = __n_last;
+ _M_check_for_last(__prev_n);
return __result;
}
@@ -2595,6 +2783,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__n && (__n_bkt != __bkt || __is_bucket_begin))
_M_buckets[__n_bkt] = __prev_n;
__prev_n->_M_nxt = __n;
+ _M_check_for_last(__prev_n);
return iterator(__n);
}
@@ -2612,6 +2801,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_bucket_count * sizeof(__node_base_ptr));
_M_element_count = 0;
_M_before_begin._M_nxt = nullptr;
+ _M_set_last(nullptr);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2621,7 +2811,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- rehash(size_type __bkt_count)
+ _M_rehash(_LastNodeManager& __last_mgr, size_type __bkt_count)
{
__rehash_guard_t __rehash_guard(_M_rehash_policy);
__bkt_count
@@ -2631,7 +2821,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__bkt_count != _M_bucket_count)
{
- _M_rehash(__bkt_count, __unique_keys{});
+ _M_rehash(__last_mgr, __bkt_count, __unique_keys{});
__rehash_guard._M_guarded_obj = nullptr;
}
}
@@ -2644,32 +2834,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_rehash(size_type __bkt_count, true_type /* __uks */)
+ _M_rehash(_LastNodeManager& __last_mgr,
+ size_type __bkt_count, true_type /* __uks */)
{
- __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
__node_ptr __p = _M_begin();
+ __node_base_ptr __bbegin_n = &_M_before_begin;
+
+ __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
_M_before_begin._M_nxt = nullptr;
- std::size_t __bbegin_bkt = 0;
+ __last_mgr._M_reset();
while (__p)
{
__node_ptr __next = __p->_M_next();
std::size_t __bkt
= __hash_code_base::_M_bucket_index(*__p, __bkt_count);
- if (!__new_buckets[__bkt])
- {
- __p->_M_nxt = _M_before_begin._M_nxt;
- _M_before_begin._M_nxt = __p;
- __new_buckets[__bkt] = &_M_before_begin;
- if (__p->_M_nxt)
- __new_buckets[__bbegin_bkt] = __p;
- __bbegin_bkt = __bkt;
- }
- else
- {
- __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
- __new_buckets[__bkt]->_M_nxt = __p;
- }
-
+ _S_insert_bucket_begin(__last_mgr, __bbegin_n, __new_buckets,
+ __bkt, __p);
__p = __next;
}
@@ -2687,16 +2867,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_rehash(size_type __bkt_count, false_type /* __uks */)
+ _M_rehash(_LastNodeManager& __last_mgr,
+ size_type __bkt_count, false_type /* __uks */)
{
- __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
__node_ptr __p = _M_begin();
- _M_before_begin._M_nxt = nullptr;
- std::size_t __bbegin_bkt = 0;
+ __node_base_ptr __bbegin_n = &_M_before_begin;
std::size_t __prev_bkt = 0;
__node_ptr __prev_p = nullptr;
bool __check_bucket = false;
+ __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
+ _M_before_begin._M_nxt = nullptr;
+ __last_mgr._M_reset();
while (__p)
{
__node_ptr __next = __p->_M_next();
@@ -2711,6 +2893,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__p->_M_nxt = __prev_p->_M_nxt;
__prev_p->_M_nxt = __p;
+ if (!__p->_M_nxt)
+ __last_mgr._M_set(__p);
+
// Inserting after a node in a bucket require to check that we
// haven't change the bucket last node, in this case next
// bucket containing its before begin node must be updated. We
@@ -2728,28 +2913,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
std::size_t __next_bkt
= __hash_code_base::_M_bucket_index(
- *__prev_p->_M_next(), __bkt_count);
+ *__prev_p->_M_next(), __bkt_count);
if (__next_bkt != __prev_bkt)
__new_buckets[__next_bkt] = __prev_p;
}
__check_bucket = false;
}
- if (!__new_buckets[__bkt])
- {
- __p->_M_nxt = _M_before_begin._M_nxt;
- _M_before_begin._M_nxt = __p;
- __new_buckets[__bkt] = &_M_before_begin;
- if (__p->_M_nxt)
- __new_buckets[__bbegin_bkt] = __p;
- __bbegin_bkt = __bkt;
- }
- else
- {
- __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
- __new_buckets[__bkt]->_M_nxt = __p;
- }
+ _S_insert_bucket_begin(__last_mgr, __bbegin_n, __new_buckets,
+ __bkt, __p);
}
+
__prev_p = __p;
__prev_bkt = __bkt;
__p = __next;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
b/libstdc++-v3/include/bits/hashtable_policy.h
index 9f775522cff..69ef84ad519 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -848,8 +848,9 @@ namespace __detail
std::tuple<const key_type&>(__k),
std::tuple<>()
};
- auto __pos
- = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
+ auto __last_mgr = __h->_M_get_last_node_mgr();
+ auto __pos = __h->_M_insert_unique_node(__last_mgr, __bkt, __code,
+ __node._M_node);
__node._M_node = nullptr;
return __pos->second;
}
@@ -875,8 +876,9 @@ namespace __detail
std::forward_as_tuple(std::move(__k)),
std::tuple<>()
};
- auto __pos
- = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
+ auto __last_mgr = __h->_M_get_last_node_mgr();
+ auto __pos = __h->_M_insert_unique_node(__last_mgr, __bkt, __code,
+ __node._M_node);
__node._M_node = nullptr;
return __pos->second;
}
@@ -964,13 +966,14 @@ namespace __detail
insert(const_iterator __hint, const value_type& __v)
{
__hashtable& __h = _M_conjure_hashtable();
- __node_gen_type __node_gen(__h);
- return __h._M_insert(__hint, __v, __node_gen, __unique_keys{});
+ auto __last_mgr = __h._M_get_last_node_mgr(__hint._M_cur);
+ __node_gen_type __node_gen(__h);
+ return __h._M_insert(__last_mgr, __v, __node_gen, __unique_keys{});
}
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);
@@ -984,8 +987,9 @@ namespace __detail
std::forward_as_tuple(std::forward<_KType>(__k)),
std::forward_as_tuple(std::forward<_Args>(__args)...)
};
- auto __it
- = __h._M_insert_unique_node(__bkt, __code, __node._M_node);
+ auto __last_mgr = __h._M_get_last_node_mgr(__hint._M_cur);
+ auto __it = __h._M_insert_unique_node(__last_mgr, __bkt, __code,
+ __node._M_node);
__node._M_node = nullptr;
return { __it, true };
}
@@ -1013,8 +1017,9 @@ namespace __detail
true_type /* __uks */)
{
__hashtable& __h = _M_conjure_hashtable();
+ auto __last_mgr = __h._M_get_last_node_mgr();
__node_gen_type __node_gen(__h);
- __h._M_insert_range(__first, __last, __node_gen);
+ __h._M_insert_range(__first, __last, __last_mgr, __node_gen);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -1037,6 +1042,7 @@ namespace __detail
return;
__hashtable& __h = _M_conjure_hashtable();
+ auto __last_mgr = __h._M_get_last_node_mgr();
__rehash_guard_t __rehash_guard(__h._M_rehash_policy);
__pair_type __do_rehash
= __h._M_rehash_policy._M_need_rehash(__h._M_bucket_count,
@@ -1044,11 +1050,11 @@ namespace __detail
__n_elt);
if (__do_rehash.first)
- __h._M_rehash(__do_rehash.second, __uks);
+ __h._M_rehash(__last_mgr, __do_rehash.second, __uks);
__rehash_guard._M_guarded_obj = nullptr;
__node_gen_type __node_gen(__h);
- __h._M_insert_range(__first, __last, __node_gen);
+ __h._M_insert_range(__first, __last, __last_mgr, __node_gen);
}
/**
@@ -1102,8 +1108,9 @@ namespace __detail
insert(const_iterator __hint, value_type&& __v)
{
__hashtable& __h = this->_M_conjure_hashtable();
+ auto __last_mgr = __h._M_get_last_node_mgr(__hint._M_cur);
__node_gen_type __node_gen(__h);
- return __h._M_insert(__hint, std::move(__v), __node_gen,
+ return __h._M_insert(__last_mgr, std::move(__v), __node_gen,
__unique_keys{});
}
};
@@ -1153,7 +1160,8 @@ namespace __detail
insert(const_iterator __hint, _Pair&& __v)
{
__hashtable& __h = this->_M_conjure_hashtable();
- return __h._M_emplace(__hint, __unique_keys{},
+ auto __last_mgr = __h._M_get_last_node_mgr(__hint._M_cur);
+ return __h._M_emplace(__last_mgr, __unique_keys{},
std::forward<_Pair>(__v));
}
};
diff --git a/libstdc++-v3/include/bits/unordered_map.h
b/libstdc++-v3/include/bits/unordered_map.h
index 1c99a83bc1e..e5df97c9229 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -443,12 +443,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
#ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
diff --git a/libstdc++-v3/include/bits/unordered_set.h
b/libstdc++-v3/include/bits/unordered_set.h
index f3b0c078baa..915cd4fb700 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -504,12 +504,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
///@{
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_map/consistency_check.cc
b/libstdc++-v3/testsuite/23_containers/unordered_map/consistency_check.cc
new file mode 100644
index 00000000000..bac37c39a83
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/consistency_check.cc
@@ -0,0 +1,108 @@
+// { dg-do run { target c++11 } }
+
+#include <string>
+#include <sstream>
+#include <vector>
+#include <unordered_map>
+
+#include <testsuite_hooks.h>
+
+namespace
+{
+ const int nb_elements = 2000;
+
+ template<typename _ElemType>
+ void check(const std::unordered_map<_ElemType, int>& us)
+ {
+ VERIFY( std::distance(us.begin(), us.end()) == us.size() );
+ std::size_t bkt_elems_count = 0;
+ for (std::size_t i = 0; i != us.bucket_count(); ++i)
+ {
+ if (us.bucket_size(i) == 0)
+ continue;
+
+ bkt_elems_count += us.bucket_size(i);
+ for (auto lit = us.begin(i); lit != us.end(i); ++lit)
+ {
+ VERIFY( us.bucket(lit->first) == i );
+ }
+ }
+
+ VERIFY( bkt_elems_count == us.size() );
+ }
+
+ template<typename _ElemType>
+ void run(const std::vector<_ElemType>& elems, bool with_copy)
+ {
+ std::unordered_map<_ElemType, int> um;
+ check(um);
+
+ for (int i = 0; i != nb_elements; ++i)
+ {
+ um.insert({ elems[i], i });
+ check(um);
+ }
+
+ if (with_copy)
+ {
+ std::unordered_map<_ElemType, int>(um).swap(um);
+ check(um);
+ }
+
+ for (int i = nb_elements - 1; i >= 0; --i)
+ {
+ auto it = um.find(elems[i]);
+ if (it != um.end())
+ {
+ um.erase(it);
+ check(um);
+ }
+ }
+
+ um.insert({ elems[0], 0 });
+ check(um);
+
+ for (int i = nb_elements - 1; i >= 0; --i)
+ {
+ um.insert({ elems[i], i });
+ check(um);
+ }
+
+ for (int j = nb_elements - 1; j >= 0; --j)
+ {
+ um.erase(elems[j]);
+ check(um);
+ }
+ }
+}
+
+int main()
+{
+ {
+ std::vector<int> elems;
+ elems.reserve(nb_elements);
+ for (int i = 0; i != nb_elements; ++i)
+ elems.push_back(i);
+
+ run(elems, false);
+ run(elems, true);
+ }
+
+ {
+ std::vector<std::string> elems;
+ {
+ elems.reserve(nb_elements);
+ for (int i = 0; i != nb_elements; ++i)
+ {
+ std::ostringstream ostr;
+ ostr << "string #" << i << ' ' << std::string(1000, 'a' + i);
+ elems.push_back(ostr.str());
+ }
+ }
+
+ run(elems, false);
+ run(elems, true);
+ }
+
+ return 0;
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_multimap/consistency_check.cc
b/libstdc++-v3/testsuite/23_containers/unordered_multimap/consistency_check.cc
new file mode 100644
index 00000000000..c4f26553d8a
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_multimap/consistency_check.cc
@@ -0,0 +1,111 @@
+// { dg-do run { target c++11 } }
+
+#include <string>
+#include <sstream>
+#include <vector>
+#include <unordered_map>
+
+#include <testsuite_hooks.h>
+
+namespace
+{
+ const int nb_elements = 1000;
+ const int nb_copies = 5;
+
+ template<typename _ElemType>
+ void check(const std::unordered_multimap<_ElemType, int>& um)
+ {
+ VERIFY( std::distance(um.begin(), um.end()) == um.size() );
+ std::size_t bkt_elems_count = 0;
+ for (std::size_t i = 0; i != um.bucket_count(); ++i)
+ {
+ if (um.bucket_size(i) == 0)
+ continue;
+
+ bkt_elems_count += um.bucket_size(i);
+ for (auto lit = um.begin(i); lit != um.end(i); ++lit)
+ {
+ VERIFY( um.bucket(lit->first) == i );
+ }
+ }
+
+ VERIFY( bkt_elems_count == um.size() );
+ }
+
+ template<typename _ElemType>
+ void run(const std::vector<_ElemType>& elems, bool with_copy)
+ {
+ std::unordered_multimap<_ElemType, int> um;
+ um.max_load_factor(nb_copies);
+ check(um);
+
+ for (int h = 0; h != nb_copies; ++h)
+ for (int i = 0; i != nb_elements; ++i)
+ {
+ um.insert({ elems[i], i + i * h });
+ check(um);
+ }
+
+ if (with_copy)
+ {
+ std::unordered_multimap<_ElemType, int>(um).swap(um);
+ check(um);
+ }
+
+ for (int i = nb_elements - 1; i >= 0; --i)
+ {
+ auto it = um.find(elems[i]);
+ if (it != um.end())
+ {
+ um.erase(it);
+ check(um);
+ }
+ }
+
+ um.insert({ elems[0], 0 });
+ check(um);
+
+ for (int i = nb_elements - 1; i >= 0; --i)
+ {
+ um.insert({ elems[i], i });
+ check(um);
+ }
+
+ for (int j = nb_elements - 1; j >= 0; --j)
+ {
+ um.erase(elems[j]);
+ check(um);
+ }
+ }
+}
+
+int main()
+{
+ {
+ std::vector<int> elems;
+ elems.reserve(nb_elements);
+ for (int i = 0; i != nb_elements; ++i)
+ elems.push_back(i);
+
+ run(elems, false);
+ run(elems, true);
+ }
+
+ {
+ std::vector<std::string> elems;
+ {
+ elems.reserve(nb_elements);
+ for (int i = 0; i != nb_elements; ++i)
+ {
+ std::ostringstream ostr;
+ ostr << "string #" << i << ' ' << std::string(1000, 'a' + i);
+ elems.push_back(ostr.str());
+ }
+ }
+
+ run(elems, false);
+ run(elems, true);
+ }
+
+ return 0;
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
index d0ed60c6799..1db71b8f30b 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
@@ -40,11 +40,12 @@ void test01()
VERIFY( it2 != m.end() );
VERIFY( it2 != it1 );
VERIFY( it2->second == 2 );
- VERIFY( it2 == std::next(it1) );
+ VERIFY( std::next(it2) == it1 );
+ it1 = it2;
Pair p(0, 1);
it2 = m.insert(it1, p);
- VERIFY( it2 == std::next(it1) );
+ VERIFY( std::next(it2) == it1 );
}
struct hasher
@@ -71,13 +72,13 @@ void test02()
VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 );
auto it4 = m.insert(it1, Pair(0, 1));
- VERIFY( it4 == std::next(it1) );
+ VERIFY( std::next(it4) == it1 );
VERIFY( m.bucket_size(m.bucket(it1->first)) == 3 );
VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 );
Pair p(1, 1);
it4 = m.insert(it2, p);
- VERIFY( it4 == std::next(it2) );
+ VERIFY( std::next(it4) == it2 );
VERIFY( m.bucket_size(m.bucket(it1->first)) == 4 );
auto range = m.equal_range(0);
VERIFY( std::distance(range.first, range.second) == 2 );
@@ -104,11 +105,12 @@ void test03()
VERIFY( it2 != m.end() );
VERIFY( it2 != it1 );
VERIFY( it2->second == 2 );
- VERIFY( it2 == std::next(it1) );
+ VERIFY( std::next(it2) == it1 );
+ it1 = it2;
Pair p(0, 1);
it2 = m.emplace_hint(it1, p);
- VERIFY( it2 == std::next(it1) );
+ VERIFY( std::next(it2) == it1 );
}
int main()
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_multiset/consistency_check.cc
b/libstdc++-v3/testsuite/23_containers/unordered_multiset/consistency_check.cc
new file mode 100644
index 00000000000..f463a2cee1d
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_multiset/consistency_check.cc
@@ -0,0 +1,110 @@
+// { dg-do run { target c++11 } }
+
+#include <string>
+#include <sstream>
+#include <vector>
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+
+namespace
+{
+ const int nb_elements = 1000;
+ const int nb_copies = 5;
+
+ template<typename _ElemType>
+ void check(const std::unordered_multiset<_ElemType>& us)
+ {
+ VERIFY( std::distance(us.begin(), us.end()) == us.size() );
+ std::size_t bkt_elems_count = 0;
+ for (std::size_t i = 0; i != us.bucket_count(); ++i)
+ {
+ if (us.bucket_size(i) == 0)
+ continue;
+
+ bkt_elems_count += us.bucket_size(i);
+ for (auto lit = us.begin(i); lit != us.end(i); ++lit)
+ {
+ VERIFY( us.bucket(*lit) == i );
+ }
+ }
+
+ VERIFY( bkt_elems_count == us.size() );
+ }
+
+ template<typename _ElemType>
+ void run(const std::vector<_ElemType>& elems, bool with_copy)
+ {
+ std::unordered_multiset<_ElemType> us;
+ us.max_load_factor(nb_copies);
+ check(us);
+
+ for (int h = 0; h != nb_copies; ++h)
+ for (int i = 0; i != nb_elements; ++i)
+ {
+ us.insert(elems[i]);
+ check(us);
+ }
+
+ if (with_copy)
+ {
+ std::unordered_multiset<_ElemType>(us).swap(us);
+ check(us);
+ }
+
+ for (int i = nb_elements - 1; i >= 0; --i)
+ {
+ auto it = us.find(elems[i]);
+ if (it != us.end())
+ {
+ us.erase(it);
+ check(us);
+ }
+ }
+
+ us.insert(elems[0]);
+ check(us);
+ for (int i = nb_elements - 1; i >= 0; --i)
+ {
+ us.insert(elems[i]);
+ check(us);
+ }
+
+ for (int j = nb_elements - 1; j >= 0; --j)
+ {
+ us.erase(elems[j]);
+ check(us);
+ }
+ }
+}
+
+int main()
+{
+ {
+ std::vector<int> elems;
+ elems.reserve(nb_elements);
+ for (int i = 0; i != nb_elements; ++i)
+ elems.push_back(i);
+
+ run(elems, false);
+ run(elems, true);
+ }
+
+ {
+ std::vector<std::string> elems;
+ {
+ elems.reserve(nb_elements);
+ for (int i = 0; i != nb_elements; ++i)
+ {
+ std::ostringstream ostr;
+ ostr << "string #" << i << ' ' << std::string(1000, 'a' + i);
+ elems.push_back(ostr.str());
+ }
+ }
+
+ run(elems, false);
+ run(elems, true);
+ }
+
+ return 0;
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_set/consistency_check.cc
b/libstdc++-v3/testsuite/23_containers/unordered_set/consistency_check.cc
new file mode 100644
index 00000000000..70581c557ad
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/consistency_check.cc
@@ -0,0 +1,107 @@
+// { dg-do run { target c++11 } }
+
+#include <string>
+#include <sstream>
+#include <vector>
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+
+namespace
+{
+ const int nb_elements = 2000;
+
+ template<typename _ElemType>
+ void check(const std::unordered_set<_ElemType>& us)
+ {
+ VERIFY( std::distance(us.begin(), us.end()) == us.size() );
+ std::size_t bkt_elems_count = 0;
+ for (std::size_t i = 0; i != us.bucket_count(); ++i)
+ {
+ if (us.bucket_size(i) == 0)
+ continue;
+
+ bkt_elems_count += us.bucket_size(i);
+ for (auto lit = us.begin(i); lit != us.end(i); ++lit)
+ {
+ VERIFY( us.bucket(*lit) == i );
+ }
+ }
+
+ VERIFY( bkt_elems_count == us.size() );
+ }
+
+ template<typename _ElemType>
+ void run(const std::vector<_ElemType>& elems, bool with_copy)
+ {
+ std::unordered_set<_ElemType> us;
+ check(us);
+
+ for (int i = 0; i != nb_elements; ++i)
+ {
+ us.insert(elems[i]);
+ check(us);
+ }
+
+ if (with_copy)
+ {
+ std::unordered_set<_ElemType>(us).swap(us);
+ check(us);
+ }
+
+ for (int i = nb_elements - 1; i >= 0; --i)
+ {
+ auto it = us.find(elems[i]);
+ if (it != us.end())
+ {
+ us.erase(it);
+ check(us);
+ }
+ }
+
+ us.insert(elems[0]);
+ check(us);
+ for (int i = nb_elements - 1; i >= 0; --i)
+ {
+ us.insert(elems[i]);
+ check(us);
+ }
+
+ for (int j = nb_elements - 1; j >= 0; --j)
+ {
+ us.erase(elems[j]);
+ check(us);
+ }
+ }
+}
+
+int main()
+{
+ {
+ std::vector<int> elems;
+ elems.reserve(nb_elements);
+ for (int i = 0; i != nb_elements; ++i)
+ elems.push_back(i);
+
+ run(elems, false);
+ run(elems, true);
+ }
+
+ {
+ std::vector<std::string> elems;
+ {
+ elems.reserve(nb_elements);
+ for (int i = 0; i != nb_elements; ++i)
+ {
+ std::ostringstream ostr;
+ ostr << "string #" << i << ' ' << std::string(1000, 'a' + i);
+ elems.push_back(ostr.str());
+ }
+ }
+
+ run(elems, false);
+ run(elems, true);
+ }
+
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx11.cc
b/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx11.cc
index 0f1736a1550..4b16354a26b 100644
--- a/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx11.cc
+++ b/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx11.cc
@@ -103,10 +103,10 @@ main()
std::unordered_map<int, std::string> uom;
uom[5] = "three";
uom[3] = "seven";
-// { dg-final { regexp-test uom {std::(__debug::)?unordered_map with 2
elements = {\[3\] = "seven", \[5\] = "three"}} } }
+// { dg-final { regexp-test uom {std::(__debug::)?unordered_map with 2
elements = {\[5\] = "three", \[3\] = "seven"}} } }
std::unordered_map<int, std::string> &ruom = uom;
-// { dg-final { regexp-test ruom {std::(__debug::)?unordered_map with 2
elements = {\[3\] = "seven", \[5\] = "three"}} } }
+// { dg-final { regexp-test ruom {std::(__debug::)?unordered_map with 2
elements = {\[5\] = "three", \[3\] = "seven"}} } }
std::unordered_multimap<int, std::string> uomm;
uomm.insert(std::pair<int, std::string> (5, "three"));
