libstdc++
algobase.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009, 2010 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/tags.h>
42 #include <parallel/settings.h>
43 #include <parallel/find.h>
44 #include <parallel/find_selectors.h>
45 
46 namespace std _GLIBCXX_VISIBILITY(default)
47 {
48 namespace __parallel
49 {
50  // NB: equal and lexicographical_compare require mismatch.
51 
52  // Sequential fallback
53  template<typename _IIter1, typename _IIter2>
54  inline pair<_IIter1, _IIter2>
55  mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
56  __gnu_parallel::sequential_tag)
57  { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2); }
58 
59  // Sequential fallback
60  template<typename _IIter1, typename _IIter2, typename _Predicate>
61  inline pair<_IIter1, _IIter2>
62  mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
63  _Predicate __pred, __gnu_parallel::sequential_tag)
64  { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); }
65 
66  // Sequential fallback for input iterator case
67  template<typename _IIter1, typename _IIter2,
68  typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
69  inline pair<_IIter1, _IIter2>
70  __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
71  _Predicate __pred, _IteratorTag1, _IteratorTag2)
72  { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); }
73 
74  // Parallel mismatch for random access iterators
75  template<typename _RAIter1, typename _RAIter2, typename _Predicate>
76  pair<_RAIter1, _RAIter2>
77  __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
78  _RAIter2 __begin2, _Predicate __pred,
79  random_access_iterator_tag, random_access_iterator_tag)
80  {
81  if (_GLIBCXX_PARALLEL_CONDITION(true))
82  {
83  _RAIter1 __res =
84  __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
85  __gnu_parallel::
86  __mismatch_selector()).first;
87  return make_pair(__res , __begin2 + (__res - __begin1));
88  }
89  else
90  return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred);
91  }
92 
93  // Public interface
94  template<typename _IIter1, typename _IIter2>
95  inline pair<_IIter1, _IIter2>
96  mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
97  {
98  typedef std::iterator_traits<_IIter1> _Iterator1Traits;
99  typedef std::iterator_traits<_IIter2> _Iterator2Traits;
100  typedef typename _Iterator1Traits::value_type _ValueType1;
101  typedef typename _Iterator2Traits::value_type _ValueType2;
102  typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
103  typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
104 
105  typedef __gnu_parallel::_EqualTo<_ValueType1, _ValueType2> _EqualTo;
106 
107  return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
108  _IteratorCategory1(), _IteratorCategory2());
109  }
110 
111  // Public interface
112  template<typename _IIter1, typename _IIter2, typename _Predicate>
113  inline pair<_IIter1, _IIter2>
114  mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
115  _Predicate __pred)
116  {
117  typedef std::iterator_traits<_IIter1> _Iterator1Traits;
118  typedef std::iterator_traits<_IIter2> _Iterator2Traits;
119  typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
120  typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
121 
122  return __mismatch_switch(__begin1, __end1, __begin2, __pred,
123  _IteratorCategory1(), _IteratorCategory2());
124  }
125 
126  // Sequential fallback
127  template<typename _IIter1, typename _IIter2>
128  inline bool
129  equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
130  __gnu_parallel::sequential_tag)
131  { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); }
132 
133  // Sequential fallback
134  template<typename _IIter1, typename _IIter2, typename _Predicate>
135  inline bool
136  equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
137  _Predicate __pred, __gnu_parallel::sequential_tag)
138  { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); }
139 
140  // Public interface
141  template<typename _IIter1, typename _IIter2>
142  inline bool
143  equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
144  {
145  return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
146  == __end1;
147  }
148 
149  // Public interface
150  template<typename _IIter1, typename _IIter2, typename _Predicate>
151  inline bool
152  equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
153  _Predicate __pred)
154  {
155  return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
156  == __end1;
157  }
158 
159  // Sequential fallback
160  template<typename _IIter1, typename _IIter2>
161  inline bool
162  lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
163  _IIter2 __begin2, _IIter2 __end2,
164  __gnu_parallel::sequential_tag)
165  { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
166  __begin2, __end2); }
167 
168  // Sequential fallback
169  template<typename _IIter1, typename _IIter2, typename _Predicate>
170  inline bool
171  lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
172  _IIter2 __begin2, _IIter2 __end2,
173  _Predicate __pred, __gnu_parallel::sequential_tag)
174  { return _GLIBCXX_STD_A::lexicographical_compare(
175  __begin1, __end1, __begin2, __end2, __pred); }
176 
177  // Sequential fallback for input iterator case
178  template<typename _IIter1, typename _IIter2,
179  typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
180  inline bool
181  __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
182  _IIter2 __begin2, _IIter2 __end2,
183  _Predicate __pred,
184  _IteratorTag1, _IteratorTag2)
185  { return _GLIBCXX_STD_A::lexicographical_compare(
186  __begin1, __end1, __begin2, __end2, __pred); }
187 
188  // Parallel lexicographical_compare for random access iterators
189  // Limitation: Both valuetypes must be the same
190  template<typename _RAIter1, typename _RAIter2, typename _Predicate>
191  bool
192  __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
193  _RAIter2 __begin2, _RAIter2 __end2,
194  _Predicate __pred,
195  random_access_iterator_tag,
196  random_access_iterator_tag)
197  {
198  if (_GLIBCXX_PARALLEL_CONDITION(true))
199  {
200  typedef iterator_traits<_RAIter1> _TraitsType1;
201  typedef typename _TraitsType1::value_type _ValueType1;
202 
203  typedef iterator_traits<_RAIter2> _TraitsType2;
204  typedef typename _TraitsType2::value_type _ValueType2;
205 
206  typedef __gnu_parallel::
207  _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
208  _EqualFromLessCompare;
209 
210  // Longer sequence in first place.
211  if ((__end1 - __begin1) < (__end2 - __begin2))
212  {
213  typedef pair<_RAIter1, _RAIter2> _SpotType;
214  _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2,
215  _EqualFromLessCompare(__pred),
216  random_access_iterator_tag(),
217  random_access_iterator_tag());
218 
219  return (__mm.first == __end1)
220  || bool(__pred(*__mm.first, *__mm.second));
221  }
222  else
223  {
224  typedef pair<_RAIter2, _RAIter1> _SpotType;
225  _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1,
226  _EqualFromLessCompare(__pred),
227  random_access_iterator_tag(),
228  random_access_iterator_tag());
229 
230  return (__mm.first != __end2)
231  && bool(__pred(*__mm.second, *__mm.first));
232  }
233  }
234  else
235  return _GLIBCXX_STD_A::lexicographical_compare(
236  __begin1, __end1, __begin2, __end2, __pred);
237  }
238 
239  // Public interface
240  template<typename _IIter1, typename _IIter2>
241  inline bool
242  lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
243  _IIter2 __begin2, _IIter2 __end2)
244  {
245  typedef iterator_traits<_IIter1> _TraitsType1;
246  typedef typename _TraitsType1::value_type _ValueType1;
247  typedef typename _TraitsType1::iterator_category _IteratorCategory1;
248 
249  typedef iterator_traits<_IIter2> _TraitsType2;
250  typedef typename _TraitsType2::value_type _ValueType2;
251  typedef typename _TraitsType2::iterator_category _IteratorCategory2;
252  typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
253 
254  return __lexicographical_compare_switch(
255  __begin1, __end1, __begin2, __end2, _LessType(),
256  _IteratorCategory1(), _IteratorCategory2());
257  }
258 
259  // Public interface
260  template<typename _IIter1, typename _IIter2, typename _Predicate>
261  inline bool
262  lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
263  _IIter2 __begin2, _IIter2 __end2,
264  _Predicate __pred)
265  {
266  typedef iterator_traits<_IIter1> _TraitsType1;
267  typedef typename _TraitsType1::iterator_category _IteratorCategory1;
268 
269  typedef iterator_traits<_IIter2> _TraitsType2;
270  typedef typename _TraitsType2::iterator_category _IteratorCategory2;
271 
272  return __lexicographical_compare_switch(
273  __begin1, __end1, __begin2, __end2, __pred,
274  _IteratorCategory1(), _IteratorCategory2());
275  }
276 } // end namespace
277 } // end namespace
278 
279 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */