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>
40 #include <parallel/multiseq_selection.h>
41 
42 namespace __gnu_parallel
43 {
44   template<typename _IIter, typename _OutputIterator>
45     _OutputIterator
__copy_tail(std::pair<_IIter,_IIter> __b,std::pair<_IIter,_IIter> __e,_OutputIterator __r)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 
__symmetric_difference_func__symmetric_difference_func74       __symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {}
75 
76       _Compare _M_comp;
77 
78       _OutputIterator
_M_invoke__symmetric_difference_func79       _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
__count__symmetric_difference_func106       __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
__first_empty__symmetric_difference_func133       __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
134       { return std::copy(__c, __d, __out); }
135 
136       _OutputIterator
__second_empty__symmetric_difference_func137       __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 
__difference_func__difference_func151       __difference_func(_Compare __comp) : _M_comp(__comp) {}
152 
153       _Compare _M_comp;
154 
155       _OutputIterator
_M_invoke__difference_func156       _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
__count__difference_func179       __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
__first_empty__difference_func201       __first_empty(_IIter, _IIter, _OutputIterator __out) const
202       { return __out; }
203 
204       _OutputIterator
__second_empty__difference_func205       __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 
__intersection_func__intersection_func219       __intersection_func(_Compare __comp) : _M_comp(__comp) {}
220 
221       _Compare _M_comp;
222 
223       _OutputIterator
_M_invoke__intersection_func224       _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
__count__intersection_func246       __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
__first_empty__intersection_func268       __first_empty(_IIter, _IIter, _OutputIterator __out) const
269       { return __out; }
270 
271       _OutputIterator
__second_empty__intersection_func272       __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 
__union_func__union_func282       __union_func(_Compare __comp) : _M_comp(__comp) {}
283 
284       _Compare _M_comp;
285 
286       _OutputIterator
_M_invoke__union_func287       _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
__count__union_func314       __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
__first_empty__union_func338       __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
339       { return std::copy(__c, __d, __out); }
340 
341       _OutputIterator
__second_empty__union_func342       __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
__parallel_set_operation(_IIter __begin1,_IIter __end1,_IIter __begin2,_IIter __end2,_OutputIterator __result,_Operation __op)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
__parallel_set_union(_IIter __begin1,_IIter __end1,_IIter __begin2,_IIter __end2,_OutputIterator __result,_Compare __comp)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
__parallel_set_intersection(_IIter __begin1,_IIter __end1,_IIter __begin2,_IIter __end2,_OutputIterator __result,_Compare __comp)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
__parallel_set_difference(_IIter __begin1,_IIter __end1,_IIter __begin2,_IIter __end2,_OutputIterator __result,_Compare __comp)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
__parallel_set_symmetric_difference(_IIter __begin1,_IIter __end1,_IIter __begin2,_IIter __end2,_OutputIterator __result,_Compare __comp)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 */
530