2008-06-06 Benjamin Kosnik <bkoz@redhat.com>

	* doc/xml/manual/using.xml: Outline exception topics.

	* include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp: Format.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	policy_access_fn_imps.hpp: Same.
	* include/ext/pb_ds/priority_queue.hpp: Same.
	* include/ext/throw_allocator.h: Same.

	* include/ext/pb_ds/tag_and_trait.hpp (string_tag): New tag.
	(sequence_tag): New tag. Doxygen markup fixes.

	* testsuite/lib/libstdc++.exp: Remove twister_ran_gen.cc source file.

	* testsuite/performance/ext/pb_ds/text_find_timing.cc: Fix
	comment typo, include paths, format.
	* testsuite/performance/ext/pb_ds/tree_text_insert_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/
	hash_random_int_erase_mem_usage.cc: Same.
	* testsuite/performance/ext/pb_ds/
	random_int_subscript_find_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/
	priority_queue_text_push_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/tree_split_join_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/random_int_find_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/multimap_text_insert_mem_usage.hpp
	* testsuite/performance/ext/pb_ds/multimap_text_find_timing.hpp
	* testsuite/performance/ext/pb_ds/
	priority_queue_random_int_push_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/priority_queue_text_modify_timing.hpp
	* testsuite/performance/ext/pb_ds/tree_order_statistics_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/
	priority_queue_text_push_pop_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/
	priority_queue_text_join_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/
	priority_queue_random_int_push_pop_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/
	random_int_subscript_insert_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/tree_text_lor_find_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/multimap_text_insert_timing.hpp
	* testsuite/performance/ext/pb_ds/
	priority_queue_text_pop_mem_usage.cc: Same.
	* testsuite/performance/ext/pb_ds/
	hash_zlob_random_int_find_timing.cc: Same.
	* testsuite/ext/pb_ds/regression/hash_data_map_rand.cc: Same.
	* testsuite/ext/pb_ds/regression/trie_data_map_rand.cc: Same.
	* testsuite/ext/pb_ds/regression/list_update_no_data_map_rand.cc: Same.
	* testsuite/ext/pb_ds/regression/tree_no_data_map_rand.cc: Same.
	* testsuite/ext/pb_ds/regression/list_update_data_map_rand.cc: Same.
	* testsuite/ext/pb_ds/regression/hash_no_data_map_rand.cc: Same.
	* testsuite/ext/pb_ds/regression/priority_queue_rand.cc: Same.
	* testsuite/ext/pb_ds/regression/tree_data_map_rand.cc: Same.
	* testsuite/ext/pb_ds/regression/trie_no_data_map_rand.cc: Same.
	* testsuite/util/regression/trait/priority_queue/trait.hpp: Same.
	* testsuite/util/regression/trait/erase_if_fn.hpp: Same.
	* testsuite/util/regression/trait/assoc/native_type_trait.hpp: Same.
	* testsuite/util/regression/trait/assoc/node_update_trait.hpp: Same.
	* testsuite/util/regression/trait/assoc/get_set_load_trait.hpp: Same.
	* testsuite/util/regression/trait/assoc/get_set_loads_trait.hpp: Same.
	* testsuite/util/regression/trait/assoc/trait.hpp: Same.
	* testsuite/util/regression/trait/assoc/resize_trait.hpp: Same.
	* testsuite/util/regression/trait/assoc/type_trait.hpp: Same.
	* testsuite/util/regression/trait/assoc/to_string.hpp: Same.
	* testsuite/util/regression/basic_type.hpp: Same.
	* testsuite/util/common_type/priority_queue/string_form.hpp: Same.
	* testsuite/util/common_type/priority_queue/detail/
	ds_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	resize_policy_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	trigger_policy_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	comb_hash_fn_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/ds_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	size_policy_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	probe_fn_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	list_update_policy_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	store_hash_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/native_set.hpp: Same.
	* testsuite/util/io/prog_bar.cc: Same.

	* testsuite/util/regression/rand/io: Remove.
	* testsuite/util/regression/rand/io/priority_queue: Same.
	* testsuite/util/regression/rand/io/assoc: Same.
	* testsuite/util/regression/rand/io/priority_queue/
	xml_formatter.hpp: Consolidate this...
	* testsuite/util/regression/rand/io/assoc/xml_formatter.hpp: ...this
	* testsuite/util/regression/rand/io/xml_formatter.hpp: ... and this
	* testsuite/util/regression/rand/xml_formatter.hpp: ...here.

	* testsuite/util/regression/rand/priority_queue/
	container_rand_regression_test.hpp:To ...
	container_rand_regression_test.h: ... this.
	* testsuite/util/regression/rand/priority_queue/detail/*.hpp:To ...
	* testsuite/util/regression/rand/priority_queue/
	container_rand_regression_test.tcc: ... this.
	PB_DS_THROW_IF_FAIL: Change to _GLIBCXX_THROW_IF, adjust predicate.
	PB_DS_SET_DESTRUCT_PRINT: Fold inline.
	PB_DS_CANCEL_DESTRUCT_PRINT: Fold inline.
	* testsuite/util/regression/rand/priority_queue/
	rand_regression_test.hpp: Adjust includes.

	* testsuite/util/regression/rand/assoc/
	container_rand_regression_test.hpp: To ...
	* testsuite/util/regression/rand/assoc/
	container_rand_regression_test.h: ... this.
	* testsuite/util/regression/rand/assoc/detail/*.hpp:To ...
	* testsuite/util/regression/rand/assoc/
	container_rand_regression_test.tcc: ...this.
	* testsuite/util/regression/rand/assoc/rand_regression_test.hpp: Adjust
	includes.

	* testsuite/util/regression/priority_queue: Remove.
	* testsuite/util/regression/assoc: Remove.
	* testsuite/util/regression/priority_queue/
	common_type.hpp: Consolidate this...
	* testsuite/util/regression/assoc/common_type.hpp: ... and this
	* testsuite/util/regression/common_type.hpp: ...here.

	* testsuite/util/rng: Remove.
	* testsuite/util/rng/twister_rand_gen.cc: Consolidate...
	* testsuite/util/rng/twister_rand_gen.hpp: ... and this
	* testsuite/util/testsuite_rng.h: ...here.

	* testsuite/util/native_type/priority_queue: Remove.
	* testsuite/util/native_type/priority_queue/
	native_priority_queue.hpp: To...
	* testsuite/util/native_type/native_priority_queue.hpp: ...here.

	* testsuite/util/native_type/assoc: Remove.
	* testsuite/util/native_type/assoc/native_multimap.hpp: To...
	* testsuite/util/native_type/assoc/native_tree_tag.hpp: To...
	* testsuite/util/native_type/assoc/native_hash_multimap.hpp: To...
	* testsuite/util/native_type/assoc/native_set.hpp: To...
	* testsuite/util/native_type/assoc/native_map.hpp: To...
	* testsuite/util/native_type/assoc/native_hash_set.hpp: To...
	* testsuite/util/native_type/assoc/native_hash_tag.hpp: To...
	* testsuite/util/native_type/assoc/native_hash_map.hpp: To...
	* testsuite/util/native_type/native_multimap.hpp: ...here.
	* testsuite/util/native_type/native_tree_tag.hpp: ...here.
	* testsuite/util/native_type/native_hash_multimap.hpp: ...here.
	* testsuite/util/native_type/native_set.hpp: ...here.
	* testsuite/util/native_type/native_map.hpp: ...here.
	* testsuite/util/native_type/native_hash_set.hpp: ...here.
	* testsuite/util/native_type/native_hash_tag.hpp: ...here.
	* testsuite/util/native_type/native_hash_map.hpp: ...here.

	* testsuite/util/common_type/priority_queue/common_type.hpp:
	Make include guard distinct.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@136497 138bc75d-0d04-0410-961f-82ee72b054a4

5 files changed, 62 insertions, 93 deletions

diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
index 489ccc12465..a32bd723415 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
@@ -50,14 +50,11 @@ PB_DS_CLASS_C_DEC::
 push(const_reference r_val)
 {
   _GLIBCXX_DEBUG_ONLY(assert_valid();)
-
-    insert_value(r_val, s_no_throw_copies_ind);
-
-  std::push_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this));
-
+  insert_value(r_val, s_no_throw_copies_ind);
+  std::push_heap(m_a_entries, m_a_entries + m_size, 
+		 static_cast<entry_cmp&>(*this));
   _GLIBCXX_DEBUG_ONLY(assert_valid();)
-
-    return point_iterator(m_a_entries);
+  return point_iterator(m_a_entries);
 }
 
 PB_DS_CLASS_T_DEC
@@ -76,15 +73,10 @@ PB_DS_CLASS_C_DEC::
 insert_value(const_reference r_val, false_type)
 {
   resize_for_insert_if_needed();
-
   pointer p_new = s_value_allocator.allocate(1);
-
   cond_dealtor_t cond(p_new);
-
   new (p_new) value_type(r_val);
-
   cond.set_no_action();
-
   m_a_entries[m_size++] = p_new;
 }
 
@@ -94,7 +86,6 @@ PB_DS_CLASS_C_DEC::
 insert_entry(entry e)
 {
   resize_for_insert_if_needed();
-
   m_a_entries[m_size++] = e;
 }
 
@@ -106,23 +97,15 @@ resize_for_insert_if_needed()
   if (!resize_policy::resize_needed_for_grow(m_size))
     {
       _GLIBCXX_DEBUG_ASSERT(m_size < m_actual_size);
-
       return;
     }
 
-  const size_type new_actual_size =
-    resize_policy::get_new_size_for_grow();
-
+  const size_type new_actual_size = resize_policy::get_new_size_for_grow();
   entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size);
-
   resize_policy::notify_grow_resize();
-
   std::copy(m_a_entries, m_a_entries + m_size, a_new_entries);
-
   s_entry_allocator.deallocate(m_a_entries, m_actual_size);
-
   m_actual_size = new_actual_size;
-
   m_a_entries = a_new_entries;
 }
 
@@ -132,13 +115,10 @@ PB_DS_CLASS_C_DEC::
 modify(point_iterator it, const_reference r_new_val)
 {
   _GLIBCXX_DEBUG_ONLY(assert_valid();)
-
-    swap_value_imp(it.m_p_e, r_new_val, s_no_throw_copies_ind);
-
+  swap_value_imp(it.m_p_e, r_new_val, s_no_throw_copies_ind);
   fix(it.m_p_e);
-
   _GLIBCXX_DEBUG_ONLY(assert_valid();)
-    }
+}
 
 PB_DS_CLASS_T_DEC
 void
@@ -146,55 +126,44 @@ PB_DS_CLASS_C_DEC::
 fix(entry_pointer p_e)
 {
   size_type i = p_e - m_a_entries;
-
-  if (i > 0&&  entry_cmp::operator()(m_a_entries[parent(i)], m_a_entries[i]))
+  if (i > 0 && entry_cmp::operator()(m_a_entries[parent(i)], m_a_entries[i]))
     {
       size_type parent_i = parent(i);
-
-      while (i > 0&&  entry_cmp::operator()(m_a_entries[parent_i], m_a_entries[i]))
+      while (i > 0 
+	     && entry_cmp::operator()(m_a_entries[parent_i], m_a_entries[i]))
         {
 	  std::swap(m_a_entries[i], m_a_entries[parent_i]);
-
 	  i = parent_i;
-
 	  parent_i = parent(i);
         }
 
       _GLIBCXX_DEBUG_ONLY(assert_valid();)
-
-        return;
+      return;
     }
 
   while (i < m_size)
     {
       const size_type left_child_i = left_child(i);
       const size_type right_child_i = right_child(i);
-
       _GLIBCXX_DEBUG_ASSERT(right_child_i > left_child_i);
-
-      const bool smaller_than_left_child =
-	left_child_i < m_size&& 
+      const bool smaller_than_left_child = left_child_i < m_size && 
 	entry_cmp::operator()(m_a_entries[i], m_a_entries[left_child_i]);
 
-      const bool smaller_than_right_child =
-	right_child_i < m_size&& 
+      const bool smaller_than_right_child = right_child_i < m_size && 
 	entry_cmp::operator()(m_a_entries[i], m_a_entries[right_child_i]);
 
-      const bool swap_with_r_child = smaller_than_right_child&& (!smaller_than_left_child ||
-								 entry_cmp::operator()(m_a_entries[left_child_i], m_a_entries[right_child_i]));
+      const bool swap_with_r_child = smaller_than_right_child && (!smaller_than_left_child || entry_cmp::operator()(m_a_entries[left_child_i], m_a_entries[right_child_i]));
 
-      const bool swap_with_l_child = !swap_with_r_child&&  smaller_than_left_child;
+      const bool swap_with_l_child = !swap_with_r_child && smaller_than_left_child;
 
       if (swap_with_l_child)
         {
 	  std::swap(m_a_entries[i], m_a_entries[left_child_i]);
-
 	  i = left_child_i;
         }
       else if (swap_with_r_child)
         {
 	  std::swap(m_a_entries[i], m_a_entries[right_child_i]);
-
 	  i = right_child_i;
         }
       else
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp
index b7503c2caf4..e17c53c539d 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp
@@ -48,15 +48,11 @@ PB_DS_CLASS_T_DEC
 Cmp_Fn& 
 PB_DS_CLASS_C_DEC::
 get_cmp_fn()
-{
-  return (*this);
-}
+{ return *this; }
 
 PB_DS_CLASS_T_DEC
 const Cmp_Fn& 
 PB_DS_CLASS_C_DEC::
 get_cmp_fn() const
-{
-  return (*this);
-}
+{ return *this; }
 
diff --git a/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp b/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp
index 3433f5116fe..3b31874dc4f 100644
--- a/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp
@@ -59,7 +59,7 @@ namespace __gnu_pbds
 	   typename Tag = pairing_heap_tag,
 	   typename Allocator = std::allocator<char> >
   class priority_queue 
-    : public detail::priority_queue_base_dispatch<Value_Type,Cmp_Fn,Tag,Allocator>::type
+  : public detail::priority_queue_base_dispatch<Value_Type,Cmp_Fn,Tag,Allocator>::type
   {
   private:
     typedef typename detail::priority_queue_base_dispatch<Value_Type,Cmp_Fn,Tag,Allocator>::type base_type;
@@ -114,7 +114,7 @@ namespace __gnu_pbds
     priority_queue& 
     operator=(const priority_queue& other)
     {
-      if (this !=& other)
+      if (this != &other)
 	{
 	  priority_queue tmp(other);
 	  swap(tmp);
diff --git a/libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp b/libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp
index bb39d17931f..5b5a2f34377 100644
--- a/libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp
@@ -1,6 +1,6 @@
 // -*- C++ -*-
 
-// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006, 2008 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
@@ -89,70 +89,77 @@ namespace __gnu_pbds
   { };
 
 
-  // A mapped-policy indicating that an associative container is a set.
+  /// A mapped-policy indicating that an associative container is a set.
   // XXX should this be a trait of the form is_set<T> ??
   struct null_mapped_type { };
 
 
-  // Base data structure tag.
+  /// Base data structure tag.
   struct container_tag
   { };
 
-  // Basic associative-container.
+  /// Basic string container, inclusive of strings, ropes, etc.
+  struct string_tag : public container_tag { };
+
+  /// Basic sequence.
+  struct sequence_tag : public container_tag { };
+
+  /// Basic associative-container.
   struct associative_container_tag : public container_tag { };
 
-  // Basic hash.
+  /// Basic hash.
   struct basic_hash_tag : public associative_container_tag { };
 
-  // Collision-chaining hash.
+  /// Collision-chaining hash.
   struct cc_hash_tag : public basic_hash_tag { };
 
-  // General-probing hash.
+  /// General-probing hash.
   struct gp_hash_tag : public basic_hash_tag { };
 
-  // Basic tree.
+  /// Basic tree.
   struct basic_tree_tag : public associative_container_tag { };
 
-  // tree.
+  /// tree.
   struct tree_tag : public basic_tree_tag { };
 
-  // Red-black tree.
+  /// Red-black tree.
   struct rb_tree_tag : public tree_tag { };
 
-  // Splay tree.
+  /// Splay tree.
   struct splay_tree_tag : public tree_tag { };
 
-  // Ordered-vector tree.
+  /// Ordered-vector tree.
   struct ov_tree_tag : public tree_tag { };
 
-  // trie.
+  /// trie.
   struct trie_tag : public basic_tree_tag { };
 
-  // PATRICIA trie.
+  /// PATRICIA trie.
   struct pat_trie_tag : public trie_tag { };
 
-  // List-update.
+  /// List-update.
   struct list_update_tag : public associative_container_tag { };
 
-  // Basic priority-queue.
+  /// Basic priority-queue.
   struct priority_queue_tag : public container_tag { };
 
-  // Pairing-heap.
+  /// Pairing-heap.
   struct pairing_heap_tag : public priority_queue_tag { };
 
-  // Binomial-heap.
+  /// Binomial-heap.
   struct binomial_heap_tag : public priority_queue_tag { };
 
-  // Redundant-counter binomial-heap.
+  /// Redundant-counter binomial-heap.
   struct rc_binomial_heap_tag : public priority_queue_tag { };
 
-  // Binary-heap (array-based).
+  /// Binary-heap (array-based).
   struct binary_heap_tag : public priority_queue_tag { };
 
-  // Thin heap.
+  /// Thin heap.
   struct thin_heap_tag : public priority_queue_tag { };
 
 
+  /// Base traits type for containers.
   template<typename Tag>
   struct container_traits_base;
 
@@ -337,7 +344,8 @@ namespace __gnu_pbds
       };
   };
 
-  
+
+  /// container_traits
   // See Matt Austern for the name, S. Meyers MEFC++ #2, others.
   template<typename Cntnr>
   struct container_traits 
diff --git a/libstdc++-v3/include/ext/throw_allocator.h b/libstdc++-v3/include/ext/throw_allocator.h
index a5aa725cdce..36dc3c0f0da 100644
--- a/libstdc++-v3/include/ext/throw_allocator.h
+++ b/libstdc++-v3/include/ext/throw_allocator.h
@@ -65,19 +65,18 @@
 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
 
   class twister_rand_gen
-  {
+  {    
+  private:
+    std::tr1::mt19937 _M_generator;
+
   public:
-    twister_rand_gen(unsigned int seed = 
-		     static_cast<unsigned int>(std::time(0)));
+    twister_rand_gen(unsigned int s = static_cast<unsigned int>(std::time(0)));
     
     void
     init(unsigned int);
     
     double
     get_prob();
-    
-  private:
-    std::tr1::mt19937 _M_generator;
   };
 
   /// Thown by throw_allocator.
@@ -116,8 +115,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
 
     struct group_throw_prob_adjustor
     {
-      group_throw_prob_adjustor(size_t size) 
-      : _M_throw_prob_orig(_S_throw_prob)
+      group_throw_prob_adjustor(size_t size) : _M_throw_prob_orig(_S_throw_prob)
       {
 	_S_throw_prob =
 	  1 - std::pow(double(1 - _S_throw_prob), double(0.5 / (size + 1)));
@@ -297,14 +295,10 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
   twister_rand_gen::
   get_prob()
   {
-    const double eng_min = _M_generator.min();
-    const double eng_range =
-      static_cast<const double>(_M_generator.max() - eng_min);
-
-    const double eng_res =
-      static_cast<const double>(_M_generator() - eng_min);
-
-    const double ret = eng_res / eng_range;
+    const double min = _M_generator.min();
+    const double res = static_cast<const double>(_M_generator() - min);
+    const double range = static_cast<const double>(_M_generator.max() - min);
+    const double ret = res / range;
     _GLIBCXX_DEBUG_ASSERT(ret >= 0 && ret <= 1);
     return ret;
   }
@@ -397,7 +391,9 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
     while (it != _S_map.end())
       {
 	if (it->second.first == label)
-	  print_to_string(found, *it);
+	  {
+	    print_to_string(found, *it);
+	  }
 	++it;
       }