libstdc++
parallel/numeric
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/numeric
27 *
28  * @brief Parallel STL function calls corresponding to stl_numeric.h.
29  * The functions defined here mainly do case switches and
30  * call the actual parallelized versions in other files.
31  * Inlining policy: Functions that basically only contain one function call,
32  * are declared inline.
33  * This file is a GNU parallel extension to the Standard C++ Library.
34  */
35 
36 // Written by Johannes Singler and Felix Putze.
37 
38 #ifndef _GLIBCXX_PARALLEL_NUMERIC_H
39 #define _GLIBCXX_PARALLEL_NUMERIC_H 1
40 
41 #include <numeric>
42 #include <bits/stl_function.h>
43 #include <parallel/numericfwd.h>
44 #include <parallel/iterator.h>
45 #include <parallel/for_each.h>
46 #include <parallel/for_each_selectors.h>
47 #include <parallel/partial_sum.h>
48 
49 namespace std _GLIBCXX_VISIBILITY(default)
50 {
51 namespace __parallel
52 {
53  // Sequential fallback.
54  template<typename _IIter, typename _Tp>
55  inline _Tp
56  accumulate(_IIter __begin, _IIter __end, _Tp __init,
57  __gnu_parallel::sequential_tag)
58  { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init); }
59 
60  template<typename _IIter, typename _Tp, typename _BinaryOperation>
61  inline _Tp
62  accumulate(_IIter __begin, _IIter __end, _Tp __init,
63  _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
64  { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init, __binary_op); }
65 
66  // Sequential fallback for input iterator case.
67  template<typename _IIter, typename _Tp, typename _IteratorTag>
68  inline _Tp
69  __accumulate_switch(_IIter __begin, _IIter __end,
70  _Tp __init, _IteratorTag)
71  { return accumulate(__begin, __end, __init,
72  __gnu_parallel::sequential_tag()); }
73 
74  template<typename _IIter, typename _Tp, typename _BinaryOperation,
75  typename _IteratorTag>
76  inline _Tp
77  __accumulate_switch(_IIter __begin, _IIter __end, _Tp __init,
78  _BinaryOperation __binary_op, _IteratorTag)
79  { return accumulate(__begin, __end, __init, __binary_op,
80  __gnu_parallel::sequential_tag()); }
81 
82  // Parallel algorithm for random access iterators.
83  template<typename __RAIter, typename _Tp, typename _BinaryOperation>
84  _Tp
85  __accumulate_switch(__RAIter __begin, __RAIter __end,
86  _Tp __init, _BinaryOperation __binary_op,
87  random_access_iterator_tag,
88  __gnu_parallel::_Parallelism __parallelism_tag)
89  {
90  if (_GLIBCXX_PARALLEL_CONDITION(
91  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
92  >= __gnu_parallel::_Settings::get().accumulate_minimal_n
93  && __gnu_parallel::__is_parallel(__parallelism_tag)))
94  {
95  _Tp __res = __init;
96  __gnu_parallel::__accumulate_selector<__RAIter>
97  __my_selector;
98  __gnu_parallel::
99  __for_each_template_random_access_ed(__begin, __end,
100  __gnu_parallel::_Nothing(),
101  __my_selector,
102  __gnu_parallel::
103  __accumulate_binop_reduct
104  <_BinaryOperation>(__binary_op),
105  __res, __res, -1);
106  return __res;
107  }
108  else
109  return accumulate(__begin, __end, __init, __binary_op,
110  __gnu_parallel::sequential_tag());
111  }
112 
113  // Public interface.
114  template<typename _IIter, typename _Tp>
115  inline _Tp
116  accumulate(_IIter __begin, _IIter __end, _Tp __init,
117  __gnu_parallel::_Parallelism __parallelism_tag)
118  {
119  typedef std::iterator_traits<_IIter> _IteratorTraits;
120  typedef typename _IteratorTraits::value_type _ValueType;
121  typedef typename _IteratorTraits::iterator_category _IteratorCategory;
122 
123  return __accumulate_switch(__begin, __end, __init,
124  __gnu_parallel::_Plus<_Tp, _ValueType>(),
125  _IteratorCategory(), __parallelism_tag);
126  }
127 
128  template<typename _IIter, typename _Tp>
129  inline _Tp
130  accumulate(_IIter __begin, _IIter __end, _Tp __init)
131  {
132  typedef std::iterator_traits<_IIter> _IteratorTraits;
133  typedef typename _IteratorTraits::value_type _ValueType;
134  typedef typename _IteratorTraits::iterator_category _IteratorCategory;
135 
136  return __accumulate_switch(__begin, __end, __init,
137  __gnu_parallel::_Plus<_Tp, _ValueType>(),
138  _IteratorCategory());
139  }
140 
141  template<typename _IIter, typename _Tp, typename _BinaryOperation>
142  inline _Tp
143  accumulate(_IIter __begin, _IIter __end, _Tp __init,
144  _BinaryOperation __binary_op,
145  __gnu_parallel::_Parallelism __parallelism_tag)
146  {
147  typedef iterator_traits<_IIter> _IteratorTraits;
148  typedef typename _IteratorTraits::iterator_category _IteratorCategory;
149  return __accumulate_switch(__begin, __end, __init, __binary_op,
150  _IteratorCategory(), __parallelism_tag);
151  }
152 
153  template<typename _IIter, typename _Tp, typename _BinaryOperation>
154  inline _Tp
155  accumulate(_IIter __begin, _IIter __end, _Tp __init,
156  _BinaryOperation __binary_op)
157  {
158  typedef iterator_traits<_IIter> _IteratorTraits;
159  typedef typename _IteratorTraits::iterator_category _IteratorCategory;
160  return __accumulate_switch(__begin, __end, __init, __binary_op,
161  _IteratorCategory());
162  }
163 
164 
165  // Sequential fallback.
166  template<typename _IIter1, typename _IIter2, typename _Tp>
167  inline _Tp
168  inner_product(_IIter1 __first1, _IIter1 __last1,
169  _IIter2 __first2, _Tp __init,
170  __gnu_parallel::sequential_tag)
171  { return _GLIBCXX_STD_A::inner_product(
172  __first1, __last1, __first2, __init); }
173 
174  template<typename _IIter1, typename _IIter2, typename _Tp,
175  typename _BinaryFunction1, typename _BinaryFunction2>
176  inline _Tp
177  inner_product(_IIter1 __first1, _IIter1 __last1,
178  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
179  _BinaryFunction2 __binary_op2,
180  __gnu_parallel::sequential_tag)
181  { return _GLIBCXX_STD_A::inner_product(__first1, __last1, __first2, __init,
182  __binary_op1, __binary_op2); }
183 
184  // Parallel algorithm for random access iterators.
185  template<typename _RAIter1, typename _RAIter2,
186  typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>
187  _Tp
188  __inner_product_switch(_RAIter1 __first1,
189  _RAIter1 __last1,
190  _RAIter2 __first2, _Tp __init,
191  _BinaryFunction1 __binary_op1,
192  _BinaryFunction2 __binary_op2,
193  random_access_iterator_tag,
194  random_access_iterator_tag,
195  __gnu_parallel::_Parallelism __parallelism_tag)
196  {
197  if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)
198  >= __gnu_parallel::_Settings::get().
199  accumulate_minimal_n
200  && __gnu_parallel::
201  __is_parallel(__parallelism_tag)))
202  {
203  _Tp __res = __init;
204  __gnu_parallel::
205  __inner_product_selector<_RAIter1,
206  _RAIter2, _Tp> __my_selector(__first1, __first2);
207  __gnu_parallel::
208  __for_each_template_random_access_ed(
209  __first1, __last1, __binary_op2, __my_selector, __binary_op1,
210  __res, __res, -1);
211  return __res;
212  }
213  else
214  return inner_product(__first1, __last1, __first2, __init,
215  __gnu_parallel::sequential_tag());
216  }
217 
218  // No parallelism for input iterators.
219  template<typename _IIter1, typename _IIter2, typename _Tp,
220  typename _BinaryFunction1, typename _BinaryFunction2,
221  typename _IteratorTag1, typename _IteratorTag2>
222  inline _Tp
223  __inner_product_switch(_IIter1 __first1, _IIter1 __last1,
224  _IIter2 __first2, _Tp __init,
225  _BinaryFunction1 __binary_op1,
226  _BinaryFunction2 __binary_op2,
227  _IteratorTag1, _IteratorTag2)
228  { return inner_product(__first1, __last1, __first2, __init, __binary_op1,
229  __binary_op2, __gnu_parallel::sequential_tag()); }
230 
231  template<typename _IIter1, typename _IIter2, typename _Tp,
232  typename _BinaryFunction1, typename _BinaryFunction2>
233  inline _Tp
234  inner_product(_IIter1 __first1, _IIter1 __last1,
235  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
236  _BinaryFunction2 __binary_op2,
237  __gnu_parallel::_Parallelism __parallelism_tag)
238  {
239  typedef iterator_traits<_IIter1> _TraitsType1;
240  typedef typename _TraitsType1::iterator_category _IteratorCategory1;
241 
242  typedef iterator_traits<_IIter2> _TraitsType2;
243  typedef typename _TraitsType2::iterator_category _IteratorCategory2;
244 
245  return __inner_product_switch(__first1, __last1, __first2, __init,
246  __binary_op1, __binary_op2,
247  _IteratorCategory1(), _IteratorCategory2(),
248  __parallelism_tag);
249  }
250 
251  template<typename _IIter1, typename _IIter2, typename _Tp,
252  typename _BinaryFunction1, typename _BinaryFunction2>
253  inline _Tp
254  inner_product(_IIter1 __first1, _IIter1 __last1,
255  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
256  _BinaryFunction2 __binary_op2)
257  {
258  typedef iterator_traits<_IIter1> _TraitsType1;
259  typedef typename _TraitsType1::iterator_category _IteratorCategory1;
260 
261  typedef iterator_traits<_IIter2> _TraitsType2;
262  typedef typename _TraitsType2::iterator_category _IteratorCategory2;
263 
264  return __inner_product_switch(__first1, __last1, __first2, __init,
265  __binary_op1, __binary_op2,
266  _IteratorCategory1(),
267  _IteratorCategory2());
268  }
269 
270  template<typename _IIter1, typename _IIter2, typename _Tp>
271  inline _Tp
272  inner_product(_IIter1 __first1, _IIter1 __last1,
273  _IIter2 __first2, _Tp __init,
274  __gnu_parallel::_Parallelism __parallelism_tag)
275  {
276  typedef iterator_traits<_IIter1> _TraitsType1;
277  typedef typename _TraitsType1::value_type _ValueType1;
278  typedef iterator_traits<_IIter2> _TraitsType2;
279  typedef typename _TraitsType2::value_type _ValueType2;
280 
281  typedef typename
282  __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
283  _MultipliesResultType;
284  return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
285  __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
286  __gnu_parallel::
287  _Multiplies<_ValueType1, _ValueType2>(),
288  __parallelism_tag);
289  }
290 
291  template<typename _IIter1, typename _IIter2, typename _Tp>
292  inline _Tp
293  inner_product(_IIter1 __first1, _IIter1 __last1,
294  _IIter2 __first2, _Tp __init)
295  {
296  typedef iterator_traits<_IIter1> _TraitsType1;
297  typedef typename _TraitsType1::value_type _ValueType1;
298  typedef iterator_traits<_IIter2> _TraitsType2;
299  typedef typename _TraitsType2::value_type _ValueType2;
300 
301  typedef typename
302  __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
303  _MultipliesResultType;
304  return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
305  __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
306  __gnu_parallel::
307  _Multiplies<_ValueType1, _ValueType2>());
308  }
309 
310  // Sequential fallback.
311  template<typename _IIter, typename _OutputIterator>
312  inline _OutputIterator
313  partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
314  __gnu_parallel::sequential_tag)
315  { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); }
316 
317  // Sequential fallback.
318  template<typename _IIter, typename _OutputIterator,
319  typename _BinaryOperation>
320  inline _OutputIterator
321  partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
322  _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
323  { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
324 
325  // Sequential fallback for input iterator case.
326  template<typename _IIter, typename _OutputIterator,
327  typename _BinaryOperation, typename _IteratorTag1,
328  typename _IteratorTag2>
329  inline _OutputIterator
330  __partial_sum_switch(_IIter __begin, _IIter __end,
331  _OutputIterator __result, _BinaryOperation __bin_op,
332  _IteratorTag1, _IteratorTag2)
333  { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
334 
335  // Parallel algorithm for random access iterators.
336  template<typename _IIter, typename _OutputIterator,
337  typename _BinaryOperation>
338  _OutputIterator
339  __partial_sum_switch(_IIter __begin, _IIter __end,
340  _OutputIterator __result, _BinaryOperation __bin_op,
341  random_access_iterator_tag,
342  random_access_iterator_tag)
343  {
344  if (_GLIBCXX_PARALLEL_CONDITION(
345  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
346  >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
347  return __gnu_parallel::__parallel_partial_sum(__begin, __end,
348  __result, __bin_op);
349  else
350  return partial_sum(__begin, __end, __result, __bin_op,
351  __gnu_parallel::sequential_tag());
352  }
353 
354  // Public interface.
355  template<typename _IIter, typename _OutputIterator>
356  inline _OutputIterator
357  partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result)
358  {
359  typedef typename iterator_traits<_IIter>::value_type _ValueType;
360  return __gnu_parallel::partial_sum(__begin, __end,
361  __result, std::plus<_ValueType>());
362  }
363 
364  // Public interface
365  template<typename _IIter, typename _OutputIterator,
366  typename _BinaryOperation>
367  inline _OutputIterator
368  partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
369  _BinaryOperation __binary_op)
370  {
371  typedef iterator_traits<_IIter> _ITraitsType;
372  typedef typename _ITraitsType::iterator_category _IIteratorCategory;
373 
374  typedef iterator_traits<_OutputIterator> _OTraitsType;
375  typedef typename _OTraitsType::iterator_category _OIterCategory;
376 
377  return __partial_sum_switch(__begin, __end, __result, __binary_op,
378  _IIteratorCategory(), _OIterCategory());
379  }
380 
381  // Sequential fallback.
382  template<typename _IIter, typename _OutputIterator>
383  inline _OutputIterator
384  adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
385  __gnu_parallel::sequential_tag)
386  { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); }
387 
388  // Sequential fallback.
389  template<typename _IIter, typename _OutputIterator,
390  typename _BinaryOperation>
391  inline _OutputIterator
392  adjacent_difference(_IIter __begin, _IIter __end,
393  _OutputIterator __result, _BinaryOperation __bin_op,
394  __gnu_parallel::sequential_tag)
395  { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end,
396  __result, __bin_op); }
397 
398  // Sequential fallback for input iterator case.
399  template<typename _IIter, typename _OutputIterator,
400  typename _BinaryOperation, typename _IteratorTag1,
401  typename _IteratorTag2>
402  inline _OutputIterator
403  __adjacent_difference_switch(_IIter __begin, _IIter __end,
404  _OutputIterator __result,
405  _BinaryOperation __bin_op, _IteratorTag1,
406  _IteratorTag2)
407  { return adjacent_difference(__begin, __end, __result, __bin_op,
408  __gnu_parallel::sequential_tag()); }
409 
410  // Parallel algorithm for random access iterators.
411  template<typename _IIter, typename _OutputIterator,
412  typename _BinaryOperation>
413  _OutputIterator
414  __adjacent_difference_switch(_IIter __begin, _IIter __end,
415  _OutputIterator __result,
416  _BinaryOperation __bin_op,
417  random_access_iterator_tag,
418  random_access_iterator_tag,
419  __gnu_parallel::_Parallelism
420  __parallelism_tag)
421  {
422  if (_GLIBCXX_PARALLEL_CONDITION(
423  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
424  >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
425  && __gnu_parallel::__is_parallel(__parallelism_tag)))
426  {
427  bool __dummy = true;
428  typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,
429  random_access_iterator_tag> _ItTrip;
430  *__result = *__begin;
431  _ItTrip __begin_pair(__begin + 1, __result + 1),
432  __end_pair(__end, __result + (__end - __begin));
433  __gnu_parallel::__adjacent_difference_selector<_ItTrip>
434  __functionality;
435  __gnu_parallel::
436  __for_each_template_random_access_ed(
437  __begin_pair, __end_pair, __bin_op, __functionality,
438  __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);
439  return __functionality._M_finish_iterator;
440  }
441  else
442  return adjacent_difference(__begin, __end, __result, __bin_op,
443  __gnu_parallel::sequential_tag());
444  }
445 
446  // Public interface.
447  template<typename _IIter, typename _OutputIterator>
448  inline _OutputIterator
449  adjacent_difference(_IIter __begin, _IIter __end,
450  _OutputIterator __result,
451  __gnu_parallel::_Parallelism __parallelism_tag)
452  {
453  typedef iterator_traits<_IIter> _TraitsType;
454  typedef typename _TraitsType::value_type _ValueType;
455  return adjacent_difference(__begin, __end, __result,
456  std::minus<_ValueType>(),
457  __parallelism_tag);
458  }
459 
460  template<typename _IIter, typename _OutputIterator>
461  inline _OutputIterator
462  adjacent_difference(_IIter __begin, _IIter __end,
463  _OutputIterator __result)
464  {
465  typedef iterator_traits<_IIter> _TraitsType;
466  typedef typename _TraitsType::value_type _ValueType;
467  return adjacent_difference(__begin, __end, __result,
468  std::minus<_ValueType>());
469  }
470 
471  template<typename _IIter, typename _OutputIterator,
472  typename _BinaryOperation>
473  inline _OutputIterator
474  adjacent_difference(_IIter __begin, _IIter __end,
475  _OutputIterator __result, _BinaryOperation __binary_op,
476  __gnu_parallel::_Parallelism __parallelism_tag)
477  {
478  typedef iterator_traits<_IIter> _ITraitsType;
479  typedef typename _ITraitsType::iterator_category _IIteratorCategory;
480 
481  typedef iterator_traits<_OutputIterator> _OTraitsType;
482  typedef typename _OTraitsType::iterator_category _OIterCategory;
483 
484  return __adjacent_difference_switch(__begin, __end, __result,
485  __binary_op,
486  _IIteratorCategory(),
487  _OIterCategory(),
488  __parallelism_tag);
489  }
490 
491  template<typename _IIter, typename _OutputIterator,
492  typename _BinaryOperation>
493  inline _OutputIterator
494  adjacent_difference(_IIter __begin, _IIter __end,
495  _OutputIterator __result, _BinaryOperation __binary_op)
496  {
497  typedef iterator_traits<_IIter> _ITraitsType;
498  typedef typename _ITraitsType::iterator_category _IIteratorCategory;
499 
500  typedef iterator_traits<_OutputIterator> _OTraitsType;
501  typedef typename _OTraitsType::iterator_category _OIterCategory;
502 
503  return __adjacent_difference_switch(__begin, __end, __result,
504  __binary_op,
505  _IIteratorCategory(),
506  _OIterCategory());
507  }
508 } // end namespace
509 } // end namespace
510 
511 #endif /* _GLIBCXX_NUMERIC_H */