34 #ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H
35 #define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1
42 namespace __gnu_parallel
44 template<
typename _IIter,
typename _OutputIterator>
53 *__r++ = *__b.
first++;
65 template<
typename _IIter,
66 typename _OutputIterator,
68 struct __symmetric_difference_func
70 typedef std::iterator_traits<_IIter> _TraitsType;
71 typedef typename _TraitsType::difference_type _DifferenceType;
74 __symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {}
79 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
80 _OutputIterator __r)
const
82 while (__a != __b && __c != __d)
84 if (_M_comp(*__a, *__c))
90 else if (_M_comp(*__c, *__a))
102 return std::copy(__c, __d, std::copy(__a, __b, __r));
106 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d)
const
108 _DifferenceType __counter = 0;
110 while (__a != __b && __c != __d)
112 if (_M_comp(*__a, *__c))
117 else if (_M_comp(*__c, *__a))
129 return __counter + (__b - __a) + (__d - __c);
133 __first_empty(_IIter __c, _IIter __d, _OutputIterator __out)
const
134 {
return std::copy(__c, __d, __out); }
137 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out)
const
138 {
return std::copy(__a, __b, __out); }
142 template<
typename _IIter,
143 typename _OutputIterator,
145 struct __difference_func
147 typedef std::iterator_traits<_IIter> _TraitsType;
148 typedef typename _TraitsType::difference_type _DifferenceType;
151 __difference_func(_Compare __comp) : _M_comp(__comp) {}
156 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
157 _OutputIterator __r)
const
159 while (__a != __b && __c != __d)
161 if (_M_comp(*__a, *__c))
167 else if (_M_comp(*__c, *__a))
175 return std::copy(__a, __b, __r);
179 __count(_IIter __a, _IIter __b,
180 _IIter __c, _IIter __d)
const
182 _DifferenceType __counter = 0;
184 while (__a != __b && __c != __d)
186 if (_M_comp(*__a, *__c))
191 else if (_M_comp(*__c, *__a))
197 return __counter + (__b - __a);
201 __first_empty(_IIter, _IIter, _OutputIterator __out)
const
205 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out)
const
206 {
return std::copy(__a, __b, __out); }
210 template<
typename _IIter,
211 typename _OutputIterator,
213 struct __intersection_func
215 typedef std::iterator_traits<_IIter> _TraitsType;
216 typedef typename _TraitsType::difference_type _DifferenceType;
219 __intersection_func(_Compare __comp) : _M_comp(__comp) {}
224 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
225 _OutputIterator __r)
const
227 while (__a != __b && __c != __d)
229 if (_M_comp(*__a, *__c))
231 else if (_M_comp(*__c, *__a))
246 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d)
const
248 _DifferenceType __counter = 0;
250 while (__a != __b && __c != __d)
252 if (_M_comp(*__a, *__c))
254 else if (_M_comp(*__c, *__a))
268 __first_empty(_IIter, _IIter, _OutputIterator __out)
const
272 __second_empty(_IIter, _IIter, _OutputIterator __out)
const
276 template<
class _IIter,
class _OutputIterator,
class _Compare>
279 typedef typename std::iterator_traits<_IIter>::difference_type
282 __union_func(_Compare __comp) : _M_comp(__comp) {}
287 _M_invoke(_IIter __a,
const _IIter __b, _IIter __c,
288 const _IIter __d, _OutputIterator __r)
const
290 while (__a != __b && __c != __d)
292 if (_M_comp(*__a, *__c))
297 else if (_M_comp(*__c, *__a))
310 return std::copy(__c, __d, std::copy(__a, __b, __r));
314 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d)
const
316 _DifferenceType __counter = 0;
318 while (__a != __b && __c != __d)
320 if (_M_comp(*__a, *__c))
322 else if (_M_comp(*__c, *__a))
332 __counter += (__b - __a);
333 __counter += (__d - __c);
338 __first_empty(_IIter __c, _IIter __d, _OutputIterator __out)
const
339 {
return std::copy(__c, __d, __out); }
342 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out)
const
343 {
return std::copy(__a, __b, __out); }
346 template<
typename _IIter,
347 typename _OutputIterator,
350 __parallel_set_operation(_IIter __begin1, _IIter __end1,
351 _IIter __begin2, _IIter __end2,
352 _OutputIterator __result, _Operation __op)
356 typedef std::iterator_traits<_IIter> _TraitsType;
357 typedef typename _TraitsType::difference_type _DifferenceType;
358 typedef typename std::pair<_IIter, _IIter> _IteratorPair;
360 if (__begin1 == __end1)
361 return __op.__first_empty(__begin2, __end2, __result);
363 if (__begin2 == __end2)
364 return __op.__second_empty(__begin1, __end1, __result);
366 const _DifferenceType __size = (__end1 - __begin1) + (__end2 - __begin2);
368 const _IteratorPair __sequence[2] = {
std::make_pair(__begin1, __end1),
370 _OutputIterator __return_value = __result;
371 _DifferenceType *__borders;
372 _IteratorPair *__block_begins;
373 _DifferenceType* __lengths;
376 std::min<_DifferenceType>(__get_max_threads(),
377 std::min(__end1 - __begin1, __end2 - __begin2));
379 # pragma omp parallel num_threads(__num_threads)
383 __num_threads = omp_get_num_threads();
385 __borders =
new _DifferenceType[__num_threads + 2];
387 __block_begins =
new _IteratorPair[__num_threads + 1];
390 __lengths =
new _DifferenceType[__num_threads];
397 const _DifferenceType __rank = __borders[__iam + 1];
400 __rank, __offset, __op._M_comp);
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)))
414 _IteratorPair __block_end = __block_begins[__iam + 1] =
415 _IteratorPair(__offset[0], __offset[1]);
420 _IteratorPair __block_begin = __block_begins[__iam];
428 __op._M_invoke(__block_begin.first, __block_end.first,
429 __block_begin.second, __block_end.second,
430 __result) - __result;
435 __op.__count(__block_begin.first, __block_end.first,
436 __block_begin.second, __block_end.second);
442 _OutputIterator __r = __result;
448 __r += __lengths[__i];
450 __block_begin = __block_begins[__num_threads];
454 __op._M_invoke(__block_begin.first, __end1,
455 __block_begin.second, __end2, __r);
461 __r += __lengths[ __i ];
464 __op._M_invoke(__block_begin.first, __block_end.first,
465 __block_begin.second, __block_end.second, __r);
468 return __return_value;
471 template<
typename _IIter,
472 typename _OutputIterator,
474 inline _OutputIterator
475 __parallel_set_union(_IIter __begin1, _IIter __end1,
476 _IIter __begin2, _IIter __end2,
477 _OutputIterator __result, _Compare __comp)
479 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
481 __union_func< _IIter, _OutputIterator,
485 template<
typename _IIter,
486 typename _OutputIterator,
488 inline _OutputIterator
489 __parallel_set_intersection(_IIter __begin1, _IIter __end1,
490 _IIter __begin2, _IIter __end2,
491 _OutputIterator __result, _Compare __comp)
493 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
495 __intersection_func<_IIter,
496 _OutputIterator, _Compare>(__comp));
499 template<
typename _IIter,
500 typename _OutputIterator,
502 inline _OutputIterator
503 __parallel_set_difference(_IIter __begin1, _IIter __end1,
504 _IIter __begin2, _IIter __end2,
505 _OutputIterator __result, _Compare __comp)
507 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
509 __difference_func<_IIter,
510 _OutputIterator, _Compare>(__comp));
513 template<
typename _IIter,
514 typename _OutputIterator,
516 inline _OutputIterator
517 __parallel_set_symmetric_difference(_IIter __begin1, _IIter __end1,
518 _IIter __begin2, _IIter __end2,
519 _OutputIterator __result,
522 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
524 __symmetric_difference_func<_IIter,
525 _OutputIterator, _Compare>(__comp));
_T1 first
second_type is the second bound type
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
Functions to find elements of a certain global __rank in multiple sorted sequences. Also serves for splitting such sequence sets.
Struct holding two objects of arbitrary type.
Runtime settings and tuning parameters, heuristics to decide whether to use parallelized algorithms...
void multiseq_partition(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankIterator __begin_offsets, _Compare __comp=std::less< typename std::iterator_traits< typename std::iterator_traits< _RanSeqs >::value_type::first_type >::value_type >())
Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each s...
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
uint16_t _ThreadIndex
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
_T2 second
first is a copy of the first object
_OutputIterator __equally_split(_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s)
function to split a sequence into parts of almost equal size.