libstdc++
parallel/numeric
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /**
00026  * @file parallel/numeric
00027 *
00028  * @brief Parallel STL function calls corresponding to stl_numeric.h.
00029  * The functions defined here mainly do case switches and
00030  * call the actual parallelized versions in other files.
00031  * Inlining policy: Functions that basically only contain one function call,
00032  * are declared inline.
00033  *  This file is a GNU parallel extension to the Standard C++ Library.
00034  */
00035 
00036 // Written by Johannes Singler and Felix Putze.
00037 
00038 #ifndef _GLIBCXX_PARALLEL_NUMERIC_H
00039 #define _GLIBCXX_PARALLEL_NUMERIC_H 1
00040 
00041 #include <numeric>
00042 #include <bits/stl_function.h>
00043 #include <parallel/numericfwd.h>
00044 #include <parallel/iterator.h>
00045 #include <parallel/for_each.h>
00046 #include <parallel/for_each_selectors.h>
00047 #include <parallel/partial_sum.h>
00048 
00049 namespace std _GLIBCXX_VISIBILITY(default)
00050 {
00051 namespace __parallel
00052 {
00053   // Sequential fallback.
00054   template<typename _IIter, typename _Tp>
00055     inline _Tp
00056     accumulate(_IIter __begin, _IIter __end, _Tp __init, 
00057                __gnu_parallel::sequential_tag)
00058     { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init); }
00059 
00060   template<typename _IIter, typename _Tp, typename _BinaryOperation>
00061     inline _Tp
00062     accumulate(_IIter __begin, _IIter __end, _Tp __init,
00063                _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
00064     { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init, __binary_op); }
00065 
00066   // Sequential fallback for input iterator case.
00067   template<typename _IIter, typename _Tp, typename _IteratorTag>
00068     inline _Tp
00069     __accumulate_switch(_IIter __begin, _IIter __end,
00070                       _Tp __init, _IteratorTag) 
00071     { return accumulate(__begin, __end, __init,
00072             __gnu_parallel::sequential_tag()); }
00073 
00074   template<typename _IIter, typename _Tp, typename _BinaryOperation,
00075            typename _IteratorTag>
00076     inline _Tp
00077     __accumulate_switch(_IIter __begin, _IIter __end, _Tp __init, 
00078                       _BinaryOperation __binary_op, _IteratorTag)
00079     { return accumulate(__begin, __end, __init, __binary_op, 
00080                         __gnu_parallel::sequential_tag()); }
00081 
00082   // Parallel algorithm for random access iterators.
00083   template<typename __RAIter, typename _Tp, typename _BinaryOperation>
00084     _Tp
00085     __accumulate_switch(__RAIter __begin, __RAIter __end, 
00086                       _Tp __init, _BinaryOperation __binary_op, 
00087                       random_access_iterator_tag, 
00088                       __gnu_parallel::_Parallelism __parallelism_tag  
00089                       = __gnu_parallel::parallel_unbalanced)
00090     {
00091       if (_GLIBCXX_PARALLEL_CONDITION(
00092             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
00093             >= __gnu_parallel::_Settings::get().accumulate_minimal_n
00094             && __gnu_parallel::__is_parallel(__parallelism_tag)))
00095         {
00096           _Tp __res = __init;
00097           __gnu_parallel::__accumulate_selector<__RAIter>
00098             __my_selector;
00099           __gnu_parallel::
00100             __for_each_template_random_access_ed(__begin, __end,
00101                          __gnu_parallel::_Nothing(),
00102                          __my_selector,
00103                          __gnu_parallel::
00104                          __accumulate_binop_reduct
00105                            <_BinaryOperation>(__binary_op),
00106                          __res, __res, -1);
00107           return __res;
00108         }
00109       else
00110         return accumulate(__begin, __end, __init, __binary_op, 
00111                           __gnu_parallel::sequential_tag());
00112     }
00113 
00114   // Public interface.
00115   template<typename _IIter, typename _Tp>
00116     inline _Tp
00117     accumulate(_IIter __begin, _IIter __end, _Tp __init, 
00118                __gnu_parallel::_Parallelism __parallelism_tag)
00119     {
00120       typedef std::iterator_traits<_IIter> _IteratorTraits;
00121       typedef typename _IteratorTraits::value_type _ValueType;
00122       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00123 
00124       return __accumulate_switch(__begin, __end, __init,
00125                  __gnu_parallel::_Plus<_Tp, _ValueType>(),
00126                  _IteratorCategory(), __parallelism_tag);
00127     }
00128 
00129   template<typename _IIter, typename _Tp>
00130     inline _Tp
00131     accumulate(_IIter __begin, _IIter __end, _Tp __init)
00132     {
00133       typedef std::iterator_traits<_IIter> _IteratorTraits;
00134       typedef typename _IteratorTraits::value_type _ValueType;
00135       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00136 
00137       return __accumulate_switch(__begin, __end, __init,
00138                  __gnu_parallel::_Plus<_Tp, _ValueType>(),
00139                  _IteratorCategory());
00140     }
00141 
00142   template<typename _IIter, typename _Tp, typename _BinaryOperation>
00143     inline _Tp
00144     accumulate(_IIter __begin, _IIter __end, _Tp __init, 
00145                _BinaryOperation __binary_op, 
00146                __gnu_parallel::_Parallelism __parallelism_tag)
00147     {
00148       typedef iterator_traits<_IIter> _IteratorTraits;
00149       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00150       return __accumulate_switch(__begin, __end, __init, __binary_op, 
00151                  _IteratorCategory(), __parallelism_tag);
00152     }
00153 
00154   template<typename _IIter, typename _Tp, typename _BinaryOperation>
00155     inline _Tp
00156     accumulate(_IIter __begin, _IIter __end, _Tp __init, 
00157                _BinaryOperation __binary_op) 
00158     {
00159       typedef iterator_traits<_IIter> _IteratorTraits;
00160       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00161       return __accumulate_switch(__begin, __end, __init, __binary_op, 
00162                  _IteratorCategory());
00163     }
00164 
00165 
00166   // Sequential fallback.
00167   template<typename _IIter1, typename _IIter2, typename _Tp>
00168     inline _Tp
00169     inner_product(_IIter1 __first1, _IIter1 __last1, 
00170                   _IIter2 __first2, _Tp __init,
00171                   __gnu_parallel::sequential_tag)
00172     { return _GLIBCXX_STD_A::inner_product(
00173                                __first1, __last1, __first2, __init); }
00174 
00175   template<typename _IIter1, typename _IIter2, typename _Tp,
00176            typename _BinaryFunction1, typename _BinaryFunction2>
00177     inline _Tp
00178     inner_product(_IIter1 __first1, _IIter1 __last1,
00179                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 
00180                   _BinaryFunction2 __binary_op2,
00181                   __gnu_parallel::sequential_tag)
00182     { return _GLIBCXX_STD_A::inner_product(__first1, __last1, __first2, __init,
00183                                            __binary_op1, __binary_op2); }
00184 
00185   // Parallel algorithm for random access iterators.
00186   template<typename _RAIter1, typename _RAIter2,
00187            typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>
00188     _Tp
00189     __inner_product_switch(_RAIter1 __first1,
00190                _RAIter1 __last1,
00191                _RAIter2 __first2, _Tp __init,
00192                _BinaryFunction1 __binary_op1,
00193                _BinaryFunction2 __binary_op2,
00194                random_access_iterator_tag,
00195                random_access_iterator_tag,
00196                __gnu_parallel::_Parallelism __parallelism_tag
00197                = __gnu_parallel::parallel_unbalanced)
00198     {
00199       if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)
00200                                       >= __gnu_parallel::_Settings::get().
00201                                       accumulate_minimal_n
00202                                       && __gnu_parallel::
00203                                       __is_parallel(__parallelism_tag)))
00204         {
00205           _Tp __res = __init;
00206           __gnu_parallel::
00207             __inner_product_selector<_RAIter1,
00208             _RAIter2, _Tp> __my_selector(__first1, __first2);
00209           __gnu_parallel::
00210             __for_each_template_random_access_ed(
00211                 __first1, __last1, __binary_op2, __my_selector, __binary_op1,
00212                 __res, __res, -1);
00213           return __res;
00214         }
00215       else
00216         return inner_product(__first1, __last1, __first2, __init, 
00217                              __gnu_parallel::sequential_tag());
00218     }
00219 
00220   // No parallelism for input iterators.
00221   template<typename _IIter1, typename _IIter2, typename _Tp,
00222            typename _BinaryFunction1, typename _BinaryFunction2,
00223            typename _IteratorTag1, typename _IteratorTag2>
00224     inline _Tp
00225     __inner_product_switch(_IIter1 __first1, _IIter1 __last1, 
00226                _IIter2 __first2, _Tp __init, 
00227                _BinaryFunction1 __binary_op1,
00228                _BinaryFunction2 __binary_op2, 
00229                _IteratorTag1, _IteratorTag2)
00230     { return inner_product(__first1, __last1, __first2, __init, __binary_op1,
00231                __binary_op2, __gnu_parallel::sequential_tag()); }
00232 
00233   template<typename _IIter1, typename _IIter2, typename _Tp,
00234            typename _BinaryFunction1, typename _BinaryFunction2>
00235     inline _Tp
00236     inner_product(_IIter1 __first1, _IIter1 __last1, 
00237                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 
00238                   _BinaryFunction2 __binary_op2, 
00239                   __gnu_parallel::_Parallelism __parallelism_tag)
00240     {
00241       typedef iterator_traits<_IIter1> _TraitsType1;
00242       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00243 
00244       typedef iterator_traits<_IIter2> _TraitsType2;
00245       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00246 
00247       return __inner_product_switch(__first1, __last1, __first2, __init,
00248                     __binary_op1, __binary_op2,
00249                     _IteratorCategory1(), _IteratorCategory2(),
00250                     __parallelism_tag);
00251     }
00252 
00253   template<typename _IIter1, typename _IIter2, typename _Tp,
00254            typename _BinaryFunction1, typename _BinaryFunction2>
00255     inline _Tp
00256     inner_product(_IIter1 __first1, _IIter1 __last1, 
00257                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 
00258                   _BinaryFunction2 __binary_op2)
00259     {
00260       typedef iterator_traits<_IIter1> _TraitsType1;
00261       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00262 
00263       typedef iterator_traits<_IIter2> _TraitsType2;
00264       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00265 
00266       return __inner_product_switch(__first1, __last1, __first2, __init,
00267                     __binary_op1, __binary_op2,
00268                     _IteratorCategory1(),
00269                     _IteratorCategory2());
00270     }
00271 
00272   template<typename _IIter1, typename _IIter2, typename _Tp>
00273     inline _Tp
00274     inner_product(_IIter1 __first1, _IIter1 __last1, 
00275                   _IIter2 __first2, _Tp __init, 
00276                   __gnu_parallel::_Parallelism __parallelism_tag)
00277     {
00278       typedef iterator_traits<_IIter1> _TraitsType1;
00279       typedef typename _TraitsType1::value_type _ValueType1;
00280       typedef iterator_traits<_IIter2> _TraitsType2;
00281       typedef typename _TraitsType2::value_type _ValueType2;
00282 
00283       typedef typename
00284         __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
00285         _MultipliesResultType;
00286       return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
00287                            __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
00288                            __gnu_parallel::
00289                            _Multiplies<_ValueType1, _ValueType2>(),
00290                            __parallelism_tag);
00291     }
00292 
00293   template<typename _IIter1, typename _IIter2, typename _Tp>
00294     inline _Tp
00295     inner_product(_IIter1 __first1, _IIter1 __last1, 
00296                   _IIter2 __first2, _Tp __init)
00297     {
00298       typedef iterator_traits<_IIter1> _TraitsType1;
00299       typedef typename _TraitsType1::value_type _ValueType1;
00300       typedef iterator_traits<_IIter2> _TraitsType2;
00301       typedef typename _TraitsType2::value_type _ValueType2;
00302 
00303       typedef typename
00304         __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
00305         _MultipliesResultType;
00306       return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
00307                            __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
00308                            __gnu_parallel::
00309                            _Multiplies<_ValueType1, _ValueType2>());
00310     }
00311 
00312   // Sequential fallback.
00313   template<typename _IIter, typename _OutputIterator>
00314     inline _OutputIterator
00315     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
00316                 __gnu_parallel::sequential_tag)
00317     { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); }
00318 
00319   // Sequential fallback.
00320   template<typename _IIter, typename _OutputIterator,
00321        typename _BinaryOperation>
00322     inline _OutputIterator
00323     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
00324                 _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
00325     { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
00326 
00327   // Sequential fallback for input iterator case.
00328   template<typename _IIter, typename _OutputIterator,
00329            typename _BinaryOperation, typename _IteratorTag1,
00330            typename _IteratorTag2>
00331     inline _OutputIterator
00332     __partial_sum_switch(_IIter __begin, _IIter __end,
00333              _OutputIterator __result, _BinaryOperation __bin_op,
00334              _IteratorTag1, _IteratorTag2)
00335     { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
00336 
00337   // Parallel algorithm for random access iterators.
00338   template<typename _IIter, typename _OutputIterator,
00339            typename _BinaryOperation>
00340     _OutputIterator
00341     __partial_sum_switch(_IIter __begin, _IIter __end,
00342              _OutputIterator __result, _BinaryOperation __bin_op,
00343              random_access_iterator_tag,
00344              random_access_iterator_tag)
00345     {
00346       if (_GLIBCXX_PARALLEL_CONDITION(
00347             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
00348             >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
00349         return __gnu_parallel::__parallel_partial_sum(__begin, __end,
00350                               __result, __bin_op);
00351       else
00352         return partial_sum(__begin, __end, __result, __bin_op,
00353                            __gnu_parallel::sequential_tag());
00354     }
00355 
00356   // Public interface.
00357   template<typename _IIter, typename _OutputIterator>
00358     inline _OutputIterator
00359     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result)
00360     {
00361       typedef typename iterator_traits<_IIter>::value_type _ValueType;
00362       return __gnu_parallel::partial_sum(__begin, __end,
00363                                          __result, std::plus<_ValueType>());
00364     }
00365 
00366   // Public interface
00367   template<typename _IIter, typename _OutputIterator,
00368            typename _BinaryOperation>
00369     inline _OutputIterator
00370     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
00371                 _BinaryOperation __binary_op)
00372     {
00373       typedef iterator_traits<_IIter> _ITraitsType;
00374       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
00375 
00376       typedef iterator_traits<_OutputIterator> _OTraitsType;
00377       typedef typename _OTraitsType::iterator_category _OIterCategory;
00378 
00379       return __partial_sum_switch(__begin, __end, __result, __binary_op,
00380                   _IIteratorCategory(), _OIterCategory());
00381     }
00382 
00383   // Sequential fallback.
00384   template<typename _IIter, typename _OutputIterator>
00385     inline _OutputIterator
00386     adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
00387                         __gnu_parallel::sequential_tag)
00388     { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); }
00389 
00390   // Sequential fallback.
00391   template<typename _IIter, typename _OutputIterator,
00392            typename _BinaryOperation>
00393     inline _OutputIterator
00394     adjacent_difference(_IIter __begin, _IIter __end,
00395                         _OutputIterator __result, _BinaryOperation __bin_op,
00396                         __gnu_parallel::sequential_tag)
00397     { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end,
00398                          __result, __bin_op); }
00399 
00400   // Sequential fallback for input iterator case.
00401   template<typename _IIter, typename _OutputIterator,
00402            typename _BinaryOperation, typename _IteratorTag1,
00403            typename _IteratorTag2>
00404     inline _OutputIterator
00405     __adjacent_difference_switch(_IIter __begin, _IIter __end,
00406                  _OutputIterator __result,
00407                  _BinaryOperation __bin_op, _IteratorTag1,
00408                  _IteratorTag2)
00409     { return adjacent_difference(__begin, __end, __result, __bin_op,
00410                                  __gnu_parallel::sequential_tag()); }
00411 
00412   // Parallel algorithm for random access iterators.
00413   template<typename _IIter, typename _OutputIterator,
00414            typename _BinaryOperation>
00415     _OutputIterator
00416     __adjacent_difference_switch(_IIter __begin, _IIter __end,
00417                  _OutputIterator __result,
00418                  _BinaryOperation __bin_op,
00419                  random_access_iterator_tag,
00420                  random_access_iterator_tag,
00421                  __gnu_parallel::_Parallelism
00422                  __parallelism_tag
00423                  = __gnu_parallel::parallel_balanced)
00424     {
00425       if (_GLIBCXX_PARALLEL_CONDITION(
00426             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
00427             >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
00428             && __gnu_parallel::__is_parallel(__parallelism_tag)))
00429         {
00430           bool __dummy = true;
00431           typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,
00432             random_access_iterator_tag> _ItTrip;
00433           *__result = *__begin;
00434           _ItTrip __begin_pair(__begin + 1, __result + 1),
00435             __end_pair(__end, __result + (__end - __begin));
00436           __gnu_parallel::__adjacent_difference_selector<_ItTrip>
00437                                                             __functionality;
00438           __gnu_parallel::
00439             __for_each_template_random_access_ed(
00440                 __begin_pair, __end_pair, __bin_op, __functionality,
00441                 __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);
00442           return __functionality._M_finish_iterator;
00443         }
00444       else
00445         return adjacent_difference(__begin, __end, __result, __bin_op, 
00446                                    __gnu_parallel::sequential_tag());
00447     }
00448 
00449   // Public interface.
00450   template<typename _IIter, typename _OutputIterator>
00451     inline _OutputIterator
00452     adjacent_difference(_IIter __begin, _IIter __end,
00453                         _OutputIterator __result,
00454                         __gnu_parallel::_Parallelism __parallelism_tag)
00455     {
00456       typedef iterator_traits<_IIter> _TraitsType;
00457       typedef typename _TraitsType::value_type _ValueType;
00458       return adjacent_difference(__begin, __end, __result,
00459                  std::minus<_ValueType>(),
00460                  __parallelism_tag);
00461     }
00462 
00463   template<typename _IIter, typename _OutputIterator>
00464     inline _OutputIterator
00465     adjacent_difference(_IIter __begin, _IIter __end,
00466                         _OutputIterator __result)
00467     {
00468       typedef iterator_traits<_IIter> _TraitsType;
00469       typedef typename _TraitsType::value_type _ValueType;
00470       return adjacent_difference(__begin, __end, __result,
00471                  std::minus<_ValueType>());
00472     }
00473 
00474   template<typename _IIter, typename _OutputIterator,
00475            typename _BinaryOperation>
00476     inline _OutputIterator
00477     adjacent_difference(_IIter __begin, _IIter __end,
00478                         _OutputIterator __result, _BinaryOperation __binary_op,
00479                         __gnu_parallel::_Parallelism __parallelism_tag)
00480     {
00481       typedef iterator_traits<_IIter> _ITraitsType;
00482       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
00483 
00484       typedef iterator_traits<_OutputIterator> _OTraitsType;
00485       typedef typename _OTraitsType::iterator_category _OIterCategory;
00486 
00487       return __adjacent_difference_switch(__begin, __end, __result,
00488                       __binary_op,
00489                       _IIteratorCategory(),
00490                       _OIterCategory(),
00491                       __parallelism_tag);
00492     }
00493 
00494   template<typename _IIter, typename _OutputIterator,
00495        typename _BinaryOperation>
00496     inline _OutputIterator
00497     adjacent_difference(_IIter __begin, _IIter __end,
00498             _OutputIterator __result, _BinaryOperation __binary_op)
00499     {
00500       typedef iterator_traits<_IIter> _ITraitsType;
00501       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
00502 
00503       typedef iterator_traits<_OutputIterator> _OTraitsType;
00504       typedef typename _OTraitsType::iterator_category _OIterCategory;
00505 
00506       return __adjacent_difference_switch(__begin, __end, __result,
00507                       __binary_op,
00508                       _IIteratorCategory(),
00509                       _OIterCategory());
00510     }
00511 } // end namespace
00512 } // end namespace
00513 
00514 #endif /* _GLIBCXX_NUMERIC_H */