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 terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 2, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License
00017 // along with this library; see the file COPYING.  If not, write to
00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
00019 // MA 02111-1307, USA.
00020 
00021 // As a special exception, you may use this file as part of a free
00022 // software library without restriction.  Specifically, if other files
00023 // instantiate templates or use macros or inline functions from this
00024 // file, or you compile this file and link it with other files to
00025 // produce an executable, this file does not by itself cause the
00026 // resulting executable to be covered by the GNU General Public
00027 // License.  This exception does not however invalidate any other
00028 // reasons why the executable file might be covered by the GNU General
00029 // Public License.
00030 
00031 /** @file profile/impl/profiler_algos.h
00032  *  @brief Algorithms used by the profile extension.
00033  *
00034  *  This file is needed to avoid including <algorithm> or <bits/stl_algo.h>.
00035  *  Including those files would result in recursive includes.
00036  *  These implementations are oversimplified.  In general, efficiency may be
00037  *  sacrificed to minimize maintenance overhead.
00038  */
00039 
00040 #ifndef _GLIBCXX_PROFILE_PROFILER_ALGOS_H
00041 #define _GLIBCXX_PROFILE_PROFILER_ALGOS_H 1
00042 
00043 namespace __gnu_profile
00044 {
00045   /* Helper for __top_n.  Insert in sorted vector, but not beyond Nth elem.  */
00046   template<typename _Container>
00047     void
00048     __insert_top_n(_Container& __output,
00049            const typename _Container::value_type& __value,
00050            typename _Container::size_type __n)
00051     {
00052       typename _Container::iterator __it = __output.begin();
00053       typename _Container::size_type __count = 0;
00054 
00055       // Skip up to N - 1 elements larger than VALUE.
00056       // XXX: Could do binary search for random iterators.
00057       while (true)
00058     {
00059       if (__count >= __n)
00060         // VALUE is not in top N.
00061         return;
00062 
00063       if (__it == __output.end())
00064         break;
00065 
00066       if (*__it < __value)
00067         break;
00068 
00069       ++__it;
00070       ++__count;
00071     }
00072 
00073       __output.insert(__it, __value);
00074     }
00075 
00076   /* Copy the top N elements in INPUT, sorted in reverse order, to OUTPUT.  */
00077   template<typename _Container>
00078     void
00079     __top_n(const _Container& __input, _Container& __output,
00080         typename _Container::size_type __n)
00081     {
00082       __output.clear();
00083       typename _Container::const_iterator __it;
00084       for (__it = __input.begin(); __it != __input.end(); ++__it)
00085     __insert_top_n(__output, *__it, __n);
00086     }
00087 
00088   /* Simplified clone of std::for_each.  */
00089   template<typename _InputIterator, typename _Function>
00090     _Function 
00091     __for_each(_InputIterator __first, _InputIterator __last, _Function __f)
00092     {
00093       for (; __first != __last; ++__first)
00094     __f(*__first);
00095       return __f;
00096     }
00097 
00098   /* Simplified clone of std::remove.  */
00099   template<typename _ForwardIterator, typename _Tp>
00100     _ForwardIterator
00101     __remove(_ForwardIterator __first, _ForwardIterator __last,
00102          const _Tp& __value)
00103     {
00104       if(__first == __last)
00105     return __first;
00106       _ForwardIterator __result = __first;
00107       ++__first;
00108       for(; __first != __last; ++__first)
00109     if(!(*__first == __value))
00110       {
00111         *__result = *__first;
00112         ++__result;
00113       }
00114       return __result;
00115     }
00116 } // namespace __gnu_profile
00117 
00118 #endif /* _GLIBCXX_PROFILE_PROFILER_ALGOS_H */