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