libstdc++-v3/include/parallel/numeric

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