libstdc++-v3/testsuite/util/performance/assoc/timing/tree_split_join_test.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2024 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 tree_split_join_test.hpp
  34  * Contains a test for splitting and joining trees
  35  */
  36
  37 #ifndef PB_DS_TREE_SPLIT_JOIN_TEST_HPP
  38 #define PB_DS_TREE_SPLIT_JOIN_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
  45 namespace __gnu_pbds
  46 {
  47   namespace test
  48   {
  49     namespace detail
  50     {
  51       template<typename Cntnr, bool Support_Split_Join>
  52       class split_join_functor
  53       {
  54       public:
  55         split_join_functor(Cntnr& r_container) : m_r_container(r_container)
  56         { }
  57
  58         void
  59         operator()(std::size_t resolution)
  60         {
  61           for (std::size_t i = 0; i < resolution; ++i)
  62             {
  63               typename Cntnr::const_iterator mid_it = m_r_container.begin();
  64               std::advance(mid_it, m_r_container.size() / 2);
  65               Cntnr other;
  66               m_r_container.split(*mid_it, other);
  67               m_r_container.join(other);
  68             }
  69         }
  70
  71       private:
  72         Cntnr& m_r_container;
  73       };
  74
  75       template<typename Cntnr>
  76       class split_join_functor<Cntnr, false>
  77       {
  78       public:
  79         split_join_functor(Cntnr& r_container) : m_r_container(r_container)
  80         { }
  81
  82         void
  83         operator()(std::size_t resolution)
  84         {
  85           for (std::size_t i = 0; i < resolution; ++i)
  86             {
  87               typename Cntnr::iterator mid_it = m_r_container.begin();
  88               std::advance(mid_it, m_r_container.size() / 2);
  89
  90               Cntnr other(mid_it, m_r_container.end());
  91               m_r_container.erase(mid_it, m_r_container.end());
  92
  93               m_r_container.insert(other.begin(), other.end());
  94               other.clear();
  95             }
  96         }
  97
  98       private:
  99         Cntnr& m_r_container;
 100       };
 101     } // namespace detail
 102
 103     template<bool Support_Split_Join>
 104     class tree_split_join_test : private __gnu_pbds::test::detail::timing_test_base
 105     {
 106     public:
 107       tree_split_join_test(size_t vn, size_t vs, size_t vm);
 108
 109       template<typename Cntnr>
 110       void
 111       operator()(Cntnr);
 112
 113     private:
 114       tree_split_join_test(const tree_split_join_test& );
 115
 116     private:
 117       const size_t m_vn;
 118       const size_t m_vs;
 119       const size_t m_vm;
 120     };
 121
 122     template<bool Support_Split_Join>
 123     tree_split_join_test<Support_Split_Join>::
 124     tree_split_join_test(size_t vn, size_t vs, size_t vm) :
 125       m_vn(vn),
 126       m_vs(vs),
 127       m_vm(vm)
 128     { }
 129
 130     template<bool Support_Split_Join>
 131     template<typename Cntnr>
 132     void
 133     tree_split_join_test<Support_Split_Join>::
 134     operator()(Cntnr)
 135     {
 136       typedef xml_result_set_performance_formatter formatter_type;
 137       formatter_type res_set_fmt(string_form<Cntnr>::name(),
 138                                  string_form<Cntnr>::desc());
 139
 140       for (size_t v = m_vn; v < m_vm; v += m_vs)
 141         {
 142           Cntnr cntnr;
 143           for (size_t ins = 0; ins < v; ++ ins)
 144             cntnr.insert((typename Cntnr::value_type)ins);
 145
 146           __gnu_pbds::test::detail::split_join_functor<Cntnr, Support_Split_Join>
 147             fn(cntnr);
 148
 149           const double res =
 150             __gnu_pbds::test::detail::timing_test_base::operator()(fn);
 151           res_set_fmt.add_res(v, res);
 152         }
 153     }
 154   } // namespace test
 155 } // namespace __gnu_pbds
 156
 157 #endif
 158