libstdc++
algobase.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2020 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 
45 namespace std _GLIBCXX_VISIBILITY(default)
46 {
47 namespace __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 } // end namespace
470 } // end namespace
471 
472 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */
base.h
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library.
find.h
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
find_selectors.h
_Function objects representing different tasks to be plugged into the parallel find algorithm....
_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
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:138
__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