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