libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009, 2010 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 = __gnu_parallel::parallel_unbalanced) 00090 { 00091 if (_GLIBCXX_PARALLEL_CONDITION( 00092 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 00093 >= __gnu_parallel::_Settings::get().accumulate_minimal_n 00094 && __gnu_parallel::__is_parallel(__parallelism_tag))) 00095 { 00096 _Tp __res = __init; 00097 __gnu_parallel::__accumulate_selector<__RAIter> 00098 __my_selector; 00099 __gnu_parallel:: 00100 __for_each_template_random_access_ed(__begin, __end, 00101 __gnu_parallel::_Nothing(), 00102 __my_selector, 00103 __gnu_parallel:: 00104 __accumulate_binop_reduct 00105 <_BinaryOperation>(__binary_op), 00106 __res, __res, -1); 00107 return __res; 00108 } 00109 else 00110 return accumulate(__begin, __end, __init, __binary_op, 00111 __gnu_parallel::sequential_tag()); 00112 } 00113 00114 // Public interface. 00115 template<typename _IIter, typename _Tp> 00116 inline _Tp 00117 accumulate(_IIter __begin, _IIter __end, _Tp __init, 00118 __gnu_parallel::_Parallelism __parallelism_tag) 00119 { 00120 typedef std::iterator_traits<_IIter> _IteratorTraits; 00121 typedef typename _IteratorTraits::value_type _ValueType; 00122 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 00123 00124 return __accumulate_switch(__begin, __end, __init, 00125 __gnu_parallel::_Plus<_Tp, _ValueType>(), 00126 _IteratorCategory(), __parallelism_tag); 00127 } 00128 00129 template<typename _IIter, typename _Tp> 00130 inline _Tp 00131 accumulate(_IIter __begin, _IIter __end, _Tp __init) 00132 { 00133 typedef std::iterator_traits<_IIter> _IteratorTraits; 00134 typedef typename _IteratorTraits::value_type _ValueType; 00135 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 00136 00137 return __accumulate_switch(__begin, __end, __init, 00138 __gnu_parallel::_Plus<_Tp, _ValueType>(), 00139 _IteratorCategory()); 00140 } 00141 00142 template<typename _IIter, typename _Tp, typename _BinaryOperation> 00143 inline _Tp 00144 accumulate(_IIter __begin, _IIter __end, _Tp __init, 00145 _BinaryOperation __binary_op, 00146 __gnu_parallel::_Parallelism __parallelism_tag) 00147 { 00148 typedef iterator_traits<_IIter> _IteratorTraits; 00149 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 00150 return __accumulate_switch(__begin, __end, __init, __binary_op, 00151 _IteratorCategory(), __parallelism_tag); 00152 } 00153 00154 template<typename _IIter, typename _Tp, typename _BinaryOperation> 00155 inline _Tp 00156 accumulate(_IIter __begin, _IIter __end, _Tp __init, 00157 _BinaryOperation __binary_op) 00158 { 00159 typedef iterator_traits<_IIter> _IteratorTraits; 00160 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 00161 return __accumulate_switch(__begin, __end, __init, __binary_op, 00162 _IteratorCategory()); 00163 } 00164 00165 00166 // Sequential fallback. 00167 template<typename _IIter1, typename _IIter2, typename _Tp> 00168 inline _Tp 00169 inner_product(_IIter1 __first1, _IIter1 __last1, 00170 _IIter2 __first2, _Tp __init, 00171 __gnu_parallel::sequential_tag) 00172 { return _GLIBCXX_STD_A::inner_product( 00173 __first1, __last1, __first2, __init); } 00174 00175 template<typename _IIter1, typename _IIter2, typename _Tp, 00176 typename _BinaryFunction1, typename _BinaryFunction2> 00177 inline _Tp 00178 inner_product(_IIter1 __first1, _IIter1 __last1, 00179 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 00180 _BinaryFunction2 __binary_op2, 00181 __gnu_parallel::sequential_tag) 00182 { return _GLIBCXX_STD_A::inner_product(__first1, __last1, __first2, __init, 00183 __binary_op1, __binary_op2); } 00184 00185 // Parallel algorithm for random access iterators. 00186 template<typename _RAIter1, typename _RAIter2, 00187 typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2> 00188 _Tp 00189 __inner_product_switch(_RAIter1 __first1, 00190 _RAIter1 __last1, 00191 _RAIter2 __first2, _Tp __init, 00192 _BinaryFunction1 __binary_op1, 00193 _BinaryFunction2 __binary_op2, 00194 random_access_iterator_tag, 00195 random_access_iterator_tag, 00196 __gnu_parallel::_Parallelism __parallelism_tag 00197 = __gnu_parallel::parallel_unbalanced) 00198 { 00199 if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1) 00200 >= __gnu_parallel::_Settings::get(). 00201 accumulate_minimal_n 00202 && __gnu_parallel:: 00203 __is_parallel(__parallelism_tag))) 00204 { 00205 _Tp __res = __init; 00206 __gnu_parallel:: 00207 __inner_product_selector<_RAIter1, 00208 _RAIter2, _Tp> __my_selector(__first1, __first2); 00209 __gnu_parallel:: 00210 __for_each_template_random_access_ed( 00211 __first1, __last1, __binary_op2, __my_selector, __binary_op1, 00212 __res, __res, -1); 00213 return __res; 00214 } 00215 else 00216 return inner_product(__first1, __last1, __first2, __init, 00217 __gnu_parallel::sequential_tag()); 00218 } 00219 00220 // No parallelism for input iterators. 00221 template<typename _IIter1, typename _IIter2, typename _Tp, 00222 typename _BinaryFunction1, typename _BinaryFunction2, 00223 typename _IteratorTag1, typename _IteratorTag2> 00224 inline _Tp 00225 __inner_product_switch(_IIter1 __first1, _IIter1 __last1, 00226 _IIter2 __first2, _Tp __init, 00227 _BinaryFunction1 __binary_op1, 00228 _BinaryFunction2 __binary_op2, 00229 _IteratorTag1, _IteratorTag2) 00230 { return inner_product(__first1, __last1, __first2, __init, __binary_op1, 00231 __binary_op2, __gnu_parallel::sequential_tag()); } 00232 00233 template<typename _IIter1, typename _IIter2, typename _Tp, 00234 typename _BinaryFunction1, typename _BinaryFunction2> 00235 inline _Tp 00236 inner_product(_IIter1 __first1, _IIter1 __last1, 00237 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 00238 _BinaryFunction2 __binary_op2, 00239 __gnu_parallel::_Parallelism __parallelism_tag) 00240 { 00241 typedef iterator_traits<_IIter1> _TraitsType1; 00242 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 00243 00244 typedef iterator_traits<_IIter2> _TraitsType2; 00245 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 00246 00247 return __inner_product_switch(__first1, __last1, __first2, __init, 00248 __binary_op1, __binary_op2, 00249 _IteratorCategory1(), _IteratorCategory2(), 00250 __parallelism_tag); 00251 } 00252 00253 template<typename _IIter1, typename _IIter2, typename _Tp, 00254 typename _BinaryFunction1, typename _BinaryFunction2> 00255 inline _Tp 00256 inner_product(_IIter1 __first1, _IIter1 __last1, 00257 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 00258 _BinaryFunction2 __binary_op2) 00259 { 00260 typedef iterator_traits<_IIter1> _TraitsType1; 00261 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 00262 00263 typedef iterator_traits<_IIter2> _TraitsType2; 00264 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 00265 00266 return __inner_product_switch(__first1, __last1, __first2, __init, 00267 __binary_op1, __binary_op2, 00268 _IteratorCategory1(), 00269 _IteratorCategory2()); 00270 } 00271 00272 template<typename _IIter1, typename _IIter2, typename _Tp> 00273 inline _Tp 00274 inner_product(_IIter1 __first1, _IIter1 __last1, 00275 _IIter2 __first2, _Tp __init, 00276 __gnu_parallel::_Parallelism __parallelism_tag) 00277 { 00278 typedef iterator_traits<_IIter1> _TraitsType1; 00279 typedef typename _TraitsType1::value_type _ValueType1; 00280 typedef iterator_traits<_IIter2> _TraitsType2; 00281 typedef typename _TraitsType2::value_type _ValueType2; 00282 00283 typedef typename 00284 __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type 00285 _MultipliesResultType; 00286 return __gnu_parallel::inner_product(__first1, __last1, __first2, __init, 00287 __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(), 00288 __gnu_parallel:: 00289 _Multiplies<_ValueType1, _ValueType2>(), 00290 __parallelism_tag); 00291 } 00292 00293 template<typename _IIter1, typename _IIter2, typename _Tp> 00294 inline _Tp 00295 inner_product(_IIter1 __first1, _IIter1 __last1, 00296 _IIter2 __first2, _Tp __init) 00297 { 00298 typedef iterator_traits<_IIter1> _TraitsType1; 00299 typedef typename _TraitsType1::value_type _ValueType1; 00300 typedef iterator_traits<_IIter2> _TraitsType2; 00301 typedef typename _TraitsType2::value_type _ValueType2; 00302 00303 typedef typename 00304 __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type 00305 _MultipliesResultType; 00306 return __gnu_parallel::inner_product(__first1, __last1, __first2, __init, 00307 __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(), 00308 __gnu_parallel:: 00309 _Multiplies<_ValueType1, _ValueType2>()); 00310 } 00311 00312 // Sequential fallback. 00313 template<typename _IIter, typename _OutputIterator> 00314 inline _OutputIterator 00315 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result, 00316 __gnu_parallel::sequential_tag) 00317 { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); } 00318 00319 // Sequential fallback. 00320 template<typename _IIter, typename _OutputIterator, 00321 typename _BinaryOperation> 00322 inline _OutputIterator 00323 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result, 00324 _BinaryOperation __bin_op, __gnu_parallel::sequential_tag) 00325 { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); } 00326 00327 // Sequential fallback for input iterator case. 00328 template<typename _IIter, typename _OutputIterator, 00329 typename _BinaryOperation, typename _IteratorTag1, 00330 typename _IteratorTag2> 00331 inline _OutputIterator 00332 __partial_sum_switch(_IIter __begin, _IIter __end, 00333 _OutputIterator __result, _BinaryOperation __bin_op, 00334 _IteratorTag1, _IteratorTag2) 00335 { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); } 00336 00337 // Parallel algorithm for random access iterators. 00338 template<typename _IIter, typename _OutputIterator, 00339 typename _BinaryOperation> 00340 _OutputIterator 00341 __partial_sum_switch(_IIter __begin, _IIter __end, 00342 _OutputIterator __result, _BinaryOperation __bin_op, 00343 random_access_iterator_tag, 00344 random_access_iterator_tag) 00345 { 00346 if (_GLIBCXX_PARALLEL_CONDITION( 00347 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 00348 >= __gnu_parallel::_Settings::get().partial_sum_minimal_n)) 00349 return __gnu_parallel::__parallel_partial_sum(__begin, __end, 00350 __result, __bin_op); 00351 else 00352 return partial_sum(__begin, __end, __result, __bin_op, 00353 __gnu_parallel::sequential_tag()); 00354 } 00355 00356 // Public interface. 00357 template<typename _IIter, typename _OutputIterator> 00358 inline _OutputIterator 00359 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result) 00360 { 00361 typedef typename iterator_traits<_IIter>::value_type _ValueType; 00362 return __gnu_parallel::partial_sum(__begin, __end, 00363 __result, std::plus<_ValueType>()); 00364 } 00365 00366 // Public interface 00367 template<typename _IIter, typename _OutputIterator, 00368 typename _BinaryOperation> 00369 inline _OutputIterator 00370 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result, 00371 _BinaryOperation __binary_op) 00372 { 00373 typedef iterator_traits<_IIter> _ITraitsType; 00374 typedef typename _ITraitsType::iterator_category _IIteratorCategory; 00375 00376 typedef iterator_traits<_OutputIterator> _OTraitsType; 00377 typedef typename _OTraitsType::iterator_category _OIterCategory; 00378 00379 return __partial_sum_switch(__begin, __end, __result, __binary_op, 00380 _IIteratorCategory(), _OIterCategory()); 00381 } 00382 00383 // Sequential fallback. 00384 template<typename _IIter, typename _OutputIterator> 00385 inline _OutputIterator 00386 adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result, 00387 __gnu_parallel::sequential_tag) 00388 { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); } 00389 00390 // Sequential fallback. 00391 template<typename _IIter, typename _OutputIterator, 00392 typename _BinaryOperation> 00393 inline _OutputIterator 00394 adjacent_difference(_IIter __begin, _IIter __end, 00395 _OutputIterator __result, _BinaryOperation __bin_op, 00396 __gnu_parallel::sequential_tag) 00397 { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, 00398 __result, __bin_op); } 00399 00400 // Sequential fallback for input iterator case. 00401 template<typename _IIter, typename _OutputIterator, 00402 typename _BinaryOperation, typename _IteratorTag1, 00403 typename _IteratorTag2> 00404 inline _OutputIterator 00405 __adjacent_difference_switch(_IIter __begin, _IIter __end, 00406 _OutputIterator __result, 00407 _BinaryOperation __bin_op, _IteratorTag1, 00408 _IteratorTag2) 00409 { return adjacent_difference(__begin, __end, __result, __bin_op, 00410 __gnu_parallel::sequential_tag()); } 00411 00412 // Parallel algorithm for random access iterators. 00413 template<typename _IIter, typename _OutputIterator, 00414 typename _BinaryOperation> 00415 _OutputIterator 00416 __adjacent_difference_switch(_IIter __begin, _IIter __end, 00417 _OutputIterator __result, 00418 _BinaryOperation __bin_op, 00419 random_access_iterator_tag, 00420 random_access_iterator_tag, 00421 __gnu_parallel::_Parallelism 00422 __parallelism_tag 00423 = __gnu_parallel::parallel_balanced) 00424 { 00425 if (_GLIBCXX_PARALLEL_CONDITION( 00426 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 00427 >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n 00428 && __gnu_parallel::__is_parallel(__parallelism_tag))) 00429 { 00430 bool __dummy = true; 00431 typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator, 00432 random_access_iterator_tag> _ItTrip; 00433 *__result = *__begin; 00434 _ItTrip __begin_pair(__begin + 1, __result + 1), 00435 __end_pair(__end, __result + (__end - __begin)); 00436 __gnu_parallel::__adjacent_difference_selector<_ItTrip> 00437 __functionality; 00438 __gnu_parallel:: 00439 __for_each_template_random_access_ed( 00440 __begin_pair, __end_pair, __bin_op, __functionality, 00441 __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1); 00442 return __functionality._M_finish_iterator; 00443 } 00444 else 00445 return adjacent_difference(__begin, __end, __result, __bin_op, 00446 __gnu_parallel::sequential_tag()); 00447 } 00448 00449 // Public interface. 00450 template<typename _IIter, typename _OutputIterator> 00451 inline _OutputIterator 00452 adjacent_difference(_IIter __begin, _IIter __end, 00453 _OutputIterator __result, 00454 __gnu_parallel::_Parallelism __parallelism_tag) 00455 { 00456 typedef iterator_traits<_IIter> _TraitsType; 00457 typedef typename _TraitsType::value_type _ValueType; 00458 return adjacent_difference(__begin, __end, __result, 00459 std::minus<_ValueType>(), 00460 __parallelism_tag); 00461 } 00462 00463 template<typename _IIter, typename _OutputIterator> 00464 inline _OutputIterator 00465 adjacent_difference(_IIter __begin, _IIter __end, 00466 _OutputIterator __result) 00467 { 00468 typedef iterator_traits<_IIter> _TraitsType; 00469 typedef typename _TraitsType::value_type _ValueType; 00470 return adjacent_difference(__begin, __end, __result, 00471 std::minus<_ValueType>()); 00472 } 00473 00474 template<typename _IIter, typename _OutputIterator, 00475 typename _BinaryOperation> 00476 inline _OutputIterator 00477 adjacent_difference(_IIter __begin, _IIter __end, 00478 _OutputIterator __result, _BinaryOperation __binary_op, 00479 __gnu_parallel::_Parallelism __parallelism_tag) 00480 { 00481 typedef iterator_traits<_IIter> _ITraitsType; 00482 typedef typename _ITraitsType::iterator_category _IIteratorCategory; 00483 00484 typedef iterator_traits<_OutputIterator> _OTraitsType; 00485 typedef typename _OTraitsType::iterator_category _OIterCategory; 00486 00487 return __adjacent_difference_switch(__begin, __end, __result, 00488 __binary_op, 00489 _IIteratorCategory(), 00490 _OIterCategory(), 00491 __parallelism_tag); 00492 } 00493 00494 template<typename _IIter, typename _OutputIterator, 00495 typename _BinaryOperation> 00496 inline _OutputIterator 00497 adjacent_difference(_IIter __begin, _IIter __end, 00498 _OutputIterator __result, _BinaryOperation __binary_op) 00499 { 00500 typedef iterator_traits<_IIter> _ITraitsType; 00501 typedef typename _ITraitsType::iterator_category _IIteratorCategory; 00502 00503 typedef iterator_traits<_OutputIterator> _OTraitsType; 00504 typedef typename _OTraitsType::iterator_category _OIterCategory; 00505 00506 return __adjacent_difference_switch(__begin, __end, __result, 00507 __binary_op, 00508 _IIteratorCategory(), 00509 _OIterCategory()); 00510 } 00511 } // end namespace 00512 } // end namespace 00513 00514 #endif /* _GLIBCXX_NUMERIC_H */