| // -*- C++ -*- |
| |
| // Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. |
| // |
| // This file is part of the GNU ISO C++ Library. This library is free |
| // software; you can redistribute it and/or modify it under the terms |
| // of the GNU General Public License as published by the Free Software |
| // Foundation; either version 3, or (at your option) any later |
| // version. |
| |
| // This library is distributed in the hope that it will be useful, but |
| // WITHOUT ANY WARRANTY; without even the implied warranty of |
| // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| // General Public License for more details. |
| |
| // Under Section 7 of GPL version 3, you are granted additional |
| // permissions described in the GCC Runtime Library Exception, version |
| // 3.1, as published by the Free Software Foundation. |
| |
| // You should have received a copy of the GNU General Public License and |
| // a copy of the GCC Runtime Library Exception along with this program; |
| // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
| // <http://www.gnu.org/licenses/>. |
| |
| /** |
| * @file parallel/numeric |
| * |
| * @brief Parallel STL function calls corresponding to stl_numeric.h. |
| * The functions defined here mainly do case switches and |
| * call the actual parallelized versions in other files. |
| * Inlining policy: Functions that basically only contain one function call, |
| * are declared inline. |
| * This file is a GNU parallel extension to the Standard C++ Library. |
| */ |
| |
| // Written by Johannes Singler and Felix Putze. |
| |
| #ifndef _GLIBCXX_PARALLEL_NUMERIC_H |
| #define _GLIBCXX_PARALLEL_NUMERIC_H 1 |
| |
| #include <numeric> |
| #include <bits/stl_function.h> |
| #include <parallel/numericfwd.h> |
| #include <parallel/iterator.h> |
| #include <parallel/for_each.h> |
| #include <parallel/for_each_selectors.h> |
| #include <parallel/partial_sum.h> |
| |
| namespace std _GLIBCXX_VISIBILITY(default) |
| { |
| namespace __parallel |
| { |
| // Sequential fallback. |
| template<typename _IIter, typename _Tp> |
| inline _Tp |
| accumulate(_IIter __begin, _IIter __end, _Tp __init, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init); } |
| |
| template<typename _IIter, typename _Tp, typename _BinaryOperation> |
| inline _Tp |
| accumulate(_IIter __begin, _IIter __end, _Tp __init, |
| _BinaryOperation __binary_op, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init, __binary_op); } |
| |
| // Sequential fallback for input iterator case. |
| template<typename _IIter, typename _Tp, typename _IteratorTag> |
| inline _Tp |
| __accumulate_switch(_IIter __begin, _IIter __end, |
| _Tp __init, _IteratorTag) |
| { return accumulate(__begin, __end, __init, |
| __gnu_parallel::sequential_tag()); } |
| |
| template<typename _IIter, typename _Tp, typename _BinaryOperation, |
| typename _IteratorTag> |
| inline _Tp |
| __accumulate_switch(_IIter __begin, _IIter __end, _Tp __init, |
| _BinaryOperation __binary_op, _IteratorTag) |
| { return accumulate(__begin, __end, __init, __binary_op, |
| __gnu_parallel::sequential_tag()); } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename __RAIter, typename _Tp, typename _BinaryOperation> |
| _Tp |
| __accumulate_switch(__RAIter __begin, __RAIter __end, |
| _Tp __init, _BinaryOperation __binary_op, |
| random_access_iterator_tag, |
| __gnu_parallel::_Parallelism __parallelism_tag |
| = __gnu_parallel::parallel_unbalanced) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
| >= __gnu_parallel::_Settings::get().accumulate_minimal_n |
| && __gnu_parallel::__is_parallel(__parallelism_tag))) |
| { |
| _Tp __res = __init; |
| __gnu_parallel::__accumulate_selector<__RAIter> |
| __my_selector; |
| __gnu_parallel:: |
| __for_each_template_random_access_ed(__begin, __end, |
| __gnu_parallel::_Nothing(), |
| __my_selector, |
| __gnu_parallel:: |
| __accumulate_binop_reduct |
| <_BinaryOperation>(__binary_op), |
| __res, __res, -1); |
| return __res; |
| } |
| else |
| return accumulate(__begin, __end, __init, __binary_op, |
| __gnu_parallel::sequential_tag()); |
| } |
| |
| // Public interface. |
| template<typename _IIter, typename _Tp> |
| inline _Tp |
| accumulate(_IIter __begin, _IIter __end, _Tp __init, |
| __gnu_parallel::_Parallelism __parallelism_tag) |
| { |
| typedef std::iterator_traits<_IIter> _IteratorTraits; |
| typedef typename _IteratorTraits::value_type _ValueType; |
| typedef typename _IteratorTraits::iterator_category _IteratorCategory; |
| |
| return __accumulate_switch(__begin, __end, __init, |
| __gnu_parallel::_Plus<_Tp, _ValueType>(), |
| _IteratorCategory(), __parallelism_tag); |
| } |
| |
| template<typename _IIter, typename _Tp> |
| inline _Tp |
| accumulate(_IIter __begin, _IIter __end, _Tp __init) |
| { |
| typedef std::iterator_traits<_IIter> _IteratorTraits; |
| typedef typename _IteratorTraits::value_type _ValueType; |
| typedef typename _IteratorTraits::iterator_category _IteratorCategory; |
| |
| return __accumulate_switch(__begin, __end, __init, |
| __gnu_parallel::_Plus<_Tp, _ValueType>(), |
| _IteratorCategory()); |
| } |
| |
| template<typename _IIter, typename _Tp, typename _BinaryOperation> |
| inline _Tp |
| accumulate(_IIter __begin, _IIter __end, _Tp __init, |
| _BinaryOperation __binary_op, |
| __gnu_parallel::_Parallelism __parallelism_tag) |
| { |
| typedef iterator_traits<_IIter> _IteratorTraits; |
| typedef typename _IteratorTraits::iterator_category _IteratorCategory; |
| return __accumulate_switch(__begin, __end, __init, __binary_op, |
| _IteratorCategory(), __parallelism_tag); |
| } |
| |
| template<typename _IIter, typename _Tp, typename _BinaryOperation> |
| inline _Tp |
| accumulate(_IIter __begin, _IIter __end, _Tp __init, |
| _BinaryOperation __binary_op) |
| { |
| typedef iterator_traits<_IIter> _IteratorTraits; |
| typedef typename _IteratorTraits::iterator_category _IteratorCategory; |
| return __accumulate_switch(__begin, __end, __init, __binary_op, |
| _IteratorCategory()); |
| } |
| |
| |
| // Sequential fallback. |
| template<typename _IIter1, typename _IIter2, typename _Tp> |
| inline _Tp |
| inner_product(_IIter1 __first1, _IIter1 __last1, |
| _IIter2 __first2, _Tp __init, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_A::inner_product( |
| __first1, __last1, __first2, __init); } |
| |
| template<typename _IIter1, typename _IIter2, typename _Tp, |
| typename _BinaryFunction1, typename _BinaryFunction2> |
| inline _Tp |
| inner_product(_IIter1 __first1, _IIter1 __last1, |
| _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, |
| _BinaryFunction2 __binary_op2, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_A::inner_product(__first1, __last1, __first2, __init, |
| __binary_op1, __binary_op2); } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename _RAIter1, typename _RAIter2, |
| typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2> |
| _Tp |
| __inner_product_switch(_RAIter1 __first1, |
| _RAIter1 __last1, |
| _RAIter2 __first2, _Tp __init, |
| _BinaryFunction1 __binary_op1, |
| _BinaryFunction2 __binary_op2, |
| random_access_iterator_tag, |
| random_access_iterator_tag, |
| __gnu_parallel::_Parallelism __parallelism_tag |
| = __gnu_parallel::parallel_unbalanced) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1) |
| >= __gnu_parallel::_Settings::get(). |
| accumulate_minimal_n |
| && __gnu_parallel:: |
| __is_parallel(__parallelism_tag))) |
| { |
| _Tp __res = __init; |
| __gnu_parallel:: |
| __inner_product_selector<_RAIter1, |
| _RAIter2, _Tp> __my_selector(__first1, __first2); |
| __gnu_parallel:: |
| __for_each_template_random_access_ed( |
| __first1, __last1, __binary_op2, __my_selector, __binary_op1, |
| __res, __res, -1); |
| return __res; |
| } |
| else |
| return inner_product(__first1, __last1, __first2, __init, |
| __gnu_parallel::sequential_tag()); |
| } |
| |
| // No parallelism for input iterators. |
| template<typename _IIter1, typename _IIter2, typename _Tp, |
| typename _BinaryFunction1, typename _BinaryFunction2, |
| typename _IteratorTag1, typename _IteratorTag2> |
| inline _Tp |
| __inner_product_switch(_IIter1 __first1, _IIter1 __last1, |
| _IIter2 __first2, _Tp __init, |
| _BinaryFunction1 __binary_op1, |
| _BinaryFunction2 __binary_op2, |
| _IteratorTag1, _IteratorTag2) |
| { return inner_product(__first1, __last1, __first2, __init, __binary_op1, |
| __binary_op2, __gnu_parallel::sequential_tag()); } |
| |
| template<typename _IIter1, typename _IIter2, typename _Tp, |
| typename _BinaryFunction1, typename _BinaryFunction2> |
| inline _Tp |
| inner_product(_IIter1 __first1, _IIter1 __last1, |
| _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, |
| _BinaryFunction2 __binary_op2, |
| __gnu_parallel::_Parallelism __parallelism_tag) |
| { |
| typedef iterator_traits<_IIter1> _TraitsType1; |
| typedef typename _TraitsType1::iterator_category _IteratorCategory1; |
| |
| typedef iterator_traits<_IIter2> _TraitsType2; |
| typedef typename _TraitsType2::iterator_category _IteratorCategory2; |
| |
| return __inner_product_switch(__first1, __last1, __first2, __init, |
| __binary_op1, __binary_op2, |
| _IteratorCategory1(), _IteratorCategory2(), |
| __parallelism_tag); |
| } |
| |
| template<typename _IIter1, typename _IIter2, typename _Tp, |
| typename _BinaryFunction1, typename _BinaryFunction2> |
| inline _Tp |
| inner_product(_IIter1 __first1, _IIter1 __last1, |
| _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, |
| _BinaryFunction2 __binary_op2) |
| { |
| typedef iterator_traits<_IIter1> _TraitsType1; |
| typedef typename _TraitsType1::iterator_category _IteratorCategory1; |
| |
| typedef iterator_traits<_IIter2> _TraitsType2; |
| typedef typename _TraitsType2::iterator_category _IteratorCategory2; |
| |
| return __inner_product_switch(__first1, __last1, __first2, __init, |
| __binary_op1, __binary_op2, |
| _IteratorCategory1(), |
| _IteratorCategory2()); |
| } |
| |
| template<typename _IIter1, typename _IIter2, typename _Tp> |
| inline _Tp |
| inner_product(_IIter1 __first1, _IIter1 __last1, |
| _IIter2 __first2, _Tp __init, |
| __gnu_parallel::_Parallelism __parallelism_tag) |
| { |
| typedef iterator_traits<_IIter1> _TraitsType1; |
| typedef typename _TraitsType1::value_type _ValueType1; |
| typedef iterator_traits<_IIter2> _TraitsType2; |
| typedef typename _TraitsType2::value_type _ValueType2; |
| |
| typedef typename |
| __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type |
| _MultipliesResultType; |
| return __gnu_parallel::inner_product(__first1, __last1, __first2, __init, |
| __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(), |
| __gnu_parallel:: |
| _Multiplies<_ValueType1, _ValueType2>(), |
| __parallelism_tag); |
| } |
| |
| template<typename _IIter1, typename _IIter2, typename _Tp> |
| inline _Tp |
| inner_product(_IIter1 __first1, _IIter1 __last1, |
| _IIter2 __first2, _Tp __init) |
| { |
| typedef iterator_traits<_IIter1> _TraitsType1; |
| typedef typename _TraitsType1::value_type _ValueType1; |
| typedef iterator_traits<_IIter2> _TraitsType2; |
| typedef typename _TraitsType2::value_type _ValueType2; |
| |
| typedef typename |
| __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type |
| _MultipliesResultType; |
| return __gnu_parallel::inner_product(__first1, __last1, __first2, __init, |
| __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(), |
| __gnu_parallel:: |
| _Multiplies<_ValueType1, _ValueType2>()); |
| } |
| |
| // Sequential fallback. |
| template<typename _IIter, typename _OutputIterator> |
| inline _OutputIterator |
| partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); } |
| |
| // Sequential fallback. |
| template<typename _IIter, typename _OutputIterator, |
| typename _BinaryOperation> |
| inline _OutputIterator |
| partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result, |
| _BinaryOperation __bin_op, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); } |
| |
| // Sequential fallback for input iterator case. |
| template<typename _IIter, typename _OutputIterator, |
| typename _BinaryOperation, typename _IteratorTag1, |
| typename _IteratorTag2> |
| inline _OutputIterator |
| __partial_sum_switch(_IIter __begin, _IIter __end, |
| _OutputIterator __result, _BinaryOperation __bin_op, |
| _IteratorTag1, _IteratorTag2) |
| { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename _IIter, typename _OutputIterator, |
| typename _BinaryOperation> |
| _OutputIterator |
| __partial_sum_switch(_IIter __begin, _IIter __end, |
| _OutputIterator __result, _BinaryOperation __bin_op, |
| random_access_iterator_tag, |
| random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
| >= __gnu_parallel::_Settings::get().partial_sum_minimal_n)) |
| return __gnu_parallel::__parallel_partial_sum(__begin, __end, |
| __result, __bin_op); |
| else |
| return partial_sum(__begin, __end, __result, __bin_op, |
| __gnu_parallel::sequential_tag()); |
| } |
| |
| // Public interface. |
| template<typename _IIter, typename _OutputIterator> |
| inline _OutputIterator |
| partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result) |
| { |
| typedef typename iterator_traits<_IIter>::value_type _ValueType; |
| return __gnu_parallel::partial_sum(__begin, __end, |
| __result, std::plus<_ValueType>()); |
| } |
| |
| // Public interface |
| template<typename _IIter, typename _OutputIterator, |
| typename _BinaryOperation> |
| inline _OutputIterator |
| partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result, |
| _BinaryOperation __binary_op) |
| { |
| typedef iterator_traits<_IIter> _ITraitsType; |
| typedef typename _ITraitsType::iterator_category _IIteratorCategory; |
| |
| typedef iterator_traits<_OutputIterator> _OTraitsType; |
| typedef typename _OTraitsType::iterator_category _OIterCategory; |
| |
| return __partial_sum_switch(__begin, __end, __result, __binary_op, |
| _IIteratorCategory(), _OIterCategory()); |
| } |
| |
| // Sequential fallback. |
| template<typename _IIter, typename _OutputIterator> |
| inline _OutputIterator |
| adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); } |
| |
| // Sequential fallback. |
| template<typename _IIter, typename _OutputIterator, |
| typename _BinaryOperation> |
| inline _OutputIterator |
| adjacent_difference(_IIter __begin, _IIter __end, |
| _OutputIterator __result, _BinaryOperation __bin_op, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, |
| __result, __bin_op); } |
| |
| // Sequential fallback for input iterator case. |
| template<typename _IIter, typename _OutputIterator, |
| typename _BinaryOperation, typename _IteratorTag1, |
| typename _IteratorTag2> |
| inline _OutputIterator |
| __adjacent_difference_switch(_IIter __begin, _IIter __end, |
| _OutputIterator __result, |
| _BinaryOperation __bin_op, _IteratorTag1, |
| _IteratorTag2) |
| { return adjacent_difference(__begin, __end, __result, __bin_op, |
| __gnu_parallel::sequential_tag()); } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename _IIter, typename _OutputIterator, |
| typename _BinaryOperation> |
| _OutputIterator |
| __adjacent_difference_switch(_IIter __begin, _IIter __end, |
| _OutputIterator __result, |
| _BinaryOperation __bin_op, |
| random_access_iterator_tag, |
| random_access_iterator_tag, |
| __gnu_parallel::_Parallelism |
| __parallelism_tag |
| = __gnu_parallel::parallel_balanced) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
| >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n |
| && __gnu_parallel::__is_parallel(__parallelism_tag))) |
| { |
| bool __dummy = true; |
| typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator, |
| random_access_iterator_tag> _ItTrip; |
| *__result = *__begin; |
| _ItTrip __begin_pair(__begin + 1, __result + 1), |
| __end_pair(__end, __result + (__end - __begin)); |
| __gnu_parallel::__adjacent_difference_selector<_ItTrip> |
| __functionality; |
| __gnu_parallel:: |
| __for_each_template_random_access_ed( |
| __begin_pair, __end_pair, __bin_op, __functionality, |
| __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1); |
| return __functionality._M_finish_iterator; |
| } |
| else |
| return adjacent_difference(__begin, __end, __result, __bin_op, |
| __gnu_parallel::sequential_tag()); |
| } |
| |
| // Public interface. |
| template<typename _IIter, typename _OutputIterator> |
| inline _OutputIterator |
| adjacent_difference(_IIter __begin, _IIter __end, |
| _OutputIterator __result, |
| __gnu_parallel::_Parallelism __parallelism_tag) |
| { |
| typedef iterator_traits<_IIter> _TraitsType; |
| typedef typename _TraitsType::value_type _ValueType; |
| return adjacent_difference(__begin, __end, __result, |
| std::minus<_ValueType>(), |
| __parallelism_tag); |
| } |
| |
| template<typename _IIter, typename _OutputIterator> |
| inline _OutputIterator |
| adjacent_difference(_IIter __begin, _IIter __end, |
| _OutputIterator __result) |
| { |
| typedef iterator_traits<_IIter> _TraitsType; |
| typedef typename _TraitsType::value_type _ValueType; |
| return adjacent_difference(__begin, __end, __result, |
| std::minus<_ValueType>()); |
| } |
| |
| template<typename _IIter, typename _OutputIterator, |
| typename _BinaryOperation> |
| inline _OutputIterator |
| adjacent_difference(_IIter __begin, _IIter __end, |
| _OutputIterator __result, _BinaryOperation __binary_op, |
| __gnu_parallel::_Parallelism __parallelism_tag) |
| { |
| typedef iterator_traits<_IIter> _ITraitsType; |
| typedef typename _ITraitsType::iterator_category _IIteratorCategory; |
| |
| typedef iterator_traits<_OutputIterator> _OTraitsType; |
| typedef typename _OTraitsType::iterator_category _OIterCategory; |
| |
| return __adjacent_difference_switch(__begin, __end, __result, |
| __binary_op, |
| _IIteratorCategory(), |
| _OIterCategory(), |
| __parallelism_tag); |
| } |
| |
| template<typename _IIter, typename _OutputIterator, |
| typename _BinaryOperation> |
| inline _OutputIterator |
| adjacent_difference(_IIter __begin, _IIter __end, |
| _OutputIterator __result, _BinaryOperation __binary_op) |
| { |
| typedef iterator_traits<_IIter> _ITraitsType; |
| typedef typename _ITraitsType::iterator_category _IIteratorCategory; |
| |
| typedef iterator_traits<_OutputIterator> _OTraitsType; |
| typedef typename _OTraitsType::iterator_category _OIterCategory; |
| |
| return __adjacent_difference_switch(__begin, __end, __result, |
| __binary_op, |
| _IIteratorCategory(), |
| _OIterCategory()); |
| } |
| } // end namespace |
| } // end namespace |
| |
| #endif /* _GLIBCXX_NUMERIC_H */ |
