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