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