1// -*- C++ -*-
2
3// Copyright (C) 2007-2014 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
42namespace __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 */
530