libstdc++
set_operations.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2022 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>
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  {
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 */
_T2 second
The second member.
Definition: stl_pair.h:192
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...
Functions to find elements of a certain global __rank in multiple sorted sequences. Also serves for splitting such sequence sets.
_T1 first
The first member.
Definition: stl_pair.h:191
_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
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
uint16_t _ThreadIndex
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
Definition: types.h:123
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:230
Runtime settings and tuning parameters, heuristics to decide whether to use parallelized algorithms...
Struct holding two objects of arbitrary type.
GNU parallel code for public use.
Traits class for iterators.