obtained gcc-4.6.4.tar.bz2 from upstream website;upstream

verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.

downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.

if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.

12 files changed, 1842 insertions, 0 deletions

diff --git a/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/erase_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/erase_test.hpp
new file mode 100644
index 000000000..6ad797a66
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/erase_test.hpp
@@ -0,0 +1,109 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file erase_test.hpp
+ * Contains a generic erase test.
+ */
+
+#ifndef PB_DS_ERASE_TEST_HPP
+#define PB_DS_ERASE_TEST_HPP
+
+#include <iterator>
+#include <testsuite_allocator.h>
+#include <ext/pb_ds/detail/type_utils.hpp>
+#include <performance/io/xml_formatter.hpp>
+#include <common_type/assoc/string_form.hpp>
+
+namespace __gnu_pbds
+{
+  namespace test
+  {
+    template<typename It>
+    class erase_test
+    {
+    public:
+      erase_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm)
+      :	m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+      { }
+
+      template<typename Cntnr>
+        void
+        operator()(Cntnr);
+
+    private:
+      erase_test(const erase_test&);
+
+      const It 		m_ins_b;
+      const size_t 	m_ins_vn;
+      const size_t 	m_ins_vs;
+      const size_t 	m_ins_vm;
+    };
+
+    template<typename It>
+    template<typename Cntnr>
+    void
+    erase_test<It>::
+    operator()(Cntnr)
+    {
+      typedef string_form<Cntnr> sform_type;
+      typedef xml_result_set_performance_formatter formatter_type;
+      formatter_type res_set_fmt(sform_type::name(), sform_type::desc());
+
+      for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
+	{
+	  const size_t ins_size = m_ins_vn + i * m_ins_vs;
+
+	  It ins_it_b = m_ins_b;
+	  It ins_it_e = m_ins_b;
+	  std::advance(ins_it_e, ins_size);
+
+	  typedef __gnu_test::tracker_allocator_counter counter_type;
+	  __gnu_test::tracker_allocator<char> alloc;
+	  const size_t init_mem = counter_type::get_allocation_count() 
+	                          - counter_type::get_deallocation_count();
+	  Cntnr cntnr(ins_it_b, ins_it_e);
+
+	  while (cntnr.size() > 1)
+            cntnr.erase(*cntnr.begin());
+
+	  const size_t final_mem = counter_type::get_allocation_count() 
+	                         - counter_type::get_deallocation_count();
+	  assert(final_mem > init_mem);
+	  const size_t delta_mem = final_mem - init_mem;
+	  res_set_fmt.add_res(ins_size, static_cast<double>(delta_mem));
+	}
+    }
+  } // namespace test
+} // namespace __gnu_pbds
+
+#endif
+
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/multimap_insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/multimap_insert_test.hpp
new file mode 100644
index 000000000..110dd923f
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/multimap_insert_test.hpp
@@ -0,0 +1,144 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file multimap_insert_test.hpp
+ * Contains a generic multimap_insert_test test.
+ */
+
+#ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP
+#define PB_DS_MULTIMAP_INSERT_TEST_HPP
+
+#include <iterator>
+#include <ext/pb_ds/detail/type_utils.hpp>
+#include <testsuite_allocator.h>
+#include <performance/io/xml_formatter.hpp>
+#include <common_type/assoc/string_form.hpp>
+
+namespace __gnu_pbds
+{
+  namespace test
+  {
+    template<typename It, bool Native>
+    class multimap_insert_test
+    {
+    public:
+      multimap_insert_test(It b, size_t ins_vn, size_t ins_vs, size_t ins_vm):
+      m_ins_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+      { }
+
+      template<typename Cntnr>
+      void
+      operator()(Cntnr);
+
+    private:
+      multimap_insert_test(const multimap_insert_test&);
+
+      template<typename Cntnr>
+      size_t
+      insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::true_type);
+
+      template<typename Cntnr>
+      size_t
+      insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::false_type);
+
+      const It m_ins_b;
+      const size_t m_ins_vn;
+      const size_t m_ins_vs;
+      const size_t m_ins_vm;
+    };
+
+    template<typename It, bool Native>
+    template<typename Cntnr>
+    void
+    multimap_insert_test<It, Native>::
+    operator()(Cntnr)
+    {
+      typedef xml_result_set_performance_formatter formatter_type;
+      formatter_type res_set_fmt(string_form<Cntnr>::name(),
+				 string_form<Cntnr>::desc());
+
+      for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
+	{
+	  const size_t ins_size = m_ins_vn + i * m_ins_vs;
+	  It ins_it_b = m_ins_b;
+	  It ins_it_e = m_ins_b;
+	  std::advance(ins_it_e, ins_size);
+
+	  const size_t delta_mem = insert(Cntnr(), ins_it_b, ins_it_e,
+					  __gnu_pbds::detail::integral_constant<int,Native>());
+
+	  res_set_fmt.add_res(ins_size, static_cast<double>(delta_mem));
+	}
+    }
+
+    template<typename It, bool Native>
+    template<typename Cntnr>
+    size_t
+    multimap_insert_test<It, Native>::
+    insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::true_type)
+    {
+      typedef __gnu_test::tracker_allocator_counter counter_type;
+      __gnu_test::tracker_allocator<char> alloc;
+      const size_t init_mem = counter_type::get_allocation_count() 
+	                      - counter_type::get_deallocation_count();
+      Cntnr cntnr;
+      for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
+        cntnr.insert((typename Cntnr::const_reference)(*ins_it));
+      const size_t final_mem = counter_type::get_allocation_count() 
+	                       - counter_type::get_deallocation_count();
+      assert(final_mem > init_mem);
+      return (final_mem - init_mem);
+    }
+
+    template<typename It, bool Native>
+    template<typename Cntnr>
+    size_t
+    multimap_insert_test<It, Native>::
+    insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::false_type)
+    {
+      typedef __gnu_test::tracker_allocator_counter counter_type;
+      __gnu_test::tracker_allocator<char> alloc;
+      const size_t init_mem = counter_type::get_allocation_count() 
+	                      - counter_type::get_deallocation_count();
+      Cntnr cntnr;
+      for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
+        cntnr[ins_it->first].insert(ins_it->second);
+      const size_t final_mem =  counter_type::get_allocation_count() 
+	                        - counter_type::get_deallocation_count();
+      assert(final_mem > init_mem);
+      return (final_mem - init_mem);
+    }
+  } // namespace test
+} // namespace __gnu_pbds
+
+#endif 
+
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/multimap_common_type.hpp b/libstdc++-v3/testsuite/util/performance/assoc/multimap_common_type.hpp
new file mode 100644
index 000000000..e31abe106
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/multimap_common_type.hpp
@@ -0,0 +1,223 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file multimap_common_type.hpp
+ * Contains types for a generic multimap_insert_test test.
+ */
+
+#ifndef PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP
+#define PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP
+
+#include <hash_fn/string_hash_fn.hpp>
+#include <common_type/assoc/common_type.hpp>
+
+namespace __gnu_pbds
+{
+  namespace test
+  {
+    namespace detail
+    {
+      struct int_hash : public std::unary_function<int, size_t>
+      {
+	inline size_t
+        operator()(const int i) const
+	{ return (static_cast<size_t>(i)); }
+      };
+
+      template<typename Key, typename Allocator = std::allocator<char> >
+      struct hash_set_tl_t
+      {
+	typedef
+        typename __gnu_pbds::test::hash_common_types<
+	  Key,
+	  __gnu_pbds::null_mapped_type,
+	  int_hash,
+	  std::equal_to<Key>,
+	  Allocator>::performance_min_tl
+        type;
+      };
+
+      template<typename Key, typename Allocator = std::allocator<char> >
+      struct lu_set_tl_t
+      {
+	typedef
+        typename __gnu_pbds::test::lu_common_types<
+	  Key,
+	  __gnu_pbds::null_mapped_type,
+	  std::equal_to<
+	  Key>,
+	  Allocator>::performance_min_tl
+        type;
+      };
+
+      template<typename Key,
+	       class Sec_Tl,
+	       typename Allocator = std::allocator<char> >
+      struct hash_mmap_tl_t
+      {
+      private:
+	typedef
+        typename __gnu_pbds::detail::__conditional_type<
+	__gnu_pbds::detail::is_same<
+	int,
+	Key>::value,
+	int_hash,
+	string_hash_fn>::__type
+        hash_fn_t;
+
+	template<typename Cntnr_T>
+	struct hash_mmap_transform
+	{
+	  typedef
+	  typename __gnu_pbds::test::hash_common_types<
+	    Key,
+	    Cntnr_T,
+	    hash_fn_t,
+	    std::equal_to<
+	    Key>,
+	    Allocator>::performance_min_tl
+	  type;
+	};
+
+      public:
+	typedef
+        typename __gnu_cxx::typelist::flatten<
+	typename __gnu_cxx::typelist::transform<
+	Sec_Tl,
+	hash_mmap_transform>::type>::type
+        type;
+      };
+
+      template<typename Key,
+	       class Sec_Tl,
+	       typename Allocator = std::allocator<char> >
+      struct tree_mmap_tl_t
+      {
+      private:
+	template<typename Cntnr_T>
+	struct tree_mmap_transform
+	{
+	  typedef
+	  typename __gnu_pbds::test::tree_common_types<
+	    Key,
+	    Cntnr_T,
+	    std::less<
+	    Key>,
+	    __gnu_pbds::null_tree_node_update,
+	    Allocator>::performance_min_tl
+	  type;
+	};
+
+      public:
+	typedef
+        typename __gnu_cxx::typelist::flatten<
+	typename __gnu_cxx::typelist::transform<
+	Sec_Tl,
+	tree_mmap_transform>::type>::type
+        type;
+      };
+
+      template<typename Key, typename Mapped, typename Allocator>
+      struct hash_hash_mmap_tl_t
+      {
+      private:
+	typedef typename hash_set_tl_t<Mapped, Allocator>::type sec_tl_t;
+
+      public:
+	typedef typename hash_mmap_tl_t<Key, sec_tl_t, Allocator>::type type;
+      };
+
+      template<typename Key, typename Mapped, typename Allocator>
+      struct tree_hash_mmap_tl_t
+      {
+      private:
+	typedef typename hash_set_tl_t<Mapped, Allocator>::type sec_tl_t;
+
+      public:
+	typedef typename tree_mmap_tl_t<Key, sec_tl_t, Allocator>::type type;
+      };
+
+      template<typename Key, typename Mapped, typename Allocator>
+      struct tree_lu_mmap_tl_t
+      {
+      private:
+	typedef typename lu_set_tl_t<Mapped, Allocator>::type sec_tl_t;
+
+      public:
+	typedef typename tree_mmap_tl_t<Key, sec_tl_t, Allocator>::type type;
+      };
+
+      template<typename Key, typename Mapped, typename Allocator>
+      struct hash_lu_mmap_tl_t
+      {
+      private:
+	typedef typename lu_set_tl_t<Mapped, Allocator>::type sec_tl_t;
+
+      public:
+	typedef typename hash_mmap_tl_t<Key, sec_tl_t, Allocator>::type type;
+      };
+    } // namespace detail
+
+    template<typename Key, typename Mapped, typename Allocator>
+    struct mmap_tl_t
+    {
+    private:
+      typedef
+      typename detail::hash_hash_mmap_tl_t<Key, Mapped, Allocator>::type
+      hh_mmap_tl_t;
+
+      typedef
+      typename detail::hash_lu_mmap_tl_t<Key, Mapped, Allocator>::type
+      hl_mmap_tl_t;
+
+      typedef
+      typename detail::tree_hash_mmap_tl_t<Key, Mapped, Allocator>::type
+      th_mmap_tl_t;
+
+      typedef
+      typename detail::tree_lu_mmap_tl_t<Key, Mapped, Allocator>::type
+      tl_mmap_tl_t;
+
+    public:
+      typedef
+      typename __gnu_cxx::typelist::append<hl_mmap_tl_t,
+      typename __gnu_cxx::typelist::append<hh_mmap_tl_t,
+      typename __gnu_cxx::typelist::append<th_mmap_tl_t,
+      tl_mmap_tl_t>::type>::type>::type
+      type;
+    };
+
+  } // namespace test
+} // namespace __gnu_pbds
+
+#endif
+
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/common_type.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/common_type.hpp
new file mode 100644
index 000000000..a553afeab
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/common_type.hpp
@@ -0,0 +1,103 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file common_type.hpp
+ * Contains types for a generic multimap_insert_test test.
+ */
+
+#ifndef PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP
+#define PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP
+
+#include <common_type/assoc/common_type.hpp>
+
+namespace __gnu_pbds
+{
+
+  namespace test
+  {
+
+    typedef
+    __gnu_pbds::test::hash_common_types<
+      int,
+      __gnu_pbds::null_mapped_type>::tl
+    hash_set_tl_t;
+
+    template<typename Cntnr_T>
+    struct hash_mmap_transform
+    {
+      typedef
+      typename __gnu_pbds::test::hash_common_types<
+	int,
+	__gnu_pbds::compound_data_type<
+	Cntnr_T> >::tl
+      type;
+    };
+
+    typedef
+    __gnu_cxx::typelist::flatten<
+      __gnu_cxx::typelist::transform<
+      hash_set_tl_t,
+      hash_mmap_transform>::type>::type
+    hash_mmap_tl_t;
+
+    typedef
+    __gnu_pbds::test::tree_common_types<
+      int,
+      __gnu_pbds::null_mapped_type>::tl
+    tree_set_tl_t;
+
+    template<typename Cntnr_T>
+    struct tree_mmap_transform
+    {
+      typedef
+      typename __gnu_pbds::test::tree_common_types<
+	int,
+	__gnu_pbds::compound_data_type<
+	Cntnr_T> >::tl
+      type;
+    };
+
+    typedef
+    __gnu_cxx::typelist::flatten<
+      __gnu_cxx::typelist::transform<
+      tree_set_tl_t,
+      tree_mmap_transform>::type>::type
+    tree_mmap_tl_t;
+
+    typedef hash_mmap_tl_t mmap_tl_t;
+
+  } // namespace test
+
+} // namespace __gnu_pbds
+
+#endif // #ifndef PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP
+
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/find_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/find_test.hpp
new file mode 100644
index 000000000..f53a1273c
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/find_test.hpp
@@ -0,0 +1,166 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file find_test.hpp
+ * Contains a generic find test.
+ */
+
+#ifndef PB_DS_FIND_TEST_HPP
+#define PB_DS_FIND_TEST_HPP
+
+#include <performance/time/timing_test_base.hpp>
+#include <performance/io/xml_formatter.hpp>
+#include <common_type/assoc/string_form.hpp>
+#include <iterator>
+
+namespace __gnu_pbds
+{
+  namespace test
+  {
+    namespace detail
+    {
+      template<typename It, class Cntnr, bool LOR>
+      class find_find_functor
+      {
+      public:
+        find_find_functor(Cntnr& contnr,  It fnd_it_b,  It fnd_it_e) 
+	: m_contnr(contnr), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      It fnd_it = m_fnd_it_b;
+	      while (fnd_it != m_fnd_it_e)
+                ++m_contnr.find((fnd_it++)->first)->second;
+	    }
+	}
+
+      private:
+	Cntnr& m_contnr;
+	const It m_fnd_it_b;
+	const It m_fnd_it_e;
+      };
+
+      template<typename It, class Cntnr>
+      class find_find_functor<It, Cntnr, true>
+      {
+      public:
+        find_find_functor(Cntnr& contnr,  It fnd_it_b,  It fnd_it_e) 
+	: m_contnr(contnr), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  It fnd_it = m_fnd_it_b;
+	  while (fnd_it != m_fnd_it_e)
+	    {
+	      for (std::size_t i = 0; i < resolution; ++i)
+                ++m_contnr.find(fnd_it->first)->second;
+	      ++fnd_it;
+	    }
+	}
+
+      private:
+	Cntnr& m_contnr;
+	const It m_fnd_it_b;
+	const It m_fnd_it_e;
+      };
+    } // namespace detail
+
+    template<typename It, bool LOR = false>
+    class find_test : private __gnu_pbds::test::detail::timing_test_base
+    {
+    public:
+      find_test(It ins_b, It fnd_it_b, size_t ins_vn, size_t ins_vs, 
+		size_t ins_vm, size_t fnd_vn, size_t fnd_vs, size_t fnd_vm):
+      m_ins_b(ins_b), m_fnd_it_b(fnd_it_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs),
+      m_ins_vm(ins_vm), m_fnd_vn(fnd_vn), m_fnd_vs(fnd_vs), m_fnd_vm(fnd_vm)
+      { }
+
+      template<typename Cntnr>
+      void
+      operator()(Cntnr);
+
+    private:
+      find_test(const find_test& );
+
+    private:
+      const It 		m_ins_b;
+      const It 		m_fnd_it_b;
+      const size_t 	m_ins_vn;
+      const size_t 	m_ins_vs;
+      const size_t 	m_ins_vm;
+      const size_t 	m_fnd_vn;
+      const size_t 	m_fnd_vs;
+      const size_t 	m_fnd_vm;
+    };
+
+    template<typename It, bool LOR>
+    template<typename Cntnr>
+    void
+    find_test<It, LOR>::
+    operator()(Cntnr)
+    {
+      typedef string_form<Cntnr> sform_type;
+      typedef xml_result_set_performance_formatter formatter_type;
+      formatter_type res_set_fmt(sform_type::name(), sform_type::desc());
+
+      for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
+	{
+	  const size_t v = m_ins_vn + i * m_ins_vs;
+	  const size_t fnd_size = m_fnd_vn + i * m_fnd_vs;
+	  It ins_it_b = m_ins_b;
+	  It ins_it_e = m_ins_b;
+	  std::advance(ins_it_e, v);
+
+	  Cntnr test_container(ins_it_b, ins_it_e);
+	  It fnd_it_b = m_fnd_it_b;
+	  It fnd_it_e = m_fnd_it_b;
+	  std::advance(fnd_it_e, fnd_size);
+
+	  __gnu_pbds::test::detail::find_find_functor<It, Cntnr, LOR>
+            fn(test_container, fnd_it_b, fnd_it_e);
+
+	  const double res =
+            __gnu_pbds::test::detail::timing_test_base::operator()(fn);
+	  res_set_fmt.add_res(v, res / fnd_size);
+	}
+    }
+  } // namespace test
+} // namespace __gnu_pbds
+
+#endif 
+
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/insert_test.hpp
new file mode 100644
index 000000000..e71d755ba
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/insert_test.hpp
@@ -0,0 +1,143 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file insert_test.hpp
+ * Contains an insert performance test.
+ */
+
+#ifndef PB_DS_INSERT_TEST_HPP
+#define PB_DS_INSERT_TEST_HPP
+
+#include <performance/time/timing_test_base.hpp>
+#include <ext/pb_ds/detail/type_utils.hpp>
+#include <performance/io/xml_formatter.hpp>
+#include <common_type/assoc/string_form.hpp>
+#include <iterator>
+
+namespace __gnu_pbds
+{
+  namespace test
+  {
+    namespace detail
+    {
+      template<typename It, class Cntnr>
+      class insert_insert_functor
+      {
+      public:
+        insert_insert_functor(It ins_it_b,  It ins_it_e) 
+	: m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      Cntnr cntnr;
+	      for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
+                cntnr.insert((typename Cntnr::const_reference)(*ins_it));
+	    }
+	}
+
+      private:
+	const It m_ins_it_b;
+	const It m_ins_it_e;
+      };
+    } // namespace detail
+
+    template<typename It>
+    class insert_test : private __gnu_pbds::test::detail::timing_test_base
+    {
+    public:
+      insert_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm)
+      :  m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+      { }
+
+      template<typename Cntnr>
+      void
+      operator()(Cntnr);
+
+    private:
+      insert_test(const insert_test& );
+
+      template<typename Cntnr>
+      void
+      insert(Cntnr, It ins_it_b, It ins_it_e);
+
+      const It m_ins_b;
+      const size_t m_ins_vn;
+      const size_t m_ins_vs;
+      const size_t m_ins_vm;
+    };
+
+    template<typename It>
+    template<typename Cntnr>
+    void
+    insert_test<It>::
+    operator()(Cntnr)
+    {
+      typedef xml_result_set_performance_formatter formatter_type;
+      formatter_type res_set_fmt(string_form<Cntnr>::name(),
+				 string_form<Cntnr>::desc());
+
+      for (size_t i = 0; m_ins_vn + i*  m_ins_vs < m_ins_vm; ++i)
+	{
+	  const size_t v = m_ins_vn + i*  m_ins_vs;
+	  It ins_it_b = m_ins_b;
+	  It ins_it_e = m_ins_b;
+	  std::advance(ins_it_e, v);
+
+	  __gnu_pbds::test::detail::insert_insert_functor<It, Cntnr>
+            fn(ins_it_b, ins_it_e);
+
+	  const double res =
+            __gnu_pbds::test::detail::timing_test_base::operator()(fn);
+
+	  res_set_fmt.add_res(v, res / v);
+	}
+    }
+
+    template<typename It>
+    template<typename Cntnr>
+    void
+    insert_test<It>::
+    insert(Cntnr, It ins_it_b, It ins_it_e)
+    {
+      Cntnr cntnr;
+      for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
+        cntnr.insert((typename Cntnr::const_reference)(*ins_it));
+    }
+  } // namespace test
+} // namespace __gnu_pbds
+
+#endif
+
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp
new file mode 100644
index 000000000..7e3f95bfc
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp
@@ -0,0 +1,191 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2007, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file multimap_find_test.hpp
+ * Contains a generic multimap_find_test test.
+ */
+
+#ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP
+#define PB_DS_MULTIMAP_INSERT_TEST_HPP
+
+#include <performance/time/timing_test_base.hpp>
+#include <performance/io/xml_formatter.hpp>
+#include <common_type/assoc/string_form.hpp>
+#include <iterator>
+
+namespace __gnu_pbds
+{
+  namespace test
+  {
+    namespace detail
+    {
+      template<typename It, class Cntnr, bool Native>
+      class multimap_find_functor
+      {
+      public:
+        multimap_find_functor(const Cntnr& container, It fnd_it_b, It fnd_it_e)
+	: m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  size_t not_found_count = 0;
+	  typedef typename Cntnr::const_point_iterator iterator_type;
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      iterator_type end = m_r_container.end();
+	      for (It fnd_it = m_fnd_it_b; fnd_it != m_fnd_it_e; ++fnd_it)
+		{
+		  iterator_type it = m_r_container.find(fnd_it->first);
+		  if (it == end ||
+		      it->second.find(fnd_it->second) == it->second.end())
+                    ++not_found_count;
+		}
+	    }
+
+	  if (not_found_count != 0)
+            std::abort();
+	}
+
+      private:
+	const Cntnr& m_r_container;
+	const It m_fnd_it_b;
+	const It m_fnd_it_e;
+      };
+
+      template<typename It, class Cntnr>
+      class multimap_find_functor<It, Cntnr, true>
+      {
+      public:
+        multimap_find_functor(const Cntnr& container, It fnd_it_b, It fnd_it_e)
+	: m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  typedef typename Cntnr::const_reference const_reference;
+	  size_t not_found_count = 0;
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      Cntnr cntnr;
+	      for (It fnd_it = m_fnd_it_b; fnd_it != m_fnd_it_e; ++fnd_it)
+                if (m_r_container.find(const_reference(*fnd_it)) 
+		    == m_r_container.end())
+		  ++not_found_count;
+	    }
+
+	  if (not_found_count != 0)
+            std::abort();
+	}
+
+      private:
+	const Cntnr& m_r_container;
+	const It m_fnd_it_b;
+	const It m_fnd_it_e;
+      };
+    } // namespace detail
+
+
+    template<typename It, bool Native>
+    class multimap_find_test 
+    : private __gnu_pbds::test::detail::timing_test_base
+    {
+    public:
+      multimap_find_test(It ins_b, size_t ins_vn, size_t vs, size_t ins_vm)
+      : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(vs), m_ins_vm(ins_vm)
+      { }
+
+      template<typename Cntnr>
+      void
+      operator()(Cntnr);
+
+    private:
+      multimap_find_test(const multimap_find_test&);
+
+      template<typename Cntnr>
+      Cntnr
+      init(It ins_b, It ins_e, Cntnr, __gnu_pbds::detail::true_type)
+      { return Cntnr(ins_b, ins_e); }
+
+      template<typename Cntnr>
+      Cntnr
+      init(It ins_b, It ins_e, Cntnr, __gnu_pbds::detail::false_type)
+      {
+	Cntnr ret;
+	for (It it = ins_b; it != ins_e; ++it)
+	  ret[it->first].insert(it->second);
+	return ret;
+      }
+
+      const It m_ins_b;
+      const size_t m_ins_vn;
+      const size_t m_ins_vs;
+      const size_t m_ins_vm;
+    };
+
+
+    template<typename It, bool Native>
+    template<typename Cntnr>
+    void
+    multimap_find_test<It, Native>::
+    operator()(Cntnr)
+    {
+      typedef xml_result_set_performance_formatter formatter_type;
+      formatter_type res_set_fmt(string_form<Cntnr>::name(),
+				 string_form<Cntnr>::desc());
+
+      for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
+	{
+	  const size_t v = m_ins_vn + i * m_ins_vs;
+	  It ins_it_b = m_ins_b;
+	  It ins_it_e = m_ins_b;
+	  std::advance(ins_it_e, v);
+
+	  Cntnr c = init(ins_it_b, ins_it_e, Cntnr(),
+			 __gnu_pbds::detail::integral_constant<int,Native>());
+
+	  __gnu_pbds::test::detail::multimap_find_functor<It, Cntnr, Native>
+            fn(c, ins_it_b, ins_it_e);
+
+	  const double res =
+            __gnu_pbds::test::detail::timing_test_base::operator()(fn);
+
+	  res_set_fmt.add_res(v, res / v);
+	}
+    }
+  } // namespace test
+} // namespace __gnu_pbds
+
+#endif 
+
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp
new file mode 100644
index 000000000..2e8539857
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp
@@ -0,0 +1,151 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file multimap_insert_test.hpp
+ * Contains a generic multimap_insert_test test.
+ */
+
+#ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP
+#define PB_DS_MULTIMAP_INSERT_TEST_HPP
+
+#include <performance/time/timing_test_base.hpp>
+#include <performance/io/xml_formatter.hpp>
+#include <common_type/assoc/string_form.hpp>
+#include <iterator>
+
+namespace __gnu_pbds
+{
+  namespace test
+  {
+    namespace detail
+    {
+      template<typename It, class Cntnr, bool Native>
+      class multimap_insert_functor
+      {
+      public:
+        multimap_insert_functor(It ins_it_b, It ins_it_e) 
+	: m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      Cntnr cntnr;
+	      for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
+                cntnr[ins_it->first].insert(ins_it->second);
+	    }
+	}
+
+      private:
+	const It m_ins_it_b;
+	const It m_ins_it_e;
+      };
+
+      template<typename It, class Cntnr>
+      class multimap_insert_functor<It, Cntnr, true>
+      {
+      public:
+        multimap_insert_functor(It ins_it_b,  It ins_it_e) 
+	: m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      Cntnr cntnr;
+	      for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
+		cntnr.insert((typename Cntnr::const_reference)(*ins_it));
+	    }
+	}
+
+      private:
+	const It m_ins_it_b;
+	const It m_ins_it_e;
+      };
+    } // namespace detail
+
+    template<typename It, bool Native>
+    class multimap_insert_test 
+    : private __gnu_pbds::test::detail::timing_test_base
+    {
+    public:
+      multimap_insert_test(It b, size_t ins_vn, size_t ins_vs, size_t ins_vm) 
+      : m_ins_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+      { }
+
+      template<typename Cntnr>
+      void
+      operator()(Cntnr);
+
+    private:
+      multimap_insert_test(const multimap_insert_test&);
+
+      const It m_ins_b;
+      const size_t m_ins_vn;
+      const size_t m_ins_vs;
+      const size_t m_ins_vm;
+    };
+
+    template<typename It, bool Native>
+    template<typename Cntnr>
+    void
+    multimap_insert_test<It, Native>::
+    operator()(Cntnr)
+    {
+      typedef xml_result_set_performance_formatter formatter_type;
+      formatter_type res_set_fmt(string_form<Cntnr>::name(),
+				 string_form<Cntnr>::desc());
+
+      for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
+	{
+	  const size_t v = m_ins_vn + i * m_ins_vs;
+	  It ins_it_b = m_ins_b;
+	  It ins_it_e = m_ins_b;
+	  std::advance(ins_it_e, v);
+
+	  __gnu_pbds::test::detail::multimap_insert_functor<It, Cntnr, Native>
+            fn(ins_it_b, ins_it_e);
+
+	  const double res =
+            __gnu_pbds::test::detail::timing_test_base::operator()(fn);
+	  res_set_fmt.add_res(v, res / v);
+	}
+    }
+  } // namespace test
+} // namespace __gnu_pbds
+
+#endif
+
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_find_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_find_test.hpp
new file mode 100644
index 000000000..d37121b8c
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_find_test.hpp
@@ -0,0 +1,144 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file subscript_find_test.hpp
+ * Contains a generic subscript_find_test test.
+ */
+
+#ifndef PB_DS_SUBSCRIPT_TEST_HPP
+#define PB_DS_SUBSCRIPT_TEST_HPP
+
+#include <performance/time/timing_test_base.hpp>
+#include <common_type/assoc/string_form.hpp>
+#include <iterator>
+
+namespace __gnu_pbds
+{
+  namespace test
+  {
+    namespace detail
+    {
+      template<typename It, class Cntnr>
+      class subscript_find_functor
+      {
+      public:
+        subscript_find_functor(Cntnr& container,  It fnd_it_b,  It fnd_it_e) 
+	: m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      It fnd_it = m_fnd_it_b;
+	      while (fnd_it != m_fnd_it_e)
+                ++m_r_container[(fnd_it++)->first];
+	      ++fnd_it;
+	    }
+	}
+
+      private:
+	Cntnr& m_r_container;
+	const It m_fnd_it_b;
+	const It m_fnd_it_e;
+      };
+
+    } // namespace detail
+
+    template<typename It>
+    class subscript_find_test : private __gnu_pbds::test::detail::timing_test_base
+    {
+    public:
+      subscript_find_test(It ins_b, It b, size_t ins_vn, size_t ins_vs, 
+			  size_t ins_vm, size_t vn, size_t vs, size_t vm)
+      : m_ins_b(ins_b), m_fnd_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs),
+	m_ins_vm(ins_vm), m_fnd_vn(vn), m_fnd_vs(vs), m_fnd_vm(vm)
+      { }
+
+      template<typename Cntnr>
+      void
+      operator()(Cntnr);
+
+    private:
+      subscript_find_test(const subscript_find_test&);
+
+    private:
+      const It m_ins_b;
+      const It m_fnd_b;
+      const size_t m_ins_vn;
+      const size_t m_ins_vs;
+      const size_t m_ins_vm;
+      const size_t m_fnd_vn;
+      const size_t m_fnd_vs;
+      const size_t m_fnd_vm;
+    };
+
+   template<typename It>
+   template<typename Cntnr>
+    void
+    subscript_find_test<It>::
+    operator()(Cntnr)
+    {
+      typedef xml_result_set_performance_formatter formatter_type;
+      formatter_type res_set_fmt(string_form<Cntnr>::name(),
+				 string_form<Cntnr>::desc());
+
+      for (size_t i = 0; m_ins_vn + i*  m_ins_vs < m_ins_vm; ++i)
+	{
+	  const size_t v = m_ins_vn + i*  m_ins_vs;
+	  const size_t fnd_size = m_fnd_vn + i*  m_fnd_vs;
+
+	  It ins_it_b = m_ins_b;
+	  It ins_it_e = m_ins_b;
+	  std::advance(ins_it_e, v);
+
+	  Cntnr test_container(ins_it_b, ins_it_e);
+
+	  It fnd_it_b = m_fnd_b;
+	  It fnd_it_e = m_fnd_b;
+	  std::advance(fnd_it_e, fnd_size);
+
+	  __gnu_pbds::test::detail::subscript_find_functor<It, Cntnr>
+            fn(test_container, fnd_it_b, fnd_it_e);
+
+	  const double res =
+            __gnu_pbds::test::detail::timing_test_base::operator()(fn);
+
+	  res_set_fmt.add_res(v, res / fnd_size);
+	}
+    }
+  } // namespace test
+} // namespace __gnu_pbds
+
+#endif 
+
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_insert_test.hpp
new file mode 100644
index 000000000..10925fd60
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_insert_test.hpp
@@ -0,0 +1,134 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file subscript_insert_test.hpp
+ * Contains a generic subscript_insert_test test.
+ */
+
+#ifndef PB_DS_SUBSCRIPT_TEST_HPP
+#define PB_DS_SUBSCRIPT_TEST_HPP
+
+#include <performance/time/timing_test_base.hpp>
+#include <performance/io/xml_formatter.hpp>
+#include <common_type/assoc/string_form.hpp>
+#include <iterator>
+
+namespace __gnu_pbds
+{
+  namespace test
+  {
+    namespace detail
+    {
+      template<typename It, class Cntnr>
+      class subscript_insert_functor
+      {
+      public:
+        subscript_insert_functor(It ins_it_b,  It ins_it_e) 
+	: m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      Cntnr cntnr;
+	      for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
+                ++cntnr[ins_it->first];
+	    }
+	}
+
+      private:
+	const It m_ins_it_b;
+	const It m_ins_it_e;
+      };
+
+    } // namespace detail
+
+    template<typename It>
+    class subscript_insert_test : private __gnu_pbds::test::detail::timing_test_base
+    {
+    public:
+      subscript_insert_test(It ins_b, It b, size_t ins_vn, size_t ins_vs, 
+			    size_t ins_vm, size_t vn, size_t vs, size_t vm)
+      : m_ins_b(ins_b), m_fnd_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), 
+	m_ins_vm(ins_vm), m_fnd_vn(vn), m_fnd_vs(vs), m_fnd_vm(vm)
+      { }
+
+      template<typename Cntnr>
+      void
+      operator()(Cntnr);
+
+    private:
+      subscript_insert_test(const subscript_insert_test& );
+
+    private:
+      const It m_ins_b;
+      const It m_fnd_b;
+      const size_t m_ins_vn;
+      const size_t m_ins_vs;
+      const size_t m_ins_vm;
+      const size_t m_fnd_vn;
+      const size_t m_fnd_vs;
+      const size_t m_fnd_vm;
+    };
+
+    template<typename It>
+    template<typename Cntnr>
+    void
+    subscript_insert_test<It>::
+    operator()(Cntnr)
+    {
+      typedef xml_result_set_performance_formatter formatter_type;
+      formatter_type res_set_fmt(string_form<Cntnr>::name(),
+				 string_form<Cntnr>::desc());
+
+      for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
+	{
+	  const size_t v = m_ins_vn + i * m_ins_vs;
+	  It ins_it_b = m_ins_b;
+	  It ins_it_e = m_ins_b;
+	  std::advance(ins_it_e, v);
+	  __gnu_pbds::test::detail::subscript_insert_functor<It, Cntnr>
+            fn(ins_it_b, ins_it_e);
+
+	  const double res =
+            __gnu_pbds::test::detail::timing_test_base::operator()(fn);
+
+	  res_set_fmt.add_res(v, res / v);
+	}
+    }
+  } // namespace test
+} // namespace __gnu_pbds
+
+#endif 
+
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_order_statistics_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_order_statistics_test.hpp
new file mode 100644
index 000000000..0fb028687
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_order_statistics_test.hpp
@@ -0,0 +1,176 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2007, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file tree_order_statistics_test.hpp
+ * Contains a test for order_statisticsing trees
+ */
+
+#ifndef PB_DS_TREE_ORDER_STATISTICS_TEST_HPP
+#define PB_DS_TREE_ORDER_STATISTICS_TEST_HPP
+
+#include <performance/time/timing_test_base.hpp>
+#include <performance/io/xml_formatter.hpp>
+#include <common_type/assoc/string_form.hpp>
+#include <ext/pb_ds/detail/type_utils.hpp>
+#include <iterator>
+#include <cstdlib>
+
+namespace __gnu_pbds
+{
+  namespace test
+  {
+    namespace detail
+    {
+      template<typename Cntnr, bool Native>
+      class order_statistics_functor
+      {
+      public:
+        order_statistics_functor(Cntnr& container) : m_r_container(container)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  enum
+	    {
+	      support_detected =
+	      __gnu_pbds::test::detail::tree_supports_order_statistics<Cntnr>::value
+	    };
+
+	  PB_DS_STATIC_ASSERT(correct_type, support_detected);
+
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      typename Cntnr::const_iterator it = m_r_container.begin();
+	      typename Cntnr::const_iterator e = m_r_container.end();
+	      const size_t max_size = m_r_container.size();
+	      while (it != e)
+		if (m_r_container.order_of_key(*(it++)) > max_size)
+		  std::abort();
+	    }
+	}
+
+      private:
+	Cntnr& m_r_container;
+      };
+
+      template<typename Cntnr>
+      class order_statistics_functor<Cntnr, false>
+      {
+      public:
+        order_statistics_functor(Cntnr& container) : m_r_container(container)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      typedef typename Cntnr::const_iterator const_iterator;
+	      const_iterator b = m_r_container.begin();
+	      const_iterator e = m_r_container.end();
+	      const_iterator it = b;
+	      const size_t max_size = m_r_container.size();
+	      while (it != e)
+		{
+		  const_iterator f_it = m_r_container.find(*(it++));
+		  if (static_cast<size_t>(std::distance(b, f_it)) > max_size)
+		    std::abort();
+		}
+	    }
+	}
+
+      private:
+	Cntnr& m_r_container;
+      };
+    } // namespace detail
+
+    template<bool Support_Order_Statistics>
+    class tree_order_statistics_test 
+    : private __gnu_pbds::test::detail::timing_test_base
+    {
+    public:
+      tree_order_statistics_test(size_t vn, size_t vs, size_t vm)
+      : m_vn(vn), m_vs(vs), m_vm(vm)
+      { }
+
+      template<typename Cntnr>
+      void
+      operator()(Cntnr);
+
+    private:
+      tree_order_statistics_test(const tree_order_statistics_test& );
+
+      template<typename Cntnr>
+      void
+      order_statistics(Cntnr& r_container, __gnu_pbds::detail::true_type);
+
+      template<typename Cntnr>
+      void
+      order_statistics(Cntnr& r_container, __gnu_pbds::detail::false_type);
+
+    private:
+      const size_t m_vn;
+      const size_t m_vs;
+      const size_t m_vm;
+    };
+
+    template<bool Support_Order_Statistics>
+    template<typename Cntnr>
+    void
+    tree_order_statistics_test<Support_Order_Statistics>::
+    operator()(Cntnr)
+    {
+      typedef xml_result_set_performance_formatter formatter_type;
+      formatter_type res_set_fmt(string_form<Cntnr>::name(), 
+				 string_form<Cntnr>::desc());
+
+      for (size_t v = m_vn; v < m_vm; v += m_vs)
+	{
+	  Cntnr cntnr;
+	  for (size_t ins = 0; ins < v; ++ ins)
+            cntnr.insert((typename Cntnr::value_type)ins);
+
+	  __gnu_pbds::test::detail::order_statistics_functor<Cntnr, Support_Order_Statistics>
+            fn(cntnr);
+
+	  const double res =
+            __gnu_pbds::test::detail::timing_test_base::operator()(fn);
+
+	  res_set_fmt.add_res(v, res / v);
+	}
+    }
+  } // namespace test
+} // namespace __gnu_pbds
+
+#endif 
+
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_split_join_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_split_join_test.hpp
new file mode 100644
index 000000000..6872291df
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_split_join_test.hpp
@@ -0,0 +1,158 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 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/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file tree_split_join_test.hpp
+ * Contains a test for splitting and joining trees
+ */
+
+#ifndef PB_DS_TREE_SPLIT_JOIN_TEST_HPP
+#define PB_DS_TREE_SPLIT_JOIN_TEST_HPP
+
+#include <performance/time/timing_test_base.hpp>
+#include <performance/io/xml_formatter.hpp>
+#include <common_type/assoc/string_form.hpp>
+#include <iterator>
+
+namespace __gnu_pbds
+{
+  namespace test
+  {
+    namespace detail
+    {
+      template<typename Cntnr, bool Support_Split_Join>
+      class split_join_functor
+      {
+      public:
+        split_join_functor(Cntnr& r_container) : m_r_container(r_container)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      typename Cntnr::const_iterator mid_it = m_r_container.begin();
+	      std::advance(mid_it, m_r_container.size() / 2);
+	      Cntnr other;
+	      m_r_container.split(*mid_it, other);
+	      m_r_container.join(other);
+	    }
+	}
+
+      private:
+	Cntnr& m_r_container;
+      };
+
+      template<typename Cntnr>
+      class split_join_functor<Cntnr, false>
+      {
+      public:
+        split_join_functor(Cntnr& r_container) : m_r_container(r_container)
+	{ }
+
+	void
+        operator()(std::size_t resolution)
+	{
+	  for (std::size_t i = 0; i < resolution; ++i)
+	    {
+	      typename Cntnr::iterator mid_it = m_r_container.begin();
+	      std::advance(mid_it, m_r_container.size() / 2);
+
+	      Cntnr other(mid_it, m_r_container.end());
+	      m_r_container.erase(mid_it, m_r_container.end());
+
+	      m_r_container.insert(other.begin(), other.end());
+	      other.clear();
+	    }
+	}
+
+      private:
+	Cntnr& m_r_container;
+      };
+    } // namespace detail
+
+    template<bool Support_Split_Join>
+    class tree_split_join_test : private __gnu_pbds::test::detail::timing_test_base
+    {
+    public:
+      tree_split_join_test(size_t vn, size_t vs, size_t vm);
+
+      template<typename Cntnr>
+      void
+      operator()(Cntnr);
+
+    private:
+      tree_split_join_test(const tree_split_join_test& );
+
+    private:
+      const size_t m_vn;
+      const size_t m_vs;
+      const size_t m_vm;
+    };
+
+    template<bool Support_Split_Join>
+    tree_split_join_test<Support_Split_Join>::
+    tree_split_join_test(size_t vn, size_t vs, size_t vm) :
+      m_vn(vn),
+      m_vs(vs),
+      m_vm(vm)
+    { }
+
+    template<bool Support_Split_Join>
+    template<typename Cntnr>
+    void
+    tree_split_join_test<Support_Split_Join>::
+    operator()(Cntnr)
+    {
+      typedef xml_result_set_performance_formatter formatter_type;
+      formatter_type res_set_fmt(string_form<Cntnr>::name(),
+				 string_form<Cntnr>::desc());
+
+      for (size_t v = m_vn; v < m_vm; v += m_vs)
+	{
+	  Cntnr cntnr;
+	  for (size_t ins = 0; ins < v; ++ ins)
+            cntnr.insert((typename Cntnr::value_type)ins);
+
+	  __gnu_pbds::test::detail::split_join_functor<Cntnr, Support_Split_Join>
+            fn(cntnr);
+
+	  const double res =
+            __gnu_pbds::test::detail::timing_test_base::operator()(fn);
+	  res_set_fmt.add_res(v, res);
+	}
+    }
+  } // namespace test
+} // namespace __gnu_pbds
+
+#endif 
+