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

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