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