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