Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/parallel/algo.h
1 // -*- C++ -*- 2 3 // Copyright (C) 2007-2025 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 #if __cplusplus >= 201703L 1000 /** @brief Search a sequence using a Searcher object. 1001 * 1002 * @param __first A forward iterator. 1003 * @param __last A forward iterator. 1004 * @param __searcher A callable object. 1005 * @return @p __searcher(__first,__last).first 1006 */ 1007 template<typename _ForwardIterator, typename _Searcher> 1008 inline _ForwardIterator 1009 search(_ForwardIterator __first, _ForwardIterator __last, 1010 const _Searcher& __searcher) 1011 { return __searcher(__first, __last).first; } 1012 #endif 1013 1014 // Sequential fallback 1015 template<typename _FIterator, typename _Integer, typename _Tp> 1016 inline _FIterator 1017 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 1018 const _Tp& __val, __gnu_parallel::sequential_tag) 1019 { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val); } 1020 1021 // Sequential fallback 1022 template<typename _FIterator, typename _Integer, typename _Tp, 1023 typename _BinaryPredicate> 1024 inline _FIterator 1025 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 1026 const _Tp& __val, _BinaryPredicate __binary_pred, 1027 __gnu_parallel::sequential_tag) 1028 { return _GLIBCXX_STD_A::search_n( 1029 __begin, __end, __count, __val, __binary_pred); } 1030 1031 // Public interface. 1032 template<typename _FIterator, typename _Integer, typename _Tp> 1033 inline _FIterator 1034 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 1035 const _Tp& __val) 1036 { 1037 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 1038 return __gnu_parallel::search_n(__begin, __end, __count, __val, 1039 __gnu_parallel::_EqualTo<_ValueType, _Tp>()); 1040 } 1041 1042 // Parallel algorithm for random access iterators. 1043 template<typename _RAIter, typename _Integer, 1044 typename _Tp, typename _BinaryPredicate> 1045 _RAIter 1046 __search_n_switch(_RAIter __begin, _RAIter __end, _Integer __count, 1047 const _Tp& __val, _BinaryPredicate __binary_pred, 1048 random_access_iterator_tag) 1049 { 1050 if (_GLIBCXX_PARALLEL_CONDITION( 1051 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1052 >= __gnu_parallel::_Settings::get().search_minimal_n)) 1053 { 1054 __gnu_parallel::_PseudoSequence<_Tp, _Integer> __ps(__val, __count); 1055 return __gnu_parallel::__search_template( 1056 __begin, __end, __ps.begin(), __ps.end(), __binary_pred); 1057 } 1058 else 1059 return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val, 1060 __binary_pred); 1061 } 1062 1063 // Sequential fallback for input iterator case. 1064 template<typename _FIterator, typename _Integer, typename _Tp, 1065 typename _BinaryPredicate, typename _IteratorTag> 1066 inline _FIterator 1067 __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count, 1068 const _Tp& __val, _BinaryPredicate __binary_pred, 1069 _IteratorTag) 1070 { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val, 1071 __binary_pred); } 1072 1073 // Public interface. 1074 template<typename _FIterator, typename _Integer, typename _Tp, 1075 typename _BinaryPredicate> 1076 inline _FIterator 1077 search_n(_FIterator __begin, _FIterator __end, _Integer __count, 1078 const _Tp& __val, _BinaryPredicate __binary_pred) 1079 { 1080 return __search_n_switch(__begin, __end, __count, __val, __binary_pred, 1081 std::__iterator_category(__begin)); 1082 } 1083 1084 1085 // Sequential fallback. 1086 template<typename _IIter, typename _OutputIterator, 1087 typename _UnaryOperation> 1088 inline _OutputIterator 1089 transform(_IIter __begin, _IIter __end, _OutputIterator __result, 1090 _UnaryOperation __unary_op, __gnu_parallel::sequential_tag) 1091 { return _GLIBCXX_STD_A::transform(__begin, __end, __result, __unary_op); } 1092 1093 // Parallel unary transform for random access iterators. 1094 template<typename _RAIter1, typename _RAIter2, 1095 typename _UnaryOperation> 1096 _RAIter2 1097 __transform1_switch(_RAIter1 __begin, _RAIter1 __end, 1098 _RAIter2 __result, _UnaryOperation __unary_op, 1099 random_access_iterator_tag, random_access_iterator_tag, 1100 __gnu_parallel::_Parallelism __parallelism_tag) 1101 { 1102 if (_GLIBCXX_PARALLEL_CONDITION( 1103 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1104 >= __gnu_parallel::_Settings::get().transform_minimal_n 1105 && __gnu_parallel::__is_parallel(__parallelism_tag))) 1106 { 1107 bool __dummy = true; 1108 typedef __gnu_parallel::_IteratorPair<_RAIter1, 1109 _RAIter2, random_access_iterator_tag> _ItTrip; 1110 _ItTrip __begin_pair(__begin, __result), 1111 __end_pair(__end, __result + (__end - __begin)); 1112 __gnu_parallel::__transform1_selector<_ItTrip> __functionality; 1113 __gnu_parallel:: 1114 __for_each_template_random_access( 1115 __begin_pair, __end_pair, __unary_op, __functionality, 1116 __gnu_parallel::_DummyReduct(), 1117 __dummy, __dummy, -1, __parallelism_tag); 1118 return __functionality._M_finish_iterator; 1119 } 1120 else 1121 return transform(__begin, __end, __result, __unary_op, 1122 __gnu_parallel::sequential_tag()); 1123 } 1124 1125 // Sequential fallback for input iterator case. 1126 template<typename _RAIter1, typename _RAIter2, 1127 typename _UnaryOperation, typename _IteratorTag1, 1128 typename _IteratorTag2> 1129 inline _RAIter2 1130 __transform1_switch(_RAIter1 __begin, _RAIter1 __end, 1131 _RAIter2 __result, _UnaryOperation __unary_op, 1132 _IteratorTag1, _IteratorTag2) 1133 { return transform(__begin, __end, __result, __unary_op, 1134 __gnu_parallel::sequential_tag()); } 1135 1136 // Public interface. 1137 template<typename _IIter, typename _OutputIterator, 1138 typename _UnaryOperation> 1139 inline _OutputIterator 1140 transform(_IIter __begin, _IIter __end, _OutputIterator __result, 1141 _UnaryOperation __unary_op, 1142 __gnu_parallel::_Parallelism __parallelism_tag) 1143 { 1144 return __transform1_switch(__begin, __end, __result, __unary_op, 1145 std::__iterator_category(__begin), 1146 std::__iterator_category(__result), 1147 __parallelism_tag); 1148 } 1149 1150 template<typename _IIter, typename _OutputIterator, 1151 typename _UnaryOperation> 1152 inline _OutputIterator 1153 transform(_IIter __begin, _IIter __end, _OutputIterator __result, 1154 _UnaryOperation __unary_op) 1155 { 1156 return __transform1_switch(__begin, __end, __result, __unary_op, 1157 std::__iterator_category(__begin), 1158 std::__iterator_category(__result)); 1159 } 1160 1161 1162 // Sequential fallback 1163 template<typename _IIter1, typename _IIter2, 1164 typename _OutputIterator, typename _BinaryOperation> 1165 inline _OutputIterator 1166 transform(_IIter1 __begin1, _IIter1 __end1, 1167 _IIter2 __begin2, _OutputIterator __result, 1168 _BinaryOperation __binary_op, __gnu_parallel::sequential_tag) 1169 { return _GLIBCXX_STD_A::transform(__begin1, __end1, 1170 __begin2, __result, __binary_op); } 1171 1172 // Parallel binary transform for random access iterators. 1173 template<typename _RAIter1, typename _RAIter2, 1174 typename _RAIter3, typename _BinaryOperation> 1175 _RAIter3 1176 __transform2_switch(_RAIter1 __begin1, _RAIter1 __end1, 1177 _RAIter2 __begin2, 1178 _RAIter3 __result, _BinaryOperation __binary_op, 1179 random_access_iterator_tag, random_access_iterator_tag, 1180 random_access_iterator_tag, 1181 __gnu_parallel::_Parallelism __parallelism_tag) 1182 { 1183 if (_GLIBCXX_PARALLEL_CONDITION( 1184 (__end1 - __begin1) >= 1185 __gnu_parallel::_Settings::get().transform_minimal_n 1186 && __gnu_parallel::__is_parallel(__parallelism_tag))) 1187 { 1188 bool __dummy = true; 1189 typedef __gnu_parallel::_IteratorTriple<_RAIter1, 1190 _RAIter2, _RAIter3, 1191 random_access_iterator_tag> _ItTrip; 1192 _ItTrip __begin_triple(__begin1, __begin2, __result), 1193 __end_triple(__end1, __begin2 + (__end1 - __begin1), 1194 __result + (__end1 - __begin1)); 1195 __gnu_parallel::__transform2_selector<_ItTrip> __functionality; 1196 __gnu_parallel:: 1197 __for_each_template_random_access(__begin_triple, __end_triple, 1198 __binary_op, __functionality, 1199 __gnu_parallel::_DummyReduct(), 1200 __dummy, __dummy, -1, 1201 __parallelism_tag); 1202 return __functionality._M_finish_iterator; 1203 } 1204 else 1205 return transform(__begin1, __end1, __begin2, __result, __binary_op, 1206 __gnu_parallel::sequential_tag()); 1207 } 1208 1209 // Sequential fallback for input iterator case. 1210 template<typename _IIter1, typename _IIter2, 1211 typename _OutputIterator, typename _BinaryOperation, 1212 typename _Tag1, typename _Tag2, typename _Tag3> 1213 inline _OutputIterator 1214 __transform2_switch(_IIter1 __begin1, _IIter1 __end1, 1215 _IIter2 __begin2, _OutputIterator __result, 1216 _BinaryOperation __binary_op, _Tag1, _Tag2, _Tag3) 1217 { return transform(__begin1, __end1, __begin2, __result, __binary_op, 1218 __gnu_parallel::sequential_tag()); } 1219 1220 // Public interface. 1221 template<typename _IIter1, typename _IIter2, 1222 typename _OutputIterator, typename _BinaryOperation> 1223 inline _OutputIterator 1224 transform(_IIter1 __begin1, _IIter1 __end1, 1225 _IIter2 __begin2, _OutputIterator __result, 1226 _BinaryOperation __binary_op, 1227 __gnu_parallel::_Parallelism __parallelism_tag) 1228 { 1229 return __transform2_switch( 1230 __begin1, __end1, __begin2, __result, __binary_op, 1231 std::__iterator_category(__begin1), 1232 std::__iterator_category(__begin2), 1233 std::__iterator_category(__result), 1234 __parallelism_tag); 1235 } 1236 1237 template<typename _IIter1, typename _IIter2, 1238 typename _OutputIterator, typename _BinaryOperation> 1239 inline _OutputIterator 1240 transform(_IIter1 __begin1, _IIter1 __end1, 1241 _IIter2 __begin2, _OutputIterator __result, 1242 _BinaryOperation __binary_op) 1243 { 1244 return __transform2_switch( 1245 __begin1, __end1, __begin2, __result, __binary_op, 1246 std::__iterator_category(__begin1), 1247 std::__iterator_category(__begin2), 1248 std::__iterator_category(__result)); 1249 } 1250 1251 // Sequential fallback 1252 template<typename _FIterator, typename _Tp> 1253 inline void 1254 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 1255 const _Tp& __new_value, __gnu_parallel::sequential_tag) 1256 { _GLIBCXX_STD_A::replace(__begin, __end, __old_value, __new_value); } 1257 1258 // Sequential fallback for input iterator case 1259 template<typename _FIterator, typename _Tp, typename _IteratorTag> 1260 inline void 1261 __replace_switch(_FIterator __begin, _FIterator __end, 1262 const _Tp& __old_value, const _Tp& __new_value, 1263 _IteratorTag) 1264 { replace(__begin, __end, __old_value, __new_value, 1265 __gnu_parallel::sequential_tag()); } 1266 1267 // Parallel replace for random access iterators 1268 template<typename _RAIter, typename _Tp> 1269 inline void 1270 __replace_switch(_RAIter __begin, _RAIter __end, 1271 const _Tp& __old_value, const _Tp& __new_value, 1272 random_access_iterator_tag, 1273 __gnu_parallel::_Parallelism __parallelism_tag) 1274 { 1275 // XXX parallel version is where? 1276 replace(__begin, __end, __old_value, __new_value, 1277 __gnu_parallel::sequential_tag()); 1278 } 1279 1280 // Public interface 1281 template<typename _FIterator, typename _Tp> 1282 inline void 1283 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 1284 const _Tp& __new_value, 1285 __gnu_parallel::_Parallelism __parallelism_tag) 1286 { 1287 __replace_switch(__begin, __end, __old_value, __new_value, 1288 std::__iterator_category(__begin), 1289 __parallelism_tag); 1290 } 1291 1292 template<typename _FIterator, typename _Tp> 1293 inline void 1294 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 1295 const _Tp& __new_value) 1296 { 1297 __replace_switch(__begin, __end, __old_value, __new_value, 1298 std::__iterator_category(__begin)); 1299 } 1300 1301 1302 // Sequential fallback 1303 template<typename _FIterator, typename _Predicate, typename _Tp> 1304 inline void 1305 replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred, 1306 const _Tp& __new_value, __gnu_parallel::sequential_tag) 1307 { _GLIBCXX_STD_A::replace_if(__begin, __end, __pred, __new_value); } 1308 1309 // Sequential fallback for input iterator case 1310 template<typename _FIterator, typename _Predicate, typename _Tp, 1311 typename _IteratorTag> 1312 inline void 1313 __replace_if_switch(_FIterator __begin, _FIterator __end, 1314 _Predicate __pred, const _Tp& __new_value, _IteratorTag) 1315 { replace_if(__begin, __end, __pred, __new_value, 1316 __gnu_parallel::sequential_tag()); } 1317 1318 // Parallel algorithm for random access iterators. 1319 template<typename _RAIter, typename _Predicate, typename _Tp> 1320 void 1321 __replace_if_switch(_RAIter __begin, _RAIter __end, 1322 _Predicate __pred, const _Tp& __new_value, 1323 random_access_iterator_tag, 1324 __gnu_parallel::_Parallelism __parallelism_tag) 1325 { 1326 if (_GLIBCXX_PARALLEL_CONDITION( 1327 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1328 >= __gnu_parallel::_Settings::get().replace_minimal_n 1329 && __gnu_parallel::__is_parallel(__parallelism_tag))) 1330 { 1331 bool __dummy; 1332 __gnu_parallel:: 1333 __replace_if_selector<_RAIter, _Predicate, _Tp> 1334 __functionality(__new_value); 1335 __gnu_parallel:: 1336 __for_each_template_random_access( 1337 __begin, __end, __pred, __functionality, 1338 __gnu_parallel::_DummyReduct(), 1339 true, __dummy, -1, __parallelism_tag); 1340 } 1341 else 1342 replace_if(__begin, __end, __pred, __new_value, 1343 __gnu_parallel::sequential_tag()); 1344 } 1345 1346 // Public interface. 1347 template<typename _FIterator, typename _Predicate, typename _Tp> 1348 inline void 1349 replace_if(_FIterator __begin, _FIterator __end, 1350 _Predicate __pred, const _Tp& __new_value, 1351 __gnu_parallel::_Parallelism __parallelism_tag) 1352 { 1353 __replace_if_switch(__begin, __end, __pred, __new_value, 1354 std::__iterator_category(__begin), 1355 __parallelism_tag); 1356 } 1357 1358 template<typename _FIterator, typename _Predicate, typename _Tp> 1359 inline void 1360 replace_if(_FIterator __begin, _FIterator __end, 1361 _Predicate __pred, const _Tp& __new_value) 1362 { 1363 __replace_if_switch(__begin, __end, __pred, __new_value, 1364 std::__iterator_category(__begin)); 1365 } 1366 1367 // Sequential fallback 1368 template<typename _FIterator, typename _Generator> 1369 inline void 1370 generate(_FIterator __begin, _FIterator __end, _Generator __gen, 1371 __gnu_parallel::sequential_tag) 1372 { _GLIBCXX_STD_A::generate(__begin, __end, __gen); } 1373 1374 // Sequential fallback for input iterator case. 1375 template<typename _FIterator, typename _Generator, typename _IteratorTag> 1376 inline void 1377 __generate_switch(_FIterator __begin, _FIterator __end, _Generator __gen, 1378 _IteratorTag) 1379 { generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); } 1380 1381 // Parallel algorithm for random access iterators. 1382 template<typename _RAIter, typename _Generator> 1383 void 1384 __generate_switch(_RAIter __begin, _RAIter __end, 1385 _Generator __gen, random_access_iterator_tag, 1386 __gnu_parallel::_Parallelism __parallelism_tag) 1387 { 1388 if (_GLIBCXX_PARALLEL_CONDITION( 1389 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1390 >= __gnu_parallel::_Settings::get().generate_minimal_n 1391 && __gnu_parallel::__is_parallel(__parallelism_tag))) 1392 { 1393 bool __dummy; 1394 __gnu_parallel::__generate_selector<_RAIter> 1395 __functionality; 1396 __gnu_parallel:: 1397 __for_each_template_random_access( 1398 __begin, __end, __gen, __functionality, 1399 __gnu_parallel::_DummyReduct(), 1400 true, __dummy, -1, __parallelism_tag); 1401 } 1402 else 1403 generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); 1404 } 1405 1406 // Public interface. 1407 template<typename _FIterator, typename _Generator> 1408 inline void 1409 generate(_FIterator __begin, _FIterator __end, 1410 _Generator __gen, __gnu_parallel::_Parallelism __parallelism_tag) 1411 { 1412 __generate_switch(__begin, __end, __gen, 1413 std::__iterator_category(__begin), 1414 __parallelism_tag); 1415 } 1416 1417 template<typename _FIterator, typename _Generator> 1418 inline void 1419 generate(_FIterator __begin, _FIterator __end, _Generator __gen) 1420 { 1421 __generate_switch(__begin, __end, __gen, 1422 std::__iterator_category(__begin)); 1423 } 1424 1425 1426 // Sequential fallback. 1427 template<typename _OutputIterator, typename _Size, typename _Generator> 1428 inline _OutputIterator 1429 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen, 1430 __gnu_parallel::sequential_tag) 1431 { return _GLIBCXX_STD_A::generate_n(__begin, __n, __gen); } 1432 1433 // Sequential fallback for input iterator case. 1434 template<typename _OutputIterator, typename _Size, typename _Generator, 1435 typename _IteratorTag> 1436 inline _OutputIterator 1437 __generate_n_switch(_OutputIterator __begin, _Size __n, _Generator __gen, 1438 _IteratorTag) 1439 { return generate_n(__begin, __n, __gen, 1440 __gnu_parallel::sequential_tag()); } 1441 1442 // Parallel algorithm for random access iterators. 1443 template<typename _RAIter, typename _Size, typename _Generator> 1444 inline _RAIter 1445 __generate_n_switch(_RAIter __begin, _Size __n, _Generator __gen, 1446 random_access_iterator_tag, 1447 __gnu_parallel::_Parallelism __parallelism_tag) 1448 { 1449 // XXX parallel version is where? 1450 return generate_n(__begin, __n, __gen, __gnu_parallel::sequential_tag()); 1451 } 1452 1453 // Public interface. 1454 template<typename _OutputIterator, typename _Size, typename _Generator> 1455 inline _OutputIterator 1456 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen, 1457 __gnu_parallel::_Parallelism __parallelism_tag) 1458 { 1459 return __generate_n_switch(__begin, __n, __gen, 1460 std::__iterator_category(__begin), 1461 __parallelism_tag); 1462 } 1463 1464 template<typename _OutputIterator, typename _Size, typename _Generator> 1465 inline _OutputIterator 1466 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen) 1467 { 1468 return __generate_n_switch(__begin, __n, __gen, 1469 std::__iterator_category(__begin)); 1470 } 1471 1472 1473 // Sequential fallback. 1474 template<typename _RAIter> 1475 inline void 1476 random_shuffle(_RAIter __begin, _RAIter __end, 1477 __gnu_parallel::sequential_tag) 1478 { _GLIBCXX_STD_A::random_shuffle(__begin, __end); } 1479 1480 // Sequential fallback. 1481 template<typename _RAIter, typename _RandomNumberGenerator> 1482 inline void 1483 random_shuffle(_RAIter __begin, _RAIter __end, 1484 _RandomNumberGenerator& __rand, 1485 __gnu_parallel::sequential_tag) 1486 { _GLIBCXX_STD_A::random_shuffle(__begin, __end, __rand); } 1487 1488 1489 /** @brief Functor wrapper for std::rand(). */ 1490 template<typename _MustBeInt = int> 1491 struct _CRandNumber 1492 { 1493 int 1494 operator()(int __limit) 1495 { return rand() % __limit; } 1496 }; 1497 1498 // Fill in random number generator. 1499 template<typename _RAIter> 1500 inline void 1501 random_shuffle(_RAIter __begin, _RAIter __end) 1502 { 1503 _CRandNumber<> __r; 1504 // Parallelization still possible. 1505 __gnu_parallel::random_shuffle(__begin, __end, __r); 1506 } 1507 1508 // Parallel algorithm for random access iterators. 1509 template<typename _RAIter, typename _RandomNumberGenerator> 1510 void 1511 random_shuffle(_RAIter __begin, _RAIter __end, 1512 #if __cplusplus >= 201103L 1513 _RandomNumberGenerator&& __rand) 1514 #else 1515 _RandomNumberGenerator& __rand) 1516 #endif 1517 { 1518 if (__begin == __end) 1519 return; 1520 if (_GLIBCXX_PARALLEL_CONDITION( 1521 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1522 >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n)) 1523 __gnu_parallel::__parallel_random_shuffle(__begin, __end, __rand); 1524 else 1525 __gnu_parallel::__sequential_random_shuffle(__begin, __end, __rand); 1526 } 1527 1528 // Sequential fallback. 1529 template<typename _FIterator, typename _Predicate> 1530 inline _FIterator 1531 partition(_FIterator __begin, _FIterator __end, 1532 _Predicate __pred, __gnu_parallel::sequential_tag) 1533 { return _GLIBCXX_STD_A::partition(__begin, __end, __pred); } 1534 1535 // Sequential fallback for input iterator case. 1536 template<typename _FIterator, typename _Predicate, typename _IteratorTag> 1537 inline _FIterator 1538 __partition_switch(_FIterator __begin, _FIterator __end, 1539 _Predicate __pred, _IteratorTag) 1540 { return partition(__begin, __end, __pred, 1541 __gnu_parallel::sequential_tag()); } 1542 1543 // Parallel algorithm for random access iterators. 1544 template<typename _RAIter, typename _Predicate> 1545 _RAIter 1546 __partition_switch(_RAIter __begin, _RAIter __end, 1547 _Predicate __pred, random_access_iterator_tag) 1548 { 1549 if (_GLIBCXX_PARALLEL_CONDITION( 1550 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1551 >= __gnu_parallel::_Settings::get().partition_minimal_n)) 1552 { 1553 typedef typename std::iterator_traits<_RAIter>:: 1554 difference_type _DifferenceType; 1555 _DifferenceType __middle = __gnu_parallel:: 1556 __parallel_partition(__begin, __end, __pred, 1557 __gnu_parallel::__get_max_threads()); 1558 return __begin + __middle; 1559 } 1560 else 1561 return partition(__begin, __end, __pred, 1562 __gnu_parallel::sequential_tag()); 1563 } 1564 1565 // Public interface. 1566 template<typename _FIterator, typename _Predicate> 1567 inline _FIterator 1568 partition(_FIterator __begin, _FIterator __end, _Predicate __pred) 1569 { 1570 return __partition_switch(__begin, __end, __pred, 1571 std::__iterator_category(__begin)); 1572 } 1573 1574 // sort interface 1575 1576 // Sequential fallback 1577 template<typename _RAIter> 1578 inline void 1579 sort(_RAIter __begin, _RAIter __end, 1580 __gnu_parallel::sequential_tag) 1581 { _GLIBCXX_STD_A::sort(__begin, __end); } 1582 1583 // Sequential fallback 1584 template<typename _RAIter, typename _Compare> 1585 inline void 1586 sort(_RAIter __begin, _RAIter __end, _Compare __comp, 1587 __gnu_parallel::sequential_tag) 1588 { _GLIBCXX_STD_A::sort<_RAIter, _Compare>(__begin, __end, 1589 __comp); } 1590 1591 // Public interface 1592 template<typename _RAIter, typename _Compare, 1593 typename _Parallelism> 1594 void 1595 sort(_RAIter __begin, _RAIter __end, _Compare __comp, 1596 _Parallelism __parallelism) 1597 { 1598 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1599 1600 if (__begin != __end) 1601 { 1602 if (_GLIBCXX_PARALLEL_CONDITION( 1603 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >= 1604 __gnu_parallel::_Settings::get().sort_minimal_n)) 1605 __gnu_parallel::__parallel_sort<false>( 1606 __begin, __end, __comp, __parallelism); 1607 else 1608 sort(__begin, __end, __comp, __gnu_parallel::sequential_tag()); 1609 } 1610 } 1611 1612 // Public interface, insert default comparator 1613 template<typename _RAIter> 1614 inline void 1615 sort(_RAIter __begin, _RAIter __end) 1616 { 1617 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1618 sort(__begin, __end, std::less<_ValueType>(), 1619 __gnu_parallel::default_parallel_tag()); 1620 } 1621 1622 // Public interface, insert default comparator 1623 template<typename _RAIter> 1624 inline void 1625 sort(_RAIter __begin, _RAIter __end, 1626 __gnu_parallel::default_parallel_tag __parallelism) 1627 { 1628 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1629 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1630 } 1631 1632 // Public interface, insert default comparator 1633 template<typename _RAIter> 1634 inline void 1635 sort(_RAIter __begin, _RAIter __end, 1636 __gnu_parallel::parallel_tag __parallelism) 1637 { 1638 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1639 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1640 } 1641 1642 // Public interface, insert default comparator 1643 template<typename _RAIter> 1644 inline void 1645 sort(_RAIter __begin, _RAIter __end, 1646 __gnu_parallel::multiway_mergesort_tag __parallelism) 1647 { 1648 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1649 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1650 } 1651 1652 // Public interface, insert default comparator 1653 template<typename _RAIter> 1654 inline void 1655 sort(_RAIter __begin, _RAIter __end, 1656 __gnu_parallel::multiway_mergesort_sampling_tag __parallelism) 1657 { 1658 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1659 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1660 } 1661 1662 // Public interface, insert default comparator 1663 template<typename _RAIter> 1664 inline void 1665 sort(_RAIter __begin, _RAIter __end, 1666 __gnu_parallel::multiway_mergesort_exact_tag __parallelism) 1667 { 1668 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1669 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1670 } 1671 1672 // Public interface, insert default comparator 1673 template<typename _RAIter> 1674 inline void 1675 sort(_RAIter __begin, _RAIter __end, 1676 __gnu_parallel::quicksort_tag __parallelism) 1677 { 1678 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1679 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1680 } 1681 1682 // Public interface, insert default comparator 1683 template<typename _RAIter> 1684 inline void 1685 sort(_RAIter __begin, _RAIter __end, 1686 __gnu_parallel::balanced_quicksort_tag __parallelism) 1687 { 1688 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1689 sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1690 } 1691 1692 // Public interface 1693 template<typename _RAIter, typename _Compare> 1694 void 1695 sort(_RAIter __begin, _RAIter __end, _Compare __comp) 1696 { 1697 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1698 sort(__begin, __end, __comp, __gnu_parallel::default_parallel_tag()); 1699 } 1700 1701 // stable_sort interface 1702 1703 1704 // Sequential fallback 1705 template<typename _RAIter> 1706 inline void 1707 stable_sort(_RAIter __begin, _RAIter __end, 1708 __gnu_parallel::sequential_tag) 1709 { _GLIBCXX_STD_A::stable_sort(__begin, __end); } 1710 1711 // Sequential fallback 1712 template<typename _RAIter, typename _Compare> 1713 inline void 1714 stable_sort(_RAIter __begin, _RAIter __end, 1715 _Compare __comp, __gnu_parallel::sequential_tag) 1716 { _GLIBCXX_STD_A::stable_sort<_RAIter, _Compare>(__begin, __end, __comp); } 1717 1718 // Public interface 1719 template<typename _RAIter, typename _Compare, 1720 typename _Parallelism> 1721 void 1722 stable_sort(_RAIter __begin, _RAIter __end, 1723 _Compare __comp, _Parallelism __parallelism) 1724 { 1725 typedef iterator_traits<_RAIter> _TraitsType; 1726 typedef typename _TraitsType::value_type _ValueType; 1727 1728 if (__begin != __end) 1729 { 1730 if (_GLIBCXX_PARALLEL_CONDITION( 1731 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >= 1732 __gnu_parallel::_Settings::get().sort_minimal_n)) 1733 __gnu_parallel::__parallel_sort<true>(__begin, __end, 1734 __comp, __parallelism); 1735 else 1736 stable_sort(__begin, __end, __comp, 1737 __gnu_parallel::sequential_tag()); 1738 } 1739 } 1740 1741 // Public interface, insert default comparator 1742 template<typename _RAIter> 1743 inline void 1744 stable_sort(_RAIter __begin, _RAIter __end) 1745 { 1746 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1747 stable_sort(__begin, __end, std::less<_ValueType>(), 1748 __gnu_parallel::default_parallel_tag()); 1749 } 1750 1751 // Public interface, insert default comparator 1752 template<typename _RAIter> 1753 inline void 1754 stable_sort(_RAIter __begin, _RAIter __end, 1755 __gnu_parallel::default_parallel_tag __parallelism) 1756 { 1757 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1758 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1759 } 1760 1761 // Public interface, insert default comparator 1762 template<typename _RAIter> 1763 inline void 1764 stable_sort(_RAIter __begin, _RAIter __end, 1765 __gnu_parallel::parallel_tag __parallelism) 1766 { 1767 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1768 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1769 } 1770 1771 // Public interface, insert default comparator 1772 template<typename _RAIter> 1773 inline void 1774 stable_sort(_RAIter __begin, _RAIter __end, 1775 __gnu_parallel::multiway_mergesort_tag __parallelism) 1776 { 1777 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1778 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1779 } 1780 1781 // Public interface, insert default comparator 1782 template<typename _RAIter> 1783 inline void 1784 stable_sort(_RAIter __begin, _RAIter __end, 1785 __gnu_parallel::quicksort_tag __parallelism) 1786 { 1787 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1788 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1789 } 1790 1791 // Public interface, insert default comparator 1792 template<typename _RAIter> 1793 inline void 1794 stable_sort(_RAIter __begin, _RAIter __end, 1795 __gnu_parallel::balanced_quicksort_tag __parallelism) 1796 { 1797 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1798 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); 1799 } 1800 1801 // Public interface 1802 template<typename _RAIter, typename _Compare> 1803 void 1804 stable_sort(_RAIter __begin, _RAIter __end, _Compare __comp) 1805 { 1806 stable_sort( 1807 __begin, __end, __comp, __gnu_parallel::default_parallel_tag()); 1808 } 1809 1810 // Sequential fallback 1811 template<typename _IIter1, typename _IIter2, 1812 typename _OutputIterator> 1813 inline _OutputIterator 1814 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 1815 _IIter2 __end2, _OutputIterator __result, 1816 __gnu_parallel::sequential_tag) 1817 { return _GLIBCXX_STD_A::merge( 1818 __begin1, __end1, __begin2, __end2, __result); } 1819 1820 // Sequential fallback 1821 template<typename _IIter1, typename _IIter2, 1822 typename _OutputIterator, typename _Compare> 1823 inline _OutputIterator 1824 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 1825 _IIter2 __end2, _OutputIterator __result, _Compare __comp, 1826 __gnu_parallel::sequential_tag) 1827 { return _GLIBCXX_STD_A::merge( 1828 __begin1, __end1, __begin2, __end2, __result, __comp); } 1829 1830 // Sequential fallback for input iterator case 1831 template<typename _IIter1, typename _IIter2, typename _OutputIterator, 1832 typename _Compare, typename _IteratorTag1, 1833 typename _IteratorTag2, typename _IteratorTag3> 1834 inline _OutputIterator 1835 __merge_switch(_IIter1 __begin1, _IIter1 __end1, 1836 _IIter2 __begin2, _IIter2 __end2, 1837 _OutputIterator __result, _Compare __comp, 1838 _IteratorTag1, _IteratorTag2, _IteratorTag3) 1839 { return _GLIBCXX_STD_A::merge(__begin1, __end1, __begin2, __end2, 1840 __result, __comp); } 1841 1842 // Parallel algorithm for random access iterators 1843 template<typename _IIter1, typename _IIter2, 1844 typename _OutputIterator, typename _Compare> 1845 _OutputIterator 1846 __merge_switch(_IIter1 __begin1, _IIter1 __end1, 1847 _IIter2 __begin2, _IIter2 __end2, 1848 _OutputIterator __result, _Compare __comp, 1849 random_access_iterator_tag, random_access_iterator_tag, 1850 random_access_iterator_tag) 1851 { 1852 if (_GLIBCXX_PARALLEL_CONDITION( 1853 (static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) 1854 >= __gnu_parallel::_Settings::get().merge_minimal_n 1855 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) 1856 >= __gnu_parallel::_Settings::get().merge_minimal_n))) 1857 return __gnu_parallel::__parallel_merge_advance( 1858 __begin1, __end1, __begin2, __end2, __result, 1859 (__end1 - __begin1) + (__end2 - __begin2), __comp); 1860 else 1861 return __gnu_parallel::__merge_advance( 1862 __begin1, __end1, __begin2, __end2, __result, 1863 (__end1 - __begin1) + (__end2 - __begin2), __comp); 1864 } 1865 1866 // Public interface 1867 template<typename _IIter1, typename _IIter2, 1868 typename _OutputIterator, typename _Compare> 1869 inline _OutputIterator 1870 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 1871 _IIter2 __end2, _OutputIterator __result, _Compare __comp) 1872 { 1873 return __merge_switch( 1874 __begin1, __end1, __begin2, __end2, __result, __comp, 1875 std::__iterator_category(__begin1), 1876 std::__iterator_category(__begin2), 1877 std::__iterator_category(__result)); 1878 } 1879 1880 // Public interface, insert default comparator 1881 template<typename _IIter1, typename _IIter2, 1882 typename _OutputIterator> 1883 inline _OutputIterator 1884 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 1885 _IIter2 __end2, _OutputIterator __result) 1886 { 1887 typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1; 1888 typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2; 1889 1890 return __gnu_parallel::merge(__begin1, __end1, __begin2, __end2, 1891 __result, __gnu_parallel::_Less<_ValueType1, _ValueType2>()); 1892 } 1893 1894 // Sequential fallback 1895 template<typename _RAIter> 1896 inline void 1897 nth_element(_RAIter __begin, _RAIter __nth, 1898 _RAIter __end, __gnu_parallel::sequential_tag) 1899 { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end); } 1900 1901 // Sequential fallback 1902 template<typename _RAIter, typename _Compare> 1903 inline void 1904 nth_element(_RAIter __begin, _RAIter __nth, 1905 _RAIter __end, _Compare __comp, 1906 __gnu_parallel::sequential_tag) 1907 { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end, __comp); } 1908 1909 // Public interface 1910 template<typename _RAIter, typename _Compare> 1911 inline void 1912 nth_element(_RAIter __begin, _RAIter __nth, 1913 _RAIter __end, _Compare __comp) 1914 { 1915 if (_GLIBCXX_PARALLEL_CONDITION( 1916 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1917 >= __gnu_parallel::_Settings::get().nth_element_minimal_n)) 1918 __gnu_parallel::__parallel_nth_element(__begin, __nth, __end, __comp); 1919 else 1920 nth_element(__begin, __nth, __end, __comp, 1921 __gnu_parallel::sequential_tag()); 1922 } 1923 1924 // Public interface, insert default comparator 1925 template<typename _RAIter> 1926 inline void 1927 nth_element(_RAIter __begin, _RAIter __nth, 1928 _RAIter __end) 1929 { 1930 typedef typename iterator_traits<_RAIter>::value_type _ValueType; 1931 __gnu_parallel::nth_element(__begin, __nth, __end, 1932 std::less<_ValueType>()); 1933 } 1934 1935 // Sequential fallback 1936 template<typename _RAIter, typename _Compare> 1937 inline void 1938 partial_sort(_RAIter __begin, _RAIter __middle, 1939 _RAIter __end, _Compare __comp, 1940 __gnu_parallel::sequential_tag) 1941 { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end, __comp); } 1942 1943 // Sequential fallback 1944 template<typename _RAIter> 1945 inline void 1946 partial_sort(_RAIter __begin, _RAIter __middle, 1947 _RAIter __end, __gnu_parallel::sequential_tag) 1948 { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end); } 1949 1950 // Public interface, parallel algorithm for random access iterators 1951 template<typename _RAIter, typename _Compare> 1952 void 1953 partial_sort(_RAIter __begin, _RAIter __middle, 1954 _RAIter __end, _Compare __comp) 1955 { 1956 if (_GLIBCXX_PARALLEL_CONDITION( 1957 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 1958 >= __gnu_parallel::_Settings::get().partial_sort_minimal_n)) 1959 __gnu_parallel:: 1960 __parallel_partial_sort(__begin, __middle, __end, __comp); 1961 else 1962 partial_sort(__begin, __middle, __end, __comp, 1963 __gnu_parallel::sequential_tag()); 1964 } 1965 1966 // Public interface, insert default comparator 1967 template<typename _RAIter> 1968 inline void 1969 partial_sort(_RAIter __begin, _RAIter __middle, 1970 _RAIter __end) 1971 { 1972 typedef iterator_traits<_RAIter> _TraitsType; 1973 typedef typename _TraitsType::value_type _ValueType; 1974 __gnu_parallel::partial_sort(__begin, __middle, __end, 1975 std::less<_ValueType>()); 1976 } 1977 1978 // Sequential fallback 1979 template<typename _FIterator> 1980 inline _FIterator 1981 max_element(_FIterator __begin, _FIterator __end, 1982 __gnu_parallel::sequential_tag) 1983 { return _GLIBCXX_STD_A::max_element(__begin, __end); } 1984 1985 // Sequential fallback 1986 template<typename _FIterator, typename _Compare> 1987 inline _FIterator 1988 max_element(_FIterator __begin, _FIterator __end, _Compare __comp, 1989 __gnu_parallel::sequential_tag) 1990 { return _GLIBCXX_STD_A::max_element(__begin, __end, __comp); } 1991 1992 // Sequential fallback for input iterator case 1993 template<typename _FIterator, typename _Compare, typename _IteratorTag> 1994 inline _FIterator 1995 __max_element_switch(_FIterator __begin, _FIterator __end, 1996 _Compare __comp, _IteratorTag) 1997 { return max_element(__begin, __end, __comp, 1998 __gnu_parallel::sequential_tag()); } 1999 2000 // Parallel algorithm for random access iterators 2001 template<typename _RAIter, typename _Compare> 2002 _RAIter 2003 __max_element_switch(_RAIter __begin, _RAIter __end, 2004 _Compare __comp, random_access_iterator_tag, 2005 __gnu_parallel::_Parallelism __parallelism_tag) 2006 { 2007 if (_GLIBCXX_PARALLEL_CONDITION( 2008 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 2009 >= __gnu_parallel::_Settings::get().max_element_minimal_n 2010 && __gnu_parallel::__is_parallel(__parallelism_tag))) 2011 { 2012 _RAIter __res(__begin); 2013 __gnu_parallel::__identity_selector<_RAIter> 2014 __functionality; 2015 __gnu_parallel:: 2016 __for_each_template_random_access( 2017 __begin, __end, __gnu_parallel::_Nothing(), __functionality, 2018 __gnu_parallel::__max_element_reduct<_Compare, _RAIter>(__comp), 2019 __res, __res, -1, __parallelism_tag); 2020 return __res; 2021 } 2022 else 2023 return max_element(__begin, __end, __comp, 2024 __gnu_parallel::sequential_tag()); 2025 } 2026 2027 // Public interface, insert default comparator 2028 template<typename _FIterator> 2029 inline _FIterator 2030 max_element(_FIterator __begin, _FIterator __end, 2031 __gnu_parallel::_Parallelism __parallelism_tag) 2032 { 2033 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 2034 return max_element(__begin, __end, std::less<_ValueType>(), 2035 __parallelism_tag); 2036 } 2037 2038 template<typename _FIterator> 2039 inline _FIterator 2040 max_element(_FIterator __begin, _FIterator __end) 2041 { 2042 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 2043 return __gnu_parallel::max_element(__begin, __end, 2044 std::less<_ValueType>()); 2045 } 2046 2047 // Public interface 2048 template<typename _FIterator, typename _Compare> 2049 inline _FIterator 2050 max_element(_FIterator __begin, _FIterator __end, _Compare __comp, 2051 __gnu_parallel::_Parallelism __parallelism_tag) 2052 { 2053 return __max_element_switch(__begin, __end, __comp, 2054 std::__iterator_category(__begin), 2055 __parallelism_tag); 2056 } 2057 2058 template<typename _FIterator, typename _Compare> 2059 inline _FIterator 2060 max_element(_FIterator __begin, _FIterator __end, _Compare __comp) 2061 { 2062 return __max_element_switch(__begin, __end, __comp, 2063 std::__iterator_category(__begin)); 2064 } 2065 2066 2067 // Sequential fallback 2068 template<typename _FIterator> 2069 inline _FIterator 2070 min_element(_FIterator __begin, _FIterator __end, 2071 __gnu_parallel::sequential_tag) 2072 { return _GLIBCXX_STD_A::min_element(__begin, __end); } 2073 2074 // Sequential fallback 2075 template<typename _FIterator, typename _Compare> 2076 inline _FIterator 2077 min_element(_FIterator __begin, _FIterator __end, _Compare __comp, 2078 __gnu_parallel::sequential_tag) 2079 { return _GLIBCXX_STD_A::min_element(__begin, __end, __comp); } 2080 2081 // Sequential fallback for input iterator case 2082 template<typename _FIterator, typename _Compare, typename _IteratorTag> 2083 inline _FIterator 2084 __min_element_switch(_FIterator __begin, _FIterator __end, 2085 _Compare __comp, _IteratorTag) 2086 { return min_element(__begin, __end, __comp, 2087 __gnu_parallel::sequential_tag()); } 2088 2089 // Parallel algorithm for random access iterators 2090 template<typename _RAIter, typename _Compare> 2091 _RAIter 2092 __min_element_switch(_RAIter __begin, _RAIter __end, 2093 _Compare __comp, random_access_iterator_tag, 2094 __gnu_parallel::_Parallelism __parallelism_tag) 2095 { 2096 if (_GLIBCXX_PARALLEL_CONDITION( 2097 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) 2098 >= __gnu_parallel::_Settings::get().min_element_minimal_n 2099 && __gnu_parallel::__is_parallel(__parallelism_tag))) 2100 { 2101 _RAIter __res(__begin); 2102 __gnu_parallel::__identity_selector<_RAIter> 2103 __functionality; 2104 __gnu_parallel:: 2105 __for_each_template_random_access( 2106 __begin, __end, __gnu_parallel::_Nothing(), __functionality, 2107 __gnu_parallel::__min_element_reduct<_Compare, _RAIter>(__comp), 2108 __res, __res, -1, __parallelism_tag); 2109 return __res; 2110 } 2111 else 2112 return min_element(__begin, __end, __comp, 2113 __gnu_parallel::sequential_tag()); 2114 } 2115 2116 // Public interface, insert default comparator 2117 template<typename _FIterator> 2118 inline _FIterator 2119 min_element(_FIterator __begin, _FIterator __end, 2120 __gnu_parallel::_Parallelism __parallelism_tag) 2121 { 2122 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 2123 return min_element(__begin, __end, std::less<_ValueType>(), 2124 __parallelism_tag); 2125 } 2126 2127 template<typename _FIterator> 2128 inline _FIterator 2129 min_element(_FIterator __begin, _FIterator __end) 2130 { 2131 typedef typename iterator_traits<_FIterator>::value_type _ValueType; 2132 return __gnu_parallel::min_element(__begin, __end, 2133 std::less<_ValueType>()); 2134 } 2135 2136 // Public interface 2137 template<typename _FIterator, typename _Compare> 2138 inline _FIterator 2139 min_element(_FIterator __begin, _FIterator __end, _Compare __comp, 2140 __gnu_parallel::_Parallelism __parallelism_tag) 2141 { 2142 return __min_element_switch(__begin, __end, __comp, 2143 std::__iterator_category(__begin), 2144 __parallelism_tag); 2145 } 2146 2147 template<typename _FIterator, typename _Compare> 2148 inline _FIterator 2149 min_element(_FIterator __begin, _FIterator __end, _Compare __comp) 2150 { 2151 return __min_element_switch(__begin, __end, __comp, 2152 std::__iterator_category(__begin)); 2153 } 2154 2155 #if __cplusplus >= 201703L 2156 using _GLIBCXX_STD_A::for_each_n; 2157 using _GLIBCXX_STD_A::sample; 2158 #endif 2159 } // end namespace 2160 } // end namespace 2161 2162 #endif /* _GLIBCXX_PARALLEL_ALGO_H */
