libstdc++
set_operations.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2020 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 /**
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 {
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
81  {
82  while (__a != __b && __c != __d)
83  {
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  }
101  }
102  return std::copy(__c, __d, std::copy(__a, __b, __r));
103  }
104 
105  _DifferenceType
106  __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
107  {
108  _DifferenceType __counter = 0;
109 
110  while (__a != __b && __c != __d)
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 
129  return __counter + (__b - __a) + (__d - __c);
130  }
131 
132  _OutputIterator
133  __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
134  { return std::copy(__c, __d, __out); }
135 
136  _OutputIterator
137  __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
138  { return std::copy(__a, __b, __out); }
139  };
140 
141 
142  template<typename _IIter,
143  typename _OutputIterator,
144  typename _Compare>
145  struct __difference_func
146  {
147  typedef std::iterator_traits<_IIter> _TraitsType;
148  typedef typename _TraitsType::difference_type _DifferenceType;
149  typedef typename std::pair<_IIter, _IIter> _IteratorPair;
150 
151  __difference_func(_Compare __comp) : _M_comp(__comp) {}
152 
153  _Compare _M_comp;
154 
155  _OutputIterator
156  _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
157  _OutputIterator __r) const
158  {
159  while (__a != __b && __c != __d)
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  }
177 
178  _DifferenceType
179  __count(_IIter __a, _IIter __b,
180  _IIter __c, _IIter __d) const
181  {
182  _DifferenceType __counter = 0;
183 
184  while (__a != __b && __c != __d)
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  }
196 
197  return __counter + (__b - __a);
198  }
199 
200  _OutputIterator
201  __first_empty(_IIter, _IIter, _OutputIterator __out) const
202  { return __out; }
203 
204  _OutputIterator
205  __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
206  { return std::copy(__a, __b, __out); }
207  };
208 
209 
210  template<typename _IIter,
211  typename _OutputIterator,
212  typename _Compare>
213  struct __intersection_func
214  {
215  typedef std::iterator_traits<_IIter> _TraitsType;
216  typedef typename _TraitsType::difference_type _DifferenceType;
217  typedef typename std::pair<_IIter, _IIter> _IteratorPair;
218 
219  __intersection_func(_Compare __comp) : _M_comp(__comp) {}
220 
221  _Compare _M_comp;
222 
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  }
241 
242  return __r;
243  }
244 
245  _DifferenceType
246  __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
247  {
248  _DifferenceType __counter = 0;
249 
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  }
263 
264  return __counter;
265  }
266 
267  _OutputIterator
268  __first_empty(_IIter, _IIter, _OutputIterator __out) const
269  { return __out; }
270 
271  _OutputIterator
272  __second_empty(_IIter, _IIter, _OutputIterator __out) const
273  { return __out; }
274  };
275 
276  template<class _IIter, class _OutputIterator, class _Compare>
277  struct __union_func
278  {
279  typedef typename std::iterator_traits<_IIter>::difference_type
280  _DifferenceType;
281 
282  __union_func(_Compare __comp) : _M_comp(__comp) {}
283 
284  _Compare _M_comp;
285 
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  }
312 
313  _DifferenceType
314  __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
315  {
316  _DifferenceType __counter = 0;
317 
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  }
331 
332  __counter += (__b - __a);
333  __counter += (__d - __c);
334  return __counter;
335  }
336 
337  _OutputIterator
338  __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
339  { return std::copy(__c, __d, __out); }
340 
341  _OutputIterator
342  __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
343  { return std::copy(__a, __b, __out); }
344  };
345 
346  template<typename _IIter,
347  typename _OutputIterator,
348  typename _Operation>
349  _OutputIterator
350  __parallel_set_operation(_IIter __begin1, _IIter __end1,
351  _IIter __begin2, _IIter __end2,
352  _OutputIterator __result, _Operation __op)
353  {
354  _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2))
355 
356  typedef std::iterator_traits<_IIter> _TraitsType;
357  typedef typename _TraitsType::difference_type _DifferenceType;
358  typedef typename std::pair<_IIter, _IIter> _IteratorPair;
359 
360  if (__begin1 == __end1)
361  return __op.__first_empty(__begin2, __end2, __result);
362 
363  if (__begin2 == __end2)
364  return __op.__second_empty(__begin1, __end1, __result);
365 
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)
380  {
381 # pragma omp single
382  {
383  __num_threads = omp_get_num_threads();
384 
385  __borders = new _DifferenceType[__num_threads + 2];
386  __equally_split(__size, __num_threads + 1, __borders);
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
419 
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.
440 # pragma omp barrier
441 
442  _OutputIterator __r = __result;
443 
444  if (__iam == 0)
445  {
446  // Do the last block.
447  for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
448  __r += __lengths[__i];
449 
450  __block_begin = __block_begins[__num_threads];
451 
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);
456 
457  }
458  else
459  {
460  for (_ThreadIndex __i = 0; __i < __iam; ++__i)
461  __r += __lengths[ __i ];
462 
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  }
470 
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  }
484 
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  }
498 
499  template<typename _IIter,
500  typename _OutputIterator,
501  typename _Compare>
502  inline _OutputIterator
503  __parallel_set_difference(_IIter __begin1, _IIter __end1,
504  _IIter __begin2, _IIter __end2,
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  }
512 
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  }
527 }
528 
529 #endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */
_GLIBCXX_CALL
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
Definition: compiletime_settings.h:44
multiseq_selection.h
Functions to find elements of a certain global __rank in multiple sorted sequences....
settings.h
Runtime settings and tuning parameters, heuristics to decide whether to use parallelized algorithms.
std::min
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:230
__gnu_parallel
GNU parallel code for public use.
Definition: balanced_quicksort.h:62
__gnu_parallel::_ThreadIndex
uint16_t _ThreadIndex
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
Definition: types.h:123
__gnu_parallel::__equally_split
_OutputIterator __equally_split(_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s)
function to split a sequence into parts of almost equal size.
Definition: equally_split.h:48
__gnu_parallel::multiseq_partition
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...
Definition: multiseq_selection.h:122
std::iterator_traits
Traits class for iterators.
Definition: stl_iterator_base_types.h:178
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
std::pair::first
_T1 first
The first member.
Definition: stl_pair.h:217
std::pair::second
_T2 second
The second member.
Definition: stl_pair.h:218