libstdc++
algobase.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2018 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  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,
239  __gnu_parallel::sequential_tag)
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,
249  __gnu_parallel::sequential_tag)
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  {
274  if (_GLIBCXX_PARALLEL_CONDITION(true))
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  {
292  typedef __gnu_parallel::_EqualTo<
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,
317  __gnu_parallel::sequential_tag)
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  {
351  if (_GLIBCXX_PARALLEL_CONDITION(true))
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;
405  typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
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 */
__gnu_parallel::sequential_tag
Forces sequential execution at compile time.
Definition: tags.h:42
__gnu_parallel::_EqualTo
Similar to std::equal_to, but allows two different types.
Definition: parallel/base.h:244
find_selectors.h
_Function objects representing different tasks to be plugged into the parallel find algorithm....
std::distance
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:138
_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:95
std::make_pair
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
find.h
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
std
ISO C++ entities toplevel namespace is std.
base.h
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library.
__gnu_parallel
GNU parallel code for public use.
Definition: balanced_quicksort.h:61
std::__iterator_category
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Definition: stl_iterator_base_types.h:205
__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
__gnu_parallel::_Less
Similar to std::less, but allows two different types.
Definition: parallel/base.h:252