libstdc++-v3/include/parallel/numeric

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /**
  32  * @file parallel/numeric
  33 *
  34  * @brief Parallel STL function calls corresponding to stl_numeric.h.
  35  * The functions defined here mainly do case switches and
  36  * call the actual parallelized versions in other files.
  37  * Inlining policy: Functions that basically only contain one function call,
  38  * are declared inline.
  39  *  This file is a GNU parallel extension to the Standard C++ Library.
  40  */
  41
  42 // Written by Johannes Singler and Felix Putze.
  43
  44 #ifndef _GLIBCXX_PARALLEL_NUMERIC_H
  45 #define _GLIBCXX_PARALLEL_NUMERIC_H 1
  46
  47 #include <numeric>
  48 #include <functional>
  49 #include <parallel/numericfwd.h>
  50 #include <parallel/iterator.h>
  51 #include <parallel/for_each.h>
  52 #include <parallel/for_each_selectors.h>
  53 #include <parallel/partial_sum.h>
  54
  55 namespace std
  56 {
  57 namespace __parallel
  58 {
  59   // Sequential fallback.
  60   template<typename InputIterator, typename T>
  61   inline T
  62   accumulate(InputIterator begin, InputIterator end, T init,
  63              __gnu_parallel::sequential_tag)
  64   { return _GLIBCXX_STD_P::accumulate(begin, end, init); }
  65
  66   template<typename InputIterator, typename T, typename BinaryOperation>
  67   inline T
  68   accumulate(InputIterator begin, InputIterator end, T init,
  69              BinaryOperation binary_op, __gnu_parallel::sequential_tag)
  70   { return _GLIBCXX_STD_P::accumulate(begin, end, init, binary_op); }
  71
  72   // Sequential fallback for input iterator case.
  73   template<typename InputIterator, typename T, typename IteratorTag>
  74   inline T
  75   accumulate_switch(InputIterator begin, InputIterator end, T init, IteratorTag)  { return accumulate(begin, end, init, __gnu_parallel::sequential_tag()); }
  76
  77   template<typename InputIterator, typename T, typename BinaryOperation, typename IteratorTag>
  78   T
  79   accumulate_switch(InputIterator begin, InputIterator end, T init,
  80                     BinaryOperation binary_op, IteratorTag)
  81   {
  82     return accumulate(begin, end, init, binary_op,
  83                       __gnu_parallel::sequential_tag());
  84   }
  85
  86   // Parallel algorithm for random access iterators.
  87   template<typename _RandomAccessIterator, typename T, typename BinaryOperation>
  88   T
  89   accumulate_switch(_RandomAccessIterator begin, _RandomAccessIterator end,
  90                     T init, BinaryOperation binary_op,
  91                     random_access_iterator_tag,
  92                     __gnu_parallel::parallelism parallelism_tag
  93                     = __gnu_parallel::parallel_unbalanced)
  94   {
  95     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::accumulate_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
  96       {
  97         T res = init;
  98         __gnu_parallel::accumulate_selector<_RandomAccessIterator> my_selector;
  99         __gnu_parallel::for_each_template_random_access(begin, end, __gnu_parallel::nothing(), my_selector, __gnu_parallel::accumulate_binop_reduct<BinaryOperation>(binary_op), res, res, -1, parallelism_tag);
 100         return res;
 101       }
 102     else
 103       return accumulate(begin, end, init, binary_op,
 104                         __gnu_parallel::sequential_tag());
 105   }
 106
 107   // Public interface.
 108   template<typename InputIterator, typename T>
 109   inline T
 110   accumulate(InputIterator begin, InputIterator end, T init,
 111              __gnu_parallel::parallelism parallelism_tag)
 112   {
 113     typedef std::iterator_traits<InputIterator> iterator_traits;
 114     typedef typename iterator_traits::value_type value_type;
 115     typedef typename iterator_traits::iterator_category iterator_category;
 116
 117     return accumulate_switch(begin, end, init, __gnu_parallel::plus<T, value_type>(),
 118                              iterator_category(), parallelism_tag);
 119   }
 120
 121   template<typename InputIterator, typename T>
 122   inline T
 123   accumulate(InputIterator begin, InputIterator end, T init)
 124   {
 125     typedef std::iterator_traits<InputIterator> iterator_traits;
 126     typedef typename iterator_traits::value_type value_type;
 127     typedef typename iterator_traits::iterator_category iterator_category;
 128
 129     return accumulate_switch(begin, end, init, __gnu_parallel::plus<T, value_type>(),
 130                              iterator_category());
 131   }
 132
 133   template<typename InputIterator, typename T, typename BinaryOperation>
 134   inline T
 135   accumulate(InputIterator begin, InputIterator end, T init,
 136              BinaryOperation binary_op,
 137              __gnu_parallel::parallelism parallelism_tag)
 138   {
 139     typedef iterator_traits<InputIterator> iterator_traits;
 140     typedef typename iterator_traits::iterator_category iterator_category;
 141     return accumulate_switch(begin, end, init, binary_op,
 142                              iterator_category(), parallelism_tag);
 143   }
 144
 145   template<typename InputIterator, typename T, typename BinaryOperation>
 146   inline T
 147   accumulate(InputIterator begin, InputIterator end, T init,
 148              BinaryOperation binary_op)
 149   {
 150     typedef iterator_traits<InputIterator> iterator_traits;
 151     typedef typename iterator_traits::iterator_category iterator_category;
 152     return accumulate_switch(begin, end, init, binary_op,
 153                              iterator_category());
 154   }
 155
 156
 157   // Sequential fallback.
 158   template<typename InputIterator1, typename InputIterator2, typename T>
 159   inline T
 160   inner_product(InputIterator1 first1, InputIterator1 last1,
 161                 InputIterator2 first2, T init, __gnu_parallel::sequential_tag)
 162   { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init); }
 163
 164   template<typename InputIterator1, typename InputIterator2, typename T, typename BinaryFunction1, typename BinaryFunction2>
 165   inline T
 166   inner_product(InputIterator1 first1, InputIterator1 last1,
 167                 InputIterator2 first2, T init, BinaryFunction1 binary_op1,
 168                 BinaryFunction2 binary_op2, __gnu_parallel::sequential_tag)
 169   {
 170     return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
 171                                          binary_op1, binary_op2);
 172   }
 173
 174   // Parallel algorithm for random access iterators.
 175   template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename T, typename BinaryFunction1, typename BinaryFunction2>
 176   T
 177   inner_product_switch(RandomAccessIterator1 first1, RandomAccessIterator1 last1, RandomAccessIterator2 first2, T init, BinaryFunction1 binary_op1, BinaryFunction2 binary_op2, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_unbalanced)
 178   {
 179     if (_GLIBCXX_PARALLEL_CONDITION((last1 - first1) >= __gnu_parallel::Settings::accumulate_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
 180       {
 181         T res = init;
 182         __gnu_parallel::inner_product_selector<RandomAccessIterator1, RandomAccessIterator2, T> my_selector(first1, first2);
 183         __gnu_parallel::for_each_template_random_access(first1, last1, binary_op2, my_selector, binary_op1, res, res, -1, parallelism_tag);
 184         return res;
 185       }
 186     else
 187       return inner_product(first1, last1, first2, init,
 188                            __gnu_parallel::sequential_tag());
 189   }
 190
 191   // No parallelism for input iterators.
 192   template<typename InputIterator1, typename InputIterator2, typename T, typename BinaryFunction1, typename BinaryFunction2, typename IteratorTag1, typename IteratorTag2>
 193   inline T
 194   inner_product_switch(InputIterator1 first1, InputIterator1 last1,
 195                        InputIterator2 first2, T init,
 196                        BinaryFunction1 binary_op1, BinaryFunction2 binary_op2,
 197                        IteratorTag1, IteratorTag2)
 198   {
 199     return inner_product(first1, last1, first2, init, binary_op1, binary_op2,
 200                          __gnu_parallel::sequential_tag());
 201   }
 202
 203   template<typename InputIterator1, typename InputIterator2, typename T, typename BinaryFunction1, typename BinaryFunction2>
 204   inline T
 205   inner_product(InputIterator1 first1, InputIterator1 last1,
 206                 InputIterator2 first2, T init, BinaryFunction1 binary_op1,
 207                 BinaryFunction2 binary_op2,
 208                 __gnu_parallel::parallelism parallelism_tag)
 209   {
 210     typedef iterator_traits<InputIterator1> traits1_type;
 211     typedef typename traits1_type::iterator_category iterator1_category;
 212
 213     typedef iterator_traits<InputIterator2> traits2_type;
 214     typedef typename traits2_type::iterator_category iterator2_category;
 215
 216     return inner_product_switch(first1, last1, first2, init, binary_op1,
 217                                 binary_op2, iterator1_category(),
 218                                 iterator2_category(), parallelism_tag);
 219   }
 220
 221   template<typename InputIterator1, typename InputIterator2, typename T, typename BinaryFunction1, typename BinaryFunction2>
 222   inline T
 223   inner_product(InputIterator1 first1, InputIterator1 last1,
 224                 InputIterator2 first2, T init, BinaryFunction1 binary_op1,
 225                 BinaryFunction2 binary_op2)
 226   {
 227     typedef iterator_traits<InputIterator1> traits1_type;
 228     typedef typename traits1_type::iterator_category iterator1_category;
 229
 230     typedef iterator_traits<InputIterator2> traits2_type;
 231     typedef typename traits2_type::iterator_category iterator2_category;
 232
 233     return inner_product_switch(first1, last1, first2, init, binary_op1,
 234                                 binary_op2, iterator1_category(),
 235                                 iterator2_category());
 236   }
 237
 238   template<typename InputIterator1, typename InputIterator2, typename T>
 239   inline T
 240   inner_product(InputIterator1 first1, InputIterator1 last1,
 241                 InputIterator2 first2, T init,
 242                 __gnu_parallel::parallelism parallelism_tag)
 243   {
 244     typedef iterator_traits<InputIterator1> traits_type1;
 245     typedef typename traits_type1::value_type value_type1;
 246     typedef iterator_traits<InputIterator2> traits_type2;
 247     typedef typename traits_type2::value_type value_type2;
 248
 249     typedef typename __gnu_parallel::multiplies<value_type1, value_type2>::result
 250         multiplies_result_type;
 251     return inner_product(first1, last1, first2, init,
 252                            __gnu_parallel::plus<T, multiplies_result_type>(),
 253                            __gnu_parallel::multiplies<value_type1, value_type2>(),
 254                            parallelism_tag);
 255   }
 256
 257   template<typename InputIterator1, typename InputIterator2, typename T>
 258   inline T
 259   inner_product(InputIterator1 first1, InputIterator1 last1,
 260                 InputIterator2 first2, T init)
 261   {
 262     typedef iterator_traits<InputIterator1> traits_type1;
 263     typedef typename traits_type1::value_type value_type1;
 264     typedef iterator_traits<InputIterator2> traits_type2;
 265     typedef typename traits_type2::value_type value_type2;
 266
 267     typedef typename __gnu_parallel::multiplies<value_type1, value_type2>::result
 268         multiplies_result_type;
 269     return inner_product(first1, last1, first2, init,
 270                            __gnu_parallel::plus<T, multiplies_result_type>(),
 271                            __gnu_parallel::multiplies<value_type1, value_type2>());
 272   }
 273
 274   // Sequential fallback.
 275   template<typename InputIterator, typename OutputIterator>
 276   inline OutputIterator
 277   partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
 278               __gnu_parallel::sequential_tag)
 279   { return _GLIBCXX_STD_P::partial_sum(begin, end, result); }
 280
 281   // Sequential fallback.
 282   template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
 283   inline OutputIterator
 284   partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
 285               BinaryOperation bin_op, __gnu_parallel::sequential_tag)
 286   { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
 287
 288   // Sequential fallback for input iterator case.
 289   template<typename InputIterator, typename OutputIterator, typename BinaryOperation, typename IteratorTag1, typename IteratorTag2>
 290   inline OutputIterator
 291   partial_sum_switch(InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, IteratorTag1, IteratorTag2)
 292   {
 293     return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op);
 294   }
 295
 296   // Parallel algorithm for random access iterators.
 297   template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
 298   OutputIterator
 299   partial_sum_switch(InputIterator begin, InputIterator end,
 300                      OutputIterator result, BinaryOperation bin_op,
 301                      random_access_iterator_tag, random_access_iterator_tag)
 302   {
 303     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::partial_sum_minimal_n))
 304       return __gnu_parallel::parallel_partial_sum(begin, end, result, bin_op);
 305     else
 306       return partial_sum(begin, end, result, bin_op, __gnu_parallel::sequential_tag());
 307   }
 308
 309   // Public interface.
 310   template<typename InputIterator, typename OutputIterator>
 311   inline OutputIterator
 312   partial_sum(InputIterator begin, InputIterator end, OutputIterator result)
 313   {
 314     typedef typename iterator_traits<InputIterator>::value_type value_type;
 315     return partial_sum(begin, end, result, std::plus<value_type>());
 316   }
 317
 318   // Public interface
 319   template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
 320   inline OutputIterator
 321   partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
 322               BinaryOperation binary_op)
 323   {
 324     typedef iterator_traits<InputIterator> traitsi_type;
 325     typedef typename traitsi_type::iterator_category iteratori_category;
 326
 327     typedef iterator_traits<OutputIterator> traitso_type;
 328     typedef typename traitso_type::iterator_category iteratoro_category;
 329
 330     return partial_sum_switch(begin, end, result, binary_op,
 331                                    iteratori_category(), iteratoro_category());
 332   }
 333
 334   // Sequential fallback.
 335   template<typename InputIterator, typename OutputIterator>
 336   inline OutputIterator
 337   adjacent_difference(InputIterator begin, InputIterator end,
 338                       OutputIterator result, __gnu_parallel::sequential_tag)
 339   { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); }
 340
 341   // Sequential fallback.
 342   template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
 343   inline OutputIterator
 344   adjacent_difference(InputIterator begin, InputIterator end,
 345                       OutputIterator result, BinaryOperation bin_op,
 346                       __gnu_parallel::sequential_tag)
 347   {
 348     return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op);
 349   }
 350
 351   // Sequential fallback for input iterator case.
 352   template<typename InputIterator, typename OutputIterator, typename BinaryOperation, typename IteratorTag1, typename IteratorTag2>
 353   inline OutputIterator
 354   adjacent_difference_switch(InputIterator begin, InputIterator end,
 355                              OutputIterator result, BinaryOperation bin_op,
 356                              IteratorTag1, IteratorTag2)
 357   {
 358     return adjacent_difference(begin, end, result, bin_op,
 359                                __gnu_parallel::sequential_tag());
 360   }
 361
 362   // Parallel algorithm for random access iterators.
 363   template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
 364   OutputIterator
 365   adjacent_difference_switch(InputIterator begin, InputIterator end,
 366                              OutputIterator result, BinaryOperation bin_op,
 367                              random_access_iterator_tag,
 368                              random_access_iterator_tag,
 369                              __gnu_parallel::parallelism parallelism_tag
 370                              = __gnu_parallel::parallel_balanced)
 371   {
 372     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::adjacent_difference_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
 373       {
 374         bool dummy = true;
 375         typedef __gnu_parallel::iterator_pair<InputIterator, OutputIterator, random_access_iterator_tag> ip;
 376         *result = *begin;
 377         ip begin_pair(begin + 1, result + 1), end_pair(end, result + (end - begin));
 378         __gnu_parallel::adjacent_difference_selector<ip> functionality;
 379         __gnu_parallel::for_each_template_random_access(begin_pair, end_pair, bin_op, functionality, __gnu_parallel::dummy_reduct(), dummy, dummy, -1, parallelism_tag);
 380         return functionality.finish_iterator;
 381       }
 382     else
 383       return adjacent_difference(begin, end, result, bin_op,
 384                                  __gnu_parallel::sequential_tag());
 385   }
 386
 387   // Public interface.
 388   template<typename InputIterator, typename OutputIterator>
 389   inline OutputIterator
 390   adjacent_difference(InputIterator begin, InputIterator end,
 391                       OutputIterator result,
 392                       __gnu_parallel::parallelism parallelism_tag)
 393   {
 394     typedef iterator_traits<InputIterator> traits_type;
 395     typedef typename traits_type::value_type value_type;
 396     return adjacent_difference(begin, end, result, std::minus<value_type>(),
 397                                parallelism_tag);
 398   }
 399
 400   template<typename InputIterator, typename OutputIterator>
 401   inline OutputIterator
 402   adjacent_difference(InputIterator begin, InputIterator end,
 403                       OutputIterator result)
 404   {
 405     typedef iterator_traits<InputIterator> traits_type;
 406     typedef typename traits_type::value_type value_type;
 407     return adjacent_difference(begin, end, result, std::minus<value_type>());
 408   }
 409
 410   template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
 411   inline OutputIterator
 412   adjacent_difference(InputIterator begin, InputIterator end,
 413                       OutputIterator result, BinaryOperation binary_op,
 414                       __gnu_parallel::parallelism parallelism_tag)
 415   {
 416     typedef iterator_traits<InputIterator> traitsi_type;
 417     typedef typename traitsi_type::iterator_category iteratori_category;
 418
 419     typedef iterator_traits<OutputIterator> traitso_type;
 420     typedef typename traitso_type::iterator_category iteratoro_category;
 421
 422     return adjacent_difference_switch(begin, end, result, binary_op,
 423                                       iteratori_category(),
 424                                       iteratoro_category(), parallelism_tag);
 425   }
 426
 427   template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
 428   inline OutputIterator
 429   adjacent_difference(InputIterator begin, InputIterator end,
 430                       OutputIterator result, BinaryOperation binary_op)
 431   {
 432     typedef iterator_traits<InputIterator> traitsi_type;
 433     typedef typename traitsi_type::iterator_category iteratori_category;
 434
 435     typedef iterator_traits<OutputIterator> traitso_type;
 436     typedef typename traitso_type::iterator_category iteratoro_category;
 437
 438     return adjacent_difference_switch(begin, end, result, binary_op,
 439                                       iteratori_category(),
 440                                       iteratoro_category());
 441   }
 442 } // end namespace
 443 } // end namespace
 444
 445 #endif /* _GLIBCXX_NUMERIC_H */