libstdc++
algobase.h
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2007-2022 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the terms
7// of the GNU General Public License as published by the Free Software
8// Foundation; either version 3, or (at your option) any later
9// version.
10
11// This library is distributed in the hope that it will be useful, but
12// WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14// General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file parallel/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.
32 */
33
34// Written by Johannes Singler and Felix Putze.
35
36#ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
37#define _GLIBCXX_PARALLEL_ALGOBASE_H 1
38
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>
44
45namespace std _GLIBCXX_VISIBILITY(default)
46{
47namespace __parallel
48{
49 // NB: equal and lexicographical_compare require mismatch.
50
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); }
57
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); }
64
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); }
72
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)
79 {
80 if (_GLIBCXX_PARALLEL_CONDITION(true))
81 {
82 _RAIter1 __res =
83 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
84 __gnu_parallel::
85 __mismatch_selector()).first;
86 return make_pair(__res , __begin2 + (__res - __begin1));
87 }
88 else
89 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred);
90 }
91
92 // Public interface
93 template<typename _IIter1, typename _IIter2>
94 inline pair<_IIter1, _IIter2>
95 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
96 {
97 typedef __gnu_parallel::_EqualTo<
98 typename std::iterator_traits<_IIter1>::value_type,
99 typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
100
101 return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
102 std::__iterator_category(__begin1),
103 std::__iterator_category(__begin2));
104 }
105
106 // Public interface
107 template<typename _IIter1, typename _IIter2, typename _Predicate>
108 inline pair<_IIter1, _IIter2>
109 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
110 _Predicate __pred)
111 {
112 return __mismatch_switch(__begin1, __end1, __begin2, __pred,
113 std::__iterator_category(__begin1),
114 std::__iterator_category(__begin2));
115 }
116
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); }
125
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)
134 {
135 return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2,
136 __binary_pred);
137 }
138
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)
146 {
147 return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
148 __begin2, __end2, __pred);
149 }
150
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)
157 {
158 if (_GLIBCXX_PARALLEL_CONDITION(true))
159 {
160 if ((__end2 - __begin2) < (__end1 - __begin1))
161 __end1 = __begin1 + (__end2 - __begin2);
162
163 _RAIter1 __res =
164 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
165 __gnu_parallel::
166 __mismatch_selector()).first;
167 return make_pair(__res , __begin2 + (__res - __begin1));
168 }
169 else
170 return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
171 __begin2, __end2, __pred);
172 }
173
174 template<typename _IIter1, typename _IIter2>
175 inline pair<_IIter1, _IIter2>
176 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
177 {
178 typedef __gnu_parallel::_EqualTo<
179 typename std::iterator_traits<_IIter1>::value_type,
180 typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
181
182 return __mismatch_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
183 std::__iterator_category(__begin1),
184 std::__iterator_category(__begin2));
185 }
186
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)
193 {
194 return __mismatch_switch(__begin1, __end1, __begin2, __end2,
195 __binary_pred,
196 std::__iterator_category(__begin1),
197 std::__iterator_category(__begin2));
198 }
199#endif
200
201 // Sequential fallback
202 template<typename _IIter1, typename _IIter2>
203 inline bool
204 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
205 __gnu_parallel::sequential_tag)
206 { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); }
207
208 // Sequential fallback
209 template<typename _IIter1, typename _IIter2, typename _Predicate>
210 inline bool
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); }
214
215 // Public interface
216 template<typename _IIter1, typename _IIter2>
217 _GLIBCXX20_CONSTEXPR
218 inline bool
219 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
220 {
221#if __cplusplus > 201703L
222 if (std::is_constant_evaluated())
223 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2);
224#endif
225
226 return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
227 == __end1;
228 }
229
230 // Public interface
231 template<typename _IIter1, typename _IIter2, typename _Predicate>
232 _GLIBCXX20_CONSTEXPR
233 inline bool
234 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
235 _Predicate __pred)
236 {
237#if __cplusplus > 201703L
238 if (std::is_constant_evaluated())
239 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred);
240#endif
241
242 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
243 == __end1;
244 }
245
246#if __cplusplus > 201103L
247 // Sequential fallback
248 template<typename _IIter1, typename _IIter2>
249 inline bool
250 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
251 __gnu_parallel::sequential_tag)
252 {
253 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
254 }
255
256 // Sequential fallback
257 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
258 inline bool
259 equal(_IIter1 __begin1, _IIter1 __end1,
260 _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred,
261 __gnu_parallel::sequential_tag)
262 {
263 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
264 __binary_pred);
265 }
266
267 // Sequential fallback for input iterator case
268 template<typename _IIter1, typename _IIter2,
269 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
270 inline bool
271 __equal_switch(_IIter1 __begin1, _IIter1 __end1,
272 _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
273 _IteratorTag1, _IteratorTag2)
274 {
275 return _GLIBCXX_STD_A::equal(__begin1, __end1,
276 __begin2, __end2, __pred);
277 }
278
279 // Parallel equal for random access iterators
280 template<typename _RAIter1, typename _RAIter2, typename _Predicate>
281 inline bool
282 __equal_switch(_RAIter1 __begin1, _RAIter1 __end1,
283 _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred,
284 random_access_iterator_tag, random_access_iterator_tag)
285 {
286 if (_GLIBCXX_PARALLEL_CONDITION(true))
287 {
288 if (std::distance(__begin1, __end1)
289 != std::distance(__begin2, __end2))
290 return false;
291
292 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2,
293 __pred).first == __end1;
294 }
295 else
296 return _GLIBCXX_STD_A::equal(__begin1, __end1,
297 __begin2, __end2, __pred);
298 }
299
300 template<typename _IIter1, typename _IIter2>
301 _GLIBCXX20_CONSTEXPR
302 inline bool
303 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
304 {
305#if __cplusplus > 201703L
306 if (std::is_constant_evaluated())
307 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
308#endif
309
310 typedef __gnu_parallel::_EqualTo<
311 typename std::iterator_traits<_IIter1>::value_type,
312 typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
313
314 return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
315 std::__iterator_category(__begin1),
316 std::__iterator_category(__begin2));
317 }
318
319 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
320 _GLIBCXX20_CONSTEXPR
321 inline bool
322 equal(_IIter1 __begin1, _IIter1 __end1,
323 _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred)
324 {
325#if __cplusplus > 201703L
326 if (std::is_constant_evaluated())
327 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
328 __binary_pred);
329#endif
330
331 return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred,
332 std::__iterator_category(__begin1),
333 std::__iterator_category(__begin2));
334 }
335#endif // C++14
336
337 // Sequential fallback
338 template<typename _IIter1, typename _IIter2>
339 inline bool
340 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
341 _IIter2 __begin2, _IIter2 __end2,
342 __gnu_parallel::sequential_tag)
343 { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
344 __begin2, __end2); }
345
346 // Sequential fallback
347 template<typename _IIter1, typename _IIter2, typename _Predicate>
348 inline bool
349 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
350 _IIter2 __begin2, _IIter2 __end2,
351 _Predicate __pred, __gnu_parallel::sequential_tag)
352 { return _GLIBCXX_STD_A::lexicographical_compare(
353 __begin1, __end1, __begin2, __end2, __pred); }
354
355 // Sequential fallback for input iterator case
356 template<typename _IIter1, typename _IIter2,
357 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
358 inline bool
359 __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
360 _IIter2 __begin2, _IIter2 __end2,
361 _Predicate __pred,
362 _IteratorTag1, _IteratorTag2)
363 { return _GLIBCXX_STD_A::lexicographical_compare(
364 __begin1, __end1, __begin2, __end2, __pred); }
365
366 // Parallel lexicographical_compare for random access iterators
367 // Limitation: Both valuetypes must be the same
368 template<typename _RAIter1, typename _RAIter2, typename _Predicate>
369 bool
370 __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
371 _RAIter2 __begin2, _RAIter2 __end2,
372 _Predicate __pred,
373 random_access_iterator_tag,
374 random_access_iterator_tag)
375 {
376 if (_GLIBCXX_PARALLEL_CONDITION(true))
377 {
378 typedef iterator_traits<_RAIter1> _TraitsType1;
379 typedef typename _TraitsType1::value_type _ValueType1;
380
381 typedef iterator_traits<_RAIter2> _TraitsType2;
382 typedef typename _TraitsType2::value_type _ValueType2;
383
384 typedef __gnu_parallel::
385 _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
386 _EqualFromLessCompare;
387
388 // Longer sequence in first place.
389 if ((__end1 - __begin1) < (__end2 - __begin2))
390 {
391 typedef pair<_RAIter1, _RAIter2> _SpotType;
392 _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2,
393 _EqualFromLessCompare(__pred),
394 random_access_iterator_tag(),
395 random_access_iterator_tag());
396
397 return (__mm.first == __end1)
398 || bool(__pred(*__mm.first, *__mm.second));
399 }
400 else
401 {
402 typedef pair<_RAIter2, _RAIter1> _SpotType;
403 _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1,
404 _EqualFromLessCompare(__pred),
405 random_access_iterator_tag(),
406 random_access_iterator_tag());
407
408 return (__mm.first != __end2)
409 && bool(__pred(*__mm.second, *__mm.first));
410 }
411 }
412 else
413 return _GLIBCXX_STD_A::lexicographical_compare(
414 __begin1, __end1, __begin2, __end2, __pred);
415 }
416
417 // Public interface
418 template<typename _IIter1, typename _IIter2>
419 _GLIBCXX20_CONSTEXPR
420 inline bool
421 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
422 _IIter2 __begin2, _IIter2 __end2)
423 {
424#if __cplusplus > 201703L
425 if (std::is_constant_evaluated())
426 return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
427 __begin2, __end2);
428#endif
429
430 typedef iterator_traits<_IIter1> _TraitsType1;
431 typedef typename _TraitsType1::value_type _ValueType1;
432 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
433
434 typedef iterator_traits<_IIter2> _TraitsType2;
435 typedef typename _TraitsType2::value_type _ValueType2;
436 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
437 typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
438
439 return __lexicographical_compare_switch(
440 __begin1, __end1, __begin2, __end2, _LessType(),
441 _IteratorCategory1(), _IteratorCategory2());
442 }
443
444 // Public interface
445 template<typename _IIter1, typename _IIter2, typename _Predicate>
446 _GLIBCXX20_CONSTEXPR
447 inline bool
448 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
449 _IIter2 __begin2, _IIter2 __end2,
450 _Predicate __pred)
451 {
452#if __cplusplus > 201703L
453 if (std::is_constant_evaluated())
454 return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
455 __begin2, __end2,
456 __pred);
457#endif
458
459 typedef iterator_traits<_IIter1> _TraitsType1;
460 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
461
462 typedef iterator_traits<_IIter2> _TraitsType2;
463 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
464
465 return __lexicographical_compare_switch(
466 __begin1, __end1, __begin2, __end2, __pred,
467 _IteratorCategory1(), _IteratorCategory2());
468 }
469
470#if __cpp_lib_three_way_comparison
471 using _GLIBCXX_STD_A::lexicographical_compare_three_way;
472#endif
473} // end namespace
474} // end namespace
475
476#endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */
_GLIBCXX_PARALLEL_CONDITION
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:94
find_selectors.h
_Function objects representing different tasks to be plugged into the parallel find algorithm....
find.h
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
base.h
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library.
std::is_constant_evaluated
constexpr bool is_constant_evaluated() noexcept
Returns true only when called during constant evaluation.
Definition: type_traits:3520
std::__iterator_category
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Definition: stl_iterator_base_types.h:238
std
ISO C++ entities toplevel namespace is std.
std::distance
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:147
__gnu_parallel
GNU parallel code for public use.
Definition: balanced_quicksort.h:62
__gnu_parallel::__find_template
std::pair< _RAIter1, _RAIter2 > __find_template(_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector)
Parallel std::find, switch for different algorithms.
Definition: find.h:60
std::iterator_traits
Traits class for iterators.
Definition: stl_iterator_base_types.h:178
__gnu_parallel::_EqualTo
Similar to std::equal_to, but allows two different types.
Definition: base.h:245
__gnu_parallel::_Less
Similar to std::less, but allows two different types.
Definition: base.h:253
__gnu_parallel::sequential_tag
Forces sequential execution at compile time.
Definition: tags.h:42