1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the terms 7// of the GNU General Public License as published by the Free Software 8// Foundation; either version 3, or (at your option) any later 9// version. 10 11// This library is distributed in the hope that it will be useful, but 12// WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14// General Public License for more details. 15 16// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING3. If not see 18// <http://www.gnu.org/licenses/>. 19 20 21// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 22 23// Permission to use, copy, modify, sell, and distribute this software 24// is hereby granted without fee, provided that the above copyright 25// notice appears in all copies, and that both that copyright notice 26// and this permission notice appear in supporting documentation. None 27// of the above authors, nor IBM Haifa Research Laboratories, make any 28// representation about the suitability of this software for any 29// purpose. It is provided "as is" without express or implied 30// warranty. 31 32/** 33 * @file find_test.hpp 34 * Contains a generic find test. 35 */ 36 37#ifndef PB_DS_FIND_TEST_HPP 38#define PB_DS_FIND_TEST_HPP 39 40#include <performance/time/timing_test_base.hpp> 41#include <performance/io/xml_formatter.hpp> 42#include <common_type/assoc/string_form.hpp> 43#include <iterator> 44 45namespace __gnu_pbds 46{ 47 namespace test 48 { 49 namespace detail 50 { 51 template<typename It, class Cntnr, bool LOR> 52 class find_find_functor 53 { 54 public: 55 find_find_functor(Cntnr& contnr, It fnd_it_b, It fnd_it_e) 56 : m_contnr(contnr), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) 57 { } 58 59 void 60 operator()(std::size_t resolution) 61 { 62 for (std::size_t i = 0; i < resolution; ++i) 63 { 64 It fnd_it = m_fnd_it_b; 65 while (fnd_it != m_fnd_it_e) 66 ++m_contnr.find((fnd_it++)->first)->second; 67 } 68 } 69 70 private: 71 Cntnr& m_contnr; 72 const It m_fnd_it_b; 73 const It m_fnd_it_e; 74 }; 75 76 template<typename It, class Cntnr> 77 class find_find_functor<It, Cntnr, true> 78 { 79 public: 80 find_find_functor(Cntnr& contnr, It fnd_it_b, It fnd_it_e) 81 : m_contnr(contnr), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) 82 { } 83 84 void 85 operator()(std::size_t resolution) 86 { 87 It fnd_it = m_fnd_it_b; 88 while (fnd_it != m_fnd_it_e) 89 { 90 for (std::size_t i = 0; i < resolution; ++i) 91 ++m_contnr.find(fnd_it->first)->second; 92 ++fnd_it; 93 } 94 } 95 96 private: 97 Cntnr& m_contnr; 98 const It m_fnd_it_b; 99 const It m_fnd_it_e; 100 }; 101 } // namespace detail 102 103 template<typename It, bool LOR = false> 104 class find_test : private __gnu_pbds::test::detail::timing_test_base 105 { 106 public: 107 find_test(It ins_b, It fnd_it_b, size_t ins_vn, size_t ins_vs, 108 size_t ins_vm, size_t fnd_vn, size_t fnd_vs, size_t fnd_vm): 109 m_ins_b(ins_b), m_fnd_it_b(fnd_it_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), 110 m_ins_vm(ins_vm), m_fnd_vn(fnd_vn), m_fnd_vs(fnd_vs), m_fnd_vm(fnd_vm) 111 { } 112 113 template<typename Cntnr> 114 void 115 operator()(Cntnr); 116 117 private: 118 find_test(const find_test& ); 119 120 private: 121 const It m_ins_b; 122 const It m_fnd_it_b; 123 const size_t m_ins_vn; 124 const size_t m_ins_vs; 125 const size_t m_ins_vm; 126 const size_t m_fnd_vn; 127 const size_t m_fnd_vs; 128 const size_t m_fnd_vm; 129 }; 130 131 template<typename It, bool LOR> 132 template<typename Cntnr> 133 void 134 find_test<It, LOR>:: 135 operator()(Cntnr) 136 { 137 typedef string_form<Cntnr> sform_type; 138 typedef xml_result_set_performance_formatter formatter_type; 139 formatter_type res_set_fmt(sform_type::name(), sform_type::desc()); 140 141 for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) 142 { 143 const size_t v = m_ins_vn + i * m_ins_vs; 144 const size_t fnd_size = m_fnd_vn + i * m_fnd_vs; 145 It ins_it_b = m_ins_b; 146 It ins_it_e = m_ins_b; 147 std::advance(ins_it_e, v); 148 149 Cntnr test_container(ins_it_b, ins_it_e); 150 It fnd_it_b = m_fnd_it_b; 151 It fnd_it_e = m_fnd_it_b; 152 std::advance(fnd_it_e, fnd_size); 153 154 __gnu_pbds::test::detail::find_find_functor<It, Cntnr, LOR> 155 fn(test_container, fnd_it_b, fnd_it_e); 156 157 const double res = 158 __gnu_pbds::test::detail::timing_test_base::operator()(fn); 159 res_set_fmt.add_res(v, res / fnd_size); 160 } 161 } 162 } // namespace test 163} // namespace __gnu_pbds 164 165#endif 166 167