libstdc++
algobase.h
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2007-2019 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>
42#include <parallel/find.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,
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 {
81 {
82 _RAIter1 __res =
83 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
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 {
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,
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,
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 {
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,
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 {
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,
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 inline bool
218 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
219 {
220 return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
221 == __end1;
222 }
223
224 // Public interface
225 template<typename _IIter1, typename _IIter2, typename _Predicate>
226 inline bool
227 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
228 _Predicate __pred)
229 {
230 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
231 == __end1;
232 }
233
234#if __cplusplus > 201103L
235 // Sequential fallback
236 template<typename _IIter1, typename _IIter2>
237 inline bool
238 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
240 {
241 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
242 }
243
244 // Sequential fallback
245 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
246 inline bool
247 equal(_IIter1 __begin1, _IIter1 __end1,
248 _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred,
250 {
251 return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
252 __binary_pred);
253 }
254
255 // Sequential fallback for input iterator case
256 template<typename _IIter1, typename _IIter2,
257 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
258 inline bool
259 __equal_switch(_IIter1 __begin1, _IIter1 __end1,
260 _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
261 _IteratorTag1, _IteratorTag2)
262 {
263 return _GLIBCXX_STD_A::equal(__begin1, __end1,
264 __begin2, __end2, __pred);
265 }
266
267 // Parallel equal for random access iterators
268 template<typename _RAIter1, typename _RAIter2, typename _Predicate>
269 inline bool
270 __equal_switch(_RAIter1 __begin1, _RAIter1 __end1,
271 _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred,
272 random_access_iterator_tag, random_access_iterator_tag)
273 {
275 {
276 if (std::distance(__begin1, __end1)
277 != std::distance(__begin2, __end2))
278 return false;
279
280 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2,
281 __pred).first == __end1;
282 }
283 else
284 return _GLIBCXX_STD_A::equal(__begin1, __end1,
285 __begin2, __end2, __pred);
286 }
287
288 template<typename _IIter1, typename _IIter2>
289 inline bool
290 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
291 {
293 typename std::iterator_traits<_IIter1>::value_type,
294 typename std::iterator_traits<_IIter2>::value_type> _EqualTo;
295
296 return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
297 std::__iterator_category(__begin1),
298 std::__iterator_category(__begin2));
299 }
300
301 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
302 inline bool
303 equal(_IIter1 __begin1, _IIter1 __end1,
304 _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred)
305 {
306 return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred,
307 std::__iterator_category(__begin1),
308 std::__iterator_category(__begin2));
309 }
310#endif
311
312 // Sequential fallback
313 template<typename _IIter1, typename _IIter2>
314 inline bool
315 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
316 _IIter2 __begin2, _IIter2 __end2,
318 { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
319 __begin2, __end2); }
320
321 // Sequential fallback
322 template<typename _IIter1, typename _IIter2, typename _Predicate>
323 inline bool
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); }
329
330 // Sequential fallback for input iterator case
331 template<typename _IIter1, typename _IIter2,
332 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
333 inline bool
334 __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
335 _IIter2 __begin2, _IIter2 __end2,
336 _Predicate __pred,
337 _IteratorTag1, _IteratorTag2)
338 { return _GLIBCXX_STD_A::lexicographical_compare(
339 __begin1, __end1, __begin2, __end2, __pred); }
340
341 // Parallel lexicographical_compare for random access iterators
342 // Limitation: Both valuetypes must be the same
343 template<typename _RAIter1, typename _RAIter2, typename _Predicate>
344 bool
345 __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
346 _RAIter2 __begin2, _RAIter2 __end2,
347 _Predicate __pred,
348 random_access_iterator_tag,
349 random_access_iterator_tag)
350 {
352 {
353 typedef iterator_traits<_RAIter1> _TraitsType1;
354 typedef typename _TraitsType1::value_type _ValueType1;
355
356 typedef iterator_traits<_RAIter2> _TraitsType2;
357 typedef typename _TraitsType2::value_type _ValueType2;
358
359 typedef __gnu_parallel::
360 _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
361 _EqualFromLessCompare;
362
363 // Longer sequence in first place.
364 if ((__end1 - __begin1) < (__end2 - __begin2))
365 {
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());
371
372 return (__mm.first == __end1)
373 || bool(__pred(*__mm.first, *__mm.second));
374 }
375 else
376 {
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());
382
383 return (__mm.first != __end2)
384 && bool(__pred(*__mm.second, *__mm.first));
385 }
386 }
387 else
388 return _GLIBCXX_STD_A::lexicographical_compare(
389 __begin1, __end1, __begin2, __end2, __pred);
390 }
391
392 // Public interface
393 template<typename _IIter1, typename _IIter2>
394 inline bool
395 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
396 _IIter2 __begin2, _IIter2 __end2)
397 {
398 typedef iterator_traits<_IIter1> _TraitsType1;
399 typedef typename _TraitsType1::value_type _ValueType1;
400 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
401
402 typedef iterator_traits<_IIter2> _TraitsType2;
403 typedef typename _TraitsType2::value_type _ValueType2;
404 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
406
407 return __lexicographical_compare_switch(
408 __begin1, __end1, __begin2, __end2, _LessType(),
409 _IteratorCategory1(), _IteratorCategory2());
410 }
411
412 // Public interface
413 template<typename _IIter1, typename _IIter2, typename _Predicate>
414 inline bool
415 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
416 _IIter2 __begin2, _IIter2 __end2,
417 _Predicate __pred)
418 {
419 typedef iterator_traits<_IIter1> _TraitsType1;
420 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
421
422 typedef iterator_traits<_IIter2> _TraitsType2;
423 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
424
425 return __lexicographical_compare_switch(
426 __begin1, __end1, __begin2, __end2, __pred,
427 _IteratorCategory1(), _IteratorCategory2());
428 }
429} // end namespace
430} // end namespace
431
432#endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:95
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
_Function objects representing different tasks to be plugged into the parallel find algorithm....
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:524
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
GNU parallel code for public use.
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
Similar to std::equal_to, but allows two different types.
Similar to std::less, but allows two different types.
Forces sequential execution at compile time.
Definition: tags.h:42
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library.