Convert ext/hash_map, set to tr1/functional, tr1/unordered_map, set.

2007-10-11  Benjamin Kosnik  <bkoz@redhat.com>

	Convert ext/hash_map, set to tr1/functional, tr1/unordered_map, set.
	* include/ext/rope: Use tr1/functional hash instead of ext/hash_fun.h.
	* include/ext/pb_ds/detail/standard_policies.hpp: Same.
	* include/precompiled/extc++.h: Remove hash_map, hash_set.
	* testsuite/util/testsuite_abi.h (__gnu_cxx): Use unordered_map
	instead of hash_map. Remove hash specialization for string.
	* testsuite/util/testsuite_abi.cc: Include <vector>.
	* testsuite/util/native_type/assoc/native_hash_set.hpp: Remove
	hash_set code.
	* testsuite/util/native_type/assoc/native_hash_map.hpp: Remove
	hash_map code.
	* testsuite/util/native_type/assoc/native_hash_multimap.hpp:
	Change hash_multimap to unordered_multimap.
	* testsuite/util/testsuite_common_types.h: Remove hash_map, hash_set.
	* testsuite/ext/headers.cc: Same.
	* testsuite/17_intro/headers/all_c++200x_compatibility.cc: Remove
	hash_map.h, hash_set.h.
	* testsuite/17_intro/headers/all.cc: Same.
	* testsuite/17_intro/headers/all_pedantic_errors.cc: Same.

	* include/ext/pb_ds/detail/standard_policies.hpp: Format.
	* testsuite/util/native_type/assoc/native_set.hpp: Same, 
	update comment.
	* testsuite/util/native_type/assoc/native_map.hpp: Same.
	* testsuite/util/native_type/assoc/native_multimap.hpp: Same.
	* testsuite/util/performance/assoc/timing/
	multimap_insert_test.hpp: Same.
	* testsuite/util/performance/assoc/timing/multimap_find_test.hpp: Same.

From-SVN: r129243

19 files changed, 107 insertions, 215 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 34c00f7..f5e60e8 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,34 @@
+2007-10-11  Benjamin Kosnik  <bkoz@redhat.com>
+
+	Convert ext/hash_map, set to tr1/functional, tr1/unordered_map, set.
+	* include/ext/rope: Use tr1/functional hash instead of ext/hash_fun.h.
+	* include/ext/pb_ds/detail/standard_policies.hpp: Same.
+	* include/precompiled/extc++.h: Remove hash_map, hash_set.
+	* testsuite/util/testsuite_abi.h (__gnu_cxx): Use unordered_map
+	instead of hash_map. Remove hash specialization for string.
+	* testsuite/util/testsuite_abi.cc: Include <vector>.
+	* testsuite/util/native_type/assoc/native_hash_set.hpp: Remove
+	hash_set code.
+	* testsuite/util/native_type/assoc/native_hash_map.hpp: Remove
+	hash_map code.
+	* testsuite/util/native_type/assoc/native_hash_multimap.hpp:
+	Change hash_multimap to unordered_multimap.
+	* testsuite/util/testsuite_common_types.h: Remove hash_map, hash_set.
+	* testsuite/ext/headers.cc: Same.
+	* testsuite/17_intro/headers/all_c++200x_compatibility.cc: Remove
+	hash_map.h, hash_set.h.
+	* testsuite/17_intro/headers/all.cc: Same.
+	* testsuite/17_intro/headers/all_pedantic_errors.cc: Same.
+
+	* include/ext/pb_ds/detail/standard_policies.hpp: Format.
+	* testsuite/util/native_type/assoc/native_set.hpp: Same, 
+	update comment.
+	* testsuite/util/native_type/assoc/native_map.hpp: Same.
+	* testsuite/util/native_type/assoc/native_multimap.hpp: Same.
+	* testsuite/util/performance/assoc/timing/
+	multimap_insert_test.hpp: Same.
+	* testsuite/util/performance/assoc/timing/multimap_find_test.hpp: Same.
+
 2007-10-11  Chris Jefferson  <chris@bubblescope.net>
 	    Paolo Carlini  <pcarlini@suse.de>
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/standard_policies.hpp b/libstdc++-v3/include/ext/pb_ds/detail/standard_policies.hpp
index bbd91c3..47bc143 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/standard_policies.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/standard_policies.hpp
@@ -1,6 +1,6 @@
 // -*- C++ -*-
 
-// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006, 2007 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
@@ -54,7 +54,7 @@
 #include <ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp>
 #include <ext/pb_ds/trie_policy.hpp>
 #include <ext/pb_ds/tag_and_trait.hpp>
-#include <ext/hash_map>
+#include <tr1/functional>
 
 namespace __gnu_pbds
 {
@@ -63,13 +63,13 @@ namespace __gnu_pbds
     template<typename Key>
     struct default_hash_fn
     {
-      typedef __gnu_cxx::hash< Key> type;
+      typedef std::tr1::hash<Key> type;
     };
 
     template<typename Key>
     struct default_eq_fn
     {
-      typedef std::equal_to< Key> type;
+      typedef std::equal_to<Key> type;
     };
 
     enum
@@ -88,27 +88,17 @@ namespace __gnu_pbds
     private:
       typedef typename Comb_Hash_Fn::size_type size_type;
 
-      typedef
-      typename __conditional_type<
-	is_same<
-	__gnu_pbds::direct_mask_range_hashing<
-	size_type>,
-	Comb_Hash_Fn>::value,
-	__gnu_pbds::hash_exponential_size_policy<
-	size_type>,
-	__gnu_pbds::hash_prime_size_policy>::__type
-      size_policy_type;
+      typedef __gnu_pbds::direct_mask_range_hashing<size_type> default_fn;
+      typedef is_same<default_fn, Comb_Hash_Fn> same_type;
+      typedef __gnu_pbds::hash_exponential_size_policy<size_type> iftrue;
+      typedef __gnu_pbds::hash_prime_size_policy iffalse;
+      typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type;
+      typedef typename cond_type::__type size_policy_type;
+
+      typedef __gnu_pbds::hash_load_check_resize_trigger<false, size_type> trigger;
 
     public:
-      typedef
-      __gnu_pbds::hash_standard_resize_policy<
-      size_policy_type,
-      __gnu_pbds::hash_load_check_resize_trigger<
-      false,
-      size_type>,
-      false,
-      size_type>
-      type;
+      typedef __gnu_pbds::hash_standard_resize_policy<size_policy_type, trigger, false, size_type> type;
     };
 
     struct default_update_policy
@@ -122,38 +112,27 @@ namespace __gnu_pbds
     private:
       typedef typename Comb_Probe_Fn::size_type size_type;
 
+      typedef __gnu_pbds::direct_mask_range_hashing<size_type> default_fn;
+      typedef is_same<default_fn, Comb_Probe_Fn> same_type;
+      typedef __gnu_pbds::linear_probe_fn<size_type> iftrue;
+      typedef __gnu_pbds::quadratic_probe_fn<size_type> iffalse;
+      typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type;
+
     public:
-      typedef
-      typename __conditional_type<
-      is_same<
-      __gnu_pbds::direct_mask_range_hashing<size_t>,
-      Comb_Probe_Fn>::value,
-      __gnu_pbds::linear_probe_fn<
-      size_type>,
-      __gnu_pbds::quadratic_probe_fn<
-      size_type> >::__type
-      type;
+      typedef typename cond_type::__type type;
     };
 
     template<typename Key>
     struct default_trie_e_access_traits;
 
     template<typename Char, class Char_Traits>
-    struct default_trie_e_access_traits<
-      std::basic_string<
-      Char,
-      Char_Traits,
-      std::allocator<
-      char> > >
+    struct default_trie_e_access_traits<std::basic_string<Char, Char_Traits, std::allocator<char> > >
     {
-      typedef
-      __gnu_pbds::string_trie_e_access_traits<
-	std::basic_string<
-	Char,
-	Char_Traits,
-	std::allocator<
-	char> > >
-      type;
+    private:
+      typedef std::basic_string<Char, Char_Traits, std::allocator<char> > string_type;
+
+    public:
+      typedef __gnu_pbds::string_trie_e_access_traits<string_type> type;
     };
 
   } // namespace detail
diff --git a/libstdc++-v3/include/ext/rope b/libstdc++-v3/include/ext/rope
index b548917..ed1df5b 100644
--- a/libstdc++-v3/include/ext/rope
+++ b/libstdc++-v3/include/ext/rope
@@ -56,8 +56,8 @@
 #include <bits/stl_function.h>
 #include <bits/stl_numeric.h>
 #include <bits/allocator.h>
-#include <ext/hash_fun.h>
 #include <bits/gthr.h>
+#include <tr1/functional>
 
 # ifdef __GC
 #   define __GC_CONST const
@@ -2906,12 +2906,18 @@ protected:
     swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y)
     { __x.swap(__y); }
 
-  // Hash functions should probably be revisited later:
+_GLIBCXX_END_NAMESPACE
+
+
+namespace std
+{ 
+namespace tr1
+{
   template<>
-    struct hash<crope>
+    struct hash<__gnu_cxx::crope>
     {
       size_t
-      operator()(const crope& __str) const
+      operator()(const __gnu_cxx::crope& __str) const
       {
 	size_t __size = __str.size();
 	if (0 == __size)
@@ -2922,10 +2928,10 @@ protected:
 
 
   template<>
-    struct hash<wrope>
+    struct hash<__gnu_cxx::wrope>
     {
       size_t
-      operator()(const wrope& __str) const
+      operator()(const __gnu_cxx::wrope& __str) const
       {
 	size_t __size = __str.size();
 	if (0 == __size)
@@ -2933,8 +2939,8 @@ protected:
 	return 13 * __str[0] + 5 * __str[__size - 1] + __size;
       }
     };
-
-_GLIBCXX_END_NAMESPACE
+} // namespace tr1
+} // namespace std
 
 # include <ext/ropeimpl.h>
 
diff --git a/libstdc++-v3/include/precompiled/extc++.h b/libstdc++-v3/include/precompiled/extc++.h
index 7e8ef02..8d0b3de 100644
--- a/libstdc++-v3/include/precompiled/extc++.h
+++ b/libstdc++-v3/include/precompiled/extc++.h
@@ -40,8 +40,6 @@
 #include <ext/concurrence.h>
 #include <ext/debug_allocator.h>
 #include <ext/functional>
-#include <ext/hash_map>
-#include <ext/hash_set>
 #include <ext/iterator>
 #include <ext/malloc_allocator.h>
 #include <ext/memory>
diff --git a/libstdc++-v3/testsuite/17_intro/headers/all.cc b/libstdc++-v3/testsuite/17_intro/headers/all.cc
index c0ef4bf..662bad6 100644
--- a/libstdc++-v3/testsuite/17_intro/headers/all.cc
+++ b/libstdc++-v3/testsuite/17_intro/headers/all.cc
@@ -117,8 +117,6 @@
 #include <ext/debug_allocator.h>
 #include <ext/enc_filebuf.h>
 #include <ext/functional>
-#include <ext/hash_map>
-#include <ext/hash_set>
 #include <ext/iterator>
 #include <ext/malloc_allocator.h>
 #include <ext/memory>
diff --git a/libstdc++-v3/testsuite/17_intro/headers/all_c++200x_compatibility.cc b/libstdc++-v3/testsuite/17_intro/headers/all_c++200x_compatibility.cc
index 1052cd7..9410805 100644
--- a/libstdc++-v3/testsuite/17_intro/headers/all_c++200x_compatibility.cc
+++ b/libstdc++-v3/testsuite/17_intro/headers/all_c++200x_compatibility.cc
@@ -118,8 +118,6 @@
 #include <ext/debug_allocator.h>
 #include <ext/enc_filebuf.h>
 #include <ext/functional>
-#include <ext/hash_map>
-#include <ext/hash_set>
 #include <ext/iterator>
 #include <ext/malloc_allocator.h>
 #include <ext/memory>
diff --git a/libstdc++-v3/testsuite/17_intro/headers/all_pedantic_errors.cc b/libstdc++-v3/testsuite/17_intro/headers/all_pedantic_errors.cc
index 1325cc9..2b72a39 100644
--- a/libstdc++-v3/testsuite/17_intro/headers/all_pedantic_errors.cc
+++ b/libstdc++-v3/testsuite/17_intro/headers/all_pedantic_errors.cc
@@ -118,8 +118,6 @@
 #include <ext/debug_allocator.h>
 #include <ext/enc_filebuf.h>
 #include <ext/functional>
-#include <ext/hash_map>
-#include <ext/hash_set>
 #include <ext/iterator>
 #include <ext/malloc_allocator.h>
 #include <ext/memory>
diff --git a/libstdc++-v3/testsuite/ext/headers.cc b/libstdc++-v3/testsuite/ext/headers.cc
index af66604..a1bdbb3 100644
--- a/libstdc++-v3/testsuite/ext/headers.cc
+++ b/libstdc++-v3/testsuite/ext/headers.cc
@@ -1,7 +1,7 @@
 // { dg-do compile }
 // 1999-06-23 bkoz 
 
-// Copyright (C) 1999, 2001, 2003 Free Software Foundation, Inc.
+// Copyright (C) 1999, 2001, 2003, 2007 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
@@ -33,8 +33,6 @@
 #include <ext/debug_allocator.h>
 #include <ext/enc_filebuf.h>
 #include <ext/functional>
-#include <ext/hash_map>
-#include <ext/hash_set>
 #include <ext/iterator>
 #include <ext/malloc_allocator.h>
 #include <ext/memory>
diff --git a/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_map.hpp b/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_map.hpp
index 7bf1879..5db3611 100644
--- a/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_map.hpp
+++ b/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_map.hpp
@@ -41,7 +41,7 @@
 
 /**
  * @file native_hash_map.hpp
- * Contains an adapter to Dinkumware/SGI hash tables
+ * Contains an adapter to TR1 unordered containers.
  */
 
 #ifndef PB_DS_NATIVE_HASH_MAP_HPP
@@ -52,29 +52,15 @@
 #include <ext/pb_ds/detail/standard_policies.hpp>
 #include <native_type/assoc/native_hash_tag.hpp>
 #include <io/xml.hpp>
-
-// Default to using tr1.
-#define PB_DS_USE_TR1 1
-
-#ifdef PB_DS_USE_TR1
 #include <tr1/unordered_map>
-#else
-#include <ext/hash_map>
-#endif 
 
 namespace __gnu_pbds
 {
   namespace test
   {
-#ifdef PB_DS_USE_TR1
 #define PB_DS_BASE_C_DEC \
     std::tr1::__unordered_map<Key, Data, Hash_Fn, Eq_Fn, \
     typename Allocator::template rebind<std::pair<const Key, Data> >::other, Cache_Hash>
-#else 
-#define PB_DS_BASE_C_DEC \
-    __gnu_cxx::hash_map<Key, Data, Hash_Fn, Eq_Fn, \
-    typename Allocator::template rebind<std::pair<const Key, Data> >::other>
-#endif
 
     template<typename Key,
 	     typename Data,
@@ -82,10 +68,7 @@ namespace __gnu_pbds
 	     typename Hash_Fn = typename __gnu_pbds::detail::default_hash_fn<Key>::type,
 	     typename Eq_Fn = std::equal_to<Key>,
 	     typename Less_Fn = std::less<Key>,
-	     typename Allocator = std::allocator<char>
-#ifdef PB_DS_USE_TR1
-	     , bool Cache_Hash = false
-#endif
+	     typename Allocator = std::allocator<char>, bool Cache_Hash = false
 	     >
     class native_hash_map : public PB_DS_BASE_C_DEC
     {
@@ -104,18 +87,13 @@ namespace __gnu_pbds
       static std::string
       name()
       {
-#ifdef PB_DS_USE_TR1
         return std::string("n_hash_map_") 
                + (Cache_Hash ? std::string("cah") : std::string("ncah"));
-#else 
-        return std::string("n_hash_map_ncah");
-#endif
       }
 
       static std::string
       desc()
       {
-#ifdef PB_DS_USE_TR1
         const std::string cache_hash_desc =
 	make_xml_tag("cache_hash_code",
 		     "value",
@@ -123,9 +101,6 @@ namespace __gnu_pbds
 
         return make_xml_tag("type", "value", "std_tr1_unordered_map", 
 			    cache_hash_desc);
-#else 
-        return make_xml_tag("type", "value", "__gnucxx_hash_map");
-#endif 
       }
     };
 
diff --git a/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_multimap.hpp b/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_multimap.hpp
index d787bc9..b9d5aa1 100644
--- a/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_multimap.hpp
+++ b/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_multimap.hpp
@@ -1,6 +1,6 @@
 // -*- C++ -*-
 
-// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006, 2007 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
@@ -41,13 +41,14 @@
 
 /**
  * @file native_hash_multimap.hpp
- * Contains an adapter to Dinkumware/SGI hash tables
+ * Contains an adapter to TR1 unordered containers.
  */
 
 #ifndef PB_DS_NATIVE_HASH_MULTIMAP_HPP
 #define PB_DS_NATIVE_HASH_MULTIMAP_HPP
 
 #include <string>
+#include <tr1/unordered_map>
 #include <ext/hash_map>
 #include <ext/pb_ds/detail/type_utils.hpp>
 #include <ext/pb_ds/detail/standard_policies.hpp>
@@ -59,32 +60,29 @@ namespace __gnu_pbds
   namespace test
   {
 #define PB_DS_BASE_C_DEC \
-    __gnu_cxx::hash_multimap<Key, Data, Hash_Fn, Eq_Fn, Allocator>
+    std::tr1::unordered_multimap<Key, Data, Hash_Fn, Eq_Fn, Allocator>
 
     template<typename Key,
 	     typename Data,
 	     size_t Init_Size = 8,
-	     class Hash_Fn = typename __gnu_pbds::detail::default_hash_fn<Key>::type,
+       class Hash_Fn = typename __gnu_pbds::detail::default_hash_fn<Key>::type,
 	     class Eq_Fn = std::equal_to<Key>,
 	     class Less_Fn = std::less<Key>,
 	     class Allocator = std::allocator<char> >
     class native_hash_multimap : public PB_DS_BASE_C_DEC
     {
     private:
-      typedef PB_DS_BASE_C_DEC base_type;
+      typedef PB_DS_BASE_C_DEC 			base_type;
+      typedef std::pair<Key, Data> 		pair_type;
 
     public:
-      typedef native_hash_tag container_category;
-
-      typedef Allocator allocator;
-
-      typedef typename base_type::iterator iterator;
-
+      typedef native_hash_tag 			container_category;
+      typedef Allocator 			allocator;
+      typedef typename base_type::iterator 	iterator;
       typedef typename base_type::const_iterator const_iterator;
 
       typedef
-      typename Allocator::template rebind<
-	std::pair<Key, Data> >::other::const_reference
+      typename allocator::template rebind<pair_type>::other::const_reference
       const_reference;
 
       native_hash_multimap() : base_type(Init_Size)
@@ -95,7 +93,7 @@ namespace __gnu_pbds
       { }
 
       inline void
-      insert(typename base_type::const_reference r_val)
+      insert(const_reference r_val)
       {
         typedef std::pair<iterator, iterator> eq_range_t;
         eq_range_t f = base_type::equal_range(r_val.first);
@@ -148,9 +146,7 @@ namespace __gnu_pbds
 
       static std::string
       desc()
-      {
-        return make_xml_tag("type", "value", "__gnucxx_hash_multimap");
-      }
+      { return make_xml_tag("type", "value", "__gnucxx_hash_multimap"); }
     };
 
 #undef PB_DS_BASE_C_DEC
diff --git a/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_set.hpp b/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_set.hpp
index 52d1aa1..86ad248 100644
--- a/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_set.hpp
+++ b/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_set.hpp
@@ -41,7 +41,7 @@
 
 /**
  * @file native_hash_set.hpp
- * Contains an adapter to Dinkumware/SGI hash tables
+ * Contains an adapter to TR1 unordered containers.
  */
 
 #ifndef PB_DS_NATIVE_HASH_SET_HPP
@@ -52,39 +52,22 @@
 #include <ext/pb_ds/detail/standard_policies.hpp>
 #include <native_type/assoc/native_hash_tag.hpp>
 #include <io/xml.hpp>
-
-// Default to using tr1.
-#define PB_DS_USE_TR1 1
-
-#ifdef PB_DS_USE_TR1
 #include <tr1/unordered_set>
-#else 
-#include <ext/hash_set>
-#endif
 
 namespace __gnu_pbds
 {
   namespace test
   {
-#ifdef PB_DS_USE_TR1
 #define PB_DS_BASE_C_DEC \
     std::tr1::__unordered_set<Key, Hash_Fn, Eq_Fn, \
     typename Allocator::template rebind<Key>::other, Cache_Hash>
-#else
-#define PB_DS_BASE_C_DEC \
-    __gnu_cxx::hash_set<Key, Hash_Fn, Eq_Fn, \
-    typename Allocator::template rebind<Key>::other>
-#endif
 
     template<typename Key,
 	     size_t Init_Size = 8,
          typename Hash_Fn = typename __gnu_pbds::detail::default_hash_fn<Key>::type,
 	     typename Eq_Fn = std::equal_to<Key>,
 	     typename Less_Fn = std::less<Key>,
-	     typename Allocator = std::allocator<char>
-#ifdef PB_DS_USE_TR1
-	     , bool Cache_Hash = false
-#endif
+	     typename Allocator = std::allocator<char>, bool Cache_Hash = false
 	     >
     class native_hash_set : public PB_DS_BASE_C_DEC
     {
@@ -129,27 +112,19 @@ namespace __gnu_pbds
       static std::string
       name()
       {
-#ifdef PB_DS_USE_TR1
         return std::string("n_hash_set_") 
 	       + (Cache_Hash ? std::string("cah") : std::string("ncah"));
-#else
-        return std::string("n_hash_set_ncah");
-#endif
       }
 
       static std::string
       desc()
       {
-#ifdef PB_DS_USE_TR1
         const std::string cache_hash_desc =
 	make_xml_tag("cache_hash_code", "value",
 		     Cache_Hash ? std::string("true") : std::string("false"));
 
         return make_xml_tag("type", "value", "std_tr1_unordered_set", 
 			    cache_hash_desc);
-#else
-        return make_xml_tag("type", "value", "__gnucxx_hash_set");
-#endif
       }
     };
 
diff --git a/libstdc++-v3/testsuite/util/native_type/assoc/native_map.hpp b/libstdc++-v3/testsuite/util/native_type/assoc/native_map.hpp
index babe038..1be7ee5 100644
--- a/libstdc++-v3/testsuite/util/native_type/assoc/native_map.hpp
+++ b/libstdc++-v3/testsuite/util/native_type/assoc/native_map.hpp
@@ -41,7 +41,7 @@
 
 /**
  * @file native_map.hpp
- * Contains an adapter to Dinkumware/SGI tree tables
+ * Contains an adapter to std::map
  */
 
 #ifndef PB_DS_NATIVE_MAP_HPP
diff --git a/libstdc++-v3/testsuite/util/native_type/assoc/native_multimap.hpp b/libstdc++-v3/testsuite/util/native_type/assoc/native_multimap.hpp
index 2bec374..906fca3 100644
--- a/libstdc++-v3/testsuite/util/native_type/assoc/native_multimap.hpp
+++ b/libstdc++-v3/testsuite/util/native_type/assoc/native_multimap.hpp
@@ -41,7 +41,7 @@
 
 /**
  * @file native_multimap.hpp
- * Contains an adapter to Dinkumware/SGI tables
+ * Contains an adapter to std::multimap
  */
 
 #ifndef PB_DS_NATIVE_MULTIMAP_HPP
diff --git a/libstdc++-v3/testsuite/util/native_type/assoc/native_set.hpp b/libstdc++-v3/testsuite/util/native_type/assoc/native_set.hpp
index c605ac6..b25f2ba 100644
--- a/libstdc++-v3/testsuite/util/native_type/assoc/native_set.hpp
+++ b/libstdc++-v3/testsuite/util/native_type/assoc/native_set.hpp
@@ -41,7 +41,7 @@
 
 /**
  * @file native_set.hpp
- * Contains an adapter to Dinkumware/SGI tree tables
+ * Contains an adapter to std::set
  */
 
 #ifndef PB_DS_NATIVE_SET_HPP
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
index efd5997..4d639d3 100644
--- a/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp
+++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp
@@ -128,7 +128,8 @@ namespace __gnu_pbds
 
 
     template<typename It, bool Native>
-    class multimap_find_test : private __gnu_pbds::test::detail::timing_test_base
+    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)
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
index bbdc245..f35d952 100644
--- a/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp
+++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp
@@ -97,7 +97,7 @@ namespace __gnu_pbds
 	    {
 	      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));
+		cntnr.insert((typename Cntnr::const_reference)(*ins_it));
 	    }
 	}
 
@@ -108,7 +108,8 @@ namespace __gnu_pbds
     } // namespace detail
 
     template<typename It, bool Native>
-    class multimap_insert_test : private __gnu_pbds::test::detail::timing_test_base
+    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) 
@@ -122,7 +123,6 @@ namespace __gnu_pbds
     private:
       multimap_insert_test(const multimap_insert_test&);
 
-    private:
       const It m_ins_b;
       const size_t m_ins_vn;
       const size_t m_ins_vs;
diff --git a/libstdc++-v3/testsuite/util/testsuite_abi.cc b/libstdc++-v3/testsuite/util/testsuite_abi.cc
index 44e10ac..6efabec 100644
--- a/libstdc++-v3/testsuite/util/testsuite_abi.cc
+++ b/libstdc++-v3/testsuite/util/testsuite_abi.cc
@@ -30,10 +30,11 @@
 // Benjamin Kosnik  <bkoz@redhat.com>
 
 #include "testsuite_abi.h"
+#include <cstdlib>
 #include <sstream>
 #include <fstream>
 #include <iostream>
-#include <cstdlib>
+#include <vector>
 
 using namespace std;
 
diff --git a/libstdc++-v3/testsuite/util/testsuite_abi.h b/libstdc++-v3/testsuite/util/testsuite_abi.h
index 89825a8..a659ef4 100644
--- a/libstdc++-v3/testsuite/util/testsuite_abi.h
+++ b/libstdc++-v3/testsuite/util/testsuite_abi.h
@@ -33,7 +33,7 @@
 #include <stdexcept>
 #include <deque>
 #include <locale>
-#include <ext/hash_map>
+#include <tr1/unordered_map>
 #include <cxxabi.h>
 
 // Encapsulates symbol characteristics.
@@ -75,7 +75,7 @@ struct symbol
   init(std::string& data);
 };
 
-typedef __gnu_cxx::hash_map<std::string, symbol> 	symbol_objects;
+typedef std::tr1::unordered_map<std::string, symbol> 	symbol_objects;
 
 typedef std::deque<std::string>				symbol_names;
 
@@ -110,20 +110,3 @@ create_symbols(const char* file);
 
 const char*
 demangle(const std::string& mangled);
-
-
-// Specialization.
-namespace __gnu_cxx
-{
-  using namespace std;
-
-  template<> 
-    struct hash<string>
-    {
-      size_t operator()(const string& s) const 
-      { 
-	const collate<char>& c = use_facet<collate<char> >(locale::classic());
-	return c.hash(s.c_str(), s.c_str() + s.size());
-      }
-    }; 
-}
diff --git a/libstdc++-v3/testsuite/util/testsuite_common_types.h b/libstdc++-v3/testsuite/util/testsuite_common_types.h
index bcb36e7..b560ae3 100644
--- a/libstdc++-v3/testsuite/util/testsuite_common_types.h
+++ b/libstdc++-v3/testsuite/util/testsuite_common_types.h
@@ -1,7 +1,7 @@
 // -*- C++ -*-
 // typelist for the C++ library testsuite. 
 //
-// Copyright (C) 2005 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2007 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
@@ -47,8 +47,7 @@
 
 #include <map>
 #include <set>
-#include <ext/hash_map>
-#include <ext/hash_set>
+#include <tr1/functional>
 #include <tr1/unordered_map>
 #include <tr1/unordered_set>
 
@@ -160,7 +159,7 @@ namespace __gnu_test
       typedef typename append<a1, a2>::type type;
     };
 
-  // Typelists for map, set, hash_map, hash_set, unordered_set, unordered_map.
+  // Typelists for map, set, unordered_set, unordered_map.
   template<typename Tp, bool Thread>
     struct maps
     {
@@ -182,26 +181,6 @@ namespace __gnu_test
     };
 
   template<typename Tp, bool Thread>
-    struct hash_maps
-    {
-      typedef Tp			    		value_type;
-      typedef Tp 					key_type;
-      typedef __gnu_cxx::hash<key_type>      		hash_function;
-      typedef std::equal_to<key_type>      		equality_function;
-
-      template<typename Tl>
-        struct container
-	{
-	  typedef Tl 					allocator_type;
-	  typedef __gnu_cxx::hash_map<key_type, value_type, hash_function, equality_function, allocator_type>	type;
-	};
-
-      typedef allocator_policies<value_type, Thread>	allocator_types;
-      typedef typename allocator_types::type 		allocator_typelist;
-      typedef typename transform<allocator_typelist, container>::type type;
-    };
-
-  template<typename Tp, bool Thread>
     struct unordered_maps
     {
       typedef Tp			    		value_type;
@@ -242,26 +221,6 @@ namespace __gnu_test
     };
 
   template<typename Tp, bool Thread>
-    struct hash_sets
-    {
-      typedef Tp			    		value_type;
-      typedef Tp 					key_type;
-      typedef __gnu_cxx::hash<key_type>      		hash_function;
-      typedef std::equal_to<key_type>      		equality_function;
-
-      template<typename Tl>
-        struct container
-	{
-	  typedef Tl 					allocator_type;
-	  typedef __gnu_cxx::hash_set<key_type, hash_function, equality_function, allocator_type>	type;
-	};
-
-      typedef allocator_policies<key_type, Thread>	allocator_types;
-      typedef typename allocator_types::type 		allocator_typelist;
-      typedef typename transform<allocator_typelist, container>::type type;
-    };
-
-  template<typename Tp, bool Thread>
     struct unordered_sets
     {
       typedef Tp			    		value_type;
@@ -291,16 +250,12 @@ namespace __gnu_test
 
       typedef typename maps<value_type, Thread>::type map_typelist;
       typedef typename sets<value_type, Thread>::type set_typelist;
-      typedef typename hash_maps<value_type, Thread>::type hash_map_typelist;
-      typedef typename hash_sets<value_type, Thread>::type hash_set_typelist;
       typedef typename unordered_maps<value_type, Thread>::type unordered_map_typelist;
       typedef typename unordered_sets<value_type, Thread>::type unordered_set_typelist;
 
-      typedef typename append<map_typelist, hash_map_typelist>::type a1;
-      typedef typename append<a1, unordered_map_typelist>::type a2;
-      typedef typename append<set_typelist, hash_set_typelist>::type a3;
-      typedef typename append<a3, unordered_set_typelist>::type a4;
-      typedef typename append<a2, a4>::type type;
+      typedef typename append<map_typelist, unordered_map_typelist>::type a1;
+      typedef typename append<set_typelist, unordered_set_typelist>::type a2;
+      typedef typename append<a1, a2>::type type;
     };
 
 } // namespace __gnu_test