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.

1 files changed, 12 insertions, 5 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