diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index aec77c34a58..d758b054b00 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 _HintPolicy + { + _Hashtable& _M_htb; + __node_ptr _M_last; + std::size_t _M_bbegin_index; + bool _M_initialized = false; + + public: + _HintPolicy(_Hashtable& __htbl, __node_ptr __last) + : _M_htb(__htbl), _M_last(__last) + { } + +#if _GLIBCXX_INLINE_VERSION + ~_HintPolicy() + { _M_htb._M_last = _M_last; } +#endif + + 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_hint() + { return _M_last; } + + void + _M_set_last(__node_ptr __n) + { _M_last = __n; } + + void + _M_checked_set(__node_ptr __n) + { + if (!__n || !__n->_M_nxt) + _M_last = __n; + } + }; + void _M_update_bbegin() { @@ -425,6 +478,51 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_uses_single_bucket() const { return _M_uses_single_bucket(_M_buckets); } + __node_ptr + _M_get_hint([[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 + } + + _HintPolicy + _M_get_hint_policy(__node_ptr __usr_hint = nullptr) + { return _HintPolicy(*this, _M_get_hint(__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 + } + + constexpr __node_ptr + _M_get_last() + { +#if _GLIBCXX_INLINE_VERSION + return _M_last; +#else + return nullptr; +#endif + } + static constexpr size_t __small_size_threshold() noexcept { @@ -612,11 +710,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 __hint_policy = _M_get_hint_policy(); + // Do not shrink to keep potential user reservation. if (_M_bucket_count < __l_bkt_count) - rehash(__l_bkt_count); + _M_rehash(__hint_policy, __l_bkt_count); - _M_insert_range(__l.begin(), __l.end(), __roan); + _M_insert_range(__l.begin(), __l.end(), __hint_policy, __roan); return *this; } @@ -838,30 +938,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Insert a node at the beginning of a bucket. void - _M_insert_bucket_begin(size_type __bkt, __node_ptr __node) + _M_insert_bucket_begin(_HintPolicy& __hint_policy, + size_type __bkt, __node_ptr __node) { + __node_base_ptr __prev; if (_M_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 = _M_buckets[__bkt]; + if (!__prev->_M_nxt) + __hint_policy._M_set_last(__node); } 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 a hint, the last container node, insert after. + __node_ptr __hint = __hint_policy._M_get_hint(); + if (__hint) + { + __prev = __hint; + __hint_policy._M_set_last(__node); + } + 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. + __prev = &_M_before_begin; + + if (__prev->_M_nxt) + { + // We must update former begin bucket that is pointing to + // _M_before_begin. + size_type __bb_bkt = __hint_policy._M_get_bbegin_bkt( + static_cast<__node_ptr>(__prev->_M_nxt)); + _M_buckets[__bb_bkt] = __node; + } + else + __hint_policy._M_set_last(__node); + + __hint_policy._M_store_bbegin_bkt(__bkt); + } + + _M_buckets[__bkt] = __prev; } + + __node->_M_nxt = __prev->_M_nxt; + __prev->_M_nxt = __node; } // Remove the bucket first node @@ -887,44 +1010,76 @@ _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; + struct _InsertInfo + { + __node_base_ptr _M_prev; + __node_ptr _M_equi_n; + __hash_code _M_code; + }; + + _InsertInfo + _M_get_insert_info(_HintPolicy& __hint_policy, const key_type& __k, + __node_ptr __n = nullptr) 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(_HintPolicy& __hint_policy, + 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(_HintPolicy& __hint_policy, + const _InsertInfo& __info, __node_ptr __n); + + template + std::pair + _M_emplace_unique(_HintPolicy&, _Args&&... __args); + + template + iterator + _M_emplace_multi(_HintPolicy&, _Args&&... __args); template std::pair - _M_emplace(true_type __uks, _Args&&... __args); + _M_emplace(true_type /*__uks*/, _Args&&... __args) + { + auto __hint_policy = _M_get_hint_policy(); + return _M_emplace_unique(__hint_policy, + std::forward<_Args>(__args)...); + } template iterator - _M_emplace(false_type __uks, _Args&&... __args) - { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); } + _M_emplace(false_type /*__uks*/, _Args&&... __args) + { + auto __hint_policy = _M_get_hint_policy(); + return _M_emplace_multi(__hint_policy, + std::forward<_Args>(__args)...); + } - // Emplace with hint, useless when keys are unique. template iterator - _M_emplace(const_iterator, true_type __uks, _Args&&... __args) - { return _M_emplace(__uks, std::forward<_Args>(__args)...).first; } + _M_emplace(_HintPolicy& __hint_policy, + true_type /*__uks*/, _Args&&... __args) + { + return _M_emplace_unique(__hint_policy, + std::forward<_Args>(__args)...).first; + } template iterator - _M_emplace(const_iterator, false_type __uks, _Args&&... __args); + _M_emplace(_HintPolicy& __hint_policy, + false_type /*__uks*/, _Args&&... __args) + { return _M_emplace_multi(__hint_policy, std::forward<_Args>(__args)...); } template std::pair - _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&); + _M_insert_unique(_HintPolicy& __hint_policy, + _Kt&&, _Arg&&, _NodeGenerator&); template static __conditional_t< @@ -944,9 +1099,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen) + _M_insert_unique_aux(_HintPolicy& __hint_policy, + _Arg&& __arg, _NodeGenerator& __node_gen) { - return _M_insert_unique( + return _M_insert_unique(__hint_policy, _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))), std::forward<_Arg>(__arg), __node_gen); } @@ -956,9 +1112,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen, true_type /* __uks */) { + auto __hint_policy = _M_get_hint_policy(); using __to_value = __detail::_ConvertToValueType<_ExtractKey, value_type>; - return _M_insert_unique_aux( + return _M_insert_unique_aux(__hint_policy, __to_value{}(std::forward<_Arg>(__arg)), __node_gen); } @@ -967,32 +1124,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen, false_type __uks) { + auto __hint_policy = _M_get_hint_policy(); using __to_value = __detail::_ConvertToValueType<_ExtractKey, value_type>; - return _M_insert(cend(), + return _M_insert(__hint_policy, __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 iterator - _M_insert(const_iterator, _Arg&& __arg, - _NodeGenerator& __node_gen, true_type __uks) + _M_insert(_HintPolicy& __hint_policy, _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(__hint_policy, + __to_value{}(std::forward<_Arg>(__arg)), __node_gen).first; } // Insert with hint when keys are not unique. template iterator - _M_insert(const_iterator, _Arg&&, + _M_insert(_HintPolicy& __hint_policy, _Arg&& __arg, _NodeGenerator&, false_type __uks); template void _M_insert_range(_InputIterator __first, _InputIterator __last, - _NodeGenerator&); + _HintPolicy&, _NodeGenerator&); size_type _M_erase(true_type __uks, const key_type&); @@ -1014,7 +1174,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator emplace_hint(const_iterator __hint, _Args&&... __args) { - return _M_emplace(__hint, __unique_keys{}, + auto __hint_policy = _M_get_hint_policy(__hint._M_cur); + return _M_emplace(__hint_policy, __unique_keys{}, std::forward<_Args>(__args)...); } @@ -1041,7 +1202,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 __hint_policy = _M_get_hint_policy(); + _M_rehash(__hint_policy, __bkt_count); + } // DR 1189. // reserve, if present, comes from _Rehash_base. @@ -1049,7 +1214,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 +1223,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { __glibcxx_assert(get_allocator() == __nh.get_allocator()); + auto __hint_policy = _M_get_hint_policy(__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) + __hint_policy._M_set_last(__last_n); } __hash_code __code; @@ -1086,8 +1259,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } else { - __ret.position - = _M_insert_unique_node(__bkt, __code, __nh._M_ptr); + __ret.position = _M_insert_unique_node( + __hint_policy, __bkt, __code, __nh._M_ptr); __nh._M_ptr = nullptr; __ret.inserted = true; } @@ -1104,10 +1277,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_assert(get_allocator() == __nh.get_allocator()); + auto __hint_policy = _M_get_hint_policy(__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 __info = _M_get_insert_info(__hint_policy, __k); + auto __ret = _M_insert_multi_node(__hint_policy, __info, __nh._M_ptr); __nh._M_ptr = nullptr; return __ret; } @@ -1147,6 +1320,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return this->_M_hash_code(__k); } + template + _InsertInfo + _M_get_insert_info(const _H2&, _HintPolicy& __hint_policy, + __node_ptr __n, const key_type& __k) + { + if constexpr (std::is_same_v<_H2, _Hash>) + if constexpr (std::is_empty_v<_Hash>) + return _M_get_insert_info(__hint_policy, __k, __n); + + return _M_get_insert_info(__hint_policy, __k); + } + public: // Extract a node. node_type @@ -1178,6 +1363,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); + auto __hint_policy = _M_get_hint_policy(); auto __n_elt = __src.size(); for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { @@ -1186,8 +1372,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 +1388,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION --__n_elt; continue; } + else + __hint_policy._M_set_last(__last_n); } __hash_code __code @@ -1209,7 +1399,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( + __hint_policy, __bkt, __code, __nh._M_ptr, __n_elt); __nh._M_ptr = nullptr; __n_elt = 1; } @@ -1227,27 +1418,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); - __node_ptr __hint = nullptr; + auto __hint_policy = _M_get_hint_policy(); 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 __info = _M_get_insert_info(__src.hash_function(), + __hint_policy, __pos._M_cur, __k); auto __nh = __src.extract(__pos); - __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur; + _M_insert_multi_node(__hint_policy, __info, __nh._M_ptr); __nh._M_ptr = nullptr; } } #endif // C++17 private: + void _M_rehash(_HintPolicy&, 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(_HintPolicy&, 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(_HintPolicy&, size_type __bkt_count, false_type __uks); }; // Definitions of class template _Hashtable's out-of-line member functions. @@ -1308,8 +1501,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bucket_count = __bkt_count; } + auto __hint_policy = _M_get_hint_policy(); __alloc_node_gen_t __node_gen(*this); - _M_insert_range(__f, __l, __node_gen); + _M_insert_range(__f, __l, __hint_policy, __node_gen); } template_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 +1774,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 +1840,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 +2351,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(_HintPolicy& __hint_policy, _Args&&... __args) -> pair { // First build the node to get access to the hash code @@ -2156,10 +2360,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 }; + + __hint_policy._M_set_last(__last_n); } __hash_code __code = this->_M_hash_code(__k); @@ -2170,7 +2378,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(__hint_policy, __bkt, __code, + __node._M_node); __node._M_node = nullptr; return { __pos, true }; } @@ -2183,17 +2392,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(_HintPolicy& __hint_policy, _Args&&... __args) -> iterator { // First build the node to get its hash code. _Scoped_node __node { this, std::forward<_Args>(__args)... }; const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); - auto __res = this->_M_compute_hash_code(__hint._M_cur, __k); - auto __pos - = _M_insert_multi_node(__res.first, __res.second, __node._M_node); + auto __info = _M_get_insert_info(__hint_policy, __k); + auto __pos = _M_insert_multi_node(__hint_policy, __info, __node._M_node); __node._M_node = nullptr; return __pos; } @@ -2205,26 +2412,32 @@ _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> + _M_get_insert_info(_HintPolicy& __hint_policy, const key_type& __k, + __node_ptr __equi_n) const + -> _InsertInfo { 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) }; + __node_ptr __last_n = nullptr; + __node_base_ptr __prev + = const_cast<__node_base_ptr>(&_M_before_begin); + for (auto __n = static_cast<__node_ptr>(__prev->_M_nxt); __n; + __prev = __last_n = __n, __n = __n->_M_next()) + if (this->_M_key_equals(__k, *__n)) + return + { + __prev, __n, + __hash_cached::value ? this->_M_hash_code(*__n) : 0 + }; - __hint = nullptr; + __hint_policy._M_set_last(__last_n); } - return { __hint, this->_M_hash_code(__k) }; + return + { + nullptr, nullptr, + __equi_n ? this->_M_hash_code(*__equi_n) : this->_M_hash_code(__k) + }; } template:: - _M_insert_unique_node(size_type __bkt, __hash_code __code, + _M_insert_unique_node(_HintPolicy& __hint_policy, + size_type __bkt, __hash_code __code, __node_ptr __node, size_type __n_elt) -> iterator { @@ -2245,7 +2459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__do_rehash.first) { - _M_rehash(__do_rehash.second, true_type{}); + _M_rehash(__hint_policy, __do_rehash.second, true_type{}); __bkt = _M_bucket_index(__code); } @@ -2253,7 +2467,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(__hint_policy, __bkt, __node); ++_M_element_count; return iterator(__node); } @@ -2265,8 +2479,8 @@ _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(_HintPolicy& __hint_policy, + const _InsertInfo& __info, __node_ptr __node) -> iterator { __rehash_guard_t __rehash_guard(_M_rehash_policy); @@ -2274,42 +2488,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION = _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(__hint_policy, __do_rehash.second, false_type{}); __rehash_guard._M_guarded_obj = nullptr; + auto __code = __info._M_code; this->_M_store_code(*__node, __code); const key_type& __k = _ExtractKey{}(__node->_M_v()); - size_type __bkt = _M_bucket_index(__code); + auto __prev = __info._M_prev; + const bool __has_prev = __prev != nullptr; + size_type __bkt; // 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); + if (!__has_prev) + { + __bkt = _M_bucket_index(__code); + __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; - } + + // __hint might be the last bucket node, in this case we need to + // update next bucket. + if (__has_prev && __node->_M_nxt != __info._M_equi_n) + { + const auto __nxt = __node->_M_next(); + if (!this->_M_equals(__k, __code, *__nxt)) + { + size_type __next_bkt = _M_bucket_index(*__nxt); + if (__next_bkt != _M_bucket_index(__code)) + _M_buckets[__next_bkt] = __node; + } + } + + __hint_policy._M_checked_set(__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); + { + // 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(__hint_policy, __bkt, __node); + } + ++_M_element_count; return iterator(__node); } @@ -2323,15 +2548,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(_HintPolicy& __hint_policy, _Kt&& __k, _Arg&& __v, _NodeGenerator& __node_gen) -> pair { 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 }; + + __hint_policy._M_set_last(__last_n); + } __hash_code __code = this->_M_hash_code_tr(__k); size_type __bkt = _M_bucket_index(__code); @@ -2346,8 +2577,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_gen), this }; + auto __pos - = _M_insert_unique_node(__bkt, __code, __node._M_node); + = _M_insert_unique_node(__hint_policy, __bkt, __code, __node._M_node); __node._M_node = nullptr; return { __pos, true }; } @@ -2361,20 +2593,19 @@ _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(_HintPolicy& __hint_policy, _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 }; + _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())); - - auto __pos - = _M_insert_multi_node(__res.first, __res.second, __node._M_node); + auto __info = + _M_get_insert_info(__hint_policy, + _ExtractKey{}(__node._M_node->_M_v())); + auto __pos = _M_insert_multi_node(__hint_policy, + __info, __node._M_node); __node._M_node = nullptr; return __pos; } @@ -2388,10 +2619,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) + _HintPolicy& __hint_policy, _NodeGenerator& __node_gen) { for (; __first != __last; ++__first) - _M_insert(*__first, __node_gen, __unique_keys{}); + _M_insert(__hint_policy, *__first, __node_gen, __unique_keys{}); } template_M_next()); this->_M_deallocate_node(__n); --_M_element_count; - + _M_check_for_last(__prev_n); return __result; } @@ -2547,7 +2778,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 +2828,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 +2846,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:: - rehash(size_type __bkt_count) + _M_rehash(_HintPolicy& __hint_policy, size_type __bkt_count) { __rehash_guard_t __rehash_guard(_M_rehash_policy); __bkt_count @@ -2631,7 +2866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__bkt_count != _M_bucket_count) { - _M_rehash(__bkt_count, __unique_keys{}); + _M_rehash(__hint_policy, __bkt_count, __unique_keys{}); __rehash_guard._M_guarded_obj = nullptr; } } @@ -2644,9 +2879,11 @@ _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(_HintPolicy& __hint_policy, + size_type __bkt_count, true_type /* __uks */) { __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count); + __node_ptr __prev_p = nullptr; __node_ptr __p = _M_begin(); _M_before_begin._M_nxt = nullptr; std::size_t __bbegin_bkt = 0; @@ -2670,12 +2907,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __new_buckets[__bkt]->_M_nxt = __p; } + __prev_p = __p; __p = __next; } _M_deallocate_buckets(); _M_bucket_count = __bkt_count; _M_buckets = __new_buckets; + __hint_policy._M_set_last(__prev_p); } // Rehash when there can be equivalent elements, preserve their relative @@ -2687,7 +2926,8 @@ _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(_HintPolicy& __hint_policy, + size_type __bkt_count, false_type /* __uks */) { __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count); __node_ptr __p = _M_begin(); @@ -2750,6 +2990,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __new_buckets[__bkt]->_M_nxt = __p; } } + __prev_p = __p; __prev_bkt = __bkt; __p = __next; @@ -2767,6 +3008,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_deallocate_buckets(); _M_bucket_count = __bkt_count; _M_buckets = __new_buckets; + __hint_policy._M_set_last(__prev_p); } #if __cplusplus > 201402L diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 9f775522cff..c8905f59289 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(__k), std::tuple<>() }; - auto __pos - = __h->_M_insert_unique_node(__bkt, __code, __node._M_node); + auto __hint_policy = __h->_M_get_hint_policy(); + auto __pos = __h->_M_insert_unique_node(__hint_policy, __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 __hint_policy = __h->_M_get_hint_policy(); + auto __pos = __h->_M_insert_unique_node(__hint_policy, __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 __hint_policy = __h._M_get_hint_policy(__hint._M_cur); + __node_gen_type __node_gen(__h); + return __h._M_insert(__hint_policy, __v, __node_gen, __unique_keys{}); } template std::pair - 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 __hint_policy = __h._M_get_hint_policy(__hint._M_cur); + auto __it = __h._M_insert_unique_node(__hint_policy, __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 __hint_policy = __h._M_get_hint_policy(); __node_gen_type __node_gen(__h); - __h._M_insert_range(__first, __last, __node_gen); + __h._M_insert_range(__first, __last, __hint_policy, __node_gen); } template_M_conjure_hashtable(); + auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur); __node_gen_type __node_gen(__h); - return __h._M_insert(__hint, std::move(__v), __node_gen, + return __h._M_insert(__hint_policy, 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 __hint_policy = __h._M_get_hint_policy(__hint._M_cur); + return __h._M_emplace(__hint_policy, __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_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()