diff options
author | François Dumont <fdumont@gcc.gnu.org> | 2021-10-13 22:04:32 +0200 |
---|---|---|
committer | François Dumont <fdumont@gcc.gnu.org> | 2021-11-09 21:50:17 +0100 |
commit | f4b4ce152a06578d94ae7630cffd655d590b2857 (patch) | |
tree | 46615606217dc6b64d3370cb652c96537abfd567 /libstdc++-v3/include/bits | |
parent | f7844b6a777cb47fec7208d7bd594f6ce66f1daa (diff) | |
download | gcc-f4b4ce152a06578d94ae7630cffd655d590b2857.zip gcc-f4b4ce152a06578d94ae7630cffd655d590b2857.tar.gz gcc-f4b4ce152a06578d94ae7630cffd655d590b2857.tar.bz2 |
libstdc++: [_GLIBCXX_DEBUG] Implement unordered container merge
The _GLIBCXX_DEBUG unordered containers need a dedicated merge implementation
so that any existing iterator on the transfered nodes is properly invalidated.
Add typedef/using declarations for everything used as-is from normal implementation.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h (__distance_fw): Replace class keyword with
typename.
* include/bits/hashtable.h (_Hashtable<>::_M_merge_unique): Remove noexcept
qualification. Use const_iterator for node extraction/reinsert.
(_Hashtable<>::_M_merge_multi): Likewise. Compute new hash code before extract.
* include/debug/safe_container.h (_Safe_container<>): Make all methods
protected.
* include/debug/safe_unordered_container.h
(_Safe_unordered_container<>::_UContInvalidatePred<_ExtractKey, _Source>): New.
(_Safe_unordered_container<>::_UMContInvalidatePred<_ExtractKey, _Source>): New.
(_Safe_unordered_container<>::_UContMergeGuard<_Source, _InvalidatePred>): New.
(_Safe_unordered_container<>::_S_uc_guard<_ExtractKey, _Source>): New.
(_Safe_unordered_container<>::_S_umc_guard<_ExtractKey, _Source>): New.
(_Safe_unordered_container<>::_M_invalide_all): Make public.
(_Safe_unordered_container<>::_M_invalide_if): Likewise.
(_Safe_unordered_container<>::_M_invalide_local_if): Likewise.
* include/debug/unordered_map
(unordered_map<>::mapped_type, pointer, const_pointer): New typedef.
(unordered_map<>::reference, const_reference, difference_type): New typedef.
(unordered_map<>::get_allocator, empty, size, max_size): Add usings.
(unordered_map<>::bucket_count, max_bucket_count, bucket): Add usings.
(unordered_map<>::hash_function, key_equal, count, contains): Add usings.
(unordered_map<>::operator[], at, rehash, reserve): Add usings.
(unordered_map<>::merge): New.
(unordered_multimap<>::mapped_type, pointer, const_pointer): New typedef.
(unordered_multimap<>::reference, const_reference, difference_type): New typedef.
(unordered_multimap<>::get_allocator, empty, size, max_size): Add usings.
(unordered_multimap<>::bucket_count, max_bucket_count, bucket): Add usings.
(unordered_multimap<>::hash_function, key_equal, count, contains): Add usings.
(unordered_multimap<>::rehash, reserve): Add usings.
(unordered_multimap<>::merge): New.
* include/debug/unordered_set
(unordered_set<>::mapped_type, pointer, const_pointer): New typedef.
(unordered_set<>::reference, const_reference, difference_type): New typedef.
(unordered_set<>::get_allocator, empty, size, max_size): Add usings.
(unordered_set<>::bucket_count, max_bucket_count, bucket): Add usings.
(unordered_set<>::hash_function, key_equal, count, contains): Add usings.
(unordered_set<>::rehash, reserve): Add usings.
(unordered_set<>::merge): New.
(unordered_multiset<>::mapped_type, pointer, const_pointer): New typedef.
(unordered_multiset<>::reference, const_reference, difference_type): New typedef.
(unordered_multiset<>::get_allocator, empty, size, max_size): Add usings.
(unordered_multiset<>::bucket_count, max_bucket_count, bucket): Add usings.
(unordered_multiset<>::hash_function, key_equal, count, contains): Add usings.
(unordered_multiset<>::rehash, reserve): Add usings.
(unordered_multiset<>::merge): New.
* testsuite/23_containers/unordered_map/debug/merge1_neg.cc: New test.
* testsuite/23_containers/unordered_map/debug/merge2_neg.cc: New test.
* testsuite/23_containers/unordered_map/debug/merge3_neg.cc: New test.
* testsuite/23_containers/unordered_map/debug/merge4_neg.cc: New test.
* testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc: New test.
* testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc: New test.
* testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc: New test.
* testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc: New test.
* testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc: New test.
* testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc: New test.
* testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc: New test.
* testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc: New test.
* testsuite/23_containers/unordered_set/debug/merge1_neg.cc: New test.
* testsuite/23_containers/unordered_set/debug/merge2_neg.cc: New test.
* testsuite/23_containers/unordered_set/debug/merge3_neg.cc: New test.
* testsuite/23_containers/unordered_set/debug/merge4_neg.cc: New test.
* testsuite/util/testsuite_abi.h: [_GLIBCXX_DEBUG] Use normal unordered
container implementation.
Diffstat (limited to 'libstdc++-v3/include/bits')
-rw-r--r-- | libstdc++-v3/include/bits/hashtable.h | 17 | ||||
-rw-r--r-- | libstdc++-v3/include/bits/hashtable_policy.h | 6 |
2 files changed, 15 insertions, 8 deletions
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 25c45d3..0e949d7 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -1065,14 +1065,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// Merge from a compatible container into one with unique keys. template<typename _Compatible_Hashtable> void - _M_merge_unique(_Compatible_Hashtable& __src) noexcept + _M_merge_unique(_Compatible_Hashtable& __src) { static_assert(is_same_v<typename _Compatible_Hashtable::node_type, node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); auto __n_elt = __src.size(); - for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) + for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { auto __pos = __i++; const key_type& __k = _ExtractKey{}(*__pos); @@ -1093,15 +1093,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// Merge from a compatible container into one with equivalent keys. template<typename _Compatible_Hashtable> void - _M_merge_multi(_Compatible_Hashtable& __src) noexcept + _M_merge_multi(_Compatible_Hashtable& __src) { static_assert(is_same_v<typename _Compatible_Hashtable::node_type, node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); this->reserve(size() + __src.size()); - for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) - _M_reinsert_node_multi(cend(), __src.extract(__i++)); + for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) + { + auto __pos = __i++; + const key_type& __k = _ExtractKey{}(*__pos); + __hash_code __code = this->_M_hash_code(__k); + auto __nh = __src.extract(__pos); + _M_insert_multi_node(nullptr, __code, __nh._M_ptr); + __nh._M_ptr = nullptr; + } } #endif // C++17 diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 8c72043..c0295b7 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -60,19 +60,19 @@ namespace __detail // Helper function: return distance(first, last) for forward // iterators, or 0/1 for input iterators. - template<class _Iterator> + template<typename _Iterator> inline typename std::iterator_traits<_Iterator>::difference_type __distance_fw(_Iterator __first, _Iterator __last, std::input_iterator_tag) { return __first != __last ? 1 : 0; } - template<class _Iterator> + template<typename _Iterator> inline typename std::iterator_traits<_Iterator>::difference_type __distance_fw(_Iterator __first, _Iterator __last, std::forward_iterator_tag) { return std::distance(__first, __last); } - template<class _Iterator> + template<typename _Iterator> inline typename std::iterator_traits<_Iterator>::difference_type __distance_fw(_Iterator __first, _Iterator __last) { return __distance_fw(__first, __last, |