From: "François Dumont" <frs.dumont@gmail.com>
To: "libstdc++@gcc.gnu.org" <libstdc++@gcc.gnu.org>
Cc: gcc-patches <gcc-patches@gcc.gnu.org>
Subject: [PATH][_GLIBCXX_DEBUG] Fix unordered container merge
Date: Wed, 13 Oct 2021 19:10:09 +0200 [thread overview]
Message-ID: <4eec3fb9-851e-3e4e-f9f4-1110db3af747@gmail.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 5204 bytes --]
Hi
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 declaration for everything used as-is from normal
implementation.
libstdc++-v3/ChangeLog:
* include/debug/safe_container.h (_Safe_container<>): Make
all methods
protected.
* include/debug/safe_unordered_container.h
(_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.
Tested under Linux x86_64.
Ok to commit ?
François
[-- Attachment #2: merge.patch --]
[-- Type: text/x-patch, Size: 30413 bytes --]
diff --git a/libstdc++-v3/include/debug/safe_container.h b/libstdc++-v3/include/debug/safe_container.h
index 97c47167fe8..5de55d69f34 100644
--- a/libstdc++-v3/include/debug/safe_container.h
+++ b/libstdc++-v3/include/debug/safe_container.h
@@ -78,7 +78,6 @@ namespace __gnu_debug
{ }
#endif
- public:
// Copy assignment invalidate all iterators.
_Safe_container&
operator=(const _Safe_container&) _GLIBCXX_NOEXCEPT
diff --git a/libstdc++-v3/include/debug/safe_unordered_container.h b/libstdc++-v3/include/debug/safe_unordered_container.h
index aae1e2dab60..06d0e91282c 100644
--- a/libstdc++-v3/include/debug/safe_unordered_container.h
+++ b/libstdc++-v3/include/debug/safe_unordered_container.h
@@ -72,6 +72,7 @@ namespace __gnu_debug
{ return __it != __local_end; });
}
+ public:
void
_M_invalidate_all()
{
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index bb697d364ea..d359d285f99 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -97,7 +97,12 @@ namespace __debug
typedef typename _Base::key_type key_type;
typedef typename _Base::value_type value_type;
+ typedef typename _Base::mapped_type mapped_type;
+ typedef typename _Base::pointer pointer;
+ typedef typename _Base::const_pointer const_pointer;
+ typedef typename _Base::reference reference;
+ typedef typename _Base::const_reference const_reference;
typedef __gnu_debug::_Safe_iterator<
_Base_iterator, unordered_map> iterator;
typedef __gnu_debug::_Safe_iterator<
@@ -106,6 +111,7 @@ namespace __debug
_Base_local_iterator, unordered_map> local_iterator;
typedef __gnu_debug::_Safe_local_iterator<
_Base_const_local_iterator, unordered_map> const_local_iterator;
+ typedef typename _Base::difference_type difference_type;
unordered_map() = default;
@@ -209,6 +215,11 @@ namespace __debug
return *this;
}
+ using _Base::get_allocator;
+ using _Base::empty;
+ using _Base::size;
+ using _Base::max_size;
+
void
swap(unordered_map& __x)
noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -291,6 +302,10 @@ namespace __debug
return { _Base::cend(__b), this };
}
+ using _Base::bucket_count;
+ using _Base::max_bucket_count;
+ using _Base::bucket;
+
size_type
bucket_size(size_type __b) const
{
@@ -298,6 +313,8 @@ namespace __debug
return _Base::bucket_size(__b);
}
+ using _Base::load_factor;
+
float
max_load_factor() const noexcept
{ return _Base::max_load_factor(); }
@@ -538,9 +555,72 @@ namespace __debug
return { _Base::insert(__hint.base(), std::move(__nh)), this };
}
- using _Base::merge;
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+ {
+ auto __size = __source.size();
+ _Base::merge(__source._M_base());
+ if (__source.size() == __size)
+ return;
+
+ if (__source.empty())
+ __source._M_invalidate_all();
+ else
+ {
+ auto __pred = [&__source](auto __it)
+ { return __source.count(__it->first) == 0; };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ }
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+ {
+ auto __size = __source.size();
+ _Base::merge(__source._M_base());
+ if (__source.size() == __size)
+ return;
+
+ if (__source.empty())
+ __source._M_invalidate_all();
+ else
+ {
+ _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&
+ __base_src = __source;
+ auto __pred = [&__base_src](auto __it)
+ {
+ auto __rng = __base_src.equal_range(__it->first);
+ for (auto __rit = __rng.first; __rit != __rng.second; ++__rit)
+ {
+ if (__it == __rit)
+ return false;
+ }
+
+ return true;
+ };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ }
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
#endif // C++17
+ using _Base::hash_function;
+ using _Base::key_eq;
+
iterator
find(const key_type& __key)
{ return { _Base::find(__key), this }; }
@@ -567,6 +647,11 @@ namespace __debug
{ return { _Base::find(__k), this }; }
#endif
+ using _Base::count;
+#if __cplusplus > 201703L
+ using _Base::contains;
+#endif
+
std::pair<iterator, iterator>
equal_range(const key_type& __key)
{
@@ -605,6 +690,9 @@ namespace __debug
}
#endif
+ using _Base::operator[];
+ using _Base::at;
+
size_type
erase(const key_type& __key)
{
@@ -651,6 +739,9 @@ namespace __debug
return { __next, this };
}
+ using _Base::rehash;
+ using _Base::reserve;
+
_Base&
_M_base() noexcept { return *this; }
@@ -843,7 +934,12 @@ namespace __debug
typedef typename _Base::key_type key_type;
typedef typename _Base::value_type value_type;
+ typedef typename _Base::mapped_type mapped_type;
+ typedef typename _Base::pointer pointer;
+ typedef typename _Base::const_pointer const_pointer;
+ typedef typename _Base::reference reference;
+ typedef typename _Base::const_reference const_reference;
typedef __gnu_debug::_Safe_iterator<
_Base_iterator, unordered_multimap> iterator;
typedef __gnu_debug::_Safe_iterator<
@@ -852,6 +948,7 @@ namespace __debug
_Base_local_iterator, unordered_multimap> local_iterator;
typedef __gnu_debug::_Safe_local_iterator<
_Base_const_local_iterator, unordered_multimap> const_local_iterator;
+ typedef typename _Base::difference_type difference_type;
unordered_multimap() = default;
@@ -952,6 +1049,11 @@ namespace __debug
return *this;
}
+ using _Base::get_allocator;
+ using _Base::empty;
+ using _Base::size;
+ using _Base::max_size;
+
void
swap(unordered_multimap& __x)
noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -1034,6 +1136,10 @@ namespace __debug
return { _Base::cend(__b), this };
}
+ using _Base::bucket_count;
+ using _Base::max_bucket_count;
+ using _Base::bucket;
+
size_type
bucket_size(size_type __b) const
{
@@ -1192,9 +1298,37 @@ namespace __debug
return { _Base::insert(__hint.base(), std::move(__nh)), this };
}
- using _Base::merge;
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+ {
+ _Base::merge(__source._M_base());
+ __source._M_invalidate_all();
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+ {
+ _Base::merge(__source._M_base());
+ __source._M_invalidate_all();
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
#endif // C++17
+ using _Base::hash_function;
+ using _Base::key_eq;
+
iterator
find(const key_type& __key)
{ return { _Base::find(__key), this }; }
@@ -1221,6 +1355,11 @@ namespace __debug
{ return { _Base::find(__k), this }; }
#endif
+ using _Base::count;
+#if __cplusplus > 201703L
+ using _Base::contains;
+#endif
+
std::pair<iterator, iterator>
equal_range(const key_type& __key)
{
@@ -1309,6 +1448,9 @@ namespace __debug
return { __next, this };
}
+ using _Base::rehash;
+ using _Base::reserve;
+
_Base&
_M_base() noexcept { return *this; }
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index c25910946b7..10f44903b8f 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -88,6 +88,7 @@ namespace __debug
public:
typedef typename _Base::size_type size_type;
+ typedef typename _Base::difference_type difference_type;
typedef typename _Base::hasher hasher;
typedef typename _Base::key_equal key_equal;
typedef typename _Base::allocator_type allocator_type;
@@ -95,6 +96,10 @@ namespace __debug
typedef typename _Base::key_type key_type;
typedef typename _Base::value_type value_type;
+ typedef typename _Base::pointer pointer;
+ typedef typename _Base::const_pointer const_pointer;
+ typedef typename _Base::reference reference;
+ typedef typename _Base::const_reference const_reference;
typedef __gnu_debug::_Safe_iterator<
_Base_iterator, unordered_set> iterator;
typedef __gnu_debug::_Safe_iterator<
@@ -203,6 +208,11 @@ namespace __debug
return *this;
}
+ using _Base::get_allocator;
+ using _Base::empty;
+ using _Base::size;
+ using _Base::max_size;
+
void
swap(unordered_set& __x)
noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -285,6 +295,9 @@ namespace __debug
return { _Base::cend(__b), this };
}
+ using _Base::bucket_count;
+ using _Base::max_bucket_count;
+
size_type
bucket_size(size_type __b) const
{
@@ -292,6 +305,9 @@ namespace __debug
return _Base::bucket_size(__b);
}
+ using _Base::bucket;
+ using _Base::load_factor;
+
float
max_load_factor() const noexcept
{ return _Base::max_load_factor(); }
@@ -303,6 +319,9 @@ namespace __debug
_Base::max_load_factor(__f);
}
+ using _Base::rehash;
+ using _Base::reserve;
+
template<typename... _Args>
std::pair<iterator, bool>
emplace(_Args&&... __args)
@@ -423,9 +442,71 @@ namespace __debug
return { _Base::insert(__hint.base(), std::move(__nh)), this };
}
- using _Base::merge;
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
+ {
+ auto __size = __source.size();
+ _Base::merge(__source._M_base());
+ if (__source.size() == __size)
+ return;
+
+ if (__source.empty())
+ __source._M_invalidate_all();
+ else
+ {
+ auto __pred = [&__source](auto __it)
+ { return __source.count(*__it) == 0; };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ }
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
+ {
+ auto __size = __source.size();
+ _Base::merge(__source._M_base());
+ if (__source.size() == __size)
+ return;
+
+ if (__source.empty())
+ __source._M_invalidate_all();
+ else
+ {
+ _GLIBCXX_STD_C::unordered_multiset<_Value, _H2, _P2, _Alloc>&
+ __base_src = __source;
+ auto __pred = [&__base_src](auto __it)
+ {
+ auto __rng = __base_src.equal_range(*__it);
+ for (auto __rit = __rng.first; __rit != __rng.second; ++__rit)
+ {
+ if (__it == __rit)
+ return false;
+ }
+
+ return true;
+ };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ }
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
#endif // C++17
+ using _Base::hash_function;
+ using _Base::key_eq;
+
iterator
find(const key_type& __key)
{ return { _Base::find(__key), this }; }
@@ -452,6 +533,12 @@ namespace __debug
{ return { _Base::find(__k), this }; }
#endif
+ using _Base::count;
+
+#if __cplusplus > 201703L
+ using _Base::contains;
+#endif
+
std::pair<iterator, iterator>
equal_range(const key_type& __key)
{
@@ -707,6 +794,7 @@ namespace __debug
public:
typedef typename _Base::size_type size_type;
+ typedef typename _Base::difference_type difference_type;
typedef typename _Base::hasher hasher;
typedef typename _Base::key_equal key_equal;
typedef typename _Base::allocator_type allocator_type;
@@ -714,6 +802,10 @@ namespace __debug
typedef typename _Base::key_type key_type;
typedef typename _Base::value_type value_type;
+ typedef typename _Base::pointer pointer;
+ typedef typename _Base::const_pointer const_pointer;
+ typedef typename _Base::reference reference;
+ typedef typename _Base::const_reference const_reference;
typedef __gnu_debug::_Safe_iterator<
_Base_iterator, unordered_multiset> iterator;
typedef __gnu_debug::_Safe_iterator<
@@ -822,6 +914,11 @@ namespace __debug
return *this;
}
+ using _Base::get_allocator;
+ using _Base::empty;
+ using _Base::size;
+ using _Base::max_size;
+
void
swap(unordered_multiset& __x)
noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -904,6 +1001,9 @@ namespace __debug
return { _Base::cend(__b), this };
}
+ using _Base::bucket_count;
+ using _Base::max_bucket_count;
+
size_type
bucket_size(size_type __b) const
{
@@ -911,6 +1011,9 @@ namespace __debug
return _Base::bucket_size(__b);
}
+ using _Base::bucket;
+ using _Base::load_factor;
+
float
max_load_factor() const noexcept
{ return _Base::max_load_factor(); }
@@ -922,6 +1025,9 @@ namespace __debug
_Base::max_load_factor(__f);
}
+ using _Base::rehash;
+ using _Base::reserve;
+
template<typename... _Args>
iterator
emplace(_Args&&... __args)
@@ -1037,9 +1143,36 @@ namespace __debug
return { _Base::insert(__hint.base(), std::move(__nh)), this };
}
- using _Base::merge;
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
+ {
+ _Base::merge(__source._M_base());
+ __source._M_invalidate_all();
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
+ {
+ _Base::merge(__source._M_base());
+ __source._M_invalidate_all();
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
#endif // C++17
+ using _Base::hash_function;
+ using _Base::key_eq;
+
iterator
find(const key_type& __key)
{ return { _Base::find(__key), this }; }
@@ -1066,6 +1199,12 @@ namespace __debug
{ return { _Base::find(__k), this }; }
#endif
+ using _Base::count;
+
+#if __cplusplus > 201703L
+ using _Base::contains;
+#endif
+
std::pair<iterator, iterator>
equal_range(const key_type& __key)
{
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge1_neg.cc
new file mode 100644
index 00000000000..69e8a6741a8
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge1_neg.cc
@@ -0,0 +1,31 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, int>;
+
+void
+test01()
+{
+ test_type c0{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 5, 5 }, { 6, 6 } };
+ test_type c1{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 } };
+
+ auto it2 = c1.find(2);
+ auto it4 = c1.find(4);
+ VERIFY( it2->second == 2 );
+ VERIFY( it4->second == 4 );
+
+ c0.merge(c1);
+
+ VERIFY( it2->second == 2 );
+ VERIFY( it4 != it2 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge2_neg.cc
new file mode 100644
index 00000000000..543cd960a5e
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge2_neg.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, int>;
+
+void
+test01()
+{
+ test_type c0{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 5, 5 }, { 6, 6 } };
+ test_type c1{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 } };
+
+ auto it2 = c1.find(2);
+ auto it4 = c1.find(4);
+ VERIFY( it2->second == 2 );
+ VERIFY( it4->second == 4 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it2->second == 2 );
+ VERIFY( it2 != it4 ); // Invalid iterator.
+}
+
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge3_neg.cc
new file mode 100644
index 00000000000..8e234799cbf
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge3_neg.cc
@@ -0,0 +1,42 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 2, 2 }, { 3, 3 },
+ { 5, 5 }, { 6, 6 }, { 7, 7 }
+ };
+ std::unordered_multimap<int, int> c1
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 }, { 2, 2 },
+ { 3, 3 }, { 3, 3 }, { 4, 4 }, { 4, 4 },
+ { 5, 5 }
+ };
+
+ auto it1 = c1.find(1);
+ auto it41 = c1.find(4);
+ auto it42 = it41;
+ ++it42;
+ VERIFY( it42->second == 4 );
+
+ c0.merge(c1);
+
+ VERIFY( it1->second == 1 );
+ VERIFY( c1.count(4) == 1 );
+ VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge4_neg.cc
new file mode 100644
index 00000000000..3c9c8268f8c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge4_neg.cc
@@ -0,0 +1,42 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 2, 2 }, { 3, 3 },
+ { 5, 5 }, { 6, 6 }, { 7, 7 }
+ };
+ std::unordered_multimap<int, int> c1
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 }, { 2, 2 },
+ { 3, 3 }, { 3, 3 }, { 4, 4 }, { 4, 4 },
+ { 5, 5 }
+ };
+
+ auto it1 = c1.find(1);
+ auto it41 = c1.find(4);
+ auto it42 = it41;
+ ++it42;
+ VERIFY( it42->second == 4 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it1->second == 1 );
+ VERIFY( c1.count(4) == 1 );
+ VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc
new file mode 100644
index 00000000000..25b3b9e0c75
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 },
+ { 2, 2 }, { 3, 3 }, { 3, 3 }
+ };
+ test_type c1 = c0;
+
+ auto it = c1.find(2);
+ VERIFY( it->second == 2 );
+
+ c0.merge(c1);
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc
new file mode 100644
index 00000000000..8d28d83b972
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 },
+ { 2, 2 }, { 3, 3 }, { 3, 3 }
+ };
+ test_type c1 = c0;
+
+ auto it = c1.find(2);
+ VERIFY( it->second == 2 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc
new file mode 100644
index 00000000000..5db91a27ca0
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 },
+ { 2, 2 }, { 3, 3 }, { 3, 3 }
+ };
+ std::unordered_map<int, int> c1{ { 1, 1 }, { 2, 2 }, { 3, 3 } };
+
+ auto it = c1.find(2);
+ VERIFY( it->second == 2 );
+
+ c0.merge(c1);
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc
new file mode 100644
index 00000000000..a1636703569
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 },
+ { 2, 2 }, { 3, 3 }, { 3, 3 }
+ };
+ std::unordered_map<int, int> c1{ { 1, 1 }, { 2, 2 }, { 3, 3 } };
+
+ auto it = c1.find(2);
+ VERIFY( it->second == 2 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc
new file mode 100644
index 00000000000..bce8da7f6cf
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 1, 2, 2, 3, 3 };
+ test_type c1 = c0;
+
+ auto it = c1.find(2);
+ VERIFY( *it == 2 );
+
+ c0.merge(c1);
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc
new file mode 100644
index 00000000000..72317a32e89
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 1, 2, 2, 3, 3 };
+ test_type c1 = c0;
+
+ auto it = c1.find(2);
+ VERIFY( *it == 2 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc
new file mode 100644
index 00000000000..1b1f4870dd1
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 1, 2, 2, 3, 3 };
+ std::unordered_set<int> c1{ 1, 2, 3 };
+
+ auto it = c1.find(2);
+ VERIFY( *it == 2 );
+
+ c0.merge(c1);
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc
new file mode 100644
index 00000000000..5005cf8468a
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 1, 2, 2, 3, 3 };
+ std::unordered_set<int> c1{ 1, 2, 3 };
+
+ auto it = c1.find(2);
+ VERIFY( *it == 2 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge1_neg.cc
new file mode 100644
index 00000000000..8a2bc6e468f
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge1_neg.cc
@@ -0,0 +1,31 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 2, 3, 5, 6 };
+ test_type c1{ 1, 2, 3, 4 };
+
+ auto it2 = c1.find(2);
+ auto it4 = c1.find(4);
+ VERIFY( *it2 == 2 );
+ VERIFY( *it4 == 4 );
+
+ c0.merge(c1);
+
+ VERIFY( *it2 == 2 );
+ VERIFY( it2 != it4 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge2_neg.cc
new file mode 100644
index 00000000000..3ac96540770
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge2_neg.cc
@@ -0,0 +1,31 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 2, 3, 5, 6 };
+ test_type c1{ 1, 2, 3, 4 };
+
+ auto it2 = c1.find(2);
+ auto it4 = c1.find(4);
+ VERIFY( *it2 == 2 );
+ VERIFY( *it4 == 4 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( *it2 == 2 );
+ VERIFY( it2 != it4 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge3_neg.cc
new file mode 100644
index 00000000000..7e93b55d507
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge3_neg.cc
@@ -0,0 +1,33 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 2, 3, 5, 6, 7 };
+ std::unordered_multiset<int> c1{ 1, 1, 2, 2, 3, 3, 4, 4, 5 };
+
+ auto it1 = c1.find(1);
+ auto it41 = c1.find(4);
+ auto it42 = it41;
+ ++it42;
+ VERIFY( *it42 == 4 );
+
+ c0.merge(c1);
+
+ VERIFY( *it1 == 1 );
+ VERIFY( c1.count(4) == 1 );
+ VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge4_neg.cc
new file mode 100644
index 00000000000..14c8ff63b05
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge4_neg.cc
@@ -0,0 +1,33 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 2, 3, 5, 6, 7 };
+ std::unordered_multiset<int> c1{ 1, 1, 2, 2, 3, 3, 4, 4, 5 };
+
+ auto it1 = c1.find(1);
+ auto it41 = c1.find(4);
+ auto it42 = it41;
+ ++it42;
+ VERIFY( *it42 == 4 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( *it1 == 1 );
+ VERIFY( c1.count(4) == 1 );
+ VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/util/testsuite_abi.h b/libstdc++-v3/testsuite/util/testsuite_abi.h
index 667c46c33d3..4a0cf64f6fb 100644
--- a/libstdc++-v3/testsuite/util/testsuite_abi.h
+++ b/libstdc++-v3/testsuite/util/testsuite_abi.h
@@ -24,7 +24,11 @@
#include <locale>
#if __cplusplus >= 201103L
# include <unordered_map>
+# ifdef _GLIBCXX_DEBUG
+namespace unord = std::_GLIBCXX_STD_C;
+# else
namespace unord = std;
+# endif
#else
# include <tr1/unordered_map>
namespace unord = std::tr1;
next reply other threads:[~2021-10-13 17:10 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-10-13 17:10 François Dumont [this message]
2021-10-14 8:23 ` Jonathan Wakely
2021-10-16 13:47 ` François Dumont
2021-10-16 14:52 ` Jonathan Wakely
2021-10-21 16:51 ` François Dumont
2021-10-21 16:55 ` Jonathan Wakely
2021-10-22 5:22 ` François Dumont
2021-10-25 18:08 ` François Dumont
2021-11-06 13:51 ` François Dumont
2021-11-08 21:36 ` François Dumont
2021-11-09 16:25 ` Jonathan Wakely
2021-11-10 5:47 ` François Dumont
2021-11-10 9:38 ` Jonathan Wakely
2021-11-15 18:16 ` François Dumont
2021-11-10 11:55 ` Jonathan Wakely
2021-11-11 20:41 ` Jonathan Wakely
2021-11-11 21:33 ` François Dumont
2021-11-11 22:01 ` Jonathan Wakely
2021-11-10 0:05 ` H.J. Lu
2021-11-10 5:44 ` François Dumont
2021-11-10 7:26 ` Jonathan Wakely
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4eec3fb9-851e-3e4e-f9f4-1110db3af747@gmail.com \
--to=frs.dumont@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).