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