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

// -*- C++ -*-

// Copyright (C) 2007-2022 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/set_operations.h
 * @brief Parallel implementations of set operations for random-access
 * iterators.
 *  This file is a GNU parallel extension to the Standard C++ Library.
 */

// Written by Marius Elvert and Felix Bondarenko.

#ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H
#define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1

#include <omp.h>

#include <parallel/settings.h>
#include <parallel/multiseq_selection.h>

namespace __gnu_parallel
{
  template<typename _IIter, typename _OutputIterator>
    _OutputIterator
    __copy_tail(std::pair<_IIter, _IIter> __b,
		std::pair<_IIter, _IIter> __e, _OutputIterator __r)
    {
      if (__b.first != __e.first)
	{
          do
            {
              *__r++ = *__b.first++;
            }
          while (__b.first != __e.first);
	}
      else
	{
          while (__b.second != __e.second)
            *__r++ = *__b.second++;
	}
      return __r;
    }

  template<typename _IIter,
           typename _OutputIterator,
           typename _Compare>
    struct __symmetric_difference_func
    {
      typedef std::iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::difference_type _DifferenceType;
      typedef typename std::pair<_IIter, _IIter> _IteratorPair;

      __symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {}

      _Compare _M_comp;

      _OutputIterator
      _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
		_OutputIterator __r) const
      {
	while (__a != __b && __c != __d)
          {
            if (_M_comp(*__a, *__c))
              {
        	*__r = *__a;
        	++__a;
        	++__r;
              }
            else if (_M_comp(*__c, *__a))
              {
        	*__r = *__c;
        	++__c;
        	++__r;
              }
            else
              {
        	++__a;
        	++__c;
              }
          }
	return std::copy(__c, __d, std::copy(__a, __b, __r));
      }

      _DifferenceType
      __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
      {
	_DifferenceType __counter = 0;

	while (__a != __b && __c != __d)
          {
            if (_M_comp(*__a, *__c))
              {
        	++__a;
        	++__counter;
              }
            else if (_M_comp(*__c, *__a))
              {
        	++__c;
        	++__counter;
              }
            else
              {
        	++__a;
        	++__c;
              }
          }

	return __counter + (__b - __a) + (__d - __c);
      }

      _OutputIterator
      __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
      { return std::copy(__c, __d, __out); }

      _OutputIterator
      __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
      { return std::copy(__a, __b, __out); }
    };


  template<typename _IIter,
           typename _OutputIterator,
           typename _Compare>
    struct __difference_func
    {
      typedef std::iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::difference_type _DifferenceType;
      typedef typename std::pair<_IIter, _IIter> _IteratorPair;

      __difference_func(_Compare __comp) : _M_comp(__comp) {}

      _Compare _M_comp;

      _OutputIterator
      _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
		_OutputIterator __r) const
      {
	while (__a != __b && __c != __d)
          {
            if (_M_comp(*__a, *__c))
              {
        	*__r = *__a;
        	++__a;
        	++__r;
              }
            else if (_M_comp(*__c, *__a))
              { ++__c; }
            else
              {
        	++__a;
        	++__c;
              }
          }
	return std::copy(__a, __b, __r);
      }

      _DifferenceType
      __count(_IIter __a, _IIter __b,
	      _IIter __c, _IIter __d) const
      {
	_DifferenceType __counter = 0;

	while (__a != __b && __c != __d)
          {
            if (_M_comp(*__a, *__c))
              {
        	++__a;
        	++__counter;
              }
            else if (_M_comp(*__c, *__a))
              { ++__c; }
            else
              { ++__a; ++__c; }
          }

	return __counter + (__b - __a);
      }

      _OutputIterator
      __first_empty(_IIter, _IIter, _OutputIterator __out) const
      { return __out; }

      _OutputIterator
      __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
      { return std::copy(__a, __b, __out); }
    };


  template<typename _IIter,
           typename _OutputIterator,
           typename _Compare>
    struct __intersection_func
    {
      typedef std::iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::difference_type _DifferenceType;
      typedef typename std::pair<_IIter, _IIter> _IteratorPair;

      __intersection_func(_Compare __comp) : _M_comp(__comp) {}

      _Compare _M_comp;

      _OutputIterator
      _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
		_OutputIterator __r) const
      {
	while (__a != __b && __c != __d)
          {
            if (_M_comp(*__a, *__c))
              { ++__a; }
            else if (_M_comp(*__c, *__a))
              { ++__c; }
            else
              {
        	*__r = *__a;
        	++__a;
        	++__c;
        	++__r;
              }
          }

	return __r;
      }

      _DifferenceType
      __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
      {
	_DifferenceType __counter = 0;

	while (__a != __b && __c != __d)
          {
            if (_M_comp(*__a, *__c))
              { ++__a; }
            else if (_M_comp(*__c, *__a))
              { ++__c; }
            else
              {
        	++__a;
        	++__c;
        	++__counter;
              }
          }

	return __counter;
      }

      _OutputIterator
      __first_empty(_IIter, _IIter, _OutputIterator __out) const
      { return __out; }

      _OutputIterator
      __second_empty(_IIter, _IIter, _OutputIterator __out) const
      { return __out; }
    };

  template<class _IIter, class _OutputIterator, class _Compare>
    struct __union_func
    {
      typedef typename std::iterator_traits<_IIter>::difference_type
      _DifferenceType;

      __union_func(_Compare __comp) : _M_comp(__comp) {}

      _Compare _M_comp;

      _OutputIterator
      _M_invoke(_IIter __a, const _IIter __b, _IIter __c,
		const _IIter __d, _OutputIterator __r) const
      {
	while (__a != __b && __c != __d)
          {
            if (_M_comp(*__a, *__c))
              {
        	*__r = *__a;
        	++__a;
              }
            else if (_M_comp(*__c, *__a))
              {
        	*__r = *__c;
        	++__c;
              }
            else
              {
        	*__r = *__a;
        	++__a;
        	++__c;
              }
            ++__r;
          }
	return std::copy(__c, __d, std::copy(__a, __b, __r));
      }

      _DifferenceType
      __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
      {
	_DifferenceType __counter = 0;

	while (__a != __b && __c != __d)
          {
            if (_M_comp(*__a, *__c))
              { ++__a; }
            else if (_M_comp(*__c, *__a))
              { ++__c; }
            else
              {
        	++__a;
        	++__c;
              }
            ++__counter;
          }

	__counter += (__b - __a);
	__counter += (__d - __c);
	return __counter;
      }

      _OutputIterator
      __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
      { return std::copy(__c, __d, __out); }

      _OutputIterator
      __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
      { return std::copy(__a, __b, __out); }
    };

  template<typename _IIter,
           typename _OutputIterator,
           typename _Operation>
    _OutputIterator
    __parallel_set_operation(_IIter __begin1, _IIter __end1,
			     _IIter __begin2, _IIter __end2,
			     _OutputIterator __result, _Operation __op)
    {
      _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2))

      typedef std::iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::difference_type _DifferenceType;
      typedef typename std::pair<_IIter, _IIter> _IteratorPair;

      if (__begin1 == __end1)
	return __op.__first_empty(__begin2, __end2, __result);

      if (__begin2 == __end2)
	return __op.__second_empty(__begin1, __end1, __result);

      const _DifferenceType __size = (__end1 - __begin1) + (__end2 - __begin2);

      const _IteratorPair __sequence[2] = { std::make_pair(__begin1, __end1),
					    std::make_pair(__begin2, __end2) };
      _OutputIterator __return_value = __result;
      _DifferenceType *__borders;
      _IteratorPair *__block_begins;
      _DifferenceType* __lengths;

      _ThreadIndex __num_threads =
          std::min<_DifferenceType>(__get_max_threads(),
              std::min(__end1 - __begin1, __end2 - __begin2));

#     pragma omp parallel num_threads(__num_threads)
      {
#       pragma omp single
	{
	  __num_threads = omp_get_num_threads();

	  __borders = new _DifferenceType[__num_threads + 2];
	  __equally_split(__size, __num_threads + 1, __borders);
	  __block_begins = new _IteratorPair[__num_threads + 1];
	  // Very __start.
	  __block_begins[0] = std::make_pair(__begin1, __begin2);
	  __lengths = new _DifferenceType[__num_threads];
	} //single

	_ThreadIndex __iam = omp_get_thread_num();

	// _Result from multiseq_partition.
	_IIter __offset[2];
	const _DifferenceType __rank = __borders[__iam + 1];

	multiseq_partition(__sequence, __sequence + 2,
			   __rank, __offset, __op._M_comp);

	// allowed to read?
	// together
	// *(__offset[ 0 ] - 1) == *__offset[ 1 ]
	if (__offset[ 0 ] != __begin1 && __offset[1] != __end2
	    && !__op._M_comp(*(__offset[0] - 1), *__offset[1])
	    && !__op._M_comp(*__offset[1], *(__offset[0] - 1)))
	  {
	    // Avoid split between globally equal elements: move one to
	    // front in first sequence.
              --__offset[0];
	  }

	_IteratorPair __block_end = __block_begins[__iam + 1] =
	  _IteratorPair(__offset[0], __offset[1]);

	// Make sure all threads have their block_begin result written out.
#       pragma omp barrier

	_IteratorPair __block_begin = __block_begins[__iam];

	// Begin working for the first block, while the others except
	// the last start to count.
	if (__iam == 0)
	  {
	    // The first thread can copy already.
	    __lengths[ __iam ] =
	      __op._M_invoke(__block_begin.first, __block_end.first,
			     __block_begin.second, __block_end.second,
			     __result) - __result;
	  }
	else
	  {
	    __lengths[ __iam ] =
	      __op.__count(__block_begin.first, __block_end.first,
			   __block_begin.second, __block_end.second);
	  }

	// Make sure everyone wrote their lengths.
#       pragma omp barrier

	_OutputIterator __r = __result;

	if (__iam == 0)
	  {
	    // Do the last block.
	    for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
	      __r += __lengths[__i];

	    __block_begin = __block_begins[__num_threads];

	    // Return the result iterator of the last block.
	    __return_value =
	      __op._M_invoke(__block_begin.first, __end1,
			     __block_begin.second, __end2, __r);

	  }
          else
            {
              for (_ThreadIndex __i = 0; __i < __iam; ++__i)
        	__r += __lengths[ __i ];

              // Reset begins for copy pass.
              __op._M_invoke(__block_begin.first, __block_end.first,
			     __block_begin.second, __block_end.second, __r);
            }
	}
      return __return_value;
    }

  template<typename _IIter,
           typename _OutputIterator,
           typename _Compare>
    inline _OutputIterator
    __parallel_set_union(_IIter __begin1, _IIter __end1,
			 _IIter __begin2, _IIter __end2,
			 _OutputIterator __result, _Compare __comp)
    {
      return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
				      __result,
				      __union_func< _IIter, _OutputIterator,
				      _Compare>(__comp));
    }

  template<typename _IIter,
           typename _OutputIterator,
           typename _Compare>
    inline _OutputIterator
    __parallel_set_intersection(_IIter __begin1, _IIter __end1,
                        	_IIter __begin2, _IIter __end2,
                        	_OutputIterator __result, _Compare __comp)
    {
      return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
				      __result,
				      __intersection_func<_IIter,
				      _OutputIterator, _Compare>(__comp));
    }

  template<typename _IIter,
           typename _OutputIterator,
           typename _Compare>
    inline _OutputIterator
    __parallel_set_difference(_IIter __begin1, _IIter __end1,
                              _IIter __begin2, _IIter __end2,
                              _OutputIterator __result, _Compare __comp)
    {
      return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
				      __result,
				      __difference_func<_IIter,
				      _OutputIterator, _Compare>(__comp));
    }

  template<typename _IIter,
           typename _OutputIterator,
           typename _Compare>
    inline _OutputIterator
    __parallel_set_symmetric_difference(_IIter __begin1, _IIter __end1,
                                	_IIter __begin2, _IIter __end2,
                                	_OutputIterator __result,
                                	_Compare __comp)
    {
      return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
				      __result,
				      __symmetric_difference_func<_IIter,
				      _OutputIterator, _Compare>(__comp));
    }
}

#endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */
Commit	Line	Data
c2ba9709 JS	1	// -- C++ --
c2ba9709 JS	2
7adcbafe	3	// Copyright (C) 2007-2022 Free Software Foundation, Inc.
c2ba9709 JS	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
748086b7	8	// Foundation; either version 3, or (at your option) any later
c2ba9709 JS	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
748086b7 JJ	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.
c2ba9709	19
748086b7 JJ	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/>.
c2ba9709 JS	24
	25	/**
	26	* @file parallel/set_operations.h
	27	* @brief Parallel implementations of set operations for random-access
	28	* iterators.
	29	* This file is a GNU parallel extension to the Standard C++ Library.
	30	*/
	31
	32	// Written by Marius Elvert and Felix Bondarenko.
	33
	34	#ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H
	35	#define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1
	36
	37	#include <omp.h>
	38
	39	#include <parallel/settings.h>
	40	#include <parallel/multiseq_selection.h>
	41
	42	namespace __gnu_parallel
	43	{
77d16198 PC	44	template<typename _IIter, typename _OutputIterator>
	45	_OutputIterator
	46	__copy_tail(std::pair<_IIter, _IIter> __b,
	47	std::pair<_IIter, _IIter> __e, _OutputIterator __r)
	48	{
	49	if (__b.first != __e.first)
	50	{
	51	do
	52	{
	53	__r++ = __b.first++;
	54	}
	55	while (__b.first != __e.first);
	56	}
	57	else
	58	{
	59	while (__b.second != __e.second)
	60	__r++ = __b.second++;
	61	}
	62	return __r;
	63	}
	64
	65	template<typename _IIter,
	66	typename _OutputIterator,
	67	typename _Compare>
	68	struct __symmetric_difference_func
	69	{
	70	typedef std::iterator_traits<_IIter> _TraitsType;
	71	typedef typename _TraitsType::difference_type _DifferenceType;
	72	typedef typename std::pair<_IIter, _IIter> _IteratorPair;
	73
	74	__symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {}
	75
	76	_Compare _M_comp;
	77
	78	_OutputIterator
	79	_M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
	80	_OutputIterator __r) const
c2ba9709	81	{
77d16198	82	while (__a != __b && __c != __d)
e683ee2a	83	{
77d16198 PC	84	if (_M_comp(__a, __c))
	85	{
	86	__r = __a;
	87	++__a;
	88	++__r;
	89	}
	90	else if (_M_comp(__c, __a))
	91	{
	92	__r = __c;
	93	++__c;
	94	++__r;
	95	}
	96	else
	97	{
	98	++__a;
	99	++__c;
	100	}
e683ee2a	101	}
77d16198	102	return std::copy(__c, __d, std::copy(__a, __b, __r));
c2ba9709	103	}
77d16198 PC	104
77d16198 PC	105	_DifferenceType
6e687a9a	106	__count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
c2ba9709	107	{
77d16198 PC	108	_DifferenceType __counter = 0;
77d16198 PC	109
6e687a9a	110	while (__a != __b && __c != __d)
77d16198 PC	111	{
	112	if (_M_comp(__a, __c))
	113	{
	114	++__a;
	115	++__counter;
	116	}
	117	else if (_M_comp(__c, __a))
	118	{
	119	++__c;
	120	++__counter;
	121	}
	122	else
	123	{
	124	++__a;
	125	++__c;
	126	}
	127	}
	128
6e687a9a	129	return __counter + (__b - __a) + (__d - __c);
c2ba9709	130	}
c2ba9709	131
77d16198	132	_OutputIterator
6e687a9a RW	133	__first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
6e687a9a RW	134	{ return std::copy(__c, __d, __out); }
c2ba9709	135
77d16198 PC	136	_OutputIterator
	137	__second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
	138	{ return std::copy(__a, __b, __out); }
	139	};
c2ba9709	140
c2ba9709	141
77d16198 PC	142	template<typename _IIter,
	143	typename _OutputIterator,
	144	typename _Compare>
	145	struct __difference_func
c2ba9709	146	{
77d16198 PC	147	typedef std::iterator_traits<_IIter> _TraitsType;
	148	typedef typename _TraitsType::difference_type _DifferenceType;
	149	typedef typename std::pair<_IIter, _IIter> _IteratorPair;
c2ba9709	150
77d16198	151	__difference_func(_Compare __comp) : _M_comp(__comp) {}
c2ba9709	152
77d16198	153	_Compare _M_comp;
c2ba9709	154
77d16198	155	_OutputIterator
6e687a9a	156	_M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
77d16198 PC	157	_OutputIterator __r) const
77d16198 PC	158	{
6e687a9a	159	while (__a != __b && __c != __d)
77d16198 PC	160	{
	161	if (_M_comp(__a, __c))
	162	{
	163	__r = __a;
	164	++__a;
	165	++__r;
	166	}
	167	else if (_M_comp(__c, __a))
	168	{ ++__c; }
	169	else
	170	{
	171	++__a;
	172	++__c;
	173	}
	174	}
	175	return std::copy(__a, __b, __r);
	176	}
c2ba9709	177
77d16198 PC	178	_DifferenceType
77d16198 PC	179	__count(_IIter __a, _IIter __b,
6e687a9a	180	_IIter __c, _IIter __d) const
77d16198 PC	181	{
77d16198 PC	182	_DifferenceType __counter = 0;
c2ba9709	183
6e687a9a	184	while (__a != __b && __c != __d)
77d16198 PC	185	{
	186	if (_M_comp(__a, __c))
	187	{
	188	++__a;
	189	++__counter;
	190	}
	191	else if (_M_comp(__c, __a))
	192	{ ++__c; }
	193	else
	194	{ ++__a; ++__c; }
	195	}
c2ba9709	196
77d16198 PC	197	return __counter + (__b - __a);
77d16198 PC	198	}
c2ba9709	199
77d16198 PC	200	_OutputIterator
	201	__first_empty(_IIter, _IIter, _OutputIterator __out) const
	202	{ return __out; }
c2ba9709	203
77d16198 PC	204	_OutputIterator
	205	__second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
	206	{ return std::copy(__a, __b, __out); }
	207	};
c2ba9709	208
c2ba9709	209
77d16198 PC	210	template<typename _IIter,
	211	typename _OutputIterator,
	212	typename _Compare>
	213	struct __intersection_func
c2ba9709	214	{
77d16198 PC	215	typedef std::iterator_traits<_IIter> _TraitsType;
	216	typedef typename _TraitsType::difference_type _DifferenceType;
	217	typedef typename std::pair<_IIter, _IIter> _IteratorPair;
c2ba9709	218
77d16198	219	__intersection_func(_Compare __comp) : _M_comp(__comp) {}
c2ba9709	220
77d16198	221	_Compare _M_comp;
c2ba9709	222
77d16198 PC	223	_OutputIterator
	224	_M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
	225	_OutputIterator __r) const
	226	{
	227	while (__a != __b && __c != __d)
	228	{
	229	if (_M_comp(__a, __c))
	230	{ ++__a; }
	231	else if (_M_comp(__c, __a))
	232	{ ++__c; }
	233	else
	234	{
	235	__r = __a;
	236	++__a;
	237	++__c;
	238	++__r;
	239	}
	240	}
c2ba9709	241
77d16198 PC	242	return __r;
77d16198 PC	243	}
c2ba9709	244
77d16198 PC	245	_DifferenceType
	246	__count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
	247	{
	248	_DifferenceType __counter = 0;
c2ba9709	249
77d16198 PC	250	while (__a != __b && __c != __d)
	251	{
	252	if (_M_comp(__a, __c))
	253	{ ++__a; }
	254	else if (_M_comp(__c, __a))
	255	{ ++__c; }
	256	else
	257	{
	258	++__a;
	259	++__c;
	260	++__counter;
	261	}
	262	}
c2ba9709	263
77d16198 PC	264	return __counter;
77d16198 PC	265	}
c2ba9709	266
77d16198 PC	267	_OutputIterator
	268	__first_empty(_IIter, _IIter, _OutputIterator __out) const
	269	{ return __out; }
c2ba9709	270
77d16198 PC	271	_OutputIterator
	272	__second_empty(_IIter, _IIter, _OutputIterator __out) const
	273	{ return __out; }
	274	};
c2ba9709	275
77d16198 PC	276	template<class _IIter, class _OutputIterator, class _Compare>
77d16198 PC	277	struct __union_func
c2ba9709	278	{
77d16198 PC	279	typedef typename std::iterator_traits<_IIter>::difference_type
77d16198 PC	280	_DifferenceType;
c2ba9709	281
77d16198	282	__union_func(_Compare __comp) : _M_comp(__comp) {}
c2ba9709	283
77d16198	284	_Compare _M_comp;
c2ba9709	285
77d16198 PC	286	_OutputIterator
	287	_M_invoke(_IIter __a, const _IIter __b, _IIter __c,
	288	const _IIter __d, _OutputIterator __r) const
	289	{
	290	while (__a != __b && __c != __d)
	291	{
	292	if (_M_comp(__a, __c))
	293	{
	294	__r = __a;
	295	++__a;
	296	}
	297	else if (_M_comp(__c, __a))
	298	{
	299	__r = __c;
	300	++__c;
	301	}
	302	else
	303	{
	304	__r = __a;
	305	++__a;
	306	++__c;
	307	}
	308	++__r;
	309	}
	310	return std::copy(__c, __d, std::copy(__a, __b, __r));
	311	}
c2ba9709	312
77d16198 PC	313	_DifferenceType
	314	__count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
	315	{
	316	_DifferenceType __counter = 0;
c2ba9709	317
77d16198 PC	318	while (__a != __b && __c != __d)
	319	{
	320	if (_M_comp(__a, __c))
	321	{ ++__a; }
	322	else if (_M_comp(__c, __a))
	323	{ ++__c; }
	324	else
	325	{
	326	++__a;
	327	++__c;
	328	}
	329	++__counter;
	330	}
c2ba9709	331
77d16198 PC	332	__counter += (__b - __a);
	333	__counter += (__d - __c);
	334	return __counter;
	335	}
c2ba9709	336
77d16198 PC	337	_OutputIterator
	338	__first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
	339	{ return std::copy(__c, __d, __out); }
c2ba9709	340
77d16198 PC	341	_OutputIterator
	342	__second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
	343	{ return std::copy(__a, __b, __out); }
	344	};
c2ba9709	345
77d16198 PC	346	template<typename _IIter,
77d16198 PC	347	typename _OutputIterator,
2d9ca17b	348	typename _Operation>
1acba85b	349	_OutputIterator
77d16198 PC	350	__parallel_set_operation(_IIter __begin1, _IIter __end1,
77d16198 PC	351	_IIter __begin2, _IIter __end2,
2d9ca17b	352	_OutputIterator __result, _Operation __op)
c2ba9709	353	{
77d16198	354	_GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2))
c2ba9709	355
77d16198 PC	356	typedef std::iterator_traits<_IIter> _TraitsType;
	357	typedef typename _TraitsType::difference_type _DifferenceType;
	358	typedef typename std::pair<_IIter, _IIter> _IteratorPair;
c2ba9709	359
77d16198 PC	360	if (__begin1 == __end1)
77d16198 PC	361	return __op.__first_empty(__begin2, __end2, __result);
c2ba9709	362
77d16198 PC	363	if (__begin2 == __end2)
77d16198 PC	364	return __op.__second_empty(__begin1, __end1, __result);
c2ba9709	365
77d16198 PC	366	const _DifferenceType __size = (__end1 - __begin1) + (__end2 - __begin2);
	367
	368	const _IteratorPair __sequence[2] = { std::make_pair(__begin1, __end1),
	369	std::make_pair(__begin2, __end2) };
	370	_OutputIterator __return_value = __result;
	371	_DifferenceType *__borders;
	372	_IteratorPair *__block_begins;
	373	_DifferenceType* __lengths;
	374
	375	_ThreadIndex __num_threads =
	376	std::min<_DifferenceType>(__get_max_threads(),
	377	std::min(__end1 - __begin1, __end2 - __begin2));
	378
	379	# pragma omp parallel num_threads(__num_threads)
e683ee2a JS	380	{
e683ee2a JS	381	# pragma omp single
77d16198 PC	382	{
	383	__num_threads = omp_get_num_threads();
	384
	385	__borders = new _DifferenceType[__num_threads + 2];
6b77089f	386	__equally_split(__size, __num_threads + 1, __borders);
77d16198 PC	387	__block_begins = new _IteratorPair[__num_threads + 1];
	388	// Very __start.
	389	__block_begins[0] = std::make_pair(__begin1, __begin2);
	390	__lengths = new _DifferenceType[__num_threads];
	391	} //single
	392
	393	_ThreadIndex __iam = omp_get_thread_num();
	394
	395	// _Result from multiseq_partition.
	396	_IIter __offset[2];
	397	const _DifferenceType __rank = __borders[__iam + 1];
	398
	399	multiseq_partition(__sequence, __sequence + 2,
	400	__rank, __offset, __op._M_comp);
	401
	402	// allowed to read?
	403	// together
	404	// (__offset[ 0 ] - 1) == __offset[ 1 ]
	405	if (__offset[ 0 ] != __begin1 && __offset[1] != __end2
	406	&& !__op._M_comp((__offset[0] - 1), __offset[1])
	407	&& !__op._M_comp(__offset[1], (__offset[0] - 1)))
	408	{
	409	// Avoid split between globally equal elements: move one to
	410	// front in first sequence.
	411	--__offset[0];
	412	}
	413
	414	_IteratorPair __block_end = __block_begins[__iam + 1] =
	415	_IteratorPair(__offset[0], __offset[1]);
	416
	417	// Make sure all threads have their block_begin result written out.
	418	# pragma omp barrier
e683ee2a	419
77d16198 PC	420	_IteratorPair __block_begin = __block_begins[__iam];
	421
	422	// Begin working for the first block, while the others except
	423	// the last start to count.
	424	if (__iam == 0)
	425	{
	426	// The first thread can copy already.
	427	__lengths[ __iam ] =
	428	__op._M_invoke(__block_begin.first, __block_end.first,
	429	__block_begin.second, __block_end.second,
	430	__result) - __result;
	431	}
	432	else
	433	{
	434	__lengths[ __iam ] =
	435	__op.__count(__block_begin.first, __block_end.first,
	436	__block_begin.second, __block_end.second);
	437	}
	438
	439	// Make sure everyone wrote their lengths.
e683ee2a JS	440	# pragma omp barrier
e683ee2a JS	441
77d16198	442	_OutputIterator __r = __result;
e683ee2a	443
77d16198 PC	444	if (__iam == 0)
	445	{
	446	// Do the last block.
8b0c13a8	447	for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
77d16198	448	__r += __lengths[__i];
e683ee2a	449
77d16198	450	__block_begin = __block_begins[__num_threads];
e683ee2a	451
77d16198 PC	452	// Return the result iterator of the last block.
	453	__return_value =
	454	__op._M_invoke(__block_begin.first, __end1,
	455	__block_begin.second, __end2, __r);
e683ee2a	456
77d16198 PC	457	}
	458	else
	459	{
8b0c13a8	460	for (_ThreadIndex __i = 0; __i < __iam; ++__i)
77d16198	461	__r += __lengths[ __i ];
e683ee2a	462
77d16198 PC	463	// Reset begins for copy pass.
	464	__op._M_invoke(__block_begin.first, __block_end.first,
	465	__block_begin.second, __block_end.second, __r);
	466	}
	467	}
	468	return __return_value;
	469	}
e683ee2a	470
77d16198 PC	471	template<typename _IIter,
	472	typename _OutputIterator,
	473	typename _Compare>
	474	inline _OutputIterator
	475	__parallel_set_union(_IIter __begin1, _IIter __end1,
	476	_IIter __begin2, _IIter __end2,
	477	_OutputIterator __result, _Compare __comp)
	478	{
	479	return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
	480	__result,
	481	__union_func< _IIter, _OutputIterator,
	482	_Compare>(__comp));
	483	}
e683ee2a	484
77d16198 PC	485	template<typename _IIter,
	486	typename _OutputIterator,
	487	typename _Compare>
	488	inline _OutputIterator
	489	__parallel_set_intersection(_IIter __begin1, _IIter __end1,
	490	_IIter __begin2, _IIter __end2,
	491	_OutputIterator __result, _Compare __comp)
	492	{
	493	return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
	494	__result,
	495	__intersection_func<_IIter,
	496	_OutputIterator, _Compare>(__comp));
	497	}
e683ee2a	498
77d16198 PC	499	template<typename _IIter,
	500	typename _OutputIterator,
	501	typename _Compare>
	502	inline _OutputIterator
	503	__parallel_set_difference(_IIter __begin1, _IIter __end1,
15ac3c72	504	_IIter __begin2, _IIter __end2,
77d16198 PC	505	_OutputIterator __result, _Compare __comp)
	506	{
	507	return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
	508	__result,
	509	__difference_func<_IIter,
	510	_OutputIterator, _Compare>(__comp));
	511	}
c2ba9709	512
77d16198 PC	513	template<typename _IIter,
	514	typename _OutputIterator,
	515	typename _Compare>
	516	inline _OutputIterator
	517	__parallel_set_symmetric_difference(_IIter __begin1, _IIter __end1,
	518	_IIter __begin2, _IIter __end2,
	519	_OutputIterator __result,
	520	_Compare __comp)
	521	{
	522	return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
	523	__result,
	524	__symmetric_difference_func<_IIter,
	525	_OutputIterator, _Compare>(__comp));
	526	}
c2ba9709 JS	527	}
c2ba9709 JS	528
cbcd1e45	529	#endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */