libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007-2017 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 /** @file parallel/algo.h 00026 * @brief Parallel STL function calls corresponding to the stl_algo.h header. 00027 * 00028 * The functions defined here mainly do case switches and 00029 * call the actual parallelized versions in other files. 00030 * Inlining policy: Functions that basically only contain one function call, 00031 * are declared inline. 00032 * This file is a GNU parallel extension to the Standard C++ Library. 00033 */ 00034 00035 // Written by Johannes Singler and Felix Putze. 00036 00037 #ifndef _GLIBCXX_PARALLEL_ALGO_H 00038 #define _GLIBCXX_PARALLEL_ALGO_H 1 00039 00040 #include <parallel/algorithmfwd.h> 00041 #include <bits/stl_algobase.h> 00042 #include <bits/stl_algo.h> 00043 #include <parallel/iterator.h> 00044 #include <parallel/base.h> 00045 #include <parallel/sort.h> 00046 #include <parallel/workstealing.h> 00047 #include <parallel/par_loop.h> 00048 #include <parallel/omp_loop.h> 00049 #include <parallel/omp_loop_static.h> 00050 #include <parallel/for_each_selectors.h> 00051 #include <parallel/for_each.h> 00052 #include <parallel/find.h> 00053 #include <parallel/find_selectors.h> 00054 #include <parallel/search.h> 00055 #include <parallel/random_shuffle.h> 00056 #include <parallel/partition.h> 00057 #include <parallel/merge.h> 00058 #include <parallel/unique_copy.h> 00059 #include <parallel/set_operations.h> 00060 00061 namespace std _GLIBCXX_VISIBILITY(default) 00062 { 00063 namespace __parallel 00064 { 00065 // Sequential fallback 00066 template<typename _IIter, typename _Function> 00067 inline _Function 00068 for_each(_IIter __begin, _IIter __end, _Function __f, 00069 __gnu_parallel::sequential_tag) 00070 { return _GLIBCXX_STD_A::for_each(__begin, __end, __f); } 00071 00072 // Sequential fallback for input iterator case 00073 template<typename _IIter, typename _Function, typename _IteratorTag> 00074 inline _Function 00075 __for_each_switch(_IIter __begin, _IIter __end, _Function __f, 00076 _IteratorTag) 00077 { return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag()); } 00078 00079 // Parallel algorithm for random access iterators 00080 template<typename _RAIter, typename _Function> 00081 _Function 00082 __for_each_switch(_RAIter __begin, _RAIter __end, 00083 _Function __f, random_access_iterator_tag, 00084 __gnu_parallel::_Parallelism __parallelism_tag) 00085 { 00086 if (_GLIBCXX_PARALLEL_CONDITION( 00087 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 00088 >= __gnu_parallel::_Settings::get().for_each_minimal_n 00089 && __gnu_parallel::__is_parallel(__parallelism_tag))) 00090 { 00091 bool __dummy; 00092 __gnu_parallel::__for_each_selector<_RAIter> __functionality; 00093 00094 return __gnu_parallel:: 00095 __for_each_template_random_access( 00096 __begin, __end, __f, __functionality, 00097 __gnu_parallel::_DummyReduct(), true, __dummy, -1, 00098 __parallelism_tag); 00099 } 00100 else 00101 return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag()); 00102 } 00103 00104 // Public interface 00105 template<typename _Iterator, typename _Function> 00106 inline _Function 00107 for_each(_Iterator __begin, _Iterator __end, _Function __f, 00108 __gnu_parallel::_Parallelism __parallelism_tag) 00109 { 00110 return __for_each_switch(__begin, __end, __f, 00111 std::__iterator_category(__begin), 00112 __parallelism_tag); 00113 } 00114 00115 template<typename _Iterator, typename _Function> 00116 inline _Function 00117 for_each(_Iterator __begin, _Iterator __end, _Function __f) 00118 { 00119 return __for_each_switch(__begin, __end, __f, 00120 std::__iterator_category(__begin)); 00121 } 00122 00123 // Sequential fallback 00124 template<typename _IIter, typename _Tp> 00125 inline _IIter 00126 find(_IIter __begin, _IIter __end, const _Tp& __val, 00127 __gnu_parallel::sequential_tag) 00128 { return _GLIBCXX_STD_A::find(__begin, __end, __val); } 00129 00130 // Sequential fallback for input iterator case 00131 template<typename _IIter, typename _Tp, typename _IteratorTag> 00132 inline _IIter 00133 __find_switch(_IIter __begin, _IIter __end, const _Tp& __val, 00134 _IteratorTag) 00135 { return _GLIBCXX_STD_A::find(__begin, __end, __val); } 00136 00137 // Parallel find for random access iterators 00138 template<typename _RAIter, typename _Tp> 00139 _RAIter 00140 __find_switch(_RAIter __begin, _RAIter __end, 00141 const _Tp& __val, random_access_iterator_tag) 00142 { 00143 typedef iterator_traits<_RAIter> _TraitsType; 00144 typedef typename _TraitsType::value_type _ValueType; 00145 00146 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00147 { 00148 __gnu_parallel::__binder2nd<__gnu_parallel::_EqualTo<_ValueType, 00149 const _Tp&>, 00150 _ValueType, const _Tp&, bool> 00151 __comp(__gnu_parallel::_EqualTo<_ValueType, const _Tp&>(), __val); 00152 return __gnu_parallel::__find_template( 00153 __begin, __end, __begin, __comp, 00154 __gnu_parallel::__find_if_selector()).first; 00155 } 00156 else 00157 return _GLIBCXX_STD_A::find(__begin, __end, __val); 00158 } 00159 00160 // Public interface 00161 template<typename _IIter, typename _Tp> 00162 inline _IIter 00163 find(_IIter __begin, _IIter __end, const _Tp& __val) 00164 { 00165 return __find_switch(__begin, __end, __val, 00166 std::__iterator_category(__begin)); 00167 } 00168 00169 // Sequential fallback 00170 template<typename _IIter, typename _Predicate> 00171 inline _IIter 00172 find_if(_IIter __begin, _IIter __end, _Predicate __pred, 00173 __gnu_parallel::sequential_tag) 00174 { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); } 00175 00176 // Sequential fallback for input iterator case 00177 template<typename _IIter, typename _Predicate, typename _IteratorTag> 00178 inline _IIter 00179 __find_if_switch(_IIter __begin, _IIter __end, _Predicate __pred, 00180 _IteratorTag) 00181 { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); } 00182 00183 // Parallel find_if for random access iterators 00184 template<typename _RAIter, typename _Predicate> 00185 _RAIter 00186 __find_if_switch(_RAIter __begin, _RAIter __end, 00187 _Predicate __pred, random_access_iterator_tag) 00188 { 00189 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00190 return __gnu_parallel::__find_template(__begin, __end, __begin, __pred, 00191 __gnu_parallel:: 00192 __find_if_selector()).first; 00193 else 00194 return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); 00195 } 00196 00197 // Public interface 00198 template<typename _IIter, typename _Predicate> 00199 inline _IIter 00200 find_if(_IIter __begin, _IIter __end, _Predicate __pred) 00201 { 00202 return __find_if_switch(__begin, __end, __pred, 00203 std::__iterator_category(__begin)); 00204 } 00205 00206 // Sequential fallback 00207 template<typename _IIter, typename _FIterator> 00208 inline _IIter 00209 find_first_of(_IIter __begin1, _IIter __end1, 00210 _FIterator __begin2, _FIterator __end2, 00211 __gnu_parallel::sequential_tag) 00212 { 00213 return _GLIBCXX_STD_A::find_first_of(__begin1, __end1, __begin2, __end2); 00214 } 00215 00216 // Sequential fallback 00217 template<typename _IIter, typename _FIterator, 00218 typename _BinaryPredicate> 00219 inline _IIter 00220 find_first_of(_IIter __begin1, _IIter __end1, 00221 _FIterator __begin2, _FIterator __end2, 00222 _BinaryPredicate __comp, __gnu_parallel::sequential_tag) 00223 { return _GLIBCXX_STD_A::find_first_of( 00224 __begin1, __end1, __begin2, __end2, __comp); } 00225 00226 // Sequential fallback for input iterator type 00227 template<typename _IIter, typename _FIterator, 00228 typename _IteratorTag1, typename _IteratorTag2> 00229 inline _IIter 00230 __find_first_of_switch(_IIter __begin1, _IIter __end1, 00231 _FIterator __begin2, _FIterator __end2, 00232 _IteratorTag1, _IteratorTag2) 00233 { return find_first_of(__begin1, __end1, __begin2, __end2, 00234 __gnu_parallel::sequential_tag()); } 00235 00236 // Parallel algorithm for random access iterators 00237 template<typename _RAIter, typename _FIterator, 00238 typename _BinaryPredicate, typename _IteratorTag> 00239 inline _RAIter 00240 __find_first_of_switch(_RAIter __begin1, 00241 _RAIter __end1, 00242 _FIterator __begin2, _FIterator __end2, 00243 _BinaryPredicate __comp, random_access_iterator_tag, 00244 _IteratorTag) 00245 { 00246 return __gnu_parallel:: 00247 __find_template(__begin1, __end1, __begin1, __comp, 00248 __gnu_parallel::__find_first_of_selector 00249 <_FIterator>(__begin2, __end2)).first; 00250 } 00251 00252 // Sequential fallback for input iterator type 00253 template<typename _IIter, typename _FIterator, 00254 typename _BinaryPredicate, typename _IteratorTag1, 00255 typename _IteratorTag2> 00256 inline _IIter 00257 __find_first_of_switch(_IIter __begin1, _IIter __end1, 00258 _FIterator __begin2, _FIterator __end2, 00259 _BinaryPredicate __comp, _IteratorTag1, _IteratorTag2) 00260 { return find_first_of(__begin1, __end1, __begin2, __end2, __comp, 00261 __gnu_parallel::sequential_tag()); } 00262 00263 // Public interface 00264 template<typename _IIter, typename _FIterator, 00265 typename _BinaryPredicate> 00266 inline _IIter 00267 find_first_of(_IIter __begin1, _IIter __end1, 00268 _FIterator __begin2, _FIterator __end2, 00269 _BinaryPredicate __comp) 00270 { 00271 return __find_first_of_switch(__begin1, __end1, __begin2, __end2, __comp, 00272 std::__iterator_category(__begin1), 00273 std::__iterator_category(__begin2)); 00274 } 00275 00276 // Public interface, insert default comparator 00277 template<typename _IIter, typename _FIterator> 00278 inline _IIter 00279 find_first_of(_IIter __begin1, _IIter __end1, 00280 _FIterator __begin2, _FIterator __end2) 00281 { 00282 typedef typename std::iterator_traits<_IIter>::value_type _IValueType; 00283 typedef typename std::iterator_traits<_FIterator>::value_type _FValueType; 00284 00285 return __gnu_parallel::find_first_of(__begin1, __end1, __begin2, __end2, 00286 __gnu_parallel::_EqualTo<_IValueType, _FValueType>()); 00287 } 00288 00289 // Sequential fallback 00290 template<typename _IIter, typename _OutputIterator> 00291 inline _OutputIterator 00292 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out, 00293 __gnu_parallel::sequential_tag) 00294 { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out); } 00295 00296 // Sequential fallback 00297 template<typename _IIter, typename _OutputIterator, 00298 typename _Predicate> 00299 inline _OutputIterator 00300 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out, 00301 _Predicate __pred, __gnu_parallel::sequential_tag) 00302 { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out, __pred); } 00303 00304 // Sequential fallback for input iterator case 00305 template<typename _IIter, typename _OutputIterator, 00306 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 00307 inline _OutputIterator 00308 __unique_copy_switch(_IIter __begin, _IIter __last, 00309 _OutputIterator __out, _Predicate __pred, 00310 _IteratorTag1, _IteratorTag2) 00311 { return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred); } 00312 00313 // Parallel unique_copy for random access iterators 00314 template<typename _RAIter, typename RandomAccessOutputIterator, 00315 typename _Predicate> 00316 RandomAccessOutputIterator 00317 __unique_copy_switch(_RAIter __begin, _RAIter __last, 00318 RandomAccessOutputIterator __out, _Predicate __pred, 00319 random_access_iterator_tag, random_access_iterator_tag) 00320 { 00321 if (_GLIBCXX_PARALLEL_CONDITION( 00322 static_cast<__gnu_parallel::_SequenceIndex>(__last - __begin) 00323 > __gnu_parallel::_Settings::get().unique_copy_minimal_n)) 00324 return __gnu_parallel::__parallel_unique_copy( 00325 __begin, __last, __out, __pred); 00326 else 00327 return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred); 00328 } 00329 00330 // Public interface 00331 template<typename _IIter, typename _OutputIterator> 00332 inline _OutputIterator 00333 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out) 00334 { 00335 typedef typename std::iterator_traits<_IIter>::value_type _ValueType; 00336 00337 return __unique_copy_switch( 00338 __begin1, __end1, __out, equal_to<_ValueType>(), 00339 std::__iterator_category(__begin1), 00340 std::__iterator_category(__out)); 00341 } 00342 00343 // Public interface 00344 template<typename _IIter, typename _OutputIterator, typename _Predicate> 00345 inline _OutputIterator 00346 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out, 00347 _Predicate __pred) 00348 { 00349 return __unique_copy_switch( 00350 __begin1, __end1, __out, __pred, 00351 std::__iterator_category(__begin1), 00352 std::__iterator_category(__out)); 00353 } 00354 00355 // Sequential fallback 00356 template<typename _IIter1, typename _IIter2, 00357 typename _OutputIterator> 00358 inline _OutputIterator 00359 set_union(_IIter1 __begin1, _IIter1 __end1, 00360 _IIter2 __begin2, _IIter2 __end2, 00361 _OutputIterator __out, __gnu_parallel::sequential_tag) 00362 { return _GLIBCXX_STD_A::set_union( 00363 __begin1, __end1, __begin2, __end2, __out); } 00364 00365 // Sequential fallback 00366 template<typename _IIter1, typename _IIter2, 00367 typename _OutputIterator, typename _Predicate> 00368 inline _OutputIterator 00369 set_union(_IIter1 __begin1, _IIter1 __end1, 00370 _IIter2 __begin2, _IIter2 __end2, 00371 _OutputIterator __out, _Predicate __pred, 00372 __gnu_parallel::sequential_tag) 00373 { return _GLIBCXX_STD_A::set_union(__begin1, __end1, 00374 __begin2, __end2, __out, __pred); } 00375 00376 // Sequential fallback for input iterator case 00377 template<typename _IIter1, typename _IIter2, typename _Predicate, 00378 typename _OutputIterator, typename _IteratorTag1, 00379 typename _IteratorTag2, typename _IteratorTag3> 00380 inline _OutputIterator 00381 __set_union_switch( 00382 _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2, 00383 _OutputIterator __result, _Predicate __pred, 00384 _IteratorTag1, _IteratorTag2, _IteratorTag3) 00385 { return _GLIBCXX_STD_A::set_union(__begin1, __end1, 00386 __begin2, __end2, __result, __pred); } 00387 00388 // Parallel set_union for random access iterators 00389 template<typename _RAIter1, typename _RAIter2, 00390 typename _Output_RAIter, typename _Predicate> 00391 _Output_RAIter 00392 __set_union_switch(_RAIter1 __begin1, _RAIter1 __end1, 00393 _RAIter2 __begin2, _RAIter2 __end2, 00394 _Output_RAIter __result, _Predicate __pred, 00395 random_access_iterator_tag, random_access_iterator_tag, 00396 random_access_iterator_tag) 00397 { 00398 if (_GLIBCXX_PARALLEL_CONDITION( 00399 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 00400 >= __gnu_parallel::_Settings::get().set_union_minimal_n 00401 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) 00402 >= __gnu_parallel::_Settings::get().set_union_minimal_n)) 00403 return __gnu_parallel::__parallel_set_union( 00404 __begin1, __end1, __begin2, __end2, __result, __pred); 00405 else 00406 return _GLIBCXX_STD_A::set_union(__begin1, __end1, 00407 __begin2, __end2, __result, __pred); 00408 } 00409 00410 // Public interface 00411 template<typename _IIter1, typename _IIter2, 00412 typename _OutputIterator> 00413 inline _OutputIterator 00414 set_union(_IIter1 __begin1, _IIter1 __end1, 00415 _IIter2 __begin2, _IIter2 __end2, _OutputIterator __out) 00416 { 00417 typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1; 00418 typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2; 00419 00420 return __set_union_switch( 00421 __begin1, __end1, __begin2, __end2, __out, 00422 __gnu_parallel::_Less<_ValueType1, _ValueType2>(), 00423 std::__iterator_category(__begin1), 00424 std::__iterator_category(__begin2), 00425 std::__iterator_category(__out)); 00426 } 00427 00428 // Public interface 00429 template<typename _IIter1, typename _IIter2, 00430 typename _OutputIterator, typename _Predicate> 00431 inline _OutputIterator 00432 set_union(_IIter1 __begin1, _IIter1 __end1, 00433 _IIter2 __begin2, _IIter2 __end2, 00434 _OutputIterator __out, _Predicate __pred) 00435 { 00436 return __set_union_switch( 00437 __begin1, __end1, __begin2, __end2, __out, __pred, 00438 std::__iterator_category(__begin1), 00439 std::__iterator_category(__begin2), 00440 std::__iterator_category(__out)); 00441 } 00442 00443 // Sequential fallback. 00444 template<typename _IIter1, typename _IIter2, 00445 typename _OutputIterator> 00446 inline _OutputIterator 00447 set_intersection(_IIter1 __begin1, _IIter1 __end1, 00448 _IIter2 __begin2, _IIter2 __end2, 00449 _OutputIterator __out, __gnu_parallel::sequential_tag) 00450 { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1, 00451 __begin2, __end2, __out); } 00452 00453 // Sequential fallback. 00454 template<typename _IIter1, typename _IIter2, 00455 typename _OutputIterator, typename _Predicate> 00456 inline _OutputIterator 00457 set_intersection(_IIter1 __begin1, _IIter1 __end1, 00458 _IIter2 __begin2, _IIter2 __end2, 00459 _OutputIterator __out, _Predicate __pred, 00460 __gnu_parallel::sequential_tag) 00461 { return _GLIBCXX_STD_A::set_intersection( 00462 __begin1, __end1, __begin2, __end2, __out, __pred); } 00463 00464 // Sequential fallback for input iterator case 00465 template<typename _IIter1, typename _IIter2, 00466 typename _Predicate, typename _OutputIterator, 00467 typename _IteratorTag1, typename _IteratorTag2, 00468 typename _IteratorTag3> 00469 inline _OutputIterator 00470 __set_intersection_switch(_IIter1 __begin1, _IIter1 __end1, 00471 _IIter2 __begin2, _IIter2 __end2, 00472 _OutputIterator __result, _Predicate __pred, 00473 _IteratorTag1, _IteratorTag2, _IteratorTag3) 00474 { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1, __begin2, 00475 __end2, __result, __pred); } 00476 00477 // Parallel set_intersection for random access iterators 00478 template<typename _RAIter1, typename _RAIter2, 00479 typename _Output_RAIter, typename _Predicate> 00480 _Output_RAIter 00481 __set_intersection_switch(_RAIter1 __begin1, 00482 _RAIter1 __end1, 00483 _RAIter2 __begin2, 00484 _RAIter2 __end2, 00485 _Output_RAIter __result, 00486 _Predicate __pred, 00487 random_access_iterator_tag, 00488 random_access_iterator_tag, 00489 random_access_iterator_tag) 00490 { 00491 if (_GLIBCXX_PARALLEL_CONDITION( 00492 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 00493 >= __gnu_parallel::_Settings::get().set_union_minimal_n 00494 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) 00495 >= __gnu_parallel::_Settings::get().set_union_minimal_n)) 00496 return __gnu_parallel::__parallel_set_intersection( 00497 __begin1, __end1, __begin2, __end2, __result, __pred); 00498 else 00499 return _GLIBCXX_STD_A::set_intersection( 00500 __begin1, __end1, __begin2, __end2, __result, __pred); 00501 } 00502 00503 // Public interface 00504 template<typename _IIter1, typename _IIter2, 00505 typename _OutputIterator> 00506 inline _OutputIterator 00507 set_intersection(_IIter1 __begin1, _IIter1 __end1, 00508 _IIter2 __begin2, _IIter2 __end2, 00509 _OutputIterator __out) 00510 { 00511 typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1; 00512 typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2; 00513 00514 return __set_intersection_switch( 00515 __begin1, __end1, __begin2, __end2, __out, 00516 __gnu_parallel::_Less<_ValueType1, _ValueType2>(), 00517 std::__iterator_category(__begin1), 00518 std::__iterator_category(__begin2), 00519 std::__iterator_category(__out)); 00520 } 00521 00522 template<typename _IIter1, typename _IIter2, 00523 typename _OutputIterator, typename _Predicate> 00524 inline _OutputIterator 00525 set_intersection(_IIter1 __begin1, _IIter1 __end1, 00526 _IIter2 __begin2, _IIter2 __end2, 00527 _OutputIterator __out, _Predicate __pred) 00528 { 00529 return __set_intersection_switch( 00530 __begin1, __end1, __begin2, __end2, __out, __pred, 00531 std::__iterator_category(__begin1), 00532 std::__iterator_category(__begin2), 00533 std::__iterator_category(__out)); 00534 } 00535 00536 // Sequential fallback 00537 template<typename _IIter1, typename _IIter2, 00538 typename _OutputIterator> 00539 inline _OutputIterator 00540 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1, 00541 _IIter2 __begin2, _IIter2 __end2, 00542 _OutputIterator __out, 00543 __gnu_parallel::sequential_tag) 00544 { return _GLIBCXX_STD_A::set_symmetric_difference( 00545 __begin1, __end1, __begin2, __end2, __out); } 00546 00547 // Sequential fallback 00548 template<typename _IIter1, typename _IIter2, 00549 typename _OutputIterator, typename _Predicate> 00550 inline _OutputIterator 00551 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1, 00552 _IIter2 __begin2, _IIter2 __end2, 00553 _OutputIterator __out, _Predicate __pred, 00554 __gnu_parallel::sequential_tag) 00555 { return _GLIBCXX_STD_A::set_symmetric_difference( 00556 __begin1, __end1, __begin2, __end2, __out, __pred); } 00557 00558 // Sequential fallback for input iterator case 00559 template<typename _IIter1, typename _IIter2, 00560 typename _Predicate, typename _OutputIterator, 00561 typename _IteratorTag1, typename _IteratorTag2, 00562 typename _IteratorTag3> 00563 inline _OutputIterator 00564 __set_symmetric_difference_switch( 00565 _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2, 00566 _OutputIterator __result, _Predicate __pred, 00567 _IteratorTag1, _IteratorTag2, _IteratorTag3) 00568 { return _GLIBCXX_STD_A::set_symmetric_difference( 00569 __begin1, __end1, __begin2, __end2, __result, __pred); } 00570 00571 // Parallel set_symmetric_difference for random access iterators 00572 template<typename _RAIter1, typename _RAIter2, 00573 typename _Output_RAIter, typename _Predicate> 00574 _Output_RAIter 00575 __set_symmetric_difference_switch(_RAIter1 __begin1, 00576 _RAIter1 __end1, 00577 _RAIter2 __begin2, 00578 _RAIter2 __end2, 00579 _Output_RAIter __result, 00580 _Predicate __pred, 00581 random_access_iterator_tag, 00582 random_access_iterator_tag, 00583 random_access_iterator_tag) 00584 { 00585 if (_GLIBCXX_PARALLEL_CONDITION( 00586 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 00587 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n 00588 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) 00589 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n)) 00590 return __gnu_parallel::__parallel_set_symmetric_difference( 00591 __begin1, __end1, __begin2, __end2, __result, __pred); 00592 else 00593 return _GLIBCXX_STD_A::set_symmetric_difference( 00594 __begin1, __end1, __begin2, __end2, __result, __pred); 00595 } 00596 00597 // Public interface. 00598 template<typename _IIter1, typename _IIter2, 00599 typename _OutputIterator> 00600 inline _OutputIterator 00601 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1, 00602 _IIter2 __begin2, _IIter2 __end2, 00603 _OutputIterator __out) 00604 { 00605 typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1; 00606 typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2; 00607 00608 return __set_symmetric_difference_switch( 00609 __begin1, __end1, __begin2, __end2, __out, 00610 __gnu_parallel::_Less<_ValueType1, _ValueType2>(), 00611 std::__iterator_category(__begin1), 00612 std::__iterator_category(__begin2), 00613 std::__iterator_category(__out)); 00614 } 00615 00616 // Public interface. 00617 template<typename _IIter1, typename _IIter2, 00618 typename _OutputIterator, typename _Predicate> 00619 inline _OutputIterator 00620 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1, 00621 _IIter2 __begin2, _IIter2 __end2, 00622 _OutputIterator __out, _Predicate __pred) 00623 { 00624 return __set_symmetric_difference_switch( 00625 __begin1, __end1, __begin2, __end2, __out, __pred, 00626 std::__iterator_category(__begin1), 00627 std::__iterator_category(__begin2), 00628 std::__iterator_category(__out)); 00629 } 00630 00631 // Sequential fallback. 00632 template<typename _IIter1, typename _IIter2, 00633 typename _OutputIterator> 00634 inline _OutputIterator 00635 set_difference(_IIter1 __begin1, _IIter1 __end1, 00636 _IIter2 __begin2, _IIter2 __end2, 00637 _OutputIterator __out, __gnu_parallel::sequential_tag) 00638 { return _GLIBCXX_STD_A::set_difference( 00639 __begin1,__end1, __begin2, __end2, __out); } 00640 00641 // Sequential fallback. 00642 template<typename _IIter1, typename _IIter2, 00643 typename _OutputIterator, typename _Predicate> 00644 inline _OutputIterator 00645 set_difference(_IIter1 __begin1, _IIter1 __end1, 00646 _IIter2 __begin2, _IIter2 __end2, 00647 _OutputIterator __out, _Predicate __pred, 00648 __gnu_parallel::sequential_tag) 00649 { return _GLIBCXX_STD_A::set_difference(__begin1, __end1, 00650 __begin2, __end2, __out, __pred); } 00651 00652 // Sequential fallback for input iterator case. 00653 template<typename _IIter1, typename _IIter2, typename _Predicate, 00654 typename _OutputIterator, typename _IteratorTag1, 00655 typename _IteratorTag2, typename _IteratorTag3> 00656 inline _OutputIterator 00657 __set_difference_switch(_IIter1 __begin1, _IIter1 __end1, 00658 _IIter2 __begin2, _IIter2 __end2, 00659 _OutputIterator __result, _Predicate __pred, 00660 _IteratorTag1, _IteratorTag2, _IteratorTag3) 00661 { return _GLIBCXX_STD_A::set_difference( 00662 __begin1, __end1, __begin2, __end2, __result, __pred); } 00663 00664 // Parallel set_difference for random access iterators 00665 template<typename _RAIter1, typename _RAIter2, 00666 typename _Output_RAIter, typename _Predicate> 00667 _Output_RAIter 00668 __set_difference_switch(_RAIter1 __begin1, 00669 _RAIter1 __end1, 00670 _RAIter2 __begin2, 00671 _RAIter2 __end2, 00672 _Output_RAIter __result, _Predicate __pred, 00673 random_access_iterator_tag, 00674 random_access_iterator_tag, 00675 random_access_iterator_tag) 00676 { 00677 if (_GLIBCXX_PARALLEL_CONDITION( 00678 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 00679 >= __gnu_parallel::_Settings::get().set_difference_minimal_n 00680 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) 00681 >= __gnu_parallel::_Settings::get().set_difference_minimal_n)) 00682 return __gnu_parallel::__parallel_set_difference( 00683 __begin1, __end1, __begin2, __end2, __result, __pred); 00684 else 00685 return _GLIBCXX_STD_A::set_difference( 00686 __begin1, __end1, __begin2, __end2, __result, __pred); 00687 } 00688 00689 // Public interface 00690 template<typename _IIter1, typename _IIter2, 00691 typename _OutputIterator> 00692 inline _OutputIterator 00693 set_difference(_IIter1 __begin1, _IIter1 __end1, 00694 _IIter2 __begin2, _IIter2 __end2, 00695 _OutputIterator __out) 00696 { 00697 typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1; 00698 typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2; 00699 00700 return __set_difference_switch( 00701 __begin1, __end1, __begin2, __end2, __out, 00702 __gnu_parallel::_Less<_ValueType1, _ValueType2>(), 00703 std::__iterator_category(__begin1), 00704 std::__iterator_category(__begin2), 00705 std::__iterator_category(__out)); 00706 } 00707 00708 // Public interface 00709 template<typename _IIter1, typename _IIter2, 00710 typename _OutputIterator, typename _Predicate> 00711 inline _OutputIterator 00712 set_difference(_IIter1 __begin1, _IIter1 __end1, 00713 _IIter2 __begin2, _IIter2 __end2, 00714 _OutputIterator __out, _Predicate __pred) 00715 { 00716 return __set_difference_switch( 00717 __begin1, __end1, __begin2, __end2, __out, __pred, 00718 std::__iterator_category(__begin1), 00719 std::__iterator_category(__begin2), 00720 std::__iterator_category(__out)); 00721 } 00722 00723 // Sequential fallback 00724 template<typename _FIterator> 00725 inline _FIterator 00726 adjacent_find(_FIterator __begin, _FIterator __end, 00727 __gnu_parallel::sequential_tag) 00728 { return _GLIBCXX_STD_A::adjacent_find(__begin, __end); } 00729 00730 // Sequential fallback 00731 template<typename _FIterator, typename _BinaryPredicate> 00732 inline _FIterator 00733 adjacent_find(_FIterator __begin, _FIterator __end, 00734 _BinaryPredicate __binary_pred, 00735 __gnu_parallel::sequential_tag) 00736 { return _GLIBCXX_STD_A::adjacent_find(__begin, __end, __binary_pred); } 00737 00738 // Parallel algorithm for random access iterators 00739 template<typename _RAIter> 00740 _RAIter 00741 __adjacent_find_switch(_RAIter __begin, _RAIter __end, 00742 random_access_iterator_tag) 00743 { 00744 typedef iterator_traits<_RAIter> _TraitsType; 00745 typedef typename _TraitsType::value_type _ValueType; 00746 00747 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00748 { 00749 _RAIter __spot = __gnu_parallel:: 00750 __find_template( 00751 __begin, __end - 1, __begin, equal_to<_ValueType>(), 00752 __gnu_parallel::__adjacent_find_selector()) 00753 .first; 00754 if (__spot == (__end - 1)) 00755 return __end; 00756 else 00757 return __spot; 00758 } 00759 else 00760 return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag()); 00761 } 00762 00763 // Sequential fallback for input iterator case 00764 template<typename _FIterator, typename _IteratorTag> 00765 inline _FIterator 00766 __adjacent_find_switch(_FIterator __begin, _FIterator __end, 00767 _IteratorTag) 00768 { return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag()); } 00769 00770 // Public interface 00771 template<typename _FIterator> 00772 inline _FIterator 00773 adjacent_find(_FIterator __begin, _FIterator __end) 00774 { 00775 return __adjacent_find_switch(__begin, __end, 00776 std::__iterator_category(__begin)); 00777 } 00778 00779 // Sequential fallback for input iterator case 00780 template<typename _FIterator, typename _BinaryPredicate, 00781 typename _IteratorTag> 00782 inline _FIterator 00783 __adjacent_find_switch(_FIterator __begin, _FIterator __end, 00784 _BinaryPredicate __pred, _IteratorTag) 00785 { return adjacent_find(__begin, __end, __pred, 00786 __gnu_parallel::sequential_tag()); } 00787 00788 // Parallel algorithm for random access iterators 00789 template<typename _RAIter, typename _BinaryPredicate> 00790 _RAIter 00791 __adjacent_find_switch(_RAIter __begin, _RAIter __end, 00792 _BinaryPredicate __pred, random_access_iterator_tag) 00793 { 00794 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00795 return __gnu_parallel::__find_template(__begin, __end, __begin, __pred, 00796 __gnu_parallel:: 00797 __adjacent_find_selector()).first; 00798 else 00799 return adjacent_find(__begin, __end, __pred, 00800 __gnu_parallel::sequential_tag()); 00801 } 00802 00803 // Public interface 00804 template<typename _FIterator, typename _BinaryPredicate> 00805 inline _FIterator 00806 adjacent_find(_FIterator __begin, _FIterator __end, 00807 _BinaryPredicate __pred) 00808 { 00809 return __adjacent_find_switch(__begin, __end, __pred, 00810 std::__iterator_category(__begin)); 00811 } 00812 00813 // Sequential fallback 00814 template<typename _IIter, typename _Tp> 00815 inline typename iterator_traits<_IIter>::difference_type 00816 count(_IIter __begin, _IIter __end, const _Tp& __value, 00817 __gnu_parallel::sequential_tag) 00818 { return _GLIBCXX_STD_A::count(__begin, __end, __value); } 00819 00820 // Parallel code for random access iterators 00821 template<typename _RAIter, typename _Tp> 00822 typename iterator_traits<_RAIter>::difference_type 00823 __count_switch(_RAIter __begin, _RAIter __end, 00824 const _Tp& __value, random_access_iterator_tag, 00825 __gnu_parallel::_Parallelism __parallelism_tag) 00826 { 00827 typedef iterator_traits<_RAIter> _TraitsType; 00828 typedef typename _TraitsType::value_type _ValueType; 00829 typedef typename _TraitsType::difference_type _DifferenceType; 00830 typedef __gnu_parallel::_SequenceIndex _SequenceIndex; 00831 00832 if (_GLIBCXX_PARALLEL_CONDITION( 00833 static_cast<_SequenceIndex>(__end - __begin) 00834 >= __gnu_parallel::_Settings::get().count_minimal_n 00835 && __gnu_parallel::__is_parallel(__parallelism_tag))) 00836 { 00837 __gnu_parallel::__count_selector<_RAIter, _DifferenceType> 00838 __functionality; 00839 _DifferenceType __res = 0; 00840 __gnu_parallel:: 00841 __for_each_template_random_access( 00842 __begin, __end, __value, __functionality, 00843 std::plus<_SequenceIndex>(), __res, __res, -1, 00844 __parallelism_tag); 00845 return __res; 00846 } 00847 else 00848 return count(__begin, __end, __value, 00849 __gnu_parallel::sequential_tag()); 00850 } 00851 00852 // Sequential fallback for input iterator case. 00853 template<typename _IIter, typename _Tp, typename _IteratorTag> 00854 inline typename iterator_traits<_IIter>::difference_type 00855 __count_switch(_IIter __begin, _IIter __end, const _Tp& __value, 00856 _IteratorTag) 00857 { return count(__begin, __end, __value, __gnu_parallel::sequential_tag()); 00858 } 00859 00860 // Public interface. 00861 template<typename _IIter, typename _Tp> 00862 inline typename iterator_traits<_IIter>::difference_type 00863 count(_IIter __begin, _IIter __end, const _Tp& __value, 00864 __gnu_parallel::_Parallelism __parallelism_tag) 00865 { 00866 return __count_switch(__begin, __end, __value, 00867 std::__iterator_category(__begin), 00868 __parallelism_tag); 00869 } 00870 00871 template<typename _IIter, typename _Tp> 00872 inline typename iterator_traits<_IIter>::difference_type 00873 count(_IIter __begin, _IIter __end, const _Tp& __value) 00874 { 00875 return __count_switch(__begin, __end, __value, 00876 std::__iterator_category(__begin)); 00877 } 00878 00879 00880 // Sequential fallback. 00881 template<typename _IIter, typename _Predicate> 00882 inline typename iterator_traits<_IIter>::difference_type 00883 count_if(_IIter __begin, _IIter __end, _Predicate __pred, 00884 __gnu_parallel::sequential_tag) 00885 { return _GLIBCXX_STD_A::count_if(__begin, __end, __pred); } 00886 00887 // Parallel count_if for random access iterators 00888 template<typename _RAIter, typename _Predicate> 00889 typename iterator_traits<_RAIter>::difference_type 00890 __count_if_switch(_RAIter __begin, _RAIter __end, 00891 _Predicate __pred, random_access_iterator_tag, 00892 __gnu_parallel::_Parallelism __parallelism_tag) 00893 { 00894 typedef iterator_traits<_RAIter> _TraitsType; 00895 typedef typename _TraitsType::value_type _ValueType; 00896 typedef typename _TraitsType::difference_type _DifferenceType; 00897 typedef __gnu_parallel::_SequenceIndex _SequenceIndex; 00898 00899 if (_GLIBCXX_PARALLEL_CONDITION( 00900 static_cast<_SequenceIndex>(__end - __begin) 00901 >= __gnu_parallel::_Settings::get().count_minimal_n 00902 && __gnu_parallel::__is_parallel(__parallelism_tag))) 00903 { 00904 _DifferenceType __res = 0; 00905 __gnu_parallel:: 00906 __count_if_selector<_RAIter, _DifferenceType> 00907 __functionality; 00908 __gnu_parallel:: 00909 __for_each_template_random_access( 00910 __begin, __end, __pred, __functionality, 00911 std::plus<_SequenceIndex>(), __res, __res, -1, 00912 __parallelism_tag); 00913 return __res; 00914 } 00915 else 00916 return count_if(__begin, __end, __pred, 00917 __gnu_parallel::sequential_tag()); 00918 } 00919 00920 // Sequential fallback for input iterator case. 00921 template<typename _IIter, typename _Predicate, typename _IteratorTag> 00922 inline typename iterator_traits<_IIter>::difference_type 00923 __count_if_switch(_IIter __begin, _IIter __end, _Predicate __pred, 00924 _IteratorTag) 00925 { return count_if(__begin, __end, __pred, 00926 __gnu_parallel::sequential_tag()); } 00927 00928 // Public interface. 00929 template<typename _IIter, typename _Predicate> 00930 inline typename iterator_traits<_IIter>::difference_type 00931 count_if(_IIter __begin, _IIter __end, _Predicate __pred, 00932 __gnu_parallel::_Parallelism __parallelism_tag) 00933 { 00934 return __count_if_switch(__begin, __end, __pred, 00935 std::__iterator_category(__begin), 00936 __parallelism_tag); 00937 } 00938 00939 template<typename _IIter, typename _Predicate> 00940 inline typename iterator_traits<_IIter>::difference_type 00941 count_if(_IIter __begin, _IIter __end, _Predicate __pred) 00942 { 00943 return __count_if_switch(__begin, __end, __pred, 00944 std::__iterator_category(__begin)); 00945 } 00946 00947 00948 // Sequential fallback. 00949 template<typename _FIterator1, typename _FIterator2> 00950 inline _FIterator1 00951 search(_FIterator1 __begin1, _FIterator1 __end1, 00952 _FIterator2 __begin2, _FIterator2 __end2, 00953 __gnu_parallel::sequential_tag) 00954 { return _GLIBCXX_STD_A::search(__begin1, __end1, __begin2, __end2); } 00955 00956 // Parallel algorithm for random access iterator 00957 template<typename _RAIter1, typename _RAIter2> 00958 _RAIter1 00959 __search_switch(_RAIter1 __begin1, _RAIter1 __end1, 00960 _RAIter2 __begin2, _RAIter2 __end2, 00961 random_access_iterator_tag, random_access_iterator_tag) 00962 { 00963 typedef typename std::iterator_traits<_RAIter1>::value_type _ValueType1; 00964 typedef typename std::iterator_traits<_RAIter2>::value_type _ValueType2; 00965 00966 if (_GLIBCXX_PARALLEL_CONDITION( 00967 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 00968 >= __gnu_parallel::_Settings::get().search_minimal_n)) 00969 return __gnu_parallel:: 00970 __search_template( 00971 __begin1, __end1, __begin2, __end2, 00972 __gnu_parallel::_EqualTo<_ValueType1, _ValueType2>()); 00973 else 00974 return search(__begin1, __end1, __begin2, __end2, 00975 __gnu_parallel::sequential_tag()); 00976 } 00977 00978 // Sequential fallback for input iterator case 00979 template<typename _FIterator1, typename _FIterator2, 00980 typename _IteratorTag1, typename _IteratorTag2> 00981 inline _FIterator1 00982 __search_switch(_FIterator1 __begin1, _FIterator1 __end1, 00983 _FIterator2 __begin2, _FIterator2 __end2, 00984 _IteratorTag1, _IteratorTag2) 00985 { return search(__begin1, __end1, __begin2, __end2, 00986 __gnu_parallel::sequential_tag()); } 00987 00988 // Public interface. 00989 template<typename _FIterator1, typename _FIterator2> 00990 inline _FIterator1 00991 search(_FIterator1 __begin1, _FIterator1 __end1, 00992 _FIterator2 __begin2, _FIterator2 __end2) 00993 { 00994 return __search_switch(__begin1, __end1, __begin2, __end2, 00995 std::__iterator_category(__begin1), 00996 std::__iterator_category(__begin2)); 00997 } 00998 00999 // Public interface. 01000 template<typename _FIterator1, typename _FIterator2, 01001 typename _BinaryPredicate> 01002 inline _FIterator1 01003 search(_FIterator1 __begin1, _FIterator1 __end1, 01004 _FIterator2 __begin2, _FIterator2 __end2, 01005 _BinaryPredicate __pred, __gnu_parallel::sequential_tag) 01006 { return _GLIBCXX_STD_A::search( 01007 __begin1, __end1, __begin2, __end2, __pred); } 01008 01009 // Parallel algorithm for random access iterator. 01010 template<typename _RAIter1, typename _RAIter2, 01011 typename _BinaryPredicate> 01012 _RAIter1 01013 __search_switch(_RAIter1 __begin1, _RAIter1 __end1, 01014 _RAIter2 __begin2, _RAIter2 __end2, 01015 _BinaryPredicate __pred, 01016 random_access_iterator_tag, random_access_iterator_tag) 01017 { 01018 if (_GLIBCXX_PARALLEL_CONDITION( 01019 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 01020 >= __gnu_parallel::_Settings::get().search_minimal_n)) 01021 return __gnu_parallel::__search_template(__begin1, __end1, 01022 __begin2, __end2, __pred); 01023 else 01024 return search(__begin1, __end1, __begin2, __end2, __pred, 01025 __gnu_parallel::sequential_tag()); 01026 } 01027 01028 // Sequential fallback for input iterator case 01029 template<typename _FIterator1, typename _FIterator2, 01030 typename _BinaryPredicate, typename _IteratorTag1, 01031 typename _IteratorTag2> 01032 inline _FIterator1 01033 __search_switch(_FIterator1 __begin1, _FIterator1 __end1, 01034 _FIterator2 __begin2, _FIterator2 __end2, 01035 _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2) 01036 { return search(__begin1, __end1, __begin2, __end2, __pred, 01037 __gnu_parallel::sequential_tag()); } 01038 01039 // Public interface 01040 template<typename _FIterator1, typename _FIterator2, 01041 typename _BinaryPredicate> 01042 inline _FIterator1 01043 search(_FIterator1 __begin1, _FIterator1 __end1, 01044 _FIterator2 __begin2, _FIterator2 __end2, 01045 _BinaryPredicate __pred) 01046 { 01047 return __search_switch(__begin1, __end1, __begin2, __end2, __pred, 01048 std::__iterator_category(__begin1), 01049 std::__iterator_category(__begin2)); 01050 } 01051 01052 // Sequential fallback 01053 template<typename _FIterator, typename _Integer, typename _Tp> 01054 inline _FIterator 01055 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 01056 const _Tp& __val, __gnu_parallel::sequential_tag) 01057 { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val); } 01058 01059 // Sequential fallback 01060 template<typename _FIterator, typename _Integer, typename _Tp, 01061 typename _BinaryPredicate> 01062 inline _FIterator 01063 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 01064 const _Tp& __val, _BinaryPredicate __binary_pred, 01065 __gnu_parallel::sequential_tag) 01066 { return _GLIBCXX_STD_A::search_n( 01067 __begin, __end, __count, __val, __binary_pred); } 01068 01069 // Public interface. 01070 template<typename _FIterator, typename _Integer, typename _Tp> 01071 inline _FIterator 01072 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 01073 const _Tp& __val) 01074 { 01075 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 01076 return __gnu_parallel::search_n(__begin, __end, __count, __val, 01077 __gnu_parallel::_EqualTo<_ValueType, _Tp>()); 01078 } 01079 01080 // Parallel algorithm for random access iterators. 01081 template<typename _RAIter, typename _Integer, 01082 typename _Tp, typename _BinaryPredicate> 01083 _RAIter 01084 __search_n_switch(_RAIter __begin, _RAIter __end, _Integer __count, 01085 const _Tp& __val, _BinaryPredicate __binary_pred, 01086 random_access_iterator_tag) 01087 { 01088 if (_GLIBCXX_PARALLEL_CONDITION( 01089 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 01090 >= __gnu_parallel::_Settings::get().search_minimal_n)) 01091 { 01092 __gnu_parallel::_PseudoSequence<_Tp, _Integer> __ps(__val, __count); 01093 return __gnu_parallel::__search_template( 01094 __begin, __end, __ps.begin(), __ps.end(), __binary_pred); 01095 } 01096 else 01097 return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val, 01098 __binary_pred); 01099 } 01100 01101 // Sequential fallback for input iterator case. 01102 template<typename _FIterator, typename _Integer, typename _Tp, 01103 typename _BinaryPredicate, typename _IteratorTag> 01104 inline _FIterator 01105 __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count, 01106 const _Tp& __val, _BinaryPredicate __binary_pred, 01107 _IteratorTag) 01108 { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val, 01109 __binary_pred); } 01110 01111 // Public interface. 01112 template<typename _FIterator, typename _Integer, typename _Tp, 01113 typename _BinaryPredicate> 01114 inline _FIterator 01115 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 01116 const _Tp& __val, _BinaryPredicate __binary_pred) 01117 { 01118 return __search_n_switch(__begin, __end, __count, __val, __binary_pred, 01119 std::__iterator_category(__begin)); 01120 } 01121 01122 01123 // Sequential fallback. 01124 template<typename _IIter, typename _OutputIterator, 01125 typename _UnaryOperation> 01126 inline _OutputIterator 01127 transform(_IIter __begin, _IIter __end, _OutputIterator __result, 01128 _UnaryOperation __unary_op, __gnu_parallel::sequential_tag) 01129 { return _GLIBCXX_STD_A::transform(__begin, __end, __result, __unary_op); } 01130 01131 // Parallel unary transform for random access iterators. 01132 template<typename _RAIter1, typename _RAIter2, 01133 typename _UnaryOperation> 01134 _RAIter2 01135 __transform1_switch(_RAIter1 __begin, _RAIter1 __end, 01136 _RAIter2 __result, _UnaryOperation __unary_op, 01137 random_access_iterator_tag, random_access_iterator_tag, 01138 __gnu_parallel::_Parallelism __parallelism_tag) 01139 { 01140 if (_GLIBCXX_PARALLEL_CONDITION( 01141 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 01142 >= __gnu_parallel::_Settings::get().transform_minimal_n 01143 && __gnu_parallel::__is_parallel(__parallelism_tag))) 01144 { 01145 bool __dummy = true; 01146 typedef __gnu_parallel::_IteratorPair<_RAIter1, 01147 _RAIter2, random_access_iterator_tag> _ItTrip; 01148 _ItTrip __begin_pair(__begin, __result), 01149 __end_pair(__end, __result + (__end - __begin)); 01150 __gnu_parallel::__transform1_selector<_ItTrip> __functionality; 01151 __gnu_parallel:: 01152 __for_each_template_random_access( 01153 __begin_pair, __end_pair, __unary_op, __functionality, 01154 __gnu_parallel::_DummyReduct(), 01155 __dummy, __dummy, -1, __parallelism_tag); 01156 return __functionality._M_finish_iterator; 01157 } 01158 else 01159 return transform(__begin, __end, __result, __unary_op, 01160 __gnu_parallel::sequential_tag()); 01161 } 01162 01163 // Sequential fallback for input iterator case. 01164 template<typename _RAIter1, typename _RAIter2, 01165 typename _UnaryOperation, typename _IteratorTag1, 01166 typename _IteratorTag2> 01167 inline _RAIter2 01168 __transform1_switch(_RAIter1 __begin, _RAIter1 __end, 01169 _RAIter2 __result, _UnaryOperation __unary_op, 01170 _IteratorTag1, _IteratorTag2) 01171 { return transform(__begin, __end, __result, __unary_op, 01172 __gnu_parallel::sequential_tag()); } 01173 01174 // Public interface. 01175 template<typename _IIter, typename _OutputIterator, 01176 typename _UnaryOperation> 01177 inline _OutputIterator 01178 transform(_IIter __begin, _IIter __end, _OutputIterator __result, 01179 _UnaryOperation __unary_op, 01180 __gnu_parallel::_Parallelism __parallelism_tag) 01181 { 01182 return __transform1_switch(__begin, __end, __result, __unary_op, 01183 std::__iterator_category(__begin), 01184 std::__iterator_category(__result), 01185 __parallelism_tag); 01186 } 01187 01188 template<typename _IIter, typename _OutputIterator, 01189 typename _UnaryOperation> 01190 inline _OutputIterator 01191 transform(_IIter __begin, _IIter __end, _OutputIterator __result, 01192 _UnaryOperation __unary_op) 01193 { 01194 return __transform1_switch(__begin, __end, __result, __unary_op, 01195 std::__iterator_category(__begin), 01196 std::__iterator_category(__result)); 01197 } 01198 01199 01200 // Sequential fallback 01201 template<typename _IIter1, typename _IIter2, 01202 typename _OutputIterator, typename _BinaryOperation> 01203 inline _OutputIterator 01204 transform(_IIter1 __begin1, _IIter1 __end1, 01205 _IIter2 __begin2, _OutputIterator __result, 01206 _BinaryOperation __binary_op, __gnu_parallel::sequential_tag) 01207 { return _GLIBCXX_STD_A::transform(__begin1, __end1, 01208 __begin2, __result, __binary_op); } 01209 01210 // Parallel binary transform for random access iterators. 01211 template<typename _RAIter1, typename _RAIter2, 01212 typename _RAIter3, typename _BinaryOperation> 01213 _RAIter3 01214 __transform2_switch(_RAIter1 __begin1, _RAIter1 __end1, 01215 _RAIter2 __begin2, 01216 _RAIter3 __result, _BinaryOperation __binary_op, 01217 random_access_iterator_tag, random_access_iterator_tag, 01218 random_access_iterator_tag, 01219 __gnu_parallel::_Parallelism __parallelism_tag) 01220 { 01221 if (_GLIBCXX_PARALLEL_CONDITION( 01222 (__end1 - __begin1) >= 01223 __gnu_parallel::_Settings::get().transform_minimal_n 01224 && __gnu_parallel::__is_parallel(__parallelism_tag))) 01225 { 01226 bool __dummy = true; 01227 typedef __gnu_parallel::_IteratorTriple<_RAIter1, 01228 _RAIter2, _RAIter3, 01229 random_access_iterator_tag> _ItTrip; 01230 _ItTrip __begin_triple(__begin1, __begin2, __result), 01231 __end_triple(__end1, __begin2 + (__end1 - __begin1), 01232 __result + (__end1 - __begin1)); 01233 __gnu_parallel::__transform2_selector<_ItTrip> __functionality; 01234 __gnu_parallel:: 01235 __for_each_template_random_access(__begin_triple, __end_triple, 01236 __binary_op, __functionality, 01237 __gnu_parallel::_DummyReduct(), 01238 __dummy, __dummy, -1, 01239 __parallelism_tag); 01240 return __functionality._M_finish_iterator; 01241 } 01242 else 01243 return transform(__begin1, __end1, __begin2, __result, __binary_op, 01244 __gnu_parallel::sequential_tag()); 01245 } 01246 01247 // Sequential fallback for input iterator case. 01248 template<typename _IIter1, typename _IIter2, 01249 typename _OutputIterator, typename _BinaryOperation, 01250 typename _Tag1, typename _Tag2, typename _Tag3> 01251 inline _OutputIterator 01252 __transform2_switch(_IIter1 __begin1, _IIter1 __end1, 01253 _IIter2 __begin2, _OutputIterator __result, 01254 _BinaryOperation __binary_op, _Tag1, _Tag2, _Tag3) 01255 { return transform(__begin1, __end1, __begin2, __result, __binary_op, 01256 __gnu_parallel::sequential_tag()); } 01257 01258 // Public interface. 01259 template<typename _IIter1, typename _IIter2, 01260 typename _OutputIterator, typename _BinaryOperation> 01261 inline _OutputIterator 01262 transform(_IIter1 __begin1, _IIter1 __end1, 01263 _IIter2 __begin2, _OutputIterator __result, 01264 _BinaryOperation __binary_op, 01265 __gnu_parallel::_Parallelism __parallelism_tag) 01266 { 01267 return __transform2_switch( 01268 __begin1, __end1, __begin2, __result, __binary_op, 01269 std::__iterator_category(__begin1), 01270 std::__iterator_category(__begin2), 01271 std::__iterator_category(__result), 01272 __parallelism_tag); 01273 } 01274 01275 template<typename _IIter1, typename _IIter2, 01276 typename _OutputIterator, typename _BinaryOperation> 01277 inline _OutputIterator 01278 transform(_IIter1 __begin1, _IIter1 __end1, 01279 _IIter2 __begin2, _OutputIterator __result, 01280 _BinaryOperation __binary_op) 01281 { 01282 return __transform2_switch( 01283 __begin1, __end1, __begin2, __result, __binary_op, 01284 std::__iterator_category(__begin1), 01285 std::__iterator_category(__begin2), 01286 std::__iterator_category(__result)); 01287 } 01288 01289 // Sequential fallback 01290 template<typename _FIterator, typename _Tp> 01291 inline void 01292 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 01293 const _Tp& __new_value, __gnu_parallel::sequential_tag) 01294 { _GLIBCXX_STD_A::replace(__begin, __end, __old_value, __new_value); } 01295 01296 // Sequential fallback for input iterator case 01297 template<typename _FIterator, typename _Tp, typename _IteratorTag> 01298 inline void 01299 __replace_switch(_FIterator __begin, _FIterator __end, 01300 const _Tp& __old_value, const _Tp& __new_value, 01301 _IteratorTag) 01302 { replace(__begin, __end, __old_value, __new_value, 01303 __gnu_parallel::sequential_tag()); } 01304 01305 // Parallel replace for random access iterators 01306 template<typename _RAIter, typename _Tp> 01307 inline void 01308 __replace_switch(_RAIter __begin, _RAIter __end, 01309 const _Tp& __old_value, const _Tp& __new_value, 01310 random_access_iterator_tag, 01311 __gnu_parallel::_Parallelism __parallelism_tag) 01312 { 01313 // XXX parallel version is where? 01314 replace(__begin, __end, __old_value, __new_value, 01315 __gnu_parallel::sequential_tag()); 01316 } 01317 01318 // Public interface 01319 template<typename _FIterator, typename _Tp> 01320 inline void 01321 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 01322 const _Tp& __new_value, 01323 __gnu_parallel::_Parallelism __parallelism_tag) 01324 { 01325 __replace_switch(__begin, __end, __old_value, __new_value, 01326 std::__iterator_category(__begin), 01327 __parallelism_tag); 01328 } 01329 01330 template<typename _FIterator, typename _Tp> 01331 inline void 01332 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 01333 const _Tp& __new_value) 01334 { 01335 __replace_switch(__begin, __end, __old_value, __new_value, 01336 std::__iterator_category(__begin)); 01337 } 01338 01339 01340 // Sequential fallback 01341 template<typename _FIterator, typename _Predicate, typename _Tp> 01342 inline void 01343 replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred, 01344 const _Tp& __new_value, __gnu_parallel::sequential_tag) 01345 { _GLIBCXX_STD_A::replace_if(__begin, __end, __pred, __new_value); } 01346 01347 // Sequential fallback for input iterator case 01348 template<typename _FIterator, typename _Predicate, typename _Tp, 01349 typename _IteratorTag> 01350 inline void 01351 __replace_if_switch(_FIterator __begin, _FIterator __end, 01352 _Predicate __pred, const _Tp& __new_value, _IteratorTag) 01353 { replace_if(__begin, __end, __pred, __new_value, 01354 __gnu_parallel::sequential_tag()); } 01355 01356 // Parallel algorithm for random access iterators. 01357 template<typename _RAIter, typename _Predicate, typename _Tp> 01358 void 01359 __replace_if_switch(_RAIter __begin, _RAIter __end, 01360 _Predicate __pred, const _Tp& __new_value, 01361 random_access_iterator_tag, 01362 __gnu_parallel::_Parallelism __parallelism_tag) 01363 { 01364 if (_GLIBCXX_PARALLEL_CONDITION( 01365 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 01366 >= __gnu_parallel::_Settings::get().replace_minimal_n 01367 && __gnu_parallel::__is_parallel(__parallelism_tag))) 01368 { 01369 bool __dummy; 01370 __gnu_parallel:: 01371 __replace_if_selector<_RAIter, _Predicate, _Tp> 01372 __functionality(__new_value); 01373 __gnu_parallel:: 01374 __for_each_template_random_access( 01375 __begin, __end, __pred, __functionality, 01376 __gnu_parallel::_DummyReduct(), 01377 true, __dummy, -1, __parallelism_tag); 01378 } 01379 else 01380 replace_if(__begin, __end, __pred, __new_value, 01381 __gnu_parallel::sequential_tag()); 01382 } 01383 01384 // Public interface. 01385 template<typename _FIterator, typename _Predicate, typename _Tp> 01386 inline void 01387 replace_if(_FIterator __begin, _FIterator __end, 01388 _Predicate __pred, const _Tp& __new_value, 01389 __gnu_parallel::_Parallelism __parallelism_tag) 01390 { 01391 __replace_if_switch(__begin, __end, __pred, __new_value, 01392 std::__iterator_category(__begin), 01393 __parallelism_tag); 01394 } 01395 01396 template<typename _FIterator, typename _Predicate, typename _Tp> 01397 inline void 01398 replace_if(_FIterator __begin, _FIterator __end, 01399 _Predicate __pred, const _Tp& __new_value) 01400 { 01401 __replace_if_switch(__begin, __end, __pred, __new_value, 01402 std::__iterator_category(__begin)); 01403 } 01404 01405 // Sequential fallback 01406 template<typename _FIterator, typename _Generator> 01407 inline void 01408 generate(_FIterator __begin, _FIterator __end, _Generator __gen, 01409 __gnu_parallel::sequential_tag) 01410 { _GLIBCXX_STD_A::generate(__begin, __end, __gen); } 01411 01412 // Sequential fallback for input iterator case. 01413 template<typename _FIterator, typename _Generator, typename _IteratorTag> 01414 inline void 01415 __generate_switch(_FIterator __begin, _FIterator __end, _Generator __gen, 01416 _IteratorTag) 01417 { generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); } 01418 01419 // Parallel algorithm for random access iterators. 01420 template<typename _RAIter, typename _Generator> 01421 void 01422 __generate_switch(_RAIter __begin, _RAIter __end, 01423 _Generator __gen, random_access_iterator_tag, 01424 __gnu_parallel::_Parallelism __parallelism_tag) 01425 { 01426 if (_GLIBCXX_PARALLEL_CONDITION( 01427 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 01428 >= __gnu_parallel::_Settings::get().generate_minimal_n 01429 && __gnu_parallel::__is_parallel(__parallelism_tag))) 01430 { 01431 bool __dummy; 01432 __gnu_parallel::__generate_selector<_RAIter> 01433 __functionality; 01434 __gnu_parallel:: 01435 __for_each_template_random_access( 01436 __begin, __end, __gen, __functionality, 01437 __gnu_parallel::_DummyReduct(), 01438 true, __dummy, -1, __parallelism_tag); 01439 } 01440 else 01441 generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); 01442 } 01443 01444 // Public interface. 01445 template<typename _FIterator, typename _Generator> 01446 inline void 01447 generate(_FIterator __begin, _FIterator __end, 01448 _Generator __gen, __gnu_parallel::_Parallelism __parallelism_tag) 01449 { 01450 __generate_switch(__begin, __end, __gen, 01451 std::__iterator_category(__begin), 01452 __parallelism_tag); 01453 } 01454 01455 template<typename _FIterator, typename _Generator> 01456 inline void 01457 generate(_FIterator __begin, _FIterator __end, _Generator __gen) 01458 { 01459 __generate_switch(__begin, __end, __gen, 01460 std::__iterator_category(__begin)); 01461 } 01462 01463 01464 // Sequential fallback. 01465 template<typename _OutputIterator, typename _Size, typename _Generator> 01466 inline _OutputIterator 01467 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen, 01468 __gnu_parallel::sequential_tag) 01469 { return _GLIBCXX_STD_A::generate_n(__begin, __n, __gen); } 01470 01471 // Sequential fallback for input iterator case. 01472 template<typename _OutputIterator, typename _Size, typename _Generator, 01473 typename _IteratorTag> 01474 inline _OutputIterator 01475 __generate_n_switch(_OutputIterator __begin, _Size __n, _Generator __gen, 01476 _IteratorTag) 01477 { return generate_n(__begin, __n, __gen, 01478 __gnu_parallel::sequential_tag()); } 01479 01480 // Parallel algorithm for random access iterators. 01481 template<typename _RAIter, typename _Size, typename _Generator> 01482 inline _RAIter 01483 __generate_n_switch(_RAIter __begin, _Size __n, _Generator __gen, 01484 random_access_iterator_tag, 01485 __gnu_parallel::_Parallelism __parallelism_tag) 01486 { 01487 // XXX parallel version is where? 01488 return generate_n(__begin, __n, __gen, __gnu_parallel::sequential_tag()); 01489 } 01490 01491 // Public interface. 01492 template<typename _OutputIterator, typename _Size, typename _Generator> 01493 inline _OutputIterator 01494 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen, 01495 __gnu_parallel::_Parallelism __parallelism_tag) 01496 { 01497 return __generate_n_switch(__begin, __n, __gen, 01498 std::__iterator_category(__begin), 01499 __parallelism_tag); 01500 } 01501 01502 template<typename _OutputIterator, typename _Size, typename _Generator> 01503 inline _OutputIterator 01504 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen) 01505 { 01506 return __generate_n_switch(__begin, __n, __gen, 01507 std::__iterator_category(__begin)); 01508 } 01509 01510 01511 // Sequential fallback. 01512 template<typename _RAIter> 01513 inline void 01514 random_shuffle(_RAIter __begin, _RAIter __end, 01515 __gnu_parallel::sequential_tag) 01516 { _GLIBCXX_STD_A::random_shuffle(__begin, __end); } 01517 01518 // Sequential fallback. 01519 template<typename _RAIter, typename _RandomNumberGenerator> 01520 inline void 01521 random_shuffle(_RAIter __begin, _RAIter __end, 01522 _RandomNumberGenerator& __rand, 01523 __gnu_parallel::sequential_tag) 01524 { _GLIBCXX_STD_A::random_shuffle(__begin, __end, __rand); } 01525 01526 01527 /** @brief Functor wrapper for std::rand(). */ 01528 template<typename _MustBeInt = int> 01529 struct _CRandNumber 01530 { 01531 int 01532 operator()(int __limit) 01533 { return rand() % __limit; } 01534 }; 01535 01536 // Fill in random number generator. 01537 template<typename _RAIter> 01538 inline void 01539 random_shuffle(_RAIter __begin, _RAIter __end) 01540 { 01541 _CRandNumber<> __r; 01542 // Parallelization still possible. 01543 __gnu_parallel::random_shuffle(__begin, __end, __r); 01544 } 01545 01546 // Parallel algorithm for random access iterators. 01547 template<typename _RAIter, typename _RandomNumberGenerator> 01548 void 01549 random_shuffle(_RAIter __begin, _RAIter __end, 01550 #if __cplusplus >= 201103L 01551 _RandomNumberGenerator&& __rand) 01552 #else 01553 _RandomNumberGenerator& __rand) 01554 #endif 01555 { 01556 if (__begin == __end) 01557 return; 01558 if (_GLIBCXX_PARALLEL_CONDITION( 01559 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 01560 >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n)) 01561 __gnu_parallel::__parallel_random_shuffle(__begin, __end, __rand); 01562 else 01563 __gnu_parallel::__sequential_random_shuffle(__begin, __end, __rand); 01564 } 01565 01566 // Sequential fallback. 01567 template<typename _FIterator, typename _Predicate> 01568 inline _FIterator 01569 partition(_FIterator __begin, _FIterator __end, 01570 _Predicate __pred, __gnu_parallel::sequential_tag) 01571 { return _GLIBCXX_STD_A::partition(__begin, __end, __pred); } 01572 01573 // Sequential fallback for input iterator case. 01574 template<typename _FIterator, typename _Predicate, typename _IteratorTag> 01575 inline _FIterator 01576 __partition_switch(_FIterator __begin, _FIterator __end, 01577 _Predicate __pred, _IteratorTag) 01578 { return partition(__begin, __end, __pred, 01579 __gnu_parallel::sequential_tag()); } 01580 01581 // Parallel algorithm for random access iterators. 01582 template<typename _RAIter, typename _Predicate> 01583 _RAIter 01584 __partition_switch(_RAIter __begin, _RAIter __end, 01585 _Predicate __pred, random_access_iterator_tag) 01586 { 01587 if (_GLIBCXX_PARALLEL_CONDITION( 01588 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 01589 >= __gnu_parallel::_Settings::get().partition_minimal_n)) 01590 { 01591 typedef typename std::iterator_traits<_RAIter>:: 01592 difference_type _DifferenceType; 01593 _DifferenceType __middle = __gnu_parallel:: 01594 __parallel_partition(__begin, __end, __pred, 01595 __gnu_parallel::__get_max_threads()); 01596 return __begin + __middle; 01597 } 01598 else 01599 return partition(__begin, __end, __pred, 01600 __gnu_parallel::sequential_tag()); 01601 } 01602 01603 // Public interface. 01604 template<typename _FIterator, typename _Predicate> 01605 inline _FIterator 01606 partition(_FIterator __begin, _FIterator __end, _Predicate __pred) 01607 { 01608 return __partition_switch(__begin, __end, __pred, 01609 std::__iterator_category(__begin)); 01610 } 01611 01612 // sort interface 01613 01614 // Sequential fallback 01615 template<typename _RAIter> 01616 inline void 01617 sort(_RAIter __begin, _RAIter __end, 01618 __gnu_parallel::sequential_tag) 01619 { _GLIBCXX_STD_A::sort(__begin, __end); } 01620 01621 // Sequential fallback 01622 template<typename _RAIter, typename _Compare> 01623 inline void 01624 sort(_RAIter __begin, _RAIter __end, _Compare __comp, 01625 __gnu_parallel::sequential_tag) 01626 { _GLIBCXX_STD_A::sort<_RAIter, _Compare>(__begin, __end, 01627 __comp); } 01628 01629 // Public interface 01630 template<typename _RAIter, typename _Compare, 01631 typename _Parallelism> 01632 void 01633 sort(_RAIter __begin, _RAIter __end, _Compare __comp, 01634 _Parallelism __parallelism) 01635 { 01636 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01637 01638 if (__begin != __end) 01639 { 01640 if (_GLIBCXX_PARALLEL_CONDITION( 01641 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >= 01642 __gnu_parallel::_Settings::get().sort_minimal_n)) 01643 __gnu_parallel::__parallel_sort<false>( 01644 __begin, __end, __comp, __parallelism); 01645 else 01646 sort(__begin, __end, __comp, __gnu_parallel::sequential_tag()); 01647 } 01648 } 01649 01650 // Public interface, insert default comparator 01651 template<typename _RAIter> 01652 inline void 01653 sort(_RAIter __begin, _RAIter __end) 01654 { 01655 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01656 sort(__begin, __end, std::less<_ValueType>(), 01657 __gnu_parallel::default_parallel_tag()); 01658 } 01659 01660 // Public interface, insert default comparator 01661 template<typename _RAIter> 01662 inline void 01663 sort(_RAIter __begin, _RAIter __end, 01664 __gnu_parallel::default_parallel_tag __parallelism) 01665 { 01666 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01667 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01668 } 01669 01670 // Public interface, insert default comparator 01671 template<typename _RAIter> 01672 inline void 01673 sort(_RAIter __begin, _RAIter __end, 01674 __gnu_parallel::parallel_tag __parallelism) 01675 { 01676 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01677 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01678 } 01679 01680 // Public interface, insert default comparator 01681 template<typename _RAIter> 01682 inline void 01683 sort(_RAIter __begin, _RAIter __end, 01684 __gnu_parallel::multiway_mergesort_tag __parallelism) 01685 { 01686 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01687 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01688 } 01689 01690 // Public interface, insert default comparator 01691 template<typename _RAIter> 01692 inline void 01693 sort(_RAIter __begin, _RAIter __end, 01694 __gnu_parallel::multiway_mergesort_sampling_tag __parallelism) 01695 { 01696 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01697 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01698 } 01699 01700 // Public interface, insert default comparator 01701 template<typename _RAIter> 01702 inline void 01703 sort(_RAIter __begin, _RAIter __end, 01704 __gnu_parallel::multiway_mergesort_exact_tag __parallelism) 01705 { 01706 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01707 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01708 } 01709 01710 // Public interface, insert default comparator 01711 template<typename _RAIter> 01712 inline void 01713 sort(_RAIter __begin, _RAIter __end, 01714 __gnu_parallel::quicksort_tag __parallelism) 01715 { 01716 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01717 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01718 } 01719 01720 // Public interface, insert default comparator 01721 template<typename _RAIter> 01722 inline void 01723 sort(_RAIter __begin, _RAIter __end, 01724 __gnu_parallel::balanced_quicksort_tag __parallelism) 01725 { 01726 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01727 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01728 } 01729 01730 // Public interface 01731 template<typename _RAIter, typename _Compare> 01732 void 01733 sort(_RAIter __begin, _RAIter __end, _Compare __comp) 01734 { 01735 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01736 sort(__begin, __end, __comp, __gnu_parallel::default_parallel_tag()); 01737 } 01738 01739 // stable_sort interface 01740 01741 01742 // Sequential fallback 01743 template<typename _RAIter> 01744 inline void 01745 stable_sort(_RAIter __begin, _RAIter __end, 01746 __gnu_parallel::sequential_tag) 01747 { _GLIBCXX_STD_A::stable_sort(__begin, __end); } 01748 01749 // Sequential fallback 01750 template<typename _RAIter, typename _Compare> 01751 inline void 01752 stable_sort(_RAIter __begin, _RAIter __end, 01753 _Compare __comp, __gnu_parallel::sequential_tag) 01754 { _GLIBCXX_STD_A::stable_sort<_RAIter, _Compare>(__begin, __end, __comp); } 01755 01756 // Public interface 01757 template<typename _RAIter, typename _Compare, 01758 typename _Parallelism> 01759 void 01760 stable_sort(_RAIter __begin, _RAIter __end, 01761 _Compare __comp, _Parallelism __parallelism) 01762 { 01763 typedef iterator_traits<_RAIter> _TraitsType; 01764 typedef typename _TraitsType::value_type _ValueType; 01765 01766 if (__begin != __end) 01767 { 01768 if (_GLIBCXX_PARALLEL_CONDITION( 01769 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >= 01770 __gnu_parallel::_Settings::get().sort_minimal_n)) 01771 __gnu_parallel::__parallel_sort<true>(__begin, __end, 01772 __comp, __parallelism); 01773 else 01774 stable_sort(__begin, __end, __comp, 01775 __gnu_parallel::sequential_tag()); 01776 } 01777 } 01778 01779 // Public interface, insert default comparator 01780 template<typename _RAIter> 01781 inline void 01782 stable_sort(_RAIter __begin, _RAIter __end) 01783 { 01784 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01785 stable_sort(__begin, __end, std::less<_ValueType>(), 01786 __gnu_parallel::default_parallel_tag()); 01787 } 01788 01789 // Public interface, insert default comparator 01790 template<typename _RAIter> 01791 inline void 01792 stable_sort(_RAIter __begin, _RAIter __end, 01793 __gnu_parallel::default_parallel_tag __parallelism) 01794 { 01795 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01796 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01797 } 01798 01799 // Public interface, insert default comparator 01800 template<typename _RAIter> 01801 inline void 01802 stable_sort(_RAIter __begin, _RAIter __end, 01803 __gnu_parallel::parallel_tag __parallelism) 01804 { 01805 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01806 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01807 } 01808 01809 // Public interface, insert default comparator 01810 template<typename _RAIter> 01811 inline void 01812 stable_sort(_RAIter __begin, _RAIter __end, 01813 __gnu_parallel::multiway_mergesort_tag __parallelism) 01814 { 01815 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01816 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01817 } 01818 01819 // Public interface, insert default comparator 01820 template<typename _RAIter> 01821 inline void 01822 stable_sort(_RAIter __begin, _RAIter __end, 01823 __gnu_parallel::quicksort_tag __parallelism) 01824 { 01825 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01826 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01827 } 01828 01829 // Public interface, insert default comparator 01830 template<typename _RAIter> 01831 inline void 01832 stable_sort(_RAIter __begin, _RAIter __end, 01833 __gnu_parallel::balanced_quicksort_tag __parallelism) 01834 { 01835 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01836 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 01837 } 01838 01839 // Public interface 01840 template<typename _RAIter, typename _Compare> 01841 void 01842 stable_sort(_RAIter __begin, _RAIter __end, _Compare __comp) 01843 { 01844 stable_sort( 01845 __begin, __end, __comp, __gnu_parallel::default_parallel_tag()); 01846 } 01847 01848 // Sequential fallback 01849 template<typename _IIter1, typename _IIter2, 01850 typename _OutputIterator> 01851 inline _OutputIterator 01852 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 01853 _IIter2 __end2, _OutputIterator __result, 01854 __gnu_parallel::sequential_tag) 01855 { return _GLIBCXX_STD_A::merge( 01856 __begin1, __end1, __begin2, __end2, __result); } 01857 01858 // Sequential fallback 01859 template<typename _IIter1, typename _IIter2, 01860 typename _OutputIterator, typename _Compare> 01861 inline _OutputIterator 01862 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 01863 _IIter2 __end2, _OutputIterator __result, _Compare __comp, 01864 __gnu_parallel::sequential_tag) 01865 { return _GLIBCXX_STD_A::merge( 01866 __begin1, __end1, __begin2, __end2, __result, __comp); } 01867 01868 // Sequential fallback for input iterator case 01869 template<typename _IIter1, typename _IIter2, typename _OutputIterator, 01870 typename _Compare, typename _IteratorTag1, 01871 typename _IteratorTag2, typename _IteratorTag3> 01872 inline _OutputIterator 01873 __merge_switch(_IIter1 __begin1, _IIter1 __end1, 01874 _IIter2 __begin2, _IIter2 __end2, 01875 _OutputIterator __result, _Compare __comp, 01876 _IteratorTag1, _IteratorTag2, _IteratorTag3) 01877 { return _GLIBCXX_STD_A::merge(__begin1, __end1, __begin2, __end2, 01878 __result, __comp); } 01879 01880 // Parallel algorithm for random access iterators 01881 template<typename _IIter1, typename _IIter2, 01882 typename _OutputIterator, typename _Compare> 01883 _OutputIterator 01884 __merge_switch(_IIter1 __begin1, _IIter1 __end1, 01885 _IIter2 __begin2, _IIter2 __end2, 01886 _OutputIterator __result, _Compare __comp, 01887 random_access_iterator_tag, random_access_iterator_tag, 01888 random_access_iterator_tag) 01889 { 01890 if (_GLIBCXX_PARALLEL_CONDITION( 01891 (static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 01892 >= __gnu_parallel::_Settings::get().merge_minimal_n 01893 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) 01894 >= __gnu_parallel::_Settings::get().merge_minimal_n))) 01895 return __gnu_parallel::__parallel_merge_advance( 01896 __begin1, __end1, __begin2, __end2, __result, 01897 (__end1 - __begin1) + (__end2 - __begin2), __comp); 01898 else 01899 return __gnu_parallel::__merge_advance( 01900 __begin1, __end1, __begin2, __end2, __result, 01901 (__end1 - __begin1) + (__end2 - __begin2), __comp); 01902 } 01903 01904 // Public interface 01905 template<typename _IIter1, typename _IIter2, 01906 typename _OutputIterator, typename _Compare> 01907 inline _OutputIterator 01908 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 01909 _IIter2 __end2, _OutputIterator __result, _Compare __comp) 01910 { 01911 return __merge_switch( 01912 __begin1, __end1, __begin2, __end2, __result, __comp, 01913 std::__iterator_category(__begin1), 01914 std::__iterator_category(__begin2), 01915 std::__iterator_category(__result)); 01916 } 01917 01918 // Public interface, insert default comparator 01919 template<typename _IIter1, typename _IIter2, 01920 typename _OutputIterator> 01921 inline _OutputIterator 01922 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 01923 _IIter2 __end2, _OutputIterator __result) 01924 { 01925 typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1; 01926 typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2; 01927 01928 return __gnu_parallel::merge(__begin1, __end1, __begin2, __end2, 01929 __result, __gnu_parallel::_Less<_ValueType1, _ValueType2>()); 01930 } 01931 01932 // Sequential fallback 01933 template<typename _RAIter> 01934 inline void 01935 nth_element(_RAIter __begin, _RAIter __nth, 01936 _RAIter __end, __gnu_parallel::sequential_tag) 01937 { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end); } 01938 01939 // Sequential fallback 01940 template<typename _RAIter, typename _Compare> 01941 inline void 01942 nth_element(_RAIter __begin, _RAIter __nth, 01943 _RAIter __end, _Compare __comp, 01944 __gnu_parallel::sequential_tag) 01945 { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end, __comp); } 01946 01947 // Public interface 01948 template<typename _RAIter, typename _Compare> 01949 inline void 01950 nth_element(_RAIter __begin, _RAIter __nth, 01951 _RAIter __end, _Compare __comp) 01952 { 01953 if (_GLIBCXX_PARALLEL_CONDITION( 01954 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 01955 >= __gnu_parallel::_Settings::get().nth_element_minimal_n)) 01956 __gnu_parallel::__parallel_nth_element(__begin, __nth, __end, __comp); 01957 else 01958 nth_element(__begin, __nth, __end, __comp, 01959 __gnu_parallel::sequential_tag()); 01960 } 01961 01962 // Public interface, insert default comparator 01963 template<typename _RAIter> 01964 inline void 01965 nth_element(_RAIter __begin, _RAIter __nth, 01966 _RAIter __end) 01967 { 01968 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 01969 __gnu_parallel::nth_element(__begin, __nth, __end, 01970 std::less<_ValueType>()); 01971 } 01972 01973 // Sequential fallback 01974 template<typename _RAIter, typename _Compare> 01975 inline void 01976 partial_sort(_RAIter __begin, _RAIter __middle, 01977 _RAIter __end, _Compare __comp, 01978 __gnu_parallel::sequential_tag) 01979 { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end, __comp); } 01980 01981 // Sequential fallback 01982 template<typename _RAIter> 01983 inline void 01984 partial_sort(_RAIter __begin, _RAIter __middle, 01985 _RAIter __end, __gnu_parallel::sequential_tag) 01986 { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end); } 01987 01988 // Public interface, parallel algorithm for random access iterators 01989 template<typename _RAIter, typename _Compare> 01990 void 01991 partial_sort(_RAIter __begin, _RAIter __middle, 01992 _RAIter __end, _Compare __comp) 01993 { 01994 if (_GLIBCXX_PARALLEL_CONDITION( 01995 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 01996 >= __gnu_parallel::_Settings::get().partial_sort_minimal_n)) 01997 __gnu_parallel:: 01998 __parallel_partial_sort(__begin, __middle, __end, __comp); 01999 else 02000 partial_sort(__begin, __middle, __end, __comp, 02001 __gnu_parallel::sequential_tag()); 02002 } 02003 02004 // Public interface, insert default comparator 02005 template<typename _RAIter> 02006 inline void 02007 partial_sort(_RAIter __begin, _RAIter __middle, 02008 _RAIter __end) 02009 { 02010 typedef iterator_traits<_RAIter> _TraitsType; 02011 typedef typename _TraitsType::value_type _ValueType; 02012 __gnu_parallel::partial_sort(__begin, __middle, __end, 02013 std::less<_ValueType>()); 02014 } 02015 02016 // Sequential fallback 02017 template<typename _FIterator> 02018 inline _FIterator 02019 max_element(_FIterator __begin, _FIterator __end, 02020 __gnu_parallel::sequential_tag) 02021 { return _GLIBCXX_STD_A::max_element(__begin, __end); } 02022 02023 // Sequential fallback 02024 template<typename _FIterator, typename _Compare> 02025 inline _FIterator 02026 max_element(_FIterator __begin, _FIterator __end, _Compare __comp, 02027 __gnu_parallel::sequential_tag) 02028 { return _GLIBCXX_STD_A::max_element(__begin, __end, __comp); } 02029 02030 // Sequential fallback for input iterator case 02031 template<typename _FIterator, typename _Compare, typename _IteratorTag> 02032 inline _FIterator 02033 __max_element_switch(_FIterator __begin, _FIterator __end, 02034 _Compare __comp, _IteratorTag) 02035 { return max_element(__begin, __end, __comp, 02036 __gnu_parallel::sequential_tag()); } 02037 02038 // Parallel algorithm for random access iterators 02039 template<typename _RAIter, typename _Compare> 02040 _RAIter 02041 __max_element_switch(_RAIter __begin, _RAIter __end, 02042 _Compare __comp, random_access_iterator_tag, 02043 __gnu_parallel::_Parallelism __parallelism_tag) 02044 { 02045 if (_GLIBCXX_PARALLEL_CONDITION( 02046 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 02047 >= __gnu_parallel::_Settings::get().max_element_minimal_n 02048 && __gnu_parallel::__is_parallel(__parallelism_tag))) 02049 { 02050 _RAIter __res(__begin); 02051 __gnu_parallel::__identity_selector<_RAIter> 02052 __functionality; 02053 __gnu_parallel:: 02054 __for_each_template_random_access( 02055 __begin, __end, __gnu_parallel::_Nothing(), __functionality, 02056 __gnu_parallel::__max_element_reduct<_Compare, _RAIter>(__comp), 02057 __res, __res, -1, __parallelism_tag); 02058 return __res; 02059 } 02060 else 02061 return max_element(__begin, __end, __comp, 02062 __gnu_parallel::sequential_tag()); 02063 } 02064 02065 // Public interface, insert default comparator 02066 template<typename _FIterator> 02067 inline _FIterator 02068 max_element(_FIterator __begin, _FIterator __end, 02069 __gnu_parallel::_Parallelism __parallelism_tag) 02070 { 02071 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 02072 return max_element(__begin, __end, std::less<_ValueType>(), 02073 __parallelism_tag); 02074 } 02075 02076 template<typename _FIterator> 02077 inline _FIterator 02078 max_element(_FIterator __begin, _FIterator __end) 02079 { 02080 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 02081 return __gnu_parallel::max_element(__begin, __end, 02082 std::less<_ValueType>()); 02083 } 02084 02085 // Public interface 02086 template<typename _FIterator, typename _Compare> 02087 inline _FIterator 02088 max_element(_FIterator __begin, _FIterator __end, _Compare __comp, 02089 __gnu_parallel::_Parallelism __parallelism_tag) 02090 { 02091 return __max_element_switch(__begin, __end, __comp, 02092 std::__iterator_category(__begin), 02093 __parallelism_tag); 02094 } 02095 02096 template<typename _FIterator, typename _Compare> 02097 inline _FIterator 02098 max_element(_FIterator __begin, _FIterator __end, _Compare __comp) 02099 { 02100 return __max_element_switch(__begin, __end, __comp, 02101 std::__iterator_category(__begin)); 02102 } 02103 02104 02105 // Sequential fallback 02106 template<typename _FIterator> 02107 inline _FIterator 02108 min_element(_FIterator __begin, _FIterator __end, 02109 __gnu_parallel::sequential_tag) 02110 { return _GLIBCXX_STD_A::min_element(__begin, __end); } 02111 02112 // Sequential fallback 02113 template<typename _FIterator, typename _Compare> 02114 inline _FIterator 02115 min_element(_FIterator __begin, _FIterator __end, _Compare __comp, 02116 __gnu_parallel::sequential_tag) 02117 { return _GLIBCXX_STD_A::min_element(__begin, __end, __comp); } 02118 02119 // Sequential fallback for input iterator case 02120 template<typename _FIterator, typename _Compare, typename _IteratorTag> 02121 inline _FIterator 02122 __min_element_switch(_FIterator __begin, _FIterator __end, 02123 _Compare __comp, _IteratorTag) 02124 { return min_element(__begin, __end, __comp, 02125 __gnu_parallel::sequential_tag()); } 02126 02127 // Parallel algorithm for random access iterators 02128 template<typename _RAIter, typename _Compare> 02129 _RAIter 02130 __min_element_switch(_RAIter __begin, _RAIter __end, 02131 _Compare __comp, random_access_iterator_tag, 02132 __gnu_parallel::_Parallelism __parallelism_tag) 02133 { 02134 if (_GLIBCXX_PARALLEL_CONDITION( 02135 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 02136 >= __gnu_parallel::_Settings::get().min_element_minimal_n 02137 && __gnu_parallel::__is_parallel(__parallelism_tag))) 02138 { 02139 _RAIter __res(__begin); 02140 __gnu_parallel::__identity_selector<_RAIter> 02141 __functionality; 02142 __gnu_parallel:: 02143 __for_each_template_random_access( 02144 __begin, __end, __gnu_parallel::_Nothing(), __functionality, 02145 __gnu_parallel::__min_element_reduct<_Compare, _RAIter>(__comp), 02146 __res, __res, -1, __parallelism_tag); 02147 return __res; 02148 } 02149 else 02150 return min_element(__begin, __end, __comp, 02151 __gnu_parallel::sequential_tag()); 02152 } 02153 02154 // Public interface, insert default comparator 02155 template<typename _FIterator> 02156 inline _FIterator 02157 min_element(_FIterator __begin, _FIterator __end, 02158 __gnu_parallel::_Parallelism __parallelism_tag) 02159 { 02160 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 02161 return min_element(__begin, __end, std::less<_ValueType>(), 02162 __parallelism_tag); 02163 } 02164 02165 template<typename _FIterator> 02166 inline _FIterator 02167 min_element(_FIterator __begin, _FIterator __end) 02168 { 02169 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 02170 return __gnu_parallel::min_element(__begin, __end, 02171 std::less<_ValueType>()); 02172 } 02173 02174 // Public interface 02175 template<typename _FIterator, typename _Compare> 02176 inline _FIterator 02177 min_element(_FIterator __begin, _FIterator __end, _Compare __comp, 02178 __gnu_parallel::_Parallelism __parallelism_tag) 02179 { 02180 return __min_element_switch(__begin, __end, __comp, 02181 std::__iterator_category(__begin), 02182 __parallelism_tag); 02183 } 02184 02185 template<typename _FIterator, typename _Compare> 02186 inline _FIterator 02187 min_element(_FIterator __begin, _FIterator __end, _Compare __comp) 02188 { 02189 return __min_element_switch(__begin, __end, __comp, 02190 std::__iterator_category(__begin)); 02191 } 02192 } // end namespace 02193 } // end namespace 02194 02195 #endif /* _GLIBCXX_PARALLEL_ALGO_H */