libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 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 <functional> 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 00050 { 00051 namespace __parallel 00052 { 00053 // Sequential fallback. 00054 template<typename InputIterator, typename T> 00055 inline T 00056 accumulate(InputIterator begin, InputIterator end, T init, 00057 __gnu_parallel::sequential_tag) 00058 { return _GLIBCXX_STD_P::accumulate(begin, end, init); } 00059 00060 template<typename InputIterator, typename T, typename BinaryOperation> 00061 inline T 00062 accumulate(InputIterator begin, InputIterator end, T init, 00063 BinaryOperation binary_op, __gnu_parallel::sequential_tag) 00064 { return _GLIBCXX_STD_P::accumulate(begin, end, init, binary_op); } 00065 00066 // Sequential fallback for input iterator case. 00067 template<typename InputIterator, typename T, typename IteratorTag> 00068 inline T 00069 accumulate_switch(InputIterator begin, InputIterator end, 00070 T init, IteratorTag) 00071 { return accumulate(begin, end, init, __gnu_parallel::sequential_tag()); } 00072 00073 template<typename InputIterator, typename T, typename BinaryOperation, 00074 typename IteratorTag> 00075 inline T 00076 accumulate_switch(InputIterator begin, InputIterator end, T init, 00077 BinaryOperation binary_op, IteratorTag) 00078 { return accumulate(begin, end, init, binary_op, 00079 __gnu_parallel::sequential_tag()); } 00080 00081 // Parallel algorithm for random access iterators. 00082 template<typename _RandomAccessIterator, typename T, 00083 typename BinaryOperation> 00084 T 00085 accumulate_switch(_RandomAccessIterator begin, _RandomAccessIterator end, 00086 T 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::sequence_index_t>(end - begin) 00093 >= __gnu_parallel::_Settings::get().accumulate_minimal_n 00094 && __gnu_parallel::is_parallel(parallelism_tag))) 00095 { 00096 T res = init; 00097 __gnu_parallel::accumulate_selector<_RandomAccessIterator> 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 InputIterator, typename T> 00116 inline T 00117 accumulate(InputIterator begin, InputIterator end, T init, 00118 __gnu_parallel::_Parallelism parallelism_tag) 00119 { 00120 typedef std::iterator_traits<InputIterator> iterator_traits; 00121 typedef typename iterator_traits::value_type value_type; 00122 typedef typename iterator_traits::iterator_category iterator_category; 00123 00124 return accumulate_switch(begin, end, init, 00125 __gnu_parallel::plus<T, value_type>(), 00126 iterator_category(), parallelism_tag); 00127 } 00128 00129 template<typename InputIterator, typename T> 00130 inline T 00131 accumulate(InputIterator begin, InputIterator end, T init) 00132 { 00133 typedef std::iterator_traits<InputIterator> iterator_traits; 00134 typedef typename iterator_traits::value_type value_type; 00135 typedef typename iterator_traits::iterator_category iterator_category; 00136 00137 return accumulate_switch(begin, end, init, 00138 __gnu_parallel::plus<T, value_type>(), 00139 iterator_category()); 00140 } 00141 00142 template<typename InputIterator, typename T, typename BinaryOperation> 00143 inline T 00144 accumulate(InputIterator begin, InputIterator end, T init, 00145 BinaryOperation binary_op, 00146 __gnu_parallel::_Parallelism parallelism_tag) 00147 { 00148 typedef iterator_traits<InputIterator> iterator_traits; 00149 typedef typename iterator_traits::iterator_category iterator_category; 00150 return accumulate_switch(begin, end, init, binary_op, 00151 iterator_category(), parallelism_tag); 00152 } 00153 00154 template<typename InputIterator, typename T, typename BinaryOperation> 00155 inline T 00156 accumulate(InputIterator begin, InputIterator end, T init, 00157 BinaryOperation binary_op) 00158 { 00159 typedef iterator_traits<InputIterator> iterator_traits; 00160 typedef typename iterator_traits::iterator_category iterator_category; 00161 return accumulate_switch(begin, end, init, binary_op, 00162 iterator_category()); 00163 } 00164 00165 00166 // Sequential fallback. 00167 template<typename InputIterator1, typename InputIterator2, typename T> 00168 inline T 00169 inner_product(InputIterator1 first1, InputIterator1 last1, 00170 InputIterator2 first2, T init, 00171 __gnu_parallel::sequential_tag) 00172 { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init); } 00173 00174 template<typename InputIterator1, typename InputIterator2, typename T, 00175 typename BinaryFunction1, typename BinaryFunction2> 00176 inline T 00177 inner_product(InputIterator1 first1, InputIterator1 last1, 00178 InputIterator2 first2, T init, BinaryFunction1 binary_op1, 00179 BinaryFunction2 binary_op2, __gnu_parallel::sequential_tag) 00180 { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init, 00181 binary_op1, binary_op2); } 00182 00183 // Parallel algorithm for random access iterators. 00184 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00185 typename T, typename BinaryFunction1, typename BinaryFunction2> 00186 T 00187 inner_product_switch(RandomAccessIterator1 first1, 00188 RandomAccessIterator1 last1, 00189 RandomAccessIterator2 first2, T init, 00190 BinaryFunction1 binary_op1, 00191 BinaryFunction2 binary_op2, 00192 random_access_iterator_tag, 00193 random_access_iterator_tag, 00194 __gnu_parallel::_Parallelism parallelism_tag 00195 = __gnu_parallel::parallel_unbalanced) 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 T res = init; 00204 __gnu_parallel:: 00205 inner_product_selector<RandomAccessIterator1, 00206 RandomAccessIterator2, T> my_selector(first1, first2); 00207 __gnu_parallel:: 00208 for_each_template_random_access_ed(first1, last1, binary_op2, 00209 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 InputIterator1, typename InputIterator2, typename T, 00220 typename BinaryFunction1, typename BinaryFunction2, 00221 typename IteratorTag1, typename IteratorTag2> 00222 inline T 00223 inner_product_switch(InputIterator1 first1, InputIterator1 last1, 00224 InputIterator2 first2, T init, 00225 BinaryFunction1 binary_op1, 00226 BinaryFunction2 binary_op2, 00227 IteratorTag1, IteratorTag2) 00228 { return inner_product(first1, last1, first2, init, 00229 binary_op1, binary_op2, 00230 __gnu_parallel::sequential_tag()); } 00231 00232 template<typename InputIterator1, typename InputIterator2, typename T, 00233 typename BinaryFunction1, typename BinaryFunction2> 00234 inline T 00235 inner_product(InputIterator1 first1, InputIterator1 last1, 00236 InputIterator2 first2, T init, BinaryFunction1 binary_op1, 00237 BinaryFunction2 binary_op2, 00238 __gnu_parallel::_Parallelism parallelism_tag) 00239 { 00240 typedef iterator_traits<InputIterator1> traits1_type; 00241 typedef typename traits1_type::iterator_category iterator1_category; 00242 00243 typedef iterator_traits<InputIterator2> traits2_type; 00244 typedef typename traits2_type::iterator_category iterator2_category; 00245 00246 return inner_product_switch(first1, last1, first2, init, binary_op1, 00247 binary_op2, iterator1_category(), 00248 iterator2_category(), parallelism_tag); 00249 } 00250 00251 template<typename InputIterator1, typename InputIterator2, typename T, 00252 typename BinaryFunction1, typename BinaryFunction2> 00253 inline T 00254 inner_product(InputIterator1 first1, InputIterator1 last1, 00255 InputIterator2 first2, T init, BinaryFunction1 binary_op1, 00256 BinaryFunction2 binary_op2) 00257 { 00258 typedef iterator_traits<InputIterator1> traits1_type; 00259 typedef typename traits1_type::iterator_category iterator1_category; 00260 00261 typedef iterator_traits<InputIterator2> traits2_type; 00262 typedef typename traits2_type::iterator_category iterator2_category; 00263 00264 return inner_product_switch(first1, last1, first2, init, binary_op1, 00265 binary_op2, iterator1_category(), 00266 iterator2_category()); 00267 } 00268 00269 template<typename InputIterator1, typename InputIterator2, typename T> 00270 inline T 00271 inner_product(InputIterator1 first1, InputIterator1 last1, 00272 InputIterator2 first2, T init, 00273 __gnu_parallel::_Parallelism parallelism_tag) 00274 { 00275 typedef iterator_traits<InputIterator1> traits_type1; 00276 typedef typename traits_type1::value_type value_type1; 00277 typedef iterator_traits<InputIterator2> traits_type2; 00278 typedef typename traits_type2::value_type value_type2; 00279 00280 typedef typename 00281 __gnu_parallel::multiplies<value_type1, value_type2>::result 00282 multiplies_result_type; 00283 return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init, 00284 __gnu_parallel::plus<T, multiplies_result_type>(), 00285 __gnu_parallel:: 00286 multiplies<value_type1, value_type2>(), 00287 parallelism_tag); 00288 } 00289 00290 template<typename InputIterator1, typename InputIterator2, typename T> 00291 inline T 00292 inner_product(InputIterator1 first1, InputIterator1 last1, 00293 InputIterator2 first2, T init) 00294 { 00295 typedef iterator_traits<InputIterator1> traits_type1; 00296 typedef typename traits_type1::value_type value_type1; 00297 typedef iterator_traits<InputIterator2> traits_type2; 00298 typedef typename traits_type2::value_type value_type2; 00299 00300 typedef typename 00301 __gnu_parallel::multiplies<value_type1, value_type2>::result 00302 multiplies_result_type; 00303 return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init, 00304 __gnu_parallel::plus<T, multiplies_result_type>(), 00305 __gnu_parallel:: 00306 multiplies<value_type1, value_type2>()); 00307 } 00308 00309 // Sequential fallback. 00310 template<typename InputIterator, typename OutputIterator> 00311 inline OutputIterator 00312 partial_sum(InputIterator begin, InputIterator end, OutputIterator result, 00313 __gnu_parallel::sequential_tag) 00314 { return _GLIBCXX_STD_P::partial_sum(begin, end, result); } 00315 00316 // Sequential fallback. 00317 template<typename InputIterator, typename OutputIterator, 00318 typename BinaryOperation> 00319 inline OutputIterator 00320 partial_sum(InputIterator begin, InputIterator end, OutputIterator result, 00321 BinaryOperation bin_op, __gnu_parallel::sequential_tag) 00322 { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); } 00323 00324 // Sequential fallback for input iterator case. 00325 template<typename InputIterator, typename OutputIterator, 00326 typename BinaryOperation, typename IteratorTag1, 00327 typename IteratorTag2> 00328 inline OutputIterator 00329 partial_sum_switch(InputIterator begin, InputIterator end, 00330 OutputIterator result, BinaryOperation bin_op, 00331 IteratorTag1, IteratorTag2) 00332 { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); } 00333 00334 // Parallel algorithm for random access iterators. 00335 template<typename InputIterator, typename OutputIterator, 00336 typename BinaryOperation> 00337 OutputIterator 00338 partial_sum_switch(InputIterator begin, InputIterator end, 00339 OutputIterator result, BinaryOperation bin_op, 00340 random_access_iterator_tag, random_access_iterator_tag) 00341 { 00342 if (_GLIBCXX_PARALLEL_CONDITION( 00343 static_cast<__gnu_parallel::sequence_index_t>(end - begin) 00344 >= __gnu_parallel::_Settings::get().partial_sum_minimal_n)) 00345 return __gnu_parallel::parallel_partial_sum(begin, end, 00346 result, bin_op); 00347 else 00348 return partial_sum(begin, end, result, bin_op, 00349 __gnu_parallel::sequential_tag()); 00350 } 00351 00352 // Public interface. 00353 template<typename InputIterator, typename OutputIterator> 00354 inline OutputIterator 00355 partial_sum(InputIterator begin, InputIterator end, OutputIterator result) 00356 { 00357 typedef typename iterator_traits<InputIterator>::value_type value_type; 00358 return _GLIBCXX_STD_P::partial_sum(begin, end, result, 00359 std::plus<value_type>()); 00360 } 00361 00362 // Public interface 00363 template<typename InputIterator, typename OutputIterator, 00364 typename BinaryOperation> 00365 inline OutputIterator 00366 partial_sum(InputIterator begin, InputIterator end, OutputIterator result, 00367 BinaryOperation binary_op) 00368 { 00369 typedef iterator_traits<InputIterator> traitsi_type; 00370 typedef typename traitsi_type::iterator_category iteratori_category; 00371 00372 typedef iterator_traits<OutputIterator> traitso_type; 00373 typedef typename traitso_type::iterator_category iteratoro_category; 00374 00375 return partial_sum_switch(begin, end, result, binary_op, 00376 iteratori_category(), iteratoro_category()); 00377 } 00378 00379 // Sequential fallback. 00380 template<typename InputIterator, typename OutputIterator> 00381 inline OutputIterator 00382 adjacent_difference(InputIterator begin, InputIterator end, 00383 OutputIterator result, __gnu_parallel::sequential_tag) 00384 { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); } 00385 00386 // Sequential fallback. 00387 template<typename InputIterator, typename OutputIterator, 00388 typename BinaryOperation> 00389 inline OutputIterator 00390 adjacent_difference(InputIterator begin, InputIterator end, 00391 OutputIterator result, BinaryOperation bin_op, 00392 __gnu_parallel::sequential_tag) 00393 { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op); } 00394 00395 // Sequential fallback for input iterator case. 00396 template<typename InputIterator, typename OutputIterator, 00397 typename BinaryOperation, typename IteratorTag1, 00398 typename IteratorTag2> 00399 inline OutputIterator 00400 adjacent_difference_switch(InputIterator begin, InputIterator end, 00401 OutputIterator result, BinaryOperation bin_op, 00402 IteratorTag1, IteratorTag2) 00403 { return adjacent_difference(begin, end, result, bin_op, 00404 __gnu_parallel::sequential_tag()); } 00405 00406 // Parallel algorithm for random access iterators. 00407 template<typename InputIterator, typename OutputIterator, 00408 typename BinaryOperation> 00409 OutputIterator 00410 adjacent_difference_switch(InputIterator begin, InputIterator end, 00411 OutputIterator result, BinaryOperation bin_op, 00412 random_access_iterator_tag, 00413 random_access_iterator_tag, 00414 __gnu_parallel::_Parallelism parallelism_tag 00415 = __gnu_parallel::parallel_balanced) 00416 { 00417 if (_GLIBCXX_PARALLEL_CONDITION( 00418 static_cast<__gnu_parallel::sequence_index_t>(end - begin) 00419 >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n 00420 && __gnu_parallel::is_parallel(parallelism_tag))) 00421 { 00422 bool dummy = true; 00423 typedef __gnu_parallel::iterator_pair<InputIterator, OutputIterator, 00424 random_access_iterator_tag> ip; 00425 *result = *begin; 00426 ip begin_pair(begin + 1, result + 1), 00427 end_pair(end, result + (end - begin)); 00428 __gnu_parallel::adjacent_difference_selector<ip> functionality; 00429 __gnu_parallel:: 00430 for_each_template_random_access_ed(begin_pair, end_pair, bin_op, 00431 functionality, 00432 __gnu_parallel::dummy_reduct(), 00433 dummy, dummy, -1); 00434 return functionality.finish_iterator; 00435 } 00436 else 00437 return adjacent_difference(begin, end, result, bin_op, 00438 __gnu_parallel::sequential_tag()); 00439 } 00440 00441 // Public interface. 00442 template<typename InputIterator, typename OutputIterator> 00443 inline OutputIterator 00444 adjacent_difference(InputIterator begin, InputIterator end, 00445 OutputIterator result, 00446 __gnu_parallel::_Parallelism parallelism_tag) 00447 { 00448 typedef iterator_traits<InputIterator> traits_type; 00449 typedef typename traits_type::value_type value_type; 00450 return adjacent_difference(begin, end, result, std::minus<value_type>(), 00451 parallelism_tag); 00452 } 00453 00454 template<typename InputIterator, typename OutputIterator> 00455 inline OutputIterator 00456 adjacent_difference(InputIterator begin, InputIterator end, 00457 OutputIterator result) 00458 { 00459 typedef iterator_traits<InputIterator> traits_type; 00460 typedef typename traits_type::value_type value_type; 00461 return adjacent_difference(begin, end, result, std::minus<value_type>()); 00462 } 00463 00464 template<typename InputIterator, typename OutputIterator, 00465 typename BinaryOperation> 00466 inline OutputIterator 00467 adjacent_difference(InputIterator begin, InputIterator end, 00468 OutputIterator result, BinaryOperation binary_op, 00469 __gnu_parallel::_Parallelism parallelism_tag) 00470 { 00471 typedef iterator_traits<InputIterator> traitsi_type; 00472 typedef typename traitsi_type::iterator_category iteratori_category; 00473 00474 typedef iterator_traits<OutputIterator> traitso_type; 00475 typedef typename traitso_type::iterator_category iteratoro_category; 00476 00477 return adjacent_difference_switch(begin, end, result, binary_op, 00478 iteratori_category(), 00479 iteratoro_category(), parallelism_tag); 00480 } 00481 00482 template<typename InputIterator, typename OutputIterator, 00483 typename BinaryOperation> 00484 inline OutputIterator 00485 adjacent_difference(InputIterator begin, InputIterator end, 00486 OutputIterator result, BinaryOperation binary_op) 00487 { 00488 typedef iterator_traits<InputIterator> traitsi_type; 00489 typedef typename traitsi_type::iterator_category iteratori_category; 00490 00491 typedef iterator_traits<OutputIterator> traitso_type; 00492 typedef typename traitso_type::iterator_category iteratoro_category; 00493 00494 return adjacent_difference_switch(begin, end, result, binary_op, 00495 iteratori_category(), 00496 iteratoro_category()); 00497 } 00498 } // end namespace 00499 } // end namespace 00500 00501 #endif /* _GLIBCXX_NUMERIC_H */