// -*- C++ -*- // // Copyright (C) 2010 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. /** @file profile/impl/profiler_algos.h * @brief Algorithms used by the profile extension. * * This file is needed to avoid including <algorithm> or <bits/stl_algo.h>. * Including those files would result in recursive includes. * These implementations are oversimplified. In general, efficiency may be * sacrificed to minimize maintenance overhead. */ #ifndef _GLIBCXX_PROFILE_PROFILER_ALGOS_H #define _GLIBCXX_PROFILE_PROFILER_ALGOS_H 1 namespace __gnu_profile { /* Helper for __top_n. Insert in sorted vector, but not beyond Nth elem. */ template<typename _Container> void __insert_top_n(_Container& __output, const typename _Container::value_type& __value, typename _Container::size_type __n) { typename _Container::iterator __it = __output.begin(); typename _Container::size_type __count = 0; // Skip up to N - 1 elements larger than VALUE. // XXX: Could do binary search for random iterators. while (true) { if (__count >= __n) // VALUE is not in top N. return; if (__it == __output.end()) break; if (*__it < __value) break; ++__it; ++__count; } __output.insert(__it, __value); } /* Copy the top N elements in INPUT, sorted in reverse order, to OUTPUT. */ template<typename _Container> void __top_n(const _Container& __input, _Container& __output, typename _Container::size_type __n) { __output.clear(); typename _Container::const_iterator __it; for (__it = __input.begin(); __it != __input.end(); ++__it) __insert_top_n(__output, *__it, __n); } /* Simplified clone of std::for_each. */ template<typename _InputIterator, typename _Function> _Function __for_each(_InputIterator __first, _InputIterator __last, _Function __f) { for (; __first != __last; ++__first) __f(*__first); return __f; } /* Simplified clone of std::remove. */ template<typename _ForwardIterator, typename _Tp> _ForwardIterator __remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { if(__first == __last) return __first; _ForwardIterator __result = __first; ++__first; for(; __first != __last; ++__first) if(!(*__first == __value)) { *__result = *__first; ++__result; } return __result; } } // namespace __gnu_profile #endif /* _GLIBCXX_PROFILE_PROFILER_ALGOS_H */