| // -*- C++ -*- | |
| // Copyright (C) 2007-2023 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) | |
| { | |
| 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) | |
| { | |
| 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) | |
| { | |
| 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 */ |