| 6554 |
serge |
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 |
// . |
|
|
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 |
|
|
41 |
#include |
|
|
42 |
#include |
|
|
43 |
#include |
|
|
44 |
#include |
|
|
45 |
#include |
|
|
46 |
#include |
|
|
47 |
#include |
|
|
48 |
#include |
|
|
49 |
#include |
|
|
50 |
#include |
|
|
51 |
#include |
|
|
52 |
#include |
|
|
53 |
#include |
|
|
54 |
#include |
|
|
55 |
#include |
|
|
56 |
#include |
|
|
57 |
#include |
|
|
58 |
#include |
|
|
59 |
#include |
|
|
60 |
|
|
|
61 |
namespace std _GLIBCXX_VISIBILITY(default) |
|
|
62 |
{ |
|
|
63 |
namespace __parallel |
|
|
64 |
{ |
|
|
65 |
// Sequential fallback |
|
|
66 |
template |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
1649 |
struct _CRandNumber |
|
|
1650 |
{ |
|
|
1651 |
int |
|
|
1652 |
operator()(int __limit) |
|
|
1653 |
{ return rand() % __limit; } |
|
|
1654 |
}; |
|
|
1655 |
|
|
|
1656 |
// Fill in random number generator. |
|
|
1657 |
template |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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( |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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( |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 */ |