libstdc++
profiler_algos.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 //
00003 // Copyright (C) 2010 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 //
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License along
00021 // with this library; see the file COPYING3.  If not see
00022 // <http://www.gnu.org/licenses/>.
00023 
00024 /** @file profile/impl/profiler_algos.h
00025  *  @brief Algorithms used by the profile extension.
00026  *
00027  *  This file is needed to avoid including <algorithm> or <bits/stl_algo.h>.
00028  *  Including those files would result in recursive includes.
00029  *  These implementations are oversimplified.  In general, efficiency may be
00030  *  sacrificed to minimize maintenance overhead.
00031  */
00032 
00033 #ifndef _GLIBCXX_PROFILE_PROFILER_ALGOS_H
00034 #define _GLIBCXX_PROFILE_PROFILER_ALGOS_H 1
00035 
00036 namespace __gnu_profile
00037 {
00038   /* Helper for __top_n.  Insert in sorted vector, but not beyond Nth elem.  */
00039   template<typename _Container>
00040     void
00041     __insert_top_n(_Container& __output,
00042            const typename _Container::value_type& __value,
00043            typename _Container::size_type __n)
00044     {
00045       typename _Container::iterator __it = __output.begin();
00046       typename _Container::size_type __count = 0;
00047 
00048       // Skip up to N - 1 elements larger than VALUE.
00049       // XXX: Could do binary search for random iterators.
00050       while (true)
00051     {
00052       if (__count >= __n)
00053         // VALUE is not in top N.
00054         return;
00055 
00056       if (__it == __output.end())
00057         break;
00058 
00059       if (*__it < __value)
00060         break;
00061 
00062       ++__it;
00063       ++__count;
00064     }
00065 
00066       __output.insert(__it, __value);
00067     }
00068 
00069   /* Copy the top N elements in INPUT, sorted in reverse order, to OUTPUT.  */
00070   template<typename _Container>
00071     void
00072     __top_n(const _Container& __input, _Container& __output,
00073         typename _Container::size_type __n)
00074     {
00075       __output.clear();
00076       typename _Container::const_iterator __it;
00077       for (__it = __input.begin(); __it != __input.end(); ++__it)
00078     __insert_top_n(__output, *__it, __n);
00079     }
00080 
00081   /* Simplified clone of std::for_each.  */
00082   template<typename _InputIterator, typename _Function>
00083     _Function 
00084     __for_each(_InputIterator __first, _InputIterator __last, _Function __f)
00085     {
00086       for (; __first != __last; ++__first)
00087     __f(*__first);
00088       return __f;
00089     }
00090 
00091   /* Simplified clone of std::remove.  */
00092   template<typename _ForwardIterator, typename _Tp>
00093     _ForwardIterator
00094     __remove(_ForwardIterator __first, _ForwardIterator __last,
00095          const _Tp& __value)
00096     {
00097       if(__first == __last)
00098     return __first;
00099       _ForwardIterator __result = __first;
00100       ++__first;
00101       for(; __first != __last; ++__first)
00102     if(!(*__first == __value))
00103       {
00104         *__result = *__first;
00105         ++__result;
00106       }
00107       return __result;
00108     }
00109 } // namespace __gnu_profile
00110 
00111 #endif /* _GLIBCXX_PROFILE_PROFILER_ALGOS_H */