(root)/
gcc-13.2.0/
libstdc++-v3/
testsuite/
util/
regression/
rand/
assoc/
container_rand_regression_test.h
1 // -*- C++ -*-
2
3 // Copyright (C) 2005-2023 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING3. If not see
18 // <http://www.gnu.org/licenses/>.
19
20
21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
22
23 // Permission to use, copy, modify, sell, and distribute this software
24 // is hereby granted without fee, provided that the above copyright
25 // notice appears in all copies, and that both that copyright notice
26 // and this permission notice appear in supporting documentation. None
27 // of the above authors, nor IBM Haifa Research Laboratories, make any
28 // representation about the suitability of this software for any
29 // purpose. It is provided "as is" without express or implied
30 // warranty.
31
32 /**
33 * @file container_rand_regression_test.h
34 * Contains a random regression test for a specific container type.
35 */
36
37 #ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_H
38 #define PB_DS_CONTAINER_RAND_REGRESSION_TEST_H
39
40 #include <algorithm>
41 #include <string>
42 #include <sstream>
43 #include <utility>
44 #include <ext/pb_ds/assoc_container.hpp>
45 #include <io/prog_bar.hpp>
46 #include <testsuite_rng.h>
47 #include <regression/trait/assoc/trait.hpp>
48 #include <common_type/assoc/string_form.hpp>
49 #include <regression/rand/xml_formatter.hpp>
50
51 namespace __gnu_pbds
52 {
53 namespace test
54 {
55 namespace detail
56 {
57 // Rand test specialized for a specific container.
58 template<typename Cntnr>
59 class container_rand_regression_test
60 {
61 public:
62
63 container_rand_regression_test(unsigned long, size_t, size_t, double,
64 double, double, double, double, bool);
65
66 virtual
67 ~container_rand_regression_test();
68
69 void
70 operator()();
71
72 private:
73 typedef Cntnr cntnr;
74 typedef typename cntnr::allocator_type allocator_type;
75 typedef typename cntnr::size_type size_type;
76 typedef regression_test_traits<Cntnr> test_traits;
77 typedef typename test_traits::key_type key_type;
78 typedef typename test_traits::key_const_reference key_const_reference;
79 typedef typename test_traits::value_type value_type;
80 typedef typename test_traits::native_type native_type;
81 typedef twister_rand_gen gen;
82 typedef __gnu_pbds::container_traits<Cntnr> container_traits;
83 typedef __gnu_cxx::throw_allocator_random<char> alloc_t;
84
85 enum op
86 {
87 insert_op,
88 erase_op,
89 clear_op,
90 other_op
91 };
92
93 op
94 get_next_op();
95
96 size_t
97 get_next_sub_op(size_t);
98
99 static void
100 defs();
101
102 static void
103 key_defs();
104
105 static void
106 mapped_defs();
107
108 static void
109 value_defs();
110
111 static void
112 ds_defs();
113
114 static void
115 iterator_defs();
116
117 static void
118 node_iterator_defs(__gnu_pbds::detail::false_type);
119
120 static void
121 node_iterator_defs(__gnu_pbds::detail::true_type);
122
123 static void
124 policy_defs();
125
126 static void
127 policy_defs(__gnu_pbds::basic_hash_tag);
128
129 static void
130 policy_defs(__gnu_pbds::cc_hash_tag);
131
132 static void
133 policy_defs(__gnu_pbds::gp_hash_tag);
134
135 static void
136 policy_defs(__gnu_pbds::tree_tag);
137
138 static void
139 policy_defs(__gnu_pbds::list_update_tag);
140
141 static void
142 policy_defs(__gnu_pbds::pat_trie_tag);
143
144 void
145 policy_access();
146
147 void
148 policy_access(__gnu_pbds::basic_hash_tag);
149
150 void
151 policy_access(__gnu_pbds::cc_hash_tag);
152
153 void
154 policy_access(__gnu_pbds::gp_hash_tag);
155
156 void
157 policy_access(__gnu_pbds::tree_tag);
158
159 void
160 policy_access(__gnu_pbds::list_update_tag);
161
162 void
163 policy_access(__gnu_pbds::pat_trie_tag);
164
165 void
166 it_copy();
167
168 void
169 it_assign();
170
171 void
172 rev_it_copy();
173
174 void
175 rev_it_assign();
176
177 void
178 rev_it_copy_imp(__gnu_pbds::detail::false_type);
179
180 void
181 rev_it_copy_imp(__gnu_pbds::detail::true_type);
182
183 void
184 rev_it_assign_imp(__gnu_pbds::detail::false_type);
185
186 void
187 rev_it_assign_imp(__gnu_pbds::detail::true_type);
188
189 bool
190 default_constructor();
191
192 void
193 swap();
194
195 bool
196 copy_constructor();
197
198 bool
199 assignment_operator();
200
201 bool
202 it_constructor();
203
204 bool
205 it_constructor_imp(__gnu_pbds::cc_hash_tag);
206
207 bool
208 it_constructor_imp(__gnu_pbds::gp_hash_tag);
209
210 bool
211 it_constructor_imp(__gnu_pbds::tree_tag);
212
213 bool
214 it_constructor_imp(__gnu_pbds::list_update_tag);
215
216 bool
217 it_constructor_imp(__gnu_pbds::pat_trie_tag);
218
219 bool
220 insert();
221
222 bool
223 erase();
224
225 bool
226 erase_it();
227
228 bool
229 erase_it_imp(__gnu_pbds::detail::false_type);
230
231 bool
232 erase_it_imp(__gnu_pbds::detail::true_type);
233
234 bool
235 erase_rev_it();
236
237 bool
238 erase_rev_it_imp(__gnu_pbds::detail::false_type);
239
240 bool
241 erase_rev_it_imp(__gnu_pbds::detail::true_type);
242
243 bool
244 erase_if();
245
246 bool
247 clear();
248
249 bool
250 resize();
251
252 bool
253 resize_imp(__gnu_pbds::detail::true_type);
254
255 bool
256 resize_imp(__gnu_pbds::detail::false_type);
257
258 bool
259 get_set_loads();
260
261 bool
262 get_set_loads_imp(__gnu_pbds::detail::true_type);
263
264 bool
265 get_set_loads_imp(__gnu_pbds::detail::false_type);
266
267 void
268 get_set_load();
269
270 void
271 get_set_load_imp(__gnu_pbds::detail::true_type);
272
273 void
274 get_set_load_imp(__gnu_pbds::detail::false_type);
275
276 bool
277 subscript();
278
279 bool
280 subscript_imp(__gnu_pbds::detail::false_type);
281
282 bool
283 subscript_imp(__gnu_pbds::detail::true_type);
284
285 bool
286 split_join();
287
288 bool
289 split_join_imp(__gnu_pbds::detail::false_type);
290
291 bool
292 split_join_imp(__gnu_pbds::detail::true_type);
293
294 void
295 cmp(const Cntnr&, const native_type&, const std::string&);
296
297 void
298 basic_cmp_(const Cntnr&, const native_type&);
299
300 void
301 cmp_(const Cntnr&, const native_type&);
302
303 void
304 order_preserving_cmp_imp(const Cntnr&, const native_type&,
305 __gnu_pbds::detail::false_type);
306
307 void
308 order_preserving_cmp_imp(const Cntnr&, const native_type&,
309 __gnu_pbds::detail::true_type);
310
311 void
312 back_order_preserving_cmp_imp(const Cntnr&, const native_type&,
313 __gnu_pbds::detail::false_type);
314
315 void
316 back_order_preserving_cmp_imp(const Cntnr&, const native_type&,
317 __gnu_pbds::detail::true_type);
318
319 void
320 reverse_iteration_cmp_imp(const Cntnr&, const native_type&,
321 __gnu_pbds::detail::false_type);
322
323 void
324 reverse_iteration_cmp_imp(const Cntnr&, const native_type&,
325 __gnu_pbds::detail::true_type);
326
327 void
328 order_statistics_cmp_imp(const Cntnr&, const native_type&,
329 __gnu_pbds::detail::false_type);
330
331 void
332 order_statistics_cmp_imp(const Cntnr&, const native_type&,
333 __gnu_pbds::detail::true_type);
334
335 void
336 prefix_search_cmp_imp(const Cntnr&, const native_type&,
337 __gnu_pbds::detail::false_type);
338
339 void
340 prefix_search_cmp_imp(const Cntnr&, const native_type&,
341 __gnu_pbds::detail::true_type);
342
343 template<typename Const_It, class Const_Native_It>
344 void
345 it_cmp_imp(Const_It, Const_It, Const_Native_It, Const_Native_It);
346
347 template<typename Const_It, class Const_Native_It>
348 void
349 back_it_cmp_imp(Const_It, Const_It, Const_Native_It, Const_Native_It);
350
351 void
352 lower_bound_cmp_imp(const Cntnr&, const native_type&,
353 __gnu_pbds::detail::false_type);
354
355 void
356 lower_bound_cmp_imp(const Cntnr&, const native_type&,
357 __gnu_pbds::detail::true_type);
358
359 void
360 upper_bound_cmp_imp(const Cntnr&, const native_type&,
361 __gnu_pbds::detail::false_type);
362
363 void
364 upper_bound_cmp_imp(const Cntnr&, const native_type&,
365 __gnu_pbds::detail::true_type);
366
367 void
368 print_container(const native_type&, std::ostream& r_os = std::cerr) const;
369
370 void
371 print_container(const cntnr&, std::ostream& r_os = std::cerr) const;
372
373 struct destructor_printer
374 {
375 destructor_printer(const std::string& r_msg)
376 : m_msg(r_msg), m_print(true) { }
377
378 void
379 cancel_print()
380 { m_print = false; }
381
382 ~destructor_printer()
383 {
384 if (!m_print)
385 return;
386
387 std::cerr << std::endl << "Uncaught exception: " << std::endl
388 << m_msg << std::endl;
389 }
390
391 private:
392 const std::string m_msg;
393 bool m_print;
394 };
395
396 const unsigned long m_seed;
397 const size_t m_n;
398 const size_t m_m;
399 const double m_tp;
400 const double m_ip;
401 const double m_ep;
402 const double m_cp;
403 const double m_mp;
404 const bool m_disp;
405 twister_rand_gen m_g;
406 Cntnr* m_p_c;
407 native_type m_native_c;
408 alloc_t m_alloc;
409 size_t m_i;
410 };
411
412 #ifdef PB_DS_REGRESSION_TRACE
413 #define PB_DS_TRACE(X) std::cerr << X << std::endl
414 #else
415 #define PB_DS_TRACE(X)
416 #endif
417
418 #define PB_DS_CLASS_T_DEC \
419 template<typename Cntnr>
420
421 #define PB_DS_CLASS_C_DEC \
422 container_rand_regression_test<Cntnr>
423
424 #define PB_DS_COND_COMPARE(L, R) \
425 if (m_g.get_prob() < m_mp) \
426 cmp(L, R, __FUNCTION__);
427
428 #define PB_DS_RUN_MTHD(MTHD) \
429 { \
430 bool done = false; \
431 \
432 while (!done) \
433 done = MTHD(); \
434 }
435
436 #define PB_DS_THROW_IF_FAILED_(PRED, MORE, P_C, P_NC, F, L) \
437 if (!(PRED)) \
438 { \
439 std::cerr << "Failure at " << F << ": " << L << std::endl; \
440 std::cerr << MORE << std::endl; \
441 std::cerr << "container:" << std::endl; \
442 print_container(*(P_C)); \
443 std::cerr << std::endl; \
444 std::cerr << "native container:" << std::endl; \
445 print_container(*(P_NC)); \
446 std::cerr << std::endl; \
447 throw std::logic_error("fucked!"); \
448 }
449
450 #define PB_DS_THROW_IF_FAILED(PRED, MORE, P_C, P_NC) \
451 PB_DS_THROW_IF_FAILED_(PRED, MORE, P_C, P_NC, __FILE__, __LINE__)
452
453 #define PB_DS_SET_DESTRUCT_PRINT \
454 destructor_printer dest_print___(__FUNCTION__);
455
456 #define PB_DS_CANCEL_DESTRUCT_PRINT \
457 dest_print___.cancel_print();
458
459 #include <regression/rand/assoc/container_rand_regression_test.tcc>
460
461 #undef PB_DS_COND_COMPARE
462 #undef PB_DS_RUN_MTHD
463 #undef PB_DS_CLASS_T_DEC
464 #undef PB_DS_CLASS_C_DEC
465 #undef PB_DS_THROW_IF_FAILED_
466 #undef PB_DS_THROW_IF_FAILED
467 #undef PB_DS_SET_DESTRUCT_PRINT
468 #undef PB_DS_CANCEL_DESTRUCT_PRINT
469 #undef PB_DS_TRACE
470
471 } // namespace detail
472 } // namespace test
473 } // namespace __gnu_pbds
474
475 #endif