From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- .../container_rand_regression_test.h | 265 +++++++ .../container_rand_regression_test.tcc | 838 +++++++++++++++++++++ .../rand/priority_queue/rand_regression_test.hpp | 202 +++++ 3 files changed, 1305 insertions(+) create mode 100644 libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.h create mode 100644 libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc create mode 100644 libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp (limited to 'libstdc++-v3/testsuite/util/regression/rand/priority_queue') diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.h b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.h new file mode 100644 index 000000000..828541ce7 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.h @@ -0,0 +1,265 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2008, 2009 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// . + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file container_rand_regression_test.h + * Contains a random regression test for a specific container type. + */ + +#ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_H +#define PB_DS_CONTAINER_RAND_REGRESSION_TEST_H + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace __gnu_pbds +{ +namespace test +{ +namespace detail +{ + // Rand test specialized for a specific container. + template + class container_rand_regression_test + { + private: + typedef Cntnr cntnr; + typedef typename cntnr::allocator_type allocator_type; + typedef typename cntnr::size_type size_type; + typedef twister_rand_gen gen; + typedef basic_type value_type; + typedef native_priority_queue native_type; + typedef regression_test_traits test_traits; + + enum op + { + insert_op, + modify_op, + erase_op, + clear_op, + other_op + }; + + op + get_next_op(); + + size_t + get_next_sub_op(size_t max); + + static void + defs(); + + static void + value_defs(); + + static void + ds_defs(); + + static void + iterator_defs(); + + static void + policy_defs(); + + void + policy_access(); + + void + it_copy(); + + void + it_assign(); + + bool + default_constructor(); + + void + swap(); + + bool + copy_constructor(); + + bool + assignment_operator(); + + bool + it_constructor(); + + bool + push(); + + bool + modify(); + + bool + pop(); + + bool + erase_if(); + + bool + erase_it(); + + bool + clear(); + + bool + split_join(); + + void + cmp(const Cntnr& r_container, const native_type& r_native_c, + const std::string& r_call_fn); + + void + print_container(const native_type& r_cnt, + std::ostream& r_os = std::cerr) const; + + void + print_container(const cntnr& r_cnt, + std::ostream& r_os = std::cerr) const; + + struct destructor_printer + { + destructor_printer(const std::string& r_msg) + : m_msg(r_msg), m_print(true) { } + + void + cancel() + { m_print = false; } + + ~destructor_printer() + { + if (m_print) + { + std::cerr << std::endl << "Uncaught exception: " << std::endl + << m_msg << std::endl; + } + } + + const std::string m_msg; + bool m_print; + }; + + const unsigned long m_seed; + const size_t m_n; + const size_t m_m; + const double m_tp; + const double m_ip; + const double m_dp; + const double m_ep; + const double m_cp; + const double m_mp; + const bool m_disp; + twister_rand_gen m_g; + Cntnr* m_p_c; + native_type m_native_c; + allocator_type m_alloc; + size_t m_i; + + public: + container_rand_regression_test(unsigned long seed, size_t n, size_t m, + double tp, double ip, double dp, + double ep, double cp, double mp, + bool disp); + + virtual + ~container_rand_regression_test(); + + void + operator()(); + }; + + +#ifdef PB_DS_REGRESSION_TRACE +# define PB_DS_TRACE(X) std::cerr << X << std::endl +#else +# define PB_DS_TRACE(X) +#endif + +#define PB_DS_CLASS_T_DEC \ + template + +#define PB_DS_CLASS_C_DEC \ + container_rand_regression_test + +#define PB_DS_COND_COMPARE(L, R) \ + if (m_g.get_prob() < m_mp) \ + cmp(L, R, __FUNCTION__); + +#define PB_DS_RUN_MTHD(MTHD) \ + { \ + bool done = false; \ + while (!done) \ + done = MTHD(); \ + } + +#define _GLIBCXX_THROW_IF_(PRED, MORE, P_C, P_NC, F, L) \ + if (PRED) \ + { \ + std::cerr << "Failure at " << F << ": " << L << std::endl; \ + std::cerr << MORE << std::endl; \ + std::cerr << "container:" << std::endl; \ + print_container(*(P_C)); \ + std::cerr << std::endl; \ + std::cerr << "native container:" << std::endl; \ + print_container(*(P_NC)); \ + std::cerr << std::endl; \ + throw std::logic_error("pbds throw if failed"); \ + } + +#define _GLIBCXX_THROW_IF(PRED, MORE, P_C, P_NC) \ + _GLIBCXX_THROW_IF_(PRED, MORE, P_C, P_NC, __FILE__, __LINE__) + +#include + +#undef PB_DS_COND_COMPARE +#undef PB_DS_RUN_MTHD +#undef PB_DS_CLASS_T_DEC +#undef PB_DS_CLASS_C_DEC +#undef _GLIBCXX_THROW_IF_ +#undef _GLIBCXX_THROW_IF +#undef PB_DS_TRACE + +} // namespace detail +} // namespace test +} // namespace __gnu_pbds + +#endif diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc new file mode 100644 index 000000000..e929f3533 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc @@ -0,0 +1,838 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2008, 2009, 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// . + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file container_rand_regression_test.tcc + * Contains a random regression test for a specific container type. + */ + +#ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC +#define PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC + + // Constructor, copy constructor, assignment and destructor. +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +container_rand_regression_test(unsigned long seed, size_t n, size_t m, + double tp, double ip, double dp, double ep, + double cp, double mp, bool disp) +: m_seed(seed == 0 ? twister_rand_gen::get_time_determined_seed(): seed), + m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_dp(dp), m_ep(ep), m_cp(cp), + m_mp(mp), m_disp(disp), m_p_c(0) +{ } + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +~container_rand_regression_test() +{ } + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +default_constructor() +{ + PB_DS_TRACE("default_constructor"); + bool done = true; + m_alloc.set_probability(m_tp); + + try + { + m_p_c = new Cntnr; + } + catch(__gnu_cxx::forced_error&) + { + done = false; + } + + if (m_p_c) + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + + return done; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +swap() +{ + PB_DS_TRACE("swap"); + m_alloc.set_probability(0); + Cntnr* p_c = new Cntnr; + m_alloc.set_probability(1); + p_c->swap(*m_p_c); + std::swap(p_c, m_p_c); + delete p_c; + PB_DS_COND_COMPARE(*m_p_c, m_native_c); +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +copy_constructor() +{ + PB_DS_TRACE("copy_constructor"); + bool done = true; + Cntnr* p_c = 0; + m_alloc.set_probability(m_tp); + + typedef typename allocator_type::group_adjustor adjustor; + adjustor adjust(m_p_c->size()); + + try + { + p_c = new Cntnr(*m_p_c); + std::swap(p_c, m_p_c); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + } + + delete p_c; + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + return done; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +assignment_operator() +{ + PB_DS_TRACE("assignment operator"); + bool done = true; + Cntnr* p_c = 0; + m_alloc.set_probability(m_tp); + + typedef typename allocator_type::group_adjustor adjustor; + adjustor adjust(m_p_c->size()); + + try + { + p_c = new Cntnr(); + *p_c = *m_p_c; + std::swap(p_c, m_p_c); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + } + + delete p_c; + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + return done; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +it_constructor() +{ + bool done = true; + Cntnr* p_c = 0; + m_alloc.set_probability(m_tp); + typedef typename allocator_type::group_adjustor adjustor; + adjustor adjust(m_p_c->size()); + + try + { + switch(get_next_sub_op(3)) + { + case 0: + p_c = new Cntnr(m_p_c->get_cmp_fn()); + m_native_c.clear(); + break; + case 1: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end()); + break; + case 2: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_cmp_fn()); + break; + default: + _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c); + }; + + std::swap(p_c, m_p_c); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + } + + delete p_c; + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + return done; +} + + + // Compare. +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +cmp(const Cntnr& c, const native_type& native, const std::string& callfn) +{ + destructor_printer notify(__FUNCTION__); + + try + { + m_alloc.set_probability(1); + + const size_t size = c.size(); + const size_t native_size = native.size(); + _GLIBCXX_THROW_IF(size != native_size, size << " " << native_size, + &c, &native); + + const bool empty = c.empty(); + const bool native_empty = native.empty(); + _GLIBCXX_THROW_IF(empty != native_empty, empty << " " << native_empty, + &c, &native); + + const size_t it_size = std::distance(c.begin(), c.end()); + _GLIBCXX_THROW_IF(it_size != size, it_size << " " << size, &c, &native); + + if (!c.empty()) + { + const std::string native_top = native.top(); + const std::string top = test_traits::native_value(c.top()); + const bool top_smaller = std::less()(top, native_top); + const bool top_larger = std::less()(native_top, top); + + if (top_smaller || top_larger) + _GLIBCXX_THROW_IF(true, top << " " << native_top, &c, &native); + } + } + catch(...) + { + _GLIBCXX_THROW_IF(true, "call-fn: " + callfn, &c, &native); + } + + notify.cancel(); +} + + // Operators. +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +operator()() +{ + typedef xml_result_set_regression_formatter formatter_type; + formatter_type* p_fmt = 0; + if (m_disp) + p_fmt = new formatter_type(string_form::name(), + string_form::desc()); + + m_g.init(m_seed); + m_alloc.seed(m_seed); + + // The __throw_allocator::_S_label defaults to 0, so to make things + // easier and more precise when debugging, start at 1. + const size_t starting_label(1); + + try + { + prog_bar pb(m_n, std::cout, m_disp); + + for (m_i = starting_label; m_i <= m_n; ++m_i) + { + PB_DS_TRACE("Op #" << m_i); + + // Track allocation from this point only. + allocator_type::set_label(m_i); + switch(m_i) + { + case 1: + PB_DS_RUN_MTHD(default_constructor); + break; + case 2: + defs(); + break; + case 3: + policy_access(); + break; + case 4: + it_copy(); + break; + case 5: + it_assign(); + break; + default: + switch(get_next_op()) + { + case insert_op: + PB_DS_RUN_MTHD(push) + break; + case modify_op: + PB_DS_RUN_MTHD(modify) + break; + case erase_op: + switch(get_next_sub_op(3)) + { + case 0: + PB_DS_RUN_MTHD(pop) + break; + case 1: + PB_DS_RUN_MTHD(erase_if) + break; + case 2: + PB_DS_RUN_MTHD(erase_it) + break; + default: + _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c); + } + break; + case clear_op: + PB_DS_RUN_MTHD(clear) + break; + case other_op: + switch(get_next_sub_op(5)) + { + case 0: + swap(); + break; + case 1: + PB_DS_RUN_MTHD(copy_constructor) + break; + case 2: + PB_DS_RUN_MTHD(it_constructor) + break; + case 3: + PB_DS_RUN_MTHD(assignment_operator) + break; + case 4: + PB_DS_RUN_MTHD(split_join) + break; + default: + _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c); + } + break; + default: + _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c); + }; + } + pb.inc(); + } + } + catch (...) + { + std::cerr << "Failed at index " << m_i << std::endl; + delete m_p_c; + throw; + } + + // Clean up, then check for allocation by special label, set above. + allocator_type::set_label(0); + delete m_p_c; + + try + { + for (size_t n = starting_label; n <= m_n; ++n) + m_alloc.check_allocated(n); + } + catch (std::logic_error& obj) + { + // On fail, check_allocated should throw std::logic_error. + std::cerr << obj.what() << std::endl; + std::cerr << typeid(Cntnr).name() << std::endl; + throw; + } + + // Reset throw probability. + m_alloc.set_probability(0); + + if (m_disp) + { + std::cout << std::endl; + delete p_fmt; + } +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::op +PB_DS_CLASS_C_DEC:: +get_next_op() +{ + const double prob = m_g.get_prob(); + + if (prob < m_ip) + return insert_op; + + if (prob < m_ip + m_dp) + return modify_op; + + if (prob < m_ip + m_dp + m_ep) + return erase_op; + + if (prob < m_ip + m_dp + m_ep + m_cp) + return clear_op; + + _GLIBCXX_THROW_IF(prob > 1, prob, m_p_c, &m_native_c); + return other_op; +} + +PB_DS_CLASS_T_DEC +size_t +PB_DS_CLASS_C_DEC:: +get_next_sub_op(size_t max) +{ + const double p = m_g.get_prob(); + const double delta = 1 / static_cast(max); + size_t i = 0; + while (true) + if (p <= (i + 1) * delta) + { + _GLIBCXX_THROW_IF(i >= max, i << " " << max, m_p_c, &m_native_c); + return i; + } + else + ++i; +} + + // Insert. +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +push() +{ + PB_DS_TRACE("push"); + bool done = true; + destructor_printer notify(__FUNCTION__); + + try + { + m_alloc.set_probability(0); + value_type v = test_traits::generate_value(m_g, m_m); + m_alloc.set_probability(m_tp); + const typename cntnr::size_type sz = m_p_c->size(); + m_p_c->push(v); + _GLIBCXX_THROW_IF(sz != m_p_c->size() - 1, sz, m_p_c, &m_native_c); + m_native_c.push(test_traits::native_value(v)); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + } + catch(...) + { + _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + notify.cancel(); + return done; +} + + + // Modify. +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +modify() +{ + PB_DS_TRACE("modify"); + destructor_printer notify(__FUNCTION__); + + bool done = true; + try + { + m_alloc.set_probability(0); + value_type v = test_traits::generate_value(m_g, m_m); + + m_alloc.set_probability(m_tp); + typename cntnr::iterator it = m_p_c->begin(); + std::advance(it, m_g.get_unsigned_long(0, m_p_c->size())); + if (it != m_p_c->end()) + { + typedef typename test_traits::native_value_type native_value_type; + native_value_type native_v = test_traits::native_value(*it); + native_value_type new_native_v = test_traits::native_value(v); + m_p_c->modify(it, v); + m_native_c.modify(native_v, new_native_v); + } + } + catch(__gnu_cxx::forced_error&) + { + done = false; + _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + notify.cancel(); + return done; +} + + // Clear. +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +clear() +{ + PB_DS_TRACE("clear"); + m_p_c->clear(); + m_native_c.clear(); + return true; +} + + // Erase. +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +pop() +{ + PB_DS_TRACE("pop"); + destructor_printer notify(__FUNCTION__); + + bool done = true; + try + { + m_alloc.set_probability(1); + if (!m_p_c->empty()) + { + m_p_c->pop(); + m_native_c.pop(); + } + } + catch(__gnu_cxx::forced_error&) + { + done = false; + _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + notify.cancel(); + return done; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +erase_if() +{ + PB_DS_TRACE("erase_if"); + destructor_printer notify(__FUNCTION__); + + bool done = true; + try + { + typedef + typename std::iterator_traits::reference + it_const_reference; + + m_alloc.set_probability(1); + + typedef + typename test_traits::template erase_if_fn + erase_if_fn_t; + + const size_t ersd = m_p_c->erase_if(erase_if_fn_t()); + + typedef + typename test_traits::template erase_if_fn + native_erase_if_fn_t; + + const size_t native_ersd = m_native_c.erase_if(native_erase_if_fn_t()); + + _GLIBCXX_THROW_IF(ersd != native_ersd, ersd << " " << native_ersd, + m_p_c, &m_native_c); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + notify.cancel(); + return done; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +erase_it() +{ + PB_DS_TRACE("erase_it"); + destructor_printer notify(__FUNCTION__); + + bool done = true; + try + { + m_alloc.set_probability(1); + typename cntnr::iterator it = m_p_c->begin(); + std::advance(it, m_g.get_unsigned_long(0, m_p_c->size())); + + if (it != m_p_c->end()) + { + m_native_c.erase(*it); + m_p_c->erase(it); + } + } + catch(__gnu_cxx::forced_error&) + { + done = false; + _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + notify.cancel(); + return done; +} + + // Defs. +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +defs() +{ + // General container types. + typedef typename Cntnr::size_type test_size_type; + typedef typename Cntnr::difference_type difference_type; + value_defs(); + iterator_defs(); + policy_defs(); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +value_defs() +{ + typedef typename Cntnr::value_type test_value_type; + typedef typename Cntnr::reference test_reference; + typedef typename Cntnr::const_reference test_const_reference; + typedef typename Cntnr::pointer test_pointer; + typedef typename Cntnr::const_pointer test_const_pointer; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +ds_defs() +{ + typedef typename Cntnr::container_category test_container_category; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +iterator_defs() +{ + typedef typename Cntnr::point_iterator test_point_iterator; + typedef typename Cntnr::const_point_iterator const_test_point_iterator; + typedef typename Cntnr::iterator test_iterator; + typedef typename Cntnr::const_iterator const_test_iterator; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_defs() +{ + typedef typename Cntnr::allocator_type test_allocator; + typedef typename Cntnr::cmp_fn test_cmp_fn; +} + + +// Policy access. +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_access() +{ + PB_DS_TRACE("policy_access"); + + { + typename Cntnr::cmp_fn& r_t = m_p_c->get_cmp_fn(); + assert(&r_t); + } + + { + const typename Cntnr::cmp_fn& r_t =((const Cntnr& )*m_p_c).get_cmp_fn(); + assert(&r_t); + } +} + +// Split join. +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +split_join() +{ + PB_DS_TRACE("split_join"); + destructor_printer notify(__FUNCTION__); + + bool done = true; + try + { + m_alloc.set_probability(0); + Cntnr lhs(*m_p_c); + Cntnr rhs; + native_type native_lhs(m_native_c); + m_alloc.set_probability(m_tp); + + typedef typename test_traits::template erase_if_fn split_fn_t; + lhs.split(split_fn_t(), rhs); + + typedef typename test_traits::template erase_if_fn + native_split_fn_t; + + native_type native_rhs; + native_lhs.split(native_split_fn_t(), native_rhs); + PB_DS_COND_COMPARE(lhs, native_lhs); + PB_DS_COND_COMPARE(rhs, native_rhs); + + m_alloc.set_probability(m_tp); + + if (m_g.get_prob() < 0.5) + lhs.swap(rhs); + lhs.join(rhs); + + _GLIBCXX_THROW_IF(rhs.size() != 0, rhs.size(), m_p_c, &m_native_c); + _GLIBCXX_THROW_IF(!rhs.empty(), rhs.size(), m_p_c, &m_native_c); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + const bool b = __gnu_pbds::container_traits::split_join_can_throw; + _GLIBCXX_THROW_IF(!b, b, m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + notify.cancel(); + return done; +} + +// Iterator conversions. +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +it_copy() +{ + PB_DS_TRACE("it_copy"); + + { + typename cntnr::iterator it = m_p_c->end(); + typename cntnr::const_iterator const_it(it); + _GLIBCXX_THROW_IF(const_it != it, "", m_p_c, &m_native_c); + _GLIBCXX_THROW_IF(!(const_it == it), "", m_p_c, &m_native_c); + } + + { + typename cntnr::const_iterator const_it = m_p_c->end(); + typename cntnr::const_point_iterator const_find_it(const_it); + _GLIBCXX_THROW_IF(const_find_it != const_it, "", m_p_c, &m_native_c); + _GLIBCXX_THROW_IF(!(const_find_it == const_it), "", m_p_c, &m_native_c); + } + + { + typename cntnr::iterator it = m_p_c->end(); + typename cntnr::const_point_iterator const_find_it1(it); + _GLIBCXX_THROW_IF(const_find_it1 != it, "", m_p_c, &m_native_c); + _GLIBCXX_THROW_IF(!(const_find_it1 == it), "", m_p_c, &m_native_c); + + typename cntnr::point_iterator find_it1(it); + _GLIBCXX_THROW_IF(find_it1 != it, "", m_p_c, &m_native_c); + _GLIBCXX_THROW_IF(!(find_it1 == it), "", m_p_c, &m_native_c); + + typename cntnr::point_iterator find_it = m_p_c->end(); + typename cntnr::const_point_iterator const_find_it(find_it); + _GLIBCXX_THROW_IF(find_it != const_find_it, "", m_p_c, &m_native_c); + _GLIBCXX_THROW_IF(!(find_it == const_find_it), "", m_p_c, &m_native_c); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +it_assign() +{ + PB_DS_TRACE("it_assign"); + + { + typename cntnr::iterator it = m_p_c->end(); + typename cntnr::const_iterator const_it; + const_it = it; + _GLIBCXX_THROW_IF(const_it != it, "", m_p_c, &m_native_c); + _GLIBCXX_THROW_IF(!(const_it == it), "", m_p_c, &m_native_c); + + typename cntnr::const_point_iterator const_find_it; + const_find_it = it; + _GLIBCXX_THROW_IF(const_find_it != it, "", m_p_c, &m_native_c); + _GLIBCXX_THROW_IF(!(const_find_it == it), "", m_p_c, &m_native_c); + + typename cntnr::point_iterator find_it; + find_it = it; + _GLIBCXX_THROW_IF(find_it != it, "", m_p_c, &m_native_c); + _GLIBCXX_THROW_IF(!(find_it == it), "", m_p_c, &m_native_c); + } + + { + typename cntnr::const_iterator const_it = m_p_c->end(); + typename cntnr::const_point_iterator const_find_it; + const_find_it = const_it; + _GLIBCXX_THROW_IF(const_find_it != const_it, "", m_p_c, &m_native_c); + _GLIBCXX_THROW_IF(!(const_find_it == const_it), "", m_p_c, &m_native_c); + } + + { + typename cntnr::point_iterator find_it = m_p_c->end(); + typename cntnr::const_point_iterator const_find_it; + const_find_it = find_it; + _GLIBCXX_THROW_IF(find_it != const_find_it, "", m_p_c, &m_native_c); + _GLIBCXX_THROW_IF(!(find_it == const_find_it), "", m_p_c, &m_native_c); + } +} + + +// Diagnostics. +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +print_container(const native_type& cnt, std::ostream& os) const +{ + m_alloc.set_probability(0); + native_type cpy(cnt); + while (!cpy.empty()) + { + os << cpy.top() << std::endl; + cpy.pop(); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +print_container(const cntnr& cnt, std::ostream& os) const +{ + typedef typename cntnr::const_iterator const_iterator; + m_alloc.set_probability(0); + for (const_iterator it = cnt.begin(); it != cnt.end(); ++it) + os << *it << std::endl; +} + +#endif diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp new file mode 100644 index 000000000..37f8d51af --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp @@ -0,0 +1,202 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2008, 2009, 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// . + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file rand_regression_test.hpp + * Contains a random-operation test. + */ + +#ifndef PB_DS_PQ_RAND_REGRESSION_TEST_HPP +#define PB_DS_PQ_RAND_REGRESSION_TEST_HPP + +#include +#include +#include +#include +#include + +namespace __gnu_pbds +{ +namespace test +{ +namespace detail +{ +#ifndef PB_DS_REGRESSION +#error "Must define PB_DS_REGRESSION" +#endif + + struct rand_reg_test + { + public: + rand_reg_test(size_t seed, size_t n, size_t m, double tp, double ip, + double dp, double ep, double cp, double mp, bool d) + : m_sd(seed), m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_dp(dp), m_ep(ep), + m_cp(cp), m_mp(mp), m_disp(d) + { } + + template + void + operator()(Cntnr) + { + unsigned long ul = static_cast(m_sd); + container_rand_regression_test t(ul, m_n, m_n, m_tp, m_ip, m_dp, + m_ep, m_cp, m_mp, m_disp); + t(); + } + + private: + const size_t m_sd; + const size_t m_n; + const size_t m_m; + const double m_tp; + const double m_ip; + const double m_dp; + const double m_ep; + const double m_cp; + const double m_mp; + const bool m_disp; + }; + + void + usage(const std::string& r_name); + + void + verify_params(size_t&, size_t&, size_t&, + double&, double&, double&, double&, double&, double&, bool&); +} // namespace detail + + template + int + rand_regression_test(size_t iter, size_t keys, const std::string name, TL tl) + { + // Sane defaults. + size_t n = iter; + size_t m = keys; + size_t sd = 0; // 0 = time-determined arbitrary + double tp = 0.2; + double ip = 0.6; + double dp = 0.1; + double ep = 0.2; + double cp = 0.001; + double mp = 1; + bool disp = false; // show progress + + try + { + detail::verify_params(sd, n, m, tp, ip, dp, ep, cp, mp, disp); + } + catch(__gnu_pbds::test::illegal_input_error&) + { + detail::usage(name); + return -1; + } + catch(...) + { + return -2; + }; + + xml_test_rand_regression_formatter* p_fmt = 0; + if (sd == 0) + sd = twister_rand_gen::get_time_determined_seed(); + if (disp) + p_fmt = new xml_test_rand_regression_formatter(sd, n, m, tp, ip, dp, + ep, cp, mp); + + try + { + detail::rand_reg_test tst(sd, n, m, tp, ip, dp, ep, cp, mp, disp); + __gnu_cxx::typelist::apply(tst, tl); + } + catch(...) + { + std::cerr << "Test failed with seed " << sd << std::endl; + if (disp) + delete p_fmt; + return -1; + } + + if (disp) + delete p_fmt; + return 0; + } + +namespace detail +{ + inline void + usage(const std::string& name) + { + using namespace std; + cerr << "usage: " << name << " ['t' | 'f']" << + endl << endl; + + cerr << "This test performs basic regression tests on various priority queues." + "For each container, it performs a sequence of operations. At each iteration, it does " + "the following: " << endl; + cerr << "* Performs an operation on the container " << endl; + cerr << "* Performs the same operation on an cntnr object" << endl; + cerr << "* Possibly compares the container to the cntnr object" << endl; + cerr << "* Checks that exceptions (thrown by an allocator) " + "do not violate exception guarantees"; + + cerr << endl << endl; + + cerr << "sd = seed for random-number generator; 0 = " + "time determined value" << endl; + cerr << "n = number of iterations" << endl; + cerr << "m = number of distinct values" << endl; + cerr << "tp = probability that an exception will be actively thrown" << endl; + cerr << "ip = probability that an operation will be insert" << endl; + cerr << "dp = probability that an operation will be modify" << endl; + cerr << "ep = probability that an operation will be erase" << endl; + cerr << "cp = probability that an operation will be clear" << endl; + cerr << "(therefore, 1 - (ip + dp + ep + cp) = probability of any other operation)" << endl; + cerr << "mp = probability that the container will be compared to the cntnr object" << endl; + cerr << "'t' or 'f' determine whether progress will be displayed" << endl; + } + + inline void + verify_params(size_t& r_seed, size_t& r_n, + size_t& r_m, double& r_tp, double& r_ip, double& r_dp, + double& r_ep, double& r_cp, double& r_mp, bool& r_d) + { + verify_prob(r_tp); + verify_prob(r_ip); + verify_prob(r_dp); + verify_prob(r_ep); + verify_prob(r_cp); + verify_prob(r_mp); + verify_prob(r_ip + r_dp + r_ep + r_cp); + } +} // namespace detail +} // namespace test +} // namespace __gnu_pbds + +#endif -- cgit v1.2.3