]> git.ipfire.org Git - thirdparty/gcc.git/blame - libstdc++-v3/include/parallel/algo.h
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Add parallel mode.
[thirdparty/gcc.git] / libstdc++-v3 / include / parallel / algo.h
CommitLineData
c2ba9709
JS		 1// -*- C++ -*-
2
3// Copyright (C) 2007 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
67namespace std
68{
69namespace __parallel
70{
71 // Sequential fallback
72 template<typename InputIterator, typename Function>
73 inline Function
74 for_each(InputIterator begin, InputIterator end, Function f, __gnu_parallel::sequential_tag)
75 {
76 return _GLIBCXX_STD_P::for_each<InputIterator, Function>(begin, end, f);
77 }
78
79 // Sequential fallback for input iterator case
80 template<typename InputIterator, typename Function, typename IteratorTag>
81 Function
82 for_each_switch(InputIterator begin, InputIterator end, Function f, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
83 {
84 return for_each<InputIterator, Function>(begin, end, f, __gnu_parallel::sequential_tag());
85 }
86
87 // Parallel algorithm for random access iterators
88 template<typename RandomAccessIterator, typename Function>
89 Function
90 for_each_switch(RandomAccessIterator begin, RandomAccessIterator end, Function f, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
91 {
92 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::for_each_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
93 {
94 bool dummy;
95 __gnu_parallel::for_each_selector<RandomAccessIterator> functionality;
96 return __gnu_parallel::for_each_template_random_access(begin, end, f, functionality, __gnu_parallel::dummy_reduct(), true, dummy, -1, parallelism_tag);
97 }
98 else
99 return for_each<RandomAccessIterator, Function>(begin, end, f, __gnu_parallel::sequential_tag());
100 }
101
102 // Public interface
103 template<typename Iterator, typename Function>
104 inline Function
105 for_each(Iterator begin, Iterator end, Function f, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
106 {
107 typedef std::iterator_traits<Iterator> iterator_traits;
108 typedef typename iterator_traits::iterator_category iterator_category;
109
110 return for_each_switch(begin, end, f, iterator_category(), parallelism_tag);
111 }
112
113
114 // Sequential fallback
115 template<typename InputIterator, typename T>
116 inline InputIterator
117 find(InputIterator begin, InputIterator end, const T& val, __gnu_parallel::sequential_tag)
118 { return _GLIBCXX_STD_P::find<InputIterator, T>(begin, end, val); }
119
120 // Sequential fallback for input iterator case
121 template<typename InputIterator, typename T, typename IteratorTag>
122 inline InputIterator
123 find_switch(InputIterator begin, InputIterator end, const T& val, IteratorTag)
124 { return _GLIBCXX_STD_P::find(begin, end, val); }
125
126 // Parallel find for random access iterators
127 template<typename RandomAccessIterator, typename T>
128 RandomAccessIterator
129 find_switch(RandomAccessIterator begin, RandomAccessIterator end, const T& val, random_access_iterator_tag)
130 {
131 typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
132
133 if (_GLIBCXX_PARALLEL_CONDITION(true))
134 {
135 binder2nd<__gnu_parallel::equal_to<value_type, T> > comp(__gnu_parallel::equal_to<value_type, T>(), val);
136 return __gnu_parallel::find_template(begin, end, begin, comp, __gnu_parallel::find_if_selector()).first;
137 }
138 else
139 return _GLIBCXX_STD_P::find(begin, end, val);
140 }
141
142 // Public interface
143 template<typename InputIterator, typename T>
144 inline InputIterator
145 find(InputIterator begin, InputIterator end, const T& val)
146 {
147 typedef std::iterator_traits<InputIterator> iterator_traits;
148 typedef typename iterator_traits::iterator_category iterator_category;
149 return find_switch(begin, end, val, iterator_category());
150 }
151
152 // Sequential fallback
153 template<typename InputIterator, typename Predicate>
154 inline InputIterator
155 find_if(InputIterator begin, InputIterator end, Predicate pred, __gnu_parallel::sequential_tag)
156 {
157 return _GLIBCXX_STD_P::find_if<InputIterator, Predicate>(begin, end, pred);
158 }
159
160 // Sequential fallback for input iterator case
161 template<typename InputIterator, typename Predicate, typename IteratorTag>
162 inline InputIterator
163 find_if_switch(InputIterator begin, InputIterator end, Predicate pred, IteratorTag)
164 {
165 return _GLIBCXX_STD_P::find_if(begin, end, pred);
166 }
167
168 // Parallel find_if for random access iterators
169 template<typename RandomAccessIterator, typename Predicate>
170 RandomAccessIterator
171 find_if_switch(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, random_access_iterator_tag)
172 {
173 if (_GLIBCXX_PARALLEL_CONDITION(true))
174 return __gnu_parallel::find_template(begin, end, begin, pred, __gnu_parallel::find_if_selector()).first;
175 else
176 return _GLIBCXX_STD_P::find_if(begin, end, pred);
177 }
178
179 // Public interface
180 template<typename InputIterator, typename Predicate>
181 inline InputIterator
182 find_if (InputIterator begin, InputIterator end, Predicate pred)
183 {
184 typedef std::iterator_traits<InputIterator> iterator_traits;
185 typedef typename iterator_traits::iterator_category iterator_category;
186 return find_if_switch(begin, end, pred, iterator_category());
187 }
188
189 // Sequential fallback
190 template<typename InputIterator, typename ForwardIterator>
191 inline InputIterator
192 find_first_of(InputIterator begin1, InputIterator end1, ForwardIterator begin2, ForwardIterator end2, __gnu_parallel::sequential_tag)
193 {
194 return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2);
195 }
196
197 // Sequential fallback
198 template<typename InputIterator, typename ForwardIterator,
199 typename BinaryPredicate>
200 inline InputIterator
201 find_first_of(InputIterator begin1, InputIterator end1,
202 ForwardIterator begin2, ForwardIterator end2,
203 BinaryPredicate comp, __gnu_parallel::sequential_tag)
204 {
205 return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2, comp);
206 }
207
208 // Sequential fallback for input iterator type
209 template<typename InputIterator, typename ForwardIterator, typename IteratorTag1, typename IteratorTag2>
210 inline InputIterator
211 find_first_of_switch(InputIterator begin1, InputIterator end1,
212 ForwardIterator begin2, ForwardIterator end2, IteratorTag1, IteratorTag2)
213 {
214 return find_first_of(begin1, end1, begin2, end2, __gnu_parallel::sequential_tag());
215 }
216
217 // Parallel algorithm for random access iterators
218 template<typename RandomAccessIterator, typename ForwardIterator, typename BinaryPredicate, typename IteratorTag>
219 inline RandomAccessIterator
220 find_first_of_switch(RandomAccessIterator begin1, RandomAccessIterator end1,
221 ForwardIterator begin2, ForwardIterator end2, BinaryPredicate comp, random_access_iterator_tag, IteratorTag)
222 {
223 return __gnu_parallel::find_template(begin1, end1, begin1, comp, __gnu_parallel::find_first_of_selector<ForwardIterator>(begin2, end2)).first;
224 }
225
226 // Sequential fallback for input iterator type
227 template<typename InputIterator, typename ForwardIterator, typename BinaryPredicate, typename IteratorTag1, typename IteratorTag2>
228 inline
229 InputIterator
230 find_first_of_switch(InputIterator begin1, InputIterator end1,
231 ForwardIterator begin2, ForwardIterator end2, BinaryPredicate comp, IteratorTag1, IteratorTag2)
232 {
233 return find_first_of(begin1, end1, begin2, end2, comp, __gnu_parallel::sequential_tag());
234 }
235
236 // Public interface
237 template<typename InputIterator, typename ForwardIterator, typename BinaryPredicate>
238 inline InputIterator
239 find_first_of(InputIterator begin1, InputIterator end1,
240 ForwardIterator begin2, ForwardIterator end2, BinaryPredicate comp)
241 {
242 typedef std::iterator_traits<InputIterator> iteratori_traits;
243 typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
244 typedef typename iteratori_traits::iterator_category iteratori_category;
245 typedef typename iteratorf_traits::iterator_category iteratorf_category;
246
247 return find_first_of_switch(begin1, end1, begin2, end2, comp, iteratori_category(), iteratorf_category());
248 }
249
250 // Public interface, insert default comparator
251 template<typename InputIterator, typename ForwardIterator>
252 InputIterator
253 find_first_of(InputIterator begin1, InputIterator end1, ForwardIterator begin2, ForwardIterator end2)
254 {
255 typedef std::iterator_traits<InputIterator> iteratori_traits;
256 typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
257 typedef typename iteratori_traits::value_type valuei_type;
258 typedef typename iteratorf_traits::value_type valuef_type;
259
260 return find_first_of(begin1, end1, begin2, end2, __gnu_parallel::equal_to<valuei_type, valuef_type>());
261 }
262
263 // Sequential fallback
264 template<typename InputIterator, typename OutputIterator>
265 inline OutputIterator
266 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
267 __gnu_parallel::sequential_tag)
268 {
269 return _GLIBCXX_STD_P::unique_copy<InputIterator, OutputIterator>(begin1, end1, out);
270 }
271
272 // Sequential fallback
273 template<typename InputIterator, typename OutputIterator, typename Predicate>
274 inline OutputIterator
275 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
276 Predicate pred, __gnu_parallel::sequential_tag)
277 {
278 return _GLIBCXX_STD_P::unique_copy<InputIterator, OutputIterator, Predicate>(begin1, end1, out, pred);
279 }
280
281 // Sequential fallback for input iterator case
282 template<typename InputIterator, typename OutputIterator, typename Predicate, typename IteratorTag1, typename IteratorTag2>
283 inline OutputIterator
284 unique_copy_switch(InputIterator begin, InputIterator last, OutputIterator out,
285 Predicate pred, IteratorTag1, IteratorTag2)
286 {
287 return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred);
288 }
289
290 // Parallel unique_copy for random access iterators
291 template<typename RandomAccessIterator, typename RandomAccessOutputIterator, typename Predicate>
292 RandomAccessOutputIterator
293 unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last, RandomAccessOutputIterator out,
294 Predicate pred, random_access_iterator_tag, random_access_iterator_tag)
295 {
296 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(last - begin) > __gnu_parallel::Settings::unique_copy_minimal_n))
297 return __gnu_parallel::parallel_unique_copy(begin, last, out, pred);
298 else
299 return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred);
300 }
301
302 // Public interface
303 template<typename InputIterator, typename OutputIterator>
304 inline OutputIterator
305 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out)
306 {
307 typedef std::iterator_traits<InputIterator> iteratori_traits;
308 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
309 typedef typename iteratori_traits::iterator_category iteratori_category;
310 typedef typename iteratori_traits::value_type value_type;
311 typedef typename iteratoro_traits::iterator_category iteratoro_category;
312
313 return unique_copy_switch(begin1, end1, out, equal_to<value_type>(),
314 iteratori_category(), iteratoro_category());
315 }
316
317 // Public interface
318 template<typename InputIterator, typename OutputIterator, typename Predicate>
319 inline OutputIterator
320 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
321 Predicate pred)
322 {
323 typedef std::iterator_traits<InputIterator> iteratori_traits;
324 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
325 typedef typename iteratori_traits::iterator_category iteratori_category;
326 typedef typename iteratoro_traits::iterator_category iteratoro_category;
327
328 return unique_copy_switch(begin1, end1, out, pred, iteratori_category(), iteratoro_category());
329 }
330
331 // Sequential fallback
332 template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
333 inline OutputIterator
334 set_union(InputIterator1 begin1, InputIterator1 end1,
335 InputIterator2 begin2, InputIterator2 end2,
336 OutputIterator out, __gnu_parallel::sequential_tag)
337 {
338 return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out);
339 }
340
341 // Sequential fallback
342 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
343 inline OutputIterator
344 set_union(InputIterator1 begin1, InputIterator1 end1,
345 InputIterator2 begin2, InputIterator2 end2,
346 OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
347 {
348 return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out, pred);
349 }
350
351 // Sequential fallback for input iterator case
352 template<typename InputIterator1, typename InputIterator2, typename Predicate,
353 typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
354 inline OutputIterator
355 set_union_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
356 InputIterator2 end2, OutputIterator result, Predicate pred, IteratorTag1,
357 IteratorTag2, IteratorTag3)
358 {
359 return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, result, pred);
360 }
361
362 // Parallel set_union for random access iterators
363 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
364 typename OutputRandomAccessIterator, typename Predicate>
365 OutputRandomAccessIterator
366 set_union_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2,
367 RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred,
368 random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
369 {
370 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::set_union_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_union_minimal_n))
371 return __gnu_parallel::parallel_set_union(begin1, end1, begin2, end2, result, pred);
372 else
373 return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, result, pred);
374 }
375
376 // Public interface
377 template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
378 inline OutputIterator
379 set_union(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
380 {
381 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
382 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
383 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
384 typedef typename iteratori1_traits::iterator_category iteratori1_category;
385 typedef typename iteratori2_traits::iterator_category iteratori2_category;
386 typedef typename iteratoro_traits::iterator_category iteratoro_category;
387 typedef typename iteratori1_traits::value_type value1_type;
388 typedef typename iteratori2_traits::value_type value2_type;
389
390 return set_union_switch(begin1, end1, begin2, end2, out, __gnu_parallel::less<value1_type, value2_type>(),
391 iteratori1_category(), iteratori2_category(), iteratoro_category());
392 }
393
394 // Public interface
395 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
396 inline OutputIterator
397 set_union(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
398 InputIterator2 end2, OutputIterator out, Predicate pred)
399 {
400 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
401 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
402 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
403 typedef typename iteratori1_traits::iterator_category iteratori1_category;
404 typedef typename iteratori2_traits::iterator_category iteratori2_category;
405 typedef typename iteratoro_traits::iterator_category iteratoro_category;
406
407 return set_union_switch(begin1, end1, begin2, end2, out, pred,
408 iteratori1_category(), iteratori2_category(), iteratoro_category());
409 }
410
411 // Sequential fallback.
412 template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
413 inline OutputIterator
414 set_intersection(InputIterator1 begin1, InputIterator1 end1,
415 InputIterator2 begin2, InputIterator2 end2,
416 OutputIterator out, __gnu_parallel::sequential_tag)
417 {
418 return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, out);
419 }
420
421 // Sequential fallback.
422 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
423 inline OutputIterator
424 set_intersection(InputIterator1 begin1, InputIterator1 end1,
425 InputIterator2 begin2, InputIterator2 end2,
426 OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
427 {
428 return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, out, pred);
429 }
430
431 // Sequential fallback for input iterator case
432 template<typename InputIterator1, typename InputIterator2, typename Predicate,
433 typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
434 inline OutputIterator
435 set_intersection_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
436 InputIterator2 end2, OutputIterator result, Predicate pred, IteratorTag1,
437 IteratorTag2, IteratorTag3)
438 {
439 return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, result, pred);
440 }
441
442 // Parallel set_intersection for random access iterators
443 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
444 typename OutputRandomAccessIterator, typename Predicate>
445 OutputRandomAccessIterator
446 set_intersection_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2,
447 RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred,
448 random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
449 {
450 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::set_union_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_union_minimal_n))
451 return __gnu_parallel::parallel_set_intersection(begin1, end1, begin2, end2, result, pred);
452 else
453 return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, result, pred);
454 }
455
456 // Public interface
457 template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
458 inline OutputIterator
459 set_intersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
460 {
461 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
462 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
463 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
464 typedef typename iteratori1_traits::iterator_category iteratori1_category;
465 typedef typename iteratori2_traits::iterator_category iteratori2_category;
466 typedef typename iteratoro_traits::iterator_category iteratoro_category;
467 typedef typename iteratori1_traits::value_type value1_type;
468 typedef typename iteratori2_traits::value_type value2_type;
469
470 return set_intersection_switch(begin1, end1, begin2, end2, out, __gnu_parallel::less<value1_type, value2_type>(),
471 iteratori1_category(), iteratori2_category(), iteratoro_category());
472 }
473
474 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
475 inline OutputIterator
476 set_intersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
477 InputIterator2 end2, OutputIterator out, Predicate pred)
478 {
479 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
480 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
481 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
482 typedef typename iteratori1_traits::iterator_category iteratori1_category;
483 typedef typename iteratori2_traits::iterator_category iteratori2_category;
484 typedef typename iteratoro_traits::iterator_category iteratoro_category;
485
486 return set_intersection_switch(begin1, end1, begin2, end2, out, pred,
487 iteratori1_category(), iteratori2_category(), iteratoro_category());
488 }
489
490 // Sequential fallback
491 template<typename InputIterator1, typename InputIterator2,
492 typename OutputIterator>
493 inline OutputIterator
494 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
495 InputIterator2 begin2, InputIterator2 end2,
496 OutputIterator out, __gnu_parallel::sequential_tag)
497 {
498 return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1, begin2, end2, out);
499 }
500
501 // Sequential fallback
502 template<typename InputIterator1, typename InputIterator2,
503 typename OutputIterator, typename Predicate>
504 inline OutputIterator
505 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
506 InputIterator2 begin2, InputIterator2 end2,
507 OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
508 {
509 return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2, end2, out, pred);
510 }
511
512 // Sequential fallback for input iterator case
513 template<typename InputIterator1, typename InputIterator2, typename Predicate, typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
514 inline OutputIterator
515 set_symmetric_difference_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Predicate pred, IteratorTag1, IteratorTag2, IteratorTag3)
516 {
517 return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2, end2, result, pred);
518 }
519
520 // Parallel set_symmetric_difference for random access iterators
521 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
522 typename OutputRandomAccessIterator, typename Predicate>
523 OutputRandomAccessIterator
524 set_symmetric_difference_switch(RandomAccessIterator1 begin1,
525 RandomAccessIterator1 end1, RandomAccessIterator2 begin2,
526 RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred,
527 random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
528 {
529 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::set_symmetric_difference_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_symmetric_difference_minimal_n))
530 return __gnu_parallel::parallel_set_symmetric_difference(begin1, end1, begin2, end2, result, pred);
531 else
532 return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2, end2, result, pred);
533 }
534
535 // Public interface.
536 template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
537 inline OutputIterator
538 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, 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 iteratori1_category;
544 typedef typename iteratori2_traits::iterator_category iteratori2_category;
545 typedef typename iteratoro_traits::iterator_category iteratoro_category;
546 typedef typename iteratori1_traits::value_type value1_type;
547 typedef typename iteratori2_traits::value_type value2_type;
548
549 return set_symmetric_difference_switch(begin1, end1, begin2, end2, out, __gnu_parallel::less<value1_type, value2_type>(),
550 iteratori1_category(), iteratori2_category(), iteratoro_category());
551 }
552
553 // Public interface.
554 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
555 inline OutputIterator
556 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
557 InputIterator2 end2, OutputIterator out, Predicate pred)
558 {
559 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
560 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
561 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
562 typedef typename iteratori1_traits::iterator_category iteratori1_category;
563 typedef typename iteratori2_traits::iterator_category iteratori2_category;
564 typedef typename iteratoro_traits::iterator_category iteratoro_category;
565
566 return set_symmetric_difference_switch(begin1, end1, begin2, end2, out, pred,
567 iteratori1_category(), iteratori2_category(), iteratoro_category());
568 }
569
570 // Sequential fallback.
571 template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
572 inline OutputIterator
573 set_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out, __gnu_parallel::sequential_tag)
574 {
575 return _GLIBCXX_STD_P::set_difference(begin1,end1, begin2, end2, out);
576 }
577
578 // Sequential fallback.
579 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
580 inline OutputIterator
581 set_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
582 {
583 return _GLIBCXX_STD_P::set_difference(begin1, end1, begin2, end2, out, pred);
584 }
585
586 // Sequential fallback for input iterator case.
587 template<typename InputIterator1, typename InputIterator2, typename Predicate,
588 typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
589 inline OutputIterator
590 set_difference_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
591 InputIterator2 end2, OutputIterator result, Predicate pred, IteratorTag1, IteratorTag2, IteratorTag3)
592 {
593 return _GLIBCXX_STD_P::set_difference(begin1, end1, begin2, end2, result, pred);
594 }
595
596 // Parallel set_difference for random access iterators
597 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
598 typename OutputRandomAccessIterator, typename Predicate>
599 OutputRandomAccessIterator
600 set_difference_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2,
601 RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred,
602 random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
603 {
604 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::set_difference_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_difference_minimal_n))
605 return __gnu_parallel::parallel_set_difference(begin1, end1, begin2, end2, result, pred);
606 else
607 return _GLIBCXX_STD_P::set_difference(begin1, end1, begin2, end2, result, pred);
608 }
609
610 // Public interface
611 template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
612 inline OutputIterator
613 set_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
614 {
615 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
616 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
617 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
618 typedef typename iteratori1_traits::iterator_category iteratori1_category;
619 typedef typename iteratori2_traits::iterator_category iteratori2_category;
620 typedef typename iteratoro_traits::iterator_category iteratoro_category;
621 typedef typename iteratori1_traits::value_type value1_type;
622 typedef typename iteratori2_traits::value_type value2_type;
623
624 return set_difference_switch(begin1, end1, begin2, end2, out, __gnu_parallel::less<value1_type, value2_type>(),
625 iteratori1_category(), iteratori2_category(), iteratoro_category());
626 }
627
628 // Public interface
629 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
630 inline OutputIterator
631 set_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
632 InputIterator2 end2, OutputIterator out, Predicate pred)
633 {
634 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
635 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
636 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
637 typedef typename iteratori1_traits::iterator_category iteratori1_category;
638 typedef typename iteratori2_traits::iterator_category iteratori2_category;
639 typedef typename iteratoro_traits::iterator_category iteratoro_category;
640
641 return set_difference_switch(begin1, end1, begin2, end2, out, pred,
642 iteratori1_category(), iteratori2_category(), iteratoro_category());
643 }
644
645 // Sequential fallback
646 template<typename ForwardIterator>
647 inline ForwardIterator
648 adjacent_find(ForwardIterator begin, ForwardIterator end, __gnu_parallel::sequential_tag)
649 {
650 return _GLIBCXX_STD_P::adjacent_find<ForwardIterator>(begin, end);
651 }
652
653 // Sequential fallback
654 template<typename ForwardIterator, typename BinaryPredicate>
655 inline ForwardIterator
656 adjacent_find(ForwardIterator begin, ForwardIterator end, BinaryPredicate binary_pred, __gnu_parallel::sequential_tag)
657 {
658 return _GLIBCXX_STD_P::adjacent_find<ForwardIterator, BinaryPredicate>(begin, end, binary_pred);
659 }
660
661 // Parallel algorithm for random access iterators
662 template<typename RandomAccessIterator>
663 RandomAccessIterator
664 adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end, random_access_iterator_tag)
665 {
666 typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
667
668 if (_GLIBCXX_PARALLEL_CONDITION(true))
669 {
670 RandomAccessIterator spot = __gnu_parallel::find_template(begin, end - 1, begin, equal_to<value_type>(), __gnu_parallel::adjacent_find_selector()).first;
671 if (spot == (end - 1))
672 return end;
673 else
674 return spot;
675 }
676 else
677 return adjacent_find<RandomAccessIterator>(begin, end, __gnu_parallel::sequential_tag());
678 }
679
680 // Sequential fallback for input iterator case
681 template<typename ForwardIterator, typename IteratorTag>
682 inline ForwardIterator
683 adjacent_find_switch(ForwardIterator begin, ForwardIterator end, IteratorTag)
684 {
685 return adjacent_find<ForwardIterator>(begin, end, __gnu_parallel::sequential_tag());
686 }
687
688 // Public interface
689 template<typename ForwardIterator>
690 inline ForwardIterator
691 adjacent_find(ForwardIterator begin, ForwardIterator end)
692 {
693 return adjacent_find_switch(begin, end, typename std::iterator_traits<ForwardIterator>::iterator_category());
694 }
695
696 // Sequential fallback for input iterator case
697 template<typename ForwardIterator, typename BinaryPredicate, typename IteratorTag>
698 inline ForwardIterator
699 adjacent_find_switch(ForwardIterator begin, ForwardIterator end, BinaryPredicate binary_pred, IteratorTag)
700 {
701 return adjacent_find<ForwardIterator, BinaryPredicate>(begin, end, binary_pred, __gnu_parallel::sequential_tag());
702 }
703
704 // Parallel algorithm for random access iterators
705 template<typename RandomAccessIterator, typename BinaryPredicate>
706 RandomAccessIterator
707 adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end, BinaryPredicate binary_pred, random_access_iterator_tag)
708 {
709 if (_GLIBCXX_PARALLEL_CONDITION(true))
710 return __gnu_parallel::find_template(begin, end, begin, binary_pred, __gnu_parallel::adjacent_find_selector()).first;
711 else
712 return adjacent_find(begin, end, binary_pred, __gnu_parallel::sequential_tag());
713 }
714
715 // Public interface
716 template<typename ForwardIterator, typename BinaryPredicate>
717 inline ForwardIterator
718 adjacent_find(ForwardIterator begin, ForwardIterator end, BinaryPredicate binary_pred)
719 {
720 return adjacent_find_switch<ForwardIterator, BinaryPredicate>(begin, end, binary_pred, typename std::iterator_traits<ForwardIterator>::iterator_category());
721 }
722
723 // Sequential fallback
724 template<typename InputIterator, typename T>
725 inline typename iterator_traits<InputIterator>::difference_type
726 count(InputIterator begin, InputIterator end, const T& value, __gnu_parallel::sequential_tag)
727 {
728 return _GLIBCXX_STD_P::count<InputIterator, T>(begin, end, value);
729 }
730
731 // Parallel code for random access iterators
732 template<typename RandomAccessIterator, typename T>
733 typename iterator_traits<RandomAccessIterator>::difference_type
734 count_switch(RandomAccessIterator begin, RandomAccessIterator end, const T& value, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
735 {
736 typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
737 typedef typename iterator_traits<RandomAccessIterator>::difference_type difference_type;
738
739 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::count_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
740 {
741 difference_type res = 0;
742 __gnu_parallel::count_selector<RandomAccessIterator, difference_type> functionality;
743 __gnu_parallel::for_each_template_random_access(begin, end, value, functionality, std::plus<__gnu_parallel::sequence_index_t>(), res, res, -1, parallelism_tag);
744 return res;
745 }
746 else
747 return count<RandomAccessIterator, T>(begin, end, value, __gnu_parallel::sequential_tag());
748 }
749
750 // Sequential fallback for input iterator case.
751 template<typename InputIterator, typename T, typename IteratorTag>
752 typename iterator_traits<InputIterator>::difference_type
753 count_switch(InputIterator begin, InputIterator end, const T& value, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
754 {
755 return count<InputIterator, T>(begin, end, value, __gnu_parallel::sequential_tag());
756 }
757
758 // Public interface.
759 template<typename InputIterator, typename T>
760 inline typename iterator_traits<InputIterator>::difference_type
761 count(InputIterator begin, InputIterator end, const T& value, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_unbalanced)
762 {
763 return count_switch(begin, end, value, typename std::iterator_traits<InputIterator>::iterator_category(), parallelism_tag);
764 }
765
766 // Sequential fallback.
767 template<typename InputIterator, typename Predicate>
768 inline typename iterator_traits<InputIterator>::difference_type
769 count_if(InputIterator begin, InputIterator end, Predicate pred, __gnu_parallel::sequential_tag)
770 {
771 return _GLIBCXX_STD_P::count_if(begin, end, pred);
772 }
773
774 // Parallel count_if for random access iterators
775 template<typename RandomAccessIterator, typename Predicate>
776 typename iterator_traits<RandomAccessIterator>::difference_type
777 count_if_switch(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
778 {
779 typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
780 typedef typename iterator_traits<RandomAccessIterator>::difference_type difference_type;
781
782 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::count_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
783 {
784 difference_type res = 0;
785 __gnu_parallel::count_if_selector<RandomAccessIterator, difference_type> functionality;
786 __gnu_parallel::for_each_template_random_access(begin, end, pred, functionality, std::plus<__gnu_parallel::sequence_index_t>(), res, res, -1, parallelism_tag);
787 return res;
788 }
789 else
790 return count_if<RandomAccessIterator, Predicate>(begin, end, pred, __gnu_parallel::sequential_tag());
791 }
792
793 // Sequential fallback for input iterator case.
794 template<typename InputIterator, typename Predicate, typename IteratorTag>
795 typename iterator_traits<InputIterator>::difference_type
796 count_if_switch(InputIterator begin, InputIterator end, Predicate pred, IteratorTag, __gnu_parallel::parallelism)
797 {
798 return count_if<InputIterator, Predicate>(begin, end, pred, __gnu_parallel::sequential_tag());
799 }
800
801 // Public interface.
802 template<typename InputIterator, typename Predicate>
803 inline typename iterator_traits<InputIterator>::difference_type
804 count_if(InputIterator begin, InputIterator end, Predicate pred, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_unbalanced)
805 {
806 typedef iterator_traits<InputIterator> traits_type;
807 typedef typename traits_type::iterator_category iterator_category;
808 return count_if_switch(begin, end, pred, iterator_category(), parallelism_tag);
809 }
810
811
812 // Sequential fallback.
813 template<typename ForwardIterator1, typename ForwardIterator2>
814 inline ForwardIterator1
815 search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, __gnu_parallel::sequential_tag)
816 {
817 return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2);
818 }
819
820 // Parallel algorithm for random access iterator
821 template<typename RandomAccessIterator1, typename RandomAccessIterator2>
822 RandomAccessIterator1
823 search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator2 end2, random_access_iterator_tag, random_access_iterator_tag)
824 {
825 typedef std::iterator_traits<RandomAccessIterator1> iterator1_traits;
826 typedef typename iterator1_traits::value_type value1_type;
827 typedef std::iterator_traits<RandomAccessIterator2> iterator2_traits;
828 typedef typename iterator2_traits::value_type value2_type;
829
830 if (_GLIBCXX_PARALLEL_CONDITION(true))
831 return __gnu_parallel::search_template(begin1, end1, begin2, end2, __gnu_parallel::equal_to<value1_type, value2_type>());
832 else
833 return search(begin1, end1, begin2, end2, __gnu_parallel::sequential_tag());
834 }
835
836 // Sequential fallback for input iterator case
837 template<typename ForwardIterator1, typename ForwardIterator2, typename IteratorTag1, typename IteratorTag2>
838 inline ForwardIterator1
839 search_switch(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, IteratorTag1, IteratorTag2)
840 {
841 return search(begin1, end1, begin2, end2, __gnu_parallel::sequential_tag());
842 }
843
844 // Public interface.
845 template<typename ForwardIterator1, typename ForwardIterator2>
846 inline ForwardIterator1
847 search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2)
848 {
849 typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
850 typedef typename iterator1_traits::iterator_category iterator1_category;
851 typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
852 typedef typename iterator2_traits::iterator_category iterator2_category;
853
854 return search_switch(begin1, end1, begin2, end2, iterator1_category(), iterator2_category());
855 }
856
857 // Public interface.
858 template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
859 inline ForwardIterator1
860 search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred, __gnu_parallel::sequential_tag)
861 {
862 return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2, pred);
863 }
864
865 // Parallel algorithm for random access iterator.
866 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
867 typename BinaryPredicate>
868 RandomAccessIterator1
869 search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
870 RandomAccessIterator2 begin2, RandomAccessIterator2 end2, BinaryPredicate pred, random_access_iterator_tag, random_access_iterator_tag)
871 {
872 if (_GLIBCXX_PARALLEL_CONDITION(true))
873 return __gnu_parallel::search_template(begin1, end1, begin2, end2, pred);
874 else
875 return search(begin1, end1, begin2, end2, pred, __gnu_parallel::sequential_tag());
876 }
877
878 // Sequential fallback for input iterator case
879 template<typename ForwardIterator1, typename ForwardIterator2,
880 typename BinaryPredicate, typename IteratorTag1, typename IteratorTag2>
881 inline ForwardIterator1
882 search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
883 ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred, IteratorTag1, IteratorTag2)
884 {
885 return search(begin1, end1, begin2, end2, pred, __gnu_parallel::sequential_tag());
886 }
887
888 // Public interface
889 template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
890 inline ForwardIterator1
891 search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred)
892 {
893 typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
894 typedef typename iterator1_traits::iterator_category iterator1_category;
895 typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
896 typedef typename iterator2_traits::iterator_category iterator2_category;
897 return search_switch(begin1, end1, begin2, end2, pred, iterator1_category(), iterator2_category());
898 }
899
900 // Sequential fallback
901 template<typename ForwardIterator, typename Integer, typename T>
902 inline ForwardIterator
903 search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, __gnu_parallel::sequential_tag)
904 { return _GLIBCXX_STD_P::search_n(begin, end, count, val); }
905
906 // Sequential fallback
907 template<typename ForwardIterator, typename Integer, typename T, typename BinaryPredicate>
908 inline ForwardIterator
909 search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, BinaryPredicate binary_pred, __gnu_parallel::sequential_tag)
910 {
911 return _GLIBCXX_STD_P::search_n(begin, end, count, val, binary_pred);
912 }
913
914 // Public interface.
915 template<typename ForwardIterator, typename Integer, typename T>
916 inline ForwardIterator
917 search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val)
918 {
919 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
920 return search_n(begin, end, count, val, __gnu_parallel::equal_to<value_type, T>());
921 }
922
923 // Parallel algorithm for random access iterators.
924 template<typename RandomAccessIterator, typename Integer, typename T, typename BinaryPredicate>
925 RandomAccessIterator
926 search_n_switch(RandomAccessIterator begin, RandomAccessIterator end, Integer count, const T& val, BinaryPredicate binary_pred, random_access_iterator_tag)
927 {
928 if (_GLIBCXX_PARALLEL_CONDITION(true))
929 {
930 __gnu_parallel::pseudo_sequence<T, Integer> ps(val, count);
931 return __gnu_parallel::search_template(begin, end, ps.begin(), ps.end(), binary_pred);
932 }
933 else
934 return std::__search_n(begin, end, count, val, binary_pred, random_access_iterator_tag());
935 }
936
937 // Sequential fallback for input iterator case.
938 template<typename ForwardIterator, typename Integer, typename T, typename BinaryPredicate, typename IteratorTag>
939 inline ForwardIterator
940 search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, BinaryPredicate binary_pred, IteratorTag)
941 {
942 return __search_n(begin, end, count, val, binary_pred, IteratorTag());
943 }
944
945 // Public interface.
946 template<typename ForwardIterator, typename Integer, typename T, typename BinaryPredicate>
947 inline ForwardIterator
948 search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, BinaryPredicate binary_pred)
949 {
950 return search_n_switch(begin, end, count, val, binary_pred, typename std::iterator_traits<ForwardIterator>::iterator_category());
951 }
952
953 // Sequential fallback.
954 template<typename InputIterator, typename OutputIterator, typename UnaryOperation>
955 inline OutputIterator
956 transform(InputIterator begin, InputIterator end, OutputIterator result, UnaryOperation unary_op, __gnu_parallel::sequential_tag)
957 {
958 return _GLIBCXX_STD_P::transform(begin, end, result, unary_op);
959 }
960
961 // Sequential fallback
962 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryOperation>
963 inline OutputIterator
964 transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, OutputIterator result, BinaryOperation binary_op, __gnu_parallel::sequential_tag)
965 {
966 return _GLIBCXX_STD_P::transform(begin1, end1, begin2, result, binary_op);
967 }
968
969 // Parallel unary transform for random access iterators.
970 template<typename RandomAccessIterator1, typename RandomAccessIterator3, typename UnaryOperation>
971 RandomAccessIterator3
972 transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, RandomAccessIterator3 result, UnaryOperation unary_op, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
973 {
974 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::transform_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
975 {
976 bool dummy = true;
977 typedef __gnu_parallel::iterator_pair<RandomAccessIterator1, RandomAccessIterator3, random_access_iterator_tag> ip;
978 ip begin_pair(begin, result), end_pair(end, result + (end - begin));
979 __gnu_parallel::transform1_selector<ip> functionality;
980 __gnu_parallel::for_each_template_random_access(begin_pair, end_pair, unary_op, functionality, __gnu_parallel::dummy_reduct(), dummy, dummy, -1, parallelism_tag);
981 return functionality.finish_iterator;
982 }
983 else
984 return transform(begin, end, result, unary_op, __gnu_parallel::sequential_tag());
985 }
986
987 // Sequential fallback for input iterator case.
988 template<typename RandomAccessIterator1, typename RandomAccessIterator3, typename UnaryOperation, typename IteratorTag1, typename IteratorTag2>
989 inline RandomAccessIterator3
990 transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, RandomAccessIterator3 result, UnaryOperation unary_op, IteratorTag1, IteratorTag2, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
991 {
992 return _GLIBCXX_STD_P::transform(begin, end, result, unary_op);
993 }
994
995
996 // Parallel binary transform for random access iterators.
997 template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename RandomAccessIterator3, typename BinaryOperation>
998 RandomAccessIterator3
999 transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator3 result, BinaryOperation binary_op, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1000 {
1001 if (_GLIBCXX_PARALLEL_CONDITION((end1 - begin1) >= __gnu_parallel::Settings::transform_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
1002 {
1003 bool dummy = true;
1004 typedef __gnu_parallel::iterator_triple<RandomAccessIterator1, RandomAccessIterator2, RandomAccessIterator3, random_access_iterator_tag> ip;
1005 ip begin_triple(begin1, begin2, result), end_triple(end1, begin2 + (end1 - begin1), result + (end1 - begin1));
1006 __gnu_parallel::transform2_selector<ip> functionality;
1007 __gnu_parallel::for_each_template_random_access(begin_triple, end_triple, binary_op, functionality, __gnu_parallel::dummy_reduct(), dummy, dummy, -1, parallelism_tag);
1008 return functionality.finish_iterator;
1009 }
1010 else
1011 return transform(begin1, end1, begin2, result, binary_op, __gnu_parallel::sequential_tag());
1012 }
1013
1014 // Sequential fallback for input iterator case.
1015 template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename RandomAccessIterator3, typename BinaryOperation, typename tag1, typename tag2, typename tag3>
1016 inline RandomAccessIterator3
1017 transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator3 result, BinaryOperation binary_op, tag1, tag2, tag3, __gnu_parallel::parallelism)
1018 {
1019 return _GLIBCXX_STD_P::transform(begin1, end1, begin2, result, binary_op);
1020 }
1021
1022 // Public interface.
1023 template<typename InputIterator, typename OutputIterator, typename UnaryOperation>
1024 inline OutputIterator
1025 transform(InputIterator begin, InputIterator end, OutputIterator result,
1026 UnaryOperation unary_op, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1027 {
1028 typedef std::iterator_traits<InputIterator> iteratori_traits;
1029 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1030 typedef typename iteratori_traits::iterator_category iteratori_category;
1031 typedef typename iteratoro_traits::iterator_category iteratoro_category;
1032
1033 return transform1_switch(begin, end, result, unary_op,
1034 iteratori_category(), iteratoro_category(), parallelism_tag);
1035 }
1036
1037 // Public interface.
1038 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryOperation>
1039 inline OutputIterator
1040 transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, OutputIterator result, BinaryOperation binary_op, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1041 {
1042 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
1043 typedef typename iteratori1_traits::iterator_category iteratori1_category;
1044 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
1045 typedef typename iteratori2_traits::iterator_category iteratori2_category;
1046 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1047 typedef typename iteratoro_traits::iterator_category iteratoro_category;
1048
1049
1050 return transform2_switch(begin1, end1, begin2, result, binary_op,
1051 iteratori1_category(), iteratori2_category(), iteratoro_category(), parallelism_tag);
1052 }
1053
1054 // Sequential fallback
1055 template<typename ForwardIterator, typename T>
1056 inline void
1057 replace(ForwardIterator begin, ForwardIterator end, const T& old_value, const T& new_value, __gnu_parallel::sequential_tag)
1058 { _GLIBCXX_STD_P::replace(begin, end, old_value, new_value); }
1059
1060 // Sequential fallback for input iterator case
1061 template<typename ForwardIterator, typename T, typename IteratorTag>
1062 void
1063 replace_switch(ForwardIterator begin, ForwardIterator end, const T& old_value, const T& new_value, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
1064 { replace(begin, end, old_value, new_value, __gnu_parallel::sequential_tag()); }
1065
1066 // Parallel replace for random access iterators
1067 template<typename RandomAccessIterator, typename T>
1068 void
1069 replace_switch(RandomAccessIterator begin, RandomAccessIterator end, const T& old_value, const T& new_value, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1070 { replace(begin, end, old_value, new_value, __gnu_parallel::sequential_tag()); }
1071
1072 // Public interface
1073 template<typename ForwardIterator, typename T>
1074 inline void
1075 replace(ForwardIterator begin, ForwardIterator end, const T& old_value, const T& new_value, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1076 {
1077 replace_switch(begin, end, old_value, new_value, typename std::iterator_traits<ForwardIterator>::iterator_category(), parallelism_tag);
1078 }
1079
1080
1081 // Sequential fallback
1082 template<typename ForwardIterator, typename Predicate, typename T>
1083 inline void
1084 replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred, const T& new_value, __gnu_parallel::sequential_tag)
1085 { _GLIBCXX_STD_P::replace_if(begin, end, pred, new_value); }
1086
1087 // Sequential fallback for input iterator case
1088 template<typename ForwardIterator, typename Predicate, typename T, typename IteratorTag>
1089 void
1090 replace_if_switch(ForwardIterator begin, ForwardIterator end, Predicate pred, const T& new_value, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
1091 { replace_if(begin, end, pred, new_value, __gnu_parallel::sequential_tag()); }
1092
1093 // Parallel algorithm for random access iterators.
1094 template<typename RandomAccessIterator, typename Predicate, typename T>
1095 void
1096 replace_if_switch(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, const T& new_value, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1097 {
1098 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::replace_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
1099 {
1100 bool dummy;
1101 __gnu_parallel::replace_if_selector<RandomAccessIterator, Predicate, T> functionality(new_value);
1102 __gnu_parallel::for_each_template_random_access(begin, end, pred, functionality, __gnu_parallel::dummy_reduct(), true, dummy, -1, parallelism_tag);
1103 }
1104 else
1105 replace_if(begin, end, pred, new_value, __gnu_parallel::sequential_tag());
1106 }
1107
1108 // Public interface.
1109 template<typename ForwardIterator, typename Predicate, typename T>
1110 inline void
1111 replace_if(ForwardIterator begin, ForwardIterator end,
1112 Predicate pred, const T& new_value, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1113 {
1114 typedef std::iterator_traits<ForwardIterator> iterator_traits;
1115 typedef typename iterator_traits::iterator_category iterator_category;
1116
1117 replace_if_switch(begin, end, pred, new_value, iterator_category(), parallelism_tag);
1118 }
1119
1120 // Sequential fallback
1121 template<typename ForwardIterator, typename Generator>
1122 inline void
1123 generate(ForwardIterator begin, ForwardIterator end, Generator gen, __gnu_parallel::sequential_tag)
1124 { _GLIBCXX_STD_P::generate<ForwardIterator, Generator>(begin, end, gen); }
1125
1126 // Sequential fallback for input iterator case.
1127 template<typename ForwardIterator, typename Generator, typename IteratorTag>
1128 void
1129 generate_switch(ForwardIterator begin, ForwardIterator end, Generator gen, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
1130 { generate(begin, end, gen, __gnu_parallel::sequential_tag()); }
1131
1132 // Parallel algorithm for random access iterators.
1133 template<typename RandomAccessIterator, typename Generator>
1134 void
1135 generate_switch(RandomAccessIterator begin, RandomAccessIterator end,
1136 Generator gen, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1137 {
1138 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::generate_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
1139 {
1140 bool dummy;
1141 __gnu_parallel::generate_selector<RandomAccessIterator> functionality;
1142 __gnu_parallel::for_each_template_random_access(begin, end, gen, functionality, __gnu_parallel::dummy_reduct(), true, dummy, -1, parallelism_tag);
1143 }
1144 else
1145 generate(begin, end, gen, __gnu_parallel::sequential_tag());
1146 }
1147
1148 // Public interface.
1149 template<typename ForwardIterator, typename Generator>
1150 inline void
1151 generate(ForwardIterator begin, ForwardIterator end,
1152 Generator gen, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1153 {
1154 typedef std::iterator_traits<ForwardIterator> iterator_traits;
1155 typedef typename iterator_traits::iterator_category iterator_category;
1156 generate_switch(begin, end, gen, iterator_category(), parallelism_tag);
1157 }
1158
1159
1160 // Sequential fallback.
1161 template<typename OutputIterator, typename Size, typename Generator>
1162 inline OutputIterator
1163 generate_n(OutputIterator begin, Size n, Generator gen, __gnu_parallel::sequential_tag)
1164 { return _GLIBCXX_STD_P::generate_n(begin, n, gen); }
1165
1166 // Sequential fallback for input iterator case.
1167 template<typename OutputIterator, typename Size, typename Generator, typename IteratorTag>
1168 OutputIterator
1169 generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag, __gnu_parallel::parallelism)
1170 { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); }
1171
1172 // Parallel algorithm for random access iterators.
1173 template<typename RandomAccessIterator, typename Size, typename Generator>
1174 RandomAccessIterator
1175 generate_n_switch(RandomAccessIterator begin, Size n, Generator gen, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1176 { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); }
1177
1178 // Public interface.
1179 template<typename OutputIterator, typename Size, typename Generator>
1180 inline OutputIterator
1181 generate_n(OutputIterator begin, Size n, Generator gen, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1182 {
1183 typedef std::iterator_traits<OutputIterator> iterator_traits;
1184 typedef typename iterator_traits::iterator_category iterator_category;
1185 return generate_n_switch(begin, n, gen, iterator_category(), parallelism_tag);
1186 }
1187
1188
1189 // Sequential fallback.
1190 template<typename RandomAccessIterator>
1191 inline void
1192 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::sequential_tag)
1193 { _GLIBCXX_STD_P::random_shuffle(begin, end); }
1194
1195 // Sequential fallback.
1196 template<typename RandomAccessIterator, typename RandomNumberGenerator>
1197 inline void
1198 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator& rand, __gnu_parallel::sequential_tag)
1199 { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); }
1200
1201
1202 /** @brief Functor wrapper for std::rand(). */
1203 template<typename must_be_int = int>
1204 struct c_rand_number
1205 {
1206 inline int operator()(int limit)
1207 { return rand() % limit; }
1208 };
1209
1210 // Fill in random number generator.
1211 template<typename RandomAccessIterator>
1212 inline void
1213 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end)
1214 {
1215 c_rand_number<> r;
1216 // Parallelization still possible.
1217 random_shuffle(begin, end, r);
1218 }
1219
1220 // Parallel algorithm for random access iterators.
1221 template<typename RandomAccessIterator, typename RandomNumberGenerator>
1222 void
1223 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator& rand)
1224 {
1225 if (begin == end)
1226 return;
1227 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::random_shuffle_minimal_n))
1228 __gnu_parallel::parallel_random_shuffle(begin, end, rand);
1229 else
1230 __gnu_parallel::sequential_random_shuffle(begin, end, rand);
1231 }
1232
1233 // Sequential fallback.
1234 template<typename ForwardIterator, typename Predicate>
1235 inline ForwardIterator
1236 partition(ForwardIterator begin, ForwardIterator end, Predicate pred, __gnu_parallel::sequential_tag)
1237 { return _GLIBCXX_STD_P::partition(begin, end, pred); }
1238
1239 // Sequential fallback for input iterator case.
1240 template<typename ForwardIterator, typename Predicate, typename IteratorTag>
1241 inline ForwardIterator
1242 partition_switch(ForwardIterator begin, ForwardIterator end, Predicate pred, IteratorTag)
1243 { return partition(begin, end, pred, __gnu_parallel::sequential_tag()); }
1244
1245 // Parallel algorithm for random access iterators.
1246 template<typename RandomAccessIterator, typename Predicate>
1247 RandomAccessIterator
1248 partition_switch(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, random_access_iterator_tag)
1249 {
1250 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::partition_minimal_n))
1251 {
1252 typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
1253 difference_type middle = __gnu_parallel::parallel_partition(begin, end, pred, __gnu_parallel::get_max_threads());
1254 return begin + middle;
1255 }
1256 else
1257 return partition(begin, end, pred, __gnu_parallel::sequential_tag());
1258 }
1259
1260 // Public interface.
1261 template<typename ForwardIterator, typename Predicate>
1262 inline ForwardIterator
1263 partition(ForwardIterator begin, ForwardIterator end, Predicate pred)
1264 {
1265 return partition_switch(begin, end, pred, typename std::iterator_traits<ForwardIterator>::iterator_category());
1266 }
1267
1268 // Sequential fallback
1269 template<typename RandomAccessIterator>
1270 inline void
1271 sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::sequential_tag)
1272 { _GLIBCXX_STD_P::sort<RandomAccessIterator>(begin, end); }
1273
1274 // Sequential fallback
1275 template<typename RandomAccessIterator, typename Comparator>
1276 inline void
1277 sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, __gnu_parallel::sequential_tag)
1278 { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end, comp); }
1279
1280 // Public interface, insert default comparator
1281 template<typename RandomAccessIterator>
1282 inline void
1283 sort(RandomAccessIterator begin, RandomAccessIterator end)
1284 {
1285 typedef iterator_traits<RandomAccessIterator> traits_type;
1286 typedef typename traits_type::value_type value_type;
1287 sort(begin, end, std::less<value_type>());
1288 }
1289
1290 template<typename RandomAccessIterator, typename Comparator>
1291 void
1292 sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
1293 {
1294 typedef iterator_traits<RandomAccessIterator> traits_type;
1295 typedef typename traits_type::value_type value_type;
1296
1297 if (begin != end)
1298 {
1299 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::sort_minimal_n))
1300 __gnu_parallel::parallel_sort(begin, end, comp, false);
1301 else
1302 sort<RandomAccessIterator, Comparator>(begin, end, comp, __gnu_parallel::sequential_tag());
1303 }
1304 }
1305
1306 // Sequential fallback.
1307 template<typename RandomAccessIterator>
1308 inline void
1309 stable_sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::sequential_tag)
1310 {
1311 return _GLIBCXX_STD_P::stable_sort<RandomAccessIterator>(begin, end);
1312 }
1313
1314 // Sequential fallback.
1315 template<typename RandomAccessIterator, typename Comparator>
1316 inline void
1317 stable_sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, __gnu_parallel::sequential_tag)
1318 {
1319 return _GLIBCXX_STD_P::stable_sort<RandomAccessIterator, Comparator>(begin, end, comp);
1320 }
1321
1322 template<typename RandomAccessIterator>
1323 void
1324 stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
1325 {
1326 typedef iterator_traits<RandomAccessIterator> traits_type;
1327 typedef typename traits_type::value_type value_type;
1328
1329 stable_sort(begin, end, std::less<value_type>());
1330 }
1331
1332 // Parallel algorithm for random access iterators
1333 template<typename RandomAccessIterator, typename Comparator>
1334 void
1335 stable_sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
1336 {
1337 if (begin != end)
1338 {
1339 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::sort_minimal_n))
1340 __gnu_parallel::parallel_sort(begin, end, comp, true);
1341 else
1342 stable_sort<RandomAccessIterator, Comparator>(begin, end, comp, __gnu_parallel::sequential_tag());
1343 }
1344 }
1345
1346 // Sequential fallback
1347 template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
1348 inline OutputIterator
1349 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result,
1350 __gnu_parallel::sequential_tag)
1351 {
1352 return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result);
1353 }
1354
1355 // Sequential fallback
1356 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator>
1357 inline OutputIterator
1358 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Comparator comp,
1359 __gnu_parallel::sequential_tag)
1360 {
1361 return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp);
1362 }
1363
1364 // Sequential fallback for input iterator case
1365 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
1366 inline OutputIterator
1367 merge_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Comparator comp, IteratorTag1, IteratorTag2, IteratorTag3)
1368 {
1369 return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp);
1370 }
1371
1372 // Parallel algorithm for random access iterators
1373 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator>
1374 OutputIterator
1375 merge_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Comparator comp, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
1376 {
1377 if (_GLIBCXX_PARALLEL_CONDITION((static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::merge_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::merge_minimal_n)))
1378 return __gnu_parallel::parallel_merge_advance(begin1, end1, begin2, end2, result, (end1 - begin1) + (end2 - begin2), comp);
1379 else
1380 return __gnu_parallel::merge_advance(begin1, end1, begin2, end2, result, (end1 - begin1) + (end2 - begin2), comp);
1381 }
1382
1383 // Public interface
1384 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator>
1385 inline OutputIterator
1386 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Comparator comp)
1387 {
1388 typedef typename iterator_traits<InputIterator1>::value_type value_type;
1389
1390 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
1391 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
1392 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1393 typedef typename iteratori1_traits::iterator_category iteratori1_category;
1394 typedef typename iteratori2_traits::iterator_category iteratori2_category;
1395 typedef typename iteratoro_traits::iterator_category iteratoro_category;
1396
1397 return merge_switch(begin1, end1, begin2, end2, result, comp, iteratori1_category(), iteratori2_category(), iteratoro_category());
1398 }
1399
1400
1401 // Public interface, insert default comparator
1402 template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
1403 inline OutputIterator
1404 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result)
1405 {
1406 typedef std::iterator_traits<InputIterator1> iterator1_traits;
1407 typedef std::iterator_traits<InputIterator2> iterator2_traits;
1408 typedef typename iterator1_traits::value_type value1_type;
1409 typedef typename iterator2_traits::value_type value2_type;
1410
1411 return merge(begin1, end1, begin2, end2, result, __gnu_parallel::less<value1_type, value2_type>());
1412 }
1413
1414 // Sequential fallback
1415 template<typename RandomAccessIterator>
1416 inline void
1417 nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, __gnu_parallel::sequential_tag)
1418 { return _GLIBCXX_STD_P::nth_element(begin, nth, end); }
1419
1420 // Sequential fallback
1421 template<typename RandomAccessIterator, typename Comparator>
1422 void
1423 nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, Comparator comp, __gnu_parallel::sequential_tag)
1424 { return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); }
1425
1426 // Public interface
1427 template<typename RandomAccessIterator, typename Comparator>
1428 inline void
1429 nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, Comparator comp)
1430 {
1431 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::nth_element_minimal_n))
1432 __gnu_parallel::parallel_nth_element(begin, nth, end, comp);
1433 else
1434 nth_element(begin, nth, end, comp, __gnu_parallel::sequential_tag());
1435 }
1436
1437 // Public interface, insert default comparator
1438 template<typename RandomAccessIterator>
1439 void
1440 nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end)
1441 {
1442 typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
1443 nth_element(begin, nth, end, std::less<value_type>());
1444 }
1445
1446 // Sequential fallback
1447 template<typename _RandomAccessIterator, typename _Compare>
1448 void
1449 partial_sort(_RandomAccessIterator begin, _RandomAccessIterator middle, _RandomAccessIterator end, _Compare comp, __gnu_parallel::sequential_tag)
1450 { _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); }
1451
1452 // Sequential fallback
1453 template<typename _RandomAccessIterator>
1454 void
1455 partial_sort(_RandomAccessIterator begin, _RandomAccessIterator middle, _RandomAccessIterator end, __gnu_parallel::sequential_tag)
1456 { _GLIBCXX_STD_P::partial_sort(begin, middle, end); }
1457
1458 // Public interface, parallel algorithm for random access iterators
1459 template<typename _RandomAccessIterator, typename _Compare>
1460 void
1461 partial_sort(_RandomAccessIterator begin, _RandomAccessIterator middle, _RandomAccessIterator end, _Compare comp)
1462 {
1463 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::partial_sort_minimal_n))
1464 __gnu_parallel::parallel_partial_sort(begin, middle, end, comp);
1465 else
1466 partial_sort(begin, middle, end, comp, __gnu_parallel::sequential_tag());
1467 }
1468
1469 // Public interface, insert default comparator
1470 template<typename _RandomAccessIterator>
1471 void
1472 partial_sort(_RandomAccessIterator begin, _RandomAccessIterator middle, _RandomAccessIterator end)
1473 {
1474 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
1475 partial_sort(begin, middle, end, std::less<value_type>());
1476 }
1477
1478 // Sequential fallback
1479 template<typename ForwardIterator>
1480 inline ForwardIterator
1481 max_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::sequential_tag)
1482 { return _GLIBCXX_STD_P::max_element(begin, end); }
1483
1484 // Sequential fallback
1485 template<typename ForwardIterator, typename Comparator>
1486 inline ForwardIterator
1487 max_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::sequential_tag)
1488 { return _GLIBCXX_STD_P::max_element(begin, end, comp); }
1489
1490 // Sequential fallback for input iterator case
1491 template<typename ForwardIterator, typename Comparator, typename IteratorTag>
1492 ForwardIterator
1493 max_element_switch(ForwardIterator begin, ForwardIterator end, Comparator comp, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
1494 { return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
1495
1496 // Public interface, insert default comparator
1497 template<typename ForwardIterator>
1498 inline ForwardIterator
1499 max_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1500 {
1501 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
1502 return max_element(begin, end, std::less<value_type>(), parallelism_tag);
1503 }
1504
1505 template<typename RandomAccessIterator, typename Comparator>
1506 RandomAccessIterator
1507 max_element_switch(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1508 {
1509 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::max_element_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
1510 {
1511 RandomAccessIterator res(begin);
1512 __gnu_parallel::identity_selector<RandomAccessIterator> functionality;
1513 __gnu_parallel::for_each_template_random_access(begin, end, __gnu_parallel::nothing(), functionality, __gnu_parallel::max_element_reduct<Comparator, RandomAccessIterator>(comp), res, res, -1, parallelism_tag);
1514 return res;
1515 }
1516 else
1517 return max_element(begin, end, __gnu_parallel::sequential_tag());
1518 }
1519
1520 // Public interface
1521 template<typename ForwardIterator, typename Comparator>
1522 inline ForwardIterator
1523 max_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1524 {
1525 return max_element_switch(begin, end, comp, typename std::iterator_traits<ForwardIterator>::iterator_category(), parallelism_tag);
1526 }
1527
1528 // Sequential fallback
1529 template<typename ForwardIterator>
1530 inline
1531 ForwardIterator
1532 min_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::sequential_tag)
1533 { return _GLIBCXX_STD_P::min_element(begin, end); }
1534
1535 // Sequential fallback
1536 template<typename ForwardIterator, typename Comparator>
1537 inline ForwardIterator
1538 min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::sequential_tag)
1539 { return _GLIBCXX_STD_P::min_element(begin, end, comp); }
1540
1541 // Public interface
1542 template<typename ForwardIterator>
1543 inline ForwardIterator
1544 min_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1545 {
1546 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
1547 return min_element(begin, end, std::less<value_type>(), parallelism_tag);
1548 }
1549
1550 // Sequential fallback for input iterator case
1551 template<typename ForwardIterator, typename Comparator, typename IteratorTag>
1552 ForwardIterator
1553 min_element_switch(ForwardIterator begin, ForwardIterator end, Comparator comp, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
1554 { return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
1555
1556 // Parallel algorithm for random access iterators
1557 template<typename RandomAccessIterator, typename Comparator>
1558 RandomAccessIterator
1559 min_element_switch(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1560 {
1561 if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::min_element_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
1562 {
1563 RandomAccessIterator res(begin);
1564 __gnu_parallel::identity_selector<RandomAccessIterator> functionality;
1565 __gnu_parallel::for_each_template_random_access(begin, end, __gnu_parallel::nothing(), functionality, __gnu_parallel::min_element_reduct<Comparator, RandomAccessIterator>(comp), res, res, -1, parallelism_tag);
1566 return res;
1567 }
1568 else
1569 return min_element(begin, end, __gnu_parallel::sequential_tag());
1570 }
1571
1572 // Public interface
1573 template<typename ForwardIterator, typename Comparator>
1574 inline ForwardIterator
1575 min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1576 {
1577 typedef iterator_traits<ForwardIterator> traits_type;
1578 typedef typename traits_type::iterator_category iterator_category;
1579 return min_element_switch(begin, end, comp, iterator_category(), parallelism_tag);
1580 }
1581} // end namespace
1582} // end namespace
1583
1584#endif /* _GLIBCXX_ALGORITHM_H */
1585
Mirror of https://gcc.gnu.org/git/gcc.git