1 // -*- C++ -*- 2 3 // Copyright (C) 2007-2014 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the terms 7 // of the GNU General Public License as published by the Free Software 8 // Foundation; either version 3, or (at your option) any later 9 // version. 10 11 // This library is distributed in the hope that it will be useful, but 12 // WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 // General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file parallel/algo.h 26 * @brief Parallel STL function calls corresponding to the stl_algo.h header. 27 * 28 * The functions defined here mainly do case switches and 29 * call the actual parallelized versions in other files. 30 * Inlining policy: Functions that basically only contain one function call, 31 * are declared inline. 32 * This file is a GNU parallel extension to the Standard C++ Library. 33 */ 34 35 // Written by Johannes Singler and Felix Putze. 36 37 #ifndef _GLIBCXX_PARALLEL_ALGO_H 38 #define _GLIBCXX_PARALLEL_ALGO_H 1 39 40 #include <parallel/algorithmfwd.h> 41 #include <bits/stl_algobase.h> 42 #include <bits/stl_algo.h> 43 #include <parallel/iterator.h> 44 #include <parallel/base.h> 45 #include <parallel/sort.h> 46 #include <parallel/workstealing.h> 47 #include <parallel/par_loop.h> 48 #include <parallel/omp_loop.h> 49 #include <parallel/omp_loop_static.h> 50 #include <parallel/for_each_selectors.h> 51 #include <parallel/for_each.h> 52 #include <parallel/find.h> 53 #include <parallel/find_selectors.h> 54 #include <parallel/search.h> 55 #include <parallel/random_shuffle.h> 56 #include <parallel/partition.h> 57 #include <parallel/merge.h> 58 #include <parallel/unique_copy.h> 59 #include <parallel/set_operations.h> 60 61 namespace std _GLIBCXX_VISIBILITY(default) 62 { 63 namespace __parallel 64 { 65 // Sequential fallback 66 template<typename _IIter, typename _Function> 67 inline _Function 68 for_each(_IIter __begin, _IIter __end, _Function __f, 69 __gnu_parallel::sequential_tag) 70 { return _GLIBCXX_STD_A::for_each(__begin, __end, __f); } 71 72 73 // Sequential fallback for input iterator case 74 template<typename _IIter, typename _Function, typename _IteratorTag> 75 inline _Function 76 __for_each_switch(_IIter __begin, _IIter __end, _Function __f, 77 _IteratorTag) 78 { return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag()); } 79 80 // Parallel algorithm for random access iterators 81 template<typename _RAIter, typename _Function> 82 _Function 83 __for_each_switch(_RAIter __begin, _RAIter __end, 84 _Function __f, random_access_iterator_tag, 85 __gnu_parallel::_Parallelism __parallelism_tag 86 = __gnu_parallel::parallel_balanced) 87 { 88 if (_GLIBCXX_PARALLEL_CONDITION( 89 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 90 >= __gnu_parallel::_Settings::get().for_each_minimal_n 91 && __gnu_parallel::__is_parallel(__parallelism_tag))) 92 { 93 bool __dummy; 94 __gnu_parallel::__for_each_selector<_RAIter> __functionality; 95 96 return __gnu_parallel:: 97 __for_each_template_random_access( 98 __begin, __end, __f, __functionality, 99 __gnu_parallel::_DummyReduct(), true, __dummy, -1, 100 __parallelism_tag); 101 } 102 else 103 return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag()); 104 } 105 106 // Public interface 107 template<typename _Iterator, typename _Function> 108 inline _Function 109 for_each(_Iterator __begin, _Iterator __end, _Function __f, 110 __gnu_parallel::_Parallelism __parallelism_tag) 111 { 112 typedef std::iterator_traits<_Iterator> _IteratorTraits; 113 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 114 return __for_each_switch(__begin, __end, __f, _IteratorCategory(), 115 __parallelism_tag); 116 } 117 118 template<typename _Iterator, typename _Function> 119 inline _Function 120 for_each(_Iterator __begin, _Iterator __end, _Function __f) 121 { 122 typedef std::iterator_traits<_Iterator> _IteratorTraits; 123 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 124 return __for_each_switch(__begin, __end, __f, _IteratorCategory()); 125 } 126 127 128 // Sequential fallback 129 template<typename _IIter, typename _Tp> 130 inline _IIter 131 find(_IIter __begin, _IIter __end, const _Tp& __val, 132 __gnu_parallel::sequential_tag) 133 { return _GLIBCXX_STD_A::find(__begin, __end, __val); } 134 135 // Sequential fallback for input iterator case 136 template<typename _IIter, typename _Tp, typename _IteratorTag> 137 inline _IIter 138 __find_switch(_IIter __begin, _IIter __end, const _Tp& __val, 139 _IteratorTag) 140 { return _GLIBCXX_STD_A::find(__begin, __end, __val); } 141 142 // Parallel find for random access iterators 143 template<typename _RAIter, typename _Tp> 144 _RAIter 145 __find_switch(_RAIter __begin, _RAIter __end, 146 const _Tp& __val, random_access_iterator_tag) 147 { 148 typedef iterator_traits<_RAIter> _TraitsType; 149 typedef typename _TraitsType::value_type _ValueType; 150 151 if (_GLIBCXX_PARALLEL_CONDITION(true)) 152 { 153 __gnu_parallel::__binder2nd<__gnu_parallel::_EqualTo<_ValueType, 154 const _Tp&>, 155 _ValueType, const _Tp&, bool> 156 __comp(__gnu_parallel::_EqualTo<_ValueType, const _Tp&>(), __val); 157 return __gnu_parallel::__find_template( 158 __begin, __end, __begin, __comp, 159 __gnu_parallel::__find_if_selector()).first; 160 } 161 else 162 return _GLIBCXX_STD_A::find(__begin, __end, __val); 163 } 164 165 // Public interface 166 template<typename _IIter, typename _Tp> 167 inline _IIter 168 find(_IIter __begin, _IIter __end, const _Tp& __val) 169 { 170 typedef std::iterator_traits<_IIter> _IteratorTraits; 171 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 172 return __find_switch(__begin, __end, __val, _IteratorCategory()); 173 } 174 175 // Sequential fallback 176 template<typename _IIter, typename _Predicate> 177 inline _IIter 178 find_if(_IIter __begin, _IIter __end, _Predicate __pred, 179 __gnu_parallel::sequential_tag) 180 { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); } 181 182 // Sequential fallback for input iterator case 183 template<typename _IIter, typename _Predicate, typename _IteratorTag> 184 inline _IIter 185 __find_if_switch(_IIter __begin, _IIter __end, _Predicate __pred, 186 _IteratorTag) 187 { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); } 188 189 // Parallel find_if for random access iterators 190 template<typename _RAIter, typename _Predicate> 191 _RAIter 192 __find_if_switch(_RAIter __begin, _RAIter __end, 193 _Predicate __pred, random_access_iterator_tag) 194 { 195 if (_GLIBCXX_PARALLEL_CONDITION(true)) 196 return __gnu_parallel::__find_template(__begin, __end, __begin, __pred, 197 __gnu_parallel:: 198 __find_if_selector()).first; 199 else 200 return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); 201 } 202 203 // Public interface 204 template<typename _IIter, typename _Predicate> 205 inline _IIter 206 find_if(_IIter __begin, _IIter __end, _Predicate __pred) 207 { 208 typedef std::iterator_traits<_IIter> _IteratorTraits; 209 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 210 return __find_if_switch(__begin, __end, __pred, _IteratorCategory()); 211 } 212 213 // Sequential fallback 214 template<typename _IIter, typename _FIterator> 215 inline _IIter 216 find_first_of(_IIter __begin1, _IIter __end1, 217 _FIterator __begin2, _FIterator __end2, 218 __gnu_parallel::sequential_tag) 219 { return _GLIBCXX_STD_A::find_first_of(__begin1, __end1, __begin2, __end2); 220 } 221 222 // Sequential fallback 223 template<typename _IIter, typename _FIterator, 224 typename _BinaryPredicate> 225 inline _IIter 226 find_first_of(_IIter __begin1, _IIter __end1, 227 _FIterator __begin2, _FIterator __end2, 228 _BinaryPredicate __comp, __gnu_parallel::sequential_tag) 229 { return _GLIBCXX_STD_A::find_first_of( 230 __begin1, __end1, __begin2, __end2, __comp); } 231 232 // Sequential fallback for input iterator type 233 template<typename _IIter, typename _FIterator, 234 typename _IteratorTag1, typename _IteratorTag2> 235 inline _IIter 236 __find_first_of_switch(_IIter __begin1, _IIter __end1, 237 _FIterator __begin2, _FIterator __end2, 238 _IteratorTag1, _IteratorTag2) 239 { return find_first_of(__begin1, __end1, __begin2, __end2, 240 __gnu_parallel::sequential_tag()); } 241 242 // Parallel algorithm for random access iterators 243 template<typename _RAIter, typename _FIterator, 244 typename _BinaryPredicate, typename _IteratorTag> 245 inline _RAIter 246 __find_first_of_switch(_RAIter __begin1, 247 _RAIter __end1, 248 _FIterator __begin2, _FIterator __end2, 249 _BinaryPredicate __comp, random_access_iterator_tag, 250 _IteratorTag) 251 { 252 return __gnu_parallel:: 253 __find_template(__begin1, __end1, __begin1, __comp, 254 __gnu_parallel::__find_first_of_selector 255 <_FIterator>(__begin2, __end2)).first; 256 } 257 258 // Sequential fallback for input iterator type 259 template<typename _IIter, typename _FIterator, 260 typename _BinaryPredicate, typename _IteratorTag1, 261 typename _IteratorTag2> 262 inline _IIter 263 __find_first_of_switch(_IIter __begin1, _IIter __end1, 264 _FIterator __begin2, _FIterator __end2, 265 _BinaryPredicate __comp, _IteratorTag1, _IteratorTag2) 266 { return find_first_of(__begin1, __end1, __begin2, __end2, __comp, 267 __gnu_parallel::sequential_tag()); } 268 269 // Public interface 270 template<typename _IIter, typename _FIterator, 271 typename _BinaryPredicate> 272 inline _IIter 273 find_first_of(_IIter __begin1, _IIter __end1, 274 _FIterator __begin2, _FIterator __end2, 275 _BinaryPredicate __comp) 276 { 277 typedef std::iterator_traits<_IIter> _IIterTraits; 278 typedef std::iterator_traits<_FIterator> _FIterTraits; 279 typedef typename _IIterTraits::iterator_category _IIteratorCategory; 280 typedef typename _FIterTraits::iterator_category _FIteratorCategory; 281 282 return __find_first_of_switch(__begin1, __end1, __begin2, __end2, __comp, 283 _IIteratorCategory(), _FIteratorCategory()); 284 } 285 286 // Public interface, insert default comparator 287 template<typename _IIter, typename _FIterator> 288 inline _IIter 289 find_first_of(_IIter __begin1, _IIter __end1, 290 _FIterator __begin2, _FIterator __end2) 291 { 292 typedef std::iterator_traits<_IIter> _IIterTraits; 293 typedef std::iterator_traits<_FIterator> _FIterTraits; 294 typedef typename _IIterTraits::value_type _IValueType; 295 typedef typename _FIterTraits::value_type _FValueType; 296 297 return __gnu_parallel::find_first_of(__begin1, __end1, __begin2, __end2, 298 __gnu_parallel::_EqualTo<_IValueType, _FValueType>()); 299 } 300 301 // Sequential fallback 302 template<typename _IIter, typename _OutputIterator> 303 inline _OutputIterator 304 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out, 305 __gnu_parallel::sequential_tag) 306 { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out); } 307 308 // Sequential fallback 309 template<typename _IIter, typename _OutputIterator, 310 typename _Predicate> 311 inline _OutputIterator 312 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out, 313 _Predicate __pred, __gnu_parallel::sequential_tag) 314 { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out, __pred); } 315 316 // Sequential fallback for input iterator case 317 template<typename _IIter, typename _OutputIterator, 318 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 319 inline _OutputIterator 320 __unique_copy_switch(_IIter __begin, _IIter __last, 321 _OutputIterator __out, _Predicate __pred, 322 _IteratorTag1, _IteratorTag2) 323 { return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred); } 324 325 // Parallel unique_copy for random access iterators 326 template<typename _RAIter, typename RandomAccessOutputIterator, 327 typename _Predicate> 328 RandomAccessOutputIterator 329 __unique_copy_switch(_RAIter __begin, _RAIter __last, 330 RandomAccessOutputIterator __out, _Predicate __pred, 331 random_access_iterator_tag, random_access_iterator_tag) 332 { 333 if (_GLIBCXX_PARALLEL_CONDITION( 334 static_cast<__gnu_parallel::_SequenceIndex>(__last - __begin) 335 > __gnu_parallel::_Settings::get().unique_copy_minimal_n)) 336 return __gnu_parallel::__parallel_unique_copy( 337 __begin, __last, __out, __pred); 338 else 339 return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred); 340 } 341 342 // Public interface 343 template<typename _IIter, typename _OutputIterator> 344 inline _OutputIterator 345 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out) 346 { 347 typedef std::iterator_traits<_IIter> _IIterTraits; 348 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 349 typedef typename _IIterTraits::iterator_category _IIteratorCategory; 350 typedef typename _IIterTraits::value_type _ValueType; 351 typedef typename _OIterTraits::iterator_category _OIterCategory; 352 353 return __unique_copy_switch( 354 __begin1, __end1, __out, equal_to<_ValueType>(), 355 _IIteratorCategory(), _OIterCategory()); 356 } 357 358 // Public interface 359 template<typename _IIter, typename _OutputIterator, typename _Predicate> 360 inline _OutputIterator 361 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out, 362 _Predicate __pred) 363 { 364 typedef std::iterator_traits<_IIter> _IIterTraits; 365 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 366 typedef typename _IIterTraits::iterator_category _IIteratorCategory; 367 typedef typename _OIterTraits::iterator_category _OIterCategory; 368 369 return __unique_copy_switch( 370 __begin1, __end1, __out, __pred, 371 _IIteratorCategory(), _OIterCategory()); 372 } 373 374 // Sequential fallback 375 template<typename _IIter1, typename _IIter2, 376 typename _OutputIterator> 377 inline _OutputIterator 378 set_union(_IIter1 __begin1, _IIter1 __end1, 379 _IIter2 __begin2, _IIter2 __end2, 380 _OutputIterator __out, __gnu_parallel::sequential_tag) 381 { return _GLIBCXX_STD_A::set_union( 382 __begin1, __end1, __begin2, __end2, __out); } 383 384 // Sequential fallback 385 template<typename _IIter1, typename _IIter2, 386 typename _OutputIterator, typename _Predicate> 387 inline _OutputIterator 388 set_union(_IIter1 __begin1, _IIter1 __end1, 389 _IIter2 __begin2, _IIter2 __end2, 390 _OutputIterator __out, _Predicate __pred, 391 __gnu_parallel::sequential_tag) 392 { return _GLIBCXX_STD_A::set_union(__begin1, __end1, 393 __begin2, __end2, __out, __pred); } 394 395 // Sequential fallback for input iterator case 396 template<typename _IIter1, typename _IIter2, typename _Predicate, 397 typename _OutputIterator, typename _IteratorTag1, 398 typename _IteratorTag2, typename _IteratorTag3> 399 inline _OutputIterator 400 __set_union_switch( 401 _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2, 402 _OutputIterator __result, _Predicate __pred, 403 _IteratorTag1, _IteratorTag2, _IteratorTag3) 404 { return _GLIBCXX_STD_A::set_union(__begin1, __end1, 405 __begin2, __end2, __result, __pred); } 406 407 // Parallel set_union for random access iterators 408 template<typename _RAIter1, typename _RAIter2, 409 typename _Output_RAIter, typename _Predicate> 410 _Output_RAIter 411 __set_union_switch(_RAIter1 __begin1, _RAIter1 __end1, 412 _RAIter2 __begin2, _RAIter2 __end2, 413 _Output_RAIter __result, _Predicate __pred, 414 random_access_iterator_tag, random_access_iterator_tag, 415 random_access_iterator_tag) 416 { 417 if (_GLIBCXX_PARALLEL_CONDITION( 418 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 419 >= __gnu_parallel::_Settings::get().set_union_minimal_n 420 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) 421 >= __gnu_parallel::_Settings::get().set_union_minimal_n)) 422 return __gnu_parallel::__parallel_set_union( 423 __begin1, __end1, __begin2, __end2, __result, __pred); 424 else 425 return _GLIBCXX_STD_A::set_union(__begin1, __end1, 426 __begin2, __end2, __result, __pred); 427 } 428 429 // Public interface 430 template<typename _IIter1, typename _IIter2, 431 typename _OutputIterator> 432 inline _OutputIterator 433 set_union(_IIter1 __begin1, _IIter1 __end1, 434 _IIter2 __begin2, _IIter2 __end2, _OutputIterator __out) 435 { 436 typedef std::iterator_traits<_IIter1> _IIterTraits1; 437 typedef std::iterator_traits<_IIter2> _IIterTraits2; 438 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 439 typedef typename _IIterTraits1::iterator_category 440 _IIterCategory1; 441 typedef typename _IIterTraits2::iterator_category 442 _IIterCategory2; 443 typedef typename _OIterTraits::iterator_category _OIterCategory; 444 typedef typename _IIterTraits1::value_type _ValueType1; 445 typedef typename _IIterTraits2::value_type _ValueType2; 446 447 return __set_union_switch( 448 __begin1, __end1, __begin2, __end2, __out, 449 __gnu_parallel::_Less<_ValueType1, _ValueType2>(), 450 _IIterCategory1(), _IIterCategory2(), _OIterCategory()); 451 } 452 453 // Public interface 454 template<typename _IIter1, typename _IIter2, 455 typename _OutputIterator, typename _Predicate> 456 inline _OutputIterator 457 set_union(_IIter1 __begin1, _IIter1 __end1, 458 _IIter2 __begin2, _IIter2 __end2, 459 _OutputIterator __out, _Predicate __pred) 460 { 461 typedef std::iterator_traits<_IIter1> _IIterTraits1; 462 typedef std::iterator_traits<_IIter2> _IIterTraits2; 463 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 464 typedef typename _IIterTraits1::iterator_category 465 _IIterCategory1; 466 typedef typename _IIterTraits2::iterator_category 467 _IIterCategory2; 468 typedef typename _OIterTraits::iterator_category _OIterCategory; 469 470 return __set_union_switch( 471 __begin1, __end1, __begin2, __end2, __out, __pred, 472 _IIterCategory1(), _IIterCategory2(), _OIterCategory()); 473 } 474 475 // Sequential fallback. 476 template<typename _IIter1, typename _IIter2, 477 typename _OutputIterator> 478 inline _OutputIterator 479 set_intersection(_IIter1 __begin1, _IIter1 __end1, 480 _IIter2 __begin2, _IIter2 __end2, 481 _OutputIterator __out, __gnu_parallel::sequential_tag) 482 { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1, 483 __begin2, __end2, __out); } 484 485 // Sequential fallback. 486 template<typename _IIter1, typename _IIter2, 487 typename _OutputIterator, typename _Predicate> 488 inline _OutputIterator 489 set_intersection(_IIter1 __begin1, _IIter1 __end1, 490 _IIter2 __begin2, _IIter2 __end2, 491 _OutputIterator __out, _Predicate __pred, 492 __gnu_parallel::sequential_tag) 493 { return _GLIBCXX_STD_A::set_intersection( 494 __begin1, __end1, __begin2, __end2, __out, __pred); } 495 496 // Sequential fallback for input iterator case 497 template<typename _IIter1, typename _IIter2, 498 typename _Predicate, typename _OutputIterator, 499 typename _IteratorTag1, typename _IteratorTag2, 500 typename _IteratorTag3> 501 inline _OutputIterator 502 __set_intersection_switch(_IIter1 __begin1, _IIter1 __end1, 503 _IIter2 __begin2, _IIter2 __end2, 504 _OutputIterator __result, _Predicate __pred, 505 _IteratorTag1, _IteratorTag2, _IteratorTag3) 506 { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1, __begin2, 507 __end2, __result, __pred); } 508 509 // Parallel set_intersection for random access iterators 510 template<typename _RAIter1, typename _RAIter2, 511 typename _Output_RAIter, typename _Predicate> 512 _Output_RAIter 513 __set_intersection_switch(_RAIter1 __begin1, 514 _RAIter1 __end1, 515 _RAIter2 __begin2, 516 _RAIter2 __end2, 517 _Output_RAIter __result, 518 _Predicate __pred, 519 random_access_iterator_tag, 520 random_access_iterator_tag, 521 random_access_iterator_tag) 522 { 523 if (_GLIBCXX_PARALLEL_CONDITION( 524 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 525 >= __gnu_parallel::_Settings::get().set_union_minimal_n 526 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) 527 >= __gnu_parallel::_Settings::get().set_union_minimal_n)) 528 return __gnu_parallel::__parallel_set_intersection( 529 __begin1, __end1, __begin2, __end2, __result, __pred); 530 else 531 return _GLIBCXX_STD_A::set_intersection( 532 __begin1, __end1, __begin2, __end2, __result, __pred); 533 } 534 535 // Public interface 536 template<typename _IIter1, typename _IIter2, 537 typename _OutputIterator> 538 inline _OutputIterator 539 set_intersection(_IIter1 __begin1, _IIter1 __end1, 540 _IIter2 __begin2, _IIter2 __end2, 541 _OutputIterator __out) 542 { 543 typedef std::iterator_traits<_IIter1> _IIterTraits1; 544 typedef std::iterator_traits<_IIter2> _IIterTraits2; 545 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 546 typedef typename _IIterTraits1::iterator_category 547 _IIterCategory1; 548 typedef typename _IIterTraits2::iterator_category 549 _IIterCategory2; 550 typedef typename _OIterTraits::iterator_category _OIterCategory; 551 typedef typename _IIterTraits1::value_type _ValueType1; 552 typedef typename _IIterTraits2::value_type _ValueType2; 553 554 return __set_intersection_switch( 555 __begin1, __end1, __begin2, __end2, __out, 556 __gnu_parallel::_Less<_ValueType1, _ValueType2>(), 557 _IIterCategory1(), _IIterCategory2(), _OIterCategory()); 558 } 559 560 template<typename _IIter1, typename _IIter2, 561 typename _OutputIterator, typename _Predicate> 562 inline _OutputIterator 563 set_intersection(_IIter1 __begin1, _IIter1 __end1, 564 _IIter2 __begin2, _IIter2 __end2, 565 _OutputIterator __out, _Predicate __pred) 566 { 567 typedef std::iterator_traits<_IIter1> _IIterTraits1; 568 typedef std::iterator_traits<_IIter2> _IIterTraits2; 569 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 570 typedef typename _IIterTraits1::iterator_category 571 _IIterCategory1; 572 typedef typename _IIterTraits2::iterator_category 573 _IIterCategory2; 574 typedef typename _OIterTraits::iterator_category _OIterCategory; 575 576 return __set_intersection_switch( 577 __begin1, __end1, __begin2, __end2, __out, __pred, 578 _IIterCategory1(), _IIterCategory2(), _OIterCategory()); 579 } 580 581 // Sequential fallback 582 template<typename _IIter1, typename _IIter2, 583 typename _OutputIterator> 584 inline _OutputIterator 585 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1, 586 _IIter2 __begin2, _IIter2 __end2, 587 _OutputIterator __out, 588 __gnu_parallel::sequential_tag) 589 { return _GLIBCXX_STD_A::set_symmetric_difference( 590 __begin1, __end1, __begin2, __end2, __out); } 591 592 // Sequential fallback 593 template<typename _IIter1, typename _IIter2, 594 typename _OutputIterator, typename _Predicate> 595 inline _OutputIterator 596 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1, 597 _IIter2 __begin2, _IIter2 __end2, 598 _OutputIterator __out, _Predicate __pred, 599 __gnu_parallel::sequential_tag) 600 { return _GLIBCXX_STD_A::set_symmetric_difference( 601 __begin1, __end1, __begin2, __end2, __out, __pred); } 602 603 // Sequential fallback for input iterator case 604 template<typename _IIter1, typename _IIter2, 605 typename _Predicate, typename _OutputIterator, 606 typename _IteratorTag1, typename _IteratorTag2, 607 typename _IteratorTag3> 608 inline _OutputIterator 609 __set_symmetric_difference_switch( 610 _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2, 611 _OutputIterator __result, _Predicate __pred, 612 _IteratorTag1, _IteratorTag2, _IteratorTag3) 613 { return _GLIBCXX_STD_A::set_symmetric_difference( 614 __begin1, __end1, __begin2, __end2, __result, __pred); } 615 616 // Parallel set_symmetric_difference for random access iterators 617 template<typename _RAIter1, typename _RAIter2, 618 typename _Output_RAIter, typename _Predicate> 619 _Output_RAIter 620 __set_symmetric_difference_switch(_RAIter1 __begin1, 621 _RAIter1 __end1, 622 _RAIter2 __begin2, 623 _RAIter2 __end2, 624 _Output_RAIter __result, 625 _Predicate __pred, 626 random_access_iterator_tag, 627 random_access_iterator_tag, 628 random_access_iterator_tag) 629 { 630 if (_GLIBCXX_PARALLEL_CONDITION( 631 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 632 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n 633 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) 634 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n)) 635 return __gnu_parallel::__parallel_set_symmetric_difference( 636 __begin1, __end1, __begin2, __end2, __result, __pred); 637 else 638 return _GLIBCXX_STD_A::set_symmetric_difference( 639 __begin1, __end1, __begin2, __end2, __result, __pred); 640 } 641 642 // Public interface. 643 template<typename _IIter1, typename _IIter2, 644 typename _OutputIterator> 645 inline _OutputIterator 646 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1, 647 _IIter2 __begin2, _IIter2 __end2, 648 _OutputIterator __out) 649 { 650 typedef std::iterator_traits<_IIter1> _IIterTraits1; 651 typedef std::iterator_traits<_IIter2> _IIterTraits2; 652 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 653 typedef typename _IIterTraits1::iterator_category 654 _IIterCategory1; 655 typedef typename _IIterTraits2::iterator_category 656 _IIterCategory2; 657 typedef typename _OIterTraits::iterator_category _OIterCategory; 658 typedef typename _IIterTraits1::value_type _ValueType1; 659 typedef typename _IIterTraits2::value_type _ValueType2; 660 661 return __set_symmetric_difference_switch( 662 __begin1, __end1, __begin2, __end2, __out, 663 __gnu_parallel::_Less<_ValueType1, _ValueType2>(), 664 _IIterCategory1(), _IIterCategory2(), _OIterCategory()); 665 } 666 667 // Public interface. 668 template<typename _IIter1, typename _IIter2, 669 typename _OutputIterator, typename _Predicate> 670 inline _OutputIterator 671 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1, 672 _IIter2 __begin2, _IIter2 __end2, 673 _OutputIterator __out, _Predicate __pred) 674 { 675 typedef std::iterator_traits<_IIter1> _IIterTraits1; 676 typedef std::iterator_traits<_IIter2> _IIterTraits2; 677 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 678 typedef typename _IIterTraits1::iterator_category 679 _IIterCategory1; 680 typedef typename _IIterTraits2::iterator_category 681 _IIterCategory2; 682 typedef typename _OIterTraits::iterator_category _OIterCategory; 683 684 return __set_symmetric_difference_switch( 685 __begin1, __end1, __begin2, __end2, __out, __pred, 686 _IIterCategory1(), _IIterCategory2(), _OIterCategory()); 687 } 688 689 // Sequential fallback. 690 template<typename _IIter1, typename _IIter2, 691 typename _OutputIterator> 692 inline _OutputIterator 693 set_difference(_IIter1 __begin1, _IIter1 __end1, 694 _IIter2 __begin2, _IIter2 __end2, 695 _OutputIterator __out, __gnu_parallel::sequential_tag) 696 { return _GLIBCXX_STD_A::set_difference( 697 __begin1,__end1, __begin2, __end2, __out); } 698 699 // Sequential fallback. 700 template<typename _IIter1, typename _IIter2, 701 typename _OutputIterator, typename _Predicate> 702 inline _OutputIterator 703 set_difference(_IIter1 __begin1, _IIter1 __end1, 704 _IIter2 __begin2, _IIter2 __end2, 705 _OutputIterator __out, _Predicate __pred, 706 __gnu_parallel::sequential_tag) 707 { return _GLIBCXX_STD_A::set_difference(__begin1, __end1, 708 __begin2, __end2, __out, __pred); } 709 710 // Sequential fallback for input iterator case. 711 template<typename _IIter1, typename _IIter2, typename _Predicate, 712 typename _OutputIterator, typename _IteratorTag1, 713 typename _IteratorTag2, typename _IteratorTag3> 714 inline _OutputIterator 715 __set_difference_switch(_IIter1 __begin1, _IIter1 __end1, 716 _IIter2 __begin2, _IIter2 __end2, 717 _OutputIterator __result, _Predicate __pred, 718 _IteratorTag1, _IteratorTag2, _IteratorTag3) 719 { return _GLIBCXX_STD_A::set_difference( 720 __begin1, __end1, __begin2, __end2, __result, __pred); } 721 722 // Parallel set_difference for random access iterators 723 template<typename _RAIter1, typename _RAIter2, 724 typename _Output_RAIter, typename _Predicate> 725 _Output_RAIter 726 __set_difference_switch(_RAIter1 __begin1, 727 _RAIter1 __end1, 728 _RAIter2 __begin2, 729 _RAIter2 __end2, 730 _Output_RAIter __result, _Predicate __pred, 731 random_access_iterator_tag, 732 random_access_iterator_tag, 733 random_access_iterator_tag) 734 { 735 if (_GLIBCXX_PARALLEL_CONDITION( 736 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 737 >= __gnu_parallel::_Settings::get().set_difference_minimal_n 738 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) 739 >= __gnu_parallel::_Settings::get().set_difference_minimal_n)) 740 return __gnu_parallel::__parallel_set_difference( 741 __begin1, __end1, __begin2, __end2, __result, __pred); 742 else 743 return _GLIBCXX_STD_A::set_difference( 744 __begin1, __end1, __begin2, __end2, __result, __pred); 745 } 746 747 // Public interface 748 template<typename _IIter1, typename _IIter2, 749 typename _OutputIterator> 750 inline _OutputIterator 751 set_difference(_IIter1 __begin1, _IIter1 __end1, 752 _IIter2 __begin2, _IIter2 __end2, 753 _OutputIterator __out) 754 { 755 typedef std::iterator_traits<_IIter1> _IIterTraits1; 756 typedef std::iterator_traits<_IIter2> _IIterTraits2; 757 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 758 typedef typename _IIterTraits1::iterator_category 759 _IIterCategory1; 760 typedef typename _IIterTraits2::iterator_category 761 _IIterCategory2; 762 typedef typename _OIterTraits::iterator_category _OIterCategory; 763 typedef typename _IIterTraits1::value_type _ValueType1; 764 typedef typename _IIterTraits2::value_type _ValueType2; 765 766 return __set_difference_switch( 767 __begin1, __end1, __begin2, __end2, __out, 768 __gnu_parallel::_Less<_ValueType1, _ValueType2>(), 769 _IIterCategory1(), _IIterCategory2(), _OIterCategory()); 770 } 771 772 // Public interface 773 template<typename _IIter1, typename _IIter2, 774 typename _OutputIterator, typename _Predicate> 775 inline _OutputIterator 776 set_difference(_IIter1 __begin1, _IIter1 __end1, 777 _IIter2 __begin2, _IIter2 __end2, 778 _OutputIterator __out, _Predicate __pred) 779 { 780 typedef std::iterator_traits<_IIter1> _IIterTraits1; 781 typedef std::iterator_traits<_IIter2> _IIterTraits2; 782 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 783 typedef typename _IIterTraits1::iterator_category 784 _IIterCategory1; 785 typedef typename _IIterTraits2::iterator_category 786 _IIterCategory2; 787 typedef typename _OIterTraits::iterator_category _OIterCategory; 788 789 return __set_difference_switch( 790 __begin1, __end1, __begin2, __end2, __out, __pred, 791 _IIterCategory1(), _IIterCategory2(), _OIterCategory()); 792 } 793 794 // Sequential fallback 795 template<typename _FIterator> 796 inline _FIterator 797 adjacent_find(_FIterator __begin, _FIterator __end, 798 __gnu_parallel::sequential_tag) 799 { return _GLIBCXX_STD_A::adjacent_find(__begin, __end); } 800 801 // Sequential fallback 802 template<typename _FIterator, typename _BinaryPredicate> 803 inline _FIterator 804 adjacent_find(_FIterator __begin, _FIterator __end, 805 _BinaryPredicate __binary_pred, 806 __gnu_parallel::sequential_tag) 807 { return _GLIBCXX_STD_A::adjacent_find(__begin, __end, __binary_pred); } 808 809 // Parallel algorithm for random access iterators 810 template<typename _RAIter> 811 _RAIter 812 __adjacent_find_switch(_RAIter __begin, _RAIter __end, 813 random_access_iterator_tag) 814 { 815 typedef iterator_traits<_RAIter> _TraitsType; 816 typedef typename _TraitsType::value_type _ValueType; 817 818 if (_GLIBCXX_PARALLEL_CONDITION(true)) 819 { 820 _RAIter __spot = __gnu_parallel:: 821 __find_template( 822 __begin, __end - 1, __begin, equal_to<_ValueType>(), 823 __gnu_parallel::__adjacent_find_selector()) 824 .first; 825 if (__spot == (__end - 1)) 826 return __end; 827 else 828 return __spot; 829 } 830 else 831 return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag()); 832 } 833 834 // Sequential fallback for input iterator case 835 template<typename _FIterator, typename _IteratorTag> 836 inline _FIterator 837 __adjacent_find_switch(_FIterator __begin, _FIterator __end, 838 _IteratorTag) 839 { return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag()); } 840 841 // Public interface 842 template<typename _FIterator> 843 inline _FIterator 844 adjacent_find(_FIterator __begin, _FIterator __end) 845 { 846 typedef iterator_traits<_FIterator> _TraitsType; 847 typedef typename _TraitsType::iterator_category _IteratorCategory; 848 return __adjacent_find_switch(__begin, __end, _IteratorCategory()); 849 } 850 851 // Sequential fallback for input iterator case 852 template<typename _FIterator, typename _BinaryPredicate, 853 typename _IteratorTag> 854 inline _FIterator 855 __adjacent_find_switch(_FIterator __begin, _FIterator __end, 856 _BinaryPredicate __pred, _IteratorTag) 857 { return adjacent_find(__begin, __end, __pred, 858 __gnu_parallel::sequential_tag()); } 859 860 // Parallel algorithm for random access iterators 861 template<typename _RAIter, typename _BinaryPredicate> 862 _RAIter 863 __adjacent_find_switch(_RAIter __begin, _RAIter __end, 864 _BinaryPredicate __pred, random_access_iterator_tag) 865 { 866 if (_GLIBCXX_PARALLEL_CONDITION(true)) 867 return __gnu_parallel::__find_template(__begin, __end, __begin, __pred, 868 __gnu_parallel:: 869 __adjacent_find_selector()).first; 870 else 871 return adjacent_find(__begin, __end, __pred, 872 __gnu_parallel::sequential_tag()); 873 } 874 875 // Public interface 876 template<typename _FIterator, typename _BinaryPredicate> 877 inline _FIterator 878 adjacent_find(_FIterator __begin, _FIterator __end, 879 _BinaryPredicate __pred) 880 { 881 typedef iterator_traits<_FIterator> _TraitsType; 882 typedef typename _TraitsType::iterator_category _IteratorCategory; 883 return __adjacent_find_switch(__begin, __end, __pred, 884 _IteratorCategory()); 885 } 886 887 // Sequential fallback 888 template<typename _IIter, typename _Tp> 889 inline typename iterator_traits<_IIter>::difference_type 890 count(_IIter __begin, _IIter __end, const _Tp& __value, 891 __gnu_parallel::sequential_tag) 892 { return _GLIBCXX_STD_A::count(__begin, __end, __value); } 893 894 // Parallel code for random access iterators 895 template<typename _RAIter, typename _Tp> 896 typename iterator_traits<_RAIter>::difference_type 897 __count_switch(_RAIter __begin, _RAIter __end, 898 const _Tp& __value, random_access_iterator_tag, 899 __gnu_parallel::_Parallelism __parallelism_tag 900 = __gnu_parallel::parallel_unbalanced) 901 { 902 typedef iterator_traits<_RAIter> _TraitsType; 903 typedef typename _TraitsType::value_type _ValueType; 904 typedef typename _TraitsType::difference_type _DifferenceType; 905 typedef __gnu_parallel::_SequenceIndex _SequenceIndex; 906 907 if (_GLIBCXX_PARALLEL_CONDITION( 908 static_cast<_SequenceIndex>(__end - __begin) 909 >= __gnu_parallel::_Settings::get().count_minimal_n 910 && __gnu_parallel::__is_parallel(__parallelism_tag))) 911 { 912 __gnu_parallel::__count_selector<_RAIter, _DifferenceType> 913 __functionality; 914 _DifferenceType __res = 0; 915 __gnu_parallel:: 916 __for_each_template_random_access( 917 __begin, __end, __value, __functionality, 918 std::plus<_SequenceIndex>(), __res, __res, -1, 919 __parallelism_tag); 920 return __res; 921 } 922 else 923 return count(__begin, __end, __value, 924 __gnu_parallel::sequential_tag()); 925 } 926 927 // Sequential fallback for input iterator case. 928 template<typename _IIter, typename _Tp, typename _IteratorTag> 929 inline typename iterator_traits<_IIter>::difference_type 930 __count_switch(_IIter __begin, _IIter __end, const _Tp& __value, 931 _IteratorTag) 932 { return count(__begin, __end, __value, __gnu_parallel::sequential_tag()); 933 } 934 935 // Public interface. 936 template<typename _IIter, typename _Tp> 937 inline typename iterator_traits<_IIter>::difference_type 938 count(_IIter __begin, _IIter __end, const _Tp& __value, 939 __gnu_parallel::_Parallelism __parallelism_tag) 940 { 941 typedef iterator_traits<_IIter> _TraitsType; 942 typedef typename _TraitsType::iterator_category _IteratorCategory; 943 return __count_switch(__begin, __end, __value, _IteratorCategory(), 944 __parallelism_tag); 945 } 946 947 template<typename _IIter, typename _Tp> 948 inline typename iterator_traits<_IIter>::difference_type 949 count(_IIter __begin, _IIter __end, const _Tp& __value) 950 { 951 typedef iterator_traits<_IIter> _TraitsType; 952 typedef typename _TraitsType::iterator_category _IteratorCategory; 953 return __count_switch(__begin, __end, __value, _IteratorCategory()); 954 } 955 956 957 // Sequential fallback. 958 template<typename _IIter, typename _Predicate> 959 inline typename iterator_traits<_IIter>::difference_type 960 count_if(_IIter __begin, _IIter __end, _Predicate __pred, 961 __gnu_parallel::sequential_tag) 962 { return _GLIBCXX_STD_A::count_if(__begin, __end, __pred); } 963 964 // Parallel count_if for random access iterators 965 template<typename _RAIter, typename _Predicate> 966 typename iterator_traits<_RAIter>::difference_type 967 __count_if_switch(_RAIter __begin, _RAIter __end, 968 _Predicate __pred, random_access_iterator_tag, 969 __gnu_parallel::_Parallelism __parallelism_tag 970 = __gnu_parallel::parallel_unbalanced) 971 { 972 typedef iterator_traits<_RAIter> _TraitsType; 973 typedef typename _TraitsType::value_type _ValueType; 974 typedef typename _TraitsType::difference_type _DifferenceType; 975 typedef __gnu_parallel::_SequenceIndex _SequenceIndex; 976 977 if (_GLIBCXX_PARALLEL_CONDITION( 978 static_cast<_SequenceIndex>(__end - __begin) 979 >= __gnu_parallel::_Settings::get().count_minimal_n 980 && __gnu_parallel::__is_parallel(__parallelism_tag))) 981 { 982 _DifferenceType __res = 0; 983 __gnu_parallel:: 984 __count_if_selector<_RAIter, _DifferenceType> 985 __functionality; 986 __gnu_parallel:: 987 __for_each_template_random_access( 988 __begin, __end, __pred, __functionality, 989 std::plus<_SequenceIndex>(), __res, __res, -1, 990 __parallelism_tag); 991 return __res; 992 } 993 else 994 return count_if(__begin, __end, __pred, 995 __gnu_parallel::sequential_tag()); 996 } 997 998 // Sequential fallback for input iterator case. 999 template<typename _IIter, typename _Predicate, typename _IteratorTag> 1000 inline typename iterator_traits<_IIter>::difference_type 1001 __count_if_switch(_IIter __begin, _IIter __end, _Predicate __pred, 1002 _IteratorTag) 1003 { return count_if(__begin, __end, __pred, 1004 __gnu_parallel::sequential_tag()); } 1005 1006 // Public interface. 1007 template<typename _IIter, typename _Predicate> 1008 inline typename iterator_traits<_IIter>::difference_type 1009 count_if(_IIter __begin, _IIter __end, _Predicate __pred, 1010 __gnu_parallel::_Parallelism __parallelism_tag) 1011 { 1012 typedef iterator_traits<_IIter> _TraitsType; 1013 typedef typename _TraitsType::iterator_category _IteratorCategory; 1014 return __count_if_switch(__begin, __end, __pred, _IteratorCategory(), 1015 __parallelism_tag); 1016 } 1017 1018 template<typename _IIter, typename _Predicate> 1019 inline typename iterator_traits<_IIter>::difference_type 1020 count_if(_IIter __begin, _IIter __end, _Predicate __pred) 1021 { 1022 typedef iterator_traits<_IIter> _TraitsType; 1023 typedef typename _TraitsType::iterator_category _IteratorCategory; 1024 return __count_if_switch(__begin, __end, __pred, _IteratorCategory()); 1025 } 1026 1027 1028 // Sequential fallback. 1029 template<typename _FIterator1, typename _FIterator2> 1030 inline _FIterator1 1031 search(_FIterator1 __begin1, _FIterator1 __end1, 1032 _FIterator2 __begin2, _FIterator2 __end2, 1033 __gnu_parallel::sequential_tag) 1034 { return _GLIBCXX_STD_A::search(__begin1, __end1, __begin2, __end2); } 1035 1036 // Parallel algorithm for random access iterator 1037 template<typename _RAIter1, typename _RAIter2> 1038 _RAIter1 1039 __search_switch(_RAIter1 __begin1, _RAIter1 __end1, 1040 _RAIter2 __begin2, _RAIter2 __end2, 1041 random_access_iterator_tag, random_access_iterator_tag) 1042 { 1043 typedef std::iterator_traits<_RAIter1> _Iterator1Traits; 1044 typedef typename _Iterator1Traits::value_type _ValueType1; 1045 typedef std::iterator_traits<_RAIter2> _Iterator2Traits; 1046 typedef typename _Iterator2Traits::value_type _ValueType2; 1047 1048 if (_GLIBCXX_PARALLEL_CONDITION( 1049 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 1050 >= __gnu_parallel::_Settings::get().search_minimal_n)) 1051 return __gnu_parallel:: 1052 __search_template( 1053 __begin1, __end1, __begin2, __end2, 1054 __gnu_parallel::_EqualTo<_ValueType1, _ValueType2>()); 1055 else 1056 return search(__begin1, __end1, __begin2, __end2, 1057 __gnu_parallel::sequential_tag()); 1058 } 1059 1060 // Sequential fallback for input iterator case 1061 template<typename _FIterator1, typename _FIterator2, 1062 typename _IteratorTag1, typename _IteratorTag2> 1063 inline _FIterator1 1064 __search_switch(_FIterator1 __begin1, _FIterator1 __end1, 1065 _FIterator2 __begin2, _FIterator2 __end2, 1066 _IteratorTag1, _IteratorTag2) 1067 { return search(__begin1, __end1, __begin2, __end2, 1068 __gnu_parallel::sequential_tag()); } 1069 1070 // Public interface. 1071 template<typename _FIterator1, typename _FIterator2> 1072 inline _FIterator1 1073 search(_FIterator1 __begin1, _FIterator1 __end1, 1074 _FIterator2 __begin2, _FIterator2 __end2) 1075 { 1076 typedef std::iterator_traits<_FIterator1> _Iterator1Traits; 1077 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1; 1078 typedef std::iterator_traits<_FIterator2> _Iterator2Traits; 1079 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2; 1080 1081 return __search_switch(__begin1, __end1, __begin2, __end2, 1082 _IteratorCategory1(), _IteratorCategory2()); 1083 } 1084 1085 // Public interface. 1086 template<typename _FIterator1, typename _FIterator2, 1087 typename _BinaryPredicate> 1088 inline _FIterator1 1089 search(_FIterator1 __begin1, _FIterator1 __end1, 1090 _FIterator2 __begin2, _FIterator2 __end2, 1091 _BinaryPredicate __pred, __gnu_parallel::sequential_tag) 1092 { return _GLIBCXX_STD_A::search( 1093 __begin1, __end1, __begin2, __end2, __pred); } 1094 1095 // Parallel algorithm for random access iterator. 1096 template<typename _RAIter1, typename _RAIter2, 1097 typename _BinaryPredicate> 1098 _RAIter1 1099 __search_switch(_RAIter1 __begin1, _RAIter1 __end1, 1100 _RAIter2 __begin2, _RAIter2 __end2, 1101 _BinaryPredicate __pred, 1102 random_access_iterator_tag, random_access_iterator_tag) 1103 { 1104 if (_GLIBCXX_PARALLEL_CONDITION( 1105 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 1106 >= __gnu_parallel::_Settings::get().search_minimal_n)) 1107 return __gnu_parallel::__search_template(__begin1, __end1, 1108 __begin2, __end2, __pred); 1109 else 1110 return search(__begin1, __end1, __begin2, __end2, __pred, 1111 __gnu_parallel::sequential_tag()); 1112 } 1113 1114 // Sequential fallback for input iterator case 1115 template<typename _FIterator1, typename _FIterator2, 1116 typename _BinaryPredicate, typename _IteratorTag1, 1117 typename _IteratorTag2> 1118 inline _FIterator1 1119 __search_switch(_FIterator1 __begin1, _FIterator1 __end1, 1120 _FIterator2 __begin2, _FIterator2 __end2, 1121 _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2) 1122 { return search(__begin1, __end1, __begin2, __end2, __pred, 1123 __gnu_parallel::sequential_tag()); } 1124 1125 // Public interface 1126 template<typename _FIterator1, typename _FIterator2, 1127 typename _BinaryPredicate> 1128 inline _FIterator1 1129 search(_FIterator1 __begin1, _FIterator1 __end1, 1130 _FIterator2 __begin2, _FIterator2 __end2, 1131 _BinaryPredicate __pred) 1132 { 1133 typedef std::iterator_traits<_FIterator1> _Iterator1Traits; 1134 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1; 1135 typedef std::iterator_traits<_FIterator2> _Iterator2Traits; 1136 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2; 1137 return __search_switch(__begin1, __end1, __begin2, __end2, __pred, 1138 _IteratorCategory1(), _IteratorCategory2()); 1139 } 1140 1141 // Sequential fallback 1142 template<typename _FIterator, typename _Integer, typename _Tp> 1143 inline _FIterator 1144 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 1145 const _Tp& __val, __gnu_parallel::sequential_tag) 1146 { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val); } 1147 1148 // Sequential fallback 1149 template<typename _FIterator, typename _Integer, typename _Tp, 1150 typename _BinaryPredicate> 1151 inline _FIterator 1152 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 1153 const _Tp& __val, _BinaryPredicate __binary_pred, 1154 __gnu_parallel::sequential_tag) 1155 { return _GLIBCXX_STD_A::search_n( 1156 __begin, __end, __count, __val, __binary_pred); } 1157 1158 // Public interface. 1159 template<typename _FIterator, typename _Integer, typename _Tp> 1160 inline _FIterator 1161 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 1162 const _Tp& __val) 1163 { 1164 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 1165 return __gnu_parallel::search_n(__begin, __end, __count, __val, 1166 __gnu_parallel::_EqualTo<_ValueType, _Tp>()); 1167 } 1168 1169 // Parallel algorithm for random access iterators. 1170 template<typename _RAIter, typename _Integer, 1171 typename _Tp, typename _BinaryPredicate> 1172 _RAIter 1173 __search_n_switch(_RAIter __begin, _RAIter __end, _Integer __count, 1174 const _Tp& __val, _BinaryPredicate __binary_pred, 1175 random_access_iterator_tag) 1176 { 1177 if (_GLIBCXX_PARALLEL_CONDITION( 1178 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1179 >= __gnu_parallel::_Settings::get().search_minimal_n)) 1180 { 1181 __gnu_parallel::_PseudoSequence<_Tp, _Integer> __ps(__val, __count); 1182 return __gnu_parallel::__search_template( 1183 __begin, __end, __ps.begin(), __ps.end(), __binary_pred); 1184 } 1185 else 1186 return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val, 1187 __binary_pred); 1188 } 1189 1190 // Sequential fallback for input iterator case. 1191 template<typename _FIterator, typename _Integer, typename _Tp, 1192 typename _BinaryPredicate, typename _IteratorTag> 1193 inline _FIterator 1194 __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count, 1195 const _Tp& __val, _BinaryPredicate __binary_pred, 1196 _IteratorTag) 1197 { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val, 1198 __binary_pred); } 1199 1200 // Public interface. 1201 template<typename _FIterator, typename _Integer, typename _Tp, 1202 typename _BinaryPredicate> 1203 inline _FIterator 1204 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 1205 const _Tp& __val, _BinaryPredicate __binary_pred) 1206 { 1207 return __search_n_switch(__begin, __end, __count, __val, __binary_pred, 1208 typename std::iterator_traits<_FIterator>:: 1209 iterator_category()); 1210 } 1211 1212 1213 // Sequential fallback. 1214 template<typename _IIter, typename _OutputIterator, 1215 typename _UnaryOperation> 1216 inline _OutputIterator 1217 transform(_IIter __begin, _IIter __end, _OutputIterator __result, 1218 _UnaryOperation __unary_op, __gnu_parallel::sequential_tag) 1219 { return _GLIBCXX_STD_A::transform(__begin, __end, __result, __unary_op); } 1220 1221 // Parallel unary transform for random access iterators. 1222 template<typename _RAIter1, typename _RAIter2, 1223 typename _UnaryOperation> 1224 _RAIter2 1225 __transform1_switch(_RAIter1 __begin, _RAIter1 __end, 1226 _RAIter2 __result, _UnaryOperation __unary_op, 1227 random_access_iterator_tag, random_access_iterator_tag, 1228 __gnu_parallel::_Parallelism __parallelism_tag 1229 = __gnu_parallel::parallel_balanced) 1230 { 1231 if (_GLIBCXX_PARALLEL_CONDITION( 1232 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1233 >= __gnu_parallel::_Settings::get().transform_minimal_n 1234 && __gnu_parallel::__is_parallel(__parallelism_tag))) 1235 { 1236 bool __dummy = true; 1237 typedef __gnu_parallel::_IteratorPair<_RAIter1, 1238 _RAIter2, random_access_iterator_tag> _ItTrip; 1239 _ItTrip __begin_pair(__begin, __result), 1240 __end_pair(__end, __result + (__end - __begin)); 1241 __gnu_parallel::__transform1_selector<_ItTrip> __functionality; 1242 __gnu_parallel:: 1243 __for_each_template_random_access( 1244 __begin_pair, __end_pair, __unary_op, __functionality, 1245 __gnu_parallel::_DummyReduct(), 1246 __dummy, __dummy, -1, __parallelism_tag); 1247 return __functionality._M_finish_iterator; 1248 } 1249 else 1250 return transform(__begin, __end, __result, __unary_op, 1251 __gnu_parallel::sequential_tag()); 1252 } 1253 1254 // Sequential fallback for input iterator case. 1255 template<typename _RAIter1, typename _RAIter2, 1256 typename _UnaryOperation, typename _IteratorTag1, 1257 typename _IteratorTag2> 1258 inline _RAIter2 1259 __transform1_switch(_RAIter1 __begin, _RAIter1 __end, 1260 _RAIter2 __result, _UnaryOperation __unary_op, 1261 _IteratorTag1, _IteratorTag2) 1262 { return transform(__begin, __end, __result, __unary_op, 1263 __gnu_parallel::sequential_tag()); } 1264 1265 // Public interface. 1266 template<typename _IIter, typename _OutputIterator, 1267 typename _UnaryOperation> 1268 inline _OutputIterator 1269 transform(_IIter __begin, _IIter __end, _OutputIterator __result, 1270 _UnaryOperation __unary_op, 1271 __gnu_parallel::_Parallelism __parallelism_tag) 1272 { 1273 typedef std::iterator_traits<_IIter> _IIterTraits; 1274 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 1275 typedef typename _IIterTraits::iterator_category _IIteratorCategory; 1276 typedef typename _OIterTraits::iterator_category _OIterCategory; 1277 1278 return __transform1_switch(__begin, __end, __result, __unary_op, 1279 _IIteratorCategory(), _OIterCategory(), 1280 __parallelism_tag); 1281 } 1282 1283 template<typename _IIter, typename _OutputIterator, 1284 typename _UnaryOperation> 1285 inline _OutputIterator 1286 transform(_IIter __begin, _IIter __end, _OutputIterator __result, 1287 _UnaryOperation __unary_op) 1288 { 1289 typedef std::iterator_traits<_IIter> _IIterTraits; 1290 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 1291 typedef typename _IIterTraits::iterator_category _IIteratorCategory; 1292 typedef typename _OIterTraits::iterator_category _OIterCategory; 1293 1294 return __transform1_switch(__begin, __end, __result, __unary_op, 1295 _IIteratorCategory(), _OIterCategory()); 1296 } 1297 1298 1299 // Sequential fallback 1300 template<typename _IIter1, typename _IIter2, 1301 typename _OutputIterator, typename _BinaryOperation> 1302 inline _OutputIterator 1303 transform(_IIter1 __begin1, _IIter1 __end1, 1304 _IIter2 __begin2, _OutputIterator __result, 1305 _BinaryOperation __binary_op, __gnu_parallel::sequential_tag) 1306 { return _GLIBCXX_STD_A::transform(__begin1, __end1, 1307 __begin2, __result, __binary_op); } 1308 1309 // Parallel binary transform for random access iterators. 1310 template<typename _RAIter1, typename _RAIter2, 1311 typename _RAIter3, typename _BinaryOperation> 1312 _RAIter3 1313 __transform2_switch(_RAIter1 __begin1, _RAIter1 __end1, 1314 _RAIter2 __begin2, 1315 _RAIter3 __result, _BinaryOperation __binary_op, 1316 random_access_iterator_tag, random_access_iterator_tag, 1317 random_access_iterator_tag, 1318 __gnu_parallel::_Parallelism __parallelism_tag 1319 = __gnu_parallel::parallel_balanced) 1320 { 1321 if (_GLIBCXX_PARALLEL_CONDITION( 1322 (__end1 - __begin1) >= 1323 __gnu_parallel::_Settings::get().transform_minimal_n 1324 && __gnu_parallel::__is_parallel(__parallelism_tag))) 1325 { 1326 bool __dummy = true; 1327 typedef __gnu_parallel::_IteratorTriple<_RAIter1, 1328 _RAIter2, _RAIter3, 1329 random_access_iterator_tag> _ItTrip; 1330 _ItTrip __begin_triple(__begin1, __begin2, __result), 1331 __end_triple(__end1, __begin2 + (__end1 - __begin1), 1332 __result + (__end1 - __begin1)); 1333 __gnu_parallel::__transform2_selector<_ItTrip> __functionality; 1334 __gnu_parallel:: 1335 __for_each_template_random_access(__begin_triple, __end_triple, 1336 __binary_op, __functionality, 1337 __gnu_parallel::_DummyReduct(), 1338 __dummy, __dummy, -1, 1339 __parallelism_tag); 1340 return __functionality._M_finish_iterator; 1341 } 1342 else 1343 return transform(__begin1, __end1, __begin2, __result, __binary_op, 1344 __gnu_parallel::sequential_tag()); 1345 } 1346 1347 // Sequential fallback for input iterator case. 1348 template<typename _IIter1, typename _IIter2, 1349 typename _OutputIterator, typename _BinaryOperation, 1350 typename _Tag1, typename _Tag2, typename _Tag3> 1351 inline _OutputIterator 1352 __transform2_switch(_IIter1 __begin1, _IIter1 __end1, 1353 _IIter2 __begin2, _OutputIterator __result, 1354 _BinaryOperation __binary_op, _Tag1, _Tag2, _Tag3) 1355 { return transform(__begin1, __end1, __begin2, __result, __binary_op, 1356 __gnu_parallel::sequential_tag()); } 1357 1358 // Public interface. 1359 template<typename _IIter1, typename _IIter2, 1360 typename _OutputIterator, typename _BinaryOperation> 1361 inline _OutputIterator 1362 transform(_IIter1 __begin1, _IIter1 __end1, 1363 _IIter2 __begin2, _OutputIterator __result, 1364 _BinaryOperation __binary_op, 1365 __gnu_parallel::_Parallelism __parallelism_tag) 1366 { 1367 typedef std::iterator_traits<_IIter1> _IIterTraits1; 1368 typedef typename _IIterTraits1::iterator_category 1369 _IIterCategory1; 1370 typedef std::iterator_traits<_IIter2> _IIterTraits2; 1371 typedef typename _IIterTraits2::iterator_category 1372 _IIterCategory2; 1373 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 1374 typedef typename _OIterTraits::iterator_category _OIterCategory; 1375 1376 return __transform2_switch( 1377 __begin1, __end1, __begin2, __result, __binary_op, 1378 _IIterCategory1(), _IIterCategory2(), _OIterCategory(), 1379 __parallelism_tag); 1380 } 1381 1382 template<typename _IIter1, typename _IIter2, 1383 typename _OutputIterator, typename _BinaryOperation> 1384 inline _OutputIterator 1385 transform(_IIter1 __begin1, _IIter1 __end1, 1386 _IIter2 __begin2, _OutputIterator __result, 1387 _BinaryOperation __binary_op) 1388 { 1389 typedef std::iterator_traits<_IIter1> _IIterTraits1; 1390 typedef typename _IIterTraits1::iterator_category 1391 _IIterCategory1; 1392 typedef std::iterator_traits<_IIter2> _IIterTraits2; 1393 typedef typename _IIterTraits2::iterator_category 1394 _IIterCategory2; 1395 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 1396 typedef typename _OIterTraits::iterator_category _OIterCategory; 1397 1398 return __transform2_switch( 1399 __begin1, __end1, __begin2, __result, __binary_op, 1400 _IIterCategory1(), _IIterCategory2(), _OIterCategory()); 1401 } 1402 1403 // Sequential fallback 1404 template<typename _FIterator, typename _Tp> 1405 inline void 1406 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 1407 const _Tp& __new_value, __gnu_parallel::sequential_tag) 1408 { _GLIBCXX_STD_A::replace(__begin, __end, __old_value, __new_value); } 1409 1410 // Sequential fallback for input iterator case 1411 template<typename _FIterator, typename _Tp, typename _IteratorTag> 1412 inline void 1413 __replace_switch(_FIterator __begin, _FIterator __end, 1414 const _Tp& __old_value, const _Tp& __new_value, 1415 _IteratorTag) 1416 { replace(__begin, __end, __old_value, __new_value, 1417 __gnu_parallel::sequential_tag()); } 1418 1419 // Parallel replace for random access iterators 1420 template<typename _RAIter, typename _Tp> 1421 inline void 1422 __replace_switch(_RAIter __begin, _RAIter __end, 1423 const _Tp& __old_value, const _Tp& __new_value, 1424 random_access_iterator_tag, 1425 __gnu_parallel::_Parallelism __parallelism_tag 1426 = __gnu_parallel::parallel_balanced) 1427 { 1428 // XXX parallel version is where? 1429 replace(__begin, __end, __old_value, __new_value, 1430 __gnu_parallel::sequential_tag()); 1431 } 1432 1433 // Public interface 1434 template<typename _FIterator, typename _Tp> 1435 inline void 1436 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 1437 const _Tp& __new_value, 1438 __gnu_parallel::_Parallelism __parallelism_tag) 1439 { 1440 typedef iterator_traits<_FIterator> _TraitsType; 1441 typedef typename _TraitsType::iterator_category _IteratorCategory; 1442 __replace_switch(__begin, __end, __old_value, __new_value, 1443 _IteratorCategory(), 1444 __parallelism_tag); 1445 } 1446 1447 template<typename _FIterator, typename _Tp> 1448 inline void 1449 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 1450 const _Tp& __new_value) 1451 { 1452 typedef iterator_traits<_FIterator> _TraitsType; 1453 typedef typename _TraitsType::iterator_category _IteratorCategory; 1454 __replace_switch(__begin, __end, __old_value, __new_value, 1455 _IteratorCategory()); 1456 } 1457 1458 1459 // Sequential fallback 1460 template<typename _FIterator, typename _Predicate, typename _Tp> 1461 inline void 1462 replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred, 1463 const _Tp& __new_value, __gnu_parallel::sequential_tag) 1464 { _GLIBCXX_STD_A::replace_if(__begin, __end, __pred, __new_value); } 1465 1466 // Sequential fallback for input iterator case 1467 template<typename _FIterator, typename _Predicate, typename _Tp, 1468 typename _IteratorTag> 1469 inline void 1470 __replace_if_switch(_FIterator __begin, _FIterator __end, 1471 _Predicate __pred, const _Tp& __new_value, _IteratorTag) 1472 { replace_if(__begin, __end, __pred, __new_value, 1473 __gnu_parallel::sequential_tag()); } 1474 1475 // Parallel algorithm for random access iterators. 1476 template<typename _RAIter, typename _Predicate, typename _Tp> 1477 void 1478 __replace_if_switch(_RAIter __begin, _RAIter __end, 1479 _Predicate __pred, const _Tp& __new_value, 1480 random_access_iterator_tag, 1481 __gnu_parallel::_Parallelism __parallelism_tag 1482 = __gnu_parallel::parallel_balanced) 1483 { 1484 if (_GLIBCXX_PARALLEL_CONDITION( 1485 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1486 >= __gnu_parallel::_Settings::get().replace_minimal_n 1487 && __gnu_parallel::__is_parallel(__parallelism_tag))) 1488 { 1489 bool __dummy; 1490 __gnu_parallel:: 1491 __replace_if_selector<_RAIter, _Predicate, _Tp> 1492 __functionality(__new_value); 1493 __gnu_parallel:: 1494 __for_each_template_random_access( 1495 __begin, __end, __pred, __functionality, 1496 __gnu_parallel::_DummyReduct(), 1497 true, __dummy, -1, __parallelism_tag); 1498 } 1499 else 1500 replace_if(__begin, __end, __pred, __new_value, 1501 __gnu_parallel::sequential_tag()); 1502 } 1503 1504 // Public interface. 1505 template<typename _FIterator, typename _Predicate, typename _Tp> 1506 inline void 1507 replace_if(_FIterator __begin, _FIterator __end, 1508 _Predicate __pred, const _Tp& __new_value, 1509 __gnu_parallel::_Parallelism __parallelism_tag) 1510 { 1511 typedef std::iterator_traits<_FIterator> _IteratorTraits; 1512 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 1513 __replace_if_switch(__begin, __end, __pred, __new_value, 1514 _IteratorCategory(), __parallelism_tag); 1515 } 1516 1517 template<typename _FIterator, typename _Predicate, typename _Tp> 1518 inline void 1519 replace_if(_FIterator __begin, _FIterator __end, 1520 _Predicate __pred, const _Tp& __new_value) 1521 { 1522 typedef std::iterator_traits<_FIterator> _IteratorTraits; 1523 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 1524 __replace_if_switch(__begin, __end, __pred, __new_value, 1525 _IteratorCategory()); 1526 } 1527 1528 // Sequential fallback 1529 template<typename _FIterator, typename _Generator> 1530 inline void 1531 generate(_FIterator __begin, _FIterator __end, _Generator __gen, 1532 __gnu_parallel::sequential_tag) 1533 { _GLIBCXX_STD_A::generate(__begin, __end, __gen); } 1534 1535 // Sequential fallback for input iterator case. 1536 template<typename _FIterator, typename _Generator, typename _IteratorTag> 1537 inline void 1538 __generate_switch(_FIterator __begin, _FIterator __end, _Generator __gen, 1539 _IteratorTag) 1540 { generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); } 1541 1542 // Parallel algorithm for random access iterators. 1543 template<typename _RAIter, typename _Generator> 1544 void 1545 __generate_switch(_RAIter __begin, _RAIter __end, 1546 _Generator __gen, random_access_iterator_tag, 1547 __gnu_parallel::_Parallelism __parallelism_tag 1548 = __gnu_parallel::parallel_balanced) 1549 { 1550 if (_GLIBCXX_PARALLEL_CONDITION( 1551 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1552 >= __gnu_parallel::_Settings::get().generate_minimal_n 1553 && __gnu_parallel::__is_parallel(__parallelism_tag))) 1554 { 1555 bool __dummy; 1556 __gnu_parallel::__generate_selector<_RAIter> 1557 __functionality; 1558 __gnu_parallel:: 1559 __for_each_template_random_access( 1560 __begin, __end, __gen, __functionality, 1561 __gnu_parallel::_DummyReduct(), 1562 true, __dummy, -1, __parallelism_tag); 1563 } 1564 else 1565 generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); 1566 } 1567 1568 // Public interface. 1569 template<typename _FIterator, typename _Generator> 1570 inline void 1571 generate(_FIterator __begin, _FIterator __end, 1572 _Generator __gen, __gnu_parallel::_Parallelism __parallelism_tag) 1573 { 1574 typedef std::iterator_traits<_FIterator> _IteratorTraits; 1575 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 1576 __generate_switch(__begin, __end, __gen, _IteratorCategory(), 1577 __parallelism_tag); 1578 } 1579 1580 template<typename _FIterator, typename _Generator> 1581 inline void 1582 generate(_FIterator __begin, _FIterator __end, _Generator __gen) 1583 { 1584 typedef std::iterator_traits<_FIterator> _IteratorTraits; 1585 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 1586 __generate_switch(__begin, __end, __gen, _IteratorCategory()); 1587 } 1588 1589 1590 // Sequential fallback. 1591 template<typename _OutputIterator, typename _Size, typename _Generator> 1592 inline _OutputIterator 1593 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen, 1594 __gnu_parallel::sequential_tag) 1595 { return _GLIBCXX_STD_A::generate_n(__begin, __n, __gen); } 1596 1597 // Sequential fallback for input iterator case. 1598 template<typename _OutputIterator, typename _Size, typename _Generator, 1599 typename _IteratorTag> 1600 inline _OutputIterator 1601 __generate_n_switch(_OutputIterator __begin, _Size __n, _Generator __gen, 1602 _IteratorTag) 1603 { return generate_n(__begin, __n, __gen, 1604 __gnu_parallel::sequential_tag()); } 1605 1606 // Parallel algorithm for random access iterators. 1607 template<typename _RAIter, typename _Size, typename _Generator> 1608 inline _RAIter 1609 __generate_n_switch(_RAIter __begin, _Size __n, _Generator __gen, 1610 random_access_iterator_tag, 1611 __gnu_parallel::_Parallelism __parallelism_tag 1612 = __gnu_parallel::parallel_balanced) 1613 { 1614 // XXX parallel version is where? 1615 return generate_n(__begin, __n, __gen, __gnu_parallel::sequential_tag()); 1616 } 1617 1618 // Public interface. 1619 template<typename _OutputIterator, typename _Size, typename _Generator> 1620 inline _OutputIterator 1621 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen, 1622 __gnu_parallel::_Parallelism __parallelism_tag) 1623 { 1624 typedef std::iterator_traits<_OutputIterator> _IteratorTraits; 1625 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 1626 return __generate_n_switch(__begin, __n, __gen, _IteratorCategory(), 1627 __parallelism_tag); 1628 } 1629 1630 template<typename _OutputIterator, typename _Size, typename _Generator> 1631 inline _OutputIterator 1632 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen) 1633 { 1634 typedef std::iterator_traits<_OutputIterator> _IteratorTraits; 1635 typedef typename _IteratorTraits::iterator_category _IteratorCategory; 1636 return __generate_n_switch(__begin, __n, __gen, _IteratorCategory()); 1637 } 1638 1639 1640 // Sequential fallback. 1641 template<typename _RAIter> 1642 inline void 1643 random_shuffle(_RAIter __begin, _RAIter __end, 1644 __gnu_parallel::sequential_tag) 1645 { _GLIBCXX_STD_A::random_shuffle(__begin, __end); } 1646 1647 // Sequential fallback. 1648 template<typename _RAIter, typename _RandomNumberGenerator> 1649 inline void 1650 random_shuffle(_RAIter __begin, _RAIter __end, 1651 _RandomNumberGenerator& __rand, 1652 __gnu_parallel::sequential_tag) 1653 { _GLIBCXX_STD_A::random_shuffle(__begin, __end, __rand); } 1654 1655 1656 /** @brief Functor wrapper for std::rand(). */ 1657 template<typename _MustBeInt = int> 1658 struct _CRandNumber 1659 { 1660 int 1661 operator()(int __limit) 1662 { return rand() % __limit; } 1663 }; 1664 1665 // Fill in random number generator. 1666 template<typename _RAIter> 1667 inline void 1668 random_shuffle(_RAIter __begin, _RAIter __end) 1669 { 1670 _CRandNumber<> __r; 1671 // Parallelization still possible. 1672 __gnu_parallel::random_shuffle(__begin, __end, __r); 1673 } 1674 1675 // Parallel algorithm for random access iterators. 1676 template<typename _RAIter, typename _RandomNumberGenerator> 1677 void 1678 random_shuffle(_RAIter __begin, _RAIter __end, 1679 #if __cplusplus >= 201103L 1680 _RandomNumberGenerator&& __rand) 1681 #else 1682 _RandomNumberGenerator& __rand) 1683 #endif 1684 { 1685 if (__begin == __end) 1686 return; 1687 if (_GLIBCXX_PARALLEL_CONDITION( 1688 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1689 >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n)) 1690 __gnu_parallel::__parallel_random_shuffle(__begin, __end, __rand); 1691 else 1692 __gnu_parallel::__sequential_random_shuffle(__begin, __end, __rand); 1693 } 1694 1695 // Sequential fallback. 1696 template<typename _FIterator, typename _Predicate> 1697 inline _FIterator 1698 partition(_FIterator __begin, _FIterator __end, 1699 _Predicate __pred, __gnu_parallel::sequential_tag) 1700 { return _GLIBCXX_STD_A::partition(__begin, __end, __pred); } 1701 1702 // Sequential fallback for input iterator case. 1703 template<typename _FIterator, typename _Predicate, typename _IteratorTag> 1704 inline _FIterator 1705 __partition_switch(_FIterator __begin, _FIterator __end, 1706 _Predicate __pred, _IteratorTag) 1707 { return partition(__begin, __end, __pred, 1708 __gnu_parallel::sequential_tag()); } 1709 1710 // Parallel algorithm for random access iterators. 1711 template<typename _RAIter, typename _Predicate> 1712 _RAIter 1713 __partition_switch(_RAIter __begin, _RAIter __end, 1714 _Predicate __pred, random_access_iterator_tag) 1715 { 1716 if (_GLIBCXX_PARALLEL_CONDITION( 1717 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1718 >= __gnu_parallel::_Settings::get().partition_minimal_n)) 1719 { 1720 typedef typename std::iterator_traits<_RAIter>:: 1721 difference_type _DifferenceType; 1722 _DifferenceType __middle = __gnu_parallel:: 1723 __parallel_partition(__begin, __end, __pred, 1724 __gnu_parallel::__get_max_threads()); 1725 return __begin + __middle; 1726 } 1727 else 1728 return partition(__begin, __end, __pred, 1729 __gnu_parallel::sequential_tag()); 1730 } 1731 1732 // Public interface. 1733 template<typename _FIterator, typename _Predicate> 1734 inline _FIterator 1735 partition(_FIterator __begin, _FIterator __end, _Predicate __pred) 1736 { 1737 typedef iterator_traits<_FIterator> _TraitsType; 1738 typedef typename _TraitsType::iterator_category _IteratorCategory; 1739 return __partition_switch(__begin, __end, __pred, _IteratorCategory()); 1740 } 1741 1742 // sort interface 1743 1744 // Sequential fallback 1745 template<typename _RAIter> 1746 inline void 1747 sort(_RAIter __begin, _RAIter __end, 1748 __gnu_parallel::sequential_tag) 1749 { _GLIBCXX_STD_A::sort(__begin, __end); } 1750 1751 // Sequential fallback 1752 template<typename _RAIter, typename _Compare> 1753 inline void 1754 sort(_RAIter __begin, _RAIter __end, _Compare __comp, 1755 __gnu_parallel::sequential_tag) 1756 { _GLIBCXX_STD_A::sort<_RAIter, _Compare>(__begin, __end, 1757 __comp); } 1758 1759 // Public interface 1760 template<typename _RAIter, typename _Compare, 1761 typename _Parallelism> 1762 void 1763 sort(_RAIter __begin, _RAIter __end, _Compare __comp, 1764 _Parallelism __parallelism) 1765 { 1766 typedef iterator_traits<_RAIter> _TraitsType; 1767 typedef typename _TraitsType::value_type _ValueType; 1768 1769 if (__begin != __end) 1770 { 1771 if (_GLIBCXX_PARALLEL_CONDITION( 1772 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >= 1773 __gnu_parallel::_Settings::get().sort_minimal_n)) 1774 __gnu_parallel::__parallel_sort<false>( 1775 __begin, __end, __comp, __parallelism); 1776 else 1777 sort(__begin, __end, __comp, __gnu_parallel::sequential_tag()); 1778 } 1779 } 1780 1781 // Public interface, insert default comparator 1782 template<typename _RAIter> 1783 inline void 1784 sort(_RAIter __begin, _RAIter __end) 1785 { 1786 typedef iterator_traits<_RAIter> _TraitsType; 1787 typedef typename _TraitsType::value_type _ValueType; 1788 sort(__begin, __end, std::less<_ValueType>(), 1789 __gnu_parallel::default_parallel_tag()); 1790 } 1791 1792 // Public interface, insert default comparator 1793 template<typename _RAIter> 1794 inline void 1795 sort(_RAIter __begin, _RAIter __end, 1796 __gnu_parallel::default_parallel_tag __parallelism) 1797 { 1798 typedef iterator_traits<_RAIter> _TraitsType; 1799 typedef typename _TraitsType::value_type _ValueType; 1800 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1801 } 1802 1803 // Public interface, insert default comparator 1804 template<typename _RAIter> 1805 inline void 1806 sort(_RAIter __begin, _RAIter __end, 1807 __gnu_parallel::parallel_tag __parallelism) 1808 { 1809 typedef iterator_traits<_RAIter> _TraitsType; 1810 typedef typename _TraitsType::value_type _ValueType; 1811 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1812 } 1813 1814 // Public interface, insert default comparator 1815 template<typename _RAIter> 1816 inline void 1817 sort(_RAIter __begin, _RAIter __end, 1818 __gnu_parallel::multiway_mergesort_tag __parallelism) 1819 { 1820 typedef iterator_traits<_RAIter> _TraitsType; 1821 typedef typename _TraitsType::value_type _ValueType; 1822 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1823 } 1824 1825 // Public interface, insert default comparator 1826 template<typename _RAIter> 1827 inline void 1828 sort(_RAIter __begin, _RAIter __end, 1829 __gnu_parallel::multiway_mergesort_sampling_tag __parallelism) 1830 { 1831 typedef iterator_traits<_RAIter> _TraitsType; 1832 typedef typename _TraitsType::value_type _ValueType; 1833 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1834 } 1835 1836 // Public interface, insert default comparator 1837 template<typename _RAIter> 1838 inline void 1839 sort(_RAIter __begin, _RAIter __end, 1840 __gnu_parallel::multiway_mergesort_exact_tag __parallelism) 1841 { 1842 typedef iterator_traits<_RAIter> _TraitsType; 1843 typedef typename _TraitsType::value_type _ValueType; 1844 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1845 } 1846 1847 // Public interface, insert default comparator 1848 template<typename _RAIter> 1849 inline void 1850 sort(_RAIter __begin, _RAIter __end, 1851 __gnu_parallel::quicksort_tag __parallelism) 1852 { 1853 typedef iterator_traits<_RAIter> _TraitsType; 1854 typedef typename _TraitsType::value_type _ValueType; 1855 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1856 } 1857 1858 // Public interface, insert default comparator 1859 template<typename _RAIter> 1860 inline void 1861 sort(_RAIter __begin, _RAIter __end, 1862 __gnu_parallel::balanced_quicksort_tag __parallelism) 1863 { 1864 typedef iterator_traits<_RAIter> _TraitsType; 1865 typedef typename _TraitsType::value_type _ValueType; 1866 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1867 } 1868 1869 // Public interface 1870 template<typename _RAIter, typename _Compare> 1871 void 1872 sort(_RAIter __begin, _RAIter __end, _Compare __comp) 1873 { 1874 typedef iterator_traits<_RAIter> _TraitsType; 1875 typedef typename _TraitsType::value_type _ValueType; 1876 sort(__begin, __end, __comp, __gnu_parallel::default_parallel_tag()); 1877 } 1878 1879 1880 // stable_sort interface 1881 1882 1883 // Sequential fallback 1884 template<typename _RAIter> 1885 inline void 1886 stable_sort(_RAIter __begin, _RAIter __end, 1887 __gnu_parallel::sequential_tag) 1888 { _GLIBCXX_STD_A::stable_sort(__begin, __end); } 1889 1890 // Sequential fallback 1891 template<typename _RAIter, typename _Compare> 1892 inline void 1893 stable_sort(_RAIter __begin, _RAIter __end, 1894 _Compare __comp, __gnu_parallel::sequential_tag) 1895 { _GLIBCXX_STD_A::stable_sort<_RAIter, _Compare>( 1896 __begin, __end, __comp); } 1897 1898 // Public interface 1899 template<typename _RAIter, typename _Compare, 1900 typename _Parallelism> 1901 void 1902 stable_sort(_RAIter __begin, _RAIter __end, 1903 _Compare __comp, _Parallelism __parallelism) 1904 { 1905 typedef iterator_traits<_RAIter> _TraitsType; 1906 typedef typename _TraitsType::value_type _ValueType; 1907 1908 if (__begin != __end) 1909 { 1910 if (_GLIBCXX_PARALLEL_CONDITION( 1911 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >= 1912 __gnu_parallel::_Settings::get().sort_minimal_n)) 1913 __gnu_parallel::__parallel_sort<true>( 1914 __begin, __end, __comp, __parallelism); 1915 else 1916 stable_sort(__begin, __end, __comp, 1917 __gnu_parallel::sequential_tag()); 1918 } 1919 } 1920 1921 // Public interface, insert default comparator 1922 template<typename _RAIter> 1923 inline void 1924 stable_sort(_RAIter __begin, _RAIter __end) 1925 { 1926 typedef iterator_traits<_RAIter> _TraitsType; 1927 typedef typename _TraitsType::value_type _ValueType; 1928 stable_sort(__begin, __end, std::less<_ValueType>(), 1929 __gnu_parallel::default_parallel_tag()); 1930 } 1931 1932 // Public interface, insert default comparator 1933 template<typename _RAIter> 1934 inline void 1935 stable_sort(_RAIter __begin, _RAIter __end, 1936 __gnu_parallel::default_parallel_tag __parallelism) 1937 { 1938 typedef iterator_traits<_RAIter> _TraitsType; 1939 typedef typename _TraitsType::value_type _ValueType; 1940 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1941 } 1942 1943 // Public interface, insert default comparator 1944 template<typename _RAIter> 1945 inline void 1946 stable_sort(_RAIter __begin, _RAIter __end, 1947 __gnu_parallel::parallel_tag __parallelism) 1948 { 1949 typedef iterator_traits<_RAIter> _TraitsType; 1950 typedef typename _TraitsType::value_type _ValueType; 1951 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1952 } 1953 1954 // Public interface, insert default comparator 1955 template<typename _RAIter> 1956 inline void 1957 stable_sort(_RAIter __begin, _RAIter __end, 1958 __gnu_parallel::multiway_mergesort_tag __parallelism) 1959 { 1960 typedef iterator_traits<_RAIter> _TraitsType; 1961 typedef typename _TraitsType::value_type _ValueType; 1962 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1963 } 1964 1965 // Public interface, insert default comparator 1966 template<typename _RAIter> 1967 inline void 1968 stable_sort(_RAIter __begin, _RAIter __end, 1969 __gnu_parallel::quicksort_tag __parallelism) 1970 { 1971 typedef iterator_traits<_RAIter> _TraitsType; 1972 typedef typename _TraitsType::value_type _ValueType; 1973 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1974 } 1975 1976 // Public interface, insert default comparator 1977 template<typename _RAIter> 1978 inline void 1979 stable_sort(_RAIter __begin, _RAIter __end, 1980 __gnu_parallel::balanced_quicksort_tag __parallelism) 1981 { 1982 typedef iterator_traits<_RAIter> _TraitsType; 1983 typedef typename _TraitsType::value_type _ValueType; 1984 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1985 } 1986 1987 // Public interface 1988 template<typename _RAIter, typename _Compare> 1989 void 1990 stable_sort(_RAIter __begin, _RAIter __end, 1991 _Compare __comp) 1992 { 1993 typedef iterator_traits<_RAIter> _TraitsType; 1994 typedef typename _TraitsType::value_type _ValueType; 1995 stable_sort( 1996 __begin, __end, __comp, __gnu_parallel::default_parallel_tag()); 1997 } 1998 1999 // Sequential fallback 2000 template<typename _IIter1, typename _IIter2, 2001 typename _OutputIterator> 2002 inline _OutputIterator 2003 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 2004 _IIter2 __end2, _OutputIterator __result, 2005 __gnu_parallel::sequential_tag) 2006 { return _GLIBCXX_STD_A::merge( 2007 __begin1, __end1, __begin2, __end2, __result); } 2008 2009 // Sequential fallback 2010 template<typename _IIter1, typename _IIter2, 2011 typename _OutputIterator, typename _Compare> 2012 inline _OutputIterator 2013 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 2014 _IIter2 __end2, _OutputIterator __result, _Compare __comp, 2015 __gnu_parallel::sequential_tag) 2016 { return _GLIBCXX_STD_A::merge( 2017 __begin1, __end1, __begin2, __end2, __result, __comp); } 2018 2019 // Sequential fallback for input iterator case 2020 template<typename _IIter1, typename _IIter2, typename _OutputIterator, 2021 typename _Compare, typename _IteratorTag1, 2022 typename _IteratorTag2, typename _IteratorTag3> 2023 inline _OutputIterator 2024 __merge_switch(_IIter1 __begin1, _IIter1 __end1, 2025 _IIter2 __begin2, _IIter2 __end2, 2026 _OutputIterator __result, _Compare __comp, 2027 _IteratorTag1, _IteratorTag2, _IteratorTag3) 2028 { return _GLIBCXX_STD_A::merge(__begin1, __end1, __begin2, __end2, 2029 __result, __comp); } 2030 2031 // Parallel algorithm for random access iterators 2032 template<typename _IIter1, typename _IIter2, 2033 typename _OutputIterator, typename _Compare> 2034 _OutputIterator 2035 __merge_switch(_IIter1 __begin1, _IIter1 __end1, 2036 _IIter2 __begin2, _IIter2 __end2, 2037 _OutputIterator __result, _Compare __comp, 2038 random_access_iterator_tag, random_access_iterator_tag, 2039 random_access_iterator_tag) 2040 { 2041 if (_GLIBCXX_PARALLEL_CONDITION( 2042 (static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 2043 >= __gnu_parallel::_Settings::get().merge_minimal_n 2044 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) 2045 >= __gnu_parallel::_Settings::get().merge_minimal_n))) 2046 return __gnu_parallel::__parallel_merge_advance( 2047 __begin1, __end1, __begin2, __end2, __result, 2048 (__end1 - __begin1) + (__end2 - __begin2), __comp); 2049 else 2050 return __gnu_parallel::__merge_advance( 2051 __begin1, __end1, __begin2, __end2, __result, 2052 (__end1 - __begin1) + (__end2 - __begin2), __comp); 2053 } 2054 2055 // Public interface 2056 template<typename _IIter1, typename _IIter2, 2057 typename _OutputIterator, typename _Compare> 2058 inline _OutputIterator 2059 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 2060 _IIter2 __end2, _OutputIterator __result, _Compare __comp) 2061 { 2062 typedef typename iterator_traits<_IIter1>::value_type _ValueType; 2063 2064 typedef std::iterator_traits<_IIter1> _IIterTraits1; 2065 typedef std::iterator_traits<_IIter2> _IIterTraits2; 2066 typedef std::iterator_traits<_OutputIterator> _OIterTraits; 2067 typedef typename _IIterTraits1::iterator_category 2068 _IIterCategory1; 2069 typedef typename _IIterTraits2::iterator_category 2070 _IIterCategory2; 2071 typedef typename _OIterTraits::iterator_category _OIterCategory; 2072 2073 return __merge_switch( 2074 __begin1, __end1, __begin2, __end2, __result, __comp, 2075 _IIterCategory1(), _IIterCategory2(), _OIterCategory()); 2076 } 2077 2078 2079 // Public interface, insert default comparator 2080 template<typename _IIter1, typename _IIter2, 2081 typename _OutputIterator> 2082 inline _OutputIterator 2083 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 2084 _IIter2 __end2, _OutputIterator __result) 2085 { 2086 typedef std::iterator_traits<_IIter1> _Iterator1Traits; 2087 typedef std::iterator_traits<_IIter2> _Iterator2Traits; 2088 typedef typename _Iterator1Traits::value_type _ValueType1; 2089 typedef typename _Iterator2Traits::value_type _ValueType2; 2090 2091 return __gnu_parallel::merge(__begin1, __end1, __begin2, __end2, 2092 __result, __gnu_parallel::_Less<_ValueType1, _ValueType2>()); 2093 } 2094 2095 // Sequential fallback 2096 template<typename _RAIter> 2097 inline void 2098 nth_element(_RAIter __begin, _RAIter __nth, 2099 _RAIter __end, __gnu_parallel::sequential_tag) 2100 { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end); } 2101 2102 // Sequential fallback 2103 template<typename _RAIter, typename _Compare> 2104 inline void 2105 nth_element(_RAIter __begin, _RAIter __nth, 2106 _RAIter __end, _Compare __comp, 2107 __gnu_parallel::sequential_tag) 2108 { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end, __comp); } 2109 2110 // Public interface 2111 template<typename _RAIter, typename _Compare> 2112 inline void 2113 nth_element(_RAIter __begin, _RAIter __nth, 2114 _RAIter __end, _Compare __comp) 2115 { 2116 if (_GLIBCXX_PARALLEL_CONDITION( 2117 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 2118 >= __gnu_parallel::_Settings::get().nth_element_minimal_n)) 2119 __gnu_parallel::__parallel_nth_element(__begin, __nth, __end, __comp); 2120 else 2121 nth_element(__begin, __nth, __end, __comp, 2122 __gnu_parallel::sequential_tag()); 2123 } 2124 2125 // Public interface, insert default comparator 2126 template<typename _RAIter> 2127 inline void 2128 nth_element(_RAIter __begin, _RAIter __nth, 2129 _RAIter __end) 2130 { 2131 typedef iterator_traits<_RAIter> _TraitsType; 2132 typedef typename _TraitsType::value_type _ValueType; 2133 __gnu_parallel::nth_element(__begin, __nth, __end, 2134 std::less<_ValueType>()); 2135 } 2136 2137 // Sequential fallback 2138 template<typename _RAIter, typename _Compare> 2139 inline void 2140 partial_sort(_RAIter __begin, _RAIter __middle, 2141 _RAIter __end, _Compare __comp, 2142 __gnu_parallel::sequential_tag) 2143 { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end, __comp); } 2144 2145 // Sequential fallback 2146 template<typename _RAIter> 2147 inline void 2148 partial_sort(_RAIter __begin, _RAIter __middle, 2149 _RAIter __end, __gnu_parallel::sequential_tag) 2150 { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end); } 2151 2152 // Public interface, parallel algorithm for random access iterators 2153 template<typename _RAIter, typename _Compare> 2154 void 2155 partial_sort(_RAIter __begin, _RAIter __middle, 2156 _RAIter __end, _Compare __comp) 2157 { 2158 if (_GLIBCXX_PARALLEL_CONDITION( 2159 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 2160 >= __gnu_parallel::_Settings::get().partial_sort_minimal_n)) 2161 __gnu_parallel:: 2162 __parallel_partial_sort(__begin, __middle, __end, __comp); 2163 else 2164 partial_sort(__begin, __middle, __end, __comp, 2165 __gnu_parallel::sequential_tag()); 2166 } 2167 2168 // Public interface, insert default comparator 2169 template<typename _RAIter> 2170 inline void 2171 partial_sort(_RAIter __begin, _RAIter __middle, 2172 _RAIter __end) 2173 { 2174 typedef iterator_traits<_RAIter> _TraitsType; 2175 typedef typename _TraitsType::value_type _ValueType; 2176 __gnu_parallel::partial_sort(__begin, __middle, __end, 2177 std::less<_ValueType>()); 2178 } 2179 2180 // Sequential fallback 2181 template<typename _FIterator> 2182 inline _FIterator 2183 max_element(_FIterator __begin, _FIterator __end, 2184 __gnu_parallel::sequential_tag) 2185 { return _GLIBCXX_STD_A::max_element(__begin, __end); } 2186 2187 // Sequential fallback 2188 template<typename _FIterator, typename _Compare> 2189 inline _FIterator 2190 max_element(_FIterator __begin, _FIterator __end, _Compare __comp, 2191 __gnu_parallel::sequential_tag) 2192 { return _GLIBCXX_STD_A::max_element(__begin, __end, __comp); } 2193 2194 // Sequential fallback for input iterator case 2195 template<typename _FIterator, typename _Compare, typename _IteratorTag> 2196 inline _FIterator 2197 __max_element_switch(_FIterator __begin, _FIterator __end, 2198 _Compare __comp, _IteratorTag) 2199 { return max_element(__begin, __end, __comp, 2200 __gnu_parallel::sequential_tag()); } 2201 2202 // Parallel algorithm for random access iterators 2203 template<typename _RAIter, typename _Compare> 2204 _RAIter 2205 __max_element_switch(_RAIter __begin, _RAIter __end, 2206 _Compare __comp, random_access_iterator_tag, 2207 __gnu_parallel::_Parallelism __parallelism_tag 2208 = __gnu_parallel::parallel_balanced) 2209 { 2210 if (_GLIBCXX_PARALLEL_CONDITION( 2211 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 2212 >= __gnu_parallel::_Settings::get().max_element_minimal_n 2213 && __gnu_parallel::__is_parallel(__parallelism_tag))) 2214 { 2215 _RAIter __res(__begin); 2216 __gnu_parallel::__identity_selector<_RAIter> 2217 __functionality; 2218 __gnu_parallel:: 2219 __for_each_template_random_access( 2220 __begin, __end, __gnu_parallel::_Nothing(), __functionality, 2221 __gnu_parallel::__max_element_reduct<_Compare, _RAIter>(__comp), 2222 __res, __res, -1, __parallelism_tag); 2223 return __res; 2224 } 2225 else 2226 return max_element(__begin, __end, __comp, 2227 __gnu_parallel::sequential_tag()); 2228 } 2229 2230 // Public interface, insert default comparator 2231 template<typename _FIterator> 2232 inline _FIterator 2233 max_element(_FIterator __begin, _FIterator __end, 2234 __gnu_parallel::_Parallelism __parallelism_tag) 2235 { 2236 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 2237 return max_element(__begin, __end, std::less<_ValueType>(), 2238 __parallelism_tag); 2239 } 2240 2241 template<typename _FIterator> 2242 inline _FIterator 2243 max_element(_FIterator __begin, _FIterator __end) 2244 { 2245 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 2246 return __gnu_parallel::max_element(__begin, __end, 2247 std::less<_ValueType>()); 2248 } 2249 2250 // Public interface 2251 template<typename _FIterator, typename _Compare> 2252 inline _FIterator 2253 max_element(_FIterator __begin, _FIterator __end, _Compare __comp, 2254 __gnu_parallel::_Parallelism __parallelism_tag) 2255 { 2256 typedef iterator_traits<_FIterator> _TraitsType; 2257 typedef typename _TraitsType::iterator_category _IteratorCategory; 2258 return __max_element_switch(__begin, __end, __comp, _IteratorCategory(), 2259 __parallelism_tag); 2260 } 2261 2262 template<typename _FIterator, typename _Compare> 2263 inline _FIterator 2264 max_element(_FIterator __begin, _FIterator __end, _Compare __comp) 2265 { 2266 typedef iterator_traits<_FIterator> _TraitsType; 2267 typedef typename _TraitsType::iterator_category _IteratorCategory; 2268 return __max_element_switch(__begin, __end, __comp, _IteratorCategory()); 2269 } 2270 2271 2272 // Sequential fallback 2273 template<typename _FIterator> 2274 inline _FIterator 2275 min_element(_FIterator __begin, _FIterator __end, 2276 __gnu_parallel::sequential_tag) 2277 { return _GLIBCXX_STD_A::min_element(__begin, __end); } 2278 2279 // Sequential fallback 2280 template<typename _FIterator, typename _Compare> 2281 inline _FIterator 2282 min_element(_FIterator __begin, _FIterator __end, _Compare __comp, 2283 __gnu_parallel::sequential_tag) 2284 { return _GLIBCXX_STD_A::min_element(__begin, __end, __comp); } 2285 2286 // Sequential fallback for input iterator case 2287 template<typename _FIterator, typename _Compare, typename _IteratorTag> 2288 inline _FIterator 2289 __min_element_switch(_FIterator __begin, _FIterator __end, 2290 _Compare __comp, _IteratorTag) 2291 { return min_element(__begin, __end, __comp, 2292 __gnu_parallel::sequential_tag()); } 2293 2294 // Parallel algorithm for random access iterators 2295 template<typename _RAIter, typename _Compare> 2296 _RAIter 2297 __min_element_switch(_RAIter __begin, _RAIter __end, 2298 _Compare __comp, random_access_iterator_tag, 2299 __gnu_parallel::_Parallelism __parallelism_tag 2300 = __gnu_parallel::parallel_balanced) 2301 { 2302 if (_GLIBCXX_PARALLEL_CONDITION( 2303 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 2304 >= __gnu_parallel::_Settings::get().min_element_minimal_n 2305 && __gnu_parallel::__is_parallel(__parallelism_tag))) 2306 { 2307 _RAIter __res(__begin); 2308 __gnu_parallel::__identity_selector<_RAIter> 2309 __functionality; 2310 __gnu_parallel:: 2311 __for_each_template_random_access( 2312 __begin, __end, __gnu_parallel::_Nothing(), __functionality, 2313 __gnu_parallel::__min_element_reduct<_Compare, _RAIter>(__comp), 2314 __res, __res, -1, __parallelism_tag); 2315 return __res; 2316 } 2317 else 2318 return min_element(__begin, __end, __comp, 2319 __gnu_parallel::sequential_tag()); 2320 } 2321 2322 // Public interface, insert default comparator 2323 template<typename _FIterator> 2324 inline _FIterator 2325 min_element(_FIterator __begin, _FIterator __end, 2326 __gnu_parallel::_Parallelism __parallelism_tag) 2327 { 2328 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 2329 return min_element(__begin, __end, std::less<_ValueType>(), 2330 __parallelism_tag); 2331 } 2332 2333 template<typename _FIterator> 2334 inline _FIterator 2335 min_element(_FIterator __begin, _FIterator __end) 2336 { 2337 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 2338 return __gnu_parallel::min_element(__begin, __end, 2339 std::less<_ValueType>()); 2340 } 2341 2342 // Public interface 2343 template<typename _FIterator, typename _Compare> 2344 inline _FIterator 2345 min_element(_FIterator __begin, _FIterator __end, _Compare __comp, 2346 __gnu_parallel::_Parallelism __parallelism_tag) 2347 { 2348 typedef iterator_traits<_FIterator> _TraitsType; 2349 typedef typename _TraitsType::iterator_category _IteratorCategory; 2350 return __min_element_switch(__begin, __end, __comp, _IteratorCategory(), 2351 __parallelism_tag); 2352 } 2353 2354 template<typename _FIterator, typename _Compare> 2355 inline _FIterator 2356 min_element(_FIterator __begin, _FIterator __end, _Compare __comp) 2357 { 2358 typedef iterator_traits<_FIterator> _TraitsType; 2359 typedef typename _TraitsType::iterator_category _IteratorCategory; 2360 return __min_element_switch(__begin, __end, __comp, _IteratorCategory()); 2361 } 2362 } // end namespace 2363 } // end namespace 2364 2365 #endif /* _GLIBCXX_PARALLEL_ALGO_H */ 2366
