Home | History | Annotate | Download | only in impl 
      1 // -*- C++ -*-
      2 //
      3 // Copyright (C) 2010-2013 Free Software Foundation, Inc.
      4 //
      5 // This file is part of the GNU ISO C++ Library.  This library is free
      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.
     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 
     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/>.
     23 
     24 /** @file profile/impl/profiler_algos.h
     25  *  @brief Algorithms used by the profile extension.
     26  *
     27  *  This file is needed to avoid including \<algorithm\> or \<bits/stl_algo.h\>.
     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 */
    112