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