This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] bootstrap/69464 Avoid including all of <random> in <algorithm>


In C++11 mode <algorithm> defines std::shuffle which uses
std::uniform_int_distribution. It doesn't need the rest of <random>,
which is huge, especially on x86 with SSE3 support, where pmmintrin.h
is pulled in.

This moves the definition of std::uniform_int_distribution to a new
header, and makes <algorithm> include that instead of <random>.  That
removes 23kloc from <algorithm>, making it much less of a problem for
the rest of the compiler to use <algorithm> during bootstrap.

The change revealed a few testsuite bugs where tests (incorrectly)
relied on <algorithm> pulling in <memory> or <vector> indirectly.
It's likely that some programs will stop compiling because of this
change, the fix will be to add the necessary headers.

Tested x86_64-linux and powerpc64-linux, committed to trunk.

commit b8cab1de33b9d3fbfbe984b6b7e9d3aa41b8e80e
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Jan 25 14:15:24 2016 +0000

    Avoid including all of <random> in <algorithm>
    
    	PR libstdc++/69464
    	* include/Makefile.am: Add new header.
    	* include/Makefile.in: Regenerate.
    	* include/bits/random.h (uniform_int_distribution): Move to
    	bits/uniform_int_dist.h.
    	* include/bits/random.tcc (uniform_int_distribution::operator(),
    	uniform_int_distribution::__generate_impl): Likewise.
    	* include/bits/uniform_int_dist.h: New header.
    	* include/bits/stl_algo.h [__cplusplus >= 201103L]: Include
    	<bits/uniform_int_dist.h> instead of <random>.
    	* testsuite/20_util/specialized_algorithms/uninitialized_copy/
    	move_iterators/1.cc: Include correct header for uninitialized_copy.
    	* testsuite/20_util/specialized_algorithms/uninitialized_copy_n/
    	move_iterators/1.cc: Likewise.
    	* testsuite/25_algorithms/nth_element/58800.cc: Include correct
    	header for vector.
    	* testsuite/26_numerics/random/pr60037-neg.cc: Adjust dg-error lines.

diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index 573f057..0b34c3c 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -180,6 +180,7 @@ bits_headers = \
 	${bits_srcdir}/stl_vector.h \
 	${bits_srcdir}/streambuf.tcc \
 	${bits_srcdir}/stringfwd.h \
+	${bits_srcdir}/uniform_int_dist.h \
 	${bits_srcdir}/unique_ptr.h \
 	${bits_srcdir}/unordered_map.h \
 	${bits_srcdir}/unordered_set.h \
diff --git a/libstdc++-v3/include/bits/random.h b/libstdc++-v3/include/bits/random.h
index 63f57d5..1babe80 100644
--- a/libstdc++-v3/include/bits/random.h
+++ b/libstdc++-v3/include/bits/random.h
@@ -32,6 +32,7 @@
 #define _RANDOM_H 1
 
 #include <vector>
+#include <bits/uniform_int_dist.h>
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
@@ -149,14 +150,6 @@ _GLIBCXX_END_NAMESPACE_VERSION
       __mod(_Tp __x)
       { return _Mod<_Tp, __m, __a, __c>::__calc(__x); }
 
-    /* Determine whether number is a power of 2.  */
-    template<typename _Tp>
-      inline bool
-      _Power_of_2(_Tp __x)
-      {
-	return ((__x - 1) & __x) == 0;
-      };
-
     /*
      * An adaptor class for converting the output of any Generator into
      * the input for a specific Distribution.
@@ -1656,164 +1649,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    * @{
    */
 
-  /**
-   * @brief Uniform discrete distribution for random numbers.
-   * A discrete random distribution on the range @f$[min, max]@f$ with equal
-   * probability throughout the range.
-   */
-  template<typename _IntType = int>
-    class uniform_int_distribution
-    {
-      static_assert(std::is_integral<_IntType>::value,
-		    "template argument not an integral type");
-
-    public:
-      /** The type of the range of the distribution. */
-      typedef _IntType result_type;
-      /** Parameter type. */
-      struct param_type
-      {
-	typedef uniform_int_distribution<_IntType> distribution_type;
-
-	explicit
-	param_type(_IntType __a = 0,
-		   _IntType __b = std::numeric_limits<_IntType>::max())
-	: _M_a(__a), _M_b(__b)
-	{
-	  __glibcxx_assert(_M_a <= _M_b);
-	}
-
-	result_type
-	a() const
-	{ return _M_a; }
-
-	result_type
-	b() const
-	{ return _M_b; }
-
-	friend bool
-	operator==(const param_type& __p1, const param_type& __p2)
-	{ return __p1._M_a == __p2._M_a && __p1._M_b == __p2._M_b; }
-
-      private:
-	_IntType _M_a;
-	_IntType _M_b;
-      };
-
-    public:
-      /**
-       * @brief Constructs a uniform distribution object.
-       */
-      explicit
-      uniform_int_distribution(_IntType __a = 0,
-			   _IntType __b = std::numeric_limits<_IntType>::max())
-      : _M_param(__a, __b)
-      { }
-
-      explicit
-      uniform_int_distribution(const param_type& __p)
-      : _M_param(__p)
-      { }
-
-      /**
-       * @brief Resets the distribution state.
-       *
-       * Does nothing for the uniform integer distribution.
-       */
-      void
-      reset() { }
-
-      result_type
-      a() const
-      { return _M_param.a(); }
-
-      result_type
-      b() const
-      { return _M_param.b(); }
-
-      /**
-       * @brief Returns the parameter set of the distribution.
-       */
-      param_type
-      param() const
-      { return _M_param; }
-
-      /**
-       * @brief Sets the parameter set of the distribution.
-       * @param __param The new parameter set of the distribution.
-       */
-      void
-      param(const param_type& __param)
-      { _M_param = __param; }
-
-      /**
-       * @brief Returns the inclusive lower bound of the distribution range.
-       */
-      result_type
-      min() const
-      { return this->a(); }
-
-      /**
-       * @brief Returns the inclusive upper bound of the distribution range.
-       */
-      result_type
-      max() const
-      { return this->b(); }
-
-      /**
-       * @brief Generating functions.
-       */
-      template<typename _UniformRandomNumberGenerator>
-	result_type
-	operator()(_UniformRandomNumberGenerator& __urng)
-        { return this->operator()(__urng, _M_param); }
-
-      template<typename _UniformRandomNumberGenerator>
-	result_type
-	operator()(_UniformRandomNumberGenerator& __urng,
-		   const param_type& __p);
-
-      template<typename _ForwardIterator,
-	       typename _UniformRandomNumberGenerator>
-	void
-	__generate(_ForwardIterator __f, _ForwardIterator __t,
-		   _UniformRandomNumberGenerator& __urng)
-	{ this->__generate(__f, __t, __urng, _M_param); }
-
-      template<typename _ForwardIterator,
-	       typename _UniformRandomNumberGenerator>
-	void
-	__generate(_ForwardIterator __f, _ForwardIterator __t,
-		   _UniformRandomNumberGenerator& __urng,
-		   const param_type& __p)
-	{ this->__generate_impl(__f, __t, __urng, __p); }
-
-      template<typename _UniformRandomNumberGenerator>
-	void
-	__generate(result_type* __f, result_type* __t,
-		   _UniformRandomNumberGenerator& __urng,
-		   const param_type& __p)
-	{ this->__generate_impl(__f, __t, __urng, __p); }
-
-      /**
-       * @brief Return true if two uniform integer distributions have
-       *        the same parameters.
-       */
-      friend bool
-      operator==(const uniform_int_distribution& __d1,
-		 const uniform_int_distribution& __d2)
-      { return __d1._M_param == __d2._M_param; }
-
-    private:
-      template<typename _ForwardIterator,
-	       typename _UniformRandomNumberGenerator>
-	void
-	__generate_impl(_ForwardIterator __f, _ForwardIterator __t,
-			_UniformRandomNumberGenerator& __urng,
-			const param_type& __p);
-
-      param_type _M_param;
-    };
+  // std::uniform_int_distribution is defined in <bits/random_uid.h>
 
   /**
    * @brief Return true if two uniform integer distributions have
diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
index d2a51c4..7dfc721 100644
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -872,158 +872,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
 
-  template<typename _IntType>
-    template<typename _UniformRandomNumberGenerator>
-      typename uniform_int_distribution<_IntType>::result_type
-      uniform_int_distribution<_IntType>::
-      operator()(_UniformRandomNumberGenerator& __urng,
-		 const param_type& __param)
-      {
-	typedef typename _UniformRandomNumberGenerator::result_type
-	  _Gresult_type;
-	typedef typename std::make_unsigned<result_type>::type __utype;
-	typedef typename std::common_type<_Gresult_type, __utype>::type
-	  __uctype;
-
-	const __uctype __urngmin = __urng.min();
-	const __uctype __urngmax = __urng.max();
-	const __uctype __urngrange = __urngmax - __urngmin;
-	const __uctype __urange
-	  = __uctype(__param.b()) - __uctype(__param.a());
-
-	__uctype __ret;
-
-	if (__urngrange > __urange)
-	  {
-	    // downscaling
-	    const __uctype __uerange = __urange + 1; // __urange can be zero
-	    const __uctype __scaling = __urngrange / __uerange;
-	    const __uctype __past = __uerange * __scaling;
-	    do
-	      __ret = __uctype(__urng()) - __urngmin;
-	    while (__ret >= __past);
-	    __ret /= __scaling;
-	  }
-	else if (__urngrange < __urange)
-	  {
-	    // upscaling
-	    /*
-	      Note that every value in [0, urange]
-	      can be written uniquely as
-
-	      (urngrange + 1) * high + low
-
-	      where
-
-	      high in [0, urange / (urngrange + 1)]
-
-	      and
-	
-	      low in [0, urngrange].
-	    */
-	    __uctype __tmp; // wraparound control
-	    do
-	      {
-		const __uctype __uerngrange = __urngrange + 1;
-		__tmp = (__uerngrange * operator()
-			 (__urng, param_type(0, __urange / __uerngrange)));
-		__ret = __tmp + (__uctype(__urng()) - __urngmin);
-	      }
-	    while (__ret > __urange || __ret < __tmp);
-	  }
-	else
-	  __ret = __uctype(__urng()) - __urngmin;
-
-	return __ret + __param.a();
-      }
-
-
-  template<typename _IntType>
-    template<typename _ForwardIterator,
-	     typename _UniformRandomNumberGenerator>
-      void
-      uniform_int_distribution<_IntType>::
-      __generate_impl(_ForwardIterator __f, _ForwardIterator __t,
-		      _UniformRandomNumberGenerator& __urng,
-		      const param_type& __param)
-      {
-	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
-	typedef typename _UniformRandomNumberGenerator::result_type
-	  _Gresult_type;
-	typedef typename std::make_unsigned<result_type>::type __utype;
-	typedef typename std::common_type<_Gresult_type, __utype>::type
-	  __uctype;
-
-	const __uctype __urngmin = __urng.min();
-	const __uctype __urngmax = __urng.max();
-	const __uctype __urngrange = __urngmax - __urngmin;
-	const __uctype __urange
-	  = __uctype(__param.b()) - __uctype(__param.a());
-
-	__uctype __ret;
-
-	if (__urngrange > __urange)
-	  {
-	    if (__detail::_Power_of_2(__urngrange + 1)
-		&& __detail::_Power_of_2(__urange + 1))
-	      {
-		while (__f != __t)
-		  {
-		    __ret = __uctype(__urng()) - __urngmin;
-		    *__f++ = (__ret & __urange) + __param.a();
-		  }
-	      }
-	    else
-	      {
-		// downscaling
-		const __uctype __uerange = __urange + 1; // __urange can be zero
-		const __uctype __scaling = __urngrange / __uerange;
-		const __uctype __past = __uerange * __scaling;
-		while (__f != __t)
-		  {
-		    do
-		      __ret = __uctype(__urng()) - __urngmin;
-		    while (__ret >= __past);
-		    *__f++ = __ret / __scaling + __param.a();
-		  }
-	      }
-	  }
-	else if (__urngrange < __urange)
-	  {
-	    // upscaling
-	    /*
-	      Note that every value in [0, urange]
-	      can be written uniquely as
-
-	      (urngrange + 1) * high + low
-
-	      where
-
-	      high in [0, urange / (urngrange + 1)]
-
-	      and
-
-	      low in [0, urngrange].
-	    */
-	    __uctype __tmp; // wraparound control
-	    while (__f != __t)
-	      {
-		do
-		  {
-		    const __uctype __uerngrange = __urngrange + 1;
-		    __tmp = (__uerngrange * operator()
-			     (__urng, param_type(0, __urange / __uerngrange)));
-		    __ret = __tmp + (__uctype(__urng()) - __urngmin);
-		  }
-		while (__ret > __urange || __ret < __tmp);
-		*__f++ = __ret;
-	      }
-	  }
-	else
-	  while (__f != __t)
-	    *__f++ = __uctype(__urng()) - __urngmin + __param.a();
-      }
-
   template<typename _IntType, typename _CharT, typename _Traits>
     std::basic_ostream<_CharT, _Traits>&
     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index fb73fd4..fbd03a7 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -63,7 +63,7 @@
 #include <bits/predefined_ops.h>
 
 #if __cplusplus >= 201103L
-#include <random>     // for std::uniform_int_distribution
+#include <bits/uniform_int_dist.h>
 #endif
 
 // See concept_check.h for the __glibcxx_*_requires macros.
diff --git a/libstdc++-v3/include/bits/uniform_int_dist.h b/libstdc++-v3/include/bits/uniform_int_dist.h
new file mode 100644
index 0000000..393aa77
--- /dev/null
+++ b/libstdc++-v3/include/bits/uniform_int_dist.h
@@ -0,0 +1,366 @@
+// Class template uniform_int_distribution -*- C++ -*-
+
+// Copyright (C) 2009-2016 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.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+/**
+ * @file bits/uniform_int_dist.h
+ *  This is an internal header file, included by other library headers.
+ *  Do not attempt to use it directly. @headername{random}
+ */
+
+#ifndef _GLIBCXX_BITS_UNIFORM_INT_DIST_H
+#define _GLIBCXX_BITS_UNIFORM_INT_DIST_H
+
+#include <type_traits>
+#include <limits>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  namespace __detail
+  {
+    /* Determine whether number is a power of 2.  */
+    template<typename _Tp>
+      inline bool
+      _Power_of_2(_Tp __x)
+      {
+	return ((__x - 1) & __x) == 0;
+      };
+  }
+
+  /**
+   * @brief Uniform discrete distribution for random numbers.
+   * A discrete random distribution on the range @f$[min, max]@f$ with equal
+   * probability throughout the range.
+   */
+  template<typename _IntType = int>
+    class uniform_int_distribution
+    {
+      static_assert(std::is_integral<_IntType>::value,
+		    "template argument not an integral type");
+
+    public:
+      /** The type of the range of the distribution. */
+      typedef _IntType result_type;
+      /** Parameter type. */
+      struct param_type
+      {
+	typedef uniform_int_distribution<_IntType> distribution_type;
+
+	explicit
+	param_type(_IntType __a = 0,
+		   _IntType __b = std::numeric_limits<_IntType>::max())
+	: _M_a(__a), _M_b(__b)
+	{
+	  __glibcxx_assert(_M_a <= _M_b);
+	}
+
+	result_type
+	a() const
+	{ return _M_a; }
+
+	result_type
+	b() const
+	{ return _M_b; }
+
+	friend bool
+	operator==(const param_type& __p1, const param_type& __p2)
+	{ return __p1._M_a == __p2._M_a && __p1._M_b == __p2._M_b; }
+
+      private:
+	_IntType _M_a;
+	_IntType _M_b;
+      };
+
+    public:
+      /**
+       * @brief Constructs a uniform distribution object.
+       */
+      explicit
+      uniform_int_distribution(_IntType __a = 0,
+			   _IntType __b = std::numeric_limits<_IntType>::max())
+      : _M_param(__a, __b)
+      { }
+
+      explicit
+      uniform_int_distribution(const param_type& __p)
+      : _M_param(__p)
+      { }
+
+      /**
+       * @brief Resets the distribution state.
+       *
+       * Does nothing for the uniform integer distribution.
+       */
+      void
+      reset() { }
+
+      result_type
+      a() const
+      { return _M_param.a(); }
+
+      result_type
+      b() const
+      { return _M_param.b(); }
+
+      /**
+       * @brief Returns the parameter set of the distribution.
+       */
+      param_type
+      param() const
+      { return _M_param; }
+
+      /**
+       * @brief Sets the parameter set of the distribution.
+       * @param __param The new parameter set of the distribution.
+       */
+      void
+      param(const param_type& __param)
+      { _M_param = __param; }
+
+      /**
+       * @brief Returns the inclusive lower bound of the distribution range.
+       */
+      result_type
+      min() const
+      { return this->a(); }
+
+      /**
+       * @brief Returns the inclusive upper bound of the distribution range.
+       */
+      result_type
+      max() const
+      { return this->b(); }
+
+      /**
+       * @brief Generating functions.
+       */
+      template<typename _UniformRandomNumberGenerator>
+	result_type
+	operator()(_UniformRandomNumberGenerator& __urng)
+        { return this->operator()(__urng, _M_param); }
+
+      template<typename _UniformRandomNumberGenerator>
+	result_type
+	operator()(_UniformRandomNumberGenerator& __urng,
+		   const param_type& __p);
+
+      template<typename _ForwardIterator,
+	       typename _UniformRandomNumberGenerator>
+	void
+	__generate(_ForwardIterator __f, _ForwardIterator __t,
+		   _UniformRandomNumberGenerator& __urng)
+	{ this->__generate(__f, __t, __urng, _M_param); }
+
+      template<typename _ForwardIterator,
+	       typename _UniformRandomNumberGenerator>
+	void
+	__generate(_ForwardIterator __f, _ForwardIterator __t,
+		   _UniformRandomNumberGenerator& __urng,
+		   const param_type& __p)
+	{ this->__generate_impl(__f, __t, __urng, __p); }
+
+      template<typename _UniformRandomNumberGenerator>
+	void
+	__generate(result_type* __f, result_type* __t,
+		   _UniformRandomNumberGenerator& __urng,
+		   const param_type& __p)
+	{ this->__generate_impl(__f, __t, __urng, __p); }
+
+      /**
+       * @brief Return true if two uniform integer distributions have
+       *        the same parameters.
+       */
+      friend bool
+      operator==(const uniform_int_distribution& __d1,
+		 const uniform_int_distribution& __d2)
+      { return __d1._M_param == __d2._M_param; }
+
+    private:
+      template<typename _ForwardIterator,
+	       typename _UniformRandomNumberGenerator>
+	void
+	__generate_impl(_ForwardIterator __f, _ForwardIterator __t,
+			_UniformRandomNumberGenerator& __urng,
+			const param_type& __p);
+
+      param_type _M_param;
+    };
+
+  template<typename _IntType>
+    template<typename _UniformRandomNumberGenerator>
+      typename uniform_int_distribution<_IntType>::result_type
+      uniform_int_distribution<_IntType>::
+      operator()(_UniformRandomNumberGenerator& __urng,
+		 const param_type& __param)
+      {
+	typedef typename _UniformRandomNumberGenerator::result_type
+	  _Gresult_type;
+	typedef typename std::make_unsigned<result_type>::type __utype;
+	typedef typename std::common_type<_Gresult_type, __utype>::type
+	  __uctype;
+
+	const __uctype __urngmin = __urng.min();
+	const __uctype __urngmax = __urng.max();
+	const __uctype __urngrange = __urngmax - __urngmin;
+	const __uctype __urange
+	  = __uctype(__param.b()) - __uctype(__param.a());
+
+	__uctype __ret;
+
+	if (__urngrange > __urange)
+	  {
+	    // downscaling
+	    const __uctype __uerange = __urange + 1; // __urange can be zero
+	    const __uctype __scaling = __urngrange / __uerange;
+	    const __uctype __past = __uerange * __scaling;
+	    do
+	      __ret = __uctype(__urng()) - __urngmin;
+	    while (__ret >= __past);
+	    __ret /= __scaling;
+	  }
+	else if (__urngrange < __urange)
+	  {
+	    // upscaling
+	    /*
+	      Note that every value in [0, urange]
+	      can be written uniquely as
+
+	      (urngrange + 1) * high + low
+
+	      where
+
+	      high in [0, urange / (urngrange + 1)]
+
+	      and
+
+	      low in [0, urngrange].
+	    */
+	    __uctype __tmp; // wraparound control
+	    do
+	      {
+		const __uctype __uerngrange = __urngrange + 1;
+		__tmp = (__uerngrange * operator()
+			 (__urng, param_type(0, __urange / __uerngrange)));
+		__ret = __tmp + (__uctype(__urng()) - __urngmin);
+	      }
+	    while (__ret > __urange || __ret < __tmp);
+	  }
+	else
+	  __ret = __uctype(__urng()) - __urngmin;
+
+	return __ret + __param.a();
+      }
+
+
+  template<typename _IntType>
+    template<typename _ForwardIterator,
+	     typename _UniformRandomNumberGenerator>
+      void
+      uniform_int_distribution<_IntType>::
+      __generate_impl(_ForwardIterator __f, _ForwardIterator __t,
+		      _UniformRandomNumberGenerator& __urng,
+		      const param_type& __param)
+      {
+	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
+	typedef typename _UniformRandomNumberGenerator::result_type
+	  _Gresult_type;
+	typedef typename std::make_unsigned<result_type>::type __utype;
+	typedef typename std::common_type<_Gresult_type, __utype>::type
+	  __uctype;
+
+	const __uctype __urngmin = __urng.min();
+	const __uctype __urngmax = __urng.max();
+	const __uctype __urngrange = __urngmax - __urngmin;
+	const __uctype __urange
+	  = __uctype(__param.b()) - __uctype(__param.a());
+
+	__uctype __ret;
+
+	if (__urngrange > __urange)
+	  {
+	    if (__detail::_Power_of_2(__urngrange + 1)
+		&& __detail::_Power_of_2(__urange + 1))
+	      {
+		while (__f != __t)
+		  {
+		    __ret = __uctype(__urng()) - __urngmin;
+		    *__f++ = (__ret & __urange) + __param.a();
+		  }
+	      }
+	    else
+	      {
+		// downscaling
+		const __uctype __uerange = __urange + 1; // __urange can be zero
+		const __uctype __scaling = __urngrange / __uerange;
+		const __uctype __past = __uerange * __scaling;
+		while (__f != __t)
+		  {
+		    do
+		      __ret = __uctype(__urng()) - __urngmin;
+		    while (__ret >= __past);
+		    *__f++ = __ret / __scaling + __param.a();
+		  }
+	      }
+	  }
+	else if (__urngrange < __urange)
+	  {
+	    // upscaling
+	    /*
+	      Note that every value in [0, urange]
+	      can be written uniquely as
+
+	      (urngrange + 1) * high + low
+
+	      where
+
+	      high in [0, urange / (urngrange + 1)]
+
+	      and
+
+	      low in [0, urngrange].
+	    */
+	    __uctype __tmp; // wraparound control
+	    while (__f != __t)
+	      {
+		do
+		  {
+		    const __uctype __uerngrange = __urngrange + 1;
+		    __tmp = (__uerngrange * operator()
+			     (__urng, param_type(0, __urange / __uerngrange)));
+		    __ret = __tmp + (__uctype(__urng()) - __urngmin);
+		  }
+		while (__ret > __urange || __ret < __tmp);
+		*__f++ = __ret;
+	      }
+	  }
+	else
+	  while (__f != __t)
+	    *__f++ = __uctype(__urng()) - __urngmin + __param.a();
+      }
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
+
+#endif
diff --git a/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_copy/move_iterators/1.cc b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_copy/move_iterators/1.cc
index c00c7c6..c1de0e0 100644
--- a/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_copy/move_iterators/1.cc
+++ b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_copy/move_iterators/1.cc
@@ -19,7 +19,7 @@
 
 #undef _GLIBCXX_CONCEPT_CHECKS
 
-#include <algorithm>
+#include <memory>
 #include <iterator>
 #include <testsuite_hooks.h>
 #include <testsuite_iterators.h>
diff --git a/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_copy_n/move_iterators/1.cc b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_copy_n/move_iterators/1.cc
index 6027a84..a7c6d72 100644
--- a/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_copy_n/move_iterators/1.cc
+++ b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_copy_n/move_iterators/1.cc
@@ -21,7 +21,7 @@
 
 #undef _GLIBCXX_CONCEPT_CHECKS
 
-#include <algorithm>
+#include <memory>
 #include <iterator>
 #include <testsuite_hooks.h>
 #include <testsuite_iterators.h>
diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc b/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc
index 2058539..f72f5e7 100644
--- a/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc
@@ -20,6 +20,7 @@
 // { dg-options "-std=gnu++11" }
 
 #include <algorithm>
+#include <vector>
 #include <testsuite_hooks.h>
 #include <testsuite_iterators.h>
 
diff --git a/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc b/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc
index 11d5539..e9ebc68 100644
--- a/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc
+++ b/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc
@@ -10,6 +10,6 @@ std::__detail::_Adaptor<std::mt19937, unsigned long> aurng(urng);
 auto x = std::generate_canonical<std::size_t,
 			std::numeric_limits<std::size_t>::digits>(urng);
 
-// { dg-error "static assertion failed: template argument not a floating point type" "" { target *-*-* } 167 }
+// { dg-error "static assertion failed: template argument not a floating point type" "" { target *-*-* } 160 }
 
-// { dg-error "static assertion failed: template argument not a floating point type" "" { target *-*-* } 3466 }
+// { dg-error "static assertion failed: template argument not a floating point type" "" { target *-*-* } 3314 }

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]