diff mbox series

[committed] libstdc++: Destroy allocators in re-inserted container nodes [PR114401]

Message ID 20240322225257.369459-1-jwakely@redhat.com
State New
Headers show
Series [committed] libstdc++: Destroy allocators in re-inserted container nodes [PR114401] | expand

Commit Message

Jonathan Wakely March 22, 2024, 10:51 p.m. UTC 
Tested aarch64-linux. Pushed to trunk.

This should be backported to all branches, as the failure to destroy the
allocators in the re-inserted nodes results in potential resource leaks.

-- >8 --

The allocator objects in container node handles were not being destroyed
after the node was re-inserted into a container. They are stored in a
union and so need to be explicitly destroyed when the node becomes
empty. The containers were zeroing the node handle's pointer, which
makes it empty, causing the handle's destructor to think there's nothign
to clean up.

Add a new member function to the node handle which destroys the
allocator and zeros the pointer. Change the containers to call that
instead of just changing the pointer manually.

We can also remove the _M_empty member of the union which is not
necessary.

libstdc++-v3/ChangeLog:

	PR libstdc++/114401
	* include/bits/hashtable.h (_Hashtable::_M_reinsert_node): Call
	release() on node handle instead of just zeroing its pointer.
	(_Hashtable::_M_reinsert_node_multi): Likewise.
	(_Hashtable::_M_merge_unique): Likewise.
	(_Hashtable::_M_merge_multi): Likewise.
	* include/bits/node_handle.h (_Node_handle_common::release()):
	New member function.
	(_Node_handle_common::_Optional_alloc::_M_empty): Remove
	unnecessary union member.
	(_Node_handle_common): Declare _Hashtable as a friend.
	* include/bits/stl_tree.h (_Rb_tree::_M_reinsert_node_unique):
	Call release() on node handle instead of just zeroing its
	pointer.
	(_Rb_tree::_M_reinsert_node_equal): Likewise.
	(_Rb_tree::_M_reinsert_node_hint_unique): Likewise.
	(_Rb_tree::_M_reinsert_node_hint_equal): Likewise.
	* testsuite/23_containers/multiset/modifiers/114401.cc: New test.
	* testsuite/23_containers/set/modifiers/114401.cc: New test.
	* testsuite/23_containers/unordered_multiset/modifiers/114401.cc: New test.
	* testsuite/23_containers/unordered_set/modifiers/114401.cc: New test.
---
 libstdc++-v3/include/bits/hashtable.h         |  12 +-
 libstdc++-v3/include/bits/node_handle.h       |  19 ++-
 libstdc++-v3/include/bits/stl_tree.h          |  12 +-
 .../multiset/modifiers/114401.cc              | 125 +++++++++++++++++
 .../23_containers/set/modifiers/114401.cc     | 125 +++++++++++++++++
 .../unordered_multiset/modifiers/114401.cc    | 126 ++++++++++++++++++
 .../unordered_set/modifiers/114401.cc         | 126 ++++++++++++++++++
 7 files changed, 530 insertions(+), 15 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/23_containers/multiset/modifiers/114401.cc
 create mode 100644 libstdc++-v3/testsuite/23_containers/set/modifiers/114401.cc
 create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/114401.cc
 create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/114401.cc
diff mbox series

Patch

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index c3ef7a0a3d5..cd3e1ac297c 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -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.
diff --git a/libstdc++-v3/include/bits/node_handle.h b/libstdc++-v3/include/bits/node_handle.h
index bd9b1afc8d7..2d8e47c5062 100644
--- a/libstdc++-v3/include/bits/node_handle.h
+++ b/libstdc++-v3/include/bits/node_handle.h
@@ -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
     };
 
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 6f470f04f6a..978093fc587 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -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)
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/modifiers/114401.cc b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/114401.cc
new file mode 100644
index 00000000000..630e18e287c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/114401.cc
@@ -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();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/modifiers/114401.cc b/libstdc++-v3/testsuite/23_containers/set/modifiers/114401.cc
new file mode 100644
index 00000000000..f0a06a8c1a2
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/114401.cc
@@ -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();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/114401.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/114401.cc
new file mode 100644
index 00000000000..0a6ea77bf31
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/114401.cc
@@ -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();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/114401.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/114401.cc
new file mode 100644
index 00000000000..3ae2f2d5b5c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/114401.cc
@@ -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();
+}