diff options
Diffstat (limited to 'libstdc++-v3/testsuite/util/regression')
19 files changed, 5643 insertions, 0 deletions
diff --git a/libstdc++-v3/testsuite/util/regression/basic_type.hpp b/libstdc++-v3/testsuite/util/regression/basic_type.hpp new file mode 100644 index 000000000..9fe6ef24d --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/basic_type.hpp @@ -0,0 +1,94 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 basic_type.hpp + * Contains a type used for regression tests' key and data. + */ + +#ifndef PB_DS_BASIC_TYPE_HPP +#define PB_DS_BASIC_TYPE_HPP + +#include <string> +#include <ext/throw_allocator.h> + +namespace __gnu_pbds +{ +namespace test +{ +#define PB_DS_BASE_C_DEC \ + std::basic_string<char, std::char_traits<char>, \ + __gnu_cxx::throw_allocator_random<char> > + + struct basic_type : public PB_DS_BASE_C_DEC + { + private: + typedef PB_DS_BASE_C_DEC base_type; + + public: + enum + { + distinct_chars = 4 + }; + + basic_type() { } + + template<typename Gen> + basic_type(Gen& r_gen, size_t max) + { + size_t rnd = r_gen.get_unsigned_long(0, static_cast<unsigned long>(max)); + while (rnd > 0) + { + base_type::push_back('a' + static_cast<char>(rnd % distinct_chars)); + rnd /= distinct_chars; + } + } + + basic_type(const std::string other) + { + std::string::const_iterator it = other.begin(); + while (it != other.end()) + { + base_type::push_back(*it); + ++it; + } + } + + operator std::string() const + { return std::string(base_type::c_str());} + }; + +#undef PB_DS_BASE_C_DEC + +} // namespace test +} // namespace __gnu_pbds + +#endif diff --git a/libstdc++-v3/testsuite/util/regression/common_type.hpp b/libstdc++-v3/testsuite/util/regression/common_type.hpp new file mode 100644 index 000000000..37705bc2d --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/common_type.hpp @@ -0,0 +1,194 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + + +// 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 common_type.hpp + * Contains types used for regression tests. + */ + +#ifndef PB_DS_RAND_REGRESSION_TEST_COMMON_TYPE_HPP +#define PB_DS_RAND_REGRESSION_TEST_COMMON_TYPE_HPP + +#include <vector> +#include <regression/basic_type.hpp> +#include <common_type/assoc/common_type.hpp> +#include <common_type/priority_queue/common_type.hpp> + +namespace __gnu_pbds +{ +namespace test +{ + typedef __gnu_cxx::throw_allocator_random<basic_type> alloc_type; + + struct hash + { + typedef alloc_type::rebind<basic_type>::other basic_type_rebind; + typedef basic_type_rebind::const_reference const_reference; + typedef basic_type::const_iterator const_iterator; + + size_t + operator()(const_reference r_key) const + { + size_t ret = 0; + for (const_iterator it = r_key.begin(); it != r_key.end(); ++it) + ret = ret * 5 + static_cast<size_t>(*it); + return ret; + } + }; + + typedef __gnu_pbds::string_trie_e_access_traits<basic_type, 'a', 'a' + basic_type::distinct_chars - 1, false, alloc_type> e_access_traits_t; + + template<typename Data_Type> + struct tree_types + { + private: + typedef typename tree_common_types<basic_type, Data_Type, std::less<basic_type>, __gnu_pbds::null_tree_node_update, alloc_type>::regression_tl no_order_statistics_tl_t; + + typedef typename tree_common_types<basic_type, Data_Type, std::less<basic_type>, __gnu_pbds::tree_order_statistics_node_update, alloc_type>::regression_tl order_statistics_tl_t; + + public: + typedef typename __gnu_cxx::typelist::append<no_order_statistics_tl_t, order_statistics_tl_t>::type tl_t; + + typedef no_order_statistics_tl_t min_tl_t; + }; + + template<typename Data_Type> + struct trie_types + { + private: + typedef typename trie_common_types<basic_type, Data_Type, e_access_traits_t, __gnu_pbds::pat_trie_tag, __gnu_pbds::null_trie_node_update, alloc_type>::regression_tl no_updates_tl_t; + + typedef typename trie_common_types<basic_type, Data_Type, e_access_traits_t, __gnu_pbds::pat_trie_tag, __gnu_pbds::trie_order_statistics_node_update, alloc_type>::regression_tl order_statistics_tl_t; + + typedef typename trie_common_types<basic_type, Data_Type, e_access_traits_t, __gnu_pbds::pat_trie_tag, __gnu_pbds::trie_prefix_search_node_update, alloc_type>::regression_tl prefix_search_tl_t; + + public: + typedef typename __gnu_cxx::typelist::append<no_updates_tl_t, typename __gnu_cxx::typelist::append<prefix_search_tl_t, order_statistics_tl_t>::type>::type tl_t; + + typedef no_updates_tl_t min_tl_t; + }; + + template<typename Data_Type> + struct hash_types + { + typedef typename hash_common_types<basic_type, Data_Type, hash, std::equal_to<basic_type>, alloc_type>::regression_tl tl_t; + + typedef tl_t min_tl_t; + }; + + template<typename Data_Type> + struct lu_types + { + typedef typename lu_common_types<basic_type, Data_Type, std::equal_to<basic_type>, alloc_type>::regression_tl tl_t; + + typedef tl_t min_tl_t; + }; + + // Sequence types. + typedef pq_common_types<basic_type, std::less<basic_type>, alloc_type> pq_types; + + typedef pq_types::regression_tl pq_tl_t; + typedef pq_tl_t min_pq_tl_t; + + template<typename _Tp, typename _Alloc> + struct vector_adaptor : public std::vector<_Tp, _Alloc> + { + private: + typedef std::vector<_Tp, _Alloc> base_type; + + public: + typedef typename base_type::value_type value_type; + typedef typename base_type::pointer pointer; + typedef typename base_type::const_pointer const_pointer; + typedef typename base_type::reference reference; + typedef typename base_type::const_reference const_reference; + typedef typename base_type::iterator iterator; + typedef typename base_type::const_iterator const_iterator; + typedef typename base_type::reverse_iterator reverse_iterator; + typedef typename base_type::const_reverse_iterator const_reverse_iterator; + typedef typename base_type::size_type size_type; + typedef typename base_type::difference_type difference_type; + typedef typename base_type::allocator_type allocator_type; + + typedef __gnu_pbds::sequence_tag container_category; + typedef std::less<_Tp> cmp_fn; + + const cmp_fn& + get_cmp_fn() const + { return _M_cmp; } + + vector_adaptor() { } + vector_adaptor(iterator) { } + vector_adaptor(iterator, iterator) { } + vector_adaptor(iterator, iterator, const cmp_fn&) { } + vector_adaptor(const cmp_fn& other) { } + + using base_type::push_back; + using base_type::pop_back; + + // erase_if + + cmp_fn _M_cmp; + + }; + + namespace detail + { + + }; + + typedef vector_adaptor<basic_type, alloc_type> vector_type; + typedef __gnu_cxx::typelist::create1<vector_type>::type vector_tl_t; + + // Associative types. + typedef tree_types<null_mapped_type>::tl_t tree_set_tl_t; + typedef tree_types<null_mapped_type>::min_tl_t min_tree_set_tl_t; + typedef tree_types<basic_type>::tl_t tree_map_tl_t; + typedef tree_types<basic_type>::min_tl_t min_tree_map_tl_t; + + typedef hash_types<null_mapped_type>::tl_t hash_set_tl_t; + typedef hash_types<null_mapped_type>::min_tl_t min_hash_set_tl_t; + typedef hash_types<basic_type>::tl_t hash_map_tl_t; + typedef hash_types<basic_type>::min_tl_t min_hash_map_tl_t; + + typedef lu_types<null_mapped_type>::tl_t lu_set_tl_t; + typedef lu_types<null_mapped_type>::min_tl_t min_lu_set_tl_t; + typedef lu_types<basic_type>::tl_t lu_map_tl_t; + typedef lu_types<basic_type>::min_tl_t min_lu_map_tl_t; + + typedef trie_types<null_mapped_type>::tl_t trie_set_tl_t; + typedef trie_types<null_mapped_type>::min_tl_t min_trie_set_tl_t; + typedef trie_types<basic_type>::tl_t trie_map_tl_t; + typedef trie_types<basic_type>::min_tl_t min_trie_map_tl_t; +} // namespace test +} // namespace __gnu_pbds + +#endif diff --git a/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.h b/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.h new file mode 100644 index 000000000..ca4433212 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.h @@ -0,0 +1,475 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + + +// 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 <algorithm> +#include <string> +#include <sstream> +#include <utility> +#include <ext/pb_ds/assoc_container.hpp> +#include <io/prog_bar.hpp> +#include <testsuite_rng.h> +#include <regression/trait/assoc/trait.hpp> +#include <common_type/assoc/string_form.hpp> +#include <regression/rand/xml_formatter.hpp> + +namespace __gnu_pbds +{ +namespace test +{ +namespace detail +{ + // Rand test specialized for a specific container. + template<typename Cntnr> + class container_rand_regression_test + { + public: + + container_rand_regression_test(unsigned long, size_t, size_t, double, + double, double, double, double, bool); + + virtual + ~container_rand_regression_test(); + + void + operator()(); + + private: + typedef Cntnr cntnr; + typedef typename cntnr::allocator_type allocator_type; + typedef typename cntnr::size_type size_type; + typedef regression_test_traits<Cntnr> test_traits; + typedef typename test_traits::key_type key_type; + typedef typename test_traits::const_key_reference const_key_reference; + typedef typename test_traits::value_type value_type; + typedef typename test_traits::native_type native_type; + typedef twister_rand_gen gen; + typedef __gnu_pbds::container_traits<Cntnr> container_traits; + typedef __gnu_cxx::throw_allocator_random<char> alloc_t; + + enum op + { + insert_op, + erase_op, + clear_op, + other_op + }; + + op + get_next_op(); + + size_t + get_next_sub_op(size_t); + + static void + defs(); + + static void + key_defs(); + + static void + mapped_defs(); + + static void + value_defs(); + + static void + ds_defs(); + + static void + iterator_defs(); + + static void + node_iterator_defs(__gnu_pbds::detail::false_type); + + static void + node_iterator_defs(__gnu_pbds::detail::true_type); + + static void + policy_defs(); + + static void + policy_defs(__gnu_pbds::basic_hash_tag); + + static void + policy_defs(__gnu_pbds::cc_hash_tag); + + static void + policy_defs(__gnu_pbds::gp_hash_tag); + + static void + policy_defs(__gnu_pbds::tree_tag); + + static void + policy_defs(__gnu_pbds::list_update_tag); + + static void + policy_defs(__gnu_pbds::pat_trie_tag); + + void + policy_access(); + + void + policy_access(__gnu_pbds::basic_hash_tag); + + void + policy_access(__gnu_pbds::cc_hash_tag); + + void + policy_access(__gnu_pbds::gp_hash_tag); + + void + policy_access(__gnu_pbds::tree_tag); + + void + policy_access(__gnu_pbds::list_update_tag); + + void + policy_access(__gnu_pbds::pat_trie_tag); + + void + it_copy(); + + void + it_assign(); + + void + rev_it_copy(); + + void + rev_it_assign(); + + void + rev_it_copy_imp(__gnu_pbds::detail::false_type); + + void + rev_it_copy_imp(__gnu_pbds::detail::true_type); + + void + rev_it_assign_imp(__gnu_pbds::detail::false_type); + + void + rev_it_assign_imp(__gnu_pbds::detail::true_type); + + bool + default_constructor(); + + void + swap(); + + bool + copy_constructor(); + + bool + assignment_operator(); + + bool + it_constructor(); + + bool + it_constructor_imp(__gnu_pbds::cc_hash_tag); + + bool + it_constructor_imp(__gnu_pbds::gp_hash_tag); + + bool + it_constructor_imp(__gnu_pbds::tree_tag); + + bool + it_constructor_imp(__gnu_pbds::list_update_tag); + + bool + it_constructor_imp(__gnu_pbds::pat_trie_tag); + + bool + insert(); + + bool + erase(); + + bool + erase_it(); + + bool + erase_it_imp(__gnu_pbds::detail::false_type); + + bool + erase_it_imp(__gnu_pbds::detail::true_type); + + bool + erase_rev_it(); + + bool + erase_rev_it_imp(__gnu_pbds::detail::false_type); + + bool + erase_rev_it_imp(__gnu_pbds::detail::true_type); + + bool + erase_if(); + + bool + clear(); + + bool + resize(); + + bool + resize_imp(__gnu_pbds::detail::true_type); + + bool + resize_imp(__gnu_pbds::detail::false_type); + + bool + get_set_loads(); + + bool + get_set_loads_imp(__gnu_pbds::detail::true_type); + + bool + get_set_loads_imp(__gnu_pbds::detail::false_type); + + void + get_set_load(); + + void + get_set_load_imp(__gnu_pbds::detail::true_type); + + void + get_set_load_imp(__gnu_pbds::detail::false_type); + + bool + subscript(); + + bool + subscript_imp(__gnu_pbds::detail::false_type); + + bool + subscript_imp(__gnu_pbds::detail::true_type); + + bool + split_join(); + + bool + split_join_imp(__gnu_pbds::detail::false_type); + + bool + split_join_imp(__gnu_pbds::detail::true_type); + + void + cmp(const Cntnr&, const native_type&, const std::string&); + + void + basic_cmp_(const Cntnr&, const native_type&); + + void + cmp_(const Cntnr&, const native_type&); + + void + order_preserving_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::false_type); + + void + order_preserving_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::true_type); + + void + back_order_preserving_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::false_type); + + void + back_order_preserving_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::true_type); + + void + reverse_iteration_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::false_type); + + void + reverse_iteration_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::true_type); + + void + order_statistics_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::false_type); + + void + order_statistics_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::true_type); + + void + prefix_search_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::false_type); + + void + prefix_search_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::true_type); + + template<typename Const_It, class Const_Native_It> + void + it_cmp_imp(Const_It, Const_It, Const_Native_It, Const_Native_It); + + template<typename Const_It, class Const_Native_It> + void + back_it_cmp_imp(Const_It, Const_It, Const_Native_It, Const_Native_It); + + void + lower_bound_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::false_type); + + void + lower_bound_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::true_type); + + void + upper_bound_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::false_type); + + void + upper_bound_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::true_type); + + void + print_container(const native_type&, std::ostream& r_os = std::cerr) const; + + void + print_container(const cntnr&, 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_print() + { m_print = false; } + + ~destructor_printer() + { + if (!m_print) + return; + + std::cerr << std::endl << "Uncaught exception: " << std::endl + << m_msg << std::endl; + } + + private: + 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_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; + alloc_t m_alloc; + size_t m_i; + }; + +#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<typename Cntnr> + +#define PB_DS_CLASS_C_DEC \ + container_rand_regression_test<Cntnr> + +#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 PB_DS_THROW_IF_FAILED_(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("fucked!"); \ + } + +#define PB_DS_THROW_IF_FAILED(PRED, MORE, P_C, P_NC) \ + PB_DS_THROW_IF_FAILED_(PRED, MORE, P_C, P_NC, __FILE__, __LINE__) + +#define PB_DS_SET_DESTRUCT_PRINT \ + destructor_printer dest_print___(__FUNCTION__); + +#define PB_DS_CANCEL_DESTRUCT_PRINT \ + dest_print___.cancel_print(); + +#include <regression/rand/assoc/container_rand_regression_test.tcc> + +#undef PB_DS_COND_COMPARE +#undef PB_DS_RUN_MTHD +#undef PB_DS_CLASS_T_DEC +#undef PB_DS_CLASS_C_DEC +#undef PB_DS_THROW_IF_FAILED_ +#undef PB_DS_THROW_IF_FAILED +#undef PB_DS_SET_DESTRUCT_PRINT +#undef PB_DS_CANCEL_DESTRUCT_PRINT +#undef PB_DS_TRACE + +} // namespace detail +} // namespace test +} // namespace __gnu_pbds + +#endif diff --git a/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc b/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc new file mode 100644 index 000000000..0f1586648 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc @@ -0,0 +1,2133 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + + +// 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 + +// Constructors/Destructors. +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 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_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); + typename alloc_t::group_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); + typename alloc_t::group_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() +{ + PB_DS_TRACE("it_constructor"); + return it_constructor_imp(typename Cntnr::container_category()); +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +it_constructor_imp(__gnu_pbds::cc_hash_tag) +{ + bool done = true; + Cntnr* p_c = 0; + m_alloc.set_probability(m_tp); + typename alloc_t::group_adjustor adjust(m_p_c->size()); + + try + { + switch(get_next_sub_op(8)) + { + case 0: + p_c = new Cntnr(m_p_c->get_hash_fn()); + m_native_c.clear(); + break; + case 1: + p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn()); + m_native_c.clear(); + break; + case 2: + p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(), + m_p_c->get_comb_hash_fn()); + m_native_c.clear(); + break; + case 3: + p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(), + m_p_c->get_comb_hash_fn(), + m_p_c->get_resize_policy()); + m_native_c.clear(); + break; + case 4: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end()); + break; + case 5: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn()); + break; + case 6: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(), + m_p_c->get_eq_fn()); + break; + case 7: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(), + m_p_c->get_eq_fn(), m_p_c->get_comb_hash_fn()); + break; + case 8: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(), + m_p_c->get_eq_fn(), m_p_c->get_comb_hash_fn(), + m_p_c->get_resize_policy()); + break; + default: + PB_DS_THROW_IF_FAILED(false, "", 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; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +it_constructor_imp(__gnu_pbds::gp_hash_tag) +{ + bool done = true; + Cntnr* p_c = 0; + m_alloc.set_probability(m_tp); + typename alloc_t::group_adjustor adjust(m_p_c->size()); + + try + { + switch(get_next_sub_op(11)) + { + case 0: + p_c = new Cntnr(m_p_c->get_hash_fn()); + m_native_c.clear(); + break; + case 1: + p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn()); + m_native_c.clear(); + break; + case 2: + p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(), + m_p_c->get_comb_probe_fn()); + m_native_c.clear(); + break; + case 3: + p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(), + m_p_c->get_comb_probe_fn()); + m_native_c.clear(); + break; + case 4: + p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(), + m_p_c->get_comb_probe_fn(), m_p_c->get_probe_fn()); + m_native_c.clear(); + break; + case 5: + p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(), + m_p_c->get_comb_probe_fn(), m_p_c->get_probe_fn(), + m_p_c->get_resize_policy()); + m_native_c.clear(); + break; + case 6: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn()); + break; + case 7: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(), + m_p_c->get_eq_fn()); + break; + case 8: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(), + m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn()); + break; + case 9: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(), + m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn()); + break; + case 10: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(), + m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn(), + m_p_c->get_probe_fn()); + break; + case 11: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(), + m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn(), + m_p_c->get_probe_fn(), m_p_c->get_resize_policy()); + break; + default: + PB_DS_THROW_IF_FAILED(false, "", 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; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +it_constructor_imp(__gnu_pbds::tree_tag) +{ + bool done = true; + Cntnr* p_c = 0; + m_alloc.set_probability(m_tp); + typename alloc_t::group_adjustor adjust(m_p_c->size()); + + try + { + switch(get_next_sub_op(2)) + { + 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(), m_p_c->get_cmp_fn()); + break; + default: + PB_DS_THROW_IF_FAILED(false, "", 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; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +it_constructor_imp(__gnu_pbds::list_update_tag) +{ + bool done = true; + Cntnr* p_c = 0; + m_alloc.set_probability(m_tp); + typename alloc_t::group_adjustor adjust(m_p_c->size()); + + try + { + p_c = new Cntnr(m_p_c->begin(), m_p_c->end()); + 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_imp(__gnu_pbds::pat_trie_tag) +{ + bool done = true; + Cntnr* p_c = 0; + m_alloc.set_probability(m_tp); + typename alloc_t::group_adjustor adjust(m_p_c->size()); + + try + { + switch(get_next_sub_op(2)) + { + case 0: + p_c = new Cntnr(m_p_c->get_e_access_traits()); + m_native_c.clear(); + break; + case 1: + p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), + m_p_c->get_e_access_traits()); + break; + default: + PB_DS_THROW_IF_FAILED(false, "", 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; +} + +// Cmp. +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +cmp(const Cntnr& r_c, const native_type& r_native_c, + const std::string& r_call_fn) +{ + m_alloc.set_probability(1); + const size_t size = r_c.size(); + const size_t native_size = r_native_c.size(); + PB_DS_THROW_IF_FAILED(size == native_size, + size << " " << native_size, &r_c, &r_native_c); + + const bool empty = r_c.empty(); + const bool native_empty = r_native_c.empty(); + PB_DS_THROW_IF_FAILED(empty == native_empty, + empty << " " << native_empty, &r_c, &r_native_c); + + try + { + basic_cmp_(r_c, r_native_c); + cmp_(r_c, r_native_c); + } + catch(...) + { + PB_DS_THROW_IF_FAILED(false, "call-fn: " + r_call_fn, &r_c, &r_native_c); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +basic_cmp_(const Cntnr& r_c, const native_type& r_native_c) +{ + PB_DS_SET_DESTRUCT_PRINT + + if (static_cast<size_t>(std::distance(r_c.begin(), r_c.end())) != r_c.size()) + PB_DS_THROW_IF_FAILED(false, + static_cast<unsigned long>(std::distance(r_c.begin(), r_c.end())) << " " << static_cast<unsigned long>(r_c.size()), &r_c, &r_native_c); + + typename native_type::const_iterator it = r_native_c.begin(); + while (it != r_native_c.end()) + { + typename native_type::key_type native_key = test_traits::extract_native_key(*it); + + m_alloc.set_probability(0); + const key_type k = native_key; + m_alloc.set_probability(1); + typename cntnr::const_point_iterator found_it = r_c.find(k); + PB_DS_THROW_IF_FAILED(found_it != r_c.end(), + test_traits::native_val_to_string(*it), + &r_c, &r_native_c); + + if (!test_traits::cmp(*found_it, * it)) + PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c); + + ++it; + } + PB_DS_CANCEL_DESTRUCT_PRINT +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +cmp_(const Cntnr& r_c, const native_type& r_native_c) +{ + enum + { + order_preserving = container_traits::order_preserving, + back_order_preserving = container_traits::order_preserving + && + !__gnu_pbds::detail::is_same< + typename std::iterator_traits< + typename cntnr::const_iterator>::iterator_category, + std::forward_iterator_tag>::value, + reverse_iteration = container_traits::reverse_iteration, + order_statistics = test_traits::order_statistics, + prefix_search = test_traits::prefix_search, + has_mapped = !__gnu_pbds::detail::is_same< + typename Cntnr::mapped_type, + __gnu_pbds::null_mapped_type>::value + }; + + order_preserving_cmp_imp(r_c, r_native_c, + __gnu_pbds::detail::integral_constant<int,order_preserving>()); + + back_order_preserving_cmp_imp(r_c, r_native_c, + __gnu_pbds::detail::integral_constant<int,back_order_preserving>()); + + order_statistics_cmp_imp(r_c, r_native_c, + __gnu_pbds::detail::integral_constant<int,order_statistics>()); + + prefix_search_cmp_imp(r_c, r_native_c, + __gnu_pbds::detail::integral_constant<int,prefix_search>()); + + reverse_iteration_cmp_imp(r_c, r_native_c, + __gnu_pbds::detail::integral_constant<int,reverse_iteration>()); + + lower_bound_cmp_imp(r_c, r_native_c, + __gnu_pbds::detail::integral_constant<int,order_preserving>()); + + upper_bound_cmp_imp(r_c, r_native_c, + __gnu_pbds::detail::integral_constant<int,order_preserving>()); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +order_preserving_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +order_preserving_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type) +{ + PB_DS_SET_DESTRUCT_PRINT + + typename cntnr::const_iterator b = r_c.begin(); + typename cntnr::const_iterator e = r_c.end(); + + typename native_type::const_iterator native_b = r_native_c.begin(); + typename native_type::const_iterator native_e = r_native_c.end(); + + try + { + it_cmp_imp(b, e, native_b, native_e); + } + catch(...) + { + PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c) + } + + try + { + back_it_cmp_imp(b, e, native_b, native_e); + } + catch(...) + { + PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c) + } + + PB_DS_CANCEL_DESTRUCT_PRINT +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +back_order_preserving_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::false_type) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +back_order_preserving_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, + __gnu_pbds::detail::true_type) +{ + PB_DS_SET_DESTRUCT_PRINT + typename cntnr::const_iterator b = r_c.begin(); + typename cntnr::const_iterator e = r_c.end(); + typename native_type::const_iterator native_b = r_native_c.begin(); + typename native_type::const_iterator native_e = r_native_c.end(); + it_cmp_imp(b, e, native_b, native_e); + PB_DS_CANCEL_DESTRUCT_PRINT +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +reverse_iteration_cmp_imp(const Cntnr&, const native_type&, + __gnu_pbds::detail::false_type) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +reverse_iteration_cmp_imp(const Cntnr& r_c, const native_type&r_native_c, __gnu_pbds::detail::true_type) +{ + PB_DS_SET_DESTRUCT_PRINT + + typename cntnr::const_reverse_iterator b = r_c.rbegin(); + typename cntnr::const_reverse_iterator e = r_c.rend(); + + typename native_type::const_reverse_iterator native_b = r_native_c.rbegin(); + typename native_type::const_reverse_iterator native_e = r_native_c.rend(); + + try + { + it_cmp_imp(b, e, native_b, native_e); + } + catch(...) + { + PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c) + } + + try + { + back_it_cmp_imp(b, e, native_b, native_e); + } + catch(...) + { + PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c) + } + + PB_DS_CANCEL_DESTRUCT_PRINT +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +order_statistics_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +order_statistics_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type) +{ + { + m_alloc.set_probability(0); + const key_type k = test_traits::generate_key(m_g, m_m); + m_alloc.set_probability(1); + const size_type order = r_c.order_of_key(k); + const size_type native_order = std::distance(r_native_c.begin(), + r_native_c.lower_bound(test_traits::native_key(k))); + + PB_DS_THROW_IF_FAILED(order == native_order, + test_traits::key_to_string(k) << " " << + static_cast<unsigned long>(order) << " " << + static_cast<unsigned long>(native_order), + &r_c, + &r_native_c); + } + + const size_type rand_ord = + static_cast<size_t>(m_g.get_unsigned_long(0, + 2 * static_cast<unsigned long>(m_m))); + + typename cntnr::const_iterator it = r_c.find_by_order(rand_ord); + typename native_type::const_iterator native_it = r_native_c.begin(); + std::advance(native_it, std::min(rand_ord, r_native_c.size())); + if (it == r_c.end()&& native_it != r_native_c.end()) + PB_DS_THROW_IF_FAILED(false, + static_cast<unsigned long>(rand_ord), + m_p_c, + &m_native_c); + + if (it != r_c.end()&& native_it == r_native_c.end()) + PB_DS_THROW_IF_FAILED(false, + static_cast<unsigned long>(rand_ord), + m_p_c, + &m_native_c); + + if (it != r_c.end()&& native_it != r_native_c.end()) + PB_DS_THROW_IF_FAILED(test_traits::cmp(*it, * native_it), + static_cast<unsigned long>(rand_ord), + m_p_c, + &m_native_c); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +prefix_search_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +prefix_search_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type) +{ + PB_DS_SET_DESTRUCT_PRINT + m_alloc.set_probability(0); + const key_type k = test_traits::generate_key(m_g, m_m); + m_alloc.set_probability(1); + try + { + typedef + std::pair<typename Cntnr::const_iterator, typename Cntnr::const_iterator> + pref_ret_t; + + const pref_ret_t pref_ret = r_c.prefix_range(k); + + typename native_type::const_iterator native_start_it = r_native_c.begin(); + + while (native_start_it != r_native_c.end() && + !test_traits::prefix_match(k, + test_traits::extract_native_key(*native_start_it))) + ++native_start_it; + + typename native_type::const_iterator native_end_it = + native_start_it; + + do + { + if (native_end_it != r_native_c.end()) + ++native_end_it; + } + while (native_end_it != r_native_c.end() && + test_traits::prefix_match(k, + test_traits::extract_native_key(*native_end_it))); + + it_cmp_imp(pref_ret.first, pref_ret.second, native_start_it, native_end_it); + } + catch(...) + { + PB_DS_THROW_IF_FAILED(false, "prefix key " << k, &r_c, &r_native_c); + } + + PB_DS_CANCEL_DESTRUCT_PRINT +} + +PB_DS_CLASS_T_DEC +template<typename Const_It, class Const_Native_It> +void +PB_DS_CLASS_C_DEC:: +it_cmp_imp(Const_It b, Const_It e, Const_Native_It native_b, + Const_Native_It native_e) +{ + PB_DS_SET_DESTRUCT_PRINT + + if (std::distance(b, e) != std::distance(native_b, native_e)) + { + const size_t dist = std::distance(b, e); + const size_t native_dist = std::distance(native_b, native_e); + PB_DS_THROW_IF_FAILED(false, + static_cast<unsigned long>(dist) << " " + << static_cast<unsigned long>(native_dist), + m_p_c, &m_native_c); + } + + while (b != e) + { + PB_DS_THROW_IF_FAILED(native_b != native_e, "", m_p_c, &m_native_c); + + if (!test_traits::cmp(*b, * native_b)) + PB_DS_THROW_IF_FAILED(false, + test_traits::val_to_string(*b) << " " << + test_traits::val_to_string(*native_b), + m_p_c, &m_native_c); + + ++b; + ++native_b; + } + + PB_DS_THROW_IF_FAILED(native_b == native_e, "", m_p_c, &m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT +} + +PB_DS_CLASS_T_DEC +template<typename Const_It, class Const_Native_It> +void +PB_DS_CLASS_C_DEC:: +back_it_cmp_imp(Const_It b, Const_It e, Const_Native_It native_b, + Const_Native_It native_e) +{ + PB_DS_SET_DESTRUCT_PRINT + while (b != e) + { + PB_DS_THROW_IF_FAILED(native_b != native_e, + test_traits::val_to_string(*native_e), + m_p_c, &m_native_c); + + --e; + --native_e; + + PB_DS_THROW_IF_FAILED(test_traits::cmp(*e, * native_e), + test_traits::val_to_string(*e) << + test_traits::val_to_string(*native_e), + m_p_c, &m_native_c); + } + + PB_DS_THROW_IF_FAILED(native_b == native_e, + test_traits::val_to_string(*native_e), + m_p_c, &m_native_c); + + PB_DS_CANCEL_DESTRUCT_PRINT +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +lower_bound_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +lower_bound_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type) +{ + PB_DS_SET_DESTRUCT_PRINT + m_alloc.set_probability(0); + const key_type k = test_traits::generate_key(m_g, m_m); + m_alloc.set_probability(1); + typename cntnr::const_iterator it = r_c.lower_bound(k); + typename native_type::key_type native_k = test_traits::native_key(k); + typename native_type::const_iterator native_it = r_native_c.lower_bound(native_k); + + if (it != r_c.end() && native_it == r_native_c.end()) + PB_DS_THROW_IF_FAILED("", + "it: " + test_traits::val_to_string(*it) + "\n\n", + &r_c, &r_native_c); + + if (it == r_c.end() && native_it != r_native_c.end()) + PB_DS_THROW_IF_FAILED("", + "native_it: " + test_traits::val_to_string(*native_it) + "\n\n", + &r_c, &r_native_c); + + if (it != r_c.end() && !test_traits::cmp(*it, * native_it)) + PB_DS_THROW_IF_FAILED(false, + "key: " + test_traits::key_to_string(k) + "\n\n" + + "it: " + test_traits::val_to_string(*it) + "\n\n" + + "native_it: " + test_traits::val_to_string(*native_it) + "\n\n", + &r_c, &r_native_c); + + PB_DS_CANCEL_DESTRUCT_PRINT +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +upper_bound_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +upper_bound_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type) +{ + PB_DS_SET_DESTRUCT_PRINT + m_alloc.set_probability(0); + const key_type k = test_traits::generate_key(m_g, m_m); + m_alloc.set_probability(1); + typename cntnr::const_iterator it = r_c.upper_bound(k); + typename native_type::key_type native_k = test_traits::native_key(k); + typename native_type::const_iterator native_it = r_native_c.upper_bound(native_k); + + if (it == r_c.end() && native_it != r_native_c.end()) + PB_DS_THROW_IF_FAILED(false, + "key: " + test_traits::key_to_string(k) + "\n\n" + + "native_it: " + test_traits::val_to_string(*native_it) + "\n\n", + &r_c, &r_native_c); + + if (it != r_c.end() && native_it == r_native_c.end()) + PB_DS_THROW_IF_FAILED(false, + "key: " + test_traits::key_to_string(k) + "\n\n" + + "it: " + test_traits::val_to_string(*it) + "\n\n", + &r_c, &r_native_c); + + if (it != r_c.end() && !test_traits::cmp(*it, * native_it)) + PB_DS_THROW_IF_FAILED(false, + "key: " + test_traits::key_to_string(k) + "\n\n" + + "it: " + test_traits::val_to_string(*it) + "\n\n" + + "native_it: " + test_traits::val_to_string(*native_it) + "\n\n", + &r_c, &r_native_c); + + PB_DS_CANCEL_DESTRUCT_PRINT +} + +// 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<Cntnr>::name(), + string_form<Cntnr>::desc()); + + m_g.init(m_seed); + + // Track allocation from this point only. + const size_t memory_label = 775; + m_alloc.seed(m_seed); + m_alloc.set_label(memory_label); + + prog_bar pb(m_n, std::cout, m_disp); + m_i = 0; + + try + { + for (m_i = 0; m_i < m_n; ++m_i) + { + PB_DS_TRACE("Op #" << static_cast<unsigned long>(m_i)); + allocator_type::set_label(m_i); + switch (m_i) + { + case 0: + PB_DS_RUN_MTHD(default_constructor); + break; + case 1: + defs(); + break; + case 2: + policy_access(); + break; + case 3: + it_copy(); + break; + case 4: + it_assign(); + break; + case 5: + rev_it_copy(); + break; + case 6: + rev_it_assign(); + break; + default: + switch(get_next_op()) + { + case insert_op: + switch(get_next_sub_op(2)) + { + case 0: + PB_DS_RUN_MTHD(insert) + break; + case 1: + PB_DS_RUN_MTHD(subscript) + break; + default: + PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c); + } + break; + case erase_op: + switch(get_next_sub_op(4)) + { + case 0: + PB_DS_RUN_MTHD(erase) + break; + case 1: + PB_DS_RUN_MTHD(erase_if) + break; + case 2: + PB_DS_RUN_MTHD(erase_it) + break; + case 3: + PB_DS_RUN_MTHD(erase_rev_it) + break; + default: + PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c); + } + break; + case clear_op: + PB_DS_RUN_MTHD(clear) + break; + case other_op: + switch(get_next_sub_op(8)) + { + 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; + case 5: + resize(); + break; + case 6: + get_set_load(); + break; + case 7: + get_set_loads(); + break; + default: + PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c); + } + break; + default: + PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c); + }; + } + + pb.inc(); + } + } + catch (...) + { + std::cerr << "Failed at index " << static_cast<unsigned long>(m_i) + << std::endl; + delete m_p_c; + throw; + } + + // Clean up, then check for allocation by special label, set above. + delete m_p_c; + + try + { m_alloc.check_allocated(memory_label); } + catch (...) + { + std::cerr << "detected leaks!" << std::endl; + std::cerr << m_alloc << std::endl; + PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c); + } + + // 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_ep) + return erase_op; + + if (prob < m_ip + m_ep + m_cp) + return clear_op; + + PB_DS_THROW_IF_FAILED(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<double>(max); + size_t i = 0; + while (true) + if (p <= (i + 1) * delta) + { + PB_DS_THROW_IF_FAILED(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:: +insert() +{ + PB_DS_TRACE("insert"); + bool done = true; + PB_DS_SET_DESTRUCT_PRINT + try + { + m_alloc.set_probability(0); + value_type v = test_traits::generate_value(m_g, m_m); + m_alloc.set_probability(m_tp); + const_key_reference r_k = test_traits::extract_key(v); + typename cntnr::const_point_iterator found_it = m_p_c->find(r_k); + const bool existed = (found_it != m_p_c->end()); + const std::pair<typename cntnr::point_iterator, bool> ins_ret = m_p_c->insert(v); + + if (ins_ret.second) + { + PB_DS_THROW_IF_FAILED(!existed, "", m_p_c, &m_native_c); + } + else + { + PB_DS_THROW_IF_FAILED(existed, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(found_it == ins_ret.first, "", m_p_c, &m_native_c); + } + m_native_c.insert(test_traits::native_value(v)); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + } + catch(__gnu_pbds::insert_error&) + { + PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT + return done; +} + +// Subscript. +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +subscript() +{ + PB_DS_TRACE("subscript"); + + enum + { + no_data = __gnu_pbds::detail::is_same< + typename Cntnr::const_key_reference, + typename Cntnr::const_reference>::value + }; + + return (subscript_imp(__gnu_pbds::detail::integral_constant<int,no_data>())); +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +subscript_imp(__gnu_pbds::detail::false_type) +{ + bool done = true; + PB_DS_SET_DESTRUCT_PRINT + + try + { + m_alloc.set_probability(0); + value_type v = test_traits::generate_value(m_g, m_m); + + m_alloc.set_probability(m_tp); + (*m_p_c)[v.first] = v.second; + + m_native_c[test_traits::native_value(v).first] = + test_traits::native_value(v).second; + } + catch(__gnu_cxx::forced_error&) + { + done = false; + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT + return done; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +subscript_imp(__gnu_pbds::detail::true_type) +{ + bool done = true; + PB_DS_SET_DESTRUCT_PRINT + try + { + m_alloc.set_probability(0); + value_type v = test_traits::generate_value(m_g, m_m); + m_alloc.set_probability(m_tp); + (*m_p_c)[v] = __gnu_pbds::null_mapped_type(); + m_native_c.insert(test_traits::native_value(v)); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT + return done; +} + +// Clear. +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +clear() +{ + m_p_c->clear(); + m_native_c.clear(); + return true; +} + + +// Erase. +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +erase() +{ + PB_DS_TRACE("erase"); + bool done = true; + PB_DS_SET_DESTRUCT_PRINT + m_alloc.set_probability(0); + const key_type k = test_traits::generate_key(m_g, m_m); + m_alloc.set_probability(m_tp); + + try + { + const bool cntnd = m_p_c->find(k) != m_p_c->end(); + PB_DS_THROW_IF_FAILED(cntnd ==(m_native_c.find(test_traits::native_key(k)) != m_native_c.end()), test_traits::key_to_string(k), m_p_c, &m_native_c); + + const bool ersd = m_p_c->erase(k); + const bool native_ersd = m_native_c.erase(test_traits::native_key(k)) != 0; + + PB_DS_THROW_IF_FAILED(ersd == native_ersd, ersd << " " << native_ersd, + m_p_c, &m_native_c); + + PB_DS_THROW_IF_FAILED(m_p_c->find(k) == m_p_c->end(), "", + m_p_c, &m_native_c); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + + PB_DS_THROW_IF_FAILED( container_traits::erase_can_throw, container_traits::erase_can_throw, m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT + return done; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +erase_if() +{ + PB_DS_TRACE("erase_if"); + bool done = true; + PB_DS_SET_DESTRUCT_PRINT + + try + { + typedef + typename std::iterator_traits<typename cntnr::iterator>::reference + it_const_reference; + + typedef + typename test_traits::template erase_if_fn<value_type> + erase_if_fn_t; + + m_alloc.set_probability(m_tp); + + const size_t ersd = m_p_c->erase_if(erase_if_fn_t()); + const size_t native_ersd = test_traits::erase_if(m_native_c); + PB_DS_THROW_IF_FAILED(ersd == native_ersd, + ersd << " " << native_ersd, m_p_c, &m_native_c); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw, + container_traits::erase_can_throw, + m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT + return done; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +erase_it() +{ + enum + { + erase_iterators = container_traits::order_preserving + }; + + return (erase_it_imp(__gnu_pbds::detail::integral_constant<int,erase_iterators>())); +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +erase_it_imp(__gnu_pbds::detail::false_type) +{ + return true; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +erase_it_imp(__gnu_pbds::detail::true_type) +{ + PB_DS_TRACE("erase_it"); + bool done = true; + PB_DS_SET_DESTRUCT_PRINT + + try + { + m_alloc.set_probability(0); + const key_type k = test_traits::generate_key(m_g, m_m); + m_alloc.set_probability(m_tp); + + typename cntnr::iterator found_it = m_p_c->find(k); + + typename native_type::iterator native_it = m_native_c.find(test_traits::native_key(k)); + + const bool found = found_it != m_p_c->end(); + const bool native_found = native_it != m_native_c.end(); + + PB_DS_THROW_IF_FAILED( + found == native_found, + found << " " << native_found, + m_p_c, + &m_native_c); + + typename cntnr::const_iterator next_it = found_it; + if (next_it != m_p_c->end()) + ++next_it; + + typename cntnr::iterator next_ers_it = m_p_c->erase(found_it); + + if (native_it != m_native_c.end()) + m_native_c.erase(native_it); + + bool range_guarantee = __gnu_pbds::detail::is_same< + typename container_traits::invalidation_guarantee, + __gnu_pbds::range_invalidation_guarantee>::value ; + + if (range_guarantee) + PB_DS_THROW_IF_FAILED(next_ers_it == next_it, "", m_p_c, &m_native_c); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw, container_traits::erase_can_throw, m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT + return done; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +erase_rev_it() +{ + enum + { + erase_iterators = container_traits::order_preserving + && container_traits::reverse_iteration + }; + + return (erase_rev_it_imp(__gnu_pbds::detail::integral_constant<int,erase_iterators>())); +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +erase_rev_it_imp(__gnu_pbds::detail::false_type) +{ + return true; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +erase_rev_it_imp(__gnu_pbds::detail::true_type) +{ + PB_DS_TRACE("erase_rev_it"); + bool done = true; + PB_DS_SET_DESTRUCT_PRINT + + try + { + m_alloc.set_probability(0); + const key_type k = test_traits::generate_key(m_g, m_m); + m_alloc.set_probability(m_tp); + + typename cntnr::iterator found_it = m_p_c->find(k); + typename native_type::iterator native_it = m_native_c.find(test_traits::native_key(k)); + + typename cntnr::const_reverse_iterator next_it = found_it; + if (next_it != m_p_c->end()) + ++next_it; + + typename cntnr::reverse_iterator next_ers_it = + m_p_c->erase((typename cntnr::reverse_iterator)found_it); + + PB_DS_THROW_IF_FAILED(next_ers_it == next_it, "", m_p_c, &m_native_c); + + if (native_it != m_native_c.end()) + m_native_c.erase(native_it); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw, + container_traits::erase_can_throw, + m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT + 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; + + key_defs(); + mapped_defs(); + value_defs(); + iterator_defs(); + node_iterator_defs(__gnu_pbds::detail::integral_constant<int, + container_traits::order_preserving>()); + policy_defs(); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +key_defs() +{ + typedef typename Cntnr::key_type test_key_type; + typedef typename Cntnr::key_reference test_key_reference; + typedef typename Cntnr::const_key_reference test_const_key_reference; + typedef typename Cntnr::key_pointer test_key_pointer; + typedef typename Cntnr::const_key_pointer test_const_key_pointer; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +mapped_defs() +{ + typedef typename Cntnr::mapped_type test_mapped_type; + typedef typename Cntnr::mapped_reference test_mapped_reference; + typedef typename Cntnr::const_mapped_reference test_const_mapped_reference; + typedef typename Cntnr::mapped_pointer test_mapped_pointer; + typedef typename Cntnr::const_mapped_pointer test_const_mapped_pointer; +} + +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 __gnu_pbds::container_traits< Cntnr> test_container_traits; + + typedef typename test_container_traits::container_category test_container_category; + + typedef + typename test_container_traits::invalidation_guarantee + test_invalidation_guarantee; + + enum + { + test_order_preserving = test_container_traits::order_preserving + }; + + enum + { + test_erase_can_throw = test_container_traits::erase_can_throw + }; +} + +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:: +node_iterator_defs(__gnu_pbds::detail::false_type) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +node_iterator_defs(__gnu_pbds::detail::true_type) +{ + typedef typename Cntnr::node_iterator test_node_iterator; + typedef typename Cntnr::const_node_iterator test_const_node_iterator; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_defs() +{ + typedef typename Cntnr::allocator_type test_allocator; + policy_defs(typename Cntnr::container_category()); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_defs(__gnu_pbds::basic_hash_tag) +{ + typedef typename Cntnr::hash_fn test_hash_fn; + typedef typename Cntnr::eq_fn test_eq_fn; + typedef typename Cntnr::resize_policy test_resize_policy; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_defs(__gnu_pbds::cc_hash_tag) +{ + policy_defs(__gnu_pbds::basic_hash_tag()); + typedef typename Cntnr::comb_hash_fn test_comb_hash_fn; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_defs(__gnu_pbds::gp_hash_tag) +{ + policy_defs(__gnu_pbds::basic_hash_tag()); + typedef typename Cntnr::comb_probe_fn test_comb_probe_fn; + typedef typename Cntnr::probe_fn test_probe_fn; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_defs(__gnu_pbds::tree_tag) +{ + typedef typename Cntnr::cmp_fn test_cmp_fn; + typedef typename Cntnr::node_update test_node_update; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_defs(__gnu_pbds::list_update_tag) +{ + typedef typename Cntnr::eq_fn test_eq_fn; + typedef typename Cntnr::update_policy test_update_policy; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_defs(__gnu_pbds::pat_trie_tag) +{ + typedef typename Cntnr::e_access_traits e_access_traits; +} + + +// Policy Access. +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_access() +{ + policy_access(typename Cntnr::container_category()); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_access(__gnu_pbds::basic_hash_tag) +{ + { + typename Cntnr::hash_fn& r_t = m_p_c->get_hash_fn(); + assert(&r_t); + } + { + const typename Cntnr::hash_fn& r_t =((const Cntnr& )*m_p_c).get_hash_fn(); + assert(&r_t); + } + + { + typename Cntnr::eq_fn& r_t = m_p_c->get_eq_fn(); + assert(&r_t); + } + { + const typename Cntnr::eq_fn& r_t =((const Cntnr& )*m_p_c).get_eq_fn(); + assert(&r_t); + } + + { + typename Cntnr::resize_policy& r_t = m_p_c->get_resize_policy(); + assert(&r_t); + } + { + const typename Cntnr::resize_policy& r_t =((const Cntnr& )*m_p_c).get_resize_policy(); + + assert(&r_t); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_access(__gnu_pbds::cc_hash_tag) +{ + policy_access(__gnu_pbds::basic_hash_tag()); + + { + typename Cntnr::comb_hash_fn& r_t = m_p_c->get_comb_hash_fn(); + assert(&r_t); + } + { + const typename Cntnr::comb_hash_fn& r_t =((const Cntnr& )*m_p_c).get_comb_hash_fn(); + + assert(&r_t); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_access(__gnu_pbds::gp_hash_tag) +{ + policy_access(__gnu_pbds::basic_hash_tag()); + + { + typename Cntnr::comb_probe_fn& r_t = m_p_c->get_comb_probe_fn(); + assert(&r_t); + } + { + const typename Cntnr::comb_probe_fn& r_t =((const Cntnr& )*m_p_c).get_comb_probe_fn(); + + assert(&r_t); + } + + { + typename Cntnr::probe_fn& r_t = m_p_c->get_probe_fn(); + assert(&r_t); + } + { + const typename Cntnr::probe_fn& r_t =((const Cntnr& )*m_p_c).get_probe_fn(); + assert(&r_t); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_access(__gnu_pbds::tree_tag) +{ + { + 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); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_access(__gnu_pbds::list_update_tag) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +policy_access(__gnu_pbds::pat_trie_tag) +{ + typename Cntnr::e_access_traits& r_t = m_p_c->get_e_access_traits(); + assert(&r_t); +} + + +// Split/Join. +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +split_join() +{ + enum + { + split_join = container_traits::order_preserving + }; + + return (split_join_imp(__gnu_pbds::detail::integral_constant<int,split_join>())); +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +split_join_imp(__gnu_pbds::detail::false_type) +{ + return true; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +split_join_imp(__gnu_pbds::detail::true_type) +{ + PB_DS_TRACE("split_join"); + bool done = true; + PB_DS_SET_DESTRUCT_PRINT + + try + { + m_alloc.set_probability(0); + Cntnr lhs(*m_p_c); + Cntnr rhs; + native_type native_lhs(m_native_c); + native_type native_rhs; + const key_type k = test_traits::generate_key(m_g, m_m); + + m_alloc.set_probability(m_tp); + lhs.split(k, rhs); + + typename native_type::const_iterator it = + native_lhs.upper_bound(test_traits::native_key(k)); + + while (!native_lhs.empty()&& it != native_lhs.end()) + { + native_rhs.insert(*it); + typename native_type::const_iterator next_it = it; + ++next_it; + native_lhs.erase(test_traits::extract_native_key(*it)); + it = next_it; + } + + 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); + PB_DS_THROW_IF_FAILED(rhs.size() == 0, rhs.size(), m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(rhs.empty(), rhs.size(), m_p_c, &m_native_c); + m_p_c->swap(lhs); + } + catch(__gnu_cxx::forced_error&) + { + done = false; + PB_DS_THROW_IF_FAILED(container_traits::split_join_can_throw, + container_traits::split_join_can_throw, + m_p_c, &m_native_c); + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT + return done; +} + +// Iterator conversions. +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +it_copy() +{ + { + typename cntnr::iterator it = m_p_c->end(); + typename cntnr::const_iterator const_it(it); + PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c); + + typename cntnr::const_point_iterator const_find_it(it); + PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c); + + typename cntnr::point_iterator find_it(it); + PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(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_it); + PB_DS_THROW_IF_FAILED(const_find_it == const_it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(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(find_it); + PB_DS_THROW_IF_FAILED(find_it == const_find_it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(find_it != const_find_it), "", m_p_c, &m_native_c); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +it_assign() +{ + { + typename cntnr::iterator it = m_p_c->end(); + typename cntnr::const_iterator const_it; + const_it = it; + PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c); + + typename cntnr::const_point_iterator const_find_it; + const_find_it = it; + PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c); + + typename cntnr::point_iterator find_it; + find_it = it; + PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(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; + PB_DS_THROW_IF_FAILED(const_find_it == const_it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(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; + PB_DS_THROW_IF_FAILED(find_it == const_find_it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(find_it != const_find_it), "", m_p_c, &m_native_c); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rev_it_copy() +{ + enum + { + reverse_iteration = container_traits::reverse_iteration + }; + + rev_it_copy_imp(__gnu_pbds::detail::integral_constant<int,reverse_iteration>()); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rev_it_assign() +{ + enum + { + reverse_iteration = container_traits::reverse_iteration + }; + + rev_it_assign_imp(__gnu_pbds::detail::integral_constant<int,reverse_iteration>()); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rev_it_copy_imp(__gnu_pbds::detail::false_type) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rev_it_copy_imp(__gnu_pbds::detail::true_type) +{ + { + typename cntnr::iterator it = m_p_c->end(); + typename cntnr::const_reverse_iterator const_it(it); + PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c); + + typename cntnr::const_point_iterator const_find_it(it); + PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c); + + typename cntnr::point_iterator find_it(it); + PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rev_it_assign_imp(__gnu_pbds::detail::false_type) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rev_it_assign_imp(__gnu_pbds::detail::true_type) +{ + { + typename cntnr::iterator it = m_p_c->end(); + typename cntnr::const_reverse_iterator const_it; + const_it = it; + PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c); + + typename cntnr::const_point_iterator const_find_it; + const_find_it = it; + PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c); + + typename cntnr::point_iterator find_it; + find_it = it; + PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c); + PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c); + } +} + +// Resize. +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +resize() +{ + typedef __gnu_pbds::detail::integral_constant<int, test_traits::resize> resize_ind; + + return resize_imp(resize_ind()); +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +resize_imp(__gnu_pbds::detail::false_type) +{ + return true; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +resize_imp(__gnu_pbds::detail::true_type) +{ + PB_DS_TRACE("resize"); + bool done = true; + PB_DS_SET_DESTRUCT_PRINT + const size_t old_size = m_p_c->get_actual_size(); + + try + { + enum + { + min_new_size = 200, + max_new_size = 2000 + }; + + m_alloc.set_probability(m_tp); + typename alloc_t::group_adjustor adjust(m_p_c->size()); + const size_t new_size = m_g.get_unsigned_long(min_new_size, max_new_size); + m_p_c->resize(new_size); + const size_t actual_new_size = m_p_c->get_actual_size(); + PB_DS_THROW_IF_FAILED(actual_new_size >= new_size, + actual_new_size << " " << new_size, + m_p_c, &m_native_c); + } + catch(...) + { + PB_DS_THROW_IF_FAILED(m_p_c->get_actual_size() == old_size, + m_p_c->get_actual_size() << " " << old_size, + m_p_c, &m_native_c); + + done = false; + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT + return done; +} + + +// Get/Set load. +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +get_set_load() +{ + typedef + __gnu_pbds::detail::integral_constant<int, test_traits::get_set_load> + get_set_load_ind; + + get_set_load_imp(get_set_load_ind()); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +get_set_load_imp(__gnu_pbds::detail::false_type) +{ } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +get_set_load_imp(__gnu_pbds::detail::true_type) +{ + PB_DS_TRACE("get_set_load"); + PB_DS_SET_DESTRUCT_PRINT + m_p_c->get_load(); + m_alloc.set_probability(1); + typename alloc_t::group_adjustor adjust(m_p_c->size()); + const float min_load = static_cast<float>(0.05); + const float max_load = static_cast<float>(0.9); + + const float new_load = static_cast<float>(m_g.get_prob() * (max_load - min_load) + min_load); + + m_p_c->set_load(new_load); + PB_DS_THROW_IF_FAILED(m_p_c->get_load() == new_load, "", m_p_c, &m_native_c); + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT +} + + +// Get/Set loads. +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +get_set_loads() +{ + typedef + __gnu_pbds::detail::integral_constant<int, test_traits::get_set_loads> + get_set_loads_ind; + + return get_set_loads_imp(get_set_loads_ind()); +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +get_set_loads_imp(__gnu_pbds::detail::false_type) +{ + return true; +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +get_set_loads_imp(__gnu_pbds::detail::true_type) +{ + PB_DS_TRACE("get_set_loads"); + bool done = true; + PB_DS_SET_DESTRUCT_PRINT + const std::pair<float, float> old_loads = m_p_c->get_loads(); + + try + { + m_alloc.set_probability(m_tp); + + typename alloc_t::group_adjustor adjust(m_p_c->size()); + + const float min_min_load = static_cast<float>(0.05); + const float max_min_load = static_cast<float>(0.2); + + const float new_min_load = + static_cast<float>(m_g.get_prob()* (max_min_load - min_min_load) + + min_min_load); + + const float new_max_load = static_cast<float>(new_min_load* 2.5); + PB_DS_THROW_IF_FAILED(new_max_load < 1, new_max_load, m_p_c, &m_native_c); + m_p_c->set_loads(std::make_pair(new_min_load, new_max_load)); + } + catch(...) + { + PB_DS_THROW_IF_FAILED(old_loads == m_p_c->get_loads(), + old_loads.first << " " << old_loads.second << " " << + m_p_c->get_loads().first << " " << + m_p_c->get_loads().second, + m_p_c, &m_native_c); + + done = false; + } + + PB_DS_COND_COMPARE(*m_p_c, m_native_c); + PB_DS_CANCEL_DESTRUCT_PRINT + return done; +} + +// Diagnostics. +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +print_container(const native_type& r_cnt, std::ostream& r_os) const +{ + m_alloc.set_probability(0); + typename native_type::const_iterator it = r_cnt.begin(); + while (it != r_cnt.end()) + { + r_os << test_traits::val_to_string(*it) + "\n"; + ++it; + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +print_container(const cntnr& r_cnt, std::ostream& r_os) const +{ + m_alloc.set_probability(0); + typename cntnr::const_iterator it = r_cnt.begin(); + while (it != r_cnt.end()) + { + r_os << test_traits::val_to_string(*it) + "\n"; + ++it; + } +} + +#endif diff --git a/libstdc++-v3/testsuite/util/regression/rand/assoc/rand_regression_test.hpp b/libstdc++-v3/testsuite/util/regression/rand/assoc/rand_regression_test.hpp new file mode 100644 index 000000000..5f2304952 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/rand/assoc/rand_regression_test.hpp @@ -0,0 +1,198 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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_ASSOC_RAND_REGRESSION_TEST_HPP +#define PB_DS_ASSOC_RAND_REGRESSION_TEST_HPP + +#include <iostream> +#include <vector> +#include <regression/rand/assoc/container_rand_regression_test.h> +#include <io/verified_cmd_line_input.hpp> +#include <common_type/assoc/common_type.hpp> +#include <regression/basic_type.hpp> +#include <regression/common_type.hpp> + +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 ep, double cp, double mp, bool d) + : m_sd(seed), m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_ep(ep), m_cp(cp), + m_mp(mp), m_disp(d) + { } + + template<typename Cntnr> + void + operator()(Cntnr) + { + unsigned long ul = static_cast<unsigned long>(m_sd); + container_rand_regression_test<Cntnr> t(ul, m_n, m_n, m_tp, m_ip, + 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_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&, bool&); +} // namespace detail + + template<typename TL> + 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 = twister_rand_gen::get_time_determined_seed(); + double tp = 0.2; + double ip = 0.6; + double ep = 0.2; + double cp = 0.001; + double mp = 0.25; + bool disp = false; // show progress + + try + { + detail::verify_params(sd, n, m, tp, ip, ep, cp, mp, disp); + } + catch (__gnu_pbds::test::illegal_input_error&) + { + detail::usage(name); + return -1; + } + catch (...) + { + return -2; + }; + + // XXX RAII, constructor takes bool for display + xml_test_rand_regression_formatter* p_fmt = 0; + if (disp) + p_fmt = new xml_test_rand_regression_formatter(sd, n, m, tp, ip, ep, cp, mp); + + try + { + detail::rand_reg_test tst(sd, n, m, tp, ip, 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; + throw; + } + + if (disp) + delete p_fmt; + return 0; + } + +namespace detail +{ + inline void + usage(const std::string& name) + { + using namespace std; + cerr << "usage: " << name << " <sd> <n> <m> <tp> <ip> <ep> <cp> <mp> ['t' | 'f']" << + endl << endl; + + cerr << "This test performs basic regression tests on various associative containers." + "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 << "ep = probability that an operation will be erase" << endl; + cerr << "cp = probability that an operation will be clear" << endl; + cerr << "(therefore, 1 - (ip + 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_ep, + double& r_cp, double& r_mp, bool& r_d) + { + verify_prob(r_tp); + verify_prob(r_ip); + verify_prob(r_ep); + verify_prob(r_cp); + verify_prob(r_mp); + verify_prob(r_ip + r_ep + r_cp); + } +} // namespace detail +} // namespace test +} // namespace __gnu_pbds + +#endif 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 +// <http://www.gnu.org/licenses/>. + + +// 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 <algorithm> +#include <string> +#include <sstream> +#include <utility> +#include <cassert> +#include <regression/basic_type.hpp> +#include <ext/pb_ds/priority_queue.hpp> +#include <io/prog_bar.hpp> +#include <testsuite_rng.h> +#include <common_type/priority_queue/string_form.hpp> +#include <regression/rand/xml_formatter.hpp> +#include <regression/trait/priority_queue/trait.hpp> + +namespace __gnu_pbds +{ +namespace test +{ +namespace detail +{ + // Rand test specialized for a specific container. + template<typename Cntnr> + 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<std::string, true> native_type; + typedef regression_test_traits<cntnr> 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<typename Cntnr> + +#define PB_DS_CLASS_C_DEC \ + container_rand_regression_test<Cntnr> + +#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 <regression/rand/priority_queue/container_rand_regression_test.tcc> + +#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 +// <http://www.gnu.org/licenses/>. + + +// 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<std::string>()(top, native_top); + const bool top_larger = std::less<std::string>()(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<Cntnr>::name(), + string_form<Cntnr>::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<double>(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<typename cntnr::iterator>::reference + it_const_reference; + + m_alloc.set_probability(1); + + typedef + typename test_traits::template erase_if_fn<value_type> + 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<std::string> + 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<value_type> split_fn_t; + lhs.split(split_fn_t(), rhs); + + typedef typename test_traits::template erase_if_fn<std::string> + 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<cntnr>::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 +// <http://www.gnu.org/licenses/>. + + +// 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 <iostream> +#include <vector> +#include <io/verified_cmd_line_input.hpp> +#include <regression/common_type.hpp> +#include <regression/rand/priority_queue/container_rand_regression_test.h> + +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<typename Cntnr> + void + operator()(Cntnr) + { + unsigned long ul = static_cast<unsigned long>(m_sd); + container_rand_regression_test<Cntnr> 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<typename TL> + 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 << " <sd> <n> <m> <tp> <ip> <dp> <ep> <cp> <mp> ['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 diff --git a/libstdc++-v3/testsuite/util/regression/rand/xml_formatter.hpp b/libstdc++-v3/testsuite/util/regression/rand/xml_formatter.hpp new file mode 100644 index 000000000..5dca782c5 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/rand/xml_formatter.hpp @@ -0,0 +1,100 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 xml_formatter.hpp + * Contains an XML formatter for regression tests. + */ + +#ifndef PB_DS_COMMON_XML_TEST_REGRESSION_FORMATTER_HPP +#define PB_DS_COMMON_XML_TEST_REGRESSION_FORMATTER_HPP + +#include <string> +#include <iostream> +#include <io/xml_test_formatter.hpp> + +namespace __gnu_pbds +{ + namespace test + { + // Test formatters. + struct xml_test_rand_regression_formatter : public xml_test_formatter + { + // Associative. + xml_test_rand_regression_formatter(size_t sd, size_t n, size_t m, + double tp, double ip, double ep, + double cp, double mp) + { + std::cout << make_xml_tag("sd", "value", sd); + std::cout << make_xml_tag("n", "value", n); + std::cout << make_xml_tag("m", "value", m); + std::cout << make_xml_tag("tp", "value", tp); + std::cout << make_xml_tag("ip", "value", ip); + std::cout << make_xml_tag("ep", "value", ep); + std::cout << make_xml_tag("cp", "value", cp); + std::cout << make_xml_tag("mp", "value", mp); + } + + // Priority Queue. + xml_test_rand_regression_formatter(size_t sd, size_t n, size_t m, + double tp, double ip, double dp, + double ep, double cp, double mp) + { + std::cout << make_xml_tag("sd", "value", sd); + std::cout << make_xml_tag("n", "value", n); + std::cout << make_xml_tag("m", "value", m); + std::cout << make_xml_tag("tp", "value", tp); + std::cout << make_xml_tag("ip", "value", ip); + std::cout << make_xml_tag("dp", "value", dp); + std::cout << make_xml_tag("ep", "value", ep); + std::cout << make_xml_tag("cp", "value", cp); + std::cout << make_xml_tag("mp", "value", mp); + } + }; + + // Result formatter. + struct xml_result_set_regression_formatter : public xml_result_set_formatter + { + xml_result_set_regression_formatter(const std::string& r_container_name, + const std::string& r_container_desc) + : xml_result_set_formatter(r_container_name, r_container_desc) + { + std::cout << detail::make_xml_name_start_tag("progress"); + std::cout << detail::make_xml_name_start_tag_end_delimiter(); + } + + ~xml_result_set_regression_formatter() + { std::cout << detail::make_xml_name_end_tag("progress"); } + }; + } // namespace test +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_COMMON_XML_TEST_REGRESSION_FORMATTER_HPP diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_load_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_load_trait.hpp new file mode 100644 index 000000000..b771b8020 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_load_trait.hpp @@ -0,0 +1,90 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 get_set_load_trait.hpp + * Contains traits for a random regression test + * for a specific container type. + */ + +#ifndef PB_DS_REGRESSION_TEST_SET_LOAD_TRAIT_HPP +#define PB_DS_REGRESSION_TEST_SET_LOAD_TRAIT_HPP + +#include <ext/pb_ds/assoc_container.hpp> + +namespace __gnu_pbds +{ + + namespace test + { + + namespace detail + { + + template<typename Cntnr, class Tag> + struct regression_test_get_set_load_traits + { + enum + { + value = false + }; + }; + + template<typename Cntnr> + struct regression_test_hash_get_set_load_traits + { + enum + { + value = Cntnr::resize_policy::trigger_policy::get_set_load + }; + }; + + template<typename Cntnr> + struct regression_test_get_set_load_traits< + Cntnr, + __gnu_pbds::cc_hash_tag> : public regression_test_hash_get_set_load_traits< + Cntnr> + { }; + + template<typename Cntnr> + struct regression_test_get_set_load_traits< + Cntnr, + __gnu_pbds::gp_hash_tag> : public regression_test_hash_get_set_load_traits< + Cntnr> + { }; + + } // namespace detail + + } // namespace test + +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_REGRESSION_TEST_SET_LOAD_TRAIT_HPP diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_loads_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_loads_trait.hpp new file mode 100644 index 000000000..6d7508da8 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_loads_trait.hpp @@ -0,0 +1,90 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 get_set_loads_trait.hpp + * Contains traits for a random regression test + * for a specific container type. + */ + +#ifndef PB_DS_REGRESSION_TEST_SET_LOADS_TRAIT_HPP +#define PB_DS_REGRESSION_TEST_SET_LOADS_TRAIT_HPP + +#include <ext/pb_ds/assoc_container.hpp> + +namespace __gnu_pbds +{ + + namespace test + { + + namespace detail + { + + template<typename Cntnr, class Tag> + struct regression_test_get_set_loacontainer_traits + { + enum + { + value = false + }; + }; + + template<typename Cntnr> + struct regression_test_hash_get_set_loacontainer_traits + { + enum + { + value = Cntnr::resize_policy::trigger_policy::get_set_loads + }; + }; + + template<typename Cntnr> + struct regression_test_get_set_loacontainer_traits< + Cntnr, + __gnu_pbds::cc_hash_tag> : public regression_test_hash_get_set_loacontainer_traits< + Cntnr> + { }; + + template<typename Cntnr> + struct regression_test_get_set_loacontainer_traits< + Cntnr, + __gnu_pbds::gp_hash_tag> : public regression_test_hash_get_set_loacontainer_traits< + Cntnr> + { }; + + } // namespace detail + + } // namespace test + +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_REGRESSION_TEST_SET_LOADS_TRAIT_HPP diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/native_type_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/native_type_trait.hpp new file mode 100644 index 000000000..38761a177 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/native_type_trait.hpp @@ -0,0 +1,185 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 native_type_trait.hpp + * Contains traits for a random regression test + * for a specific container type. + */ + +#ifndef PB_DS_REGRESSION_TEST_NATIVE_TYPE_TRAIT_HPP +#define PB_DS_REGRESSION_TEST_NATIVE_TYPE_TRAIT_HPP + +namespace __gnu_pbds +{ + + namespace test + { + + namespace detail + { + + template<typename Key, class Allocator> + struct native_key_type; + + template<typename Allocator> + struct native_key_type< + basic_type, + Allocator> + { + typedef std::string type; + + static type + native_key(typename Allocator::template rebind< + basic_type>::other::const_reference r_key) + { + return (std::string(r_key)); + } + }; + + template<typename Hd, class Tl, class Allocator> + struct native_key_type< + std::pair< + Hd, + Tl>, + Allocator> + { + typedef typename native_key_type< Hd, Allocator>::type hd_type; + + typedef typename native_key_type< Tl, Allocator>::type tl_type; + + typedef std::pair< hd_type, tl_type> type; + + static type + native_key(typename Allocator::template rebind< std::pair<Hd, Tl> >::other::const_reference r_key) + { + return (std::make_pair( + native_key_type<Hd, Allocator>::native_key(r_key.first), + native_key_type<Tl, Allocator>::native_key(r_key.second))); + } + }; + + template<typename Native_Key_Type, + class Key_Type, + class Data_Type, + class Allocator> + struct native_type_traits_base; + + template<typename Native_Key_Type, class Key_Type, class Allocator> + struct native_type_traits_base< + Native_Key_Type, + Key_Type, + basic_type, + Allocator> + { + public: + typedef std::map< Native_Key_Type, std::string> type; + + public: + static const typename type::key_type& + extract_key(typename type::const_reference r_val) + { + return (r_val.first); + } + + static typename type::value_type + native_value(typename Allocator::template rebind< std::pair<Key_Type, basic_type> >::other::const_reference r_val) + { + return (std::make_pair( + native_key_type<Key_Type, Allocator>::native_key(r_val.first), + std::string(r_val.second))); + } + }; + + template<typename Native_Key_Type, class Key_Type, class Allocator> + struct native_type_traits_base< + Native_Key_Type, + Key_Type, + __gnu_pbds::null_mapped_type, + Allocator> + { + public: + typedef std::set< Native_Key_Type> type; + + public: + static const typename type::key_type& + extract_key(typename type::const_reference r_val) + { + return (r_val); + } + + static typename type::value_type + native_value(typename Allocator::template rebind< + Key_Type>::other::const_reference r_val) + { + return (native_key_type<Key_Type, Allocator>::native_key( + r_val)); + } + }; + +#define PB_DS_NATIVE_KEY_TYPE_C_DEC \ + native_key_type< \ + Key_Type, \ + Allocator> + +#define PB_DS_BASE_C_DEC \ + native_type_traits_base< \ + typename PB_DS_NATIVE_KEY_TYPE_C_DEC::type, \ + Key_Type, \ + Data_Type, \ + Allocator> + + template<typename Key_Type, class Data_Type, class Allocator> + struct native_type_traits : public PB_DS_BASE_C_DEC + { + typedef typename PB_DS_BASE_C_DEC::type type; + + typedef typename type::key_type key_type; + + static typename PB_DS_NATIVE_KEY_TYPE_C_DEC::type + native_key(typename Allocator::template rebind< + Key_Type>::other::const_reference r_key) + { + return (PB_DS_NATIVE_KEY_TYPE_C_DEC::native_key(r_key)); + } + }; + +#undef PB_DS_BASE_C_DEC + +#undef PB_DS_NATIVE_KEY_TYPE_C_DEC + + } // namespace detail + + } // namespace test + +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_REGRESSION_TEST_NATIVE_TYPE_TRAIT_HPP diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/node_update_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/node_update_trait.hpp new file mode 100644 index 000000000..d971c1fb2 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/node_update_trait.hpp @@ -0,0 +1,124 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 node_update_trait.hpp + * Contains traits for a random regression test + * for a specific container type. + */ + +#ifndef PB_DS_REGRESSION_TEST_NODE_UPDATOR_TRAIT_HPP +#define PB_DS_REGRESSION_TEST_NODE_UPDATOR_TRAIT_HPP + +#include <ext/pb_ds/assoc_container.hpp> +#include <common_type/assoc/detail/tree_supports_order_statistics.hpp> +#include <common_type/assoc/detail/trie_supports_order_statistics.hpp> +#include <common_type/assoc/detail/trie_supports_prefix_search.hpp> + +namespace __gnu_pbds +{ + + namespace test + { + + namespace detail + { + + template<typename Cntnr, class Tag> + struct regression_test_node_update_traits + { + enum + { + order_statistics = false, + prefix_search = false + }; + }; + + template<typename Cntnr> + struct regression_test_node_update_traits< + Cntnr, + __gnu_pbds::pat_trie_tag> + { + enum + { + order_statistics = + trie_supports_order_statistics<Cntnr>::value, + prefix_search = + trie_supports_prefix_search<Cntnr>::value + }; + }; + + template<typename Cntnr> + struct regression_test_node_update_traits< + Cntnr, + __gnu_pbds::rb_tree_tag> + { + enum + { + order_statistics = + tree_supports_order_statistics<Cntnr>::value, + prefix_search = false + }; + }; + + template<typename Cntnr> + struct regression_test_node_update_traits< + Cntnr, + __gnu_pbds::splay_tree_tag> + { + enum + { + order_statistics = + tree_supports_order_statistics<Cntnr>::value, + prefix_search = false + }; + }; + + template<typename Cntnr> + struct regression_test_node_update_traits< + Cntnr, + __gnu_pbds::ov_tree_tag> + { + enum + { + order_statistics = + tree_supports_order_statistics<Cntnr>::value, + prefix_search = false + }; + }; + + } // namespace detail + + } // namespace test + +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_REGRESSION_TEST_NODE_UPDATOR_TRAIT_HPP diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/resize_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/resize_trait.hpp new file mode 100644 index 000000000..51e012775 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/resize_trait.hpp @@ -0,0 +1,90 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 resize_trait.hpp + * Contains traits for a random regression test + * for a specific container type. + */ + +#ifndef PB_DS_REGRESSION_TEST_RESIZE_TRAIT_HPP +#define PB_DS_REGRESSION_TEST_RESIZE_TRAIT_HPP + +#include <ext/pb_ds/assoc_container.hpp> + +namespace __gnu_pbds +{ + + namespace test + { + + namespace detail + { + + template<typename Cntnr, class Tag> + struct regression_test_resize_traits + { + enum + { + value = false + }; + }; + + template<typename Cntnr> + struct regression_test_hash_resize_traits + { + enum + { + value = Cntnr::resize_policy::external_size_access + }; + }; + + template<typename Cntnr> + struct regression_test_resize_traits< + Cntnr, + __gnu_pbds::cc_hash_tag> : public regression_test_hash_resize_traits< + Cntnr> + { }; + + template<typename Cntnr> + struct regression_test_resize_traits< + Cntnr, + __gnu_pbds::gp_hash_tag> : public regression_test_hash_resize_traits< + Cntnr> + { }; + + } // namespace detail + + } // namespace test + +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_REGRESSION_TEST_RESIZE_TRAIT_HPP diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/to_string.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/to_string.hpp new file mode 100644 index 000000000..7a1a2e305 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/to_string.hpp @@ -0,0 +1,81 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 to_string.hpp + * Contains classes for transforming stuff to strings. + */ + +#ifndef PB_DS_REGRESSION_TEST_TO_STRING_HPP +#define PB_DS_REGRESSION_TEST_TO_STRING_HPP + +#include <regression/basic_type.hpp> +#include <string> + +namespace __gnu_pbds +{ + + namespace test + { + + namespace detail + { + + std::string + to_string(const basic_type& r_t) + { + return (r_t); + } + + std::string + to_string(const std::string& r_t) + { + return (r_t); + } + + template<typename Hd, class Tl> + std::string + to_string(const std::pair<Hd, Tl>&r_t) + { + std::ostringstream ret; + + ret << to_string(r_t.first) << " " << to_string(r_t.second); + + return (ret.str()); + } + + } // namespace detail + + } // namespace test + +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_REGRESSION_TEST_TO_STRING_HPP diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp new file mode 100644 index 000000000..a4a768e5e --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp @@ -0,0 +1,206 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 trait.hpp + * Contains traits for a random regression test + * for a specific container type. + */ + +#ifndef PB_DS_REGRESSION_TEST_TRAIT_HPP +#define PB_DS_REGRESSION_TEST_TRAIT_HPP + +#include <regression/trait/erase_if_fn.hpp> +#include <regression/trait/assoc/to_string.hpp> +#include <regression/trait/assoc/type_trait.hpp> +#include <regression/trait/assoc/native_type_trait.hpp> +#include <regression/trait/assoc/resize_trait.hpp> +#include <regression/trait/assoc/get_set_loads_trait.hpp> +#include <regression/trait/assoc/get_set_load_trait.hpp> +#include <regression/trait/assoc/node_update_trait.hpp> + +namespace __gnu_pbds +{ +namespace test +{ +namespace detail +{ + +#define PB_DS_CLASS_T_DEC \ + template<typename Cntnr> + +#define PB_DS_CLASS_C_DEC \ + regression_test_traits<Cntnr> + +#define PB_DS_TYPE_TRAITS_C_DEC \ + regression_test_type_traits<Cntnr> + +#define PB_DS_NATIVE_TYPE_TRAITS_C_DEC \ + native_type_traits<typename PB_DS_TYPE_TRAITS_C_DEC::key_type, \ + typename PB_DS_TYPE_TRAITS_C_DEC::mapped_type, \ + typename Cntnr::allocator_type> + +#define PB_DS_RESIZE_TRAITS_C_DEC \ + regression_test_resize_traits<Cntnr, typename Cntnr::container_category> + +#define PB_DS_SET_LOADS_TRAITS_C_DEC \ + regression_test_get_set_loacontainer_traits<Cntnr, \ + typename Cntnr::container_category> + +#define PB_DS_SET_LOAD_TRAITS_C_DEC \ + regression_test_get_set_load_traits<Cntnr,typename Cntnr::container_category> + +#define PB_DS_NODE_UPDATOR_TRAITS_C_DEC \ + regression_test_node_update_traits<Cntnr, typename Cntnr::container_category> + + template<typename Cntnr> + struct regression_test_traits : private PB_DS_TYPE_TRAITS_C_DEC, + private PB_DS_NATIVE_TYPE_TRAITS_C_DEC, + private PB_DS_RESIZE_TRAITS_C_DEC, + private PB_DS_NODE_UPDATOR_TRAITS_C_DEC, + private PB_DS_SET_LOADS_TRAITS_C_DEC, + private PB_DS_SET_LOAD_TRAITS_C_DEC + { + private: + typedef PB_DS_NATIVE_TYPE_TRAITS_C_DEC native_type_traits_base; + typedef PB_DS_TYPE_TRAITS_C_DEC type_traits_base; + + public: + typedef typename Cntnr::value_type value_type; + typedef typename Cntnr::const_reference const_reference; + typedef typename PB_DS_NATIVE_TYPE_TRAITS_C_DEC::type native_type; + typedef typename native_type::value_type native_value_type; + + // Only associative containers. + typedef typename Cntnr::key_type key_type; + typedef typename Cntnr::const_key_reference const_key_reference; + typedef typename native_type::key_type native_key_type; + + enum + { + resize = PB_DS_RESIZE_TRAITS_C_DEC::value, + get_set_loads = PB_DS_SET_LOADS_TRAITS_C_DEC::value, + get_set_load = PB_DS_SET_LOAD_TRAITS_C_DEC::value, + order_statistics = PB_DS_NODE_UPDATOR_TRAITS_C_DEC::order_statistics, + prefix_search = PB_DS_NODE_UPDATOR_TRAITS_C_DEC::prefix_search + }; + + template<typename T> + struct erase_if_fn : public regression_test_erase_if_fn<T> + { }; + + static size_t + erase_if(native_type& r_native_c) + { + typedef regression_test_erase_if_fn<native_value_type> erase_if_fn; + typename native_type::iterator it = r_native_c.begin(); + size_t num_ersd = 0; + while (it != r_native_c.end()) + if (erase_if_fn()(*it)) + { + ++num_ersd; + r_native_c.erase(it); + it = r_native_c.begin(); + } + else + ++it; + return num_ersd; + } + + static void + print_container(const Cntnr& r_c, std::ostream& r_os) + { PB_DS_TYPE_TRAITS_C_DEC::print_container(r_c, r_os); } + + template<typename Gen> + static key_type + generate_key(Gen& r_gen, size_t max) + { return PB_DS_TYPE_TRAITS_C_DEC::generate_key(r_gen, max); } + + template<typename Gen> + static value_type + generate_value(Gen& r_gen, size_t max) + { return PB_DS_TYPE_TRAITS_C_DEC::generate_value(r_gen, max); } + + static const_key_reference + extract_key(const_reference r_val) + { return type_traits_base::extract_key(r_val); } + + static native_key_type + native_key(const_key_reference r_key) + { return native_type_traits_base::native_key(r_key); } + + static native_value_type + native_value(const_reference r_val) + { return native_type_traits_base::native_value(r_val); } + + static const native_key_type& + extract_native_key(const native_value_type& r_val) + { return native_type_traits_base::extract_key(r_val); } + + static bool + cmp(const_reference r_val, const native_value_type& r_native_val) + { return val_to_string(r_val) == native_val_to_string(r_native_val); } + + static std::string + val_to_string(const_reference r_val) + { return to_string(r_val); } + + static std::string + key_to_string(const_key_reference r_key) + { return to_string(r_key); } + + static std::string + native_val_to_string(const native_value_type& r_native_val) + { return to_string(r_native_val); } + + static bool + prefix_match(const_key_reference r_key, const std::string& r_native_key) + { + const size_t len = std::min(r_key.length(), r_native_key.length()); + const std::string substr = r_native_key.substr(0, len); + return substr == static_cast<const std::string&>(r_key); + } + }; + +#undef PB_DS_TYPE_TRAITS_C_DEC +#undef PB_DS_NATIVE_TYPE_TRAITS_C_DEC +#undef PB_DS_RESIZE_TRAITS_C_DEC +#undef PB_DS_SET_LOADS_TRAITS_C_DEC +#undef PB_DS_SET_LOAD_TRAITS_C_DEC +#undef PB_DS_NODE_UPDATOR_TRAITS_C_DEC +#undef PB_DS_CLASS_T_DEC +#undef PB_DS_CLASS_C_DEC + +} // namespace detail +} // namespace test +} // namespace __gnu_pbds + +#endif diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp new file mode 100644 index 000000000..c7ce5f7a3 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp @@ -0,0 +1,111 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 type_trait.hpp + * Contains traits for a random regression test + * for a specific container type. + */ + +#ifndef PB_DS_REGRESSION_TEST_TYPE_TRAIT_HPP +#define PB_DS_REGRESSION_TEST_TYPE_TRAIT_HPP + +#include <regression/basic_type.hpp> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename Cntnr> + struct regression_test_type_traits + { + typedef Cntnr cntnr; + typedef typename cntnr::key_type key_type; + typedef typename cntnr::const_key_reference const_key_reference; + typedef typename cntnr::value_type value_type; + typedef typename cntnr::const_reference const_reference; + typedef typename cntnr::mapped_type mapped_type; + typedef typename cntnr::const_mapped_reference const_mapped_reference; + + template<typename Gen> + static key_type + generate_key(Gen& r_gen, size_t max) + { return basic_type(r_gen, max); } + + template<typename Gen> + static value_type + generate_value(Gen& r_gen, size_t max) + { return generate_value(r_gen, max, value_type()); } + + static const_key_reference + extract_key(const_reference r_val) + { return extract_key_imp(r_val); } + + private: + typedef typename cntnr::allocator_type::template rebind<basic_type>::other + basic_type_rebind; + + typedef typename basic_type_rebind::const_reference basic_type_const_reference; + + typedef typename cntnr::allocator_type::template rebind<std::pair<const basic_type, basic_type> >::other pair_type_rebind; + typedef typename pair_type_rebind::const_reference pair_type_const_reference; + + template<typename Gen> + static value_type + generate_value(Gen& r_gen, size_t max, __gnu_pbds::null_mapped_type) + { return basic_type(r_gen, max); } + + template<typename Gen> + static value_type + generate_value(Gen& r_gen, size_t max, basic_type) + { return basic_type(r_gen, max); } + + template<typename Gen> + static value_type + generate_value(Gen& gen, size_t max, + std::pair<const basic_type, basic_type>) + { return std::make_pair(basic_type(gen, max), basic_type(gen, max)); } + + static const_key_reference + extract_key_imp(basic_type_const_reference r_val) + { return r_val; } + + static const_key_reference + extract_key_imp(pair_type_const_reference r_val) + { return r_val.first; } + }; + } // namespace detail + } // namespace test +} // namespace __gnu_pbds + +#endif diff --git a/libstdc++-v3/testsuite/util/regression/trait/erase_if_fn.hpp b/libstdc++-v3/testsuite/util/regression/trait/erase_if_fn.hpp new file mode 100644 index 000000000..9903dfeb3 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/trait/erase_if_fn.hpp @@ -0,0 +1,85 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 erase_if_fn.hpp + * Contains traits for a random regression test + * for a specific container type. + */ + +#ifndef PB_DS_REGRESSION_TEST_ERASE_IF_FN_HPP +#define PB_DS_REGRESSION_TEST_ERASE_IF_FN_HPP + +#include <functional> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename T> + struct regression_test_erase_if_fn + : public std::unary_function<T, bool> + { + private: + typedef const T& const_reference; + + public: + bool + operator()(const_reference r_t) const + { + return (r_t.length() == 0 || + static_cast<size_t>(*((r_t).begin())) % 2 == 1); + } + }; + + template<typename Hd, class Tl> + struct regression_test_erase_if_fn<std::pair<Hd, Tl> > + : public std::unary_function<std::pair<Hd, Tl>, bool> + { + private: + typedef const std::pair<Hd, Tl>& const_reference; + typedef regression_test_erase_if_fn<Hd> hd_erase_if_fn; + typedef regression_test_erase_if_fn<Tl> tl_erase_if_fn; + + public: + bool + operator()(const_reference r_t) const + { + return (hd_erase_if_fn()(r_t.first) && tl_erase_if_fn()(r_t.second)); + } + }; + } // namespace detail + } // namespace test +} // namespace __gnu_pbds + +#endif diff --git a/libstdc++-v3/testsuite/util/regression/trait/priority_queue/trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/priority_queue/trait.hpp new file mode 100644 index 000000000..f55dbbc99 --- /dev/null +++ b/libstdc++-v3/testsuite/util/regression/trait/priority_queue/trait.hpp @@ -0,0 +1,82 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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 +// <http://www.gnu.org/licenses/>. + + +// 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 trait.hpp + * Contains traits for a random regression test + * for a specific container type. + */ + +#ifndef PB_DS_REGRESSION_TEST_TRAIT_HPP +#define PB_DS_REGRESSION_TEST_TRAIT_HPP + +#include <regression/trait/erase_if_fn.hpp> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename Cntnr> + struct regression_test_traits + { + typedef typename Cntnr::value_type value_type; + typedef typename Cntnr::const_reference const_reference; + typedef __gnu_pbds::test::native_priority_queue<std::string, true> native_type; + typedef typename native_type::value_type native_value_type; + + template<typename T> + struct erase_if_fn : public regression_test_erase_if_fn<T> + { }; + + template<typename Gen> + static value_type + generate_value(Gen& r_gen, size_t max) + { return basic_type(r_gen, max); } + + static native_value_type + native_value(const_reference r_val) + { return native_value_type(r_val); } + + static bool + cmp(const_reference r_val, const native_value_type& r_native_val) + { return val_to_string(r_val) == r_native_val; } + + static std::string + val_to_string(const_reference r_val) + { return std::string(r_val); } + }; + } // namespace detail + } // namespace test +} // namespace __gnu_pbds + +#endif |