1// -*- C++ -*- 2 3// Copyright (C) 2007, 2008, 2009, 2010 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 49namespace std _GLIBCXX_VISIBILITY(default) 50{ 51namespace __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 = __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_A::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_A::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 __gnu_parallel::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 __gnu_parallel::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_A::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_A::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_A::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 __gnu_parallel::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_A::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_A::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 */ 515