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