This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: PATCH: profile mode fix for threads on solaris and cleanup
- From: Silvius Rus <rus at google dot com>
- To: gcc-patches at gcc dot gnu dot org, Paolo Carlini <paolo dot carlini at oracle dot com>
- Cc: "libstdc++" <libstdc++ at gcc dot gnu dot org>
- Date: Mon, 10 May 2010 15:46:28 -0700
- Subject: Re: PATCH: profile mode fix for threads on solaris and cleanup
- References: <t2ke90dbffc1005101532ha23d8972z93ab4cbcce9c0b46@mail.gmail.com>
On Mon, May 10, 2010 at 3:32 PM, Silvius Rus <rus@google.com> wrote:
> Could you please review the attached trunk patch.
Attached.
Silvius
Index: include/Makefile.in
===================================================================
--- include/Makefile.in (revision 159238)
+++ include/Makefile.in (working copy)
@@ -1032,6 +1032,7 @@
profile_impl_builddir = ./profile/impl
profile_impl_headers = \
${profile_impl_srcdir}/profiler.h \
+ ${profile_impl_srcdir}/profiler_algos.h \
${profile_impl_srcdir}/profiler_container_size.h \
${profile_impl_srcdir}/profiler_hash_func.h \
${profile_impl_srcdir}/profiler_hashtable_size.h \
Index: include/profile/impl/profiler_trace.h
===================================================================
--- include/profile/impl/profiler_trace.h (revision 159238)
+++ include/profile/impl/profiler_trace.h (working copy)
@@ -53,43 +53,32 @@
#define _GLIBCXX_IMPL_UNORDERED_MAP std::tr1::unordered_map
#endif
+#include <bits/stl_algobase.h>
+#include <ext/concurrence.h>
#include <fstream>
#include <string>
#include <utility>
-#include <bits/stl_heap.h> // for std::make_heap, std::sort_heap
+#include <vector>
-#if (defined _GLIBCXX_PROFILE_THREADS) && !(defined _GLIBCXX_HAVE_TLS)
-#error You do not seem to have TLS support, which is required by the profile \
- mode. If your program is not multithreaded, recompile with \
- -D_GLIBCXX_PROFILE_NO_THREADS
-#endif
-
-#if defined _GLIBCXX_PROFILE_THREADS && defined _GLIBCXX_HAVE_TLS
-#include <pthread.h>
-#endif
-
+#include "profile/impl/profiler_algos.h"
#include "profile/impl/profiler_state.h"
#include "profile/impl/profiler_node.h"
namespace __gnu_profile
{
+/** @brief Internal environment. Values can be set one of two ways:
+ 1. In config file "var = value". The default config file path is
+ libstdcxx-profile.conf.
+ 2. By setting process environment variables. For instance, in a Bash
+ shell you can set the unit cost of iterating through a map like this:
+ export __map_iterate_cost_factor=5.0.
+ If a value is set both in the input file and through an environment
+ variable, the environment value takes precedence. */
+typedef _GLIBCXX_IMPL_UNORDERED_MAP<std::string, std::string> __env_t;
+_GLIBCXX_PROFILE_DEFINE_UNINIT_DATA(__env_t, __env);
-#if defined _GLIBCXX_PROFILE_THREADS && defined _GLIBCXX_HAVE_TLS
-#define _GLIBCXX_IMPL_MUTEX_INITIALIZER PTHREAD_MUTEX_INITIALIZER
-typedef pthread_mutex_t __mutex_t;
-/** @brief Pthread mutex wrapper. */
-_GLIBCXX_PROFILE_DEFINE_DATA(__mutex_t, __global_lock,
- PTHREAD_MUTEX_INITIALIZER);
-inline void __lock(__mutex_t& __m) { pthread_mutex_lock(&__m); }
-inline void __unlock(__mutex_t& __m) { pthread_mutex_unlock(&__m); }
-#else
-typedef int __mutex_t;
-/** @brief Mock mutex interface. */
-#define _GLIBCXX_IMPL_MUTEX_INITIALIZER 0
-_GLIBCXX_PROFILE_DEFINE_DATA(__mutex_t, __global_lock, 0);
-inline void __lock(__mutex_t& __m) {}
-inline void __unlock(__mutex_t& __m) {}
-#endif
+/** @brief Master lock. */
+_GLIBCXX_PROFILE_DEFINE_UNINIT_DATA(__gnu_cxx::__mutex, __global_lock);
/** @brief Representation of a warning. */
struct __warning_data
@@ -98,19 +87,15 @@
__stack_t __context;
const char* __warning_id;
const char* __warning_message;
-
__warning_data()
- : __magnitude(0.0), __context(NULL), __warning_id(NULL),
- __warning_message(NULL) { }
-
+ : __magnitude(0.0), __context(NULL), __warning_id(NULL),
+ __warning_message(NULL) { }
__warning_data(float __m, __stack_t __c, const char* __id,
const char* __msg)
- : __magnitude(__m), __context(__c), __warning_id(__id),
- __warning_message(__msg) { }
-
- bool
- operator>(const struct __warning_data& __other) const
- { return __magnitude > __other.__magnitude; }
+ : __magnitude(__m), __context(__c), __warning_id(__id),
+ __warning_message(__msg) { }
+ bool operator<(const struct __warning_data& __other) const
+ { return __magnitude < __other.__magnitude; }
};
typedef std::_GLIBCXX_STD_PR::vector<__warning_data> __warning_vector_t;
@@ -228,14 +213,9 @@
void __write(FILE* f);
void __collect_warnings(__warning_vector_t& __warnings);
- void __lock_object_table();
- void __lock_stack_table();
- void __unlock_object_table();
- void __unlock_stack_table();
-
private:
- __mutex_t __object_table_lock;
- __mutex_t __stack_table_lock;
+ __gnu_cxx::__mutex __object_table_lock;
+ __gnu_cxx::__mutex __stack_table_lock;
typedef _GLIBCXX_IMPL_UNORDERED_MAP<__object_t,
__object_info> __object_table_t;
typedef _GLIBCXX_IMPL_UNORDERED_MAP<__stack_t, __stack_info, __stack_hash,
@@ -263,30 +243,6 @@
}
template <typename __object_info, typename __stack_info>
-void __trace_base<__object_info, __stack_info>::__lock_object_table()
-{
- __lock(this->__object_table_lock);
-}
-
-template <typename __object_info, typename __stack_info>
-void __trace_base<__object_info, __stack_info>::__lock_stack_table()
-{
- __lock(this->__stack_table_lock);
-}
-
-template <typename __object_info, typename __stack_info>
-void __trace_base<__object_info, __stack_info>::__unlock_object_table()
-{
- __unlock(this->__object_table_lock);
-}
-
-template <typename __object_info, typename __stack_info>
-void __trace_base<__object_info, __stack_info>::__unlock_stack_table()
-{
- __unlock(this->__stack_table_lock);
-}
-
-template <typename __object_info, typename __stack_info>
__trace_base<__object_info, __stack_info>::__trace_base()
{
// Do not pick the initial size too large, as we don't know which diagnostics
@@ -295,7 +251,6 @@
__stack_table.rehash(10000);
__stack_table_byte_size = 0;
__id = NULL;
- __object_table_lock = __stack_table_lock = _GLIBCXX_IMPL_MUTEX_INITIALIZER;
}
template <typename __object_info, typename __stack_info>
@@ -304,10 +259,10 @@
{
if (__max_mem() == 0
|| __object_table.size() * sizeof(__object_info) <= __max_mem()) {
- __lock_object_table();
+ this->__object_table_lock.lock();
__object_table.insert(
typename __object_table_t::value_type(__object, __info));
- __unlock_object_table();
+ this->__object_table_lock.unlock();
}
}
@@ -318,14 +273,14 @@
// XXX: Revisit this to see if we can decrease mutex spans.
// Without this mutex, the object table could be rehashed during an
// insertion on another thread, which could result in a segfault.
- __lock_object_table();
+ this->__object_table_lock.lock();
typename __object_table_t::iterator __object_it =
__object_table.find(__object);
if (__object_it == __object_table.end()){
- __unlock_object_table();
+ this->__object_table_lock.unlock();
return NULL;
} else {
- __unlock_object_table();
+ this->__object_table_lock.unlock();
return &__object_it->second;
}
}
@@ -334,8 +289,8 @@
void __trace_base<__object_info, __stack_info>::__retire_object(
__object_t __object)
{
- __lock_object_table();
- __lock_stack_table();
+ this->__object_table_lock.lock();
+ this->__stack_table_lock.lock();
typename __object_table_t::iterator __object_it =
__object_table.find(__object);
if (__object_it != __object_table.end()){
@@ -358,8 +313,8 @@
}
__object_table.erase(__object);
}
- __unlock_stack_table();
- __unlock_object_table();
+ this->__object_table_lock.unlock();
+ this->__stack_table_lock.unlock();
}
template <typename __object_info, typename __stack_info>
@@ -442,6 +397,24 @@
}
}
+struct __warn
+{
+ FILE* __file;
+ __warn(FILE* __f) { __file = __f; }
+ void operator() (const __warning_data& __info)
+ {
+ fprintf(__file, __info.__warning_id);
+ fprintf(__file, ": improvement = %d",
+ __log_magnitude(__info.__magnitude));
+ fprintf(__file, ": call stack = ");
+ __gnu_profile::__write(__file, __info.__context);
+ fprintf(__file, ": advice = %s\n", __info.__warning_message);
+ free(
+ const_cast<void*>(
+ reinterpret_cast<const void*>(__info.__warning_message)));
+ }
+};
+
/** @brief Final report method, registered with @b atexit.
*
* This can also be called directly by user code, including signal handlers.
@@ -451,9 +424,9 @@
*/
inline void __report(void)
{
- __lock(_GLIBCXX_PROFILE_DATA(__global_lock));
+ _GLIBCXX_PROFILE_DATA(__global_lock).lock();
- __warning_vector_t __warnings;
+ __warning_vector_t __warnings, __top_warnings;
FILE* __raw_file = __open_output_file("raw");
__trace_vector_size_report(__raw_file, __warnings);
@@ -465,35 +438,17 @@
__trace_map_to_unordered_map_report(__raw_file, __warnings);
fclose(__raw_file);
- // Sort data by magnitude.
- // XXX: instead of sorting, should collect only top N for better performance.
+ // Sort data by magnitude, keeping just top N.
size_t __cutoff = __min(_GLIBCXX_PROFILE_DATA(_S_max_warn_count),
__warnings.size());
+ __top_n(__warnings, __top_warnings, __cutoff);
- std::make_heap(__warnings.begin(), __warnings.end(),
- std::greater<__warning_vector_t::value_type>());
- std::sort_heap(__warnings.begin(), __warnings.end(),
- std::greater<__warning_vector_t::value_type>());
- __warnings.resize(__cutoff);
-
FILE* __warn_file = __open_output_file("txt");
-
- for (__warning_vector_t::iterator __it = __warnings.begin();
- __it != __warnings.end(); ++__it)
- {
- fprintf(__warn_file, __it->__warning_id);
- fprintf(__warn_file, ": improvement = %d",
- __log_magnitude(__it->__magnitude));
- fprintf(__warn_file, ": call stack = ");
- __gnu_profile::__write(__warn_file, __it->__context);
- fprintf(__warn_file, ": advice = %s\n", __it->__warning_message);
- free(const_cast<void*>(reinterpret_cast<const void*>
- (__it->__warning_message)));
- }
-
+ __for_each(__top_warnings.begin(), __top_warnings.end(),
+ __warn(__warn_file));
fclose(__warn_file);
- __unlock(_GLIBCXX_PROFILE_DATA(__global_lock));
+ _GLIBCXX_PROFILE_DATA(__global_lock).unlock();
}
inline void __set_trace_path()
@@ -519,7 +474,8 @@
}
}
-inline void __read_cost_factors()
+inline void
+__read_cost_factors()
{
std::string __conf_file_name(_GLIBCXX_PROFILE_DATA(_S_trace_file_name));
__conf_file_name += ".conf";
@@ -534,48 +490,65 @@
{
std::string::size_type __i = __line.find_first_not_of(" \t\n\v");
- if (__line.length() <= 0 || __line[__i] == '#') {
- // Skip empty lines or comments.
- continue;
- }
+ if (__line.length() <= 0 || __line[__i] == '#')
+ {
+ // Skip empty lines or comments.
+ continue;
+ }
+ }
- // Trim.
- if (__line.begin() != __line.end())
- {
- // A simple remove operation.
- std::string::iterator __first = __line.begin();
- std::string::iterator __result = __first;
- ++__first;
- for(; __first != __line.end(); ++__first)
- if(!(*__first == ' '))
- {
- *__result = *__first;
- ++__result;
- }
- __line.erase(__result, __line.end());
- }
- std::string::size_type __pos = __line.find("=");
- std::string __factor_name = __line.substr(0, __pos);
- std::string::size_type __end = __line.find_first_of(";\n");
- std::string __factor_value = __line.substr(__pos + 1, __end - __pos);
+ // Trim.
+ __line.erase(__remove(__line.begin(), __line.end(), ' '), __line.end());
+ std::string::size_type __pos = __line.find("=");
+ std::string __factor_name = __line.substr(0, __pos);
+ std::string::size_type __end = __line.find_first_of(";\n");
+ std::string __factor_value = __line.substr(__pos + 1, __end - __pos);
- setenv(__factor_name.c_str(), __factor_value.c_str(), 0);
- }
+ _GLIBCXX_PROFILE_DATA(__env)[__factor_name] = __factor_value;
}
}
-inline void __write_cost_factors()
+struct __cost_factor_writer
{
- FILE* __file = __open_output_file("conf.out");
+ FILE* __file;
+ __cost_factor_writer(FILE* __f) : __file(__f) {}
+ void operator() (const __cost_factor* __factor)
+ {
+ fprintf(__file, "%s = %f\n", __factor->__env_var, __factor->__value);
+ }
+};
- for (__decltype(_GLIBCXX_PROFILE_DATA(__cost_factors)->begin()) __it
- = _GLIBCXX_PROFILE_DATA(__cost_factors)->begin();
- __it != _GLIBCXX_PROFILE_DATA(__cost_factors)->end(); ++__it)
- fprintf(__file, "%s = %f\n", (*__it)->__env_var, (*__it)->__value);
-
+inline void
+__write_cost_factors()
+{
+ FILE* __file = __open_output_file("conf.out");
+ __for_each(_GLIBCXX_PROFILE_DATA(__cost_factors)->begin(),
+ _GLIBCXX_PROFILE_DATA(__cost_factors)->end(),
+ __cost_factor_writer(__file));
fclose(__file);
}
+struct __cost_factor_setter
+{
+ void operator() (__cost_factor* __factor)
+ {
+ // Look it up in the process environment first.
+ const char* __env_value = getenv(__factor->__env_var);
+
+ if (!__env_value)
+ {
+ // Look it up in the config file.
+ __env_t::iterator it = _GLIBCXX_PROFILE_DATA(__env).find(
+ __factor->__env_var);
+ if (it != _GLIBCXX_PROFILE_DATA(__env).end())
+ __env_value = (*it).second.c_str();
+ }
+
+ if (__env_value)
+ __factor->__value = atof(__env_value);
+ }
+};
+
inline void __set_cost_factors()
{
_GLIBCXX_PROFILE_DATA(__cost_factors) = new __cost_factor_vector;
@@ -607,18 +580,14 @@
&_GLIBCXX_PROFILE_DATA(__umap_find_cost_factor));
_GLIBCXX_PROFILE_DATA(__cost_factors)->push_back(
&_GLIBCXX_PROFILE_DATA(__umap_iterate_cost_factor));
-
-
- for (__decltype(_GLIBCXX_PROFILE_DATA(__cost_factors)->begin()) __it
- = _GLIBCXX_PROFILE_DATA(__cost_factors)->begin();
- __it != _GLIBCXX_PROFILE_DATA(__cost_factors)->end(); ++__it)
- if (char* __env_cost_factor = getenv((*__it)->__env_var))
- (*__it)->__value = atof(__env_cost_factor);
+ __for_each(_GLIBCXX_PROFILE_DATA(__cost_factors)->begin(),
+ _GLIBCXX_PROFILE_DATA(__cost_factors)->end(),
+ __cost_factor_setter());
}
inline void __profcxx_init_unconditional()
{
- __lock(_GLIBCXX_PROFILE_DATA(__global_lock));
+ _GLIBCXX_PROFILE_DATA(__global_lock).lock();
if (__is_invalid()) {
@@ -652,7 +621,7 @@
}
}
- __unlock(_GLIBCXX_PROFILE_DATA(__global_lock));
+ _GLIBCXX_PROFILE_DATA(__global_lock).unlock();
}
/** @brief This function must be called by each instrumentation point.
Index: include/profile/impl/profiler.h
===================================================================
--- include/profile/impl/profiler.h (revision 159238)
+++ include/profile/impl/profiler.h (working copy)
@@ -44,6 +44,13 @@
#endif
// Mechanism to define data with inline linkage.
+#define _GLIBCXX_PROFILE_DEFINE_UNINIT_DATA(__type, __name) \
+ inline __type& \
+ __get_##__name() \
+ { \
+ static __type __name; \
+ return __name; \
+ }
#define _GLIBCXX_PROFILE_DEFINE_DATA(__type, __name, __initial_value...) \
inline __type& __get_##__name() { \
static __type __name(__initial_value); \
@@ -362,11 +369,6 @@
#define __profcxx_map_to_unordered_map_find(__x...)
#endif
-// Run multithreaded unless instructed not to do so.
-#ifndef _GLIBCXX_PROFILE_NO_THREADS
-#define _GLIBCXX_PROFILE_THREADS
-#endif
-
// Set default values for compile-time customizable variables.
#ifndef _GLIBCXX_PROFILE_TRACE_PATH_ROOT
#define _GLIBCXX_PROFILE_TRACE_PATH_ROOT "libstdcxx-profile"
@@ -389,7 +391,7 @@
"_GLIBCXX_PROFILE_MAX_STACK_DEPTH"
#endif
#ifndef _GLIBCXX_PROFILE_MEM_PER_DIAGNOSTIC
-#define _GLIBCXX_PROFILE_MEM_PER_DIAGNOSTIC 2 << 27
+#define _GLIBCXX_PROFILE_MEM_PER_DIAGNOSTIC (1 << 28)
#endif
#ifndef _GLIBCXX_PROFILE_MEM_PER_DIAGNOSTIC_ENV_VAR
#define _GLIBCXX_PROFILE_MEM_PER_DIAGNOSTIC_ENV_VAR \
Index: include/profile/impl/profiler_algos.h
===================================================================
--- include/profile/impl/profiler_algos.h (revision 0)
+++ include/profile/impl/profiler_algos.h (revision 0)
@@ -0,0 +1,128 @@
+// -*- 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.
+ * At least for now, <bits/stl_algobase.h> is included.
+ */
+
+#ifndef _GLIBCXX_PROFILE_PROFILER_ALGOS_H
+#define _GLIBCXX_PROFILE_PROFILER_ALGOS_H 1
+
+#include <bits/stl_algobase.h>
+#include <vector>
+
+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 */
Index: include/Makefile.am
===================================================================
--- include/Makefile.am (revision 159238)
+++ include/Makefile.am (working copy)
@@ -800,6 +800,7 @@
profile_impl_builddir = ./profile/impl
profile_impl_headers = \
${profile_impl_srcdir}/profiler.h \
+ ${profile_impl_srcdir}/profiler_algos.h \
${profile_impl_srcdir}/profiler_container_size.h \
${profile_impl_srcdir}/profiler_hash_func.h \
${profile_impl_srcdir}/profiler_hashtable_size.h \
Index: ChangeLog
===================================================================
--- ChangeLog (revision 159238)
+++ ChangeLog (working copy)
@@ -1,3 +1,20 @@
+2010-05-10 Silvius Rus <silvius.rus@gmail.com>
+
+ PR libstdc++/43259
+ * include/Makefile.am: Add profiler_algos.h.
+ * include/Makefile.in: Add profiler_algos.h.
+ * include/profile/impl/profiler_algos.h: New.
+ * testsuite/ext/profile/profiler_algos.cc: New.
+ * include/profile/impl/profiler.h: Add
+ (_GLIBCXX_PROFILE_DEFINE_UNINIT_DATA): Add.
+ * include/profile/impl/profiler_trace.h:
+ (__mutex_t, __lock, __unlock): Remove.
+ (__lock_object_table, __lock_stack_table): Remove. Replace uses with
+ calls to __gnu_cxx::__mutex::lock.
+ (__unlock_object_table, __unlock_stack_table): Remove. Replace uses
+ with calls to __gnu_cxx::__mutex::unlock.
+ (__warn, __cost_factor_writer, __cost_factor_setter): Add.
+
2010-05-07 Jonathan Wakely <jwakely.gcc@gmail.com>
* libsupc++/exception_ptr.h (make_exception_ptr): Add.
Index: testsuite/ext/profile/profiler_algos.cc
===================================================================
--- testsuite/ext/profile/profiler_algos.cc (revision 0)
+++ testsuite/ext/profile/profiler_algos.cc (revision 0)
@@ -0,0 +1,146 @@
+// { dg-options "-D_GLIBCXX_PROFILE" }
+
+// -*- C++ -*-
+
+// Unit tests for profile/impl/profile_algos.h.
+
+// 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include <profile/impl/profiler.h>
+
+using std::__norm::vector;
+
+enum Failure
+{
+ NO_FAILURES = 0x0,
+ INSERT_AFTER_N = 0x1,
+ INSERT_AT_HEAD = 0x2,
+ INSERT_AT_TAIL = 0x4,
+ INSERT_IN_THE_MIDDLE = 0x8,
+ TOP_N = 0x10,
+ FOR_EACH = 0x20,
+ REMOVE = 0x40
+};
+
+
+static int
+test_insert_top_n()
+{
+ vector<int> v;
+
+ for (int i = 0; i < 10; i++)
+ v.push_back(10 - i);
+
+ // Inserting -5 should have no effect if size is limited to 10.
+ __gnu_profile::__insert_top_n(v, -5, 10);
+ for (int i = 0; i < 10; i++)
+ if (v[i] != 10 - i)
+ return INSERT_AFTER_N;
+
+ // Insert at head.
+ __gnu_profile::__insert_top_n(v, 11, 10);
+ for (int i = 0; i < 11; i++)
+ if (v[i] != 11 - i)
+ return INSERT_AT_HEAD;
+
+ // Insert at end.
+ __gnu_profile::__insert_top_n(v, 0, 100);
+ for (int i = 0; i < 12; i++)
+ if (v[i] != 11 - i)
+ return INSERT_AT_TAIL;
+
+ // Insert in the middle.
+ __gnu_profile::__insert_top_n(v, 6, 11);
+ for (int i = 0; i < 6; i++)
+ if (v[i] != 11 - i)
+ return INSERT_IN_THE_MIDDLE;
+ for (int i = 6; i < 13; i++)
+ if (v[i] != 12 - i)
+ return INSERT_IN_THE_MIDDLE;
+
+ return NO_FAILURES;
+}
+
+static int
+test_top_n()
+{
+ vector<int> v, out;
+
+ for (int i = 0; i < 100; i++)
+ {
+ v.push_back(100 + i);
+ v.push_back(100 - i);
+ }
+
+ __gnu_profile::__top_n(v, out, 10);
+
+ for (int i = 0; i < 10; i++)
+ if (out[i] != 199 - i)
+ return TOP_N;
+
+ return NO_FAILURES;
+}
+
+struct test_for_each_helper
+{
+ static int sum;
+ void operator ()(int i) {
+ sum += i;
+ }
+};
+
+int test_for_each_helper::sum = 0;
+
+static int
+test_for_each()
+{
+ vector<int> v;
+ test_for_each_helper helper;
+ int checksum = 0;
+
+ for (int i = 0; i < 10; i++)
+ {
+ v.push_back(i);
+ checksum += i;
+ }
+
+ __gnu_profile::__for_each(v.begin(), v.end(), helper);
+
+ return helper.sum == checksum ? NO_FAILURES : FOR_EACH;
+}
+
+static int
+test_remove()
+{
+ vector<char> v;
+
+ for (int i = 0; i < 10; i++)
+ v.push_back(' ');
+ v.push_back('x');
+ for (int i = 0; i < 10; i++)
+ v.push_back(' ');
+ v.push_back('x');
+
+ return __gnu_profile::__remove(v.begin(), v.end(), ' ') == v.begin() + 2
+ ? NO_FAILURES : REMOVE;
+}
+
+int main() {
+ return test_insert_top_n() | test_top_n() | test_for_each() | test_remove();
+}