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
31static std::size_t const num_threads =
32 std::max(a: 2u, b: std::thread::hardware_concurrency());
33
34std::atomic_bool should_throw{false};
35
36constexpr std::uint32_t throw_threshold = 2300;
37constexpr std::uint32_t alloc_throw_threshold = 10;
38
39void enable_exceptions() { should_throw = true; }
40void disable_exceptions() { should_throw = false; }
41
42struct exception_tag
43{
44};
45
46struct 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
95std::atomic<std::uint32_t> stateful_hash::c{0};
96
97struct 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};
143std::atomic<std::uint32_t> stateful_key_equal::c{0};
144
145static std::atomic<std::uint32_t> allocator_c = {};
146
147template <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
184struct 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
303std::atomic<std::uint32_t> raii::default_constructor{0};
304std::atomic<std::uint32_t> raii::copy_constructor{0};
305std::atomic<std::uint32_t> raii::move_constructor{0};
306std::atomic<std::uint32_t> raii::destructor{0};
307std::atomic<std::uint32_t> raii::copy_assignment{0};
308std::atomic<std::uint32_t> raii::move_assignment{0};
309std::atomic<std::uint32_t> raii::c{0};
310
311std::size_t hash_value(raii const& r) noexcept
312{
313 boost::hash<int> hasher;
314 return hasher(r.x_);
315}
316
317template <typename K>
318struct 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
330template <typename K, typename V>
331struct 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
348struct 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
357struct 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
366struct 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
377template <class T>
378std::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
414template <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
435template <class T> using span_value_type = typename T::value_type;
436
437void 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
446template <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
454template <class F>
455auto 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

source code of boost/libs/unordered/test/cfoa/exception_helpers.hpp