1// -*- C++ -*- 2 3// Copyright (C) 2005-2015 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 51namespace __gnu_pbds 52{ 53namespace test 54{ 55namespace 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 476