| // -*- C++ -*- |
| |
| // Copyright (C) 2007, 2008, 2009 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 <functional> |
| #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 |
| { |
| namespace __parallel |
| { |
| // Sequential fallback. |
| template<typename InputIterator, typename T> |
| inline T |
| accumulate(InputIterator begin, InputIterator end, T init, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::accumulate(begin, end, init); } |
| |
| template<typename InputIterator, typename T, typename BinaryOperation> |
| inline T |
| accumulate(InputIterator begin, InputIterator end, T init, |
| BinaryOperation binary_op, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::accumulate(begin, end, init, binary_op); } |
| |
| // Sequential fallback for input iterator case. |
| template<typename InputIterator, typename T, typename IteratorTag> |
| inline T |
| accumulate_switch(InputIterator begin, InputIterator end, |
| T init, IteratorTag) |
| { return accumulate(begin, end, init, __gnu_parallel::sequential_tag()); } |
| |
| template<typename InputIterator, typename T, typename BinaryOperation, |
| typename IteratorTag> |
| inline T |
| accumulate_switch(InputIterator begin, InputIterator end, T init, |
| BinaryOperation binary_op, IteratorTag) |
| { return accumulate(begin, end, init, binary_op, |
| __gnu_parallel::sequential_tag()); } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename _RandomAccessIterator, typename T, |
| typename BinaryOperation> |
| T |
| accumulate_switch(_RandomAccessIterator begin, _RandomAccessIterator end, |
| T 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::sequence_index_t>(end - begin) |
| >= __gnu_parallel::_Settings::get().accumulate_minimal_n |
| && __gnu_parallel::is_parallel(parallelism_tag))) |
| { |
| T res = init; |
| __gnu_parallel::accumulate_selector<_RandomAccessIterator> |
| 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 InputIterator, typename T> |
| inline T |
| accumulate(InputIterator begin, InputIterator end, T init, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef std::iterator_traits<InputIterator> iterator_traits; |
| typedef typename iterator_traits::value_type value_type; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| |
| return accumulate_switch(begin, end, init, |
| __gnu_parallel::plus<T, value_type>(), |
| iterator_category(), parallelism_tag); |
| } |
| |
| template<typename InputIterator, typename T> |
| inline T |
| accumulate(InputIterator begin, InputIterator end, T init) |
| { |
| typedef std::iterator_traits<InputIterator> iterator_traits; |
| typedef typename iterator_traits::value_type value_type; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| |
| return accumulate_switch(begin, end, init, |
| __gnu_parallel::plus<T, value_type>(), |
| iterator_category()); |
| } |
| |
| template<typename InputIterator, typename T, typename BinaryOperation> |
| inline T |
| accumulate(InputIterator begin, InputIterator end, T init, |
| BinaryOperation binary_op, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef iterator_traits<InputIterator> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| return accumulate_switch(begin, end, init, binary_op, |
| iterator_category(), parallelism_tag); |
| } |
| |
| template<typename InputIterator, typename T, typename BinaryOperation> |
| inline T |
| accumulate(InputIterator begin, InputIterator end, T init, |
| BinaryOperation binary_op) |
| { |
| typedef iterator_traits<InputIterator> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| return accumulate_switch(begin, end, init, binary_op, |
| iterator_category()); |
| } |
| |
| |
| // Sequential fallback. |
| template<typename InputIterator1, typename InputIterator2, typename T> |
| inline T |
| inner_product(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, T init, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init); } |
| |
| template<typename InputIterator1, typename InputIterator2, typename T, |
| typename BinaryFunction1, typename BinaryFunction2> |
| inline T |
| inner_product(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, T init, BinaryFunction1 binary_op1, |
| BinaryFunction2 binary_op2, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init, |
| binary_op1, binary_op2); } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename RandomAccessIterator1, typename RandomAccessIterator2, |
| typename T, typename BinaryFunction1, typename BinaryFunction2> |
| T |
| inner_product_switch(RandomAccessIterator1 first1, |
| RandomAccessIterator1 last1, |
| RandomAccessIterator2 first2, T 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))) |
| { |
| T res = init; |
| __gnu_parallel:: |
| inner_product_selector<RandomAccessIterator1, |
| RandomAccessIterator2, T> 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 InputIterator1, typename InputIterator2, typename T, |
| typename BinaryFunction1, typename BinaryFunction2, |
| typename IteratorTag1, typename IteratorTag2> |
| inline T |
| inner_product_switch(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, T 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 InputIterator1, typename InputIterator2, typename T, |
| typename BinaryFunction1, typename BinaryFunction2> |
| inline T |
| inner_product(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, T init, BinaryFunction1 binary_op1, |
| BinaryFunction2 binary_op2, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef iterator_traits<InputIterator1> traits1_type; |
| typedef typename traits1_type::iterator_category iterator1_category; |
| |
| typedef iterator_traits<InputIterator2> traits2_type; |
| typedef typename traits2_type::iterator_category iterator2_category; |
| |
| return inner_product_switch(first1, last1, first2, init, binary_op1, |
| binary_op2, iterator1_category(), |
| iterator2_category(), parallelism_tag); |
| } |
| |
| template<typename InputIterator1, typename InputIterator2, typename T, |
| typename BinaryFunction1, typename BinaryFunction2> |
| inline T |
| inner_product(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, T init, BinaryFunction1 binary_op1, |
| BinaryFunction2 binary_op2) |
| { |
| typedef iterator_traits<InputIterator1> traits1_type; |
| typedef typename traits1_type::iterator_category iterator1_category; |
| |
| typedef iterator_traits<InputIterator2> traits2_type; |
| typedef typename traits2_type::iterator_category iterator2_category; |
| |
| return inner_product_switch(first1, last1, first2, init, binary_op1, |
| binary_op2, iterator1_category(), |
| iterator2_category()); |
| } |
| |
| template<typename InputIterator1, typename InputIterator2, typename T> |
| inline T |
| inner_product(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, T init, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef iterator_traits<InputIterator1> traits_type1; |
| typedef typename traits_type1::value_type value_type1; |
| typedef iterator_traits<InputIterator2> traits_type2; |
| typedef typename traits_type2::value_type value_type2; |
| |
| typedef typename |
| __gnu_parallel::multiplies<value_type1, value_type2>::result |
| multiplies_result_type; |
| return inner_product(first1, last1, first2, init, |
| __gnu_parallel::plus<T, multiplies_result_type>(), |
| __gnu_parallel:: |
| multiplies<value_type1, value_type2>(), |
| parallelism_tag); |
| } |
| |
| template<typename InputIterator1, typename InputIterator2, typename T> |
| inline T |
| inner_product(InputIterator1 first1, InputIterator1 last1, |
| InputIterator2 first2, T init) |
| { |
| typedef iterator_traits<InputIterator1> traits_type1; |
| typedef typename traits_type1::value_type value_type1; |
| typedef iterator_traits<InputIterator2> traits_type2; |
| typedef typename traits_type2::value_type value_type2; |
| |
| typedef typename |
| __gnu_parallel::multiplies<value_type1, value_type2>::result |
| multiplies_result_type; |
| return inner_product(first1, last1, first2, init, |
| __gnu_parallel::plus<T, multiplies_result_type>(), |
| __gnu_parallel:: |
| multiplies<value_type1, value_type2>()); |
| } |
| |
| // Sequential fallback. |
| template<typename InputIterator, typename OutputIterator> |
| inline OutputIterator |
| partial_sum(InputIterator begin, InputIterator end, OutputIterator result, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::partial_sum(begin, end, result); } |
| |
| // Sequential fallback. |
| template<typename InputIterator, typename OutputIterator, |
| typename BinaryOperation> |
| inline OutputIterator |
| partial_sum(InputIterator begin, InputIterator end, OutputIterator result, |
| BinaryOperation bin_op, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); } |
| |
| // Sequential fallback for input iterator case. |
| template<typename InputIterator, typename OutputIterator, |
| typename BinaryOperation, typename IteratorTag1, |
| typename IteratorTag2> |
| inline OutputIterator |
| partial_sum_switch(InputIterator begin, InputIterator end, |
| OutputIterator result, BinaryOperation bin_op, |
| IteratorTag1, IteratorTag2) |
| { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename InputIterator, typename OutputIterator, |
| typename BinaryOperation> |
| OutputIterator |
| partial_sum_switch(InputIterator begin, InputIterator end, |
| OutputIterator result, BinaryOperation bin_op, |
| random_access_iterator_tag, random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(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 InputIterator, typename OutputIterator> |
| inline OutputIterator |
| partial_sum(InputIterator begin, InputIterator end, OutputIterator result) |
| { |
| typedef typename iterator_traits<InputIterator>::value_type value_type; |
| return partial_sum(begin, end, result, std::plus<value_type>()); |
| } |
| |
| // Public interface |
| template<typename InputIterator, typename OutputIterator, |
| typename BinaryOperation> |
| inline OutputIterator |
| partial_sum(InputIterator begin, InputIterator end, OutputIterator result, |
| BinaryOperation binary_op) |
| { |
| typedef iterator_traits<InputIterator> traitsi_type; |
| typedef typename traitsi_type::iterator_category iteratori_category; |
| |
| typedef iterator_traits<OutputIterator> traitso_type; |
| typedef typename traitso_type::iterator_category iteratoro_category; |
| |
| return partial_sum_switch(begin, end, result, binary_op, |
| iteratori_category(), iteratoro_category()); |
| } |
| |
| // Sequential fallback. |
| template<typename InputIterator, typename OutputIterator> |
| inline OutputIterator |
| adjacent_difference(InputIterator begin, InputIterator end, |
| OutputIterator result, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); } |
| |
| // Sequential fallback. |
| template<typename InputIterator, typename OutputIterator, |
| typename BinaryOperation> |
| inline OutputIterator |
| adjacent_difference(InputIterator begin, InputIterator end, |
| OutputIterator result, BinaryOperation bin_op, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op); } |
| |
| // Sequential fallback for input iterator case. |
| template<typename InputIterator, typename OutputIterator, |
| typename BinaryOperation, typename IteratorTag1, |
| typename IteratorTag2> |
| inline OutputIterator |
| adjacent_difference_switch(InputIterator begin, InputIterator 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 InputIterator, typename OutputIterator, |
| typename BinaryOperation> |
| OutputIterator |
| adjacent_difference_switch(InputIterator begin, InputIterator 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::sequence_index_t>(end - begin) |
| >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n |
| && __gnu_parallel::is_parallel(parallelism_tag))) |
| { |
| bool dummy = true; |
| typedef __gnu_parallel::iterator_pair<InputIterator, OutputIterator, |
| random_access_iterator_tag> ip; |
| *result = *begin; |
| ip begin_pair(begin + 1, result + 1), |
| end_pair(end, result + (end - begin)); |
| __gnu_parallel::adjacent_difference_selector<ip> functionality; |
| __gnu_parallel:: |
| for_each_template_random_access_ed(begin_pair, end_pair, bin_op, |
| functionality, |
| __gnu_parallel::dummy_reduct(), |
| dummy, dummy, -1); |
| return functionality.finish_iterator; |
| } |
| else |
| return adjacent_difference(begin, end, result, bin_op, |
| __gnu_parallel::sequential_tag()); |
| } |
| |
| // Public interface. |
| template<typename InputIterator, typename OutputIterator> |
| inline OutputIterator |
| adjacent_difference(InputIterator begin, InputIterator end, |
| OutputIterator result, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef iterator_traits<InputIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| return adjacent_difference(begin, end, result, std::minus<value_type>(), |
| parallelism_tag); |
| } |
| |
| template<typename InputIterator, typename OutputIterator> |
| inline OutputIterator |
| adjacent_difference(InputIterator begin, InputIterator end, |
| OutputIterator result) |
| { |
| typedef iterator_traits<InputIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| return adjacent_difference(begin, end, result, std::minus<value_type>()); |
| } |
| |
| template<typename InputIterator, typename OutputIterator, |
| typename BinaryOperation> |
| inline OutputIterator |
| adjacent_difference(InputIterator begin, InputIterator end, |
| OutputIterator result, BinaryOperation binary_op, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef iterator_traits<InputIterator> traitsi_type; |
| typedef typename traitsi_type::iterator_category iteratori_category; |
| |
| typedef iterator_traits<OutputIterator> traitso_type; |
| typedef typename traitso_type::iterator_category iteratoro_category; |
| |
| return adjacent_difference_switch(begin, end, result, binary_op, |
| iteratori_category(), |
| iteratoro_category(), parallelism_tag); |
| } |
| |
| template<typename InputIterator, typename OutputIterator, |
| typename BinaryOperation> |
| inline OutputIterator |
| adjacent_difference(InputIterator begin, InputIterator end, |
| OutputIterator result, BinaryOperation binary_op) |
| { |
| typedef iterator_traits<InputIterator> traitsi_type; |
| typedef typename traitsi_type::iterator_category iteratori_category; |
| |
| typedef iterator_traits<OutputIterator> traitso_type; |
| typedef typename traitso_type::iterator_category iteratoro_category; |
| |
| return adjacent_difference_switch(begin, end, result, binary_op, |
| iteratori_category(), |
| iteratoro_category()); |
| } |
| } // end namespace |
| } // end namespace |
| |
| #endif /* _GLIBCXX_NUMERIC_H */ |
