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.

3 files changed, 1305 insertions, 0 deletions

diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.h b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.h
new file mode 100644
index 000000000..828541ce7
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.h
@@ -0,0 +1,265 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2008, 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 container_rand_regression_test.h
+ * Contains a random regression test for a specific container type.
+ */
+
+#ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_H
+#define PB_DS_CONTAINER_RAND_REGRESSION_TEST_H
+
+#include <algorithm>
+#include <string>
+#include <sstream>
+#include <utility>
+#include <cassert>
+#include <regression/basic_type.hpp>
+#include <ext/pb_ds/priority_queue.hpp>
+#include <io/prog_bar.hpp>
+#include <testsuite_rng.h>
+#include <common_type/priority_queue/string_form.hpp>
+#include <regression/rand/xml_formatter.hpp>
+#include <regression/trait/priority_queue/trait.hpp>
+
+namespace __gnu_pbds
+{
+namespace test
+{
+namespace detail
+{
+  // Rand test specialized for a specific container.
+  template<typename Cntnr>
+    class container_rand_regression_test
+    {
+    private:
+      typedef Cntnr 						cntnr;
+      typedef typename cntnr::allocator_type 			allocator_type;
+      typedef typename cntnr::size_type 			size_type;
+      typedef twister_rand_gen 					gen;
+      typedef basic_type 					value_type;
+      typedef native_priority_queue<std::string, true>		native_type;
+      typedef regression_test_traits<cntnr> 			test_traits;
+
+      enum op
+	{
+	  insert_op,
+	  modify_op,
+	  erase_op,
+	  clear_op,
+	  other_op
+	};
+
+      op
+      get_next_op();
+
+      size_t
+      get_next_sub_op(size_t max);
+
+      static void
+      defs();
+
+      static void
+      value_defs();
+
+      static void
+      ds_defs();
+
+      static void
+      iterator_defs();
+
+      static void
+      policy_defs();
+
+      void
+      policy_access();
+
+      void
+      it_copy();
+
+      void
+      it_assign();
+
+      bool
+      default_constructor();
+
+      void
+      swap();
+
+      bool
+      copy_constructor();
+
+      bool
+      assignment_operator();
+
+      bool
+      it_constructor();
+
+      bool
+      push();
+
+      bool
+      modify();
+
+      bool
+      pop();
+
+      bool
+      erase_if();
+
+      bool
+      erase_it();
+
+      bool
+      clear();
+
+      bool
+      split_join();
+
+      void
+      cmp(const Cntnr& r_container, const native_type& r_native_c, 
+	  const std::string& r_call_fn);
+
+      void
+      print_container(const native_type& r_cnt, 
+		      std::ostream& r_os = std::cerr) const;
+
+      void
+      print_container(const cntnr& r_cnt, 
+		      std::ostream& r_os = std::cerr) const;
+
+      struct destructor_printer
+      {
+	destructor_printer(const std::string& r_msg) 
+	: m_msg(r_msg), m_print(true) { }
+
+	void
+	cancel()
+	{ m_print = false; }
+
+	~destructor_printer()
+	{
+	  if (m_print)
+	    {
+	      std::cerr << std::endl << "Uncaught exception: " << std::endl 
+			<< m_msg << std::endl;
+	    }
+	}
+
+	const std::string 	m_msg;
+	bool 			m_print;
+      };
+
+      const unsigned long 	m_seed;
+      const size_t 		m_n;
+      const size_t 		m_m;
+      const double 		m_tp;
+      const double 		m_ip;
+      const double 		m_dp;
+      const double 		m_ep;
+      const double 		m_cp;
+      const double 		m_mp;
+      const bool 		m_disp;
+      twister_rand_gen 		m_g;
+      Cntnr* 			m_p_c;
+      native_type 		m_native_c;
+      allocator_type 		m_alloc;
+      size_t 			m_i;
+
+    public:
+      container_rand_regression_test(unsigned long seed, size_t n, size_t m, 
+				     double tp, double ip, double dp, 
+				     double ep, double cp, double mp, 
+				     bool disp);
+
+      virtual
+      ~container_rand_regression_test();
+      
+      void
+      operator()();
+  };
+
+
+#ifdef PB_DS_REGRESSION_TRACE
+# define PB_DS_TRACE(X) std::cerr << X << std::endl
+#else 
+# define PB_DS_TRACE(X)
+#endif
+
+#define PB_DS_CLASS_T_DEC			\
+      template<typename Cntnr>
+
+#define PB_DS_CLASS_C_DEC				\
+      container_rand_regression_test<Cntnr>
+
+#define PB_DS_COND_COMPARE(L, R)		\
+      if (m_g.get_prob() < m_mp)		\
+        cmp(L, R, __FUNCTION__);
+
+#define PB_DS_RUN_MTHD(MTHD)			\
+      {						\
+        bool done = false;			\
+        while (!done)				\
+	  done = MTHD();			\
+      }
+
+#define _GLIBCXX_THROW_IF_(PRED, MORE, P_C, P_NC, F, L)			\
+      if (PRED)								\
+	{								\
+	  std::cerr << "Failure at " << F << ": " << L << std::endl;	\
+	  std::cerr << MORE << std::endl;				\
+	  std::cerr << "container:" << std::endl;			\
+	  print_container(*(P_C));					\
+	  std::cerr << std::endl;					\
+	  std::cerr << "native container:" << std::endl;		\
+	  print_container(*(P_NC));					\
+	  std::cerr << std::endl;					\
+	  throw std::logic_error("pbds throw if failed");		\
+	}
+
+#define _GLIBCXX_THROW_IF(PRED, MORE, P_C, P_NC)			\
+      _GLIBCXX_THROW_IF_(PRED, MORE, P_C, P_NC, __FILE__, __LINE__)
+
+#include <regression/rand/priority_queue/container_rand_regression_test.tcc>
+
+#undef PB_DS_COND_COMPARE
+#undef PB_DS_RUN_MTHD
+#undef PB_DS_CLASS_T_DEC
+#undef PB_DS_CLASS_C_DEC
+#undef _GLIBCXX_THROW_IF_
+#undef _GLIBCXX_THROW_IF
+#undef PB_DS_TRACE
+
+} // namespace detail
+} // namespace test
+} // namespace __gnu_pbds
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc
new file mode 100644
index 000000000..e929f3533
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc
@@ -0,0 +1,838 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2008, 2009, 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// 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 container_rand_regression_test.tcc
+ * Contains a random regression test for a specific container type.
+ */
+
+#ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC
+#define PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC
+
+  // Constructor, copy constructor, assignment and destructor.
+PB_DS_CLASS_T_DEC
+PB_DS_CLASS_C_DEC::
+container_rand_regression_test(unsigned long seed, size_t n, size_t m, 
+			       double tp, double ip, double dp, double ep, 
+			       double cp, double mp, bool disp) 
+: m_seed(seed == 0 ? twister_rand_gen::get_time_determined_seed(): seed),
+  m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_dp(dp), m_ep(ep), m_cp(cp),
+  m_mp(mp), m_disp(disp), m_p_c(0)
+{ }
+
+PB_DS_CLASS_T_DEC
+PB_DS_CLASS_C_DEC::
+~container_rand_regression_test()
+{ }
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+default_constructor()
+{
+  PB_DS_TRACE("default_constructor");
+  bool done = true;
+  m_alloc.set_probability(m_tp);
+
+  try
+    {
+      m_p_c = new Cntnr;
+    }
+  catch(__gnu_cxx::forced_error&)
+    {
+      done = false;
+    }
+
+  if (m_p_c)
+    PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+
+  return done;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+swap()
+{
+  PB_DS_TRACE("swap");
+  m_alloc.set_probability(0);
+  Cntnr* p_c = new Cntnr;
+  m_alloc.set_probability(1);
+  p_c->swap(*m_p_c);
+  std::swap(p_c, m_p_c);
+  delete p_c;
+  PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+copy_constructor()
+{
+  PB_DS_TRACE("copy_constructor");
+  bool done = true;
+  Cntnr* p_c = 0;
+  m_alloc.set_probability(m_tp);
+
+  typedef typename allocator_type::group_adjustor adjustor;
+  adjustor adjust(m_p_c->size());
+
+  try
+    {
+      p_c = new Cntnr(*m_p_c);
+      std::swap(p_c, m_p_c);
+    }
+  catch(__gnu_cxx::forced_error&)
+    {
+      done = false;
+    }
+
+  delete p_c;
+  PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+  return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+assignment_operator()
+{
+  PB_DS_TRACE("assignment operator");
+  bool done = true;
+  Cntnr* p_c = 0;
+  m_alloc.set_probability(m_tp);
+
+  typedef typename allocator_type::group_adjustor adjustor;
+  adjustor adjust(m_p_c->size());
+
+  try
+    {
+      p_c = new Cntnr();
+      *p_c = *m_p_c;
+      std::swap(p_c, m_p_c);
+    }
+  catch(__gnu_cxx::forced_error&)
+    {
+      done = false;
+    }
+
+  delete p_c;
+  PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+  return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+it_constructor()
+{
+  bool done = true;
+  Cntnr* p_c = 0;
+  m_alloc.set_probability(m_tp);
+  typedef typename allocator_type::group_adjustor adjustor;
+  adjustor adjust(m_p_c->size());
+
+  try
+    {
+      switch(get_next_sub_op(3))
+        {
+        case 0:
+	  p_c = new Cntnr(m_p_c->get_cmp_fn());
+	  m_native_c.clear();
+	  break;
+        case 1:
+	  p_c = new Cntnr(m_p_c->begin(), m_p_c->end());
+	  break;
+        case 2:
+	  p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_cmp_fn());
+	  break;
+        default:
+	  _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+        };
+
+      std::swap(p_c, m_p_c);
+    }
+  catch(__gnu_cxx::forced_error&)
+    {
+      done = false;
+    }
+
+  delete p_c;
+  PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+  return done;
+}
+
+
+  // Compare.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+cmp(const Cntnr& c, const native_type& native, const std::string& callfn)
+{
+  destructor_printer notify(__FUNCTION__);
+
+  try
+    {
+      m_alloc.set_probability(1);
+      
+      const size_t size = c.size();
+      const size_t native_size = native.size();
+      _GLIBCXX_THROW_IF(size != native_size, size << " " << native_size,
+			&c, &native);
+      
+      const bool empty = c.empty();
+      const bool native_empty = native.empty();
+      _GLIBCXX_THROW_IF(empty != native_empty, empty << " " << native_empty, 
+			&c, &native);
+      
+      const size_t it_size = std::distance(c.begin(), c.end());
+      _GLIBCXX_THROW_IF(it_size != size, it_size << " " << size, &c, &native);
+      
+      if (!c.empty())
+	{
+	  const std::string native_top = native.top();
+	  const std::string top = test_traits::native_value(c.top());
+	  const bool top_smaller = std::less<std::string>()(top, native_top);
+	  const bool top_larger = std::less<std::string>()(native_top, top);
+	  
+	  if (top_smaller || top_larger)
+	    _GLIBCXX_THROW_IF(true, top << " " << native_top, &c, &native);
+	}
+    }
+  catch(...)
+    {
+      _GLIBCXX_THROW_IF(true, "call-fn: " + callfn, &c, &native);
+    }
+  
+  notify.cancel();
+}
+
+  // Operators.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+operator()()
+{
+  typedef xml_result_set_regression_formatter formatter_type;
+  formatter_type* p_fmt = 0;
+  if (m_disp)
+    p_fmt = new formatter_type(string_form<Cntnr>::name(),
+			       string_form<Cntnr>::desc());
+
+  m_g.init(m_seed);
+  m_alloc.seed(m_seed);
+
+  // The __throw_allocator::_S_label defaults to 0, so to make things
+  // easier and more precise when debugging, start at 1.
+  const size_t starting_label(1);
+
+  try
+    {
+      prog_bar pb(m_n, std::cout, m_disp);
+
+      for (m_i = starting_label; m_i <= m_n; ++m_i)
+        {
+	  PB_DS_TRACE("Op #" << m_i);
+
+	  // Track allocation from this point only.
+	  allocator_type::set_label(m_i);
+	  switch(m_i)
+            {
+            case 1:
+	      PB_DS_RUN_MTHD(default_constructor);
+	      break;
+            case 2:
+	      defs();
+	      break;
+            case 3:
+	      policy_access();
+	      break;
+            case 4:
+	      it_copy();
+	      break;
+            case 5:
+	      it_assign();
+	      break;
+            default:
+	      switch(get_next_op())
+                {
+                case insert_op:
+		  PB_DS_RUN_MTHD(push)
+                    break;
+                case modify_op:
+		  PB_DS_RUN_MTHD(modify)
+                    break;
+                case erase_op:
+		  switch(get_next_sub_op(3))
+                    {
+                    case 0:
+		      PB_DS_RUN_MTHD(pop)
+                        break;
+                    case 1:
+		      PB_DS_RUN_MTHD(erase_if)
+                        break;
+                    case 2:
+		      PB_DS_RUN_MTHD(erase_it)
+                        break;
+                    default:
+		      _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+                    }
+		  break;
+                case clear_op:
+		  PB_DS_RUN_MTHD(clear)
+                    break;
+                case other_op:
+		  switch(get_next_sub_op(5))
+                    {
+                    case 0:
+		      swap();
+		      break;
+                    case 1:
+		      PB_DS_RUN_MTHD(copy_constructor)
+                        break;
+                    case 2:
+		      PB_DS_RUN_MTHD(it_constructor)
+                        break;
+                    case 3:
+		      PB_DS_RUN_MTHD(assignment_operator)
+                        break;
+                    case 4:
+		      PB_DS_RUN_MTHD(split_join)
+                        break;
+                    default:
+		      _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+                    }
+		  break;
+                default:
+		  _GLIBCXX_THROW_IF(true, "", m_p_c,  &m_native_c);
+                };
+            }
+	  pb.inc();
+        }
+    }
+  catch (...)
+    {
+      std::cerr << "Failed at index " << m_i << std::endl;
+      delete m_p_c;
+      throw;
+    }
+
+  // Clean up, then check for allocation by special label, set above.
+  allocator_type::set_label(0);
+  delete m_p_c;
+
+  try 
+    { 
+      for (size_t n = starting_label; n <= m_n; ++n)
+	m_alloc.check_allocated(n); 
+    }
+  catch (std::logic_error& obj)
+    {
+      // On fail, check_allocated should throw std::logic_error.
+      std::cerr << obj.what() << std::endl;
+      std::cerr << typeid(Cntnr).name() << std::endl;
+      throw;
+    }
+
+  // Reset throw probability.
+  m_alloc.set_probability(0);
+
+  if (m_disp)
+    {
+      std::cout << std::endl;
+      delete p_fmt;
+    }
+}
+
+PB_DS_CLASS_T_DEC
+typename PB_DS_CLASS_C_DEC::op
+PB_DS_CLASS_C_DEC::
+get_next_op()
+{
+  const double prob = m_g.get_prob();
+
+  if (prob < m_ip)
+    return insert_op;
+
+  if (prob < m_ip + m_dp)
+    return modify_op;
+
+  if (prob < m_ip + m_dp + m_ep)
+    return erase_op;
+
+  if (prob < m_ip + m_dp + m_ep + m_cp)
+    return clear_op;
+
+  _GLIBCXX_THROW_IF(prob > 1, prob, m_p_c, &m_native_c);
+  return other_op;
+}
+
+PB_DS_CLASS_T_DEC
+size_t
+PB_DS_CLASS_C_DEC::
+get_next_sub_op(size_t max)
+{
+  const double p = m_g.get_prob();
+  const double delta = 1 / static_cast<double>(max);
+  size_t i = 0;
+  while (true)
+    if (p <= (i + 1) * delta)
+      {
+	_GLIBCXX_THROW_IF(i >= max, i << " " << max, m_p_c, &m_native_c);
+	return i;
+      }
+    else
+      ++i;
+}
+
+  // Insert.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+push()
+{
+  PB_DS_TRACE("push");
+  bool done = true;
+  destructor_printer notify(__FUNCTION__);
+
+    try
+      {
+        m_alloc.set_probability(0);
+        value_type v = test_traits::generate_value(m_g, m_m);
+        m_alloc.set_probability(m_tp);
+        const typename cntnr::size_type sz = m_p_c->size();
+        m_p_c->push(v);
+        _GLIBCXX_THROW_IF(sz != m_p_c->size() - 1, sz, m_p_c, &m_native_c);
+        m_native_c.push(test_traits::native_value(v));
+      }
+    catch(__gnu_cxx::forced_error&)
+      {
+        done = false;
+      }
+    catch(...)
+      {
+        _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+      }
+
+  PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+  notify.cancel();
+  return done;
+}
+
+
+  // Modify.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+modify()
+{
+  PB_DS_TRACE("modify");
+  destructor_printer notify(__FUNCTION__);
+
+  bool done = true;
+  try
+    {
+      m_alloc.set_probability(0);
+      value_type v = test_traits::generate_value(m_g, m_m);
+
+      m_alloc.set_probability(m_tp);
+      typename cntnr::iterator it = m_p_c->begin();
+      std::advance(it, m_g.get_unsigned_long(0, m_p_c->size()));
+      if (it != m_p_c->end())
+	{
+	  typedef typename test_traits::native_value_type native_value_type;
+	  native_value_type native_v = test_traits::native_value(*it);
+	  native_value_type new_native_v = test_traits::native_value(v);
+	  m_p_c->modify(it, v);
+	  m_native_c.modify(native_v, new_native_v);
+	}
+    }
+  catch(__gnu_cxx::forced_error&)
+    {
+      done = false;
+      _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+    }
+
+  PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+  notify.cancel();
+  return done;
+}
+
+  // Clear.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+clear()
+{
+  PB_DS_TRACE("clear");
+  m_p_c->clear();
+  m_native_c.clear();
+  return true;
+}
+
+  // Erase.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+pop()
+{
+  PB_DS_TRACE("pop");
+  destructor_printer notify(__FUNCTION__);
+
+  bool done = true;
+  try
+    {
+      m_alloc.set_probability(1);
+      if (!m_p_c->empty())
+        {
+	  m_p_c->pop();
+	  m_native_c.pop();
+        }
+    }
+  catch(__gnu_cxx::forced_error&)
+    {
+      done = false;
+      _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+    }
+
+  PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+  notify.cancel();
+  return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase_if()
+{
+  PB_DS_TRACE("erase_if");
+  destructor_printer notify(__FUNCTION__);
+
+  bool done = true;
+  try
+    {
+      typedef
+	typename std::iterator_traits<typename cntnr::iterator>::reference
+	it_const_reference;
+      
+      m_alloc.set_probability(1);
+      
+      typedef
+	typename test_traits::template erase_if_fn<value_type>
+	erase_if_fn_t;
+      
+      const size_t ersd = m_p_c->erase_if(erase_if_fn_t());
+      
+      typedef
+	typename test_traits::template erase_if_fn<std::string>
+	native_erase_if_fn_t;
+      
+      const size_t native_ersd = m_native_c.erase_if(native_erase_if_fn_t());
+
+      _GLIBCXX_THROW_IF(ersd != native_ersd, ersd << " " << native_ersd,
+			m_p_c, &m_native_c);
+    }
+  catch(__gnu_cxx::forced_error&)
+    {
+      done = false;      
+      _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+    }
+
+  PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+  notify.cancel();
+  return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase_it()
+{
+  PB_DS_TRACE("erase_it");
+  destructor_printer notify(__FUNCTION__);
+
+  bool done = true;
+  try
+    {
+      m_alloc.set_probability(1);      
+      typename cntnr::iterator it = m_p_c->begin();      
+      std::advance(it, m_g.get_unsigned_long(0, m_p_c->size()));
+      
+      if (it != m_p_c->end())
+	{
+	  m_native_c.erase(*it);	 
+	  m_p_c->erase(it);
+	}
+    }
+  catch(__gnu_cxx::forced_error&)
+    {
+      done = false;      
+      _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+    }
+
+  PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+  notify.cancel();
+  return done;
+}
+
+  // Defs.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+defs()
+{
+  // General container types.
+  typedef typename Cntnr::size_type test_size_type;
+  typedef typename Cntnr::difference_type difference_type;
+  value_defs();
+  iterator_defs();
+  policy_defs();
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+value_defs()
+{
+  typedef typename Cntnr::value_type test_value_type;
+  typedef typename Cntnr::reference test_reference;
+  typedef typename Cntnr::const_reference test_const_reference;
+  typedef typename Cntnr::pointer test_pointer;
+  typedef typename Cntnr::const_pointer test_const_pointer;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+ds_defs()
+{
+  typedef typename Cntnr::container_category test_container_category;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+iterator_defs()
+{
+  typedef typename Cntnr::point_iterator test_point_iterator;
+  typedef typename Cntnr::const_point_iterator const_test_point_iterator;
+  typedef typename Cntnr::iterator test_iterator;
+  typedef typename Cntnr::const_iterator const_test_iterator;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_defs()
+{
+  typedef typename Cntnr::allocator_type test_allocator;
+  typedef typename Cntnr::cmp_fn test_cmp_fn;
+}
+
+
+// Policy access.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_access()
+{
+  PB_DS_TRACE("policy_access");
+
+  {
+    typename Cntnr::cmp_fn& r_t = m_p_c->get_cmp_fn();
+    assert(&r_t);
+  }
+
+  {
+    const typename Cntnr::cmp_fn& r_t =((const Cntnr& )*m_p_c).get_cmp_fn();
+    assert(&r_t);
+  }
+}
+
+// Split join.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+split_join()
+{
+  PB_DS_TRACE("split_join");
+  destructor_printer notify(__FUNCTION__);
+
+  bool done = true;
+  try
+    {
+      m_alloc.set_probability(0);
+      Cntnr lhs(*m_p_c);
+      Cntnr rhs;
+      native_type native_lhs(m_native_c);
+      m_alloc.set_probability(m_tp);
+      
+      typedef typename test_traits::template erase_if_fn<value_type> split_fn_t;
+      lhs.split(split_fn_t(), rhs);
+      
+      typedef typename test_traits::template erase_if_fn<std::string>
+	native_split_fn_t;
+      
+      native_type native_rhs;      
+      native_lhs.split(native_split_fn_t(), native_rhs);      
+      PB_DS_COND_COMPARE(lhs, native_lhs);
+      PB_DS_COND_COMPARE(rhs, native_rhs);
+      
+      m_alloc.set_probability(m_tp);
+      
+      if (m_g.get_prob() < 0.5)
+	lhs.swap(rhs);      
+      lhs.join(rhs);
+      
+      _GLIBCXX_THROW_IF(rhs.size() != 0, rhs.size(), m_p_c, &m_native_c);
+      _GLIBCXX_THROW_IF(!rhs.empty(), rhs.size(), m_p_c, &m_native_c);
+    }
+  catch(__gnu_cxx::forced_error&)
+    {
+      done = false;      
+      const bool b = __gnu_pbds::container_traits<cntnr>::split_join_can_throw;
+      _GLIBCXX_THROW_IF(!b, b, m_p_c, &m_native_c);
+    }
+  
+  PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+  notify.cancel();
+  return done;
+}
+
+// Iterator conversions.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+it_copy()
+{
+  PB_DS_TRACE("it_copy");
+
+  {
+    typename cntnr::iterator it = m_p_c->end();
+    typename cntnr::const_iterator const_it(it);
+    _GLIBCXX_THROW_IF(const_it != it, "", m_p_c, &m_native_c);
+    _GLIBCXX_THROW_IF(!(const_it == it), "", m_p_c, &m_native_c);
+  }
+
+  {
+    typename cntnr::const_iterator const_it = m_p_c->end();
+    typename cntnr::const_point_iterator const_find_it(const_it);
+    _GLIBCXX_THROW_IF(const_find_it != const_it, "", m_p_c, &m_native_c);
+    _GLIBCXX_THROW_IF(!(const_find_it == const_it), "", m_p_c, &m_native_c);
+  }
+
+  {
+    typename cntnr::iterator it = m_p_c->end();
+    typename cntnr::const_point_iterator const_find_it1(it);
+    _GLIBCXX_THROW_IF(const_find_it1 != it, "", m_p_c, &m_native_c);
+    _GLIBCXX_THROW_IF(!(const_find_it1 == it), "", m_p_c, &m_native_c);
+
+    typename cntnr::point_iterator find_it1(it);
+    _GLIBCXX_THROW_IF(find_it1 != it, "", m_p_c, &m_native_c);
+    _GLIBCXX_THROW_IF(!(find_it1 == it), "", m_p_c, &m_native_c);
+
+    typename cntnr::point_iterator find_it = m_p_c->end();
+    typename cntnr::const_point_iterator const_find_it(find_it);
+    _GLIBCXX_THROW_IF(find_it != const_find_it, "", m_p_c, &m_native_c);
+    _GLIBCXX_THROW_IF(!(find_it == const_find_it), "", m_p_c, &m_native_c);
+  }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+it_assign()
+{
+  PB_DS_TRACE("it_assign");
+
+  {
+    typename cntnr::iterator it = m_p_c->end();
+    typename cntnr::const_iterator const_it;
+    const_it = it;
+    _GLIBCXX_THROW_IF(const_it != it, "", m_p_c, &m_native_c);
+    _GLIBCXX_THROW_IF(!(const_it == it), "", m_p_c, &m_native_c);
+
+    typename cntnr::const_point_iterator const_find_it;
+    const_find_it = it;
+    _GLIBCXX_THROW_IF(const_find_it != it, "", m_p_c, &m_native_c);
+    _GLIBCXX_THROW_IF(!(const_find_it == it), "", m_p_c, &m_native_c);
+
+    typename cntnr::point_iterator find_it;
+    find_it = it;
+    _GLIBCXX_THROW_IF(find_it != it, "", m_p_c, &m_native_c);
+    _GLIBCXX_THROW_IF(!(find_it == it), "", m_p_c, &m_native_c);
+  }
+
+  {
+    typename cntnr::const_iterator const_it = m_p_c->end();
+    typename cntnr::const_point_iterator const_find_it;
+    const_find_it = const_it;
+    _GLIBCXX_THROW_IF(const_find_it != const_it, "", m_p_c, &m_native_c);
+    _GLIBCXX_THROW_IF(!(const_find_it == const_it), "", m_p_c, &m_native_c);
+  }
+
+  {
+    typename cntnr::point_iterator find_it = m_p_c->end();
+    typename cntnr::const_point_iterator const_find_it;
+    const_find_it = find_it;
+    _GLIBCXX_THROW_IF(find_it != const_find_it, "", m_p_c, &m_native_c);
+    _GLIBCXX_THROW_IF(!(find_it == const_find_it), "", m_p_c, &m_native_c);
+  }
+}
+
+
+// Diagnostics.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+print_container(const native_type& cnt, std::ostream& os) const
+{
+  m_alloc.set_probability(0);
+  native_type cpy(cnt);
+  while (!cpy.empty())
+    {
+      os << cpy.top() << std::endl;
+      cpy.pop();
+    }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+print_container(const cntnr& cnt, std::ostream& os) const
+{
+  typedef typename cntnr::const_iterator const_iterator;
+  m_alloc.set_probability(0);
+  for (const_iterator it = cnt.begin(); it != cnt.end(); ++it)
+    os << *it << std::endl;
+}
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp
new file mode 100644
index 000000000..37f8d51af
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp
@@ -0,0 +1,202 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2008, 2009, 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// 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 rand_regression_test.hpp
+ * Contains a random-operation test.
+ */
+
+#ifndef PB_DS_PQ_RAND_REGRESSION_TEST_HPP
+#define PB_DS_PQ_RAND_REGRESSION_TEST_HPP
+
+#include <iostream>
+#include <vector>
+#include <io/verified_cmd_line_input.hpp>
+#include <regression/common_type.hpp>
+#include <regression/rand/priority_queue/container_rand_regression_test.h>
+
+namespace __gnu_pbds
+{
+namespace test
+{
+namespace detail
+{
+#ifndef PB_DS_REGRESSION
+#error "Must define PB_DS_REGRESSION"
+#endif
+
+  struct rand_reg_test
+  {
+  public:
+    rand_reg_test(size_t seed, size_t n, size_t m, double tp, double ip, 
+		  double dp, double ep, double cp, double mp, bool d) 
+    : m_sd(seed), m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_dp(dp), m_ep(ep), 
+      m_cp(cp), m_mp(mp), m_disp(d)
+    { }
+
+    template<typename Cntnr>
+    void
+    operator()(Cntnr)
+    {
+      unsigned long ul = static_cast<unsigned long>(m_sd);
+      container_rand_regression_test<Cntnr> t(ul, m_n, m_n, m_tp, m_ip, m_dp, 
+					      m_ep, m_cp, m_mp, m_disp);
+      t();
+    }
+
+  private:
+    const size_t m_sd;
+    const size_t m_n;
+    const size_t m_m;
+    const double m_tp;
+    const double m_ip;
+    const double m_dp;
+    const double m_ep;
+    const double m_cp;
+    const double m_mp;
+    const bool m_disp;
+  };
+
+  void
+  usage(const std::string& r_name);
+
+  void
+  verify_params(size_t&, size_t&, size_t&, 
+		double&, double&, double&, double&, double&, double&, bool&);
+} // namespace detail
+
+  template<typename TL>
+  int
+  rand_regression_test(size_t iter, size_t keys, const std::string name, TL tl)
+  {
+    // Sane defaults.
+    size_t n = iter;
+    size_t m = keys;
+    size_t sd = 0; // 0 = time-determined arbitrary
+    double tp = 0.2;
+    double ip = 0.6;
+    double dp = 0.1;
+    double ep = 0.2; 
+    double cp = 0.001;
+    double mp = 1;
+    bool disp = false; // show progress
+
+    try
+      {
+	detail::verify_params(sd, n, m, tp, ip, dp, ep, cp, mp, disp);
+      }
+    catch(__gnu_pbds::test::illegal_input_error&)
+      {
+	detail::usage(name);
+	return -1;
+      }
+    catch(...)
+      {
+	return -2;
+      };
+
+    xml_test_rand_regression_formatter* p_fmt = 0;
+    if (sd == 0)
+      sd = twister_rand_gen::get_time_determined_seed();
+    if (disp)
+      p_fmt = new xml_test_rand_regression_formatter(sd, n, m, tp, ip, dp,
+						     ep, cp, mp);
+
+    try
+      {
+	detail::rand_reg_test tst(sd, n, m, tp, ip, dp, ep, cp, mp, disp);
+	__gnu_cxx::typelist::apply(tst, tl);
+      }
+    catch(...)
+      {
+	std::cerr << "Test failed with seed " << sd << std::endl;
+	if (disp)
+	  delete p_fmt;
+	return -1;
+      }
+
+    if (disp)
+      delete p_fmt;
+    return 0;
+  }
+
+namespace detail
+{
+  inline void
+  usage(const std::string& name)
+  {
+    using namespace std;
+    cerr << "usage: " << name << " <sd> <n> <m> <tp> <ip> <dp> <ep> <cp> <mp> ['t' | 'f']" <<
+      endl << endl;
+
+    cerr << "This test performs basic regression tests on various priority queues."
+      "For each container, it performs a sequence of operations. At each iteration, it does "
+      "the following: " << endl;
+    cerr << "*  Performs an operation on the container " << endl;
+    cerr << "*  Performs the same operation on an cntnr object" << endl;
+    cerr << "*  Possibly compares the container to the cntnr object" << endl;
+    cerr << "*  Checks that exceptions (thrown by an allocator) "
+      "do not violate exception guarantees";
+
+    cerr << endl << endl;
+
+    cerr << "sd = seed for random-number generator; 0 = "
+      "time determined value" << endl;
+    cerr << "n = number of iterations" << endl;
+    cerr << "m = number of distinct values" << endl;
+    cerr << "tp = probability that an exception will be actively thrown" << endl;
+    cerr << "ip = probability that an operation will be insert" << endl;
+    cerr << "dp = probability that an operation will be modify" << endl;
+    cerr << "ep = probability that an operation will be erase" << endl;
+    cerr << "cp = probability that an operation will be clear" << endl;
+    cerr << "(therefore, 1 - (ip + dp + ep + cp) = probability of any other operation)" << endl;
+    cerr << "mp = probability that the container will be compared to the cntnr object" << endl;
+    cerr << "'t' or 'f' determine whether progress will be displayed" << endl;
+  }
+
+  inline void
+  verify_params(size_t& r_seed, size_t& r_n, 
+		size_t& r_m, double& r_tp, double& r_ip, double& r_dp, 
+		double& r_ep, double& r_cp, double& r_mp, bool& r_d)
+  {
+    verify_prob(r_tp);
+    verify_prob(r_ip);
+    verify_prob(r_dp);
+    verify_prob(r_ep);
+    verify_prob(r_cp);
+    verify_prob(r_mp);
+    verify_prob(r_ip + r_dp + r_ep + r_cp);
+  }
+} // namespace detail
+} // namespace test
+} // namespace __gnu_pbds
+
+#endif