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 InputIterator, typename T>
56 accumulate(InputIterator begin, InputIterator end, T init,
57 __gnu_parallel::sequential_tag)
58 { return _GLIBCXX_STD_P::accumulate(begin, end, init); }
60 template<typename InputIterator, typename T, typename BinaryOperation>
62 accumulate(InputIterator begin, InputIterator end, T 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 InputIterator, typename T, typename IteratorTag>
69 accumulate_switch(InputIterator begin, InputIterator end,
71 { return accumulate(begin, end, init, __gnu_parallel::sequential_tag()); }
73 template<typename InputIterator, typename T, typename BinaryOperation,
76 accumulate_switch(InputIterator begin, InputIterator end, T init,
77 BinaryOperation binary_op, IteratorTag)
78 { return accumulate(begin, end, init, binary_op,
79 __gnu_parallel::sequential_tag()); }
81 // Parallel algorithm for random access iterators.
82 template<typename _RandomAccessIterator, typename T,
83 typename BinaryOperation>
85 accumulate_switch(_RandomAccessIterator begin, _RandomAccessIterator end,
86 T init, BinaryOperation binary_op,
87 random_access_iterator_tag,
88 __gnu_parallel::_Parallelism parallelism_tag
89 = __gnu_parallel::parallel_unbalanced)
91 if (_GLIBCXX_PARALLEL_CONDITION(
92 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
93 >= __gnu_parallel::_Settings::get().accumulate_minimal_n
94 && __gnu_parallel::is_parallel(parallelism_tag)))
97 __gnu_parallel::accumulate_selector<_RandomAccessIterator>
100 for_each_template_random_access_ed(begin, end,
101 __gnu_parallel::nothing(),
104 accumulate_binop_reduct
105 <BinaryOperation>(binary_op),
110 return accumulate(begin, end, init, binary_op,
111 __gnu_parallel::sequential_tag());
115 template<typename InputIterator, typename T>
117 accumulate(InputIterator begin, InputIterator end, T init,
118 __gnu_parallel::_Parallelism parallelism_tag)
120 typedef std::iterator_traits<InputIterator> iterator_traits;
121 typedef typename iterator_traits::value_type value_type;
122 typedef typename iterator_traits::iterator_category iterator_category;
124 return accumulate_switch(begin, end, init,
125 __gnu_parallel::plus<T, value_type>(),
126 iterator_category(), parallelism_tag);
129 template<typename InputIterator, typename T>
131 accumulate(InputIterator begin, InputIterator end, T init)
133 typedef std::iterator_traits<InputIterator> iterator_traits;
134 typedef typename iterator_traits::value_type value_type;
135 typedef typename iterator_traits::iterator_category iterator_category;
137 return accumulate_switch(begin, end, init,
138 __gnu_parallel::plus<T, value_type>(),
139 iterator_category());
142 template<typename InputIterator, typename T, typename BinaryOperation>
144 accumulate(InputIterator begin, InputIterator end, T init,
145 BinaryOperation binary_op,
146 __gnu_parallel::_Parallelism parallelism_tag)
148 typedef iterator_traits<InputIterator> iterator_traits;
149 typedef typename iterator_traits::iterator_category iterator_category;
150 return accumulate_switch(begin, end, init, binary_op,
151 iterator_category(), parallelism_tag);
154 template<typename InputIterator, typename T, typename BinaryOperation>
156 accumulate(InputIterator begin, InputIterator end, T init,
157 BinaryOperation binary_op)
159 typedef iterator_traits<InputIterator> iterator_traits;
160 typedef typename iterator_traits::iterator_category iterator_category;
161 return accumulate_switch(begin, end, init, binary_op,
162 iterator_category());
166 // Sequential fallback.
167 template<typename InputIterator1, typename InputIterator2, typename T>
169 inner_product(InputIterator1 first1, InputIterator1 last1,
170 InputIterator2 first2, T init,
171 __gnu_parallel::sequential_tag)
172 { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init); }
174 template<typename InputIterator1, typename InputIterator2, typename T,
175 typename BinaryFunction1, typename BinaryFunction2>
177 inner_product(InputIterator1 first1, InputIterator1 last1,
178 InputIterator2 first2, T init, BinaryFunction1 binary_op1,
179 BinaryFunction2 binary_op2, __gnu_parallel::sequential_tag)
180 { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
181 binary_op1, binary_op2); }
183 // Parallel algorithm for random access iterators.
184 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
185 typename T, typename BinaryFunction1, typename BinaryFunction2>
187 inner_product_switch(RandomAccessIterator1 first1,
188 RandomAccessIterator1 last1,
189 RandomAccessIterator2 first2, T init,
190 BinaryFunction1 binary_op1,
191 BinaryFunction2 binary_op2,
192 random_access_iterator_tag,
193 random_access_iterator_tag,
194 __gnu_parallel::_Parallelism parallelism_tag
195 = __gnu_parallel::parallel_unbalanced)
197 if (_GLIBCXX_PARALLEL_CONDITION((last1 - first1)
198 >= __gnu_parallel::_Settings::get().
201 is_parallel(parallelism_tag)))
205 inner_product_selector<RandomAccessIterator1,
206 RandomAccessIterator2, T> my_selector(first1, first2);
208 for_each_template_random_access_ed(first1, last1, binary_op2,
209 my_selector, binary_op1,
214 return inner_product(first1, last1, first2, init,
215 __gnu_parallel::sequential_tag());
218 // No parallelism for input iterators.
219 template<typename InputIterator1, typename InputIterator2, typename T,
220 typename BinaryFunction1, typename BinaryFunction2,
221 typename IteratorTag1, typename IteratorTag2>
223 inner_product_switch(InputIterator1 first1, InputIterator1 last1,
224 InputIterator2 first2, T init,
225 BinaryFunction1 binary_op1,
226 BinaryFunction2 binary_op2,
227 IteratorTag1, IteratorTag2)
228 { return inner_product(first1, last1, first2, init,
229 binary_op1, binary_op2,
230 __gnu_parallel::sequential_tag()); }
232 template<typename InputIterator1, typename InputIterator2, typename T,
233 typename BinaryFunction1, typename BinaryFunction2>
235 inner_product(InputIterator1 first1, InputIterator1 last1,
236 InputIterator2 first2, T init, BinaryFunction1 binary_op1,
237 BinaryFunction2 binary_op2,
238 __gnu_parallel::_Parallelism parallelism_tag)
240 typedef iterator_traits<InputIterator1> traits1_type;
241 typedef typename traits1_type::iterator_category iterator1_category;
243 typedef iterator_traits<InputIterator2> traits2_type;
244 typedef typename traits2_type::iterator_category iterator2_category;
246 return inner_product_switch(first1, last1, first2, init, binary_op1,
247 binary_op2, iterator1_category(),
248 iterator2_category(), parallelism_tag);
251 template<typename InputIterator1, typename InputIterator2, typename T,
252 typename BinaryFunction1, typename BinaryFunction2>
254 inner_product(InputIterator1 first1, InputIterator1 last1,
255 InputIterator2 first2, T init, BinaryFunction1 binary_op1,
256 BinaryFunction2 binary_op2)
258 typedef iterator_traits<InputIterator1> traits1_type;
259 typedef typename traits1_type::iterator_category iterator1_category;
261 typedef iterator_traits<InputIterator2> traits2_type;
262 typedef typename traits2_type::iterator_category iterator2_category;
264 return inner_product_switch(first1, last1, first2, init, binary_op1,
265 binary_op2, iterator1_category(),
266 iterator2_category());
269 template<typename InputIterator1, typename InputIterator2, typename T>
271 inner_product(InputIterator1 first1, InputIterator1 last1,
272 InputIterator2 first2, T init,
273 __gnu_parallel::_Parallelism parallelism_tag)
275 typedef iterator_traits<InputIterator1> traits_type1;
276 typedef typename traits_type1::value_type value_type1;
277 typedef iterator_traits<InputIterator2> traits_type2;
278 typedef typename traits_type2::value_type value_type2;
281 __gnu_parallel::multiplies<value_type1, value_type2>::result
282 multiplies_result_type;
283 return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
284 __gnu_parallel::plus<T, multiplies_result_type>(),
286 multiplies<value_type1, value_type2>(),
290 template<typename InputIterator1, typename InputIterator2, typename T>
292 inner_product(InputIterator1 first1, InputIterator1 last1,
293 InputIterator2 first2, T init)
295 typedef iterator_traits<InputIterator1> traits_type1;
296 typedef typename traits_type1::value_type value_type1;
297 typedef iterator_traits<InputIterator2> traits_type2;
298 typedef typename traits_type2::value_type value_type2;
301 __gnu_parallel::multiplies<value_type1, value_type2>::result
302 multiplies_result_type;
303 return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
304 __gnu_parallel::plus<T, multiplies_result_type>(),
306 multiplies<value_type1, value_type2>());
309 // Sequential fallback.
310 template<typename InputIterator, typename OutputIterator>
311 inline OutputIterator
312 partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
313 __gnu_parallel::sequential_tag)
314 { return _GLIBCXX_STD_P::partial_sum(begin, end, result); }
316 // Sequential fallback.
317 template<typename InputIterator, typename OutputIterator,
318 typename BinaryOperation>
319 inline OutputIterator
320 partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
321 BinaryOperation bin_op, __gnu_parallel::sequential_tag)
322 { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
324 // Sequential fallback for input iterator case.
325 template<typename InputIterator, typename OutputIterator,
326 typename BinaryOperation, typename IteratorTag1,
327 typename IteratorTag2>
328 inline OutputIterator
329 partial_sum_switch(InputIterator begin, InputIterator end,
330 OutputIterator result, BinaryOperation bin_op,
331 IteratorTag1, IteratorTag2)
332 { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
334 // Parallel algorithm for random access iterators.
335 template<typename InputIterator, typename OutputIterator,
336 typename BinaryOperation>
338 partial_sum_switch(InputIterator begin, InputIterator end,
339 OutputIterator result, BinaryOperation bin_op,
340 random_access_iterator_tag, random_access_iterator_tag)
342 if (_GLIBCXX_PARALLEL_CONDITION(
343 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
344 >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
345 return __gnu_parallel::parallel_partial_sum(begin, end,
348 return partial_sum(begin, end, result, bin_op,
349 __gnu_parallel::sequential_tag());
353 template<typename InputIterator, typename OutputIterator>
354 inline OutputIterator
355 partial_sum(InputIterator begin, InputIterator end, OutputIterator result)
357 typedef typename iterator_traits<InputIterator>::value_type value_type;
358 return _GLIBCXX_STD_P::partial_sum(begin, end, result,
359 std::plus<value_type>());
363 template<typename InputIterator, typename OutputIterator,
364 typename BinaryOperation>
365 inline OutputIterator
366 partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
367 BinaryOperation binary_op)
369 typedef iterator_traits<InputIterator> traitsi_type;
370 typedef typename traitsi_type::iterator_category iteratori_category;
372 typedef iterator_traits<OutputIterator> traitso_type;
373 typedef typename traitso_type::iterator_category iteratoro_category;
375 return partial_sum_switch(begin, end, result, binary_op,
376 iteratori_category(), iteratoro_category());
379 // Sequential fallback.
380 template<typename InputIterator, typename OutputIterator>
381 inline OutputIterator
382 adjacent_difference(InputIterator begin, InputIterator end,
383 OutputIterator result, __gnu_parallel::sequential_tag)
384 { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); }
386 // Sequential fallback.
387 template<typename InputIterator, typename OutputIterator,
388 typename BinaryOperation>
389 inline OutputIterator
390 adjacent_difference(InputIterator begin, InputIterator end,
391 OutputIterator result, BinaryOperation bin_op,
392 __gnu_parallel::sequential_tag)
393 { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op); }
395 // Sequential fallback for input iterator case.
396 template<typename InputIterator, typename OutputIterator,
397 typename BinaryOperation, typename IteratorTag1,
398 typename IteratorTag2>
399 inline OutputIterator
400 adjacent_difference_switch(InputIterator begin, InputIterator end,
401 OutputIterator result, BinaryOperation bin_op,
402 IteratorTag1, IteratorTag2)
403 { return adjacent_difference(begin, end, result, bin_op,
404 __gnu_parallel::sequential_tag()); }
406 // Parallel algorithm for random access iterators.
407 template<typename InputIterator, typename OutputIterator,
408 typename BinaryOperation>
410 adjacent_difference_switch(InputIterator begin, InputIterator end,
411 OutputIterator result, BinaryOperation bin_op,
412 random_access_iterator_tag,
413 random_access_iterator_tag,
414 __gnu_parallel::_Parallelism parallelism_tag
415 = __gnu_parallel::parallel_balanced)
417 if (_GLIBCXX_PARALLEL_CONDITION(
418 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
419 >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
420 && __gnu_parallel::is_parallel(parallelism_tag)))
423 typedef __gnu_parallel::iterator_pair<InputIterator, OutputIterator,
424 random_access_iterator_tag> ip;
426 ip begin_pair(begin + 1, result + 1),
427 end_pair(end, result + (end - begin));
428 __gnu_parallel::adjacent_difference_selector<ip> functionality;
430 for_each_template_random_access_ed(begin_pair, end_pair, bin_op,
432 __gnu_parallel::dummy_reduct(),
434 return functionality.finish_iterator;
437 return adjacent_difference(begin, end, result, bin_op,
438 __gnu_parallel::sequential_tag());
442 template<typename InputIterator, typename OutputIterator>
443 inline OutputIterator
444 adjacent_difference(InputIterator begin, InputIterator end,
445 OutputIterator result,
446 __gnu_parallel::_Parallelism parallelism_tag)
448 typedef iterator_traits<InputIterator> traits_type;
449 typedef typename traits_type::value_type value_type;
450 return adjacent_difference(begin, end, result, std::minus<value_type>(),
454 template<typename InputIterator, typename OutputIterator>
455 inline OutputIterator
456 adjacent_difference(InputIterator begin, InputIterator end,
457 OutputIterator result)
459 typedef iterator_traits<InputIterator> traits_type;
460 typedef typename traits_type::value_type value_type;
461 return adjacent_difference(begin, end, result, std::minus<value_type>());
464 template<typename InputIterator, typename OutputIterator,
465 typename BinaryOperation>
466 inline OutputIterator
467 adjacent_difference(InputIterator begin, InputIterator end,
468 OutputIterator result, BinaryOperation binary_op,
469 __gnu_parallel::_Parallelism parallelism_tag)
471 typedef iterator_traits<InputIterator> traitsi_type;
472 typedef typename traitsi_type::iterator_category iteratori_category;
474 typedef iterator_traits<OutputIterator> traitso_type;
475 typedef typename traitso_type::iterator_category iteratoro_category;
477 return adjacent_difference_switch(begin, end, result, binary_op,
478 iteratori_category(),
479 iteratoro_category(), parallelism_tag);
482 template<typename InputIterator, typename OutputIterator,
483 typename BinaryOperation>
484 inline OutputIterator
485 adjacent_difference(InputIterator begin, InputIterator end,
486 OutputIterator result, BinaryOperation binary_op)
488 typedef iterator_traits<InputIterator> traitsi_type;
489 typedef typename traitsi_type::iterator_category iteratori_category;
491 typedef iterator_traits<OutputIterator> traitso_type;
492 typedef typename traitso_type::iterator_category iteratoro_category;
494 return adjacent_difference_switch(begin, end, result, binary_op,
495 iteratori_category(),
496 iteratoro_category());
501 #endif /* _GLIBCXX_NUMERIC_H */