]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
531898c3 | 3 | // Copyright (C) 2007, 2008 Free Software Foundation, Inc. |
c2ba9709 JS |
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 2, 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 | // You should have received a copy of the GNU General Public License | |
17 | // along with this library; see the file COPYING. If not, write to | |
18 | // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, | |
19 | // MA 02111-1307, USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free | |
22 | // software library without restriction. Specifically, if other files | |
23 | // instantiate templates or use macros or inline functions from this | |
24 | // file, or you compile this file and link it with other files to | |
25 | // produce an executable, this file does not by itself cause the | |
26 | // resulting executable to be covered by the GNU General Public | |
27 | // License. This exception does not however invalidate any other | |
28 | // reasons why the executable file might be covered by the GNU General | |
29 | // Public License. | |
30 | ||
31 | /** @file parallel/algobase.h | |
32 | * @brief Parallel STL function calls corresponding to the | |
33 | * stl_algobase.h header. The functions defined here mainly do case | |
34 | * switches and call the actual parallelized versions in other files. | |
35 | * Inlining policy: Functions that basically only contain one | |
36 | * function call, are declared inline. | |
37 | * This file is a GNU parallel extension to the Standard C++ Library. | |
38 | */ | |
39 | ||
40 | // Written by Johannes Singler and Felix Putze. | |
41 | ||
42 | #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H | |
43 | #define _GLIBCXX_PARALLEL_ALGOBASE_H 1 | |
44 | ||
c2ba9709 JS |
45 | #include <bits/stl_algobase.h> |
46 | #include <parallel/base.h> | |
47 | #include <parallel/tags.h> | |
48 | #include <parallel/settings.h> | |
49 | #include <parallel/find.h> | |
50 | #include <parallel/find_selectors.h> | |
c2ba9709 JS |
51 | |
52 | namespace std | |
53 | { | |
54 | namespace __parallel | |
55 | { | |
4f39bf5c | 56 | // NB: equal and lexicographical_compare require mismatch. |
c2ba9709 JS |
57 | |
58 | // Sequential fallback | |
59 | template<typename InputIterator1, typename InputIterator2> | |
531898c3 | 60 | inline pair<InputIterator1, InputIterator2> |
a4797b34 | 61 | mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
531898c3 PC |
62 | __gnu_parallel::sequential_tag) |
63 | { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); } | |
c2ba9709 JS |
64 | |
65 | // Sequential fallback | |
531898c3 PC |
66 | template<typename InputIterator1, typename InputIterator2, |
67 | typename Predicate> | |
68 | inline pair<InputIterator1, InputIterator2> | |
a4797b34 | 69 | mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
531898c3 PC |
70 | Predicate pred, __gnu_parallel::sequential_tag) |
71 | { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); } | |
c2ba9709 JS |
72 | |
73 | // Sequential fallback for input iterator case | |
531898c3 PC |
74 | template<typename InputIterator1, typename InputIterator2, |
75 | typename Predicate, typename IteratorTag1, typename IteratorTag2> | |
76 | inline pair<InputIterator1, InputIterator2> | |
77 | mismatch_switch(InputIterator1 begin1, InputIterator1 end1, | |
78 | InputIterator2 begin2, Predicate pred, IteratorTag1, | |
79 | IteratorTag2) | |
80 | { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); } | |
c2ba9709 JS |
81 | |
82 | // Parallel mismatch for random access iterators | |
531898c3 PC |
83 | template<typename RandomAccessIterator1, typename RandomAccessIterator2, |
84 | typename Predicate> | |
85 | pair<RandomAccessIterator1, RandomAccessIterator2> | |
a4797b34 | 86 | mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, |
531898c3 PC |
87 | RandomAccessIterator2 begin2, Predicate pred, |
88 | random_access_iterator_tag, random_access_iterator_tag) | |
89 | { | |
90 | if (_GLIBCXX_PARALLEL_CONDITION(true)) | |
91 | { | |
92 | RandomAccessIterator1 res = | |
93 | __gnu_parallel::find_template(begin1, end1, begin2, pred, | |
94 | __gnu_parallel:: | |
95 | mismatch_selector()).first; | |
96 | return make_pair(res , begin2 + (res - begin1)); | |
97 | } | |
98 | else | |
99 | return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); | |
100 | } | |
c2ba9709 JS |
101 | |
102 | // Public interface | |
103 | template<typename InputIterator1, typename InputIterator2> | |
531898c3 PC |
104 | inline pair<InputIterator1, InputIterator2> |
105 | mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2) | |
106 | { | |
107 | typedef std::iterator_traits<InputIterator1> iterator1_traits; | |
108 | typedef std::iterator_traits<InputIterator2> iterator2_traits; | |
109 | typedef typename iterator1_traits::value_type value1_type; | |
110 | typedef typename iterator2_traits::value_type value2_type; | |
111 | typedef typename iterator1_traits::iterator_category iterator1_category; | |
112 | typedef typename iterator2_traits::iterator_category iterator2_category; | |
113 | ||
114 | typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type; | |
115 | ||
116 | return mismatch_switch(begin1, end1, begin2, equal_to_type(), | |
117 | iterator1_category(), iterator2_category()); | |
118 | } | |
c2ba9709 JS |
119 | |
120 | // Public interface | |
531898c3 PC |
121 | template<typename InputIterator1, typename InputIterator2, |
122 | typename Predicate> | |
123 | inline pair<InputIterator1, InputIterator2> | |
124 | mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, | |
125 | Predicate pred) | |
126 | { | |
127 | typedef std::iterator_traits<InputIterator1> iterator1_traits; | |
128 | typedef std::iterator_traits<InputIterator2> iterator2_traits; | |
129 | typedef typename iterator1_traits::iterator_category iterator1_category; | |
130 | typedef typename iterator2_traits::iterator_category iterator2_category; | |
131 | ||
132 | return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(), | |
133 | iterator2_category()); | |
134 | } | |
c2ba9709 | 135 | |
4f39bf5c PC |
136 | // Sequential fallback |
137 | template<typename InputIterator1, typename InputIterator2> | |
531898c3 PC |
138 | inline bool |
139 | equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, | |
140 | __gnu_parallel::sequential_tag) | |
141 | { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); } | |
4f39bf5c PC |
142 | |
143 | // Sequential fallback | |
531898c3 PC |
144 | template<typename InputIterator1, typename InputIterator2, |
145 | typename Predicate> | |
146 | inline bool | |
147 | equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, | |
148 | Predicate pred, __gnu_parallel::sequential_tag) | |
149 | { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); } | |
4f39bf5c PC |
150 | |
151 | // Public interface | |
152 | template<typename InputIterator1, typename InputIterator2> | |
531898c3 PC |
153 | inline bool |
154 | equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2) | |
155 | { return mismatch(begin1, end1, begin2).first == end1; } | |
4f39bf5c PC |
156 | |
157 | // Public interface | |
531898c3 PC |
158 | template<typename InputIterator1, typename InputIterator2, |
159 | typename Predicate> | |
160 | inline bool | |
161 | equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, | |
162 | Predicate pred) | |
163 | { return mismatch(begin1, end1, begin2, pred).first == end1; } | |
4f39bf5c | 164 | |
c2ba9709 JS |
165 | // Sequential fallback |
166 | template<typename InputIterator1, typename InputIterator2> | |
531898c3 PC |
167 | inline bool |
168 | lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, | |
169 | InputIterator2 begin2, InputIterator2 end2, | |
170 | __gnu_parallel::sequential_tag) | |
171 | { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, | |
172 | begin2, end2); } | |
c2ba9709 JS |
173 | |
174 | // Sequential fallback | |
531898c3 PC |
175 | template<typename InputIterator1, typename InputIterator2, |
176 | typename Predicate> | |
177 | inline bool | |
178 | lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, | |
179 | InputIterator2 begin2, InputIterator2 end2, | |
180 | Predicate pred, __gnu_parallel::sequential_tag) | |
181 | { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, | |
182 | begin2, end2, pred); } | |
c2ba9709 JS |
183 | |
184 | // Sequential fallback for input iterator case | |
531898c3 PC |
185 | template<typename InputIterator1, typename InputIterator2, |
186 | typename Predicate, typename IteratorTag1, typename IteratorTag2> | |
187 | inline bool | |
188 | lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1, | |
189 | InputIterator2 begin2, InputIterator2 end2, | |
190 | Predicate pred, IteratorTag1, IteratorTag2) | |
191 | { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, | |
192 | begin2, end2, pred); } | |
c2ba9709 JS |
193 | |
194 | // Parallel lexicographical_compare for random access iterators | |
195 | // Limitation: Both valuetypes must be the same | |
531898c3 PC |
196 | template<typename RandomAccessIterator1, typename RandomAccessIterator2, |
197 | typename Predicate> | |
198 | bool | |
199 | lexicographical_compare_switch(RandomAccessIterator1 begin1, | |
200 | RandomAccessIterator1 end1, | |
201 | RandomAccessIterator2 begin2, | |
202 | RandomAccessIterator2 end2, Predicate pred, | |
203 | random_access_iterator_tag, | |
204 | random_access_iterator_tag) | |
205 | { | |
206 | if (_GLIBCXX_PARALLEL_CONDITION(true)) | |
207 | { | |
208 | typedef iterator_traits<RandomAccessIterator1> traits1_type; | |
209 | typedef typename traits1_type::value_type value1_type; | |
210 | ||
211 | typedef iterator_traits<RandomAccessIterator2> traits2_type; | |
212 | typedef typename traits2_type::value_type value2_type; | |
213 | ||
214 | typedef __gnu_parallel::equal_from_less<Predicate, value1_type, | |
215 | value2_type> equal_type; | |
216 | ||
217 | // Longer sequence in first place. | |
218 | if ((end1 - begin1) < (end2 - begin2)) | |
219 | { | |
220 | typedef pair<RandomAccessIterator1, RandomAccessIterator2> | |
221 | pair_type; | |
222 | pair_type mm = mismatch_switch(begin1, end1, begin2, | |
223 | equal_type(pred), | |
224 | random_access_iterator_tag(), | |
225 | random_access_iterator_tag()); | |
226 | ||
227 | return (mm.first == end1) || bool(pred(*mm.first, *mm.second)); | |
228 | } | |
229 | else | |
230 | { | |
231 | typedef pair<RandomAccessIterator2, RandomAccessIterator1> | |
232 | pair_type; | |
233 | pair_type mm = mismatch_switch(begin2, end2, begin1, | |
234 | equal_type(pred), | |
235 | random_access_iterator_tag(), | |
236 | random_access_iterator_tag()); | |
237 | ||
238 | return (mm.first != end2) && bool(pred(*mm.second, *mm.first)); | |
239 | } | |
240 | } | |
241 | else | |
242 | return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, | |
243 | begin2, end2, pred); | |
244 | } | |
c2ba9709 JS |
245 | |
246 | // Public interface | |
247 | template<typename InputIterator1, typename InputIterator2> | |
531898c3 PC |
248 | inline bool |
249 | lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, | |
250 | InputIterator2 begin2, InputIterator2 end2) | |
251 | { | |
252 | typedef iterator_traits<InputIterator1> traits1_type; | |
253 | typedef typename traits1_type::value_type value1_type; | |
254 | typedef typename traits1_type::iterator_category iterator1_category; | |
255 | ||
256 | typedef iterator_traits<InputIterator2> traits2_type; | |
257 | typedef typename traits2_type::value_type value2_type; | |
258 | typedef typename traits2_type::iterator_category iterator2_category; | |
259 | typedef __gnu_parallel::less<value1_type, value2_type> less_type; | |
260 | ||
261 | return lexicographical_compare_switch(begin1, end1, begin2, end2, | |
262 | less_type(), iterator1_category(), | |
263 | iterator2_category()); | |
264 | } | |
c2ba9709 JS |
265 | |
266 | // Public interface | |
531898c3 PC |
267 | template<typename InputIterator1, typename InputIterator2, |
268 | typename Predicate> | |
269 | inline bool | |
270 | lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, | |
271 | InputIterator2 begin2, InputIterator2 end2, | |
272 | Predicate pred) | |
273 | { | |
274 | typedef iterator_traits<InputIterator1> traits1_type; | |
275 | typedef typename traits1_type::iterator_category iterator1_category; | |
276 | ||
277 | typedef iterator_traits<InputIterator2> traits2_type; | |
278 | typedef typename traits2_type::iterator_category iterator2_category; | |
279 | ||
280 | return lexicographical_compare_switch(begin1, end1, begin2, end2, pred, | |
281 | iterator1_category(), | |
282 | iterator2_category()); | |
283 | } | |
c2ba9709 JS |
284 | } // end namespace |
285 | } // end namespace | |
286 | ||
cbcd1e45 | 287 | #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */ |