[thirdparty/gcc.git] / libstdc++-v3 / include / parallel / base.h

// -*- C++ -*-

// Copyright (C) 2007-2025 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 parallel/base.h
 *  @brief Sequential helper functions.
 *  This file is a GNU parallel extension to the Standard C++ Library.
 */

// Written by Johannes Singler.

#ifndef _GLIBCXX_PARALLEL_BASE_H
#define _GLIBCXX_PARALLEL_BASE_H 1

#include <bits/c++config.h>
#include <bits/stl_function.h>
#include <omp.h>
#include <parallel/features.h>
#include <parallel/basic_iterator.h>
#include <parallel/parallel.h>

// Parallel mode namespaces.

/**
 * @namespace std::__parallel
 * @brief GNU parallel code, replaces standard behavior with parallel behavior.
 */
namespace std _GLIBCXX_VISIBILITY(default)
{
  namespace __parallel { }
}

/**
 * @namespace __gnu_parallel
 * @brief GNU parallel code for public use.
 */
namespace __gnu_parallel
{
  // Import all the parallel versions of components in namespace std.
  using namespace std::__parallel;
}

/**
 * @namespace __gnu_sequential
 * @brief GNU sequential classes for public use.
 */
namespace __gnu_sequential
{
  // Import whatever is the serial version.
#ifdef _GLIBCXX_PARALLEL
  using namespace std::_GLIBCXX_STD_A;
#else
  using namespace std;
#endif
}


namespace __gnu_parallel
{
  // NB: Including this file cannot produce (unresolved) symbols from
  // the OpenMP runtime unless the parallel mode is actually invoked
  // and active, which imples that the OpenMP runtime is actually
  // going to be linked in.
  inline _ThreadIndex
  __get_max_threads()
  {
    _ThreadIndex __i = omp_get_max_threads();
    return __i > 1 ? __i : 1;
  }


  inline bool
  __is_parallel(const _Parallelism __p) { return __p != sequential; }


  /** @brief Calculates the rounded-down logarithm of @c __n for base 2.
   *  @param __n Argument.
   *  @return Returns 0 for any argument <1.
   */
  template<typename _Size>
    inline _Size
    __rd_log2(_Size __n)
    {
      _Size __k;
      for (__k = 0; __n > 1; __n >>= 1)
        ++__k;
      return __k;
    }

  /** @brief Encode two integers into one gnu_parallel::_CASable.
   *  @param __a First integer, to be encoded in the most-significant @c
   *  _CASable_bits/2 bits.
   *  @param __b Second integer, to be encoded in the least-significant
   *  @c _CASable_bits/2 bits.
   *  @return value encoding @c __a and @c __b.
   *  @see __decode2
   */
  inline _CASable
  __encode2(int __a, int __b)     //must all be non-negative, actually
  {
    return (((_CASable)__a) << (_CASable_bits / 2)) | (((_CASable)__b) << 0);
  }

  /** @brief Decode two integers from one gnu_parallel::_CASable.
   *  @param __x __gnu_parallel::_CASable to decode integers from.
   *  @param __a First integer, to be decoded from the most-significant
   *  @c _CASable_bits/2 bits of @c __x.
   *  @param __b Second integer, to be encoded in the least-significant
   *  @c _CASable_bits/2 bits of @c __x.
   *  @see __encode2
   */
  inline void
  __decode2(_CASable __x, int& __a, int& __b)
  {
    __a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask);
    __b = (int)((__x >>               0 ) & _CASable_mask);
  }

  //needed for parallel "numeric", even if "algorithm" not included

  /** @brief Equivalent to std::min. */
  template<typename _Tp>
    inline const _Tp&
    min(const _Tp& __a, const _Tp& __b)
    { return (__a < __b) ? __a : __b; }

  /** @brief Equivalent to std::max. */
  template<typename _Tp>
    inline const _Tp&
    max(const _Tp& __a, const _Tp& __b)
    { return (__a > __b) ? __a : __b; }

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations" // *nary_function

  /** @brief Constructs predicate for equality from strict weak
   *  ordering predicate
   */
  template<typename _T1, typename _T2, typename _Compare>
    class _EqualFromLess : public std::binary_function<_T1, _T2, bool>
    {
    private:
      _Compare& _M_comp;

    public:
      _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { }

      bool operator()(const _T1& __a, const _T2& __b)
      { return !_M_comp(__a, __b) && !_M_comp(__b, __a); }
    };

  /** @brief Similar to std::unary_negate,
   *  but giving the argument types explicitly. */
  template<typename _Predicate, typename argument_type>
    class __unary_negate
    : public std::unary_function<argument_type, bool>
    {
    protected:
      _Predicate _M_pred;

    public:
      explicit
      __unary_negate(const _Predicate& __x) : _M_pred(__x) { }

      bool
      operator()(const argument_type& __x)
      { return !_M_pred(__x); }
    };

  /** @brief Similar to std::binder1st,
   *  but giving the argument types explicitly. */
  template<typename _Operation, typename _FirstArgumentType,
	   typename _SecondArgumentType, typename _ResultType>
    class __binder1st
    : public std::unary_function<_SecondArgumentType, _ResultType>
    {
    protected:
      _Operation _M_op;
      _FirstArgumentType _M_value;

    public:
      __binder1st(const _Operation& __x, const _FirstArgumentType& __y)
      : _M_op(__x), _M_value(__y) { }

      _ResultType
      operator()(const _SecondArgumentType& __x)
      { return _M_op(_M_value, __x); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 109.  Missing binders for non-const sequence elements
      _ResultType
      operator()(_SecondArgumentType& __x) const
      { return _M_op(_M_value, __x); }
    };

  /**
   *  @brief Similar to std::binder2nd, but giving the argument types
   *  explicitly.
   */
  template<typename _Operation, typename _FirstArgumentType,
	   typename _SecondArgumentType, typename _ResultType>
    class __binder2nd
    : public std::unary_function<_FirstArgumentType, _ResultType>
    {
    protected:
      _Operation _M_op;
      _SecondArgumentType _M_value;

    public:
      __binder2nd(const _Operation& __x, const _SecondArgumentType& __y)
      : _M_op(__x), _M_value(__y) { }

      _ResultType
      operator()(const _FirstArgumentType& __x) const
      { return _M_op(__x, _M_value); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 109.  Missing binders for non-const sequence elements
      _ResultType
      operator()(_FirstArgumentType& __x)
      { return _M_op(__x, _M_value); }
    };

  /** @brief Similar to std::equal_to, but allows two different types. */
  template<typename _T1, typename _T2>
    struct _EqualTo : std::binary_function<_T1, _T2, bool>
    {
      bool operator()(const _T1& __t1, const _T2& __t2) const
      { return __t1 == __t2; }
    };

  /** @brief Similar to std::less, but allows two different types. */
  template<typename _T1, typename _T2>
    struct _Less : std::binary_function<_T1, _T2, bool>
    {
      bool
      operator()(const _T1& __t1, const _T2& __t2) const
      { return __t1 < __t2; }

      bool
      operator()(const _T2& __t2, const _T1& __t1) const
      { return __t2 < __t1; }
    };

  // Partial specialization for one type. Same as std::less.
  template<typename _Tp>
    struct _Less<_Tp, _Tp>
    : public std::less<_Tp> { };

  /** @brief Similar to std::plus, but allows two different types. */
  template<typename _Tp1, typename _Tp2, typename _Result
	   = __typeof__(*static_cast<_Tp1*>(0)
			+ *static_cast<_Tp2*>(0))>
    struct _Plus : public std::binary_function<_Tp1, _Tp2, _Result>
    {
      _Result
      operator()(const _Tp1& __x, const _Tp2& __y) const
      { return __x + __y; }
    };

  // Partial specialization for one type. Same as std::plus.
  template<typename _Tp>
    struct _Plus<_Tp, _Tp, _Tp>
    : public std::plus<_Tp> { };

  /** @brief Similar to std::multiplies, but allows two different types. */
  template<typename _Tp1, typename _Tp2, typename _Result
	   = __typeof__(*static_cast<_Tp1*>(0)
			* *static_cast<_Tp2*>(0))>
    struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Result>
    {
      _Result
      operator()(const _Tp1& __x, const _Tp2& __y) const
      { return __x * __y; }
    };

  // Partial specialization for one type. Same as std::multiplies.
  template<typename _Tp>
    struct _Multiplies<_Tp, _Tp, _Tp>
    : public std::multiplies<_Tp> { };

#pragma GCC diagnostic pop // -Wdeprecated-declarations

  /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence.
   *  If features the usual random-access iterator functionality.
   *  @param _Tp Sequence _M_value type.
   *  @param _DifferenceTp Sequence difference type.
   */
  template<typename _Tp, typename _DifferenceTp>
    class _PseudoSequenceIterator
    {
    public:
      typedef _DifferenceTp _DifferenceType;

      _PseudoSequenceIterator(const _Tp& __val, _DifferenceType __pos)
      : _M_val(__val), _M_pos(__pos) { }

      // Pre-increment operator.
      _PseudoSequenceIterator&
      operator++()
      {
	++_M_pos;
	return *this;
      }

      // Post-increment operator.
      _PseudoSequenceIterator
      operator++(int)
      { return _PseudoSequenceIterator(_M_pos++); }

      const _Tp&
      operator*() const
      { return _M_val; }

      const _Tp&
      operator[](_DifferenceType) const
      { return _M_val; }

      bool
      operator==(const _PseudoSequenceIterator& __i2)
      { return _M_pos == __i2._M_pos; }

      bool
      operator!=(const _PseudoSequenceIterator& __i2)
      { return _M_pos != __i2._M_pos; }

      _DifferenceType
      operator-(const _PseudoSequenceIterator& __i2)
      { return _M_pos - __i2._M_pos; }

    private:
      const _Tp& _M_val;
      _DifferenceType _M_pos;
    };

  /** @brief Sequence that conceptually consists of multiple copies of
      the same element.
      *  The copies are not stored explicitly, of course.
      *  @param _Tp Sequence _M_value type.
      *  @param _DifferenceTp Sequence difference type.
      */
  template<typename _Tp, typename _DifferenceTp>
    class _PseudoSequence
    {
    public:
      typedef _DifferenceTp _DifferenceType;

      // Better cast down to uint64_t, than up to _DifferenceTp.
      typedef _PseudoSequenceIterator<_Tp, uint64_t> iterator;

      /** @brief Constructor.
       *  @param __val Element of the sequence.
       *  @param __count Number of (virtual) copies.
       */
      _PseudoSequence(const _Tp& __val, _DifferenceType __count)
      : _M_val(__val), _M_count(__count)  { }

      /** @brief Begin iterator. */
      iterator
      begin() const
      { return iterator(_M_val, 0); }

      /** @brief End iterator. */
      iterator
      end() const
      { return iterator(_M_val, _M_count); }

    private:
      const _Tp& _M_val;
      _DifferenceType _M_count;
    };

  /** @brief Compute the median of three referenced elements,
      according to @c __comp.
      *  @param __a First iterator.
      *  @param __b Second iterator.
      *  @param __c Third iterator.
      *  @param __comp Comparator.
      */
  template<typename _RAIter, typename _Compare>
    _RAIter
    __median_of_three_iterators(_RAIter __a, _RAIter __b,
				_RAIter __c, _Compare __comp)
    {
      if (__comp(*__a, *__b))
	if (__comp(*__b, *__c))
	  return __b;
	else
	  if (__comp(*__a, *__c))
	    return __c;
	  else
	    return __a;
      else
	{
	  // Just swap __a and __b.
	  if (__comp(*__a, *__c))
	    return __a;
	  else
	    if (__comp(*__b, *__c))
	      return __c;
	    else
	      return __b;
	}
    }

#if _GLIBCXX_PARALLEL_ASSERTIONS && defined(__glibcxx_assert_impl)
# define _GLIBCXX_PARALLEL_ASSERT(_Condition) \
  do { __glibcxx_assert_impl(_Condition); } while (false)
#else
# define _GLIBCXX_PARALLEL_ASSERT(_Condition) do { } while (false)
#endif

} //namespace __gnu_parallel

#endif /* _GLIBCXX_PARALLEL_BASE_H */
Commit	Line	Data
	1	// -- C++ --
	2
	3	// Copyright (C) 2007-2025 Free Software Foundation, Inc.
	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the terms
	7	// of the GNU General Public License as published by the Free Software
	8	// Foundation; either version 3, or (at your option) any later
	9	// version.
	10
	11	// This library is distributed in the hope that it will be useful, but
	12	// WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	14	// General Public License for more details.
	15
	16	// Under Section 7 of GPL version 3, you are granted additional
	17	// permissions described in the GCC Runtime Library Exception, version
	18	// 3.1, as published by the Free Software Foundation.
	19
	20	// You should have received a copy of the GNU General Public License and
	21	// a copy of the GCC Runtime Library Exception along with this program;
	22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	23	// <http://www.gnu.org/licenses/>.
	24
	25	/** @file parallel/base.h
	26	* @brief Sequential helper functions.
	27	* This file is a GNU parallel extension to the Standard C++ Library.
	28	*/
	29
	30	// Written by Johannes Singler.
	31
	32	#ifndef _GLIBCXX_PARALLEL_BASE_H
	33	#define _GLIBCXX_PARALLEL_BASE_H 1
	34
	35	#include <bits/c++config.h>
	36	#include <bits/stl_function.h>
	37	#include <omp.h>
	38	#include <parallel/features.h>
	39	#include <parallel/basic_iterator.h>
	40	#include <parallel/parallel.h>
	41
	42	// Parallel mode namespaces.
	43
	44	/**
	45	* @namespace std::__parallel
	46	* @brief GNU parallel code, replaces standard behavior with parallel behavior.
	47	*/
	48	namespace std _GLIBCXX_VISIBILITY(default)
	49	{
	50	namespace __parallel { }
	51	}
	52
	53	/**
	54	* @namespace __gnu_parallel
	55	* @brief GNU parallel code for public use.
	56	*/
	57	namespace __gnu_parallel
	58	{
	59	// Import all the parallel versions of components in namespace std.
	60	using namespace std::__parallel;
	61	}
	62
	63	/**
	64	* @namespace __gnu_sequential
	65	* @brief GNU sequential classes for public use.
	66	*/
	67	namespace __gnu_sequential
	68	{
	69	// Import whatever is the serial version.
	70	#ifdef _GLIBCXX_PARALLEL
	71	using namespace std::_GLIBCXX_STD_A;
	72	#else
	73	using namespace std;
	74	#endif
	75	}
	76
	77
	78	namespace __gnu_parallel
	79	{
	80	// NB: Including this file cannot produce (unresolved) symbols from
	81	// the OpenMP runtime unless the parallel mode is actually invoked
	82	// and active, which imples that the OpenMP runtime is actually
	83	// going to be linked in.
	84	inline _ThreadIndex
	85	__get_max_threads()
	86	{
	87	_ThreadIndex __i = omp_get_max_threads();
	88	return __i > 1 ? __i : 1;
	89	}
	90
	91
	92	inline bool
	93	__is_parallel(const _Parallelism __p) { return __p != sequential; }
	94
	95
	96	/** @brief Calculates the rounded-down logarithm of @c __n for base 2.
	97	* @param __n Argument.
	98	* @return Returns 0 for any argument <1.
	99	*/
	100	template<typename _Size>
	101	inline _Size
	102	__rd_log2(_Size __n)
	103	{
	104	_Size __k;
	105	for (__k = 0; __n > 1; __n >>= 1)
	106	++__k;
	107	return __k;
	108	}
	109
	110	/** @brief Encode two integers into one gnu_parallel::_CASable.
	111	* @param __a First integer, to be encoded in the most-significant @c
	112	* _CASable_bits/2 bits.
	113	* @param __b Second integer, to be encoded in the least-significant
	114	* @c _CASable_bits/2 bits.
	115	* @return value encoding @c __a and @c __b.
	116	* @see __decode2
	117	*/
	118	inline _CASable
	119	__encode2(int __a, int __b) //must all be non-negative, actually
	120	{
	121	return (((_CASable)__a) << (_CASable_bits / 2)) \| (((_CASable)__b) << 0);
	122	}
	123
	124	/** @brief Decode two integers from one gnu_parallel::_CASable.
	125	* @param __x __gnu_parallel::_CASable to decode integers from.
	126	* @param __a First integer, to be decoded from the most-significant
	127	* @c _CASable_bits/2 bits of @c __x.
	128	* @param __b Second integer, to be encoded in the least-significant
	129	* @c _CASable_bits/2 bits of @c __x.
	130	* @see __encode2
	131	*/
	132	inline void
	133	__decode2(_CASable __x, int& __a, int& __b)
	134	{
	135	__a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask);
	136	__b = (int)((__x >> 0 ) & _CASable_mask);
	137	}
	138
	139	//needed for parallel "numeric", even if "algorithm" not included
	140
	141	/** @brief Equivalent to std::min. */
	142	template<typename _Tp>
	143	inline const _Tp&
	144	min(const _Tp& __a, const _Tp& __b)
	145	{ return (__a < __b) ? __a : __b; }
	146
	147	/** @brief Equivalent to std::max. */
	148	template<typename _Tp>
	149	inline const _Tp&
	150	max(const _Tp& __a, const _Tp& __b)
	151	{ return (__a > __b) ? __a : __b; }
	152
	153	#pragma GCC diagnostic push
	154	#pragma GCC diagnostic ignored "-Wdeprecated-declarations" // *nary_function
	155
	156	/** @brief Constructs predicate for equality from strict weak
	157	* ordering predicate
	158	*/
	159	template<typename _T1, typename _T2, typename _Compare>
	160	class _EqualFromLess : public std::binary_function<_T1, _T2, bool>
	161	{
	162	private:
	163	_Compare& _M_comp;
	164
	165	public:
	166	_EqualFromLess(_Compare& __comp) : _M_comp(__comp) { }
	167
	168	bool operator()(const _T1& __a, const _T2& __b)
	169	{ return !_M_comp(__a, __b) && !_M_comp(__b, __a); }
	170	};
	171
	172	/** @brief Similar to std::unary_negate,
	173	* but giving the argument types explicitly. */
	174	template<typename _Predicate, typename argument_type>
	175	class __unary_negate
	176	: public std::unary_function<argument_type, bool>
	177	{
	178	protected:
	179	_Predicate _M_pred;
	180
	181	public:
	182	explicit
	183	__unary_negate(const _Predicate& __x) : _M_pred(__x) { }
	184
	185	bool
	186	operator()(const argument_type& __x)
	187	{ return !_M_pred(__x); }
	188	};
	189
	190	/** @brief Similar to std::binder1st,
	191	* but giving the argument types explicitly. */
	192	template<typename _Operation, typename _FirstArgumentType,
	193	typename _SecondArgumentType, typename _ResultType>
	194	class __binder1st
	195	: public std::unary_function<_SecondArgumentType, _ResultType>
	196	{
	197	protected:
	198	_Operation _M_op;
	199	_FirstArgumentType _M_value;
	200
	201	public:
	202	__binder1st(const _Operation& __x, const _FirstArgumentType& __y)
	203	: _M_op(__x), _M_value(__y) { }
	204
	205	_ResultType
	206	operator()(const _SecondArgumentType& __x)
	207	{ return _M_op(_M_value, __x); }
	208
	209	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	210	// 109. Missing binders for non-const sequence elements
	211	_ResultType
	212	operator()(_SecondArgumentType& __x) const
	213	{ return _M_op(_M_value, __x); }
	214	};
	215
	216	/**
	217	* @brief Similar to std::binder2nd, but giving the argument types
	218	* explicitly.
	219	*/
	220	template<typename _Operation, typename _FirstArgumentType,
	221	typename _SecondArgumentType, typename _ResultType>
	222	class __binder2nd
	223	: public std::unary_function<_FirstArgumentType, _ResultType>
	224	{
	225	protected:
	226	_Operation _M_op;
	227	_SecondArgumentType _M_value;
	228
	229	public:
	230	__binder2nd(const _Operation& __x, const _SecondArgumentType& __y)
	231	: _M_op(__x), _M_value(__y) { }
	232
	233	_ResultType
	234	operator()(const _FirstArgumentType& __x) const
	235	{ return _M_op(__x, _M_value); }
	236
	237	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	238	// 109. Missing binders for non-const sequence elements
	239	_ResultType
	240	operator()(_FirstArgumentType& __x)
	241	{ return _M_op(__x, _M_value); }
	242	};
	243
	244	/** @brief Similar to std::equal_to, but allows two different types. */
	245	template<typename _T1, typename _T2>
	246	struct _EqualTo : std::binary_function<_T1, _T2, bool>
	247	{
	248	bool operator()(const _T1& __t1, const _T2& __t2) const
	249	{ return __t1 == __t2; }
	250	};
	251
	252	/** @brief Similar to std::less, but allows two different types. */
	253	template<typename _T1, typename _T2>
	254	struct _Less : std::binary_function<_T1, _T2, bool>
	255	{
	256	bool
	257	operator()(const _T1& __t1, const _T2& __t2) const
	258	{ return __t1 < __t2; }
	259
	260	bool
	261	operator()(const _T2& __t2, const _T1& __t1) const
	262	{ return __t2 < __t1; }
	263	};
	264
	265	// Partial specialization for one type. Same as std::less.
	266	template<typename _Tp>
	267	struct _Less<_Tp, _Tp>
	268	: public std::less<_Tp> { };
	269
	270	/** @brief Similar to std::plus, but allows two different types. */
	271	template<typename _Tp1, typename _Tp2, typename _Result
	272	= __typeof__(static_cast<_Tp1>(0)
	273	+ static_cast<_Tp2>(0))>
	274	struct _Plus : public std::binary_function<_Tp1, _Tp2, _Result>
	275	{
	276	_Result
	277	operator()(const _Tp1& __x, const _Tp2& __y) const
	278	{ return __x + __y; }
	279	};
	280
	281	// Partial specialization for one type. Same as std::plus.
	282	template<typename _Tp>
	283	struct _Plus<_Tp, _Tp, _Tp>
	284	: public std::plus<_Tp> { };
	285
	286	/** @brief Similar to std::multiplies, but allows two different types. */
	287	template<typename _Tp1, typename _Tp2, typename _Result
	288	= __typeof__(static_cast<_Tp1>(0)
	289	* static_cast<_Tp2>(0))>
	290	struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Result>
	291	{
	292	_Result
	293	operator()(const _Tp1& __x, const _Tp2& __y) const
	294	{ return __x * __y; }
	295	};
	296
	297	// Partial specialization for one type. Same as std::multiplies.
	298	template<typename _Tp>
	299	struct _Multiplies<_Tp, _Tp, _Tp>
	300	: public std::multiplies<_Tp> { };
	301
	302	#pragma GCC diagnostic pop // -Wdeprecated-declarations
	303
	304	/** @brief _Iterator associated with __gnu_parallel::_PseudoSequence.
	305	* If features the usual random-access iterator functionality.
	306	* @param _Tp Sequence _M_value type.
	307	* @param _DifferenceTp Sequence difference type.
	308	*/
	309	template<typename _Tp, typename _DifferenceTp>
	310	class _PseudoSequenceIterator
	311	{
	312	public:
	313	typedef _DifferenceTp _DifferenceType;
	314
	315	_PseudoSequenceIterator(const _Tp& __val, _DifferenceType __pos)
	316	: _M_val(__val), _M_pos(__pos) { }
	317
	318	// Pre-increment operator.
	319	_PseudoSequenceIterator&
	320	operator++()
	321	{
	322	++_M_pos;
	323	return *this;
	324	}
	325
	326	// Post-increment operator.
	327	_PseudoSequenceIterator
	328	operator++(int)
	329	{ return _PseudoSequenceIterator(_M_pos++); }
	330
	331	const _Tp&
	332	operator*() const
	333	{ return _M_val; }
	334
	335	const _Tp&
	336	operator[](_DifferenceType) const
	337	{ return _M_val; }
	338
	339	bool
	340	operator==(const _PseudoSequenceIterator& __i2)
	341	{ return _M_pos == __i2._M_pos; }
	342
	343	bool
	344	operator!=(const _PseudoSequenceIterator& __i2)
	345	{ return _M_pos != __i2._M_pos; }
	346
	347	_DifferenceType
	348	operator-(const _PseudoSequenceIterator& __i2)
	349	{ return _M_pos - __i2._M_pos; }
	350
	351	private:
	352	const _Tp& _M_val;
	353	_DifferenceType _M_pos;
	354	};
	355
	356	/** @brief Sequence that conceptually consists of multiple copies of
	357	the same element.
	358	* The copies are not stored explicitly, of course.
	359	* @param _Tp Sequence _M_value type.
	360	* @param _DifferenceTp Sequence difference type.
	361	*/
	362	template<typename _Tp, typename _DifferenceTp>
	363	class _PseudoSequence
	364	{
	365	public:
	366	typedef _DifferenceTp _DifferenceType;
	367
	368	// Better cast down to uint64_t, than up to _DifferenceTp.
	369	typedef _PseudoSequenceIterator<_Tp, uint64_t> iterator;
	370
	371	/** @brief Constructor.
	372	* @param __val Element of the sequence.
	373	* @param __count Number of (virtual) copies.
	374	*/
	375	_PseudoSequence(const _Tp& __val, _DifferenceType __count)
	376	: _M_val(__val), _M_count(__count) { }
	377
	378	/** @brief Begin iterator. */
	379	iterator
	380	begin() const
	381	{ return iterator(_M_val, 0); }
	382
	383	/** @brief End iterator. */
	384	iterator
	385	end() const
	386	{ return iterator(_M_val, _M_count); }
	387
	388	private:
	389	const _Tp& _M_val;
	390	_DifferenceType _M_count;
	391	};
	392
	393	/** @brief Compute the median of three referenced elements,
	394	according to @c __comp.
	395	* @param __a First iterator.
	396	* @param __b Second iterator.
	397	* @param __c Third iterator.
	398	* @param __comp Comparator.
	399	*/
	400	template<typename _RAIter, typename _Compare>
	401	_RAIter
	402	__median_of_three_iterators(_RAIter __a, _RAIter __b,
	403	_RAIter __c, _Compare __comp)
	404	{
	405	if (__comp(__a, __b))
	406	if (__comp(__b, __c))
	407	return __b;
	408	else
	409	if (__comp(__a, __c))
	410	return __c;
	411	else
	412	return __a;
	413	else
	414	{
	415	// Just swap __a and __b.
	416	if (__comp(__a, __c))
	417	return __a;
	418	else
	419	if (__comp(__b, __c))
	420	return __c;
	421	else
	422	return __b;
	423	}
	424	}
	425
	426	#if _GLIBCXX_PARALLEL_ASSERTIONS && defined(__glibcxx_assert_impl)
	427	# define _GLIBCXX_PARALLEL_ASSERT(_Condition) \
	428	do { __glibcxx_assert_impl(_Condition); } while (false)
	429	#else
	430	# define _GLIBCXX_PARALLEL_ASSERT(_Condition) do { } while (false)
	431	#endif
	432
	433	} //namespace __gnu_parallel
	434
	435	#endif /* _GLIBCXX_PARALLEL_BASE_H */