libstdc++-v3/include/parallel/numeric

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /**
  26  * @file parallel/numeric
  27 *
  28  * @brief Parallel STL function calls corresponding to stl_numeric.h.
  29  * The functions defined here mainly do case switches and
  30  * call the actual parallelized versions in other files.
  31  * Inlining policy: Functions that basically only contain one function call,
  32  * are declared inline.
  33  *  This file is a GNU parallel extension to the Standard C++ Library.
  34  */
  35
  36 // Written by Johannes Singler and Felix Putze.
  37
  38 #ifndef _GLIBCXX_PARALLEL_NUMERIC_H
  39 #define _GLIBCXX_PARALLEL_NUMERIC_H 1
  40
  41 #include <numeric>
  42 #include <functional>
  43 #include <parallel/numericfwd.h>
  44 #include <parallel/iterator.h>
  45 #include <parallel/for_each.h>
  46 #include <parallel/for_each_selectors.h>
  47 #include <parallel/partial_sum.h>
  48
  49 namespace std
  50 {
  51 namespace __parallel
  52 {
  53   // Sequential fallback.
  54   template<typename _IIter, typename _Tp>
  55     inline _Tp
  56     accumulate(_IIter __begin, _IIter __end, _Tp __init,
  57                __gnu_parallel::sequential_tag)
  58     { return _GLIBCXX_STD_P::accumulate(__begin, __end, __init); }
  59
  60   template<typename _IIter, typename _Tp, typename _BinaryOperation>
  61     inline _Tp
  62     accumulate(_IIter __begin, _IIter __end, _Tp __init,
  63                _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
  64     { return _GLIBCXX_STD_P::accumulate(__begin, __end, __init, __binary_op); }
  65
  66   // Sequential fallback for input iterator case.
  67   template<typename _IIter, typename _Tp, typename _IteratorTag>
  68     inline _Tp
  69     __accumulate_switch(_IIter __begin, _IIter __end,
  70                       _Tp __init, _IteratorTag)
  71     { return accumulate(__begin, __end, __init,
  72 __gnu_parallel::sequential_tag()); }
  73
  74   template<typename _IIter, typename _Tp, typename _BinaryOperation,
  75            typename _IteratorTag>
  76     inline _Tp
  77     __accumulate_switch(_IIter __begin, _IIter __end, _Tp __init,
  78                       _BinaryOperation __binary_op, _IteratorTag)
  79     { return accumulate(__begin, __end, __init, __binary_op,
  80                         __gnu_parallel::sequential_tag()); }
  81
  82   // Parallel algorithm for random access iterators.
  83   template<typename __RAIter, typename _Tp,
  84            typename _BinaryOperation>
  85     _Tp
  86     __accumulate_switch(__RAIter __begin, __RAIter __end,
  87                       _Tp __init, _BinaryOperation __binary_op,
  88                       random_access_iterator_tag,
  89                       __gnu_parallel::_Parallelism __parallelism_tag
  90                       = __gnu_parallel::parallel_unbalanced)
  91     {
  92       if (_GLIBCXX_PARALLEL_CONDITION(
  93             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  94             >= __gnu_parallel::_Settings::get().accumulate_minimal_n
  95             && __gnu_parallel::__is_parallel(__parallelism_tag)))
  96         {
  97           _Tp __res = __init;
  98           __gnu_parallel::__accumulate_selector<__RAIter>
  99             __my_selector;
 100           __gnu_parallel::
 101             __for_each_template_random_access_ed(__begin, __end,
 102                                             __gnu_parallel::_Nothing(),
 103                                             __my_selector,
 104                                             __gnu_parallel::
 105                                             __accumulate_binop_reduct
 106                                             <_BinaryOperation>(__binary_op),
 107                                             __res, __res, -1);
 108           return __res;
 109         }
 110       else
 111         return accumulate(__begin, __end, __init, __binary_op,
 112                           __gnu_parallel::sequential_tag());
 113     }
 114
 115   // Public interface.
 116   template<typename _IIter, typename _Tp>
 117     inline _Tp
 118     accumulate(_IIter __begin, _IIter __end, _Tp __init,
 119                __gnu_parallel::_Parallelism __parallelism_tag)
 120     {
 121       typedef std::iterator_traits<_IIter> _IteratorTraits;
 122       typedef typename _IteratorTraits::value_type _ValueType;
 123       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
 124
 125       return __accumulate_switch(__begin, __end, __init,
 126                                __gnu_parallel::_Plus<_Tp, _ValueType>(),
 127                                _IteratorCategory(), __parallelism_tag);
 128     }
 129
 130   template<typename _IIter, typename _Tp>
 131     inline _Tp
 132     accumulate(_IIter __begin, _IIter __end, _Tp __init)
 133     {
 134       typedef std::iterator_traits<_IIter> _IteratorTraits;
 135       typedef typename _IteratorTraits::value_type _ValueType;
 136       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
 137
 138       return __accumulate_switch(__begin, __end, __init,
 139                                __gnu_parallel::_Plus<_Tp, _ValueType>(),
 140                                _IteratorCategory());
 141     }
 142
 143   template<typename _IIter, typename _Tp, typename _BinaryOperation>
 144     inline _Tp
 145     accumulate(_IIter __begin, _IIter __end, _Tp __init,
 146                _BinaryOperation __binary_op,
 147                __gnu_parallel::_Parallelism __parallelism_tag)
 148     {
 149       typedef iterator_traits<_IIter> _IteratorTraits;
 150       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
 151       return __accumulate_switch(__begin, __end, __init, __binary_op,
 152                                _IteratorCategory(), __parallelism_tag);
 153     }
 154
 155   template<typename _IIter, typename _Tp, typename _BinaryOperation>
 156     inline _Tp
 157     accumulate(_IIter __begin, _IIter __end, _Tp __init,
 158                _BinaryOperation __binary_op)
 159     {
 160       typedef iterator_traits<_IIter> _IteratorTraits;
 161       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
 162       return __accumulate_switch(__begin, __end, __init, __binary_op,
 163                                _IteratorCategory());
 164     }
 165
 166
 167   // Sequential fallback.
 168   template<typename _IIter1, typename _IIter2, typename _Tp>
 169     inline _Tp
 170     inner_product(_IIter1 __first1, _IIter1 __last1,
 171                   _IIter2 __first2, _Tp __init,
 172                   __gnu_parallel::sequential_tag)
 173     { return _GLIBCXX_STD_P::inner_product(
 174                                __first1, __last1, __first2, __init); }
 175
 176   template<typename _IIter1, typename _IIter2, typename _Tp,
 177            typename _BinaryFunction1, typename _BinaryFunction2>
 178     inline _Tp
 179     inner_product(_IIter1 __first1, _IIter1 __last1,
 180                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
 181                   _BinaryFunction2 __binary_op2,
 182                   __gnu_parallel::sequential_tag)
 183     { return _GLIBCXX_STD_P::inner_product(__first1, __last1, __first2, __init,
 184                                            __binary_op1, __binary_op2); }
 185
 186   // Parallel algorithm for random access iterators.
 187   template<typename _RAIter1, typename _RAIter2,
 188            typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>
 189     _Tp
 190     __inner_product_switch(_RAIter1 __first1,
 191                          _RAIter1 __last1,
 192                          _RAIter2 __first2, _Tp __init,
 193                          _BinaryFunction1 __binary_op1,
 194                          _BinaryFunction2 __binary_op2,
 195                          random_access_iterator_tag,
 196                          random_access_iterator_tag,
 197                          __gnu_parallel::_Parallelism __parallelism_tag
 198                          = __gnu_parallel::parallel_unbalanced)
 199     {
 200       if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)
 201                                       >= __gnu_parallel::_Settings::get().
 202                                       accumulate_minimal_n
 203                                       && __gnu_parallel::
 204                                       __is_parallel(__parallelism_tag)))
 205         {
 206           _Tp __res = __init;
 207           __gnu_parallel::
 208             __inner_product_selector<_RAIter1,
 209             _RAIter2, _Tp> __my_selector(__first1, __first2);
 210           __gnu_parallel::
 211             __for_each_template_random_access_ed(
 212                 __first1, __last1, __binary_op2, __my_selector, __binary_op1,
 213                 __res, __res, -1);
 214           return __res;
 215         }
 216       else
 217         return inner_product(__first1, __last1, __first2, __init,
 218                              __gnu_parallel::sequential_tag());
 219     }
 220
 221   // No parallelism for input iterators.
 222   template<typename _IIter1, typename _IIter2, typename _Tp,
 223            typename _BinaryFunction1, typename _BinaryFunction2,
 224            typename _IteratorTag1, typename _IteratorTag2>
 225     inline _Tp
 226     __inner_product_switch(_IIter1 __first1, _IIter1 __last1,
 227                          _IIter2 __first2, _Tp __init,
 228                          _BinaryFunction1 __binary_op1,
 229                          _BinaryFunction2 __binary_op2,
 230                          _IteratorTag1, _IteratorTag2)
 231     { return inner_product(__first1, __last1, __first2, __init,
 232                            __binary_op1, __binary_op2,
 233                            __gnu_parallel::sequential_tag()); }
 234
 235   template<typename _IIter1, typename _IIter2, typename _Tp,
 236            typename _BinaryFunction1, typename _BinaryFunction2>
 237     inline _Tp
 238     inner_product(_IIter1 __first1, _IIter1 __last1,
 239                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
 240                   _BinaryFunction2 __binary_op2,
 241                   __gnu_parallel::_Parallelism __parallelism_tag)
 242     {
 243       typedef iterator_traits<_IIter1> _TraitsType1;
 244       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
 245
 246       typedef iterator_traits<_IIter2> _TraitsType2;
 247       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
 248
 249       return __inner_product_switch(
 250                __first1, __last1, __first2, __init, __binary_op1,
 251                __binary_op2, _IteratorCategory1(), _IteratorCategory2(),
 252                __parallelism_tag);
 253     }
 254
 255   template<typename _IIter1, typename _IIter2, typename _Tp,
 256            typename _BinaryFunction1, typename _BinaryFunction2>
 257     inline _Tp
 258     inner_product(_IIter1 __first1, _IIter1 __last1,
 259                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
 260                   _BinaryFunction2 __binary_op2)
 261     {
 262       typedef iterator_traits<_IIter1> _TraitsType1;
 263       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
 264
 265       typedef iterator_traits<_IIter2> _TraitsType2;
 266       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
 267
 268       return __inner_product_switch(
 269                __first1, __last1, __first2, __init, __binary_op1, __binary_op2,
 270                _IteratorCategory1(), _IteratorCategory2());
 271     }
 272
 273   template<typename _IIter1, typename _IIter2, typename _Tp>
 274     inline _Tp
 275     inner_product(_IIter1 __first1, _IIter1 __last1,
 276                   _IIter2 __first2, _Tp __init,
 277                   __gnu_parallel::_Parallelism __parallelism_tag)
 278     {
 279       typedef iterator_traits<_IIter1> _TraitsType1;
 280       typedef typename _TraitsType1::value_type _ValueType1;
 281       typedef iterator_traits<_IIter2> _TraitsType2;
 282       typedef typename _TraitsType2::value_type _ValueType2;
 283
 284       typedef typename
 285         __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::__result
 286         _MultipliesResultType;
 287       return inner_product(__first1, __last1, __first2, __init,
 288                            __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
 289                            __gnu_parallel::
 290                            _Multiplies<_ValueType1, _ValueType2>(),
 291                            __parallelism_tag);
 292     }
 293
 294   template<typename _IIter1, typename _IIter2, typename _Tp>
 295     inline _Tp
 296     inner_product(_IIter1 __first1, _IIter1 __last1,
 297                   _IIter2 __first2, _Tp __init)
 298     {
 299       typedef iterator_traits<_IIter1> _TraitsType1;
 300       typedef typename _TraitsType1::value_type _ValueType1;
 301       typedef iterator_traits<_IIter2> _TraitsType2;
 302       typedef typename _TraitsType2::value_type _ValueType2;
 303
 304       typedef typename
 305         __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::__result
 306         _MultipliesResultType;
 307       return inner_product(__first1, __last1, __first2, __init,
 308                            __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
 309                            __gnu_parallel::
 310                            _Multiplies<_ValueType1, _ValueType2>());
 311     }
 312
 313   // Sequential fallback.
 314   template<typename _IIter, typename _OutputIterator>
 315     inline _OutputIterator
 316     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
 317                 __gnu_parallel::sequential_tag)
 318     { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result); }
 319
 320   // Sequential fallback.
 321   template<typename _IIter, typename _OutputIterator,
 322            typename _BinaryOperation>
 323     inline _OutputIterator
 324     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
 325                 _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
 326     { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result, __bin_op); }
 327
 328   // Sequential fallback for input iterator case.
 329   template<typename _IIter, typename _OutputIterator,
 330            typename _BinaryOperation, typename _IteratorTag1,
 331            typename _IteratorTag2>
 332     inline _OutputIterator
 333     __partial_sum_switch(_IIter __begin, _IIter __end,
 334                        _OutputIterator __result, _BinaryOperation __bin_op,
 335                        _IteratorTag1, _IteratorTag2)
 336     { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result, __bin_op); }
 337
 338   // Parallel algorithm for random access iterators.
 339   template<typename _IIter, typename _OutputIterator,
 340            typename _BinaryOperation>
 341     _OutputIterator
 342     __partial_sum_switch(_IIter __begin, _IIter __end,
 343                        _OutputIterator __result, _BinaryOperation __bin_op,
 344                        random_access_iterator_tag, random_access_iterator_tag)
 345     {
 346       if (_GLIBCXX_PARALLEL_CONDITION(
 347             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
 348             >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
 349         return __gnu_parallel::__parallel_partial_sum(__begin, __end,
 350                                                     __result, __bin_op);
 351       else
 352         return partial_sum(__begin, __end, __result, __bin_op,
 353                            __gnu_parallel::sequential_tag());
 354     }
 355
 356   // Public interface.
 357   template<typename _IIter, typename _OutputIterator>
 358     inline _OutputIterator
 359     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result)
 360     {
 361       typedef typename iterator_traits<_IIter>::value_type _ValueType;
 362       return partial_sum(__begin, __end, __result, std::plus<_ValueType>());
 363     }
 364
 365   // Public interface
 366   template<typename _IIter, typename _OutputIterator,
 367            typename _BinaryOperation>
 368     inline _OutputIterator
 369     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
 370                 _BinaryOperation __binary_op)
 371     {
 372       typedef iterator_traits<_IIter> _ITraitsType;
 373       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
 374
 375       typedef iterator_traits<_OutputIterator> _OTraitsType;
 376       typedef typename _OTraitsType::iterator_category _OIterCategory;
 377
 378       return __partial_sum_switch(__begin, __end, __result, __binary_op,
 379                                 _IIteratorCategory(), _OIterCategory());
 380     }
 381
 382   // Sequential fallback.
 383   template<typename _IIter, typename _OutputIterator>
 384     inline _OutputIterator
 385     adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
 386                         __gnu_parallel::sequential_tag)
 387     { return _GLIBCXX_STD_P::adjacent_difference(__begin, __end, __result); }
 388
 389   // Sequential fallback.
 390   template<typename _IIter, typename _OutputIterator,
 391            typename _BinaryOperation>
 392     inline _OutputIterator
 393     adjacent_difference(_IIter __begin, _IIter __end,
 394                         _OutputIterator __result, _BinaryOperation __bin_op,
 395                         __gnu_parallel::sequential_tag)
 396     { return _GLIBCXX_STD_P::adjacent_difference(
 397                                __begin, __end, __result, __bin_op); }
 398
 399   // Sequential fallback for input iterator case.
 400   template<typename _IIter, typename _OutputIterator,
 401            typename _BinaryOperation, typename _IteratorTag1,
 402            typename _IteratorTag2>
 403     inline _OutputIterator
 404     __adjacent_difference_switch(
 405       _IIter __begin, _IIter __end, _OutputIterator __result,
 406       _BinaryOperation __bin_op, _IteratorTag1, _IteratorTag2)
 407     { return adjacent_difference(__begin, __end, __result, __bin_op,
 408                                  __gnu_parallel::sequential_tag()); }
 409
 410   // Parallel algorithm for random access iterators.
 411   template<typename _IIter, typename _OutputIterator,
 412            typename _BinaryOperation>
 413     _OutputIterator
 414     __adjacent_difference_switch(
 415       _IIter __begin, _IIter __end, _OutputIterator __result,
 416       _BinaryOperation __bin_op,
 417       random_access_iterator_tag, random_access_iterator_tag,
 418       __gnu_parallel::_Parallelism __parallelism_tag
 419                                = __gnu_parallel::parallel_balanced)
 420     {
 421       if (_GLIBCXX_PARALLEL_CONDITION(
 422             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
 423             >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
 424             && __gnu_parallel::__is_parallel(__parallelism_tag)))
 425         {
 426           bool __dummy = true;
 427           typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,
 428             random_access_iterator_tag> _ItTrip;
 429           *__result = *__begin;
 430           _ItTrip __begin_pair(__begin + 1, __result + 1),
 431             __end_pair(__end, __result + (__end - __begin));
 432           __gnu_parallel::__adjacent_difference_selector<_ItTrip>
 433                                                             __functionality;
 434           __gnu_parallel::
 435             __for_each_template_random_access_ed(
 436                 __begin_pair, __end_pair, __bin_op, __functionality,
 437                 __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);
 438           return __functionality.finish_iterator;
 439         }
 440       else
 441         return adjacent_difference(__begin, __end, __result, __bin_op,
 442                                    __gnu_parallel::sequential_tag());
 443     }
 444
 445   // Public interface.
 446   template<typename _IIter, typename _OutputIterator>
 447     inline _OutputIterator
 448     adjacent_difference(_IIter __begin, _IIter __end,
 449                         _OutputIterator __result,
 450                         __gnu_parallel::_Parallelism __parallelism_tag)
 451     {
 452       typedef iterator_traits<_IIter> _TraitsType;
 453       typedef typename _TraitsType::value_type _ValueType;
 454       return adjacent_difference(
 455                __begin, __end, __result, std::minus<_ValueType>(),
 456                __parallelism_tag);
 457     }
 458
 459   template<typename _IIter, typename _OutputIterator>
 460     inline _OutputIterator
 461     adjacent_difference(_IIter __begin, _IIter __end,
 462                         _OutputIterator __result)
 463     {
 464       typedef iterator_traits<_IIter> _TraitsType;
 465       typedef typename _TraitsType::value_type _ValueType;
 466       return adjacent_difference(__begin, __end, __result,
 467                                  std::minus<_ValueType>());
 468     }
 469
 470   template<typename _IIter, typename _OutputIterator,
 471            typename _BinaryOperation>
 472     inline _OutputIterator
 473     adjacent_difference(_IIter __begin, _IIter __end,
 474                         _OutputIterator __result, _BinaryOperation __binary_op,
 475                         __gnu_parallel::_Parallelism __parallelism_tag)
 476     {
 477       typedef iterator_traits<_IIter> _ITraitsType;
 478       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
 479
 480       typedef iterator_traits<_OutputIterator> _OTraitsType;
 481       typedef typename _OTraitsType::iterator_category _OIterCategory;
 482
 483       return __adjacent_difference_switch(
 484                __begin, __end, __result, __binary_op,
 485                _IIteratorCategory(), _OIterCategory(), __parallelism_tag);
 486     }
 487
 488   template<typename _IIter, typename _OutputIterator,
 489            typename _BinaryOperation>
 490     inline _OutputIterator
 491     adjacent_difference(_IIter __begin, _IIter __end,
 492                         _OutputIterator __result, _BinaryOperation __binary_op)
 493     {
 494       typedef iterator_traits<_IIter> _ITraitsType;
 495       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
 496
 497       typedef iterator_traits<_OutputIterator> _OTraitsType;
 498       typedef typename _OTraitsType::iterator_category _OIterCategory;
 499
 500       return __adjacent_difference_switch(
 501                __begin, __end, __result, __binary_op,
 502                _IIteratorCategory(), _OIterCategory());
 503     }
 504 } // end namespace
 505 } // end namespace
 506
 507 #endif /* _GLIBCXX_NUMERIC_H */