From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- .../performance/assoc/mem_usage/erase_test.hpp | 109 ++++++++++ .../assoc/mem_usage/multimap_insert_test.hpp | 144 +++++++++++++ .../performance/assoc/multimap_common_type.hpp | 223 +++++++++++++++++++++ .../util/performance/assoc/timing/common_type.hpp | 103 ++++++++++ .../util/performance/assoc/timing/find_test.hpp | 166 +++++++++++++++ .../util/performance/assoc/timing/insert_test.hpp | 143 +++++++++++++ .../assoc/timing/multimap_find_test.hpp | 191 ++++++++++++++++++ .../assoc/timing/multimap_insert_test.hpp | 151 ++++++++++++++ .../assoc/timing/subscript_find_test.hpp | 144 +++++++++++++ .../assoc/timing/subscript_insert_test.hpp | 134 +++++++++++++ .../assoc/timing/tree_order_statistics_test.hpp | 176 ++++++++++++++++ .../assoc/timing/tree_split_join_test.hpp | 158 +++++++++++++++ 12 files changed, 1842 insertions(+) create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/mem_usage/erase_test.hpp create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/mem_usage/multimap_insert_test.hpp create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/multimap_common_type.hpp create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/timing/common_type.hpp create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/timing/find_test.hpp create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/timing/insert_test.hpp create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_find_test.hpp create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_insert_test.hpp create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/timing/tree_order_statistics_test.hpp create mode 100644 libstdc++-v3/testsuite/util/performance/assoc/timing/tree_split_join_test.hpp (limited to 'libstdc++-v3/testsuite/util/performance/assoc') diff --git a/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/erase_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/erase_test.hpp new file mode 100644 index 000000000..6ad797a66 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/erase_test.hpp @@ -0,0 +1,109 @@ +// -*- 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 +// . + + +// 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_test.hpp + * Contains a generic erase test. + */ + +#ifndef PB_DS_ERASE_TEST_HPP +#define PB_DS_ERASE_TEST_HPP + +#include +#include +#include +#include +#include + +namespace __gnu_pbds +{ + namespace test + { + template + class erase_test + { + public: + erase_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) + : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template + void + operator()(Cntnr); + + private: + erase_test(const erase_test&); + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + template + template + void + erase_test:: + operator()(Cntnr) + { + typedef string_form sform_type; + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(sform_type::name(), sform_type::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t ins_size = m_ins_vn + i * m_ins_vs; + + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, ins_size); + + typedef __gnu_test::tracker_allocator_counter counter_type; + __gnu_test::tracker_allocator alloc; + const size_t init_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + Cntnr cntnr(ins_it_b, ins_it_e); + + while (cntnr.size() > 1) + cntnr.erase(*cntnr.begin()); + + const size_t final_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + assert(final_mem > init_mem); + const size_t delta_mem = final_mem - init_mem; + res_set_fmt.add_res(ins_size, static_cast(delta_mem)); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/multimap_insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/multimap_insert_test.hpp new file mode 100644 index 000000000..110dd923f --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/multimap_insert_test.hpp @@ -0,0 +1,144 @@ +// -*- 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 +// . + + +// 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 multimap_insert_test.hpp + * Contains a generic multimap_insert_test test. + */ + +#ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP +#define PB_DS_MULTIMAP_INSERT_TEST_HPP + +#include +#include +#include +#include +#include + +namespace __gnu_pbds +{ + namespace test + { + template + class multimap_insert_test + { + public: + multimap_insert_test(It b, size_t ins_vn, size_t ins_vs, size_t ins_vm): + m_ins_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template + void + operator()(Cntnr); + + private: + multimap_insert_test(const multimap_insert_test&); + + template + size_t + insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::true_type); + + template + size_t + insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::false_type); + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + template + template + void + multimap_insert_test:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form::name(), + string_form::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t ins_size = m_ins_vn + i * m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, ins_size); + + const size_t delta_mem = insert(Cntnr(), ins_it_b, ins_it_e, + __gnu_pbds::detail::integral_constant()); + + res_set_fmt.add_res(ins_size, static_cast(delta_mem)); + } + } + + template + template + size_t + multimap_insert_test:: + insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::true_type) + { + typedef __gnu_test::tracker_allocator_counter counter_type; + __gnu_test::tracker_allocator alloc; + const size_t init_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + Cntnr cntnr; + for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it) + cntnr.insert((typename Cntnr::const_reference)(*ins_it)); + const size_t final_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + assert(final_mem > init_mem); + return (final_mem - init_mem); + } + + template + template + size_t + multimap_insert_test:: + insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::false_type) + { + typedef __gnu_test::tracker_allocator_counter counter_type; + __gnu_test::tracker_allocator alloc; + const size_t init_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + Cntnr cntnr; + for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it) + cntnr[ins_it->first].insert(ins_it->second); + const size_t final_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + assert(final_mem > init_mem); + return (final_mem - init_mem); + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/multimap_common_type.hpp b/libstdc++-v3/testsuite/util/performance/assoc/multimap_common_type.hpp new file mode 100644 index 000000000..e31abe106 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/multimap_common_type.hpp @@ -0,0 +1,223 @@ +// -*- 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 +// . + + +// 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 multimap_common_type.hpp + * Contains types for a generic multimap_insert_test test. + */ + +#ifndef PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP +#define PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP + +#include +#include + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + struct int_hash : public std::unary_function + { + inline size_t + operator()(const int i) const + { return (static_cast(i)); } + }; + + template > + struct hash_set_tl_t + { + typedef + typename __gnu_pbds::test::hash_common_types< + Key, + __gnu_pbds::null_mapped_type, + int_hash, + std::equal_to, + Allocator>::performance_min_tl + type; + }; + + template > + struct lu_set_tl_t + { + typedef + typename __gnu_pbds::test::lu_common_types< + Key, + __gnu_pbds::null_mapped_type, + std::equal_to< + Key>, + Allocator>::performance_min_tl + type; + }; + + template > + struct hash_mmap_tl_t + { + private: + typedef + typename __gnu_pbds::detail::__conditional_type< + __gnu_pbds::detail::is_same< + int, + Key>::value, + int_hash, + string_hash_fn>::__type + hash_fn_t; + + template + struct hash_mmap_transform + { + typedef + typename __gnu_pbds::test::hash_common_types< + Key, + Cntnr_T, + hash_fn_t, + std::equal_to< + Key>, + Allocator>::performance_min_tl + type; + }; + + public: + typedef + typename __gnu_cxx::typelist::flatten< + typename __gnu_cxx::typelist::transform< + Sec_Tl, + hash_mmap_transform>::type>::type + type; + }; + + template > + struct tree_mmap_tl_t + { + private: + template + struct tree_mmap_transform + { + typedef + typename __gnu_pbds::test::tree_common_types< + Key, + Cntnr_T, + std::less< + Key>, + __gnu_pbds::null_tree_node_update, + Allocator>::performance_min_tl + type; + }; + + public: + typedef + typename __gnu_cxx::typelist::flatten< + typename __gnu_cxx::typelist::transform< + Sec_Tl, + tree_mmap_transform>::type>::type + type; + }; + + template + struct hash_hash_mmap_tl_t + { + private: + typedef typename hash_set_tl_t::type sec_tl_t; + + public: + typedef typename hash_mmap_tl_t::type type; + }; + + template + struct tree_hash_mmap_tl_t + { + private: + typedef typename hash_set_tl_t::type sec_tl_t; + + public: + typedef typename tree_mmap_tl_t::type type; + }; + + template + struct tree_lu_mmap_tl_t + { + private: + typedef typename lu_set_tl_t::type sec_tl_t; + + public: + typedef typename tree_mmap_tl_t::type type; + }; + + template + struct hash_lu_mmap_tl_t + { + private: + typedef typename lu_set_tl_t::type sec_tl_t; + + public: + typedef typename hash_mmap_tl_t::type type; + }; + } // namespace detail + + template + struct mmap_tl_t + { + private: + typedef + typename detail::hash_hash_mmap_tl_t::type + hh_mmap_tl_t; + + typedef + typename detail::hash_lu_mmap_tl_t::type + hl_mmap_tl_t; + + typedef + typename detail::tree_hash_mmap_tl_t::type + th_mmap_tl_t; + + typedef + typename detail::tree_lu_mmap_tl_t::type + tl_mmap_tl_t; + + public: + typedef + typename __gnu_cxx::typelist::append::type>::type>::type + type; + }; + + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/common_type.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/common_type.hpp new file mode 100644 index 000000000..a553afeab --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/common_type.hpp @@ -0,0 +1,103 @@ +// -*- 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 +// . + + +// 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 for a generic multimap_insert_test test. + */ + +#ifndef PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP +#define PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP + +#include + +namespace __gnu_pbds +{ + + namespace test + { + + typedef + __gnu_pbds::test::hash_common_types< + int, + __gnu_pbds::null_mapped_type>::tl + hash_set_tl_t; + + template + struct hash_mmap_transform + { + typedef + typename __gnu_pbds::test::hash_common_types< + int, + __gnu_pbds::compound_data_type< + Cntnr_T> >::tl + type; + }; + + typedef + __gnu_cxx::typelist::flatten< + __gnu_cxx::typelist::transform< + hash_set_tl_t, + hash_mmap_transform>::type>::type + hash_mmap_tl_t; + + typedef + __gnu_pbds::test::tree_common_types< + int, + __gnu_pbds::null_mapped_type>::tl + tree_set_tl_t; + + template + struct tree_mmap_transform + { + typedef + typename __gnu_pbds::test::tree_common_types< + int, + __gnu_pbds::compound_data_type< + Cntnr_T> >::tl + type; + }; + + typedef + __gnu_cxx::typelist::flatten< + __gnu_cxx::typelist::transform< + tree_set_tl_t, + tree_mmap_transform>::type>::type + tree_mmap_tl_t; + + typedef hash_mmap_tl_t mmap_tl_t; + + } // namespace test + +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/find_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/find_test.hpp new file mode 100644 index 000000000..f53a1273c --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/find_test.hpp @@ -0,0 +1,166 @@ +// -*- 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 +// . + + +// 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 find_test.hpp + * Contains a generic find test. + */ + +#ifndef PB_DS_FIND_TEST_HPP +#define PB_DS_FIND_TEST_HPP + +#include +#include +#include +#include + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template + class find_find_functor + { + public: + find_find_functor(Cntnr& contnr, It fnd_it_b, It fnd_it_e) + : m_contnr(contnr), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + It fnd_it = m_fnd_it_b; + while (fnd_it != m_fnd_it_e) + ++m_contnr.find((fnd_it++)->first)->second; + } + } + + private: + Cntnr& m_contnr; + const It m_fnd_it_b; + const It m_fnd_it_e; + }; + + template + class find_find_functor + { + public: + find_find_functor(Cntnr& contnr, It fnd_it_b, It fnd_it_e) + : m_contnr(contnr), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) + { } + + void + operator()(std::size_t resolution) + { + It fnd_it = m_fnd_it_b; + while (fnd_it != m_fnd_it_e) + { + for (std::size_t i = 0; i < resolution; ++i) + ++m_contnr.find(fnd_it->first)->second; + ++fnd_it; + } + } + + private: + Cntnr& m_contnr; + const It m_fnd_it_b; + const It m_fnd_it_e; + }; + } // namespace detail + + template + class find_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + find_test(It ins_b, It fnd_it_b, size_t ins_vn, size_t ins_vs, + size_t ins_vm, size_t fnd_vn, size_t fnd_vs, size_t fnd_vm): + m_ins_b(ins_b), m_fnd_it_b(fnd_it_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), + m_ins_vm(ins_vm), m_fnd_vn(fnd_vn), m_fnd_vs(fnd_vs), m_fnd_vm(fnd_vm) + { } + + template + void + operator()(Cntnr); + + private: + find_test(const find_test& ); + + private: + const It m_ins_b; + const It m_fnd_it_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + const size_t m_fnd_vn; + const size_t m_fnd_vs; + const size_t m_fnd_vm; + }; + + template + template + void + find_test:: + operator()(Cntnr) + { + typedef string_form sform_type; + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(sform_type::name(), sform_type::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i * m_ins_vs; + const size_t fnd_size = m_fnd_vn + i * m_fnd_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + Cntnr test_container(ins_it_b, ins_it_e); + It fnd_it_b = m_fnd_it_b; + It fnd_it_e = m_fnd_it_b; + std::advance(fnd_it_e, fnd_size); + + __gnu_pbds::test::detail::find_find_functor + fn(test_container, fnd_it_b, fnd_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + res_set_fmt.add_res(v, res / fnd_size); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/insert_test.hpp new file mode 100644 index 000000000..e71d755ba --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/insert_test.hpp @@ -0,0 +1,143 @@ +// -*- 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 +// . + + +// 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 insert_test.hpp + * Contains an insert performance test. + */ + +#ifndef PB_DS_INSERT_TEST_HPP +#define PB_DS_INSERT_TEST_HPP + +#include +#include +#include +#include +#include + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template + class insert_insert_functor + { + public: + insert_insert_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + cntnr.insert((typename Cntnr::const_reference)(*ins_it)); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + } // namespace detail + + template + class insert_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + insert_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) + : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template + void + operator()(Cntnr); + + private: + insert_test(const insert_test& ); + + template + void + insert(Cntnr, It ins_it_b, It ins_it_e); + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + template + template + void + insert_test:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form::name(), + string_form::desc()); + + for (size_t i = 0; m_ins_vn + i* m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i* m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + __gnu_pbds::test::detail::insert_insert_functor + fn(ins_it_b, ins_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / v); + } + } + + template + template + void + insert_test:: + insert(Cntnr, It ins_it_b, It ins_it_e) + { + Cntnr cntnr; + for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it) + cntnr.insert((typename Cntnr::const_reference)(*ins_it)); + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp new file mode 100644 index 000000000..7e3f95bfc --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp @@ -0,0 +1,191 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 2009 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// . + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file multimap_find_test.hpp + * Contains a generic multimap_find_test test. + */ + +#ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP +#define PB_DS_MULTIMAP_INSERT_TEST_HPP + +#include +#include +#include +#include + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template + class multimap_find_functor + { + public: + multimap_find_functor(const Cntnr& container, It fnd_it_b, It fnd_it_e) + : m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) + { } + + void + operator()(std::size_t resolution) + { + size_t not_found_count = 0; + typedef typename Cntnr::const_point_iterator iterator_type; + for (std::size_t i = 0; i < resolution; ++i) + { + iterator_type end = m_r_container.end(); + for (It fnd_it = m_fnd_it_b; fnd_it != m_fnd_it_e; ++fnd_it) + { + iterator_type it = m_r_container.find(fnd_it->first); + if (it == end || + it->second.find(fnd_it->second) == it->second.end()) + ++not_found_count; + } + } + + if (not_found_count != 0) + std::abort(); + } + + private: + const Cntnr& m_r_container; + const It m_fnd_it_b; + const It m_fnd_it_e; + }; + + template + class multimap_find_functor + { + public: + multimap_find_functor(const Cntnr& container, It fnd_it_b, It fnd_it_e) + : m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) + { } + + void + operator()(std::size_t resolution) + { + typedef typename Cntnr::const_reference const_reference; + size_t not_found_count = 0; + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It fnd_it = m_fnd_it_b; fnd_it != m_fnd_it_e; ++fnd_it) + if (m_r_container.find(const_reference(*fnd_it)) + == m_r_container.end()) + ++not_found_count; + } + + if (not_found_count != 0) + std::abort(); + } + + private: + const Cntnr& m_r_container; + const It m_fnd_it_b; + const It m_fnd_it_e; + }; + } // namespace detail + + + template + class multimap_find_test + : private __gnu_pbds::test::detail::timing_test_base + { + public: + multimap_find_test(It ins_b, size_t ins_vn, size_t vs, size_t ins_vm) + : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(vs), m_ins_vm(ins_vm) + { } + + template + void + operator()(Cntnr); + + private: + multimap_find_test(const multimap_find_test&); + + template + Cntnr + init(It ins_b, It ins_e, Cntnr, __gnu_pbds::detail::true_type) + { return Cntnr(ins_b, ins_e); } + + template + Cntnr + init(It ins_b, It ins_e, Cntnr, __gnu_pbds::detail::false_type) + { + Cntnr ret; + for (It it = ins_b; it != ins_e; ++it) + ret[it->first].insert(it->second); + return ret; + } + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + + template + template + void + multimap_find_test:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form::name(), + string_form::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i * m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + Cntnr c = init(ins_it_b, ins_it_e, Cntnr(), + __gnu_pbds::detail::integral_constant()); + + __gnu_pbds::test::detail::multimap_find_functor + fn(c, ins_it_b, ins_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / v); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp new file mode 100644 index 000000000..2e8539857 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp @@ -0,0 +1,151 @@ +// -*- 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 +// . + + +// 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 multimap_insert_test.hpp + * Contains a generic multimap_insert_test test. + */ + +#ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP +#define PB_DS_MULTIMAP_INSERT_TEST_HPP + +#include +#include +#include +#include + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template + class multimap_insert_functor + { + public: + multimap_insert_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + cntnr[ins_it->first].insert(ins_it->second); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + + template + class multimap_insert_functor + { + public: + multimap_insert_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + cntnr.insert((typename Cntnr::const_reference)(*ins_it)); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + } // namespace detail + + template + class multimap_insert_test + : private __gnu_pbds::test::detail::timing_test_base + { + public: + multimap_insert_test(It b, size_t ins_vn, size_t ins_vs, size_t ins_vm) + : m_ins_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template + void + operator()(Cntnr); + + private: + multimap_insert_test(const multimap_insert_test&); + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + template + template + void + multimap_insert_test:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form::name(), + string_form::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i * m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + __gnu_pbds::test::detail::multimap_insert_functor + fn(ins_it_b, ins_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + res_set_fmt.add_res(v, res / v); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_find_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_find_test.hpp new file mode 100644 index 000000000..d37121b8c --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_find_test.hpp @@ -0,0 +1,144 @@ +// -*- 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 +// . + + +// 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 subscript_find_test.hpp + * Contains a generic subscript_find_test test. + */ + +#ifndef PB_DS_SUBSCRIPT_TEST_HPP +#define PB_DS_SUBSCRIPT_TEST_HPP + +#include +#include +#include + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template + class subscript_find_functor + { + public: + subscript_find_functor(Cntnr& container, It fnd_it_b, It fnd_it_e) + : m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + It fnd_it = m_fnd_it_b; + while (fnd_it != m_fnd_it_e) + ++m_r_container[(fnd_it++)->first]; + ++fnd_it; + } + } + + private: + Cntnr& m_r_container; + const It m_fnd_it_b; + const It m_fnd_it_e; + }; + + } // namespace detail + + template + class subscript_find_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + subscript_find_test(It ins_b, It b, size_t ins_vn, size_t ins_vs, + size_t ins_vm, size_t vn, size_t vs, size_t vm) + : m_ins_b(ins_b), m_fnd_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), + m_ins_vm(ins_vm), m_fnd_vn(vn), m_fnd_vs(vs), m_fnd_vm(vm) + { } + + template + void + operator()(Cntnr); + + private: + subscript_find_test(const subscript_find_test&); + + private: + const It m_ins_b; + const It m_fnd_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + const size_t m_fnd_vn; + const size_t m_fnd_vs; + const size_t m_fnd_vm; + }; + + template + template + void + subscript_find_test:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form::name(), + string_form::desc()); + + for (size_t i = 0; m_ins_vn + i* m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i* m_ins_vs; + const size_t fnd_size = m_fnd_vn + i* m_fnd_vs; + + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + Cntnr test_container(ins_it_b, ins_it_e); + + It fnd_it_b = m_fnd_b; + It fnd_it_e = m_fnd_b; + std::advance(fnd_it_e, fnd_size); + + __gnu_pbds::test::detail::subscript_find_functor + fn(test_container, fnd_it_b, fnd_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / fnd_size); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_insert_test.hpp new file mode 100644 index 000000000..10925fd60 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_insert_test.hpp @@ -0,0 +1,134 @@ +// -*- 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 +// . + + +// 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 subscript_insert_test.hpp + * Contains a generic subscript_insert_test test. + */ + +#ifndef PB_DS_SUBSCRIPT_TEST_HPP +#define PB_DS_SUBSCRIPT_TEST_HPP + +#include +#include +#include +#include + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template + class subscript_insert_functor + { + public: + subscript_insert_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + ++cntnr[ins_it->first]; + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + + } // namespace detail + + template + class subscript_insert_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + subscript_insert_test(It ins_b, It b, size_t ins_vn, size_t ins_vs, + size_t ins_vm, size_t vn, size_t vs, size_t vm) + : m_ins_b(ins_b), m_fnd_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), + m_ins_vm(ins_vm), m_fnd_vn(vn), m_fnd_vs(vs), m_fnd_vm(vm) + { } + + template + void + operator()(Cntnr); + + private: + subscript_insert_test(const subscript_insert_test& ); + + private: + const It m_ins_b; + const It m_fnd_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + const size_t m_fnd_vn; + const size_t m_fnd_vs; + const size_t m_fnd_vm; + }; + + template + template + void + subscript_insert_test:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form::name(), + string_form::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i * m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + __gnu_pbds::test::detail::subscript_insert_functor + fn(ins_it_b, ins_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / v); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_order_statistics_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_order_statistics_test.hpp new file mode 100644 index 000000000..0fb028687 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_order_statistics_test.hpp @@ -0,0 +1,176 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 2009 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// . + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file tree_order_statistics_test.hpp + * Contains a test for order_statisticsing trees + */ + +#ifndef PB_DS_TREE_ORDER_STATISTICS_TEST_HPP +#define PB_DS_TREE_ORDER_STATISTICS_TEST_HPP + +#include +#include +#include +#include +#include +#include + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template + class order_statistics_functor + { + public: + order_statistics_functor(Cntnr& container) : m_r_container(container) + { } + + void + operator()(std::size_t resolution) + { + enum + { + support_detected = + __gnu_pbds::test::detail::tree_supports_order_statistics::value + }; + + PB_DS_STATIC_ASSERT(correct_type, support_detected); + + for (std::size_t i = 0; i < resolution; ++i) + { + typename Cntnr::const_iterator it = m_r_container.begin(); + typename Cntnr::const_iterator e = m_r_container.end(); + const size_t max_size = m_r_container.size(); + while (it != e) + if (m_r_container.order_of_key(*(it++)) > max_size) + std::abort(); + } + } + + private: + Cntnr& m_r_container; + }; + + template + class order_statistics_functor + { + public: + order_statistics_functor(Cntnr& container) : m_r_container(container) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + typedef typename Cntnr::const_iterator const_iterator; + const_iterator b = m_r_container.begin(); + const_iterator e = m_r_container.end(); + const_iterator it = b; + const size_t max_size = m_r_container.size(); + while (it != e) + { + const_iterator f_it = m_r_container.find(*(it++)); + if (static_cast(std::distance(b, f_it)) > max_size) + std::abort(); + } + } + } + + private: + Cntnr& m_r_container; + }; + } // namespace detail + + template + class tree_order_statistics_test + : private __gnu_pbds::test::detail::timing_test_base + { + public: + tree_order_statistics_test(size_t vn, size_t vs, size_t vm) + : m_vn(vn), m_vs(vs), m_vm(vm) + { } + + template + void + operator()(Cntnr); + + private: + tree_order_statistics_test(const tree_order_statistics_test& ); + + template + void + order_statistics(Cntnr& r_container, __gnu_pbds::detail::true_type); + + template + void + order_statistics(Cntnr& r_container, __gnu_pbds::detail::false_type); + + private: + const size_t m_vn; + const size_t m_vs; + const size_t m_vm; + }; + + template + template + void + tree_order_statistics_test:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form::name(), + string_form::desc()); + + for (size_t v = m_vn; v < m_vm; v += m_vs) + { + Cntnr cntnr; + for (size_t ins = 0; ins < v; ++ ins) + cntnr.insert((typename Cntnr::value_type)ins); + + __gnu_pbds::test::detail::order_statistics_functor + fn(cntnr); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / v); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_split_join_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_split_join_test.hpp new file mode 100644 index 000000000..6872291df --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_split_join_test.hpp @@ -0,0 +1,158 @@ +// -*- 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 +// . + + +// 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 tree_split_join_test.hpp + * Contains a test for splitting and joining trees + */ + +#ifndef PB_DS_TREE_SPLIT_JOIN_TEST_HPP +#define PB_DS_TREE_SPLIT_JOIN_TEST_HPP + +#include +#include +#include +#include + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template + class split_join_functor + { + public: + split_join_functor(Cntnr& r_container) : m_r_container(r_container) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + typename Cntnr::const_iterator mid_it = m_r_container.begin(); + std::advance(mid_it, m_r_container.size() / 2); + Cntnr other; + m_r_container.split(*mid_it, other); + m_r_container.join(other); + } + } + + private: + Cntnr& m_r_container; + }; + + template + class split_join_functor + { + public: + split_join_functor(Cntnr& r_container) : m_r_container(r_container) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + typename Cntnr::iterator mid_it = m_r_container.begin(); + std::advance(mid_it, m_r_container.size() / 2); + + Cntnr other(mid_it, m_r_container.end()); + m_r_container.erase(mid_it, m_r_container.end()); + + m_r_container.insert(other.begin(), other.end()); + other.clear(); + } + } + + private: + Cntnr& m_r_container; + }; + } // namespace detail + + template + class tree_split_join_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + tree_split_join_test(size_t vn, size_t vs, size_t vm); + + template + void + operator()(Cntnr); + + private: + tree_split_join_test(const tree_split_join_test& ); + + private: + const size_t m_vn; + const size_t m_vs; + const size_t m_vm; + }; + + template + tree_split_join_test:: + tree_split_join_test(size_t vn, size_t vs, size_t vm) : + m_vn(vn), + m_vs(vs), + m_vm(vm) + { } + + template + template + void + tree_split_join_test:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form::name(), + string_form::desc()); + + for (size_t v = m_vn; v < m_vm; v += m_vs) + { + Cntnr cntnr; + for (size_t ins = 0; ins < v; ++ ins) + cntnr.insert((typename Cntnr::value_type)ins); + + __gnu_pbds::test::detail::split_join_functor + fn(cntnr); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + res_set_fmt.add_res(v, res); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + -- cgit v1.2.3