1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2016 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