libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2019 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