3 // Copyright (C) 2007-2018 Free Software Foundation, Inc.
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
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.
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.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file parallel/algobase.h
26 * @brief Parallel STL function calls corresponding to the
27 * stl_algobase.h header. The functions defined here mainly do case
28 * switches and call the actual parallelized versions in other files.
29 * Inlining policy: Functions that basically only contain one
30 * function call, are declared inline.
31 * This file is a GNU parallel extension to the Standard C++ Library.
34 // Written by Johannes Singler and Felix Putze.
36 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
37 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1
39 #include <bits/stl_algobase.h>
40 #include <parallel/base.h>
41 #include <parallel/algorithmfwd.h>
42 #include <parallel/find.h>
43 #include <parallel/find_selectors.h>
45 namespace std
_GLIBCXX_VISIBILITY(default)
49 // NB: equal and lexicographical_compare require mismatch.
51 // Sequential fallback
52 template<typename _IIter1
, typename _IIter2
>
53 inline pair
<_IIter1
, _IIter2
>
54 mismatch(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
55 __gnu_parallel::sequential_tag
)
56 { return _GLIBCXX_STD_A::mismatch(__begin1
, __end1
, __begin2
); }
58 // Sequential fallback
59 template<typename _IIter1
, typename _IIter2
, typename _Predicate
>
60 inline pair
<_IIter1
, _IIter2
>
61 mismatch(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
62 _Predicate __pred
, __gnu_parallel::sequential_tag
)
63 { return _GLIBCXX_STD_A::mismatch(__begin1
, __end1
, __begin2
, __pred
); }
65 // Sequential fallback for input iterator case
66 template<typename _IIter1
, typename _IIter2
,
67 typename _Predicate
, typename _IteratorTag1
, typename _IteratorTag2
>
68 inline pair
<_IIter1
, _IIter2
>
69 __mismatch_switch(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
70 _Predicate __pred
, _IteratorTag1
, _IteratorTag2
)
71 { return _GLIBCXX_STD_A::mismatch(__begin1
, __end1
, __begin2
, __pred
); }
73 // Parallel mismatch for random access iterators
74 template<typename _RAIter1
, typename _RAIter2
, typename _Predicate
>
75 pair
<_RAIter1
, _RAIter2
>
76 __mismatch_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
77 _RAIter2 __begin2
, _Predicate __pred
,
78 random_access_iterator_tag
, random_access_iterator_tag
)
80 if (_GLIBCXX_PARALLEL_CONDITION(true))
83 __gnu_parallel::__find_template(__begin1
, __end1
, __begin2
, __pred
,
85 __mismatch_selector()).first
;
86 return make_pair(__res
, __begin2
+ (__res
- __begin1
));
89 return _GLIBCXX_STD_A::mismatch(__begin1
, __end1
, __begin2
, __pred
);
93 template<typename _IIter1
, typename _IIter2
>
94 inline pair
<_IIter1
, _IIter2
>
95 mismatch(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
)
97 typedef __gnu_parallel::_EqualTo
<
98 typename
std::iterator_traits
<_IIter1
>::value_type
,
99 typename
std::iterator_traits
<_IIter2
>::value_type
> _EqualTo
;
101 return __mismatch_switch(__begin1
, __end1
, __begin2
, _EqualTo(),
102 std::__iterator_category(__begin1
),
103 std::__iterator_category(__begin2
));
107 template<typename _IIter1
, typename _IIter2
, typename _Predicate
>
108 inline pair
<_IIter1
, _IIter2
>
109 mismatch(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
112 return __mismatch_switch(__begin1
, __end1
, __begin2
, __pred
,
113 std::__iterator_category(__begin1
),
114 std::__iterator_category(__begin2
));
117 #if __cplusplus > 201103L
118 // Sequential fallback.
119 template<typename _InputIterator1
, typename _InputIterator2
>
120 inline pair
<_InputIterator1
, _InputIterator2
>
121 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
122 _InputIterator2 __first2
, _InputIterator2 __last2
,
123 __gnu_parallel::sequential_tag
)
124 { return _GLIBCXX_STD_A::mismatch(__first1
, __last1
, __first2
, __last2
); }
126 // Sequential fallback.
127 template<typename _InputIterator1
, typename _InputIterator2
,
128 typename _BinaryPredicate
>
129 inline pair
<_InputIterator1
, _InputIterator2
>
130 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
131 _InputIterator2 __first2
, _InputIterator2 __last2
,
132 _BinaryPredicate __binary_pred
,
133 __gnu_parallel::sequential_tag
)
135 return _GLIBCXX_STD_A::mismatch(__first1
, __last1
, __first2
, __last2
,
139 // Sequential fallback for input iterator case
140 template<typename _IIter1
, typename _IIter2
,
141 typename _Predicate
, typename _IteratorTag1
, typename _IteratorTag2
>
142 inline pair
<_IIter1
, _IIter2
>
143 __mismatch_switch(_IIter1 __begin1
, _IIter1 __end1
,
144 _IIter2 __begin2
, _IIter2 __end2
, _Predicate __pred
,
145 _IteratorTag1
, _IteratorTag2
)
147 return _GLIBCXX_STD_A::mismatch(__begin1
, __end1
,
148 __begin2
, __end2
, __pred
);
151 // Parallel mismatch for random access iterators
152 template<typename _RAIter1
, typename _RAIter2
, typename _Predicate
>
153 pair
<_RAIter1
, _RAIter2
>
154 __mismatch_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
155 _RAIter2 __begin2
, _RAIter2 __end2
, _Predicate __pred
,
156 random_access_iterator_tag
, random_access_iterator_tag
)
158 if (_GLIBCXX_PARALLEL_CONDITION(true))
160 if ((__end2
- __begin2
) < (__end1
- __begin1
))
161 __end1
= __begin1
+ (__end2
- __begin2
);
164 __gnu_parallel::__find_template(__begin1
, __end1
, __begin2
, __pred
,
166 __mismatch_selector()).first
;
167 return make_pair(__res
, __begin2
+ (__res
- __begin1
));
170 return _GLIBCXX_STD_A::mismatch(__begin1
, __end1
,
171 __begin2
, __end2
, __pred
);
174 template<typename _IIter1
, typename _IIter2
>
175 inline pair
<_IIter1
, _IIter2
>
176 mismatch(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
, _IIter2 __end2
)
178 typedef __gnu_parallel::_EqualTo
<
179 typename
std::iterator_traits
<_IIter1
>::value_type
,
180 typename
std::iterator_traits
<_IIter2
>::value_type
> _EqualTo
;
182 return __mismatch_switch(__begin1
, __end1
, __begin2
, __end2
, _EqualTo(),
183 std::__iterator_category(__begin1
),
184 std::__iterator_category(__begin2
));
187 template<typename _InputIterator1
, typename _InputIterator2
,
188 typename _BinaryPredicate
>
189 inline pair
<_InputIterator1
, _InputIterator2
>
190 mismatch(_InputIterator1 __begin1
, _InputIterator1 __end1
,
191 _InputIterator2 __begin2
, _InputIterator2 __end2
,
192 _BinaryPredicate __binary_pred
)
194 return __mismatch_switch(__begin1
, __end1
, __begin2
, __end2
,
196 std::__iterator_category(__begin1
),
197 std::__iterator_category(__begin2
));
201 // Sequential fallback
202 template<typename _IIter1
, typename _IIter2
>
204 equal(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
205 __gnu_parallel::sequential_tag
)
206 { return _GLIBCXX_STD_A::equal(__begin1
, __end1
, __begin2
); }
208 // Sequential fallback
209 template<typename _IIter1
, typename _IIter2
, typename _Predicate
>
211 equal(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
212 _Predicate __pred
, __gnu_parallel::sequential_tag
)
213 { return _GLIBCXX_STD_A::equal(__begin1
, __end1
, __begin2
, __pred
); }
216 template<typename _IIter1
, typename _IIter2
>
218 equal(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
)
220 return __gnu_parallel::mismatch(__begin1
, __end1
, __begin2
).first
225 template<typename _IIter1
, typename _IIter2
, typename _Predicate
>
227 equal(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
230 return __gnu_parallel::mismatch(__begin1
, __end1
, __begin2
, __pred
).first
234 #if __cplusplus > 201103L
235 // Sequential fallback
236 template<typename _IIter1
, typename _IIter2
>
238 equal(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
, _IIter2 __end2
,
239 __gnu_parallel::sequential_tag
)
241 return _GLIBCXX_STD_A::equal(__begin1
, __end1
, __begin2
, __end2
);
244 // Sequential fallback
245 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
247 equal(_IIter1 __begin1
, _IIter1 __end1
,
248 _IIter2 __begin2
, _IIter2 __end2
, _BinaryPredicate __binary_pred
,
249 __gnu_parallel::sequential_tag
)
251 return _GLIBCXX_STD_A::equal(__begin1
, __end1
, __begin2
, __end2
,
255 // Sequential fallback for input iterator case
256 template<typename _IIter1
, typename _IIter2
,
257 typename _Predicate
, typename _IteratorTag1
, typename _IteratorTag2
>
259 __equal_switch(_IIter1 __begin1
, _IIter1 __end1
,
260 _IIter2 __begin2
, _IIter2 __end2
, _Predicate __pred
,
261 _IteratorTag1
, _IteratorTag2
)
263 return _GLIBCXX_STD_A::equal(__begin1
, __end1
,
264 __begin2
, __end2
, __pred
);
267 // Parallel equal for random access iterators
268 template<typename _RAIter1
, typename _RAIter2
, typename _Predicate
>
270 __equal_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
271 _RAIter2 __begin2
, _RAIter2 __end2
, _Predicate __pred
,
272 random_access_iterator_tag
, random_access_iterator_tag
)
274 if (_GLIBCXX_PARALLEL_CONDITION(true))
276 if (std::distance(__begin1
, __end1
)
277 != std::distance(__begin2
, __end2
))
280 return __gnu_parallel::mismatch(__begin1
, __end1
, __begin2
, __end2
,
281 __pred
).first
== __end1
;
284 return _GLIBCXX_STD_A::equal(__begin1
, __end1
,
285 __begin2
, __end2
, __pred
);
288 template<typename _IIter1
, typename _IIter2
>
290 equal(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
, _IIter2 __end2
)
292 typedef __gnu_parallel::_EqualTo
<
293 typename
std::iterator_traits
<_IIter1
>::value_type
,
294 typename
std::iterator_traits
<_IIter2
>::value_type
> _EqualTo
;
296 return __equal_switch(__begin1
, __end1
, __begin2
, __end2
, _EqualTo(),
297 std::__iterator_category(__begin1
),
298 std::__iterator_category(__begin2
));
301 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
303 equal(_IIter1 __begin1
, _IIter1 __end1
,
304 _IIter2 __begin2
, _IIter2 __end2
, _BinaryPredicate __binary_pred
)
306 return __equal_switch(__begin1
, __end1
, __begin2
, __end2
, __binary_pred
,
307 std::__iterator_category(__begin1
),
308 std::__iterator_category(__begin2
));
312 // Sequential fallback
313 template<typename _IIter1
, typename _IIter2
>
315 lexicographical_compare(_IIter1 __begin1
, _IIter1 __end1
,
316 _IIter2 __begin2
, _IIter2 __end2
,
317 __gnu_parallel::sequential_tag
)
318 { return _GLIBCXX_STD_A::lexicographical_compare(__begin1
, __end1
,
321 // Sequential fallback
322 template<typename _IIter1
, typename _IIter2
, typename _Predicate
>
324 lexicographical_compare(_IIter1 __begin1
, _IIter1 __end1
,
325 _IIter2 __begin2
, _IIter2 __end2
,
326 _Predicate __pred
, __gnu_parallel::sequential_tag
)
327 { return _GLIBCXX_STD_A::lexicographical_compare(
328 __begin1
, __end1
, __begin2
, __end2
, __pred
); }
330 // Sequential fallback for input iterator case
331 template<typename _IIter1
, typename _IIter2
,
332 typename _Predicate
, typename _IteratorTag1
, typename _IteratorTag2
>
334 __lexicographical_compare_switch(_IIter1 __begin1
, _IIter1 __end1
,
335 _IIter2 __begin2
, _IIter2 __end2
,
337 _IteratorTag1
, _IteratorTag2
)
338 { return _GLIBCXX_STD_A::lexicographical_compare(
339 __begin1
, __end1
, __begin2
, __end2
, __pred
); }
341 // Parallel lexicographical_compare for random access iterators
342 // Limitation: Both valuetypes must be the same
343 template<typename _RAIter1
, typename _RAIter2
, typename _Predicate
>
345 __lexicographical_compare_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
346 _RAIter2 __begin2
, _RAIter2 __end2
,
348 random_access_iterator_tag
,
349 random_access_iterator_tag
)
351 if (_GLIBCXX_PARALLEL_CONDITION(true))
353 typedef iterator_traits
<_RAIter1
> _TraitsType1
;
354 typedef typename
_TraitsType1::value_type _ValueType1
;
356 typedef iterator_traits
<_RAIter2
> _TraitsType2
;
357 typedef typename
_TraitsType2::value_type _ValueType2
;
359 typedef __gnu_parallel::
360 _EqualFromLess
<_ValueType1
, _ValueType2
, _Predicate
>
361 _EqualFromLessCompare
;
363 // Longer sequence in first place.
364 if ((__end1
- __begin1
) < (__end2
- __begin2
))
366 typedef pair
<_RAIter1
, _RAIter2
> _SpotType
;
367 _SpotType __mm
= __mismatch_switch(__begin1
, __end1
, __begin2
,
368 _EqualFromLessCompare(__pred
),
369 random_access_iterator_tag(),
370 random_access_iterator_tag());
372 return (__mm
.first
== __end1
)
373 || bool(__pred(*__mm
.first
, *__mm
.second
));
377 typedef pair
<_RAIter2
, _RAIter1
> _SpotType
;
378 _SpotType __mm
= __mismatch_switch(__begin2
, __end2
, __begin1
,
379 _EqualFromLessCompare(__pred
),
380 random_access_iterator_tag(),
381 random_access_iterator_tag());
383 return (__mm
.first
!= __end2
)
384 && bool(__pred(*__mm
.second
, *__mm
.first
));
388 return _GLIBCXX_STD_A::lexicographical_compare(
389 __begin1
, __end1
, __begin2
, __end2
, __pred
);
393 template<typename _IIter1
, typename _IIter2
>
395 lexicographical_compare(_IIter1 __begin1
, _IIter1 __end1
,
396 _IIter2 __begin2
, _IIter2 __end2
)
398 typedef iterator_traits
<_IIter1
> _TraitsType1
;
399 typedef typename
_TraitsType1::value_type _ValueType1
;
400 typedef typename
_TraitsType1::iterator_category _IteratorCategory1
;
402 typedef iterator_traits
<_IIter2
> _TraitsType2
;
403 typedef typename
_TraitsType2::value_type _ValueType2
;
404 typedef typename
_TraitsType2::iterator_category _IteratorCategory2
;
405 typedef __gnu_parallel::_Less
<_ValueType1
, _ValueType2
> _LessType
;
407 return __lexicographical_compare_switch(
408 __begin1
, __end1
, __begin2
, __end2
, _LessType(),
409 _IteratorCategory1(), _IteratorCategory2());
413 template<typename _IIter1
, typename _IIter2
, typename _Predicate
>
415 lexicographical_compare(_IIter1 __begin1
, _IIter1 __end1
,
416 _IIter2 __begin2
, _IIter2 __end2
,
419 typedef iterator_traits
<_IIter1
> _TraitsType1
;
420 typedef typename
_TraitsType1::iterator_category _IteratorCategory1
;
422 typedef iterator_traits
<_IIter2
> _TraitsType2
;
423 typedef typename
_TraitsType2::iterator_category _IteratorCategory2
;
425 return __lexicographical_compare_switch(
426 __begin1
, __end1
, __begin2
, __end2
, __pred
,
427 _IteratorCategory1(), _IteratorCategory2());
432 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */