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 | #ifndef BOOST_UNORDERED_TEST_CFOA_EXCEPTION_HELPERS_HPP |
7 | #define BOOST_UNORDERED_TEST_CFOA_EXCEPTION_HELPERS_HPP |
8 | |
9 | #include "../helpers/generators.hpp" |
10 | #include "../helpers/test.hpp" |
11 | #include "common_helpers.hpp" |
12 | |
13 | #include <boost/compat/latch.hpp> |
14 | #include <boost/container_hash/hash.hpp> |
15 | #include <boost/core/span.hpp> |
16 | #include <boost/unordered/unordered_flat_map.hpp> |
17 | #include <boost/unordered/unordered_flat_set.hpp> |
18 | |
19 | #include <algorithm> |
20 | #include <atomic> |
21 | #include <cmath> |
22 | #include <condition_variable> |
23 | #include <cstddef> |
24 | #include <iostream> |
25 | #include <mutex> |
26 | #include <random> |
27 | #include <thread> |
28 | #include <type_traits> |
29 | #include <vector> |
30 | |
31 | static std::size_t const num_threads = |
32 | std::max(a: 2u, b: std::thread::hardware_concurrency()); |
33 | |
34 | std::atomic_bool should_throw{false}; |
35 | |
36 | constexpr std::uint32_t throw_threshold = 2300; |
37 | constexpr std::uint32_t alloc_throw_threshold = 10; |
38 | |
39 | void enable_exceptions() { should_throw = true; } |
40 | void disable_exceptions() { should_throw = false; } |
41 | |
42 | struct exception_tag |
43 | { |
44 | }; |
45 | |
46 | struct stateful_hash |
47 | { |
48 | int x_ = -1; |
49 | |
50 | static std::atomic<std::uint32_t> c; |
51 | |
52 | void throw_helper() const |
53 | { |
54 | auto n = ++c; |
55 | if (should_throw && ((n + 1) % throw_threshold == 0)) { |
56 | throw exception_tag{}; |
57 | } |
58 | } |
59 | |
60 | stateful_hash() {} |
61 | stateful_hash(stateful_hash const& rhs) : x_(rhs.x_) {} |
62 | stateful_hash(stateful_hash&& rhs) noexcept |
63 | { |
64 | auto tmp = x_; |
65 | x_ = rhs.x_; |
66 | rhs.x_ = tmp; |
67 | } |
68 | |
69 | stateful_hash(int const x) : x_{x} {} |
70 | |
71 | template <class T> std::size_t operator()(T const& t) const |
72 | { |
73 | throw_helper(); |
74 | std::size_t h = static_cast<std::size_t>(x_); |
75 | boost::hash_combine(h, t); |
76 | return h; |
77 | } |
78 | |
79 | bool operator==(stateful_hash const& rhs) const { return x_ == rhs.x_; } |
80 | |
81 | friend std::ostream& operator<<(std::ostream& os, stateful_hash const& rhs) |
82 | { |
83 | os << "{ x_: " << rhs.x_ << " }" ; |
84 | return os; |
85 | } |
86 | |
87 | friend void swap(stateful_hash& lhs, stateful_hash& rhs) noexcept |
88 | { |
89 | if (&lhs != &rhs) { |
90 | std::swap(a&: lhs.x_, b&: rhs.x_); |
91 | } |
92 | } |
93 | }; |
94 | |
95 | std::atomic<std::uint32_t> stateful_hash::c{0}; |
96 | |
97 | struct stateful_key_equal |
98 | { |
99 | int x_ = -1; |
100 | static std::atomic<std::uint32_t> c; |
101 | |
102 | void throw_helper() const |
103 | { |
104 | auto n = ++c; |
105 | if (should_throw && ((n + 1) % throw_threshold == 0)) { |
106 | throw exception_tag{}; |
107 | } |
108 | } |
109 | |
110 | stateful_key_equal() = default; |
111 | stateful_key_equal(stateful_key_equal const&) = default; |
112 | stateful_key_equal(stateful_key_equal&& rhs) noexcept |
113 | { |
114 | auto tmp = x_; |
115 | x_ = rhs.x_; |
116 | rhs.x_ = tmp; |
117 | } |
118 | |
119 | stateful_key_equal(int const x) : x_{x} {} |
120 | |
121 | template <class T, class U> bool operator()(T const& t, U const& u) const |
122 | { |
123 | throw_helper(); |
124 | return t == u; |
125 | } |
126 | |
127 | bool operator==(stateful_key_equal const& rhs) const { return x_ == rhs.x_; } |
128 | |
129 | friend std::ostream& operator<<( |
130 | std::ostream& os, stateful_key_equal const& rhs) |
131 | { |
132 | os << "{ x_: " << rhs.x_ << " }" ; |
133 | return os; |
134 | } |
135 | |
136 | friend void swap(stateful_key_equal& lhs, stateful_key_equal& rhs) noexcept |
137 | { |
138 | if (&lhs != &rhs) { |
139 | std::swap(a&: lhs.x_, b&: rhs.x_); |
140 | } |
141 | } |
142 | }; |
143 | std::atomic<std::uint32_t> stateful_key_equal::c{0}; |
144 | |
145 | static std::atomic<std::uint32_t> allocator_c = {}; |
146 | |
147 | template <class T> struct stateful_allocator |
148 | { |
149 | int x_ = -1; |
150 | |
151 | void throw_helper() const |
152 | { |
153 | auto n = ++allocator_c; |
154 | if (should_throw && ((n + 1) % alloc_throw_threshold == 0)) { |
155 | throw exception_tag{}; |
156 | } |
157 | } |
158 | |
159 | using value_type = T; |
160 | |
161 | stateful_allocator() = default; |
162 | stateful_allocator(stateful_allocator const&) = default; |
163 | stateful_allocator(stateful_allocator&&) = default; |
164 | |
165 | stateful_allocator(int const x) : x_{x} {} |
166 | |
167 | template <class U> |
168 | stateful_allocator(stateful_allocator<U> const& rhs) : x_{rhs.x_} |
169 | { |
170 | } |
171 | |
172 | T* allocate(std::size_t n) |
173 | { |
174 | throw_helper(); |
175 | return static_cast<T*>(::operator new(n * sizeof(T))); |
176 | } |
177 | |
178 | void deallocate(T* p, std::size_t) { ::operator delete(p); } |
179 | |
180 | bool operator==(stateful_allocator const& rhs) const { return x_ == rhs.x_; } |
181 | bool operator!=(stateful_allocator const& rhs) const { return x_ != rhs.x_; } |
182 | }; |
183 | |
184 | struct raii |
185 | { |
186 | static std::atomic<std::uint32_t> default_constructor; |
187 | static std::atomic<std::uint32_t> copy_constructor; |
188 | static std::atomic<std::uint32_t> move_constructor; |
189 | static std::atomic<std::uint32_t> destructor; |
190 | |
191 | static std::atomic<std::uint32_t> copy_assignment; |
192 | static std::atomic<std::uint32_t> move_assignment; |
193 | |
194 | static std::atomic<std::uint32_t> c; |
195 | void throw_helper() const |
196 | { |
197 | auto n = ++c; |
198 | if (should_throw && ((n + 1) % throw_threshold == 0)) { |
199 | throw exception_tag{}; |
200 | } |
201 | } |
202 | |
203 | int x_ = -1; |
204 | |
205 | raii() |
206 | { |
207 | throw_helper(); |
208 | ++default_constructor; |
209 | } |
210 | |
211 | raii(int const x) : x_{x} |
212 | { |
213 | throw_helper(); |
214 | ++default_constructor; |
215 | } |
216 | |
217 | raii(raii const& rhs) : x_{rhs.x_} |
218 | { |
219 | throw_helper(); |
220 | ++copy_constructor; |
221 | } |
222 | raii(raii&& rhs) noexcept : x_{rhs.x_} |
223 | { |
224 | rhs.x_ = -1; |
225 | ++move_constructor; |
226 | } |
227 | ~raii() { ++destructor; } |
228 | |
229 | raii& operator=(raii const& rhs) |
230 | { |
231 | throw_helper(); |
232 | ++copy_assignment; |
233 | if (this != &rhs) { |
234 | x_ = rhs.x_; |
235 | } |
236 | return *this; |
237 | } |
238 | |
239 | raii& operator=(raii&& rhs) noexcept |
240 | { |
241 | ++move_assignment; |
242 | if (this != &rhs) { |
243 | x_ = rhs.x_; |
244 | rhs.x_ = -1; |
245 | } |
246 | return *this; |
247 | } |
248 | |
249 | friend bool operator==(raii const& lhs, raii const& rhs) |
250 | { |
251 | return lhs.x_ == rhs.x_; |
252 | } |
253 | |
254 | friend bool operator!=(raii const& lhs, raii const& rhs) |
255 | { |
256 | return !(lhs == rhs); |
257 | } |
258 | |
259 | friend bool operator==(raii const& lhs, int const x) { return lhs.x_ == x; } |
260 | friend bool operator!=(raii const& lhs, int const x) |
261 | { |
262 | return !(lhs.x_ == x); |
263 | } |
264 | |
265 | friend bool operator==(int const x, raii const& rhs) { return rhs.x_ == x; } |
266 | |
267 | friend bool operator!=(int const x, raii const& rhs) |
268 | { |
269 | return !(rhs.x_ == x); |
270 | } |
271 | |
272 | friend std::ostream& operator<<(std::ostream& os, raii const& rhs) |
273 | { |
274 | os << "{ x_: " << rhs.x_ << " }" ; |
275 | return os; |
276 | } |
277 | |
278 | friend std::ostream& operator<<( |
279 | std::ostream& os, std::pair<raii const, raii> const& rhs) |
280 | { |
281 | os << "pair<" << rhs.first << ", " << rhs.second << ">" ; |
282 | return os; |
283 | } |
284 | |
285 | static void reset_counts() |
286 | { |
287 | default_constructor = 0; |
288 | copy_constructor = 0; |
289 | move_constructor = 0; |
290 | destructor = 0; |
291 | copy_assignment = 0; |
292 | move_assignment = 0; |
293 | c = 0; |
294 | |
295 | stateful_hash::c = 0; |
296 | stateful_key_equal::c = 0; |
297 | allocator_c = 0; |
298 | } |
299 | |
300 | friend void swap(raii& lhs, raii& rhs) { std::swap(a&: lhs.x_, b&: rhs.x_); } |
301 | }; |
302 | |
303 | std::atomic<std::uint32_t> raii::default_constructor{0}; |
304 | std::atomic<std::uint32_t> raii::copy_constructor{0}; |
305 | std::atomic<std::uint32_t> raii::move_constructor{0}; |
306 | std::atomic<std::uint32_t> raii::destructor{0}; |
307 | std::atomic<std::uint32_t> raii::copy_assignment{0}; |
308 | std::atomic<std::uint32_t> raii::move_assignment{0}; |
309 | std::atomic<std::uint32_t> raii::c{0}; |
310 | |
311 | std::size_t hash_value(raii const& r) noexcept |
312 | { |
313 | boost::hash<int> hasher; |
314 | return hasher(r.x_); |
315 | } |
316 | |
317 | template <typename K> |
318 | struct exception_value_generator |
319 | { |
320 | using value_type = raii; |
321 | |
322 | value_type operator()(test::random_generator rg) |
323 | { |
324 | int* p = nullptr; |
325 | int a = generate(p, g: rg); |
326 | return value_type(a); |
327 | } |
328 | }; |
329 | |
330 | template <typename K, typename V> |
331 | struct exception_value_generator<std::pair<K, V> > |
332 | { |
333 | static constexpr bool const_key = std::is_const<K>::value; |
334 | static constexpr bool const_mapped = std::is_const<V>::value; |
335 | using value_type = std::pair< |
336 | typename std::conditional<const_key, raii const, raii>::type, |
337 | typename std::conditional<const_mapped, raii const, raii>::type>; |
338 | |
339 | value_type operator()(test::random_generator rg) |
340 | { |
341 | int* p = nullptr; |
342 | int a = generate(p, g: rg); |
343 | int b = generate(p, g: rg); |
344 | return std::make_pair(x: raii{a}, y: raii{b}); |
345 | } |
346 | }; |
347 | |
348 | struct exception_value_type_generator_factory_type |
349 | { |
350 | template <typename Container> |
351 | exception_value_generator<typename Container::value_type> get() |
352 | { |
353 | return {}; |
354 | } |
355 | } exception_value_type_generator_factory; |
356 | |
357 | struct exception_init_type_generator_factory_type |
358 | { |
359 | template <typename Container> |
360 | exception_value_generator<typename Container::init_type> get() |
361 | { |
362 | return {}; |
363 | } |
364 | } exception_init_type_generator_factory; |
365 | |
366 | struct exception_init_type_generator_type |
367 | { |
368 | std::pair<raii, raii> operator()(test::random_generator rg) |
369 | { |
370 | int* p = nullptr; |
371 | int a = generate(p, g: rg); |
372 | int b = generate(p, g: rg); |
373 | return std::make_pair(x: raii{a}, y: raii{b}); |
374 | } |
375 | } exception_init_type_generator; |
376 | |
377 | template <class T> |
378 | std::vector<boost::span<T> > split( |
379 | boost::span<T> s, std::size_t const nt /* num threads*/) |
380 | { |
381 | std::vector<boost::span<T> > subslices; |
382 | subslices.reserve(nt); |
383 | |
384 | auto a = s.size() / nt; |
385 | auto b = a; |
386 | if (s.size() % nt != 0) { |
387 | ++b; |
388 | } |
389 | |
390 | auto num_a = nt; |
391 | auto num_b = std::size_t{0}; |
392 | |
393 | if (nt * b > s.size()) { |
394 | num_a = nt * b - s.size(); |
395 | num_b = nt - num_a; |
396 | } |
397 | |
398 | auto sub_b = s.subspan(0, num_b * b); |
399 | auto sub_a = s.subspan(num_b * b); |
400 | |
401 | for (std::size_t i = 0; i < num_b; ++i) { |
402 | subslices.push_back(sub_b.subspan(i * b, b)); |
403 | } |
404 | |
405 | for (std::size_t i = 0; i < num_a; ++i) { |
406 | auto const is_last = i == (num_a - 1); |
407 | subslices.push_back( |
408 | sub_a.subspan(i * a, is_last ? boost::dynamic_extent : a)); |
409 | } |
410 | |
411 | return subslices; |
412 | } |
413 | |
414 | template <class T, class F> void thread_runner(std::vector<T>& values, F f) |
415 | { |
416 | boost::compat::latch latch(static_cast<std::ptrdiff_t>(num_threads)); |
417 | |
418 | std::vector<std::thread> threads; |
419 | auto subslices = split<T>(values, num_threads); |
420 | |
421 | for (std::size_t i = 0; i < num_threads; ++i) { |
422 | threads.emplace_back([&f, &subslices, i, &latch] { |
423 | latch.arrive_and_wait(); |
424 | |
425 | auto s = subslices[i]; |
426 | f(s); |
427 | }); |
428 | } |
429 | |
430 | for (auto& t : threads) { |
431 | t.join(); |
432 | } |
433 | } |
434 | |
435 | template <class T> using span_value_type = typename T::value_type; |
436 | |
437 | void check_raii_counts() |
438 | { |
439 | BOOST_TEST_GT(raii::destructor, 0u); |
440 | |
441 | BOOST_TEST_EQ( |
442 | raii::default_constructor + raii::copy_constructor + raii::move_constructor, |
443 | raii::destructor); |
444 | } |
445 | |
446 | template <class T> void shuffle_values(std::vector<T>& v) |
447 | { |
448 | std::random_device rd; |
449 | std::mt19937 g(rd()); |
450 | |
451 | std::shuffle(v.begin(), v.end(), g); |
452 | } |
453 | |
454 | template <class F> |
455 | auto make_random_values(std::size_t count, F f) -> std::vector<decltype(f())> |
456 | { |
457 | using vector_type = std::vector<decltype(f())>; |
458 | |
459 | vector_type v; |
460 | v.reserve(count); |
461 | for (std::size_t i = 0; i < count; ++i) { |
462 | v.emplace_back(f()); |
463 | } |
464 | return v; |
465 | } |
466 | |
467 | #endif // BOOST_UNORDERED_TEST_CFOA_EXCEPTION_HELPERS_HPP |
468 | |