1// Copyright (C) 2023 Christian Mazakas
2// Copyright (C) 2023 Joaquin M Lopez Munoz
3// Distributed under the Boost Software License, Version 1.0. (See accompanying
4// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6#include "helpers.hpp"
7
8#include <boost/unordered/concurrent_flat_map.hpp>
9#include <boost/unordered/concurrent_flat_set.hpp>
10
11test::seed_t initialize_seed{402031699};
12
13using test::default_generator;
14using test::limited_range;
15using test::sequential;
16
17using hasher = stateful_hash;
18using key_equal = stateful_key_equal;
19
20using map_type = boost::unordered::concurrent_flat_map<raii, raii,
21 hasher, key_equal, stateful_allocator<std::pair<raii const, raii> > >;
22using map2_type = boost::unordered::concurrent_flat_map<raii, raii,
23 std::hash<raii>, std::equal_to<raii>,
24 stateful_allocator<std::pair<raii const, raii> > >;
25
26using set_type = boost::unordered::concurrent_flat_set<raii, hasher,
27 key_equal, stateful_allocator<raii> >;
28using set2_type = boost::unordered::concurrent_flat_set<raii, std::hash<raii>,
29 std::equal_to<raii>, stateful_allocator<raii> >;
30
31map_type* test_map;
32map2_type* test_map2;
33auto test_maps=std::make_pair(x&: test_map,y&: test_map2);
34
35set_type* test_set;
36set2_type* test_set2;
37auto test_sets=std::make_pair(x&: test_set,y&: test_set2);
38
39struct
40{
41 template <class X1, class X2>
42 std::size_t operator()(X1& x1, X2& x2) const noexcept
43 {
44 return x1.merge(x2);
45 }
46} lvalue_merge;
47
48struct
49{
50 template <class X1, class X2>
51 std::size_t operator()(X1& x1, X2& x2) const noexcept
52 {
53 return x1.merge(std::move(x2));
54 }
55} rvalue_merge;
56
57namespace {
58 template <typename X, typename Y, class F, class GF>
59 void merge_tests(
60 std::pair<X*, Y*>, F merger, GF gen_factory, test::random_generator rg)
61 {
62 using value_type = typename X::value_type;
63 static constexpr auto value_type_cardinality =
64 value_cardinality<value_type>::value;
65 using allocator_type = typename X::allocator_type;
66
67 auto gen = gen_factory.template get<X>();
68 auto values = make_random_values(1024 * 8, [&] { return gen(rg); });
69 auto reference_cont = reference_container<X>(values.begin(), values.end());
70
71 {
72 raii::reset_counts();
73
74 X x(values.size(), hasher(1), key_equal(2), allocator_type(3));
75
76 auto const old_cc = +raii::copy_constructor;
77
78 std::atomic<unsigned long long> expected_copies{0};
79 std::atomic<unsigned long long> num_merged{0};
80
81 thread_runner(values, [&x, &expected_copies, &num_merged, merger](
82 boost::span<value_type> s) {
83 Y y(s.size(), allocator_type(3));
84 for (auto const& v : s) {
85 y.insert(v);
86 }
87 expected_copies += value_type_cardinality * y.size();
88
89 BOOST_TEST(x.get_allocator() == y.get_allocator());
90 num_merged += merger(x, y);
91 });
92
93 BOOST_TEST_EQ(raii::copy_constructor, old_cc + expected_copies);
94 BOOST_TEST_EQ(
95 raii::move_constructor,
96 value_type_cardinality * reference_cont.size());
97 BOOST_TEST_EQ(+num_merged, reference_cont.size());
98
99 test_fuzzy_matches_reference(x, reference_cont, rg);
100 }
101 check_raii_counts();
102 }
103
104 template <typename X, typename Y, class GF>
105 void insert_and_merge_tests(
106 std::pair<X*, Y*>, GF gen_factory, test::random_generator rg)
107 {
108 static constexpr auto value_type_cardinality =
109 value_cardinality<typename X::value_type>::value;
110 using allocator_type = typename X::allocator_type;
111
112 auto gen = gen_factory.template get<X>();
113 auto vals1 = make_random_values(1024 * 8, [&] { return gen(rg); });
114 auto vals2 = make_random_values(1024 * 4, [&] { return gen(rg); });
115
116 auto reference_cont = reference_container<X>();
117 reference_cont.insert(vals1.begin(), vals1.end());
118 reference_cont.insert(vals2.begin(), vals2.end());
119
120 {
121 raii::reset_counts();
122
123 X x1(2 * vals1.size(), hasher(1), key_equal(2), allocator_type(3));
124
125 Y x2(2 * vals1.size(), allocator_type(3));
126
127 std::thread t1, t2, t3;
128 boost::compat::latch l(2);
129
130 std::mutex m;
131 std::condition_variable cv;
132 std::atomic_bool done1{false}, done2{false};
133 std::atomic<unsigned long long> num_merges{0};
134 std::atomic<unsigned long long> call_count{0};
135 bool ready = false;
136
137 auto const old_mc = +raii::move_constructor;
138 BOOST_TEST_EQ(old_mc, 0u);
139
140 t1 = std::thread([&x1, &vals1, &l, &done1, &cv, &ready, &m] {
141 l.arrive_and_wait();
142
143 for (std::size_t idx = 0; idx < vals1.size(); ++idx) {
144 auto const& val = vals1[idx];
145 x1.insert(val);
146
147 if (idx % (vals1.size() / 128) == 0) {
148 {
149 std::unique_lock<std::mutex> lk(m);
150 ready = true;
151 }
152 cv.notify_all();
153 std::this_thread::yield();
154 }
155 }
156
157 done1 = true;
158 {
159 std::unique_lock<std::mutex> lk(m);
160 ready = true;
161 }
162 cv.notify_all();
163 });
164
165 t2 = std::thread([&x2, &vals2, &l, &done2, &cv, &m, &ready] {
166 l.arrive_and_wait();
167
168 for (std::size_t idx = 0; idx < vals2.size(); ++idx) {
169 auto const& val = vals2[idx];
170 x2.insert(val);
171 if (idx % 100 == 0) {
172 std::this_thread::yield();
173 }
174 }
175
176 done2 = true;
177 {
178 std::unique_lock<std::mutex> lk(m);
179 ready = true;
180 }
181 cv.notify_all();
182 });
183
184 t3 = std::thread(
185 [&x1, &x2, &m, &cv, &done1, &done2, &num_merges, &call_count, &ready] {
186 while (x1.empty() && x2.empty()) {
187 }
188
189 do {
190 {
191 std::unique_lock<std::mutex> lk(m);
192 cv.wait(lk, [&ready] { return ready; });
193 ready = false;
194 }
195
196 num_merges += x1.merge(x2);
197 std::this_thread::yield();
198 num_merges += x2.merge(x1);
199
200 call_count += 1;
201
202 } while (!done1 || !done2);
203
204 BOOST_TEST(done1);
205 BOOST_TEST(done2);
206 });
207
208 t1.join();
209 t2.join();
210 t3.join();
211
212 if (num_merges > 0) {
213 // num merges is 0 most commonly in the cast of the limited_range
214 // generator as both maps will contains keys from 0 to 99
215 BOOST_TEST_EQ(
216 +raii::move_constructor, value_type_cardinality * num_merges);
217 BOOST_TEST_GE(call_count, 1u);
218 }
219
220 x1.merge(x2);
221 test_fuzzy_matches_reference(x1, reference_cont, rg);
222 }
223
224 check_raii_counts();
225 }
226
227} // namespace
228
229// clang-format off
230UNORDERED_TEST(
231 merge_tests,
232 ((test_maps)(test_sets))
233 ((lvalue_merge)(rvalue_merge))
234 ((value_type_generator_factory))
235 ((default_generator)(sequential)(limited_range)))
236
237UNORDERED_TEST(
238 insert_and_merge_tests,
239 ((test_maps)(test_sets))
240 ((value_type_generator_factory))
241 ((default_generator)(sequential)(limited_range)))
242// clang-format on
243
244RUN_TESTS()
245

source code of boost/libs/unordered/test/cfoa/merge_tests.cpp