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