@@ -1036,7 +1036,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// DR 1189.
// reserve, if present, comes from _Rehash_base.
-#if __cplusplus > 201402L
+#if __glibcxx_node_extract // >= C++17
/// Re-insert an extracted node into a container with unique keys.
insert_return_type
_M_reinsert_node(node_type&& __nh)
@@ -1078,7 +1078,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__ret.position
= _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
- __nh._M_ptr = nullptr;
+ __nh.release();
__ret.inserted = true;
}
}
@@ -1098,7 +1098,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto __code = this->_M_hash_code(__k);
auto __ret
= _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
- __nh._M_ptr = nullptr;
+ __nh.release();
return __ret;
}
@@ -1200,7 +1200,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
auto __nh = __src.extract(__pos);
_M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
- __nh._M_ptr = nullptr;
+ __nh.release();
__n_elt = 1;
}
else if (__n_elt != 1)
@@ -1227,10 +1227,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
= _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;
- __nh._M_ptr = nullptr;
+ __nh.release();
}
}
-#endif // C++17
+#endif // C++17 __glibcxx_node_extract
private:
// Helper rehash method used when keys are unique.
@@ -169,6 +169,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_ptr = nullptr;
}
+ // Destroys the allocator. Does not deallocate or destroy the node.
+ // Precondition: !empty()
+ // Postcondition: empty()
+ void
+ release() noexcept
+ {
+ _M_alloc.release();
+ _M_ptr = nullptr;
+ }
+
protected:
typename _AllocTraits::pointer _M_ptr;
@@ -220,9 +230,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __tmp;
}
- struct _Empty { };
-
- [[__no_unique_address__]] _Empty _M_empty;
[[__no_unique_address__]] _NodeAlloc _M_alloc;
};
@@ -232,6 +239,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Compare, typename _ValueAlloc>
friend class _Rb_tree;
+ template<typename _Key2, typename _Value2, typename _ValueAlloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
+ friend class _Hashtable;
+
/// @endcond
};
@@ -1431,7 +1431,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_move_assign(_Rb_tree&, false_type);
#endif
-#if __cplusplus > 201402L
+#if __glibcxx_node_extract // >= C++17
public:
/// Re-insert an extracted node.
insert_return_type
@@ -1449,7 +1449,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__ret.position
= _M_insert_node(__res.first, __res.second, __nh._M_ptr);
- __nh._M_ptr = nullptr;
+ __nh.release();
__ret.inserted = true;
}
else
@@ -1477,7 +1477,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
else
__ret = _M_insert_equal_lower_node(__nh._M_ptr);
- __nh._M_ptr = nullptr;
+ __nh.release();
}
return __ret;
}
@@ -1496,7 +1496,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__res.second)
{
__ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
- __nh._M_ptr = nullptr;
+ __nh.release();
}
else
__ret = iterator(__res.first);
@@ -1519,7 +1519,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
else
__ret = _M_insert_equal_lower_node(__nh._M_ptr);
- __nh._M_ptr = nullptr;
+ __nh.release();
}
return __ret;
}
@@ -1595,7 +1595,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
}
}
-#endif // C++17
+#endif // C++17 node_extract
friend bool
operator==(const _Rb_tree& __x, const _Rb_tree& __y)
new file mode 100644
@@ -0,0 +1,125 @@
+// { dg-do run { target c++17 } }
+
+// PR libstdc++/114401 allocator destructor omitted when reinserting node_handle
+
+#include <set>
+#include <memory>
+#include <testsuite_hooks.h>
+
+template<typename T>
+struct Alloc
+{
+ using value_type = T;
+ using propagate_on_container_copy_assignment = std::true_type;
+ using propagate_on_container_move_assignment = std::true_type;
+ using propagate_on_container_swap = std::true_type;
+
+ Alloc(int identity) : id(std::make_shared<int>(identity)) { }
+
+ template<typename U>
+ Alloc(const Alloc<U> a) : id(a.id) { }
+
+ T* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }
+ void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }
+
+ template<typename U>
+ friend bool
+ operator==(const Alloc& a, const Alloc<U>& a2)
+ { return a.id == a2.id; }
+
+ template<typename U>
+ friend bool
+ operator!=(const Alloc& a, const Alloc<U>& a2)
+ { return !(a == a2); }
+
+ std::shared_ptr<int> id;
+};
+
+using test_type = std::multiset<int, std::less<int>, Alloc<int>>;
+
+void
+test_node_ops()
+{
+ test_type s1({1,3,5}, Alloc<int>(1));
+ test_type s2({2,4,6,8}, Alloc<int>(2));
+ VERIFY( s1.get_allocator() != s2.get_allocator() );
+
+ auto node_a = s1.extract(1);
+ VERIFY( ! node_a.empty() );
+ VERIFY( node_a.get_allocator() == s1.get_allocator() );
+
+ node_a = std::move(node_a); // self-move
+ VERIFY( node_a.empty() );
+
+ swap(node_a, node_a); // self-swap
+ VERIFY( node_a.empty() );
+
+ auto node_b = s2.extract(2);
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ node_a = std::move(node_b); // empty = !empty
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.empty() );
+
+ swap(node_a, node_b); // swap(!empty, empty)
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ swap(node_a, node_b); // swap(empty, !empty)
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.empty() );
+
+ node_a = s1.extract(3); // !empty = !empty
+ VERIFY( node_a.get_allocator() == s1.get_allocator() );
+ node_b = s2.extract(0); // empty = empty
+ VERIFY( node_b.empty() );
+ node_b = s2.extract(6); // empty = !empty
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ swap(node_a, node_b); // swap(!empty, !empty)
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.get_allocator() == s1.get_allocator() );
+
+ node_a = {};
+ node_b = std::move(node_a); // !empty = empty
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.empty() );
+
+ swap(node_a, node_b); // swap(empty, empty)
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.empty() );
+}
+
+void
+test_alloc_lifetime()
+{
+ Alloc<int> a(1);
+ test_type s({1,2,3}, a);
+ VERIFY( a.id.use_count() == 2 ); // a and the copy in s
+
+ s.insert(s.extract(1));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.insert(s.begin(), s.extract(2));
+ VERIFY( a.id.use_count() == 2 );
+
+ auto node = s.extract(1);
+ VERIFY( a.id.use_count() == 3 );
+ node = s.extract(0);
+ VERIFY( a.id.use_count() == 2 );
+
+ s.insert(std::move(node));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.merge(test_type(s));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.merge(test_type({4,5,6}, a));
+ VERIFY( a.id.use_count() == 2 );
+}
+
+int main()
+{
+ test_node_ops();
+ test_alloc_lifetime();
+}
new file mode 100644
@@ -0,0 +1,125 @@
+// { dg-do run { target c++17 } }
+
+// PR libstdc++/114401 allocator destructor omitted when reinserting node_handle
+
+#include <set>
+#include <memory>
+#include <testsuite_hooks.h>
+
+template<typename T>
+struct Alloc
+{
+ using value_type = T;
+ using propagate_on_container_copy_assignment = std::true_type;
+ using propagate_on_container_move_assignment = std::true_type;
+ using propagate_on_container_swap = std::true_type;
+
+ Alloc(int identity) : id(std::make_shared<int>(identity)) { }
+
+ template<typename U>
+ Alloc(const Alloc<U> a) : id(a.id) { }
+
+ T* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }
+ void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }
+
+ template<typename U>
+ friend bool
+ operator==(const Alloc& a, const Alloc<U>& a2)
+ { return a.id == a2.id; }
+
+ template<typename U>
+ friend bool
+ operator!=(const Alloc& a, const Alloc<U>& a2)
+ { return !(a == a2); }
+
+ std::shared_ptr<int> id;
+};
+
+using test_type = std::set<int, std::less<int>, Alloc<int>>;
+
+void
+test_node_ops()
+{
+ test_type s1({1,3,5}, Alloc<int>(1));
+ test_type s2({2,4,6,8}, Alloc<int>(2));
+ VERIFY( s1.get_allocator() != s2.get_allocator() );
+
+ auto node_a = s1.extract(1);
+ VERIFY( ! node_a.empty() );
+ VERIFY( node_a.get_allocator() == s1.get_allocator() );
+
+ node_a = std::move(node_a); // self-move
+ VERIFY( node_a.empty() );
+
+ swap(node_a, node_a); // self-swap
+ VERIFY( node_a.empty() );
+
+ auto node_b = s2.extract(2);
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ node_a = std::move(node_b); // empty = !empty
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.empty() );
+
+ swap(node_a, node_b); // swap(!empty, empty)
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ swap(node_a, node_b); // swap(empty, !empty)
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.empty() );
+
+ node_a = s1.extract(3); // !empty = !empty
+ VERIFY( node_a.get_allocator() == s1.get_allocator() );
+ node_b = s2.extract(0); // empty = empty
+ VERIFY( node_b.empty() );
+ node_b = s2.extract(6); // empty = !empty
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ swap(node_a, node_b); // swap(!empty, !empty)
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.get_allocator() == s1.get_allocator() );
+
+ node_a = {};
+ node_b = std::move(node_a); // !empty = empty
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.empty() );
+
+ swap(node_a, node_b); // swap(empty, empty)
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.empty() );
+}
+
+void
+test_alloc_lifetime()
+{
+ Alloc<int> a(1);
+ test_type s({1,2,3}, a);
+ VERIFY( a.id.use_count() == 2 ); // a and the copy in s
+
+ s.insert(s.extract(1));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.insert(s.begin(), s.extract(2));
+ VERIFY( a.id.use_count() == 2 );
+
+ auto node = s.extract(1);
+ VERIFY( a.id.use_count() == 3 );
+ node = s.extract(0);
+ VERIFY( a.id.use_count() == 2 );
+
+ s.insert(std::move(node));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.merge(test_type(s));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.merge(test_type({4,5,6}, a));
+ VERIFY( a.id.use_count() == 2 );
+}
+
+int main()
+{
+ test_node_ops();
+ test_alloc_lifetime();
+}
new file mode 100644
@@ -0,0 +1,126 @@
+// { dg-do run { target c++17 } }
+
+// PR libstdc++/114401 allocator destructor omitted when reinserting node_handle
+
+#include <unordered_set>
+#include <memory>
+#include <testsuite_hooks.h>
+
+template<typename T>
+struct Alloc
+{
+ using value_type = T;
+ using propagate_on_container_copy_assignment = std::true_type;
+ using propagate_on_container_move_assignment = std::true_type;
+ using propagate_on_container_swap = std::true_type;
+
+ Alloc(int identity) : id(std::make_shared<int>(identity)) { }
+
+ template<typename U>
+ Alloc(const Alloc<U> a) : id(a.id) { }
+
+ T* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }
+ void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }
+
+ template<typename U>
+ friend bool
+ operator==(const Alloc& a, const Alloc<U>& a2)
+ { return a.id == a2.id; }
+
+ template<typename U>
+ friend bool
+ operator!=(const Alloc& a, const Alloc<U>& a2)
+ { return !(a == a2); }
+
+ std::shared_ptr<int> id;
+};
+
+using test_type
+ = std::unordered_multiset<int, std::hash<int>, std::equal_to<int>, Alloc<int>>;
+
+void
+test_node_ops()
+{
+ test_type s1({1,3,5}, 3, Alloc<int>(1));
+ test_type s2({2,4,6,8}, 4, Alloc<int>(2));
+ VERIFY( s1.get_allocator() != s2.get_allocator() );
+
+ auto node_a = s1.extract(1);
+ VERIFY( ! node_a.empty() );
+ VERIFY( node_a.get_allocator() == s1.get_allocator() );
+
+ node_a = std::move(node_a); // self-move
+ VERIFY( node_a.empty() );
+
+ swap(node_a, node_a); // self-swap
+ VERIFY( node_a.empty() );
+
+ auto node_b = s2.extract(2);
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ node_a = std::move(node_b); // empty = !empty
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.empty() );
+
+ swap(node_a, node_b); // swap(!empty, empty)
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ swap(node_a, node_b); // swap(empty, !empty)
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.empty() );
+
+ node_a = s1.extract(3); // !empty = !empty
+ VERIFY( node_a.get_allocator() == s1.get_allocator() );
+ node_b = s2.extract(0); // empty = empty
+ VERIFY( node_b.empty() );
+ node_b = s2.extract(6); // empty = !empty
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ swap(node_a, node_b); // swap(!empty, !empty)
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.get_allocator() == s1.get_allocator() );
+
+ node_a = {};
+ node_b = std::move(node_a); // !empty = empty
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.empty() );
+
+ swap(node_a, node_b); // swap(empty, empty)
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.empty() );
+}
+
+void
+test_alloc_lifetime()
+{
+ Alloc<int> a(1);
+ test_type s({1,2,3}, 3, a);
+ VERIFY( a.id.use_count() == 2 ); // a and the copy in s
+
+ s.insert(s.extract(1));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.insert(s.begin(), s.extract(2));
+ VERIFY( a.id.use_count() == 2 );
+
+ auto node = s.extract(1);
+ VERIFY( a.id.use_count() == 3 );
+ node = s.extract(0);
+ VERIFY( a.id.use_count() == 2 );
+
+ s.insert(std::move(node));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.merge(test_type(s));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.merge(test_type({4,5,6}, 3, a));
+ VERIFY( a.id.use_count() == 2 );
+}
+
+int main()
+{
+ test_node_ops();
+ test_alloc_lifetime();
+}
new file mode 100644
@@ -0,0 +1,126 @@
+// { dg-do run { target c++17 } }
+
+// PR libstdc++/114401 allocator destructor omitted when reinserting node_handle
+
+#include <unordered_set>
+#include <memory>
+#include <testsuite_hooks.h>
+
+template<typename T>
+struct Alloc
+{
+ using value_type = T;
+ using propagate_on_container_copy_assignment = std::true_type;
+ using propagate_on_container_move_assignment = std::true_type;
+ using propagate_on_container_swap = std::true_type;
+
+ Alloc(int identity) : id(std::make_shared<int>(identity)) { }
+
+ template<typename U>
+ Alloc(const Alloc<U> a) : id(a.id) { }
+
+ T* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }
+ void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }
+
+ template<typename U>
+ friend bool
+ operator==(const Alloc& a, const Alloc<U>& a2)
+ { return a.id == a2.id; }
+
+ template<typename U>
+ friend bool
+ operator!=(const Alloc& a, const Alloc<U>& a2)
+ { return !(a == a2); }
+
+ std::shared_ptr<int> id;
+};
+
+using test_type
+ = std::unordered_set<int, std::hash<int>, std::equal_to<int>, Alloc<int>>;
+
+void
+test_node_ops()
+{
+ test_type s1({1,3,5}, 3, Alloc<int>(1));
+ test_type s2({2,4,6,8}, 4, Alloc<int>(2));
+ VERIFY( s1.get_allocator() != s2.get_allocator() );
+
+ auto node_a = s1.extract(1);
+ VERIFY( ! node_a.empty() );
+ VERIFY( node_a.get_allocator() == s1.get_allocator() );
+
+ node_a = std::move(node_a); // self-move
+ VERIFY( node_a.empty() );
+
+ swap(node_a, node_a); // self-swap
+ VERIFY( node_a.empty() );
+
+ auto node_b = s2.extract(2);
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ node_a = std::move(node_b); // empty = !empty
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.empty() );
+
+ swap(node_a, node_b); // swap(!empty, empty)
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ swap(node_a, node_b); // swap(empty, !empty)
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.empty() );
+
+ node_a = s1.extract(3); // !empty = !empty
+ VERIFY( node_a.get_allocator() == s1.get_allocator() );
+ node_b = s2.extract(0); // empty = empty
+ VERIFY( node_b.empty() );
+ node_b = s2.extract(6); // empty = !empty
+ VERIFY( node_b.get_allocator() == s2.get_allocator() );
+
+ swap(node_a, node_b); // swap(!empty, !empty)
+ VERIFY( node_a.get_allocator() == s2.get_allocator() );
+ VERIFY( node_b.get_allocator() == s1.get_allocator() );
+
+ node_a = {};
+ node_b = std::move(node_a); // !empty = empty
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.empty() );
+
+ swap(node_a, node_b); // swap(empty, empty)
+ VERIFY( node_a.empty() );
+ VERIFY( node_b.empty() );
+}
+
+void
+test_alloc_lifetime()
+{
+ Alloc<int> a(1);
+ test_type s({1,2,3}, 3, a);
+ VERIFY( a.id.use_count() == 2 ); // a and the copy in s
+
+ s.insert(s.extract(1));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.insert(s.begin(), s.extract(2));
+ VERIFY( a.id.use_count() == 2 );
+
+ auto node = s.extract(1);
+ VERIFY( a.id.use_count() == 3 );
+ node = s.extract(0);
+ VERIFY( a.id.use_count() == 2 );
+
+ s.insert(std::move(node));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.merge(test_type(s));
+ VERIFY( a.id.use_count() == 2 );
+
+ s.merge(test_type({4,5,6}, 3, a));
+ VERIFY( a.id.use_count() == 2 );
+}
+
+int main()
+{
+ test_node_ops();
+ test_alloc_lifetime();
+}