--- /dev/null
+// -*- 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 */
projects / cross.git / blobdiff