1// Copyright (C) 2023 Christian Mazakas
2// Copyright (C) 2023 Joaquin M Lopez Munoz
3// Copyright (C) 2024 Braden Ganetsky
4// Distributed under the Boost Software License, Version 1.0. (See accompanying
5// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7#include "helpers.hpp"
8#include "../helpers/count.hpp"
9
10#include <boost/unordered/concurrent_flat_map.hpp>
11#include <boost/unordered/concurrent_flat_set.hpp>
12
13#include <boost/core/ignore_unused.hpp>
14
15namespace {
16 test::seed_t initialize_seed(335740237);
17
18 template <typename Container, typename Value>
19 bool member_emplace(Container& x, Value const & v)
20 {
21 return x.emplace(v.x_);
22 }
23
24 template <typename Container, typename Key, typename Value>
25 bool member_emplace(Container& x, std::pair<Key, Value> const & v)
26 {
27 return x.emplace(v.first.x_, v.second.x_);
28 }
29
30 template <typename Container, typename Value, typename F>
31 bool member_emplace_or_visit(Container& x, Value& v, F f)
32 {
33 return x.emplace_or_visit(v.x_, f);
34 }
35
36 template <typename Container, typename Key, typename Value, typename F>
37 bool member_emplace_or_visit(Container& x, std::pair<Key, Value>& v, F f)
38 {
39 return x.emplace_or_visit(v.first.x_, v.second.x_, f);
40 }
41
42 template <typename Container, typename Value, typename F>
43 bool member_emplace_or_cvisit(Container& x, Value& v, F f)
44 {
45 return x.emplace_or_cvisit(v.x_, f);
46 }
47
48 template <typename Container, typename Key, typename Value, typename F>
49 bool member_emplace_or_cvisit(Container& x, std::pair<Key, Value>& v, F f)
50 {
51 return x.emplace_or_cvisit(v.first.x_, v.second.x_, f);
52 }
53
54 struct lvalue_emplacer_type
55 {
56 template <class T, class X> void call_impl(std::vector<T>& values, X& x)
57 {
58 static constexpr auto value_type_cardinality =
59 value_cardinality<typename X::value_type>::value;
60
61 std::atomic<std::uint64_t> num_inserts{0};
62 thread_runner(values, [&x, &num_inserts](boost::span<T> s) {
63 for (auto const& r : s) {
64 bool b = member_emplace(x, r);
65 if (b) {
66 ++num_inserts;
67 }
68 }
69 });
70 BOOST_TEST_EQ(num_inserts, x.size());
71
72 std::uint64_t const default_constructors = value_type_cardinality == 2
73 ? values.size() + num_inserts
74 : values.size();
75 BOOST_TEST_EQ(raii::default_constructor, default_constructors);
76
77 BOOST_TEST_EQ(raii::copy_constructor, 0u);
78 BOOST_TEST_EQ(raii::copy_assignment, 0u);
79 BOOST_TEST_EQ(raii::move_assignment, 0u);
80 }
81 template <class T, class X> void operator()(std::vector<T>& values, X& x)
82 {
83 static constexpr auto value_type_cardinality =
84 value_cardinality<typename X::value_type>::value;
85
86 call_impl(values, x);
87 BOOST_TEST_GE(raii::move_constructor, value_type_cardinality * x.size());
88 }
89 } lvalue_emplacer;
90
91 struct norehash_lvalue_emplacer_type : public lvalue_emplacer_type
92 {
93 template <class T, class X> void operator()(std::vector<T>& values, X& x)
94 {
95 x.reserve(values.size());
96 lvalue_emplacer_type::call_impl(values, x);
97 BOOST_TEST_EQ(raii::move_constructor, x.size());
98 }
99 } norehash_lvalue_emplacer;
100
101 struct lvalue_emplace_or_cvisit_type
102 {
103 template <class T, class X> void operator()(std::vector<T>& values, X& x)
104 {
105 static constexpr auto value_type_cardinality =
106 value_cardinality<typename X::value_type>::value;
107
108 std::atomic<std::uint64_t> num_inserts{0};
109 std::atomic<std::uint64_t> num_invokes{0};
110 thread_runner(values, [&x, &num_inserts, &num_invokes](boost::span<T> s) {
111 for (auto& r : s) {
112 bool b = member_emplace_or_cvisit(
113 x, r,
114 [&num_invokes](typename X::value_type const& v) {
115 (void)v;
116 ++num_invokes;
117 });
118
119 if (b) {
120 ++num_inserts;
121 }
122 }
123 });
124
125 BOOST_TEST_EQ(num_inserts, x.size());
126 BOOST_TEST_EQ(num_invokes, values.size() - x.size());
127
128 BOOST_TEST_EQ(
129 raii::default_constructor, value_type_cardinality * values.size());
130 BOOST_TEST_EQ(raii::copy_constructor, 0u);
131 BOOST_TEST_GE(raii::move_constructor, value_type_cardinality * x.size());
132 BOOST_TEST_EQ(raii::move_assignment, 0u);
133 BOOST_TEST_EQ(raii::copy_assignment, 0u);
134 }
135 } lvalue_emplace_or_cvisit;
136
137 struct lvalue_emplace_or_visit_type
138 {
139 template <class T, class X> void operator()(std::vector<T>& values, X& x)
140 {
141 static constexpr auto value_type_cardinality =
142 value_cardinality<typename X::value_type>::value;
143
144 // concurrent_flat_set visit is always const access
145 using arg_type = typename std::conditional<
146 std::is_same<typename X::key_type, typename X::value_type>::value,
147 typename X::value_type const,
148 typename X::value_type
149 >::type;
150
151 std::atomic<std::uint64_t> num_inserts{0};
152 std::atomic<std::uint64_t> num_invokes{0};
153 thread_runner(values, [&x, &num_inserts, &num_invokes](boost::span<T> s) {
154 for (auto& r : s) {
155 bool b = member_emplace_or_visit(
156 x, r,
157 [&num_invokes](arg_type& v) {
158 (void)v;
159 ++num_invokes;
160 });
161
162 if (b) {
163 ++num_inserts;
164 }
165 }
166 });
167
168 BOOST_TEST_EQ(num_inserts, x.size());
169 BOOST_TEST_EQ(num_invokes, values.size() - x.size());
170
171 BOOST_TEST_EQ(
172 raii::default_constructor, value_type_cardinality * values.size());
173 BOOST_TEST_EQ(raii::copy_constructor, 0u);
174 BOOST_TEST_GE(raii::move_constructor, value_type_cardinality * x.size());
175 BOOST_TEST_EQ(raii::move_assignment, 0u);
176 BOOST_TEST_EQ(raii::copy_assignment, 0u);
177 }
178 } lvalue_emplace_or_visit;
179
180 struct copy_emplacer_type
181 {
182 template <class T, class X> void operator()(std::vector<T>& values, X& x)
183 {
184 static constexpr auto value_type_cardinality =
185 value_cardinality<typename X::value_type>::value;
186
187 std::atomic<std::uint64_t> num_inserts{0};
188 thread_runner(values, [&x, &num_inserts](boost::span<T> s) {
189 for (auto const& r : s) {
190 bool b = x.emplace(r);
191 if (b) {
192 ++num_inserts;
193 }
194 }
195 });
196 BOOST_TEST_EQ(num_inserts, x.size());
197 BOOST_TEST_EQ(raii::default_constructor, 0u);
198
199 BOOST_TEST_EQ(raii::copy_constructor, value_type_cardinality * x.size());
200 BOOST_TEST_GT(raii::move_constructor, 0u);
201
202 BOOST_TEST_EQ(raii::copy_assignment, 0u);
203 BOOST_TEST_EQ(raii::move_assignment, 0u);
204 }
205 } copy_emplacer;
206
207 struct move_emplacer_type
208 {
209 template <class T, class X> void operator()(std::vector<T>& values, X& x)
210 {
211 static constexpr auto value_type_cardinality =
212 value_cardinality<typename X::value_type>::value;
213
214 std::atomic<std::uint64_t> num_inserts{0};
215 thread_runner(values, [&x, &num_inserts](boost::span<T> s) {
216 for (auto& r : s) {
217 bool b = x.emplace(std::move(r));
218 if (b) {
219 ++num_inserts;
220 }
221 }
222 });
223 BOOST_TEST_EQ(num_inserts, x.size());
224 BOOST_TEST_EQ(raii::default_constructor, 0u);
225
226#if defined(BOOST_MSVC)
227#pragma warning(push)
228#pragma warning(disable : 4127) // conditional expression is constant
229#endif
230 if (std::is_same<T, typename X::value_type>::value &&
231 !std::is_same<typename X::key_type,
232 typename X::value_type>::value) { // map value_type can only be
233 // copied, no move
234 BOOST_TEST_EQ(raii::copy_constructor, x.size());
235 } else {
236 BOOST_TEST_EQ(raii::copy_constructor, 0u);
237 }
238#if defined(BOOST_MSVC)
239#pragma warning(pop) // C4127
240#endif
241 BOOST_TEST_GT(raii::move_constructor, value_type_cardinality * x.size());
242
243 BOOST_TEST_EQ(raii::copy_assignment, 0u);
244 BOOST_TEST_EQ(raii::move_assignment, 0u);
245 }
246 } move_emplacer;
247
248 template <class X, class GF, class F>
249 void emplace(X*, GF gen_factory, F emplacer, test::random_generator rg)
250 {
251 auto gen = gen_factory.template get<X>();
252 auto values = make_random_values(1024 * 16, [&] { return gen(rg); });
253 auto reference_cont = reference_container<X>(values.begin(), values.end());
254 raii::reset_counts();
255
256 {
257 X x;
258
259 emplacer(values, x);
260
261 BOOST_TEST_EQ(x.size(), reference_cont.size());
262
263 using value_type = typename X::value_type;
264 BOOST_TEST_EQ(x.size(), x.visit_all([&](value_type const& v) {
265 BOOST_TEST(reference_cont.contains(get_key(v)));
266 if (rg == test::sequential) {
267 BOOST_TEST_EQ(v, *reference_cont.find(get_key(v)));
268 }
269 }));
270 }
271
272 BOOST_TEST_GE(raii::default_constructor, 0u);
273 BOOST_TEST_GE(raii::copy_constructor, 0u);
274 BOOST_TEST_GE(raii::move_constructor, 0u);
275 BOOST_TEST_GT(raii::destructor, 0u);
276
277 BOOST_TEST_EQ(raii::default_constructor + raii::copy_constructor +
278 raii::move_constructor,
279 raii::destructor);
280 }
281
282 boost::unordered::concurrent_flat_map<raii, raii>* map;
283 boost::unordered::concurrent_flat_set<raii>* set;
284
285} // namespace
286
287using test::default_generator;
288using test::limited_range;
289using test::sequential;
290
291// clang-format off
292
293UNORDERED_TEST(
294 emplace,
295 ((map)(set))
296 ((value_type_generator_factory)(init_type_generator_factory))
297 ((lvalue_emplacer)(norehash_lvalue_emplacer)
298 (lvalue_emplace_or_cvisit)(lvalue_emplace_or_visit)(copy_emplacer)(move_emplacer))
299 ((default_generator)(sequential)(limited_range)))
300
301// clang-format on
302
303namespace {
304 using converting_key_type = basic_raii<struct converting_key_tag_>;
305 using converting_value_type = basic_raii<struct converting_value_tag_>;
306
307 class counted_key_type : public basic_raii<struct counted_key_tag_>
308 {
309 public:
310 using basic_raii::basic_raii;
311 counted_key_type() = default;
312 counted_key_type(const converting_key_type& k) : counted_key_type(k.x_) {}
313 };
314 class counted_value_type : public basic_raii<struct counted_value_tag_>
315 {
316 public:
317 using basic_raii::basic_raii;
318 counted_value_type() = default;
319 counted_value_type(const converting_value_type& v)
320 : counted_value_type(v.x_)
321 {
322 }
323 };
324
325 void reset_counts()
326 {
327 counted_key_type::reset_counts();
328 counted_value_type::reset_counts();
329 converting_key_type::reset_counts();
330 converting_value_type::reset_counts();
331 }
332
333 using test::smf_count;
334
335 template <class T> smf_count count_for()
336 {
337 return test::smf_count{
338 .default_constructions: (int)T::default_constructor.load(std::memory_order_relaxed),
339 .copy_constructions: (int)T::copy_constructor.load(std::memory_order_relaxed),
340 .move_constructions: (int)T::move_constructor.load(std::memory_order_relaxed),
341 .copy_assignments: (int)T::copy_assignment.load(std::memory_order_relaxed),
342 .move_assignments: (int)T::move_assignment.load(std::memory_order_relaxed),
343 .destructions: (int)T::destructor.load(std::memory_order_relaxed)};
344 }
345
346 enum emplace_kind
347 {
348 copy,
349 move
350 };
351
352 enum emplace_status
353 {
354 fail,
355 success
356 };
357
358 struct counted_key_checker_type
359 {
360 using key_type = counted_key_type;
361 void operator()(emplace_kind kind, emplace_status status)
362 {
363 int copies = (kind == copy && status == success) ? 1 : 0;
364 int moves = (kind == move && status == success) ? 1 : 0;
365 BOOST_TEST_EQ(
366 count_for<counted_key_type>(), (smf_count{0, copies, moves, 0, 0, 0}));
367 }
368 } counted_key_checker;
369
370 struct converting_key_checker_type
371 {
372 using key_type = converting_key_type;
373 void operator()(emplace_kind, emplace_status status)
374 {
375 int moves = (status == success) ? 1 : 0;
376 BOOST_TEST_EQ(
377 count_for<counted_key_type>(), (smf_count{1, 0, moves, 0, 0, 1}));
378 }
379 } converting_key_checker;
380
381 struct counted_value_checker_type
382 {
383 using mapped_type = counted_value_type;
384 void operator()(emplace_kind kind, emplace_status status)
385 {
386 int copies = (kind == copy && status == success) ? 1 : 0;
387 int moves = (kind == move && status == success) ? 1 : 0;
388 BOOST_TEST_EQ(count_for<counted_value_type>(),
389 (smf_count{0, copies, moves, 0, 0, 0}));
390 }
391 } counted_value_checker;
392
393 struct converting_value_checker_type
394 {
395 using mapped_type = converting_value_type;
396 void operator()(emplace_kind, emplace_status status)
397 {
398 int ctors = (status == success) ? 1 : 0;
399 BOOST_TEST_EQ(
400 count_for<counted_value_type>(), (smf_count{ctors, 0, 0, 0, 0, 0}));
401 }
402 } converting_value_checker;
403
404 template <class X, class KC, class VC>
405 void emplace_map_key_value(
406 X*, emplace_kind kind, KC key_checker, VC value_checker)
407 {
408 using container = X;
409 using key_type = typename KC::key_type;
410 using mapped_type = typename VC::mapped_type;
411
412 container x;
413 key_type key{};
414 key_type key2 = key;
415 mapped_type value{};
416 mapped_type value2 = value;
417
418 {
419 reset_counts();
420 auto ret = (kind == copy) ? x.emplace(key, value)
421 : x.emplace(std::move(key), std::move(value));
422 BOOST_TEST_EQ(ret, true);
423 key_checker(kind, success);
424 value_checker(kind, success);
425 BOOST_TEST_EQ(
426 count_for<converting_key_type>(), (smf_count{0, 0, 0, 0, 0, 0}));
427 BOOST_TEST_EQ(
428 count_for<converting_value_type>(), (smf_count{0, 0, 0, 0, 0, 0}));
429 }
430
431 {
432 reset_counts();
433 bool ret = x.emplace(key2, value2);
434 BOOST_TEST_EQ(ret, false);
435 key_checker(kind, fail);
436 value_checker(kind, fail);
437 BOOST_TEST_EQ(
438 count_for<converting_key_type>(), (smf_count{0, 0, 0, 0, 0, 0}));
439 BOOST_TEST_EQ(
440 count_for<converting_value_type>(), (smf_count{0, 0, 0, 0, 0, 0}));
441 }
442
443 {
444 reset_counts();
445 bool ret = x.emplace(std::move(key2), std::move(value2));
446 BOOST_TEST_EQ(ret, false);
447 key_checker(kind, fail);
448 value_checker(kind, fail);
449 BOOST_TEST_EQ(
450 count_for<converting_key_type>(), (smf_count{0, 0, 0, 0, 0, 0}));
451 BOOST_TEST_EQ(
452 count_for<converting_value_type>(), (smf_count{0, 0, 0, 0, 0, 0}));
453 }
454 }
455
456 boost::unordered::concurrent_flat_map<counted_key_type, counted_value_type>*
457 test_counted_flat_map = {};
458
459} // namespace
460
461// clang-format off
462
463UNORDERED_TEST(
464 emplace_map_key_value,
465 ((test_counted_flat_map))
466 ((copy)(move))
467 ((counted_key_checker)(converting_key_checker))
468 ((counted_value_checker)(converting_value_checker))
469)
470
471// clang-format on
472
473RUN_TESTS()
474

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