From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2181) id AB0D6384773E; Wed, 3 Apr 2024 10:46:49 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AB0D6384773E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1712141209; bh=G136r03ro5oIV7nP5g2tXKMpyYS8b32FS9nZbDy93kM=; h=From:To:Subject:Date:From; b=qmf/VV2JpyMxxylCVJmD5fVQW4I4bpUZbVC4aK0v7hepJir1rtWYR3nYD7WCsT5wo IcwurOLFTeiIJJh6qXrz5v0Lwkey8+lrRoFjUWBCfQfIr7ZUxkkoRkIeVCb5v7EJI/ lDhvsCKYtS39ADnXl+z6cb7CIpF7RCRkSfFuso10= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Jonathan Wakely To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r13-8570] libstdc++: Destroy allocators in re-inserted container nodes [PR114401] X-Act-Checkin: gcc X-Git-Author: Jonathan Wakely X-Git-Refname: refs/heads/releases/gcc-13 X-Git-Oldrev: 87ec5b369eed205dfe6802afaaec3986b246ade9 X-Git-Newrev: 47ebdbe5bf71d9eb260359b6aceb5cb071d97acd Message-Id: <20240403104649.AB0D6384773E@sourceware.org> Date: Wed, 3 Apr 2024 10:46:49 +0000 (GMT) List-Id: https://gcc.gnu.org/g:47ebdbe5bf71d9eb260359b6aceb5cb071d97acd commit r13-8570-g47ebdbe5bf71d9eb260359b6aceb5cb071d97acd Author: Jonathan Wakely Date: Thu Mar 21 13:25:15 2024 +0000 libstdc++: Destroy allocators in re-inserted container nodes [PR114401] 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 nothing 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. (cherry picked from commit c2e28df90a1640cebadef6c6c8ab5ea964071bb1) Diff: --- libstdc++-v3/include/bits/hashtable.h | 10 +- libstdc++-v3/include/bits/node_handle.h | 19 +++- libstdc++-v3/include/bits/stl_tree.h | 10 +- .../23_containers/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, 528 insertions(+), 13 deletions(-) diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index dd3e655866a..1b5d0a7f42f 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -996,7 +996,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // DR 1189. // reserve, if present, comes from _Rehash_base. -#if __cplusplus > 201402L +#if __cplusplus > 201404L /// Re-insert an extracted node into a container with unique keys. insert_return_type _M_reinsert_node(node_type&& __nh) @@ -1021,7 +1021,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; } } @@ -1041,7 +1041,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; } @@ -1123,7 +1123,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) @@ -1150,7 +1150,7 @@ _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 diff --git a/libstdc++-v3/include/bits/node_handle.h b/libstdc++-v3/include/bits/node_handle.h index 8904a5ac496..79afa547ec4 100644 --- a/libstdc++-v3/include/bits/node_handle.h +++ b/libstdc++-v3/include/bits/node_handle.h @@ -168,6 +168,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; @@ -219,9 +229,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __tmp; } - struct _Empty { }; - - [[__no_unique_address__]] _Empty _M_empty; [[__no_unique_address__]] _NodeAlloc _M_alloc; }; @@ -231,6 +238,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Compare, typename _ValueAlloc> friend class _Rb_tree; + template + friend class _Hashtable; + /// @endcond }; diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index f870f3dfa53..c3ecbeb1379 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -1435,7 +1435,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_move_assign(_Rb_tree&, false_type); #endif -#if __cplusplus > 201402L +#if __cplusplus > 201404L public: /// Re-insert an extracted node. insert_return_type @@ -1453,7 +1453,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 @@ -1481,7 +1481,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; } @@ -1500,7 +1500,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); @@ -1523,7 +1523,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; } 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 +#include +#include + +template +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(identity)) { } + + template + Alloc(const Alloc a) : id(a.id) { } + + T* allocate(std::size_t n) { return std::allocator().allocate(n); } + void deallocate(T* p, std::size_t n) { std::allocator().deallocate(p, n); } + + template + friend bool + operator==(const Alloc& a, const Alloc& a2) + { return a.id == a2.id; } + + template + friend bool + operator!=(const Alloc& a, const Alloc& a2) + { return !(a == a2); } + + std::shared_ptr id; +}; + +using test_type = std::multiset, Alloc>; + +void +test_node_ops() +{ + test_type s1({1,3,5}, Alloc(1)); + test_type s2({2,4,6,8}, Alloc(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 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 +#include +#include + +template +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(identity)) { } + + template + Alloc(const Alloc a) : id(a.id) { } + + T* allocate(std::size_t n) { return std::allocator().allocate(n); } + void deallocate(T* p, std::size_t n) { std::allocator().deallocate(p, n); } + + template + friend bool + operator==(const Alloc& a, const Alloc& a2) + { return a.id == a2.id; } + + template + friend bool + operator!=(const Alloc& a, const Alloc& a2) + { return !(a == a2); } + + std::shared_ptr id; +}; + +using test_type = std::set, Alloc>; + +void +test_node_ops() +{ + test_type s1({1,3,5}, Alloc(1)); + test_type s2({2,4,6,8}, Alloc(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 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 +#include +#include + +template +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(identity)) { } + + template + Alloc(const Alloc a) : id(a.id) { } + + T* allocate(std::size_t n) { return std::allocator().allocate(n); } + void deallocate(T* p, std::size_t n) { std::allocator().deallocate(p, n); } + + template + friend bool + operator==(const Alloc& a, const Alloc& a2) + { return a.id == a2.id; } + + template + friend bool + operator!=(const Alloc& a, const Alloc& a2) + { return !(a == a2); } + + std::shared_ptr id; +}; + +using test_type + = std::unordered_multiset, std::equal_to, Alloc>; + +void +test_node_ops() +{ + test_type s1({1,3,5}, 3, Alloc(1)); + test_type s2({2,4,6,8}, 4, Alloc(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 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 +#include +#include + +template +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(identity)) { } + + template + Alloc(const Alloc a) : id(a.id) { } + + T* allocate(std::size_t n) { return std::allocator().allocate(n); } + void deallocate(T* p, std::size_t n) { std::allocator().deallocate(p, n); } + + template + friend bool + operator==(const Alloc& a, const Alloc& a2) + { return a.id == a2.id; } + + template + friend bool + operator!=(const Alloc& a, const Alloc& a2) + { return !(a == a2); } + + std::shared_ptr id; +}; + +using test_type + = std::unordered_set, std::equal_to, Alloc>; + +void +test_node_ops() +{ + test_type s1({1,3,5}, 3, Alloc(1)); + test_type s2({2,4,6,8}, 4, Alloc(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 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(); +}