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