libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** 00026 * @file parallel/numeric 00027 * 00028 * @brief Parallel STL function calls corresponding to stl_numeric.h. 00029 * The functions defined here mainly do case switches and 00030 * call the actual parallelized versions in other files. 00031 * Inlining policy: Functions that basically only contain one function call, 00032 * are declared inline. 00033 * This file is a GNU parallel extension to the Standard C++ Library. 00034 */ 00035 00036 // Written by Johannes Singler and Felix Putze. 00037 00038 #ifndef _GLIBCXX_PARALLEL_NUMERIC_H 00039 #define _GLIBCXX_PARALLEL_NUMERIC_H 1 00040 00041 #include <numeric> 00042 #include <bits/stl_function.h> 00043 #include <parallel/numericfwd.h> 00044 #include <parallel/iterator.h> 00045 #include <parallel/for_each.h> 00046 #include <parallel/for_each_selectors.h> 00047 #include <parallel/partial_sum.h> 00048 00049 namespace std _GLIBCXX_VISIBILITY(default) 00050 { 00051 namespace __parallel 00052 { 00053 // Sequential fallback. 00054 template<typename _IIter, typename _Tp> 00055 inline _Tp 00056 accumulate(_IIter __begin, _IIter __end, _Tp __init, 00057 __gnu_parallel::sequential_tag) 00058 { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init); } 00059 00060 template<typename _IIter, typename _Tp, typename _BinaryOperation> 00061 inline _Tp 00062 accumulate(_IIter __begin, _IIter __end, _Tp __init, 00063 _BinaryOperation __binary_op, __gnu_parallel::sequential_tag) 00064 { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init, __binary_op); } 00065 00066 // Sequential fallback for input iterator case. 00067 template<typename _IIter, typename _Tp, typename _IteratorTag> 00068 inline _Tp 00069 __accumulate_switch(_IIter __begin, _IIter __end, 00070 _Tp __init, _IteratorTag) 00071 { return accumulate(__begin, __end, __init, 00072 __gnu_parallel::sequential_tag()); } 00073 00074 template<typename _IIter, typename _Tp, typename _BinaryOperation, 00075 typename _IteratorTag> 00076 inline _Tp 00077 __accumulate_switch(_IIter __begin, _IIter __end, _Tp __init, 00078 _BinaryOperation __binary_op, _IteratorTag) 00079 { return accumulate(__begin, __end, __init, __binary_op, 00080 __gnu_parallel::sequential_tag()); } 00081 00082 // Parallel algorithm for random access iterators. 00083 template<typename __RAIter, typename _Tp, typename _BinaryOperation> 00084 _Tp 00085 __accumulate_switch(__RAIter __begin, __RAIter __end, 00086 _Tp __init, _BinaryOperation __binary_op, 00087 random_access_iterator_tag, 00088 __gnu_parallel::_Parallelism __parallelism_tag) 00089 { 00090 if (_GLIBCXX_PARALLEL_CONDITION( 00091 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 00092 >= __gnu_parallel::_Settings::get().accumulate_minimal_n 00093 && __gnu_parallel::__is_parallel(__parallelism_tag))) 00094 { 00095 _Tp __res = __init; 00096 __gnu_parallel::__accumulate_selector<__RAIter> 00097 __my_selector; 00098 __gnu_parallel:: 00099 __for_each_template_random_access_ed(__begin, __end, 00100 __gnu_parallel::_Nothing(), 00101 __my_selector, 00102 __gnu_parallel:: 00103 __accumulate_binop_reduct 00104 <_BinaryOperation>(__binary_op), 00105 __res, __res, -1); 00106 return __res; 00107 } 00108 else 00109 return accumulate(__begin, __end, __init, __binary_op, 00110 __gnu_parallel::sequential_tag()); 00111 } 00112 00113 // Public interface. 00114 template<typename _IIter, typename _Tp> 00115 inline _Tp 00116 accumulate(_IIter __begin, _IIter __end, _Tp __init, 00117 __gnu_parallel::_Parallelism __parallelism_tag) 00118 { 00119 typedef std::iterator_traits<_IIter> _IteratorTraits; 00120 typedef typename _IteratorTraits::value_type _ValueType; 00121 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 00122 00123 return __accumulate_switch(__begin, __end, __init, 00124 __gnu_parallel::_Plus<_Tp, _ValueType>(), 00125 _IteratorCategory(), __parallelism_tag); 00126 } 00127 00128 template<typename _IIter, typename _Tp> 00129 inline _Tp 00130 accumulate(_IIter __begin, _IIter __end, _Tp __init) 00131 { 00132 typedef std::iterator_traits<_IIter> _IteratorTraits; 00133 typedef typename _IteratorTraits::value_type _ValueType; 00134 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 00135 00136 return __accumulate_switch(__begin, __end, __init, 00137 __gnu_parallel::_Plus<_Tp, _ValueType>(), 00138 _IteratorCategory()); 00139 } 00140 00141 template<typename _IIter, typename _Tp, typename _BinaryOperation> 00142 inline _Tp 00143 accumulate(_IIter __begin, _IIter __end, _Tp __init, 00144 _BinaryOperation __binary_op, 00145 __gnu_parallel::_Parallelism __parallelism_tag) 00146 { 00147 typedef iterator_traits<_IIter> _IteratorTraits; 00148 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 00149 return __accumulate_switch(__begin, __end, __init, __binary_op, 00150 _IteratorCategory(), __parallelism_tag); 00151 } 00152 00153 template<typename _IIter, typename _Tp, typename _BinaryOperation> 00154 inline _Tp 00155 accumulate(_IIter __begin, _IIter __end, _Tp __init, 00156 _BinaryOperation __binary_op) 00157 { 00158 typedef iterator_traits<_IIter> _IteratorTraits; 00159 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 00160 return __accumulate_switch(__begin, __end, __init, __binary_op, 00161 _IteratorCategory()); 00162 } 00163 00164 00165 // Sequential fallback. 00166 template<typename _IIter1, typename _IIter2, typename _Tp> 00167 inline _Tp 00168 inner_product(_IIter1 __first1, _IIter1 __last1, 00169 _IIter2 __first2, _Tp __init, 00170 __gnu_parallel::sequential_tag) 00171 { return _GLIBCXX_STD_A::inner_product( 00172 __first1, __last1, __first2, __init); } 00173 00174 template<typename _IIter1, typename _IIter2, typename _Tp, 00175 typename _BinaryFunction1, typename _BinaryFunction2> 00176 inline _Tp 00177 inner_product(_IIter1 __first1, _IIter1 __last1, 00178 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 00179 _BinaryFunction2 __binary_op2, 00180 __gnu_parallel::sequential_tag) 00181 { return _GLIBCXX_STD_A::inner_product(__first1, __last1, __first2, __init, 00182 __binary_op1, __binary_op2); } 00183 00184 // Parallel algorithm for random access iterators. 00185 template<typename _RAIter1, typename _RAIter2, 00186 typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2> 00187 _Tp 00188 __inner_product_switch(_RAIter1 __first1, 00189 _RAIter1 __last1, 00190 _RAIter2 __first2, _Tp __init, 00191 _BinaryFunction1 __binary_op1, 00192 _BinaryFunction2 __binary_op2, 00193 random_access_iterator_tag, 00194 random_access_iterator_tag, 00195 __gnu_parallel::_Parallelism __parallelism_tag) 00196 { 00197 if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1) 00198 >= __gnu_parallel::_Settings::get(). 00199 accumulate_minimal_n 00200 && __gnu_parallel:: 00201 __is_parallel(__parallelism_tag))) 00202 { 00203 _Tp __res = __init; 00204 __gnu_parallel:: 00205 __inner_product_selector<_RAIter1, 00206 _RAIter2, _Tp> __my_selector(__first1, __first2); 00207 __gnu_parallel:: 00208 __for_each_template_random_access_ed( 00209 __first1, __last1, __binary_op2, __my_selector, __binary_op1, 00210 __res, __res, -1); 00211 return __res; 00212 } 00213 else 00214 return inner_product(__first1, __last1, __first2, __init, 00215 __gnu_parallel::sequential_tag()); 00216 } 00217 00218 // No parallelism for input iterators. 00219 template<typename _IIter1, typename _IIter2, typename _Tp, 00220 typename _BinaryFunction1, typename _BinaryFunction2, 00221 typename _IteratorTag1, typename _IteratorTag2> 00222 inline _Tp 00223 __inner_product_switch(_IIter1 __first1, _IIter1 __last1, 00224 _IIter2 __first2, _Tp __init, 00225 _BinaryFunction1 __binary_op1, 00226 _BinaryFunction2 __binary_op2, 00227 _IteratorTag1, _IteratorTag2) 00228 { return inner_product(__first1, __last1, __first2, __init, __binary_op1, 00229 __binary_op2, __gnu_parallel::sequential_tag()); } 00230 00231 template<typename _IIter1, typename _IIter2, typename _Tp, 00232 typename _BinaryFunction1, typename _BinaryFunction2> 00233 inline _Tp 00234 inner_product(_IIter1 __first1, _IIter1 __last1, 00235 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 00236 _BinaryFunction2 __binary_op2, 00237 __gnu_parallel::_Parallelism __parallelism_tag) 00238 { 00239 typedef iterator_traits<_IIter1> _TraitsType1; 00240 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 00241 00242 typedef iterator_traits<_IIter2> _TraitsType2; 00243 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 00244 00245 return __inner_product_switch(__first1, __last1, __first2, __init, 00246 __binary_op1, __binary_op2, 00247 _IteratorCategory1(), _IteratorCategory2(), 00248 __parallelism_tag); 00249 } 00250 00251 template<typename _IIter1, typename _IIter2, typename _Tp, 00252 typename _BinaryFunction1, typename _BinaryFunction2> 00253 inline _Tp 00254 inner_product(_IIter1 __first1, _IIter1 __last1, 00255 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 00256 _BinaryFunction2 __binary_op2) 00257 { 00258 typedef iterator_traits<_IIter1> _TraitsType1; 00259 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 00260 00261 typedef iterator_traits<_IIter2> _TraitsType2; 00262 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 00263 00264 return __inner_product_switch(__first1, __last1, __first2, __init, 00265 __binary_op1, __binary_op2, 00266 _IteratorCategory1(), 00267 _IteratorCategory2()); 00268 } 00269 00270 template<typename _IIter1, typename _IIter2, typename _Tp> 00271 inline _Tp 00272 inner_product(_IIter1 __first1, _IIter1 __last1, 00273 _IIter2 __first2, _Tp __init, 00274 __gnu_parallel::_Parallelism __parallelism_tag) 00275 { 00276 typedef iterator_traits<_IIter1> _TraitsType1; 00277 typedef typename _TraitsType1::value_type _ValueType1; 00278 typedef iterator_traits<_IIter2> _TraitsType2; 00279 typedef typename _TraitsType2::value_type _ValueType2; 00280 00281 typedef typename 00282 __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type 00283 _MultipliesResultType; 00284 return __gnu_parallel::inner_product(__first1, __last1, __first2, __init, 00285 __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(), 00286 __gnu_parallel:: 00287 _Multiplies<_ValueType1, _ValueType2>(), 00288 __parallelism_tag); 00289 } 00290 00291 template<typename _IIter1, typename _IIter2, typename _Tp> 00292 inline _Tp 00293 inner_product(_IIter1 __first1, _IIter1 __last1, 00294 _IIter2 __first2, _Tp __init) 00295 { 00296 typedef iterator_traits<_IIter1> _TraitsType1; 00297 typedef typename _TraitsType1::value_type _ValueType1; 00298 typedef iterator_traits<_IIter2> _TraitsType2; 00299 typedef typename _TraitsType2::value_type _ValueType2; 00300 00301 typedef typename 00302 __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type 00303 _MultipliesResultType; 00304 return __gnu_parallel::inner_product(__first1, __last1, __first2, __init, 00305 __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(), 00306 __gnu_parallel:: 00307 _Multiplies<_ValueType1, _ValueType2>()); 00308 } 00309 00310 // Sequential fallback. 00311 template<typename _IIter, typename _OutputIterator> 00312 inline _OutputIterator 00313 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result, 00314 __gnu_parallel::sequential_tag) 00315 { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); } 00316 00317 // Sequential fallback. 00318 template<typename _IIter, typename _OutputIterator, 00319 typename _BinaryOperation> 00320 inline _OutputIterator 00321 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result, 00322 _BinaryOperation __bin_op, __gnu_parallel::sequential_tag) 00323 { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); } 00324 00325 // Sequential fallback for input iterator case. 00326 template<typename _IIter, typename _OutputIterator, 00327 typename _BinaryOperation, typename _IteratorTag1, 00328 typename _IteratorTag2> 00329 inline _OutputIterator 00330 __partial_sum_switch(_IIter __begin, _IIter __end, 00331 _OutputIterator __result, _BinaryOperation __bin_op, 00332 _IteratorTag1, _IteratorTag2) 00333 { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); } 00334 00335 // Parallel algorithm for random access iterators. 00336 template<typename _IIter, typename _OutputIterator, 00337 typename _BinaryOperation> 00338 _OutputIterator 00339 __partial_sum_switch(_IIter __begin, _IIter __end, 00340 _OutputIterator __result, _BinaryOperation __bin_op, 00341 random_access_iterator_tag, 00342 random_access_iterator_tag) 00343 { 00344 if (_GLIBCXX_PARALLEL_CONDITION( 00345 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 00346 >= __gnu_parallel::_Settings::get().partial_sum_minimal_n)) 00347 return __gnu_parallel::__parallel_partial_sum(__begin, __end, 00348 __result, __bin_op); 00349 else 00350 return partial_sum(__begin, __end, __result, __bin_op, 00351 __gnu_parallel::sequential_tag()); 00352 } 00353 00354 // Public interface. 00355 template<typename _IIter, typename _OutputIterator> 00356 inline _OutputIterator 00357 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result) 00358 { 00359 typedef typename iterator_traits<_IIter>::value_type _ValueType; 00360 return __gnu_parallel::partial_sum(__begin, __end, 00361 __result, std::plus<_ValueType>()); 00362 } 00363 00364 // Public interface 00365 template<typename _IIter, typename _OutputIterator, 00366 typename _BinaryOperation> 00367 inline _OutputIterator 00368 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result, 00369 _BinaryOperation __binary_op) 00370 { 00371 typedef iterator_traits<_IIter> _ITraitsType; 00372 typedef typename _ITraitsType::iterator_category _IIteratorCategory; 00373 00374 typedef iterator_traits<_OutputIterator> _OTraitsType; 00375 typedef typename _OTraitsType::iterator_category _OIterCategory; 00376 00377 return __partial_sum_switch(__begin, __end, __result, __binary_op, 00378 _IIteratorCategory(), _OIterCategory()); 00379 } 00380 00381 // Sequential fallback. 00382 template<typename _IIter, typename _OutputIterator> 00383 inline _OutputIterator 00384 adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result, 00385 __gnu_parallel::sequential_tag) 00386 { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); } 00387 00388 // Sequential fallback. 00389 template<typename _IIter, typename _OutputIterator, 00390 typename _BinaryOperation> 00391 inline _OutputIterator 00392 adjacent_difference(_IIter __begin, _IIter __end, 00393 _OutputIterator __result, _BinaryOperation __bin_op, 00394 __gnu_parallel::sequential_tag) 00395 { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, 00396 __result, __bin_op); } 00397 00398 // Sequential fallback for input iterator case. 00399 template<typename _IIter, typename _OutputIterator, 00400 typename _BinaryOperation, typename _IteratorTag1, 00401 typename _IteratorTag2> 00402 inline _OutputIterator 00403 __adjacent_difference_switch(_IIter __begin, _IIter __end, 00404 _OutputIterator __result, 00405 _BinaryOperation __bin_op, _IteratorTag1, 00406 _IteratorTag2) 00407 { return adjacent_difference(__begin, __end, __result, __bin_op, 00408 __gnu_parallel::sequential_tag()); } 00409 00410 // Parallel algorithm for random access iterators. 00411 template<typename _IIter, typename _OutputIterator, 00412 typename _BinaryOperation> 00413 _OutputIterator 00414 __adjacent_difference_switch(_IIter __begin, _IIter __end, 00415 _OutputIterator __result, 00416 _BinaryOperation __bin_op, 00417 random_access_iterator_tag, 00418 random_access_iterator_tag, 00419 __gnu_parallel::_Parallelism 00420 __parallelism_tag) 00421 { 00422 if (_GLIBCXX_PARALLEL_CONDITION( 00423 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 00424 >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n 00425 && __gnu_parallel::__is_parallel(__parallelism_tag))) 00426 { 00427 bool __dummy = true; 00428 typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator, 00429 random_access_iterator_tag> _ItTrip; 00430 *__result = *__begin; 00431 _ItTrip __begin_pair(__begin + 1, __result + 1), 00432 __end_pair(__end, __result + (__end - __begin)); 00433 __gnu_parallel::__adjacent_difference_selector<_ItTrip> 00434 __functionality; 00435 __gnu_parallel:: 00436 __for_each_template_random_access_ed( 00437 __begin_pair, __end_pair, __bin_op, __functionality, 00438 __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1); 00439 return __functionality._M_finish_iterator; 00440 } 00441 else 00442 return adjacent_difference(__begin, __end, __result, __bin_op, 00443 __gnu_parallel::sequential_tag()); 00444 } 00445 00446 // Public interface. 00447 template<typename _IIter, typename _OutputIterator> 00448 inline _OutputIterator 00449 adjacent_difference(_IIter __begin, _IIter __end, 00450 _OutputIterator __result, 00451 __gnu_parallel::_Parallelism __parallelism_tag) 00452 { 00453 typedef iterator_traits<_IIter> _TraitsType; 00454 typedef typename _TraitsType::value_type _ValueType; 00455 return adjacent_difference(__begin, __end, __result, 00456 std::minus<_ValueType>(), 00457 __parallelism_tag); 00458 } 00459 00460 template<typename _IIter, typename _OutputIterator> 00461 inline _OutputIterator 00462 adjacent_difference(_IIter __begin, _IIter __end, 00463 _OutputIterator __result) 00464 { 00465 typedef iterator_traits<_IIter> _TraitsType; 00466 typedef typename _TraitsType::value_type _ValueType; 00467 return adjacent_difference(__begin, __end, __result, 00468 std::minus<_ValueType>()); 00469 } 00470 00471 template<typename _IIter, typename _OutputIterator, 00472 typename _BinaryOperation> 00473 inline _OutputIterator 00474 adjacent_difference(_IIter __begin, _IIter __end, 00475 _OutputIterator __result, _BinaryOperation __binary_op, 00476 __gnu_parallel::_Parallelism __parallelism_tag) 00477 { 00478 typedef iterator_traits<_IIter> _ITraitsType; 00479 typedef typename _ITraitsType::iterator_category _IIteratorCategory; 00480 00481 typedef iterator_traits<_OutputIterator> _OTraitsType; 00482 typedef typename _OTraitsType::iterator_category _OIterCategory; 00483 00484 return __adjacent_difference_switch(__begin, __end, __result, 00485 __binary_op, 00486 _IIteratorCategory(), 00487 _OIterCategory(), 00488 __parallelism_tag); 00489 } 00490 00491 template<typename _IIter, typename _OutputIterator, 00492 typename _BinaryOperation> 00493 inline _OutputIterator 00494 adjacent_difference(_IIter __begin, _IIter __end, 00495 _OutputIterator __result, _BinaryOperation __binary_op) 00496 { 00497 typedef iterator_traits<_IIter> _ITraitsType; 00498 typedef typename _ITraitsType::iterator_category _IIteratorCategory; 00499 00500 typedef iterator_traits<_OutputIterator> _OTraitsType; 00501 typedef typename _OTraitsType::iterator_category _OIterCategory; 00502 00503 return __adjacent_difference_switch(__begin, __end, __result, 00504 __binary_op, 00505 _IIteratorCategory(), 00506 _OIterCategory()); 00507 } 00508 } // end namespace 00509 } // end namespace 00510 00511 #endif /* _GLIBCXX_NUMERIC_H */