xref: /dflybsd-src/contrib/gcc-4.7/libstdc++-v3/include/profile/impl/profiler_algos.h (revision 04febcfb30580676d3e95f58a16c5137ee478b32)
1*e4b17023SJohn Marino // -*- C++ -*-
2*e4b17023SJohn Marino //
3*e4b17023SJohn Marino // Copyright (C) 2010 Free Software Foundation, Inc.
4*e4b17023SJohn Marino //
5*e4b17023SJohn Marino // This file is part of the GNU ISO C++ Library.  This library is free
6*e4b17023SJohn Marino // software; you can redistribute it and/or modify it under the
7*e4b17023SJohn Marino // terms of the GNU General Public License as published by the
8*e4b17023SJohn Marino // Free Software Foundation; either version 3, or (at your option)
9*e4b17023SJohn Marino // any later version.
10*e4b17023SJohn Marino //
11*e4b17023SJohn Marino // This library is distributed in the hope that it will be useful,
12*e4b17023SJohn Marino // but WITHOUT ANY WARRANTY; without even the implied warranty of
13*e4b17023SJohn Marino // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14*e4b17023SJohn Marino // GNU General Public License for more details.
15*e4b17023SJohn Marino 
16*e4b17023SJohn Marino // Under Section 7 of GPL version 3, you are granted additional
17*e4b17023SJohn Marino // permissions described in the GCC Runtime Library Exception, version
18*e4b17023SJohn Marino // 3.1, as published by the Free Software Foundation.
19*e4b17023SJohn Marino 
20*e4b17023SJohn Marino // You should have received a copy of the GNU General Public License along
21*e4b17023SJohn Marino // with this library; see the file COPYING3.  If not see
22*e4b17023SJohn Marino // <http://www.gnu.org/licenses/>.
23*e4b17023SJohn Marino 
24*e4b17023SJohn Marino /** @file profile/impl/profiler_algos.h
25*e4b17023SJohn Marino  *  @brief Algorithms used by the profile extension.
26*e4b17023SJohn Marino  *
27*e4b17023SJohn Marino  *  This file is needed to avoid including <algorithm> or <bits/stl_algo.h>.
28*e4b17023SJohn Marino  *  Including those files would result in recursive includes.
29*e4b17023SJohn Marino  *  These implementations are oversimplified.  In general, efficiency may be
30*e4b17023SJohn Marino  *  sacrificed to minimize maintenance overhead.
31*e4b17023SJohn Marino  */
32*e4b17023SJohn Marino 
33*e4b17023SJohn Marino #ifndef _GLIBCXX_PROFILE_PROFILER_ALGOS_H
34*e4b17023SJohn Marino #define _GLIBCXX_PROFILE_PROFILER_ALGOS_H 1
35*e4b17023SJohn Marino 
36*e4b17023SJohn Marino namespace __gnu_profile
37*e4b17023SJohn Marino {
38*e4b17023SJohn Marino   /* Helper for __top_n.  Insert in sorted vector, but not beyond Nth elem.  */
39*e4b17023SJohn Marino   template<typename _Container>
40*e4b17023SJohn Marino     void
__insert_top_n(_Container & __output,const typename _Container::value_type & __value,typename _Container::size_type __n)41*e4b17023SJohn Marino     __insert_top_n(_Container& __output,
42*e4b17023SJohn Marino 		   const typename _Container::value_type& __value,
43*e4b17023SJohn Marino 		   typename _Container::size_type __n)
44*e4b17023SJohn Marino     {
45*e4b17023SJohn Marino       typename _Container::iterator __it = __output.begin();
46*e4b17023SJohn Marino       typename _Container::size_type __count = 0;
47*e4b17023SJohn Marino 
48*e4b17023SJohn Marino       // Skip up to N - 1 elements larger than VALUE.
49*e4b17023SJohn Marino       // XXX: Could do binary search for random iterators.
50*e4b17023SJohn Marino       while (true)
51*e4b17023SJohn Marino 	{
52*e4b17023SJohn Marino 	  if (__count >= __n)
53*e4b17023SJohn Marino 	    // VALUE is not in top N.
54*e4b17023SJohn Marino 	    return;
55*e4b17023SJohn Marino 
56*e4b17023SJohn Marino 	  if (__it == __output.end())
57*e4b17023SJohn Marino 	    break;
58*e4b17023SJohn Marino 
59*e4b17023SJohn Marino 	  if (*__it < __value)
60*e4b17023SJohn Marino 	    break;
61*e4b17023SJohn Marino 
62*e4b17023SJohn Marino 	  ++__it;
63*e4b17023SJohn Marino 	  ++__count;
64*e4b17023SJohn Marino 	}
65*e4b17023SJohn Marino 
66*e4b17023SJohn Marino       __output.insert(__it, __value);
67*e4b17023SJohn Marino     }
68*e4b17023SJohn Marino 
69*e4b17023SJohn Marino   /* Copy the top N elements in INPUT, sorted in reverse order, to OUTPUT.  */
70*e4b17023SJohn Marino   template<typename _Container>
71*e4b17023SJohn Marino     void
__top_n(const _Container & __input,_Container & __output,typename _Container::size_type __n)72*e4b17023SJohn Marino     __top_n(const _Container& __input, _Container& __output,
73*e4b17023SJohn Marino 	    typename _Container::size_type __n)
74*e4b17023SJohn Marino     {
75*e4b17023SJohn Marino       __output.clear();
76*e4b17023SJohn Marino       typename _Container::const_iterator __it;
77*e4b17023SJohn Marino       for (__it = __input.begin(); __it != __input.end(); ++__it)
78*e4b17023SJohn Marino 	__insert_top_n(__output, *__it, __n);
79*e4b17023SJohn Marino     }
80*e4b17023SJohn Marino 
81*e4b17023SJohn Marino   /* Simplified clone of std::for_each.  */
82*e4b17023SJohn Marino   template<typename _InputIterator, typename _Function>
83*e4b17023SJohn Marino     _Function
__for_each(_InputIterator __first,_InputIterator __last,_Function __f)84*e4b17023SJohn Marino     __for_each(_InputIterator __first, _InputIterator __last, _Function __f)
85*e4b17023SJohn Marino     {
86*e4b17023SJohn Marino       for (; __first != __last; ++__first)
87*e4b17023SJohn Marino 	__f(*__first);
88*e4b17023SJohn Marino       return __f;
89*e4b17023SJohn Marino     }
90*e4b17023SJohn Marino 
91*e4b17023SJohn Marino   /* Simplified clone of std::remove.  */
92*e4b17023SJohn Marino   template<typename _ForwardIterator, typename _Tp>
93*e4b17023SJohn Marino     _ForwardIterator
__remove(_ForwardIterator __first,_ForwardIterator __last,const _Tp & __value)94*e4b17023SJohn Marino     __remove(_ForwardIterator __first, _ForwardIterator __last,
95*e4b17023SJohn Marino 	     const _Tp& __value)
96*e4b17023SJohn Marino     {
97*e4b17023SJohn Marino       if(__first == __last)
98*e4b17023SJohn Marino 	return __first;
99*e4b17023SJohn Marino       _ForwardIterator __result = __first;
100*e4b17023SJohn Marino       ++__first;
101*e4b17023SJohn Marino       for(; __first != __last; ++__first)
102*e4b17023SJohn Marino 	if(!(*__first == __value))
103*e4b17023SJohn Marino 	  {
104*e4b17023SJohn Marino 	    *__result = *__first;
105*e4b17023SJohn Marino 	    ++__result;
106*e4b17023SJohn Marino 	  }
107*e4b17023SJohn Marino       return __result;
108*e4b17023SJohn Marino     }
109*e4b17023SJohn Marino } // namespace __gnu_profile
110*e4b17023SJohn Marino 
111*e4b17023SJohn Marino #endif /* _GLIBCXX_PROFILE_PROFILER_ALGOS_H */
112