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
11using test::default_generator;
12using test::limited_range;
13using test::sequential;
14
15using hasher = stateful_hash;
16using key_equal = stateful_key_equal;
17
18using map_type = boost::unordered::concurrent_flat_map<raii, raii, hasher,
19 key_equal, stateful_allocator<std::pair<raii const, raii> > >;
20
21using set_type = boost::unordered::concurrent_flat_set<raii, hasher,
22 key_equal, stateful_allocator<raii> >;
23
24map_type* test_map;
25set_type* test_set;
26
27namespace {
28 test::seed_t initialize_seed{748775921};
29
30 template <typename X>
31 void rehash_no_insert(X*)
32 {
33 using allocator_type = typename X::allocator_type;
34
35 X x(0, hasher(1), key_equal(2), allocator_type(3));
36 BOOST_TEST_EQ(x.bucket_count(), 0u);
37
38 x.rehash(1024);
39 BOOST_TEST_GE(x.bucket_count(), 1024u);
40
41 x.rehash(512);
42 BOOST_TEST_GE(x.bucket_count(), 512u);
43 BOOST_TEST_LT(x.bucket_count(), 1024u);
44
45 x.rehash(0);
46 BOOST_TEST_EQ(x.bucket_count(), 0u);
47 }
48
49 template <typename X>
50 void reserve_no_insert(X*)
51 {
52 using allocator_type = typename X::allocator_type;
53 using size_type = typename X::size_type;
54
55 X x(0, hasher(1), key_equal(2), allocator_type(3));
56
57 auto f = [&x](double c) {
58 return static_cast<size_type>(std::ceil(c / x.max_load_factor()));
59 };
60
61 BOOST_TEST_EQ(x.bucket_count(), f(0.0));
62
63 x.reserve(1024);
64 BOOST_TEST_GE(x.bucket_count(), f(1024.0));
65
66 x.reserve(512);
67 BOOST_TEST_GE(x.bucket_count(), f(512.0));
68 BOOST_TEST_LT(x.bucket_count(), f(1024.0));
69
70 x.reserve(0);
71 BOOST_TEST_EQ(x.bucket_count(), f(0.0));
72 }
73
74 template <class X, class GF>
75 void insert_and_erase_with_rehash(
76 X*, GF gen_factory, test::random_generator rg)
77 {
78 using allocator_type = typename X::allocator_type;
79
80 auto gen = gen_factory.template get<X>();
81 auto vals1 = make_random_values(1024 * 8, [&] { return gen(rg); });
82
83 auto erase_indices = std::vector<std::size_t>(vals1.size());
84 for (std::size_t idx = 0; idx < erase_indices.size(); ++idx) {
85 erase_indices[idx] = idx;
86 }
87 shuffle_values(v&: erase_indices);
88
89 auto reference_cont = reference_container<X>();
90 reference_cont.insert(vals1.begin(), vals1.end());
91
92 {
93 raii::reset_counts();
94
95 X x(0, hasher(1), key_equal(2), allocator_type(3));
96
97 std::thread t1, t2, t3;
98 boost::compat::latch l(2);
99
100 std::mutex m;
101 std::condition_variable cv;
102 std::atomic_bool done1{false}, done2{false};
103 std::atomic<unsigned long long> call_count{0};
104 bool ready = false;
105
106 auto const old_mc = +raii::move_constructor;
107 BOOST_TEST_EQ(old_mc, 0u);
108
109 t1 = std::thread([&x, &vals1, &l, &done1, &cv, &ready, &m] {
110 l.arrive_and_wait();
111
112 for (std::size_t idx = 0; idx < vals1.size(); ++idx) {
113 auto const& val = vals1[idx];
114 x.insert(val);
115
116 if (idx % (vals1.size() / 128) == 0) {
117 {
118 std::unique_lock<std::mutex> lk(m);
119 ready = true;
120 }
121 cv.notify_all();
122 std::this_thread::yield();
123 }
124 }
125
126 done1 = true;
127 {
128 std::unique_lock<std::mutex> lk(m);
129 ready = true;
130 }
131 cv.notify_all();
132 });
133
134 t2 =
135 std::thread([&x, &vals1, &erase_indices, &l, &done2, &cv, &m, &ready] {
136 l.arrive_and_wait();
137
138 for (std::size_t idx = 0; idx < erase_indices.size(); ++idx) {
139 auto const& val = vals1[erase_indices[idx]];
140 x.erase(get_key(val));
141 if (idx % 100 == 0) {
142 std::this_thread::yield();
143 }
144 }
145
146 done2 = true;
147 {
148 std::unique_lock<std::mutex> lk(m);
149 ready = true;
150 }
151 cv.notify_all();
152 });
153
154 t3 =
155 std::thread([&x, &vals1, &m, &cv, &done1, &done2, &call_count, &ready] {
156 do {
157 {
158 std::unique_lock<std::mutex> lk(m);
159 cv.wait(lk, [&ready] { return ready; });
160 ready = false;
161 }
162
163 auto const bc = static_cast<std::size_t>(rand()) % vals1.size();
164 x.rehash(bc);
165 call_count += 1;
166
167 std::this_thread::yield();
168 } while (!done1 || !done2);
169
170 BOOST_TEST(done1);
171 BOOST_TEST(done2);
172 });
173
174 t1.join();
175 t2.join();
176 t3.join();
177
178 BOOST_TEST_GE(call_count, 1u);
179
180 test_fuzzy_matches_reference(x, reference_cont, rg);
181 }
182
183 check_raii_counts();
184 }
185} // namespace
186
187// clang-format off
188UNORDERED_TEST(
189 rehash_no_insert,
190 ((test_map)(test_set)))
191
192UNORDERED_TEST(
193 reserve_no_insert,
194 ((test_map)(test_set)))
195
196UNORDERED_TEST(
197 insert_and_erase_with_rehash,
198 ((test_map)(test_set))
199 ((value_type_generator_factory))
200 ((default_generator)(sequential)(limited_range)))
201// clang-format on
202
203RUN_TESTS()
204

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