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