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 <bits/stl_function.h>
  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, typename _BinaryOperation>
  84     _Tp
  85     __accumulate_switch(__RAIter __begin, __RAIter __end,
  86                       _Tp __init, _BinaryOperation __binary_op,
  87                       random_access_iterator_tag,
  88                       __gnu_parallel::_Parallelism __parallelism_tag
  89                       = __gnu_parallel::parallel_unbalanced)
  90     {
  91       if (_GLIBCXX_PARALLEL_CONDITION(
  92             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  93             >= __gnu_parallel::_Settings::get().accumulate_minimal_n
  94             && __gnu_parallel::__is_parallel(__parallelism_tag)))
  95         {
  96           _Tp __res = __init;
  97           __gnu_parallel::__accumulate_selector<__RAIter>
  98             __my_selector;
  99           __gnu_parallel::
 100             __for_each_template_random_access_ed(__begin, __end,
 101                                                  __gnu_parallel::_Nothing(),
 102                                                  __my_selector,
 103                                                  __gnu_parallel::
 104                                                  __accumulate_binop_reduct
 105                                                <_BinaryOperation>(__binary_op),
 106                                                  __res, __res, -1);
 107           return __res;
 108         }
 109       else
 110         return accumulate(__begin, __end, __init, __binary_op,
 111                           __gnu_parallel::sequential_tag());
 112     }
 113
 114   // Public interface.
 115   template<typename _IIter, typename _Tp>
 116     inline _Tp
 117     accumulate(_IIter __begin, _IIter __end, _Tp __init,
 118                __gnu_parallel::_Parallelism __parallelism_tag)
 119     {
 120       typedef std::iterator_traits<_IIter> _IteratorTraits;
 121       typedef typename _IteratorTraits::value_type _ValueType;
 122       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
 123
 124       return __accumulate_switch(__begin, __end, __init,
 125                                  __gnu_parallel::_Plus<_Tp, _ValueType>(),
 126                                  _IteratorCategory(), __parallelism_tag);
 127     }
 128
 129   template<typename _IIter, typename _Tp>
 130     inline _Tp
 131     accumulate(_IIter __begin, _IIter __end, _Tp __init)
 132     {
 133       typedef std::iterator_traits<_IIter> _IteratorTraits;
 134       typedef typename _IteratorTraits::value_type _ValueType;
 135       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
 136
 137       return __accumulate_switch(__begin, __end, __init,
 138                                  __gnu_parallel::_Plus<_Tp, _ValueType>(),
 139                                  _IteratorCategory());
 140     }
 141
 142   template<typename _IIter, typename _Tp, typename _BinaryOperation>
 143     inline _Tp
 144     accumulate(_IIter __begin, _IIter __end, _Tp __init,
 145                _BinaryOperation __binary_op,
 146                __gnu_parallel::_Parallelism __parallelism_tag)
 147     {
 148       typedef iterator_traits<_IIter> _IteratorTraits;
 149       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
 150       return __accumulate_switch(__begin, __end, __init, __binary_op,
 151                                  _IteratorCategory(), __parallelism_tag);
 152     }
 153
 154   template<typename _IIter, typename _Tp, typename _BinaryOperation>
 155     inline _Tp
 156     accumulate(_IIter __begin, _IIter __end, _Tp __init,
 157                _BinaryOperation __binary_op)
 158     {
 159       typedef iterator_traits<_IIter> _IteratorTraits;
 160       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
 161       return __accumulate_switch(__begin, __end, __init, __binary_op,
 162                                  _IteratorCategory());
 163     }
 164
 165
 166   // Sequential fallback.
 167   template<typename _IIter1, typename _IIter2, typename _Tp>
 168     inline _Tp
 169     inner_product(_IIter1 __first1, _IIter1 __last1,
 170                   _IIter2 __first2, _Tp __init,
 171                   __gnu_parallel::sequential_tag)
 172     { return _GLIBCXX_STD_P::inner_product(
 173                                __first1, __last1, __first2, __init); }
 174
 175   template<typename _IIter1, typename _IIter2, typename _Tp,
 176            typename _BinaryFunction1, typename _BinaryFunction2>
 177     inline _Tp
 178     inner_product(_IIter1 __first1, _IIter1 __last1,
 179                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
 180                   _BinaryFunction2 __binary_op2,
 181                   __gnu_parallel::sequential_tag)
 182     { return _GLIBCXX_STD_P::inner_product(__first1, __last1, __first2, __init,
 183                                            __binary_op1, __binary_op2); }
 184
 185   // Parallel algorithm for random access iterators.
 186   template<typename _RAIter1, typename _RAIter2,
 187            typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>
 188     _Tp
 189     __inner_product_switch(_RAIter1 __first1,
 190                            _RAIter1 __last1,
 191                            _RAIter2 __first2, _Tp __init,
 192                            _BinaryFunction1 __binary_op1,
 193                            _BinaryFunction2 __binary_op2,
 194                            random_access_iterator_tag,
 195                            random_access_iterator_tag,
 196                            __gnu_parallel::_Parallelism __parallelism_tag
 197                            = __gnu_parallel::parallel_unbalanced)
 198     {
 199       if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)
 200                                       >= __gnu_parallel::_Settings::get().
 201                                       accumulate_minimal_n
 202                                       && __gnu_parallel::
 203                                       __is_parallel(__parallelism_tag)))
 204         {
 205           _Tp __res = __init;
 206           __gnu_parallel::
 207             __inner_product_selector<_RAIter1,
 208             _RAIter2, _Tp> __my_selector(__first1, __first2);
 209           __gnu_parallel::
 210             __for_each_template_random_access_ed(
 211                 __first1, __last1, __binary_op2, __my_selector, __binary_op1,
 212                 __res, __res, -1);
 213           return __res;
 214         }
 215       else
 216         return inner_product(__first1, __last1, __first2, __init,
 217                              __gnu_parallel::sequential_tag());
 218     }
 219
 220   // No parallelism for input iterators.
 221   template<typename _IIter1, typename _IIter2, typename _Tp,
 222            typename _BinaryFunction1, typename _BinaryFunction2,
 223            typename _IteratorTag1, typename _IteratorTag2>
 224     inline _Tp
 225     __inner_product_switch(_IIter1 __first1, _IIter1 __last1,
 226                            _IIter2 __first2, _Tp __init,
 227                            _BinaryFunction1 __binary_op1,
 228                            _BinaryFunction2 __binary_op2,
 229                            _IteratorTag1, _IteratorTag2)
 230     { return inner_product(__first1, __last1, __first2, __init, __binary_op1,
 231                            __binary_op2, __gnu_parallel::sequential_tag()); }
 232
 233   template<typename _IIter1, typename _IIter2, typename _Tp,
 234            typename _BinaryFunction1, typename _BinaryFunction2>
 235     inline _Tp
 236     inner_product(_IIter1 __first1, _IIter1 __last1,
 237                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
 238                   _BinaryFunction2 __binary_op2,
 239                   __gnu_parallel::_Parallelism __parallelism_tag)
 240     {
 241       typedef iterator_traits<_IIter1> _TraitsType1;
 242       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
 243
 244       typedef iterator_traits<_IIter2> _TraitsType2;
 245       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
 246
 247       return __inner_product_switch(__first1, __last1, __first2, __init,
 248                                     __binary_op1, __binary_op2,
 249                                     _IteratorCategory1(), _IteratorCategory2(),
 250                                     __parallelism_tag);
 251     }
 252
 253   template<typename _IIter1, typename _IIter2, typename _Tp,
 254            typename _BinaryFunction1, typename _BinaryFunction2>
 255     inline _Tp
 256     inner_product(_IIter1 __first1, _IIter1 __last1,
 257                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
 258                   _BinaryFunction2 __binary_op2)
 259     {
 260       typedef iterator_traits<_IIter1> _TraitsType1;
 261       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
 262
 263       typedef iterator_traits<_IIter2> _TraitsType2;
 264       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
 265
 266       return __inner_product_switch(__first1, __last1, __first2, __init,
 267                                     __binary_op1, __binary_op2,
 268                                     _IteratorCategory1(),
 269                                     _IteratorCategory2());
 270     }
 271
 272   template<typename _IIter1, typename _IIter2, typename _Tp>
 273     inline _Tp
 274     inner_product(_IIter1 __first1, _IIter1 __last1,
 275                   _IIter2 __first2, _Tp __init,
 276                   __gnu_parallel::_Parallelism __parallelism_tag)
 277     {
 278       typedef iterator_traits<_IIter1> _TraitsType1;
 279       typedef typename _TraitsType1::value_type _ValueType1;
 280       typedef iterator_traits<_IIter2> _TraitsType2;
 281       typedef typename _TraitsType2::value_type _ValueType2;
 282
 283       typedef typename
 284         __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
 285         _MultipliesResultType;
 286       return _GLIBCXX_STD_P::inner_product(__first1, __last1, __first2, __init,
 287                            __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
 288                            __gnu_parallel::
 289                            _Multiplies<_ValueType1, _ValueType2>(),
 290                            __parallelism_tag);
 291     }
 292
 293   template<typename _IIter1, typename _IIter2, typename _Tp>
 294     inline _Tp
 295     inner_product(_IIter1 __first1, _IIter1 __last1,
 296                   _IIter2 __first2, _Tp __init)
 297     {
 298       typedef iterator_traits<_IIter1> _TraitsType1;
 299       typedef typename _TraitsType1::value_type _ValueType1;
 300       typedef iterator_traits<_IIter2> _TraitsType2;
 301       typedef typename _TraitsType2::value_type _ValueType2;
 302
 303       typedef typename
 304         __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
 305         _MultipliesResultType;
 306       return _GLIBCXX_STD_P::inner_product(__first1, __last1, __first2, __init,
 307                            __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
 308                            __gnu_parallel::
 309                            _Multiplies<_ValueType1, _ValueType2>());
 310     }
 311
 312   // Sequential fallback.
 313   template<typename _IIter, typename _OutputIterator>
 314     inline _OutputIterator
 315     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
 316                 __gnu_parallel::sequential_tag)
 317     { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result); }
 318
 319   // Sequential fallback.
 320   template<typename _IIter, typename _OutputIterator,
 321            typename _BinaryOperation>
 322     inline _OutputIterator
 323     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
 324                 _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
 325     { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result, __bin_op); }
 326
 327   // Sequential fallback for input iterator case.
 328   template<typename _IIter, typename _OutputIterator,
 329            typename _BinaryOperation, typename _IteratorTag1,
 330            typename _IteratorTag2>
 331     inline _OutputIterator
 332     __partial_sum_switch(_IIter __begin, _IIter __end,
 333                          _OutputIterator __result, _BinaryOperation __bin_op,
 334                          _IteratorTag1, _IteratorTag2)
 335     { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result, __bin_op); }
 336
 337   // Parallel algorithm for random access iterators.
 338   template<typename _IIter, typename _OutputIterator,
 339            typename _BinaryOperation>
 340     _OutputIterator
 341     __partial_sum_switch(_IIter __begin, _IIter __end,
 342                          _OutputIterator __result, _BinaryOperation __bin_op,
 343                          random_access_iterator_tag,
 344                          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 _GLIBCXX_STD_P::partial_sum(__begin, __end,
 363                                          __result, std::plus<_ValueType>());
 364     }
 365
 366   // Public interface
 367   template<typename _IIter, typename _OutputIterator,
 368            typename _BinaryOperation>
 369     inline _OutputIterator
 370     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
 371                 _BinaryOperation __binary_op)
 372     {
 373       typedef iterator_traits<_IIter> _ITraitsType;
 374       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
 375
 376       typedef iterator_traits<_OutputIterator> _OTraitsType;
 377       typedef typename _OTraitsType::iterator_category _OIterCategory;
 378
 379       return __partial_sum_switch(__begin, __end, __result, __binary_op,
 380                                   _IIteratorCategory(), _OIterCategory());
 381     }
 382
 383   // Sequential fallback.
 384   template<typename _IIter, typename _OutputIterator>
 385     inline _OutputIterator
 386     adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
 387                         __gnu_parallel::sequential_tag)
 388     { return _GLIBCXX_STD_P::adjacent_difference(__begin, __end, __result); }
 389
 390   // Sequential fallback.
 391   template<typename _IIter, typename _OutputIterator,
 392            typename _BinaryOperation>
 393     inline _OutputIterator
 394     adjacent_difference(_IIter __begin, _IIter __end,
 395                         _OutputIterator __result, _BinaryOperation __bin_op,
 396                         __gnu_parallel::sequential_tag)
 397     { return _GLIBCXX_STD_P::adjacent_difference(__begin, __end,
 398                                                  __result, __bin_op); }
 399
 400   // Sequential fallback for input iterator case.
 401   template<typename _IIter, typename _OutputIterator,
 402            typename _BinaryOperation, typename _IteratorTag1,
 403            typename _IteratorTag2>
 404     inline _OutputIterator
 405     __adjacent_difference_switch(_IIter __begin, _IIter __end,
 406                                  _OutputIterator __result,
 407                                  _BinaryOperation __bin_op, _IteratorTag1,
 408                                  _IteratorTag2)
 409     { return adjacent_difference(__begin, __end, __result, __bin_op,
 410                                  __gnu_parallel::sequential_tag()); }
 411
 412   // Parallel algorithm for random access iterators.
 413   template<typename _IIter, typename _OutputIterator,
 414            typename _BinaryOperation>
 415     _OutputIterator
 416     __adjacent_difference_switch(_IIter __begin, _IIter __end,
 417                                  _OutputIterator __result,
 418                                  _BinaryOperation __bin_op,
 419                                  random_access_iterator_tag,
 420                                  random_access_iterator_tag,
 421                                  __gnu_parallel::_Parallelism
 422                                  __parallelism_tag
 423                                  = __gnu_parallel::parallel_balanced)
 424     {
 425       if (_GLIBCXX_PARALLEL_CONDITION(
 426             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
 427             >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
 428             && __gnu_parallel::__is_parallel(__parallelism_tag)))
 429         {
 430           bool __dummy = true;
 431           typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,
 432             random_access_iterator_tag> _ItTrip;
 433           *__result = *__begin;
 434           _ItTrip __begin_pair(__begin + 1, __result + 1),
 435             __end_pair(__end, __result + (__end - __begin));
 436           __gnu_parallel::__adjacent_difference_selector<_ItTrip>
 437                                                             __functionality;
 438           __gnu_parallel::
 439             __for_each_template_random_access_ed(
 440                 __begin_pair, __end_pair, __bin_op, __functionality,
 441                 __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);
 442           return __functionality._M_finish_iterator;
 443         }
 444       else
 445         return adjacent_difference(__begin, __end, __result, __bin_op,
 446                                    __gnu_parallel::sequential_tag());
 447     }
 448
 449   // Public interface.
 450   template<typename _IIter, typename _OutputIterator>
 451     inline _OutputIterator
 452     adjacent_difference(_IIter __begin, _IIter __end,
 453                         _OutputIterator __result,
 454                         __gnu_parallel::_Parallelism __parallelism_tag)
 455     {
 456       typedef iterator_traits<_IIter> _TraitsType;
 457       typedef typename _TraitsType::value_type _ValueType;
 458       return adjacent_difference(__begin, __end, __result,
 459                                  std::minus<_ValueType>(),
 460                                  __parallelism_tag);
 461     }
 462
 463   template<typename _IIter, typename _OutputIterator>
 464     inline _OutputIterator
 465     adjacent_difference(_IIter __begin, _IIter __end,
 466                         _OutputIterator __result)
 467     {
 468       typedef iterator_traits<_IIter> _TraitsType;
 469       typedef typename _TraitsType::value_type _ValueType;
 470       return adjacent_difference(__begin, __end, __result,
 471                                  std::minus<_ValueType>());
 472     }
 473
 474   template<typename _IIter, typename _OutputIterator,
 475            typename _BinaryOperation>
 476     inline _OutputIterator
 477     adjacent_difference(_IIter __begin, _IIter __end,
 478                         _OutputIterator __result, _BinaryOperation __binary_op,
 479                         __gnu_parallel::_Parallelism __parallelism_tag)
 480     {
 481       typedef iterator_traits<_IIter> _ITraitsType;
 482       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
 483
 484       typedef iterator_traits<_OutputIterator> _OTraitsType;
 485       typedef typename _OTraitsType::iterator_category _OIterCategory;
 486
 487       return __adjacent_difference_switch(__begin, __end, __result,
 488                                           __binary_op,
 489                                           _IIteratorCategory(),
 490                                           _OIterCategory(),
 491                                           __parallelism_tag);
 492     }
 493
 494   template<typename _IIter, typename _OutputIterator,
 495            typename _BinaryOperation>
 496     inline _OutputIterator
 497     adjacent_difference(_IIter __begin, _IIter __end,
 498                         _OutputIterator __result, _BinaryOperation __binary_op)
 499     {
 500       typedef iterator_traits<_IIter> _ITraitsType;
 501       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
 502
 503       typedef iterator_traits<_OutputIterator> _OTraitsType;
 504       typedef typename _OTraitsType::iterator_category _OIterCategory;
 505
 506       return __adjacent_difference_switch(__begin, __end, __result,
 507                                           __binary_op,
 508                                           _IIteratorCategory(),
 509                                           _OIterCategory());
 510     }
 511 } // end namespace
 512 } // end namespace
 513
 514 #endif /* _GLIBCXX_NUMERIC_H */