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