[11/12] libstdc++: Simplify _Hashtable merge functions

Message ID	20241108154548.813315-12-jwakely@redhat.com
State	New
Headers	show Return-Path: <gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org> DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 5202A3858D21 From: Jonathan Wakely <jwakely@redhat.com> To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH 11/12] libstdc++: Simplify _Hashtable merge functions Date: Fri, 8 Nov 2024 15:30:21 +0000 Message-ID: <20241108154548.813315-12-jwakely@redhat.com> In-Reply-To: <20241108154548.813315-1-jwakely@redhat.com> References: <20241108154548.813315-1-jwakely@redhat.com> MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 8bit Precedence: list Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org
Series	libstdc++: Refactor _Hashtable class \| expand [0/12] libstdc++: Refactor _Hashtable class [01/12] libstdc++: Refactor _Hashtable::operator=(initializer_list<value_type>) [02/12] libstdc++: Allow unordered_set assignment to assign to existing nodes [03/12] libstdc++: Refactor Hashtable insertion [PR115285] [04/12] libstdc++: Refactor Hashtable erasure [05/12] libstdc++: Add _Hashtable::_M_assign for the common case [06/12] libstdc++: Replace _Hashtable::__fwd_value_for with cast [07/12] libstdc++: Use RAII in _Hashtable [08/12] libstdc++: Remove _Insert base class from _Hashtable [09/12] libstdc++: Remove _Equality base class from _Hashtable [10/12] libstdc++: Remove _Hashtable_base::_S_equals [11/12] libstdc++: Simplify _Hashtable merge functions [12/12] libstdc++: Add _Hashtable::_M_locate(const key_type&)

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 7b0a684a2d2..aca431ae216 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -1212,6 +1212,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __nh; } + /// Merge from another container of the same type. + void + _M_merge_unique(_Hashtable& __src) + { + __glibcxx_assert(get_allocator() == __src.get_allocator()); + + auto __size = size(); + auto __n_elt = __src.size(); + size_type __first = 1; + // For a container of identical type we can use its private members. + auto __p = static_cast<__node_ptr>(&__src._M_before_begin); + while (__n_elt--) + { + const auto __prev = __p; + __p = __p->_M_next(); + const auto& __node = *__p; + const key_type& __k = _ExtractKey{}(__node._M_v()); + if (__size <= __small_size_threshold()) + { + auto __n = _M_begin(); + for (; __n; __n = __n->_M_next()) + if (this->_M_key_equals(__k, *__n)) + break; + if (__n) + continue; + } + + __hash_code __code + = _M_src_hash_code(__src.hash_function(), __k, __node); + size_type __bkt = _M_bucket_index(__code); + if (__size > __small_size_threshold()) + if (_M_find_node(__bkt, __k, __code) != nullptr) + continue; + + __hash_code __src_code = __src.hash_function()(__k); + size_type __src_bkt = __src._M_bucket_index(__src_code); + auto __nh = __src._M_extract_node(__src_bkt, __prev); + _M_insert_unique_node(__bkt, __code, __nh._M_ptr, + __first * __n_elt + 1); + __nh.release(); + __first = 0; + ++__size; + __p = __prev; + } + } + /// Merge from a compatible container into one with unique keys. template<typename _Compatible_Hashtable> void @@ -1221,46 +1267,68 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); + auto __size = size(); auto __n_elt = __src.size(); + size_type __first = 1; + // For a compatible container we can only use the public API, + // so cbegin(), cend(), hash_function(), and extract(iterator). for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { + --__n_elt; auto __pos = __i++; - const size_type __size = size(); const key_type& __k = _ExtractKey{}(*__pos); if (__size <= __small_size_threshold()) { - bool __found = false; - for (auto __n = _M_begin(); __n; __n = __n->_M_next()) + auto __n = _M_begin(); + for (; __n; __n = __n->_M_next()) if (this->_M_key_equals(__k, *__n)) - { - __found = true; - break; - } - - if (__found) - { - if (__n_elt != 1) - --__n_elt; - continue; - } + break; + if (__n) + continue; } __hash_code __code = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur); size_type __bkt = _M_bucket_index(__code); - if (__size <= __small_size_threshold() - || _M_find_node(__bkt, __k, __code) == nullptr) - { - auto __nh = __src.extract(__pos); - _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt); - __nh.release(); - __n_elt = 1; - } - else if (__n_elt != 1) - --__n_elt; + if (__size > __small_size_threshold()) + if (_M_find_node(__bkt, __k, __code) != nullptr) + continue; + + auto __nh = __src.extract(__pos); + _M_insert_unique_node(__bkt, __code, __nh._M_ptr, + __first * __n_elt + 1); + __nh.release(); + __first = 0; + ++__size; } } + /// Merge from another container of the same type. + void + _M_merge_multi(_Hashtable& __src) + { + __glibcxx_assert(get_allocator() == __src.get_allocator()); + + if (__src.size() == 0) [[__unlikely__]] + return; + + __node_ptr __hint = nullptr; + this->reserve(size() + __src.size()); + // For a container of identical type we can use its private members. + auto __prev = static_cast<__node_ptr>(&__src._M_before_begin); + do + { + const auto& __node = *__prev->_M_next(); + const key_type& __k = _ExtractKey{}(__node._M_v()); + __hash_code __code = this->_M_hash_code(__k); + size_type __src_bkt = __src._M_bucket_index(__node); + auto __nh = __src._M_extract_node(__src_bkt, __prev); + __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur; + __nh.release(); + } + while (__prev->_M_nxt != nullptr); + } + /// Merge from a compatible container into one with equivalent keys. template<typename _Compatible_Hashtable> void @@ -1272,6 +1340,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_ptr __hint = nullptr; this->reserve(size() + __src.size()); + // For a compatible container we can only use the public API, + // so cbegin(), cend(), hash_function(), and extract(iterator). for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { auto __pos = __i++; diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 3b472534c66..9bc1cca7e1b 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -821,6 +821,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) { + if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>) + if (std::__addressof(__source) == this) [[__unlikely__]] + return; + using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>; _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); } @@ -828,7 +832,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _H2, typename _P2> void merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) - { merge(__source); } + { + using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>; + _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); + } template<typename _H2, typename _P2> void @@ -1764,6 +1771,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) { + if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>) + if (std::__addressof(__source) == this) [[__unlikely__]] + return; + using _Merge_helper = _Hash_merge_helper<unordered_multimap, _H2, _P2>; _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); @@ -1772,7 +1783,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _H2, typename _P2> void merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) - { merge(__source); } + { + using _Merge_helper + = _Hash_merge_helper<unordered_multimap, _H2, _P2>; + _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); + } template<typename _H2, typename _P2> void diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 08dcfa2a9b9..a76769df9b9 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -602,6 +602,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) { + if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>) + if (std::__addressof(__source) == this) [[__unlikely__]] + return; + using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>; _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); } @@ -609,7 +613,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _H2, typename _P2> void merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) - { merge(__source); } + { + using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>; + _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); + } template<typename _H2, typename _P2> void @@ -1452,6 +1459,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) { + if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>) + if (std::__addressof(__source) == this) [[__unlikely__]] + return; + using _Merge_helper = _Hash_merge_helper<unordered_multiset, _H2, _P2>; _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); @@ -1460,7 +1471,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _H2, typename _P2> void merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) - { merge(__source); } + { + using _Merge_helper + = _Hash_merge_helper<unordered_multiset, _H2, _P2>; + _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); + } template<typename _H2, typename _P2> void diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc index df9d79ebeaa..c84ef8cb6f7 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc @@ -290,6 +290,133 @@ test06() VERIFY( c2.empty() ); } +void +test07() +{ + test_type c1{ {1, 1}, {3, 3}, {5, 5} }; + test_type c2{ {2, 2}, {4, 4}, {6, 6} }; + const test_type c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + const test_type c4 = c1; + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c3 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); + + test_type c5 = c3; + c2.merge(c5); + VERIFY( c2 == c3 ); + VERIFY( c5 == c3 ); + + c5.emplace(9, 9); + c2.merge(c5); + VERIFY( c2.size() == c3.size() + 1 ); + VERIFY( c5 == c3 ); +} + +void +test08() +{ + test_type c1{ {1, 1}, {3, 3}, {5, 5} }; + std::unordered_map<int, int, xhash<int>, equal> c2{ {2, 2}, {4, 4}, {6, 6} }; + const auto c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + const test_type c4 = c1; + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( equal_elements(c1, c3) ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); + + auto c5 = c3; + c2.merge(c5); + VERIFY( c2 == c3 ); + VERIFY( c5 == c3 ); + + c5.emplace(9, 9); + c2.merge(c5); + VERIFY( c2.size() == c3.size() + 1 ); + VERIFY( c5 == c3 ); +} + +void +test09() +{ + struct stateful_hash + { + size_t seed = 0; + + auto operator()(const int& i) const noexcept + { return std::hash<int>()(i) + seed; } + }; + + using map_type = std::unordered_map<int, int, stateful_hash>; + map_type c1({ {1, 1}, {3, 3}, {5, 5} }, 0, stateful_hash{1}); + map_type c2({ {2, 2}, {4, 4}, {6, 6} }, 0, stateful_hash{2}); + const auto c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c3 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); + + test_type c5{ {-1, 1}, {-3, 3}, {-5, 5} }; + c2.merge(c5); + VERIFY( c2.size() == 6 ); + VERIFY( c5.empty() ); + auto c6 = c3; + c6.merge(c2); + VERIFY( c6.size() == 6 ); + VERIFY( c2.size() == 3 ); +} + int main() { @@ -299,4 +426,7 @@ main() test04(); test05(); test06(); + test07(); + test08(); + test09(); } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc index 3e2b26380f9..bf03c4cc34e 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc @@ -105,6 +105,122 @@ test04() VERIFY( c2.empty() ); } +void +test07() +{ + test_type c1{ {1, 1}, {3, 3}, {5, 5} }; + test_type c2{ {2, 2}, {4, 4}, {6, 6} }; + const test_type c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + const test_type c4 = c1; + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c3 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); + + auto c5 = c4; + c2.merge(c5); + VERIFY( c2.size() == 9 ); + VERIFY( c5.empty() ); + + c5 = c4; + c5.emplace(9, 9); + c2.merge(c5); + VERIFY( c2.size() == 16 ); + VERIFY( c5.empty() ); +} + +void +test08() +{ + test_type c1{ {1, 1}, {3, 3}, {5, 5} }; + std::unordered_map<int, int, hash, equal> c2{ {2, 2}, {4, 4}, {6, 6} }; + const auto c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + const test_type c4 = c1; + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); +} + +void +test09() +{ + struct stateful_hash + { + size_t seed = 0; + + auto operator()(const int& i) const noexcept + { return std::hash<int>()(i) + seed; } + }; + + using map_type = std::unordered_multimap<int, int, stateful_hash>; + map_type c1({ {1, 1}, {3, 3}, {5, 5} }, 0, stateful_hash{1}); + map_type c2({ {2, 2}, {4, 4}, {6, 6} }, 0, stateful_hash{2}); + const auto c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c3 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); + + test_type c4{ {-1, 0}, {-3, 0}, {-5, 0} }; + c2.merge(c4); + VERIFY( c2.size() == 6 ); + VERIFY( c4.empty() ); + auto c6 = c3; + c6.merge(c2); + VERIFY( c6.size() == 9 ); + VERIFY( c2.size() == 0 ); +} int main() { @@ -112,4 +228,7 @@ main() test02(); test03(); test04(); + test07(); + test08(); + test09(); } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc index 41f98f28249..291b4866281 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc @@ -126,6 +126,124 @@ test05() VERIFY( c2.empty() ); } +void +test07() +{ + test_type c1{ 1, 3, 5 }; + test_type c2{ 2, 4, 6 }; + const test_type c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + const test_type c4 = c1; + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c3 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); + + auto c5 = c4; + c2.merge(c5); + VERIFY( c2.size() == 9 ); + VERIFY( c5.empty() ); + + c5 = c4; + c5.emplace(9); + c2.merge(c5); + VERIFY( c2.size() == 16 ); + VERIFY( c5.empty() ); + +} + +void +test08() +{ + test_type c1{ 1, 3, 5 }; + std::unordered_set<int, hash, equal> c2{ 2, 4, 6 }; + const auto c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + const test_type c4 = c1; + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); +} + +void +test09() +{ + struct stateful_hash + { + size_t seed = 0; + + auto operator()(const int& i) const noexcept + { return std::hash<int>()(i) + seed; } + }; + + using set_type = std::unordered_multiset<int, stateful_hash>; + set_type c1({ 1, 3, 5 }, 0, stateful_hash{1}); + set_type c2({ 2, 4, 6 }, 0, stateful_hash{2}); + const auto c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c3 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); + + test_type c4{ -1, -3, -5 }; + c2.merge(c4); + VERIFY( c2.size() == 6 ); + VERIFY( c4.empty() ); + auto c6 = c3; + c6.merge(c2); + VERIFY( c6.size() == 9 ); + VERIFY( c2.size() == 0 ); +} + int main() { @@ -134,4 +252,7 @@ main() test03(); test04(); test05(); + test07(); + test08(); + test09(); } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc index 45fe3952ebb..6cf2c98d4b3 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc @@ -167,6 +167,131 @@ test04() VERIFY( c2.empty() ); } +void +test07() +{ + test_type c1{ 1, 3, 5 }; + test_type c2{ 2, 4, 6 }; + const test_type c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c3 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); + + test_type c4 = c3; + c2.merge(c4); + VERIFY( c2 == c3 ); + VERIFY( c4 == c3 ); + + c4.emplace(9); + c2.merge(c4); + VERIFY( c2.size() == c3.size() + 1 ); + VERIFY( c4 == c3 ); +} + +void +test08() +{ + test_type c1{ 1, 3, 5 }; + std::unordered_set<int, hash, equal> c2{ 2, 4, 6 }; + const auto c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( equal_elements(c1, c3) ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); + + auto c4 = c3; + c2.merge(c4); + VERIFY( c2 == c3 ); + VERIFY( c4 == c3 ); + + c4.emplace(9); + c2.merge(c4); + VERIFY( c2.size() == c3.size() + 1 ); + VERIFY( c4 == c3 ); +} + +void +test09() +{ + struct stateful_hash + { + size_t seed = 0; + + auto operator()(const int& i) const noexcept + { return std::hash<int>()(i) + seed; } + }; + + using set_type = std::unordered_set<int, stateful_hash>; + set_type c1({ 1, 3, 5 }, 0, stateful_hash{1}); + set_type c2({ 2, 4, 6 }, 0, stateful_hash{2}); + const auto c3 = c2; + + c1.merge(c2); + VERIFY( c1.size() == 6 ); + VERIFY( c2.empty() ); + + c2 = c3; + c1.clear(); + c1.merge(std::move(c2)); + VERIFY( c1 == c3 ); + VERIFY( c2.empty() ); + + c2.merge(std::move(c1)); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c1); + VERIFY( c1.empty() ); + VERIFY( c2 == c3 ); + + c2.merge(c2); + VERIFY( c2 == c3 ); + + test_type c4{ -1, -3, -5 }; + c2.merge(c4); + VERIFY( c2.size() == 6 ); + VERIFY( c4.empty() ); + auto c6 = c3; + c6.merge(c2); + VERIFY( c6.size() == 6 ); + VERIFY( c2.size() == 3 ); +} + int main() { @@ -174,4 +299,7 @@ main() test02(); test03(); test04(); + test07(); + test08(); + test09(); }

[11/12] libstdc++: Simplify _Hashtable merge functions

Commit Message

Patch