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