libstdc++
|
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 */