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 std::pair - _M_emplace(true_type __uks, _Args&&... __args); + _M_emplace_unique(_LastNodeManager&, _Args&&... __args); template iterator - _M_emplace(false_type __uks, _Args&&... __args) - { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); } + _M_emplace_multi(_LastNodeManager&, _Args&&... __args); + + template + std::pair + _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 + 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 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 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 std::pair - _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&); + _M_insert_unique(_LastNodeManager&, _Kt&&, _Arg&&, _NodeGenerator&); template static __conditional_t< @@ -944,9 +1082,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _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 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 iterator - _M_insert(const_iterator, _Arg&&, + _M_insert(_LastNodeManager& __last_mgr, _Arg&& __arg, _NodeGenerator&, false_type __uks); template 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 + 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_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 { // 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 - 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 __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 { 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_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:: - 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(__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 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 __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_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 +#include +#include +#include + +#include + +namespace +{ + const int nb_elements = 2000; + + template + 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 + 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 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 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 +#include +#include +#include + +#include + +namespace +{ + const int nb_elements = 1000; + const int nb_copies = 5; + + template + 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 + 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 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 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 +#include +#include +#include + +#include + +namespace +{ + const int nb_elements = 1000; + const int nb_copies = 5; + + template + 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 + 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 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 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 +#include +#include +#include + +#include + +namespace +{ + const int nb_elements = 2000; + + template + 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 + 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 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 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 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 &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 uomm; uomm.insert(std::pair (5, "three"));