3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
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
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.
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.
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/>.
26 * @file parallel/numeric
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.
36 // Written by Johannes Singler and Felix Putze.
38 #ifndef _GLIBCXX_PARALLEL_NUMERIC_H
39 #define _GLIBCXX_PARALLEL_NUMERIC_H 1
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>
53 // Sequential fallback.
54 template<typename _IIter, typename _Tp>
56 accumulate(_IIter __begin, _IIter __end, _Tp __init,
57 __gnu_parallel::sequential_tag)
58 { return _GLIBCXX_STD_P::accumulate(__begin, __end, __init); }
60 template<typename _IIter, typename _Tp, typename _BinaryOperation>
62 accumulate(_IIter __begin, _IIter __end, _Tp __init,
63 _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
64 { return _GLIBCXX_STD_P::accumulate(__begin, __end, __init, __binary_op); }
66 // Sequential fallback for input iterator case.
67 template<typename _IIter, typename _Tp, typename _IteratorTag>
69 __accumulate_switch(_IIter __begin, _IIter __end,
70 _Tp __init, _IteratorTag)
71 { return accumulate(__begin, __end, __init,
72 __gnu_parallel::sequential_tag()); }
74 template<typename _IIter, typename _Tp, typename _BinaryOperation,
75 typename _IteratorTag>
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()); }
82 // Parallel algorithm for random access iterators.
83 template<typename __RAIter, typename _Tp,
84 typename _BinaryOperation>
86 __accumulate_switch(__RAIter __begin, __RAIter __end,
87 _Tp __init, _BinaryOperation __binary_op,
88 random_access_iterator_tag,
89 __gnu_parallel::_Parallelism __parallelism_tag
90 = __gnu_parallel::parallel_unbalanced)
92 if (_GLIBCXX_PARALLEL_CONDITION(
93 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
94 >= __gnu_parallel::_Settings::get().accumulate_minimal_n
95 && __gnu_parallel::__is_parallel(__parallelism_tag)))
98 __gnu_parallel::__accumulate_selector<__RAIter>
101 __for_each_template_random_access_ed(__begin, __end,
102 __gnu_parallel::_Nothing(),
105 __accumulate_binop_reduct
106 <_BinaryOperation>(__binary_op),
111 return accumulate(__begin, __end, __init, __binary_op,
112 __gnu_parallel::sequential_tag());
116 template<typename _IIter, typename _Tp>
118 accumulate(_IIter __begin, _IIter __end, _Tp __init,
119 __gnu_parallel::_Parallelism __parallelism_tag)
121 typedef std::iterator_traits<_IIter> _IteratorTraits;
122 typedef typename _IteratorTraits::value_type _ValueType;
123 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
125 return __accumulate_switch(__begin, __end, __init,
126 __gnu_parallel::_Plus<_Tp, _ValueType>(),
127 _IteratorCategory(), __parallelism_tag);
130 template<typename _IIter, typename _Tp>
132 accumulate(_IIter __begin, _IIter __end, _Tp __init)
134 typedef std::iterator_traits<_IIter> _IteratorTraits;
135 typedef typename _IteratorTraits::value_type _ValueType;
136 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
138 return __accumulate_switch(__begin, __end, __init,
139 __gnu_parallel::_Plus<_Tp, _ValueType>(),
140 _IteratorCategory());
143 template<typename _IIter, typename _Tp, typename _BinaryOperation>
145 accumulate(_IIter __begin, _IIter __end, _Tp __init,
146 _BinaryOperation __binary_op,
147 __gnu_parallel::_Parallelism __parallelism_tag)
149 typedef iterator_traits<_IIter> _IteratorTraits;
150 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
151 return __accumulate_switch(__begin, __end, __init, __binary_op,
152 _IteratorCategory(), __parallelism_tag);
155 template<typename _IIter, typename _Tp, typename _BinaryOperation>
157 accumulate(_IIter __begin, _IIter __end, _Tp __init,
158 _BinaryOperation __binary_op)
160 typedef iterator_traits<_IIter> _IteratorTraits;
161 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
162 return __accumulate_switch(__begin, __end, __init, __binary_op,
163 _IteratorCategory());
167 // Sequential fallback.
168 template<typename _IIter1, typename _IIter2, typename _Tp>
170 inner_product(_IIter1 __first1, _IIter1 __last1,
171 _IIter2 __first2, _Tp __init,
172 __gnu_parallel::sequential_tag)
173 { return _GLIBCXX_STD_P::inner_product(
174 __first1, __last1, __first2, __init); }
176 template<typename _IIter1, typename _IIter2, typename _Tp,
177 typename _BinaryFunction1, typename _BinaryFunction2>
179 inner_product(_IIter1 __first1, _IIter1 __last1,
180 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
181 _BinaryFunction2 __binary_op2,
182 __gnu_parallel::sequential_tag)
183 { return _GLIBCXX_STD_P::inner_product(__first1, __last1, __first2, __init,
184 __binary_op1, __binary_op2); }
186 // Parallel algorithm for random access iterators.
187 template<typename _RAIter1, typename _RAIter2,
188 typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>
190 __inner_product_switch(_RAIter1 __first1,
192 _RAIter2 __first2, _Tp __init,
193 _BinaryFunction1 __binary_op1,
194 _BinaryFunction2 __binary_op2,
195 random_access_iterator_tag,
196 random_access_iterator_tag,
197 __gnu_parallel::_Parallelism __parallelism_tag
198 = __gnu_parallel::parallel_unbalanced)
200 if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)
201 >= __gnu_parallel::_Settings::get().
204 __is_parallel(__parallelism_tag)))
208 __inner_product_selector<_RAIter1,
209 _RAIter2, _Tp> __my_selector(__first1, __first2);
211 __for_each_template_random_access_ed(
212 __first1, __last1, __binary_op2, __my_selector, __binary_op1,
217 return inner_product(__first1, __last1, __first2, __init,
218 __gnu_parallel::sequential_tag());
221 // No parallelism for input iterators.
222 template<typename _IIter1, typename _IIter2, typename _Tp,
223 typename _BinaryFunction1, typename _BinaryFunction2,
224 typename _IteratorTag1, typename _IteratorTag2>
226 __inner_product_switch(_IIter1 __first1, _IIter1 __last1,
227 _IIter2 __first2, _Tp __init,
228 _BinaryFunction1 __binary_op1,
229 _BinaryFunction2 __binary_op2,
230 _IteratorTag1, _IteratorTag2)
231 { return inner_product(__first1, __last1, __first2, __init,
232 __binary_op1, __binary_op2,
233 __gnu_parallel::sequential_tag()); }
235 template<typename _IIter1, typename _IIter2, typename _Tp,
236 typename _BinaryFunction1, typename _BinaryFunction2>
238 inner_product(_IIter1 __first1, _IIter1 __last1,
239 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
240 _BinaryFunction2 __binary_op2,
241 __gnu_parallel::_Parallelism __parallelism_tag)
243 typedef iterator_traits<_IIter1> _TraitsType1;
244 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
246 typedef iterator_traits<_IIter2> _TraitsType2;
247 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
249 return __inner_product_switch(
250 __first1, __last1, __first2, __init, __binary_op1,
251 __binary_op2, _IteratorCategory1(), _IteratorCategory2(),
255 template<typename _IIter1, typename _IIter2, typename _Tp,
256 typename _BinaryFunction1, typename _BinaryFunction2>
258 inner_product(_IIter1 __first1, _IIter1 __last1,
259 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
260 _BinaryFunction2 __binary_op2)
262 typedef iterator_traits<_IIter1> _TraitsType1;
263 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
265 typedef iterator_traits<_IIter2> _TraitsType2;
266 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
268 return __inner_product_switch(
269 __first1, __last1, __first2, __init, __binary_op1, __binary_op2,
270 _IteratorCategory1(), _IteratorCategory2());
273 template<typename _IIter1, typename _IIter2, typename _Tp>
275 inner_product(_IIter1 __first1, _IIter1 __last1,
276 _IIter2 __first2, _Tp __init,
277 __gnu_parallel::_Parallelism __parallelism_tag)
279 typedef iterator_traits<_IIter1> _TraitsType1;
280 typedef typename _TraitsType1::value_type _ValueType1;
281 typedef iterator_traits<_IIter2> _TraitsType2;
282 typedef typename _TraitsType2::value_type _ValueType2;
285 __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::__result
286 _MultipliesResultType;
287 return inner_product(__first1, __last1, __first2, __init,
288 __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
290 _Multiplies<_ValueType1, _ValueType2>(),
294 template<typename _IIter1, typename _IIter2, typename _Tp>
296 inner_product(_IIter1 __first1, _IIter1 __last1,
297 _IIter2 __first2, _Tp __init)
299 typedef iterator_traits<_IIter1> _TraitsType1;
300 typedef typename _TraitsType1::value_type _ValueType1;
301 typedef iterator_traits<_IIter2> _TraitsType2;
302 typedef typename _TraitsType2::value_type _ValueType2;
305 __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::__result
306 _MultipliesResultType;
307 return inner_product(__first1, __last1, __first2, __init,
308 __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
310 _Multiplies<_ValueType1, _ValueType2>());
313 // Sequential fallback.
314 template<typename _IIter, typename _OutputIterator>
315 inline _OutputIterator
316 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
317 __gnu_parallel::sequential_tag)
318 { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result); }
320 // Sequential fallback.
321 template<typename _IIter, typename _OutputIterator,
322 typename _BinaryOperation>
323 inline _OutputIterator
324 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
325 _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
326 { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result, __bin_op); }
328 // Sequential fallback for input iterator case.
329 template<typename _IIter, typename _OutputIterator,
330 typename _BinaryOperation, typename _IteratorTag1,
331 typename _IteratorTag2>
332 inline _OutputIterator
333 __partial_sum_switch(_IIter __begin, _IIter __end,
334 _OutputIterator __result, _BinaryOperation __bin_op,
335 _IteratorTag1, _IteratorTag2)
336 { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result, __bin_op); }
338 // Parallel algorithm for random access iterators.
339 template<typename _IIter, typename _OutputIterator,
340 typename _BinaryOperation>
342 __partial_sum_switch(_IIter __begin, _IIter __end,
343 _OutputIterator __result, _BinaryOperation __bin_op,
344 random_access_iterator_tag, random_access_iterator_tag)
346 if (_GLIBCXX_PARALLEL_CONDITION(
347 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
348 >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
349 return __gnu_parallel::__parallel_partial_sum(__begin, __end,
352 return partial_sum(__begin, __end, __result, __bin_op,
353 __gnu_parallel::sequential_tag());
357 template<typename _IIter, typename _OutputIterator>
358 inline _OutputIterator
359 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result)
361 typedef typename iterator_traits<_IIter>::value_type _ValueType;
362 return partial_sum(__begin, __end, __result, std::plus<_ValueType>());
366 template<typename _IIter, typename _OutputIterator,
367 typename _BinaryOperation>
368 inline _OutputIterator
369 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
370 _BinaryOperation __binary_op)
372 typedef iterator_traits<_IIter> _ITraitsType;
373 typedef typename _ITraitsType::iterator_category _IIteratorCategory;
375 typedef iterator_traits<_OutputIterator> _OTraitsType;
376 typedef typename _OTraitsType::iterator_category _OIterCategory;
378 return __partial_sum_switch(__begin, __end, __result, __binary_op,
379 _IIteratorCategory(), _OIterCategory());
382 // Sequential fallback.
383 template<typename _IIter, typename _OutputIterator>
384 inline _OutputIterator
385 adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
386 __gnu_parallel::sequential_tag)
387 { return _GLIBCXX_STD_P::adjacent_difference(__begin, __end, __result); }
389 // Sequential fallback.
390 template<typename _IIter, typename _OutputIterator,
391 typename _BinaryOperation>
392 inline _OutputIterator
393 adjacent_difference(_IIter __begin, _IIter __end,
394 _OutputIterator __result, _BinaryOperation __bin_op,
395 __gnu_parallel::sequential_tag)
396 { return _GLIBCXX_STD_P::adjacent_difference(
397 __begin, __end, __result, __bin_op); }
399 // Sequential fallback for input iterator case.
400 template<typename _IIter, typename _OutputIterator,
401 typename _BinaryOperation, typename _IteratorTag1,
402 typename _IteratorTag2>
403 inline _OutputIterator
404 __adjacent_difference_switch(
405 _IIter __begin, _IIter __end, _OutputIterator __result,
406 _BinaryOperation __bin_op, _IteratorTag1, _IteratorTag2)
407 { return adjacent_difference(__begin, __end, __result, __bin_op,
408 __gnu_parallel::sequential_tag()); }
410 // Parallel algorithm for random access iterators.
411 template<typename _IIter, typename _OutputIterator,
412 typename _BinaryOperation>
414 __adjacent_difference_switch(
415 _IIter __begin, _IIter __end, _OutputIterator __result,
416 _BinaryOperation __bin_op,
417 random_access_iterator_tag, random_access_iterator_tag,
418 __gnu_parallel::_Parallelism __parallelism_tag
419 = __gnu_parallel::parallel_balanced)
421 if (_GLIBCXX_PARALLEL_CONDITION(
422 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
423 >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
424 && __gnu_parallel::__is_parallel(__parallelism_tag)))
427 typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,
428 random_access_iterator_tag> _ItTrip;
429 *__result = *__begin;
430 _ItTrip __begin_pair(__begin + 1, __result + 1),
431 __end_pair(__end, __result + (__end - __begin));
432 __gnu_parallel::__adjacent_difference_selector<_ItTrip>
435 __for_each_template_random_access_ed(
436 __begin_pair, __end_pair, __bin_op, __functionality,
437 __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);
438 return __functionality.finish_iterator;
441 return adjacent_difference(__begin, __end, __result, __bin_op,
442 __gnu_parallel::sequential_tag());
446 template<typename _IIter, typename _OutputIterator>
447 inline _OutputIterator
448 adjacent_difference(_IIter __begin, _IIter __end,
449 _OutputIterator __result,
450 __gnu_parallel::_Parallelism __parallelism_tag)
452 typedef iterator_traits<_IIter> _TraitsType;
453 typedef typename _TraitsType::value_type _ValueType;
454 return adjacent_difference(
455 __begin, __end, __result, std::minus<_ValueType>(),
459 template<typename _IIter, typename _OutputIterator>
460 inline _OutputIterator
461 adjacent_difference(_IIter __begin, _IIter __end,
462 _OutputIterator __result)
464 typedef iterator_traits<_IIter> _TraitsType;
465 typedef typename _TraitsType::value_type _ValueType;
466 return adjacent_difference(__begin, __end, __result,
467 std::minus<_ValueType>());
470 template<typename _IIter, typename _OutputIterator,
471 typename _BinaryOperation>
472 inline _OutputIterator
473 adjacent_difference(_IIter __begin, _IIter __end,
474 _OutputIterator __result, _BinaryOperation __binary_op,
475 __gnu_parallel::_Parallelism __parallelism_tag)
477 typedef iterator_traits<_IIter> _ITraitsType;
478 typedef typename _ITraitsType::iterator_category _IIteratorCategory;
480 typedef iterator_traits<_OutputIterator> _OTraitsType;
481 typedef typename _OTraitsType::iterator_category _OIterCategory;
483 return __adjacent_difference_switch(
484 __begin, __end, __result, __binary_op,
485 _IIteratorCategory(), _OIterCategory(), __parallelism_tag);
488 template<typename _IIter, typename _OutputIterator,
489 typename _BinaryOperation>
490 inline _OutputIterator
491 adjacent_difference(_IIter __begin, _IIter __end,
492 _OutputIterator __result, _BinaryOperation __binary_op)
494 typedef iterator_traits<_IIter> _ITraitsType;
495 typedef typename _ITraitsType::iterator_category _IIteratorCategory;
497 typedef iterator_traits<_OutputIterator> _OTraitsType;
498 typedef typename _OTraitsType::iterator_category _OIterCategory;
500 return __adjacent_difference_switch(
501 __begin, __end, __result, __binary_op,
502 _IIteratorCategory(), _OIterCategory());
507 #endif /* _GLIBCXX_NUMERIC_H */