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