libstdc++
algobase.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009 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>
45 
46 namespace std
47 {
48 namespace __parallel
49 {
50  // NB: equal and lexicographical_compare require mismatch.
51 
52  // Sequential fallback
53  template<typename InputIterator1, typename InputIterator2>
54  inline pair<InputIterator1, InputIterator2>
55  mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
57  { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); }
58 
59  // Sequential fallback
60  template<typename InputIterator1, typename InputIterator2,
61  typename Predicate>
62  inline pair<InputIterator1, InputIterator2>
63  mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
64  Predicate pred, __gnu_parallel::sequential_tag)
65  { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
66 
67  // Sequential fallback for input iterator case
68  template<typename InputIterator1, typename InputIterator2,
69  typename Predicate, typename IteratorTag1, typename IteratorTag2>
70  inline pair<InputIterator1, InputIterator2>
71  mismatch_switch(InputIterator1 begin1, InputIterator1 end1,
72  InputIterator2 begin2, Predicate pred, IteratorTag1,
73  IteratorTag2)
74  { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); }
75 
76  // Parallel mismatch for random access iterators
77  template<typename RandomAccessIterator1, typename RandomAccessIterator2,
78  typename Predicate>
79  pair<RandomAccessIterator1, RandomAccessIterator2>
80  mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
81  RandomAccessIterator2 begin2, Predicate pred,
82  random_access_iterator_tag, random_access_iterator_tag)
83  {
85  {
86  RandomAccessIterator1 res =
87  __gnu_parallel::find_template(begin1, end1, begin2, pred,
88  __gnu_parallel::
89  mismatch_selector()).first;
90  return make_pair(res , begin2 + (res - begin1));
91  }
92  else
93  return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred);
94  }
95 
96  // Public interface
97  template<typename InputIterator1, typename InputIterator2>
98  inline pair<InputIterator1, InputIterator2>
99  mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
100  {
101  typedef std::iterator_traits<InputIterator1> iterator1_traits;
102  typedef std::iterator_traits<InputIterator2> iterator2_traits;
103  typedef typename iterator1_traits::value_type value1_type;
104  typedef typename iterator2_traits::value_type value2_type;
105  typedef typename iterator1_traits::iterator_category iterator1_category;
106  typedef typename iterator2_traits::iterator_category iterator2_category;
107 
109 
110  return mismatch_switch(begin1, end1, begin2, equal_to_type(),
111  iterator1_category(), iterator2_category());
112  }
113 
114  // Public interface
115  template<typename InputIterator1, typename InputIterator2,
116  typename Predicate>
117  inline pair<InputIterator1, InputIterator2>
118  mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
119  Predicate pred)
120  {
121  typedef std::iterator_traits<InputIterator1> iterator1_traits;
122  typedef std::iterator_traits<InputIterator2> iterator2_traits;
123  typedef typename iterator1_traits::iterator_category iterator1_category;
124  typedef typename iterator2_traits::iterator_category iterator2_category;
125 
126  return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(),
127  iterator2_category());
128  }
129 
130  // Sequential fallback
131  template<typename InputIterator1, typename InputIterator2>
132  inline bool
133  equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
135  { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); }
136 
137  // Sequential fallback
138  template<typename InputIterator1, typename InputIterator2,
139  typename Predicate>
140  inline bool
141  equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
142  Predicate pred, __gnu_parallel::sequential_tag)
143  { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); }
144 
145  // Public interface
146  template<typename InputIterator1, typename InputIterator2>
147  inline bool
148  equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
149  { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2).first == end1; }
150 
151  // Public interface
152  template<typename InputIterator1, typename InputIterator2,
153  typename Predicate>
154  inline bool
155  equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
156  Predicate pred)
157  {
158  return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred).first
159  == end1;
160  }
161 
162  // Sequential fallback
163  template<typename InputIterator1, typename InputIterator2>
164  inline bool
165  lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
166  InputIterator2 begin2, InputIterator2 end2,
168  { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
169  begin2, end2); }
170 
171  // Sequential fallback
172  template<typename InputIterator1, typename InputIterator2,
173  typename Predicate>
174  inline bool
175  lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
176  InputIterator2 begin2, InputIterator2 end2,
177  Predicate pred, __gnu_parallel::sequential_tag)
178  { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
179  begin2, end2, pred); }
180 
181  // Sequential fallback for input iterator case
182  template<typename InputIterator1, typename InputIterator2,
183  typename Predicate, typename IteratorTag1, typename IteratorTag2>
184  inline bool
185  lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1,
186  InputIterator2 begin2, InputIterator2 end2,
187  Predicate pred, IteratorTag1, IteratorTag2)
188  { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
189  begin2, end2, pred); }
190 
191  // Parallel lexicographical_compare for random access iterators
192  // Limitation: Both valuetypes must be the same
193  template<typename RandomAccessIterator1, typename RandomAccessIterator2,
194  typename Predicate>
195  bool
196  lexicographical_compare_switch(RandomAccessIterator1 begin1,
197  RandomAccessIterator1 end1,
198  RandomAccessIterator2 begin2,
199  RandomAccessIterator2 end2, Predicate pred,
200  random_access_iterator_tag,
201  random_access_iterator_tag)
202  {
203  if (_GLIBCXX_PARALLEL_CONDITION(true))
204  {
205  typedef iterator_traits<RandomAccessIterator1> traits1_type;
206  typedef typename traits1_type::value_type value1_type;
207 
208  typedef iterator_traits<RandomAccessIterator2> traits2_type;
209  typedef typename traits2_type::value_type value2_type;
210 
211  typedef __gnu_parallel::equal_from_less<Predicate, value1_type,
212  value2_type> equal_type;
213 
214  // Longer sequence in first place.
215  if ((end1 - begin1) < (end2 - begin2))
216  {
217  typedef pair<RandomAccessIterator1, RandomAccessIterator2>
218  pair_type;
219  pair_type mm = mismatch_switch(begin1, end1, begin2,
220  equal_type(pred),
221  random_access_iterator_tag(),
222  random_access_iterator_tag());
223 
224  return (mm.first == end1) || bool(pred(*mm.first, *mm.second));
225  }
226  else
227  {
228  typedef pair<RandomAccessIterator2, RandomAccessIterator1>
229  pair_type;
230  pair_type mm = mismatch_switch(begin2, end2, begin1,
231  equal_type(pred),
232  random_access_iterator_tag(),
233  random_access_iterator_tag());
234 
235  return (mm.first != end2) && bool(pred(*mm.second, *mm.first));
236  }
237  }
238  else
239  return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1,
240  begin2, end2, pred);
241  }
242 
243  // Public interface
244  template<typename InputIterator1, typename InputIterator2>
245  inline bool
246  lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
247  InputIterator2 begin2, InputIterator2 end2)
248  {
249  typedef iterator_traits<InputIterator1> traits1_type;
250  typedef typename traits1_type::value_type value1_type;
251  typedef typename traits1_type::iterator_category iterator1_category;
252 
253  typedef iterator_traits<InputIterator2> traits2_type;
254  typedef typename traits2_type::value_type value2_type;
255  typedef typename traits2_type::iterator_category iterator2_category;
257 
258  return lexicographical_compare_switch(begin1, end1, begin2, end2,
259  less_type(), iterator1_category(),
260  iterator2_category());
261  }
262 
263  // Public interface
264  template<typename InputIterator1, typename InputIterator2,
265  typename Predicate>
266  inline bool
267  lexicographical_compare(InputIterator1 begin1, InputIterator1 end1,
268  InputIterator2 begin2, InputIterator2 end2,
269  Predicate pred)
270  {
271  typedef iterator_traits<InputIterator1> traits1_type;
272  typedef typename traits1_type::iterator_category iterator1_category;
273 
274  typedef iterator_traits<InputIterator2> traits2_type;
275  typedef typename traits2_type::iterator_category iterator2_category;
276 
277  return lexicographical_compare_switch(begin1, end1, begin2, end2, pred,
278  iterator1_category(),
279  iterator2_category());
280  }
281 } // end namespace
282 } // end namespace
283 
284 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */
Constructs predicate for equality from strict weak ordering predicate.
Definition: base.h:159
#define _GLIBCXX_PARALLEL_CONDITION(c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:95
Runtime settings and tuning parameters, heuristics to decide whether to use parallelized algorithms...
Forces sequential execution at compile time.
Definition: tags.h:42
Similar to std::equal_to, but allows two different types.
Definition: base.h:250
Similar to std::less, but allows two different types.
Definition: base.h:258
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library...
Function objects representing different tasks to be plugged into the parallel find algorithm...
Tags for compile-time selection. This file is a GNU parallel extension to the Standard C++ Library...
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
std::pair< RandomAccessIterator1, RandomAccessIterator2 > find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector)
Parallel std::find, switch for different algorithms.
Definition: find.h:60