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 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 { 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 */ 512