34 #ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H
35 #define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1
44 template<
typename InputIterator,
typename OutputIterator>
65 template<
typename InputIterator,
66 typename OutputIterator,
68 struct symmetric_difference_func
71 typedef typename traits_type::difference_type difference_type;
74 symmetric_difference_func(Comparator c) : comp(c) {}
79 invoke(InputIterator a, InputIterator b,
80 InputIterator c, InputIterator d,
81 OutputIterator r)
const
83 while (a != b && c != d)
91 else if (comp(*c, *a))
103 return std::copy(c, d, std::copy(a, b, r));
107 count(InputIterator a, InputIterator b,
108 InputIterator c, InputIterator d)
const
110 difference_type counter = 0;
112 while (a != b && c != d)
119 else if (comp(*c, *a))
131 return counter + (b - a) + (d - c);
135 first_empty(InputIterator c, InputIterator d, OutputIterator out)
const
136 {
return std::copy(c, d, out); }
139 second_empty(InputIterator a, InputIterator b, OutputIterator out)
const
140 {
return std::copy(a, b, out); }
144 template<
typename InputIterator,
145 typename OutputIterator,
147 struct difference_func
150 typedef typename traits_type::difference_type difference_type;
153 difference_func(Comparator c) : comp(c) {}
158 invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
159 OutputIterator r)
const
161 while (a != b && c != d)
169 else if (comp(*c, *a))
177 return std::copy(a, b, r);
181 count(InputIterator a, InputIterator b,
182 InputIterator c, InputIterator d)
const
184 difference_type counter = 0;
186 while (a != b && c != d)
193 else if (comp(*c, *a))
199 return counter + (b - a);
202 inline OutputIterator
203 first_empty(InputIterator c, InputIterator d, OutputIterator out)
const
206 inline OutputIterator
207 second_empty(InputIterator a, InputIterator b, OutputIterator out)
const
208 {
return std::copy(a, b, out); }
212 template<
typename InputIterator,
213 typename OutputIterator,
215 struct intersection_func
218 typedef typename traits_type::difference_type difference_type;
221 intersection_func(Comparator c) : comp(c) {}
226 invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
227 OutputIterator r)
const
229 while (a != b && c != d)
233 else if (comp(*c, *a))
248 count(InputIterator a, InputIterator b,
249 InputIterator c, InputIterator d)
const
251 difference_type counter = 0;
253 while (a != b && c != d)
257 else if (comp(*c, *a))
270 inline OutputIterator
271 first_empty(InputIterator c, InputIterator d, OutputIterator out)
const
274 inline OutputIterator
275 second_empty(InputIterator a, InputIterator b, OutputIterator out)
const
279 template<
class InputIterator,
class OutputIterator,
class Comparator>
282 typedef typename std::iterator_traits<InputIterator>::difference_type
285 union_func(Comparator c) : comp(c) {}
290 invoke(InputIterator a,
const InputIterator b, InputIterator c,
291 const InputIterator d, OutputIterator r)
const
293 while (a != b && c != d)
300 else if (comp(*c, *a))
313 return std::copy(c, d, std::copy(a, b, r));
317 count(InputIterator a, InputIterator b,
318 InputIterator c, InputIterator d)
const
320 difference_type counter = 0;
322 while (a != b && c != d)
326 else if (comp(*c, *a))
341 inline OutputIterator
342 first_empty(InputIterator c, InputIterator d, OutputIterator out)
const
343 {
return std::copy(c, d, out); }
345 inline OutputIterator
346 second_empty(InputIterator a, InputIterator b, OutputIterator out)
const
347 {
return std::copy(a, b, out); }
350 template<
typename InputIterator,
351 typename OutputIterator,
354 parallel_set_operation(InputIterator begin1, InputIterator end1,
355 InputIterator begin2, InputIterator end2,
356 OutputIterator result, Operation op)
360 typedef
std::iterator_traits<InputIterator> traits_type;
361 typedef typename traits_type::difference_type difference_type;
362 typedef typename
std::pair<InputIterator, InputIterator> iterator_pair;
365 return op.first_empty(begin2, end2, result);
368 return op.second_empty(begin1, end1, result);
370 const difference_type size = (end1 - begin1) + (end2 - begin2);
372 const iterator_pair sequence[ 2 ] =
373 { std::make_pair(begin1, end1), std::make_pair(begin2, end2) } ;
374 OutputIterator return_value = result;
375 difference_type *borders;
376 iterator_pair *block_begins;
377 difference_type* lengths;
380 std::min<difference_type>(get_max_threads(),
381 std::min(end1 - begin1, end2 - begin2));
383 # pragma omp parallel num_threads(num_threads)
387 num_threads = omp_get_num_threads();
389 borders =
new difference_type[num_threads + 2];
391 block_begins =
new iterator_pair[num_threads + 1];
393 block_begins[0] = std::make_pair(begin1, begin2);
394 lengths =
new difference_type[num_threads];
400 InputIterator offset[2];
401 const difference_type rank = borders[iam + 1];
408 if (offset[ 0 ] != begin1 && offset[ 1 ] != end2
409 && !op.comp(*(offset[ 0 ] - 1), *offset[ 1 ])
410 && !op.comp(*offset[ 1 ], *(offset[ 0 ] - 1)))
417 iterator_pair block_end = block_begins[ iam + 1 ] =
418 iterator_pair(offset[ 0 ], offset[ 1 ]);
423 iterator_pair block_begin = block_begins[ iam ];
430 lengths[ iam ] = op.invoke(block_begin.first, block_end.first,
431 block_begin.second, block_end.second,
437 lengths[ iam ] = op.count(block_begin.first, block_end.first,
438 block_begin.second, block_end.second);
444 OutputIterator r = result;
449 for (
int i = 0; i < num_threads; ++i)
452 block_begin = block_begins[num_threads];
455 return_value = op.invoke(
456 block_begin.first, end1, block_begin.second, end2, r);
461 for (
int i = 0; i < iam; ++i)
465 op.invoke(block_begin.first, block_end.first,
466 block_begin.second, block_end.second, r);
473 template<
typename InputIterator,
474 typename OutputIterator,
476 inline OutputIterator
477 parallel_set_union(InputIterator begin1, InputIterator end1,
478 InputIterator begin2, InputIterator end2,
479 OutputIterator result, Comparator comp)
481 return parallel_set_operation(begin1, end1, begin2, end2, result,
482 union_func< InputIterator, OutputIterator, Comparator>(comp));
485 template<
typename InputIterator,
486 typename OutputIterator,
488 inline OutputIterator
489 parallel_set_intersection(InputIterator begin1, InputIterator end1,
490 InputIterator begin2, InputIterator end2,
491 OutputIterator result, Comparator comp)
493 return parallel_set_operation(begin1, end1, begin2, end2, result,
494 intersection_func<InputIterator, OutputIterator, Comparator>(comp));
497 template<
typename InputIterator,
498 typename OutputIterator,
500 inline OutputIterator
501 parallel_set_difference(InputIterator begin1, InputIterator end1,
502 InputIterator begin2, InputIterator end2,
503 OutputIterator result, Comparator comp)
505 return parallel_set_operation(begin1, end1, begin2, end2, result,
506 difference_func<InputIterator, OutputIterator, Comparator>(comp));
509 template<
typename InputIterator,
510 typename OutputIterator,
512 inline OutputIterator
513 parallel_set_symmetric_difference(InputIterator begin1, InputIterator end1,
514 InputIterator begin2, InputIterator end2,
515 OutputIterator result, Comparator comp)
517 return parallel_set_operation(begin1, end1, begin2, end2, result,
518 symmetric_difference_func<InputIterator, OutputIterator, Comparator>
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.
void multiseq_partition(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, RankIterator begin_offsets, Comparator 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 seq...
Runtime settings and tuning parameters, heuristics to decide whether to use parallelized algorithms...
_T1 first
first is a copy of the first object
ISO C++ entities toplevel namespace is std.
GNU parallel code for public use.
_T2 second
second is a copy of the second object
pair holds two objects of arbitrary type.
Functions to find elements of a certain global rank in multiple sorted sequences. Also serves for spl...
uint16 thread_index_t
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
OutputIterator equally_split(difference_type n, thread_index_t num_threads, OutputIterator s)
Function to split a sequence into parts of almost equal size.