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 <boost/config.hpp>
7#include <boost/config/workaround.hpp>
8
9#if BOOST_WORKAROUND(BOOST_GCC_VERSION, < 40900)
10// warning triggered in transform_iterator.hpp transitive includes
11#pragma GCC diagnostic push
12#pragma GCC diagnostic ignored "-Wconversion"
13#pragma GCC diagnostic ignored "-Wsign-conversion"
14#endif
15
16#include "helpers.hpp"
17
18#include <boost/unordered/concurrent_flat_map.hpp>
19#include <boost/unordered/concurrent_flat_set.hpp>
20
21#include <boost/core/ignore_unused.hpp>
22#include <boost/iterator/transform_iterator.hpp>
23
24#if BOOST_WORKAROUND(BOOST_GCC_VERSION, < 40900)
25#pragma GCC diagnostic pop
26#endif
27
28#include <algorithm>
29#include <array>
30#include <functional>
31#include <vector>
32
33namespace {
34 test::seed_t initialize_seed(335740237);
35
36 auto non_present_keys = []
37 {
38 std::array<raii,128> a;
39 for(std::size_t i = 0; i < a.size(); ++i) {
40 a[i].x_ = -((int)i + 1);
41 }
42 return a;
43 }();
44
45 template<typename T>
46 raii const & get_non_present_key(T const & x)
47 {
48 return non_present_keys[
49 (std::size_t)get_key(x).x_ % non_present_keys.size()];
50 }
51
52 struct lvalue_visitor_type
53 {
54 template <class T, class X, class M>
55 void operator()(std::vector<T>& values, X& x, M const& reference_cont)
56 {
57 using value_type = typename X::value_type;
58
59 // concurrent_flat_set visit is always const access
60 using arg_type = typename std::conditional<
61 std::is_same<typename X::key_type, typename X::value_type>::value,
62 typename X::value_type const,
63 typename X::value_type
64 >::type;
65
66 std::atomic<std::uint64_t> num_visits{0};
67 std::atomic<std::uint64_t> total_count{0};
68
69 auto mut_visitor = [&num_visits, &reference_cont](arg_type& v) {
70 BOOST_TEST(reference_cont.contains(get_key(v)));
71 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
72 ++num_visits;
73 };
74
75 auto const_visitor =
76 [&num_visits, &reference_cont](value_type const& v) {
77 BOOST_TEST(reference_cont.contains(get_key(v)));
78 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
79 ++num_visits;
80 };
81
82 {
83 thread_runner(
84 values, [&x, &mut_visitor, &total_count](boost::span<T> s) {
85 for (auto const& val : s) {
86 auto r = get_key(val).x_;
87 BOOST_TEST(r >= 0);
88
89 auto count = x.visit(get_key(val), mut_visitor);
90 BOOST_TEST_EQ(count, 1u);
91 total_count += count;
92
93 count = x.visit(get_non_present_key(val), mut_visitor);
94 BOOST_TEST_EQ(count, 0u);
95 }
96 });
97
98 BOOST_TEST_EQ(num_visits, values.size());
99 BOOST_TEST_EQ(total_count, values.size());
100
101 num_visits = 0;
102 total_count = 0;
103 }
104
105 {
106 thread_runner(
107 values, [&x, &const_visitor, &total_count](boost::span<T> s) {
108 for (auto const& val : s) {
109 auto r = get_key(val).x_;
110 BOOST_TEST(r >= 0);
111
112 auto const& y = x;
113 auto count = y.visit(get_key(val), const_visitor);
114
115 BOOST_TEST_EQ(count, 1u);
116 total_count += count;
117
118 count = y.visit(get_non_present_key(val), const_visitor);
119 BOOST_TEST_EQ(count, 0u);
120 }
121 });
122
123 BOOST_TEST_EQ(num_visits, values.size());
124 BOOST_TEST_EQ(total_count, values.size());
125
126 num_visits = 0;
127 total_count = 0;
128 }
129
130 {
131 thread_runner(
132 values, [&x, &const_visitor, &total_count](boost::span<T> s) {
133 for (auto const& val : s) {
134 auto r = get_key(val).x_;
135 BOOST_TEST(r >= 0);
136
137 auto count = x.cvisit(get_key(val), const_visitor);
138
139 BOOST_TEST_EQ(count, 1u);
140 total_count += count;
141
142 count = x.cvisit(get_non_present_key(val), const_visitor);
143 BOOST_TEST_EQ(count, 0u);
144 }
145 });
146
147 BOOST_TEST_EQ(num_visits, values.size());
148 BOOST_TEST_EQ(total_count, values.size());
149
150 num_visits = 0;
151 total_count = 0;
152 }
153
154 {
155 thread_runner(values, [&x, &total_count](boost::span<T> s) {
156 for (auto const& val : s) {
157 auto r = get_key(val).x_;
158 BOOST_TEST(r >= 0);
159
160 auto count = x.count(get_key(val));
161 BOOST_TEST_EQ(count, 1u);
162 total_count += count;
163
164 count = x.count(get_non_present_key(val));
165 BOOST_TEST_EQ(count, 0u);
166 }
167 });
168
169 BOOST_TEST_EQ(total_count, values.size());
170
171 num_visits = 0;
172 total_count = 0;
173 }
174
175 {
176 thread_runner(values, [&x](boost::span<T> s) {
177 for (auto const& val : s) {
178 auto r = get_key(val).x_;
179 BOOST_TEST(r >= 0);
180
181 auto contains = x.contains(get_key(val));
182 BOOST_TEST(contains);
183
184 contains = x.contains(get_non_present_key(val));
185 BOOST_TEST(!contains);
186 }
187 });
188
189 num_visits = 0;
190 total_count = 0;
191 }
192 }
193 } lvalue_visitor;
194
195 struct transp_visitor_type
196 {
197 template <class T, class X, class M>
198 void operator()(std::vector<T>& values, X& x, M const& reference_cont)
199 {
200 using value_type = typename X::value_type;
201
202 // concurrent_flat_set visit is always const access
203 using arg_type = typename std::conditional<
204 std::is_same<typename X::key_type, typename X::value_type>::value,
205 typename X::value_type const,
206 typename X::value_type
207 >::type;
208
209 std::atomic<std::uint64_t> num_visits{0};
210 std::atomic<std::uint64_t> total_count{0};
211
212 auto mut_visitor = [&num_visits, &reference_cont](arg_type& v) {
213 BOOST_TEST(reference_cont.contains(get_key(v)));
214 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
215 ++num_visits;
216 };
217
218 auto const_visitor = [&num_visits, &reference_cont](value_type const& v) {
219 BOOST_TEST(reference_cont.contains(get_key(v)));
220 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
221 ++num_visits;
222 };
223
224 {
225 thread_runner(
226 values, [&x, &mut_visitor, &total_count](boost::span<T> s) {
227 for (auto const& val : s) {
228 auto r = get_key(val).x_;
229 BOOST_TEST(r >= 0);
230
231 auto count = x.visit(get_key(val).x_, mut_visitor);
232
233 BOOST_TEST_EQ(count, 1u);
234 total_count += count;
235
236 count = x.visit(get_non_present_key(val).x_, mut_visitor);
237 BOOST_TEST_EQ(count, 0u);
238 }
239 });
240
241 BOOST_TEST_EQ(num_visits, values.size());
242 BOOST_TEST_EQ(total_count, values.size());
243
244 num_visits = 0;
245 total_count = 0;
246 }
247
248 {
249 thread_runner(
250 values, [&x, &const_visitor, &total_count](boost::span<T> s) {
251 for (auto const& val : s) {
252 auto r = get_key(val).x_;
253 BOOST_TEST(r >= 0);
254
255 auto const& y = x;
256 auto count = y.visit(get_key(val).x_, const_visitor);
257
258 BOOST_TEST_EQ(count, 1u);
259 total_count += count;
260
261 count = y.visit(get_non_present_key(val).x_, const_visitor);
262 BOOST_TEST_EQ(count, 0u);
263 }
264 });
265
266 BOOST_TEST_EQ(num_visits, values.size());
267 BOOST_TEST_EQ(total_count, values.size());
268
269 num_visits = 0;
270 total_count = 0;
271 }
272
273 {
274 thread_runner(
275 values, [&x, &const_visitor, &total_count](boost::span<T> s) {
276 for (auto const& val : s) {
277 auto r = get_key(val).x_;
278 BOOST_TEST(r >= 0);
279
280 auto count = x.cvisit(get_key(val).x_, const_visitor);
281
282 BOOST_TEST_EQ(count, 1u);
283 total_count += count;
284
285 count = x.cvisit(get_non_present_key(val).x_, const_visitor);
286 BOOST_TEST_EQ(count, 0u);
287 }
288 });
289
290 BOOST_TEST_EQ(num_visits, values.size());
291 BOOST_TEST_EQ(total_count, values.size());
292
293 num_visits = 0;
294 total_count = 0;
295 }
296
297 {
298 thread_runner(values, [&x, &total_count](boost::span<T> s) {
299 for (auto const& val : s) {
300 auto r = get_key(val).x_;
301 BOOST_TEST(r >= 0);
302
303 auto count = x.count(get_key(val).x_);
304 BOOST_TEST_EQ(count, 1u);
305 total_count += count;
306
307 count = x.count(get_non_present_key(val).x_);
308 BOOST_TEST_EQ(count, 0u);
309 }
310 });
311
312 BOOST_TEST_EQ(total_count, values.size());
313
314 num_visits = 0;
315 total_count = 0;
316 }
317
318 {
319 thread_runner(values, [&x](boost::span<T> s) {
320 for (auto const& val : s) {
321 auto r = get_key(val).x_;
322 BOOST_TEST(r >= 0);
323
324 auto contains = x.contains(get_key(val).x_);
325 BOOST_TEST(contains);
326
327 contains = x.contains(get_non_present_key(val).x_);
328 BOOST_TEST(!contains);
329 }
330 });
331
332 num_visits = 0;
333 total_count = 0;
334 }
335 }
336 } transp_visitor;
337
338 struct visit_all_type
339 {
340 template <class T, class X, class M>
341 void operator()(std::vector<T>& values, X& x, M const& reference_cont)
342 {
343 using value_type = typename X::value_type;
344
345 // concurrent_flat_set visit is always const access
346 using arg_type = typename std::conditional<
347 std::is_same<typename X::key_type, typename X::value_type>::value,
348 typename X::value_type const,
349 typename X::value_type
350 >::type;
351
352 std::atomic<std::uint64_t> total_count{0};
353
354 auto mut_visitor = [&reference_cont](std::atomic<uint64_t>& num_visits) {
355 return [&reference_cont, &num_visits](arg_type& v) {
356 BOOST_TEST(reference_cont.contains(get_key(v)));
357 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
358 ++num_visits;
359 };
360 };
361
362 auto const_visitor = [&reference_cont](std::atomic<uint64_t>& num_visits) {
363 return [&reference_cont, &num_visits](value_type const& v) {
364 BOOST_TEST(reference_cont.contains(get_key(v)));
365 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
366 ++num_visits;
367 };
368 };
369
370 {
371 thread_runner(values, [&x, &total_count, &mut_visitor](boost::span<T>) {
372 std::atomic<std::uint64_t> num_visits{0};
373 total_count += x.visit_all(mut_visitor(num_visits));
374 BOOST_TEST_EQ(x.size(), num_visits);
375 });
376
377 BOOST_TEST_EQ(total_count, num_threads * x.size());
378 total_count = 0;
379 }
380
381 {
382 thread_runner(
383 values, [&x, &total_count, &const_visitor](boost::span<T>) {
384 std::atomic<std::uint64_t> num_visits{0};
385 auto const& y = x;
386 total_count += y.visit_all(const_visitor(num_visits));
387 BOOST_TEST_EQ(x.size(), num_visits);
388 });
389
390 BOOST_TEST_EQ(total_count, num_threads * x.size());
391 total_count = 0;
392 }
393
394 {
395 thread_runner(
396 values, [&x, &total_count, &const_visitor](boost::span<T>) {
397 std::atomic<std::uint64_t> num_visits{0};
398 total_count += x.cvisit_all(const_visitor(num_visits));
399 BOOST_TEST_EQ(x.size(), num_visits);
400 });
401
402 BOOST_TEST_EQ(total_count, num_threads * x.size());
403 total_count = 0;
404 }
405 }
406
407 } visit_all;
408
409 struct visit_while_type
410 {
411 template <class T, class X, class M>
412 void operator()(std::vector<T>& values, X& x, M const& reference_cont)
413 {
414 using value_type = typename X::value_type;
415
416 // concurrent_flat_set visit is always const access
417 using arg_type = typename std::conditional<
418 std::is_same<typename X::key_type, typename X::value_type>::value,
419 typename X::value_type const,
420 typename X::value_type
421 >::type;
422
423 auto mut_truthy_visitor = [&reference_cont](
424 std::atomic<uint64_t>& num_visits) {
425 return [&reference_cont, &num_visits](arg_type& v) {
426 BOOST_TEST(reference_cont.contains(get_key(v)));
427 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
428 ++num_visits;
429 return true;
430 };
431 };
432
433 auto const_truthy_visitor = [&reference_cont](
434 std::atomic<uint64_t>& num_visits) {
435 return [&reference_cont, &num_visits](value_type const& v) {
436 BOOST_TEST(reference_cont.contains(get_key(v)));
437 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
438 ++num_visits;
439 return true;
440 };
441 };
442
443 auto mut_falsey_visitor = [&reference_cont](
444 std::atomic<uint64_t>& num_visits) {
445 return [&reference_cont, &num_visits](arg_type& v) {
446 BOOST_TEST(reference_cont.contains(get_key(v)));
447 ++num_visits;
448 return (get_value(v).x_ % 100) == 0;
449 };
450 };
451
452 auto const_falsey_visitor = [&reference_cont](
453 std::atomic<uint64_t>& num_visits) {
454 return [&reference_cont, &num_visits](value_type const& v) {
455 BOOST_TEST(reference_cont.contains(get_key(v)));
456 ++num_visits;
457 return (get_value(v).x_ % 100) == 0;
458 };
459 };
460
461 {
462 thread_runner(values, [&x, &mut_truthy_visitor](boost::span<T>) {
463 std::atomic<std::uint64_t> num_visits{0};
464 BOOST_TEST(x.visit_while(mut_truthy_visitor(num_visits)));
465 BOOST_TEST_EQ(x.size(), num_visits);
466 });
467 }
468
469 {
470 thread_runner(values, [&x, &const_truthy_visitor](boost::span<T>) {
471 std::atomic<std::uint64_t> num_visits{0};
472 auto const& y = x;
473 BOOST_TEST(y.visit_while(const_truthy_visitor(num_visits)));
474 BOOST_TEST_EQ(x.size(), num_visits);
475 });
476 }
477
478 {
479 thread_runner(values, [&x, &const_truthy_visitor](boost::span<T>) {
480 std::atomic<std::uint64_t> num_visits{0};
481 BOOST_TEST(x.cvisit_while(const_truthy_visitor(num_visits)));
482 BOOST_TEST_EQ(x.size(), num_visits);
483 });
484 }
485
486 {
487 thread_runner(values, [&x, &mut_falsey_visitor](boost::span<T>) {
488 std::atomic<std::uint64_t> num_visits{0};
489 BOOST_TEST_NOT(x.visit_while(mut_falsey_visitor(num_visits)));
490 BOOST_TEST_LT(num_visits, x.size());
491 BOOST_TEST_GT(num_visits, 0u);
492 });
493 }
494
495 {
496 thread_runner(values, [&x, &const_falsey_visitor](boost::span<T>) {
497 std::atomic<std::uint64_t> num_visits{0};
498 auto const& y = x;
499 BOOST_TEST_NOT(y.visit_while(const_falsey_visitor(num_visits)));
500 BOOST_TEST_LT(num_visits, x.size());
501 BOOST_TEST_GT(num_visits, 0u);
502 });
503 }
504
505 {
506 thread_runner(values, [&x, &const_falsey_visitor](boost::span<T>) {
507 std::atomic<std::uint64_t> num_visits{0};
508 BOOST_TEST_NOT(x.cvisit_while(const_falsey_visitor(num_visits)));
509 BOOST_TEST_LT(num_visits, x.size());
510 BOOST_TEST_GT(num_visits, 0u);
511 });
512 }
513 }
514 } visit_while;
515
516 struct exec_policy_visit_all_type
517 {
518 template <class T, class X, class M>
519 void operator()(std::vector<T>& values, X& x, M const& reference_cont)
520 {
521#if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
522 using value_type = typename X::value_type;
523
524 // concurrent_flat_set visit is always const access
525 using arg_type = typename std::conditional<
526 std::is_same<typename X::key_type, typename X::value_type>::value,
527 typename X::value_type const,
528 typename X::value_type
529 >::type;
530
531 auto mut_visitor = [&reference_cont](std::atomic<uint64_t>& num_visits) {
532 return [&reference_cont, &num_visits](arg_type& v) {
533 BOOST_TEST(reference_cont.contains(get_key(v)));
534 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
535 ++num_visits;
536 };
537 };
538
539 auto const_visitor = [&reference_cont](std::atomic<uint64_t>& num_visits) {
540 return [&reference_cont, &num_visits](value_type const& v) {
541 BOOST_TEST(reference_cont.contains(get_key(v)));
542 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
543 ++num_visits;
544 };
545 };
546
547 {
548 thread_runner(values, [&x, &mut_visitor](boost::span<T>) {
549 std::atomic<std::uint64_t> num_visits{0};
550
551 x.visit_all(std::execution::par, mut_visitor(num_visits));
552 BOOST_TEST_EQ(x.size(), num_visits);
553 });
554 }
555
556 {
557 thread_runner(values, [&x, &const_visitor](boost::span<T>) {
558 std::atomic<std::uint64_t> num_visits{0};
559 auto const& y = x;
560
561 y.visit_all(std::execution::par, const_visitor(num_visits));
562 BOOST_TEST_EQ(x.size(), num_visits);
563 });
564 }
565
566 {
567 thread_runner(values, [&x, &const_visitor](boost::span<T>) {
568 std::atomic<std::uint64_t> num_visits{0};
569 x.cvisit_all(std::execution::par, const_visitor(num_visits));
570 BOOST_TEST_EQ(x.size(), num_visits);
571 });
572 }
573#else
574 (void)values;
575 (void)x;
576 (void)reference_cont;
577#endif
578 }
579 } exec_policy_visit_all;
580
581 struct exec_policy_visit_while_type
582 {
583 template <class T, class X, class M>
584 void operator()(std::vector<T>& values, X& x, M const& reference_cont)
585 {
586#if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
587 using value_type = typename X::value_type;
588
589 // concurrent_flat_set visit is always const access
590 using arg_type = typename std::conditional<
591 std::is_same<typename X::key_type, typename X::value_type>::value,
592 typename X::value_type const,
593 typename X::value_type
594 >::type;
595
596 auto mut_truthy_visitor = [&reference_cont](
597 std::atomic<uint64_t>& num_visits) {
598 return [&reference_cont, &num_visits](arg_type& v) {
599 BOOST_TEST(reference_cont.contains(get_key(v)));
600 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
601 ++num_visits;
602 return true;
603 };
604 };
605
606 auto const_truthy_visitor = [&reference_cont](
607 std::atomic<uint64_t>& num_visits) {
608 return [&reference_cont, &num_visits](value_type const& v) {
609 BOOST_TEST(reference_cont.contains(get_key(v)));
610 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
611 ++num_visits;
612 return true;
613 };
614 };
615
616 auto mut_falsey_visitor = [&reference_cont](
617 std::atomic<uint64_t>& num_visits) {
618 return [&reference_cont, &num_visits](arg_type& v) {
619 BOOST_TEST(reference_cont.contains(get_key(v)));
620 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
621 ++num_visits;
622 return (get_value(v).x_ % 100) == 0;
623 };
624 };
625
626 auto const_falsey_visitor = [&reference_cont](
627 std::atomic<uint64_t>& num_visits) {
628 return [&reference_cont, &num_visits](value_type const& v) {
629 BOOST_TEST(reference_cont.contains(get_key(v)));
630 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
631 ++num_visits;
632 return (get_value(v).x_ % 100) == 0;
633 };
634 };
635
636 {
637 thread_runner(values, [&x, &mut_truthy_visitor](boost::span<T>) {
638 std::atomic<std::uint64_t> num_visits{0};
639 BOOST_TEST(
640 x.visit_while(std::execution::par, mut_truthy_visitor(num_visits)));
641 BOOST_TEST_EQ(x.size(), num_visits);
642 });
643 }
644
645 {
646 thread_runner(values, [&x, &const_truthy_visitor](boost::span<T>) {
647 std::atomic<std::uint64_t> num_visits{0};
648 auto const& y = x;
649 BOOST_TEST(y.visit_while(
650 std::execution::par, const_truthy_visitor(num_visits)));
651 BOOST_TEST_EQ(x.size(), num_visits);
652 });
653 }
654
655 {
656 thread_runner(values, [&x, &const_truthy_visitor](boost::span<T>) {
657 std::atomic<std::uint64_t> num_visits{0};
658 BOOST_TEST(x.cvisit_while(
659 std::execution::par, const_truthy_visitor(num_visits)));
660 BOOST_TEST_EQ(x.size(), num_visits);
661 });
662 }
663
664 {
665 thread_runner(values, [&x, &mut_falsey_visitor](boost::span<T>) {
666 std::atomic<std::uint64_t> num_visits{0};
667 BOOST_TEST_NOT(
668 x.visit_while(std::execution::par, mut_falsey_visitor(num_visits)));
669 BOOST_TEST_LT(num_visits, x.size());
670 BOOST_TEST_GT(num_visits, 0u);
671 });
672 }
673
674 {
675 thread_runner(values, [&x, &const_falsey_visitor](boost::span<T>) {
676 std::atomic<std::uint64_t> num_visits{0};
677 auto const& y = x;
678 BOOST_TEST_NOT(y.visit_while(
679 std::execution::par, const_falsey_visitor(num_visits)));
680 BOOST_TEST_LT(num_visits, x.size());
681 BOOST_TEST_GT(num_visits, 0u);
682 });
683 }
684
685 {
686 thread_runner(values, [&x, &const_falsey_visitor](boost::span<T>) {
687 std::atomic<std::uint64_t> num_visits{0};
688 BOOST_TEST_NOT(x.cvisit_while(
689 std::execution::par, const_falsey_visitor(num_visits)));
690 BOOST_TEST_LT(num_visits, x.size());
691 BOOST_TEST_GT(num_visits, 0u);
692 });
693 }
694#else
695 (void)values;
696 (void)x;
697 (void)reference_cont;
698#endif
699 }
700 } exec_policy_visit_while;
701
702 template <class X, class GF, class F>
703 void visit(X*, GF gen_factory, F visitor, test::random_generator rg)
704 {
705 auto gen = gen_factory.template get<X>();
706 auto values = make_random_values(1024 * 16, [&] { return gen(rg); });
707 auto reference_cont = reference_container<X>(values.begin(), values.end());
708
709 raii::reset_counts();
710
711 {
712 X x;
713 for (auto const& v : values) {
714 x.insert(v);
715 }
716 BOOST_TEST_EQ(x.size(), reference_cont.size());
717
718 std::uint64_t old_default_constructor = raii::default_constructor;
719 std::uint64_t old_copy_constructor = raii::copy_constructor;
720 std::uint64_t old_move_constructor = raii::move_constructor;
721 std::uint64_t old_copy_assignment = raii::copy_assignment;
722 std::uint64_t old_move_assignment = raii::move_assignment;
723
724 visitor(values, x, reference_cont);
725
726 BOOST_TEST_EQ(old_default_constructor, raii::default_constructor);
727 BOOST_TEST_EQ(old_copy_constructor, raii::copy_constructor);
728 BOOST_TEST_EQ(old_move_constructor, raii::move_constructor);
729 BOOST_TEST_EQ(old_copy_assignment, raii::copy_assignment);
730 BOOST_TEST_EQ(old_move_assignment, raii::move_assignment);
731 }
732
733 BOOST_TEST_GE(raii::default_constructor, 0u);
734 BOOST_TEST_GE(raii::copy_constructor, 0u);
735 BOOST_TEST_GE(raii::move_constructor, 0u);
736 BOOST_TEST_GT(raii::destructor, 0u);
737
738 BOOST_TEST_EQ(raii::default_constructor + raii::copy_constructor +
739 raii::move_constructor,
740 raii::destructor);
741 }
742
743 template <class X, class GF>
744 void empty_visit(X*, GF gen_factory, test::random_generator rg)
745 {
746 auto gen = gen_factory.template get<X>();
747 auto values = make_random_values(1024 * 16, [&] { return gen(rg); });
748 using values_type = decltype(values);
749 using span_value_type = typename values_type::value_type;
750
751 raii::reset_counts();
752
753 {
754 X x;
755
756 std::uint64_t old_default_constructor = raii::default_constructor;
757 std::uint64_t old_copy_constructor = raii::copy_constructor;
758 std::uint64_t old_move_constructor = raii::move_constructor;
759 std::uint64_t old_copy_assignment = raii::copy_assignment;
760 std::uint64_t old_move_assignment = raii::move_assignment;
761
762 {
763 thread_runner(values, [&x](boost::span<span_value_type> s) {
764 std::atomic<std::uint64_t> num_visits{0};
765
766 x.visit_all(
767 [&num_visits](typename X::value_type const&) { ++num_visits; });
768 BOOST_TEST_EQ(num_visits, 0u);
769
770 for (auto const& val : s) {
771 auto count = x.visit(get_key(val),
772 [&num_visits](typename X::value_type const&) { ++num_visits; });
773 BOOST_TEST_EQ(count, 0u);
774 }
775 });
776 }
777
778 BOOST_TEST_EQ(old_default_constructor, raii::default_constructor);
779 BOOST_TEST_EQ(old_copy_constructor, raii::copy_constructor);
780 BOOST_TEST_EQ(old_move_constructor, raii::move_constructor);
781 BOOST_TEST_EQ(old_copy_assignment, raii::copy_assignment);
782 BOOST_TEST_EQ(old_move_assignment, raii::move_assignment);
783 }
784
785 BOOST_TEST_EQ(raii::default_constructor, 0u);
786 BOOST_TEST_EQ(raii::copy_constructor, 0u);
787 BOOST_TEST_EQ(raii::move_constructor, 0u);
788 BOOST_TEST_EQ(raii::destructor, 0u);
789 }
790
791 template <class X, class GF>
792 void insert_and_visit(X*, GF gen_factory, test::random_generator rg)
793 {
794 // here we attempt to ensure happens-before and synchronizes-with
795 // the visitation thread essentially chases the insertion one
796 // we double-check unreloated loads/stores to ensure that a store is visible
797 // in the visitation thread
798
799 BOOST_TEST(rg == test::sequential);
800
801 auto gen = gen_factory.template get<X>();
802 auto const values = make_random_values(1024 * 16, [&] { return gen(rg); });
803
804 {
805 raii::reset_counts();
806
807 X x;
808
809 std::thread t1, t2;
810 boost::compat::latch l(2);
811 std::vector<std::string> strs(values.size());
812
813 t1 = std::thread([&l, &values, &x, &strs] {
814 l.arrive_and_wait();
815 for (std::size_t idx = 0; idx < values.size(); ++idx) {
816 strs[idx] = "rawr";
817 auto const& val = values[idx];
818 x.insert(val);
819 }
820 });
821
822 t2 = std::thread([&l, &values, &x, &strs] {
823 l.arrive_and_wait();
824
825 for (std::size_t idx = 0; idx < values.size(); ++idx) {
826 std::atomic_bool b{false};
827 while (!b) {
828 x.cvisit(get_key(values[idx]),
829 [&b, &strs, idx, &values](typename X::value_type const& v) {
830 BOOST_TEST_EQ(get_value(v), get_value(values[idx]));
831 BOOST_TEST_EQ(strs[idx], "rawr");
832 b = true;
833 });
834 }
835 }
836 });
837
838 t1.join();
839 t2.join();
840 }
841 check_raii_counts();
842 }
843
844 struct regular_key_extractor
845 {
846 template<typename T>
847 auto operator()(const T& x) const -> decltype(get_key(x))
848 {
849 return get_key(x);
850 }
851 } regular_key_extract;
852
853 struct transp_key_extractor
854 {
855 template<typename T>
856 auto operator()(const T& x) const -> decltype((get_key(x).x_))
857 {
858 return get_key(x).x_;
859 }
860 } transp_key_extract;
861
862 template <class X, class KeyExtractor, class GF>
863 void bulk_visit(
864 X*, KeyExtractor key_extract, GF gen_factory, test::random_generator rg)
865 {
866 using key_type = typename X::key_type;
867 using value_type = typename X::value_type;
868
869 // concurrent_flat_set visit is always const access
870 using arg_type = typename std::conditional<
871 std::is_same<key_type, value_type>::value,
872 value_type const,
873 value_type
874 >::type;
875
876 auto gen = gen_factory.template get<X>();
877 auto values = make_random_values(16384 * 16, [&] { return gen(rg); });
878
879 using values_type = decltype(values);
880 using span_value_type = typename values_type::value_type;
881
882 raii::reset_counts();
883
884 {
885 X x;
886 for (auto const& v: values) {
887 if (get_key(v).x_ % 3 != 0) x.insert(v);
888 }
889 X const& cx = x;
890
891 std::uint64_t old_default_constructor = raii::default_constructor;
892 std::uint64_t old_copy_constructor = raii::copy_constructor;
893 std::uint64_t old_move_constructor = raii::move_constructor;
894 std::uint64_t old_copy_assignment = raii::copy_assignment;
895 std::uint64_t old_move_assignment = raii::move_assignment;
896
897 std::atomic<std::size_t> num_visits{0};
898
899 thread_runner(values, [&x, &cx, &num_visits, key_extract]
900 (boost::span<span_value_type> s) {
901 auto it = boost::make_transform_iterator(s.begin(), key_extract);
902
903 std::size_t n = s.size(), m = 0, q = 0;
904
905 auto found = [&it, &m](value_type const& v) {
906 return std::find(
907 it, it + (std::ptrdiff_t)m, get_key(v)) != it + (std::ptrdiff_t)m;
908 };
909
910 while (n) {
911 if (m > n) m = n;
912
913 switch (q % 3) {
914 case 0:
915 x.visit(
916 it, it + (std::ptrdiff_t)m,
917 [&num_visits, &found](arg_type& v) {
918 if ( found(v) ) ++num_visits;
919 });
920 break;
921 case 1:
922 cx.visit(
923 it, it + (std::ptrdiff_t)m,
924 [&num_visits, &found](value_type const& v) {
925 if ( found(v) ) ++num_visits;
926 });
927 break;
928 case 2:
929 cx.cvisit(
930 it, it + (std::ptrdiff_t)m,
931 [&num_visits, &found](value_type const& v) {
932 if ( found(v) ) ++num_visits;
933 });
934 break;
935 default:
936 break;
937 }
938 it += (std::ptrdiff_t)m;
939 n -= m;
940 ++m;
941 if (m > 5*X::bulk_visit_size){
942 m = 0;
943 ++ q;
944 }
945 }
946 });
947
948 BOOST_TEST_EQ(num_visits, x.size());
949
950 BOOST_TEST_EQ(old_default_constructor, raii::default_constructor);
951 BOOST_TEST_EQ(old_copy_constructor, raii::copy_constructor);
952 BOOST_TEST_EQ(old_move_constructor, raii::move_constructor);
953 BOOST_TEST_EQ(old_copy_assignment, raii::copy_assignment);
954 BOOST_TEST_EQ(old_move_assignment, raii::move_assignment);
955 }
956
957 BOOST_TEST_GE(raii::default_constructor, 0u);
958 BOOST_TEST_GE(raii::copy_constructor, 0u);
959 BOOST_TEST_GE(raii::move_constructor, 0u);
960 BOOST_TEST_GT(raii::destructor, 0u);
961
962 BOOST_TEST_EQ(raii::default_constructor + raii::copy_constructor +
963 raii::move_constructor,
964 raii::destructor);
965 }
966
967 boost::unordered::concurrent_flat_map<raii, raii>* map;
968 boost::unordered::concurrent_flat_map<raii, raii, transp_hash,
969 transp_key_equal>* transp_map;
970 boost::unordered::concurrent_flat_set<raii>* set;
971 boost::unordered::concurrent_flat_set<raii, transp_hash,
972 transp_key_equal>* transp_set;
973
974} // namespace
975
976using test::default_generator;
977using test::limited_range;
978using test::sequential;
979
980// clang-format off
981
982UNORDERED_TEST(
983 visit,
984 ((map)(set))
985 ((value_type_generator_factory)(init_type_generator_factory))
986 ((lvalue_visitor)(visit_all)(visit_while)(exec_policy_visit_all)
987 (exec_policy_visit_while))
988 ((default_generator)(sequential)(limited_range)))
989
990UNORDERED_TEST(
991 visit,
992 ((transp_map)(transp_set))
993 ((value_type_generator_factory)(init_type_generator_factory))
994 ((transp_visitor))
995 ((default_generator)(sequential)(limited_range)))
996
997UNORDERED_TEST(
998 empty_visit,
999 ((map)(transp_map)(set)(transp_set))
1000 ((value_type_generator_factory)(init_type_generator_factory))
1001 ((default_generator)(sequential)(limited_range))
1002)
1003
1004UNORDERED_TEST(
1005 insert_and_visit,
1006 ((map)(set))
1007 ((value_type_generator_factory))
1008 ((sequential))
1009)
1010
1011UNORDERED_TEST(
1012 bulk_visit,
1013 ((map)(set))
1014 ((regular_key_extract))
1015 ((value_type_generator_factory))
1016 ((sequential))
1017)
1018
1019UNORDERED_TEST(
1020 bulk_visit,
1021 ((transp_map)(transp_set))
1022 ((transp_key_extract))
1023 ((value_type_generator_factory))
1024 ((sequential))
1025)
1026
1027// clang-format on
1028
1029RUN_TESTS()
1030

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