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
11#include <boost/core/ignore_unused.hpp>
12
13namespace {
14 test::seed_t initialize_seed(3292023);
15
16 struct lvalue_eraser_type
17 {
18 template <class T, class X> void operator()(std::vector<T>& values, X& x)
19 {
20 static constexpr auto value_type_cardinality =
21 value_cardinality<typename X::value_type>::value;
22
23 std::atomic<std::uint64_t> num_erased{0};
24 auto const old_size = x.size();
25
26 auto const old_dc = +raii::default_constructor;
27 auto const old_cc = +raii::copy_constructor;
28 auto const old_mc = +raii::move_constructor;
29
30 auto const old_d = +raii::destructor;
31
32 BOOST_TEST_EQ(raii::default_constructor + raii::copy_constructor +
33 raii::move_constructor,
34 raii::destructor + value_type_cardinality * x.size());
35
36 thread_runner(values, [&values, &num_erased, &x](boost::span<T>) {
37 for (auto const& v : values) {
38 auto count = x.erase(get_key(v));
39 num_erased += count;
40 BOOST_TEST_LE(count, 1u);
41 BOOST_TEST_GE(count, 0u);
42 }
43 });
44
45 BOOST_TEST_EQ(raii::default_constructor, old_dc);
46 BOOST_TEST_EQ(raii::copy_constructor, old_cc);
47 BOOST_TEST_EQ(raii::move_constructor, old_mc);
48
49 BOOST_TEST_EQ(raii::destructor, old_d + value_type_cardinality * old_size);
50
51 BOOST_TEST_EQ(x.size(), 0u);
52 BOOST_TEST(x.empty());
53 BOOST_TEST_EQ(num_erased, old_size);
54 }
55 } lvalue_eraser;
56
57 struct transp_lvalue_eraser_type
58 {
59 template <class T, class X> void operator()(std::vector<T>& values, X& x)
60 {
61 static constexpr auto value_type_cardinality =
62 value_cardinality<typename X::value_type>::value;
63
64 std::atomic<std::uint64_t> num_erased{0};
65 auto const old_size = x.size();
66
67 auto const old_dc = +raii::default_constructor;
68 auto const old_cc = +raii::copy_constructor;
69 auto const old_mc = +raii::move_constructor;
70
71 auto const old_d = +raii::destructor;
72
73 BOOST_TEST_EQ(raii::default_constructor + raii::copy_constructor +
74 raii::move_constructor,
75 raii::destructor + value_type_cardinality * x.size());
76
77 thread_runner(values, [&num_erased, &x](boost::span<T> s) {
78 for (auto const& v : s) {
79 auto count = x.erase(get_key(v).x_);
80 num_erased += count;
81 BOOST_TEST_LE(count, 1u);
82 BOOST_TEST_GE(count, 0u);
83 }
84 });
85
86 BOOST_TEST_EQ(raii::default_constructor, old_dc);
87 BOOST_TEST_EQ(raii::copy_constructor, old_cc);
88 BOOST_TEST_EQ(raii::move_constructor, old_mc);
89
90 BOOST_TEST_EQ(
91 raii::destructor, old_d + value_type_cardinality * num_erased);
92
93 BOOST_TEST_EQ(x.size(), 0u);
94 BOOST_TEST(x.empty());
95 BOOST_TEST_EQ(num_erased, old_size);
96 }
97 } transp_lvalue_eraser;
98
99 struct lvalue_eraser_if_type
100 {
101 template <class T, class X> void operator()(std::vector<T>& values, X& x)
102 {
103 using value_type = typename X::value_type;
104 static constexpr auto value_type_cardinality =
105 value_cardinality<value_type>::value;
106
107 // concurrent_flat_set visit is always const access
108 using arg_type = typename std::conditional<
109 std::is_same<typename X::key_type, typename X::value_type>::value,
110 typename X::value_type const,
111 typename X::value_type
112 >::type;
113
114 std::atomic<std::uint64_t> num_erased{0};
115
116 auto const old_size = x.size();
117
118 auto const old_dc = +raii::default_constructor;
119 auto const old_cc = +raii::copy_constructor;
120 auto const old_mc = +raii::move_constructor;
121
122 auto const old_d = +raii::destructor;
123
124 auto max = 0;
125 x.visit_all([&max](value_type const& v) {
126 if (get_value(v).x_ > max) {
127 max = get_value(v).x_;
128 }
129 });
130
131 auto threshold = max / 2;
132
133 auto expected_erasures = 0u;
134 x.visit_all([&expected_erasures, threshold](value_type const& v) {
135 if (get_value(v).x_ > threshold) {
136 ++expected_erasures;
137 }
138 });
139
140 thread_runner(values, [&num_erased, &x, threshold](boost::span<T> s) {
141 for (auto const& v : s) {
142 auto count = x.erase_if(get_key(v),
143 [threshold](arg_type& w) { return get_value(w).x_ > threshold; });
144 num_erased += count;
145 BOOST_TEST_LE(count, 1u);
146 BOOST_TEST_GE(count, 0u);
147 }
148 });
149
150 BOOST_TEST_EQ(num_erased, expected_erasures);
151 BOOST_TEST_EQ(x.size(), old_size - num_erased);
152
153 BOOST_TEST_EQ(raii::default_constructor, old_dc);
154 BOOST_TEST_EQ(raii::copy_constructor, old_cc);
155 BOOST_TEST_EQ(raii::move_constructor, old_mc);
156
157 BOOST_TEST_EQ(
158 raii::destructor, old_d + value_type_cardinality * num_erased);
159 }
160 } lvalue_eraser_if;
161
162 struct transp_lvalue_eraser_if_type
163 {
164 template <class T, class X> void operator()(std::vector<T>& values, X& x)
165 {
166 using value_type = typename X::value_type;
167 static constexpr auto value_type_cardinality =
168 value_cardinality<value_type>::value;
169
170 // concurrent_flat_set visit is always const access
171 using arg_type = typename std::conditional<
172 std::is_same<typename X::key_type, typename X::value_type>::value,
173 typename X::value_type const,
174 typename X::value_type
175 >::type;
176
177 std::atomic<std::uint64_t> num_erased{0};
178
179 auto const old_size = x.size();
180
181 auto const old_dc = +raii::default_constructor;
182 auto const old_cc = +raii::copy_constructor;
183 auto const old_mc = +raii::move_constructor;
184
185 auto const old_d = +raii::destructor;
186
187 auto max = 0;
188 x.visit_all([&max](value_type const& v) {
189 if (get_value(v).x_ > max) {
190 max = get_value(v).x_;
191 }
192 });
193
194 auto threshold = max / 2;
195
196 auto expected_erasures = 0u;
197 x.visit_all([&expected_erasures, threshold](value_type const& v) {
198 if (get_value(v).x_ > threshold) {
199 ++expected_erasures;
200 }
201 });
202
203 thread_runner(values, [&num_erased, &x, threshold](boost::span<T> s) {
204 for (auto const& v : s) {
205 auto count = x.erase_if(get_key(v).x_,
206 [threshold](arg_type& w) { return get_value(w).x_ > threshold; });
207 num_erased += count;
208 BOOST_TEST_LE(count, 1u);
209 BOOST_TEST_GE(count, 0u);
210 }
211 });
212
213 BOOST_TEST_EQ(num_erased, expected_erasures);
214 BOOST_TEST_EQ(x.size(), old_size - num_erased);
215
216 BOOST_TEST_EQ(raii::default_constructor, old_dc);
217 BOOST_TEST_EQ(raii::copy_constructor, old_cc);
218 BOOST_TEST_EQ(raii::move_constructor, old_mc);
219
220 BOOST_TEST_EQ(
221 raii::destructor, old_d + value_type_cardinality * num_erased);
222 }
223 } transp_lvalue_eraser_if;
224
225 struct erase_if_type
226 {
227 template <class T, class X> void operator()(std::vector<T>& values, X& x)
228 {
229 using value_type = typename X::value_type;
230 static constexpr auto value_type_cardinality =
231 value_cardinality<value_type>::value;
232
233 // concurrent_flat_set visit is always const access
234 using arg_type = typename std::conditional<
235 std::is_same<typename X::key_type, typename X::value_type>::value,
236 typename X::value_type const,
237 typename X::value_type
238 >::type;
239
240 std::atomic<std::uint64_t> num_erased{0};
241
242 auto const old_size = x.size();
243
244 auto const old_dc = +raii::default_constructor;
245 auto const old_cc = +raii::copy_constructor;
246 auto const old_mc = +raii::move_constructor;
247
248 auto const old_d = +raii::destructor;
249
250 auto max = 0;
251 x.visit_all([&max](value_type const& v) {
252 if (get_value(v).x_ > max) {
253 max = get_value(v).x_;
254 }
255 });
256
257 auto threshold = max / 2;
258
259 auto expected_erasures = 0u;
260 x.visit_all([&expected_erasures, threshold](value_type const& v) {
261 if (get_value(v).x_ > threshold) {
262 ++expected_erasures;
263 }
264 });
265
266 thread_runner(
267 values, [&num_erased, &x, threshold](boost::span<T> /* s */) {
268 for (std::size_t i = 0; i < 128; ++i) {
269 auto count = x.erase_if(
270 [threshold](arg_type& v) { return get_value(v).x_ > threshold; });
271 num_erased += count;
272 }
273 });
274
275 BOOST_TEST_EQ(num_erased, expected_erasures);
276 BOOST_TEST_EQ(x.size(), old_size - num_erased);
277
278 BOOST_TEST_EQ(raii::default_constructor, old_dc);
279 BOOST_TEST_EQ(raii::copy_constructor, old_cc);
280 BOOST_TEST_EQ(raii::move_constructor, old_mc);
281
282 BOOST_TEST_EQ(
283 raii::destructor, old_d + value_type_cardinality * num_erased);
284 }
285 } erase_if;
286
287 struct free_fn_erase_if_type
288 {
289 template <class T, class X> void operator()(std::vector<T>& values, X& x)
290 {
291 using value_type = typename X::value_type;
292 static constexpr auto value_type_cardinality =
293 value_cardinality<value_type>::value;
294
295 // concurrent_flat_set visit is always const access
296 using arg_type = typename std::conditional<
297 std::is_same<typename X::key_type, typename X::value_type>::value,
298 typename X::value_type const,
299 typename X::value_type
300 >::type;
301
302 std::atomic<std::uint64_t> num_erased{0};
303
304 auto const old_size = x.size();
305
306 auto const old_dc = +raii::default_constructor;
307 auto const old_cc = +raii::copy_constructor;
308 auto const old_mc = +raii::move_constructor;
309
310 auto const old_d = +raii::destructor;
311
312 auto max = 0;
313 x.visit_all([&max](value_type const& v) {
314 if (get_value(v).x_ > max) {
315 max = get_value(v).x_;
316 }
317 });
318
319 auto threshold = max / 2;
320
321 auto expected_erasures = 0u;
322 x.visit_all([&expected_erasures, threshold](value_type const& v) {
323 if (get_value(v).x_ > threshold) {
324 ++expected_erasures;
325 }
326 });
327
328 thread_runner(
329 values, [&num_erased, &x, threshold](boost::span<T> /* s */) {
330 for (std::size_t i = 0; i < 128; ++i) {
331 auto count = boost::unordered::erase_if(x,
332 [threshold](arg_type& v) {
333 return get_value(v).x_ > threshold; });
334 num_erased += count;
335 }
336 });
337
338 BOOST_TEST_EQ(num_erased, expected_erasures);
339 BOOST_TEST_EQ(x.size(), old_size - num_erased);
340
341 BOOST_TEST_EQ(raii::default_constructor, old_dc);
342 BOOST_TEST_EQ(raii::copy_constructor, old_cc);
343 BOOST_TEST_EQ(raii::move_constructor, old_mc);
344
345 BOOST_TEST_EQ(
346 raii::destructor, old_d + value_type_cardinality * num_erased);
347 }
348 } free_fn_erase_if;
349
350 struct erase_if_exec_policy_type
351 {
352 template <class T, class X> void operator()(std::vector<T>& values, X& x)
353 {
354#if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
355 using value_type = typename X::value_type;
356 static constexpr auto value_type_cardinality =
357 value_cardinality<value_type>::value;
358
359 // concurrent_flat_set visit is always const access
360 using arg_type = typename std::conditional<
361 std::is_same<typename X::key_type, typename X::value_type>::value,
362 typename X::value_type const,
363 typename X::value_type
364 >::type;
365
366 std::atomic<std::uint64_t> num_invokes{0};
367
368 auto const old_size = x.size();
369
370 auto const old_dc = +raii::default_constructor;
371 auto const old_cc = +raii::copy_constructor;
372 auto const old_mc = +raii::move_constructor;
373
374 auto const old_d = +raii::destructor;
375
376 auto max = 0;
377 x.visit_all([&max](value_type const& v) {
378 if (get_value(v).x_ > max) {
379 max = get_value(v).x_;
380 }
381 });
382
383 auto threshold = max / 2;
384
385 auto expected_erasures = 0u;
386 x.visit_all([&expected_erasures, threshold](value_type const& v) {
387 if (get_value(v).x_ > threshold) {
388 ++expected_erasures;
389 }
390 });
391
392 thread_runner(values, [&num_invokes, &x, threshold](boost::span<T> s) {
393 (void)s;
394 x.erase_if(
395 std::execution::par, [&num_invokes, threshold](arg_type& v) {
396 ++num_invokes;
397 return get_value(v).x_ > threshold;
398 });
399 });
400
401 BOOST_TEST_GE(+num_invokes, old_size);
402 BOOST_TEST_LE(+num_invokes, old_size * num_threads);
403
404 BOOST_TEST_EQ(raii::default_constructor, old_dc);
405 BOOST_TEST_EQ(raii::copy_constructor, old_cc);
406 BOOST_TEST_EQ(raii::move_constructor, old_mc);
407
408 BOOST_TEST_EQ(
409 raii::destructor, old_d + value_type_cardinality * expected_erasures);
410#else
411 (void)values;
412 (void)x;
413#endif
414 }
415 } erase_if_exec_policy;
416
417 template <class X, class GF, class F>
418 void erase(X*, GF gen_factory, F eraser, test::random_generator rg)
419 {
420 auto gen = gen_factory.template get<X>();
421 auto values = make_random_values(1024 * 16, [&] { return gen(rg); });
422 auto reference_cont = reference_container<X>(values.begin(), values.end());
423 raii::reset_counts();
424
425 {
426 X x;
427
428 x.insert(values.begin(), values.end());
429
430 BOOST_TEST_EQ(x.size(), reference_cont.size());
431
432 test_fuzzy_matches_reference(x, reference_cont, rg);
433
434 eraser(values, x);
435 test_fuzzy_matches_reference(x, reference_cont, rg);
436 }
437
438 check_raii_counts();
439 }
440
441 boost::unordered::concurrent_flat_map<raii, raii>* map;
442 boost::unordered::concurrent_flat_set<raii>* set;
443 boost::unordered::concurrent_flat_map<raii, raii, transp_hash,
444 transp_key_equal>* transparent_map;
445 boost::unordered::concurrent_flat_set<raii, transp_hash,
446 transp_key_equal>* transparent_set;
447
448} // namespace
449
450using test::default_generator;
451using test::limited_range;
452using test::sequential;
453
454// clang-format off
455UNORDERED_TEST(
456 erase,
457 ((map)(set))
458 ((value_type_generator_factory)(init_type_generator_factory))
459 ((lvalue_eraser)(lvalue_eraser_if)(erase_if)(free_fn_erase_if)(erase_if_exec_policy))
460 ((default_generator)(sequential)(limited_range)))
461
462UNORDERED_TEST(
463 erase,
464 ((transparent_map)(transparent_set))
465 ((value_type_generator_factory)(init_type_generator_factory))
466 ((transp_lvalue_eraser)(transp_lvalue_eraser_if)(erase_if_exec_policy))
467 ((default_generator)(sequential)(limited_range)))
468
469// clang-format on
470
471RUN_TESTS()
472

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