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