]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
5817ff8e | 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/base.h | |
32 | * @brief Sequential helper functions. | |
33 | * This file is a GNU parallel extension to the Standard C++ Library. | |
34 | */ | |
35 | ||
36 | // Written by Johannes Singler. | |
37 | ||
38 | #ifndef _GLIBCXX_PARALLEL_BASE_H | |
39 | #define _GLIBCXX_PARALLEL_BASE_H 1 | |
40 | ||
41 | #include <parallel/features.h> | |
42 | #include <functional> | |
43 | #include <parallel/basic_iterator.h> | |
44 | #include <parallel/parallel.h> | |
45 | #include <cstdio> | |
46 | ||
47 | namespace __gnu_parallel | |
48 | { | |
49 | // XXX remove std::duplicates from here if possible, | |
50 | // XXX but keep minimal dependencies. | |
51 | ||
e683ee2a JS |
52 | /** @brief Calculates the rounded-down logarithm of @c n for base 2. |
53 | * @param n Argument. | |
54 | * @return Returns 0 for argument 0. | |
55 | */ | |
56 | template<typename Size> | |
57 | inline Size | |
58 | log2(Size n) | |
c2ba9709 JS |
59 | { |
60 | Size k; | |
61 | for (k = 0; n != 1; n >>= 1) | |
e683ee2a | 62 | ++k; |
c2ba9709 JS |
63 | return k; |
64 | } | |
65 | ||
e683ee2a JS |
66 | /** @brief Encode two integers into one __gnu_parallel::lcas_t. |
67 | * @param a First integer, to be encoded in the most-significant @c | |
68 | * lcas_t_bits/2 bits. | |
69 | * @param b Second integer, to be encoded in the least-significant | |
70 | * @c lcas_t_bits/2 bits. | |
71 | * @return __gnu_parallel::lcas_t value encoding @c a and @c b. | |
72 | * @see decode2 | |
73 | */ | |
74 | inline lcas_t | |
75 | encode2(int a, int b) //must all be non-negative, actually | |
76 | { | |
77 | return (((lcas_t)a) << (lcas_t_bits / 2)) | (((lcas_t)b) << 0); | |
78 | } | |
79 | ||
80 | /** @brief Decode two integers from one __gnu_parallel::lcas_t. | |
81 | * @param x __gnu_parallel::lcas_t to decode integers from. | |
82 | * @param a First integer, to be decoded from the most-significant | |
83 | * @c lcas_t_bits/2 bits of @c x. | |
84 | * @param b Second integer, to be encoded in the least-significant | |
85 | * @c lcas_t_bits/2 bits of @c x. | |
86 | * @see encode2 | |
87 | */ | |
88 | inline void | |
89 | decode2(lcas_t x, int& a, int& b) | |
90 | { | |
91 | a = (int)((x >> (lcas_t_bits / 2)) & lcas_t_mask); | |
92 | b = (int)((x >> 0 ) & lcas_t_mask); | |
93 | } | |
94 | ||
95 | /** @brief Equivalent to std::min. */ | |
96 | template<typename T> | |
97 | const T& | |
98 | min(const T& a, const T& b) | |
5817ff8e | 99 | { return (a < b) ? a : b; } |
c2ba9709 | 100 | |
e683ee2a JS |
101 | /** @brief Equivalent to std::max. */ |
102 | template<typename T> | |
103 | const T& | |
104 | max(const T& a, const T& b) | |
5817ff8e | 105 | { return (a > b) ? a : b; } |
c2ba9709 | 106 | |
e683ee2a JS |
107 | /** @brief Constructs predicate for equality from strict weak |
108 | * ordering predicate | |
109 | */ | |
110 | // XXX comparator at the end, as per others | |
111 | template<typename Comparator, typename T1, typename T2> | |
c2ba9709 JS |
112 | class equal_from_less : public std::binary_function<T1, T2, bool> |
113 | { | |
114 | private: | |
115 | Comparator& comp; | |
116 | ||
117 | public: | |
118 | equal_from_less(Comparator& _comp) : comp(_comp) { } | |
119 | ||
120 | bool operator()(const T1& a, const T2& b) | |
121 | { | |
c2ba9709 JS |
122 | return !comp(a, b) && !comp(b, a); |
123 | } | |
124 | }; | |
125 | ||
126 | ||
e683ee2a JS |
127 | /** @brief Similar to std::binder1st, |
128 | * but giving the argument types explicitly. */ | |
129 | template<typename _Predicate, typename argument_type> | |
130 | class unary_negate | |
131 | : public std::unary_function<argument_type, bool> | |
132 | { | |
133 | protected: | |
134 | _Predicate _M_pred; | |
135 | ||
136 | public: | |
137 | explicit | |
138 | unary_negate(const _Predicate& __x) : _M_pred(__x) { } | |
139 | ||
140 | bool | |
141 | operator()(const argument_type& __x) | |
142 | { return !_M_pred(__x); } | |
143 | }; | |
144 | ||
145 | /** @brief Similar to std::binder1st, | |
146 | * but giving the argument types explicitly. */ | |
147 | template< | |
148 | typename _Operation, | |
149 | typename first_argument_type, | |
150 | typename second_argument_type, | |
151 | typename result_type> | |
152 | class binder1st | |
153 | : public std::unary_function<second_argument_type, result_type> | |
154 | { | |
155 | protected: | |
156 | _Operation op; | |
157 | first_argument_type value; | |
158 | ||
159 | public: | |
160 | binder1st(const _Operation& __x, | |
161 | const first_argument_type& __y) | |
162 | : op(__x), value(__y) { } | |
163 | ||
164 | result_type | |
165 | operator()(const second_argument_type& __x) | |
166 | { return op(value, __x); } | |
167 | ||
168 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
169 | // 109. Missing binders for non-const sequence elements | |
170 | result_type | |
171 | operator()(second_argument_type& __x) const | |
172 | { return op(value, __x); } | |
173 | }; | |
174 | ||
175 | /** | |
176 | * @brief Similar to std::binder2nd, but giving the argument types | |
177 | * explicitly. | |
178 | */ | |
179 | template< | |
180 | typename _Operation, | |
181 | typename first_argument_type, | |
182 | typename second_argument_type, | |
183 | typename result_type> | |
184 | class binder2nd | |
185 | : public std::unary_function<first_argument_type, result_type> | |
186 | { | |
187 | protected: | |
188 | _Operation op; | |
189 | second_argument_type value; | |
190 | ||
191 | public: | |
192 | binder2nd(const _Operation& __x, | |
193 | const second_argument_type& __y) | |
194 | : op(__x), value(__y) { } | |
195 | ||
196 | result_type | |
197 | operator()(const first_argument_type& __x) const | |
198 | { return op(__x, value); } | |
199 | ||
200 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
201 | // 109. Missing binders for non-const sequence elements | |
202 | result_type | |
203 | operator()(first_argument_type& __x) | |
204 | { return op(__x, value); } | |
205 | }; | |
206 | ||
207 | /** @brief Similar to std::equal_to, but allows two different types. */ | |
208 | template<typename T1, typename T2> | |
0e6c9eaa JS |
209 | struct equal_to : std::binary_function<T1, T2, bool> |
210 | { | |
211 | bool operator()(const T1& t1, const T2& t2) const | |
212 | { return t1 == t2; } | |
213 | }; | |
214 | ||
e683ee2a JS |
215 | /** @brief Similar to std::less, but allows two different types. */ |
216 | template<typename T1, typename T2> | |
c2ba9709 JS |
217 | struct less : std::binary_function<T1, T2, bool> |
218 | { | |
e683ee2a | 219 | bool |
c5654e49 | 220 | operator()(const T1& t1, const T2& t2) const |
c2ba9709 | 221 | { return t1 < t2; } |
c5654e49 | 222 | |
e683ee2a | 223 | bool |
c5654e49 BK |
224 | operator()(const T2& t2, const T1& t1) const |
225 | { return t2 < t1; } | |
c2ba9709 JS |
226 | }; |
227 | ||
e683ee2a JS |
228 | // Partial specialization for one type. Same as std::less. |
229 | template<typename _Tp> | |
230 | struct less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool> | |
231 | { | |
232 | bool | |
233 | operator()(const _Tp& __x, const _Tp& __y) const | |
234 | { return __x < __y; } | |
235 | }; | |
c2ba9709 | 236 | |
0e6c9eaa | 237 | |
e683ee2a JS |
238 | /** @brief Similar to std::plus, but allows two different types. */ |
239 | template<typename _Tp1, typename _Tp2> | |
240 | struct plus : public std::binary_function<_Tp1, _Tp2, _Tp1> | |
241 | { | |
242 | typedef typeof(*static_cast<_Tp1*>(NULL) | |
243 | + *static_cast<_Tp2*>(NULL)) result; | |
0e6c9eaa | 244 | |
e683ee2a JS |
245 | result |
246 | operator()(const _Tp1& __x, const _Tp2& __y) const | |
247 | { return __x + __y; } | |
248 | }; | |
0e6c9eaa | 249 | |
e683ee2a JS |
250 | // Partial specialization for one type. Same as std::plus. |
251 | template<typename _Tp> | |
252 | struct plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp> | |
253 | { | |
254 | typedef typeof(*static_cast<_Tp*>(NULL) | |
255 | + *static_cast<_Tp*>(NULL)) result; | |
0e6c9eaa | 256 | |
e683ee2a JS |
257 | result |
258 | operator()(const _Tp& __x, const _Tp& __y) const | |
259 | { return __x + __y; } | |
260 | }; | |
0e6c9eaa JS |
261 | |
262 | ||
e683ee2a JS |
263 | /** @brief Similar to std::multiplies, but allows two different types. */ |
264 | template<typename _Tp1, typename _Tp2> | |
265 | struct multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1> | |
266 | { | |
267 | typedef typeof(*static_cast<_Tp1*>(NULL) | |
268 | * *static_cast<_Tp2*>(NULL)) result; | |
0e6c9eaa | 269 | |
e683ee2a JS |
270 | result |
271 | operator()(const _Tp1& __x, const _Tp2& __y) const | |
272 | { return __x * __y; } | |
273 | }; | |
0e6c9eaa | 274 | |
e683ee2a JS |
275 | // Partial specialization for one type. Same as std::multiplies. |
276 | template<typename _Tp> | |
277 | struct multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp> | |
278 | { | |
279 | typedef typeof(*static_cast<_Tp*>(NULL) | |
280 | * *static_cast<_Tp*>(NULL)) result; | |
0e6c9eaa | 281 | |
e683ee2a JS |
282 | result |
283 | operator()(const _Tp& __x, const _Tp& __y) const | |
284 | { return __x * __y; } | |
285 | }; | |
0e6c9eaa JS |
286 | |
287 | ||
e683ee2a | 288 | template<typename T, typename _DifferenceTp> |
c2ba9709 JS |
289 | class pseudo_sequence; |
290 | ||
e683ee2a JS |
291 | /** @brief Iterator associated with __gnu_parallel::pseudo_sequence. |
292 | * If features the usual random-access iterator functionality. | |
293 | * @param T Sequence value type. | |
294 | * @param difference_type Sequence difference type. | |
295 | */ | |
296 | template<typename T, typename _DifferenceTp> | |
c2ba9709 JS |
297 | class pseudo_sequence_iterator |
298 | { | |
299 | public: | |
300 | typedef _DifferenceTp difference_type; | |
301 | ||
302 | private: | |
303 | typedef pseudo_sequence_iterator<T, _DifferenceTp> type; | |
304 | ||
305 | const T& val; | |
306 | difference_type pos; | |
307 | ||
308 | public: | |
309 | pseudo_sequence_iterator(const T& val, difference_type pos) | |
310 | : val(val), pos(pos) { } | |
311 | ||
312 | // Pre-increment operator. | |
313 | type& | |
314 | operator++() | |
315 | { | |
316 | ++pos; | |
317 | return *this; | |
318 | } | |
319 | ||
320 | // Post-increment operator. | |
321 | const type | |
322 | operator++(int) | |
323 | { return type(pos++); } | |
324 | ||
e683ee2a | 325 | const T& |
c2ba9709 JS |
326 | operator*() const |
327 | { return val; } | |
328 | ||
e683ee2a | 329 | const T& |
c2ba9709 JS |
330 | operator[](difference_type) const |
331 | { return val; } | |
332 | ||
e683ee2a | 333 | bool |
c2ba9709 JS |
334 | operator==(const type& i2) |
335 | { return pos == i2.pos; } | |
336 | ||
e683ee2a | 337 | difference_type |
c2ba9709 JS |
338 | operator!=(const type& i2) |
339 | { return pos != i2.pos; } | |
340 | ||
e683ee2a | 341 | difference_type |
c2ba9709 JS |
342 | operator-(const type& i2) |
343 | { return pos - i2.pos; } | |
344 | }; | |
345 | ||
e683ee2a JS |
346 | /** @brief Sequence that conceptually consists of multiple copies of |
347 | the same element. | |
348 | * The copies are not stored explicitly, of course. | |
349 | * @param T Sequence value type. | |
350 | * @param difference_type Sequence difference type. | |
351 | */ | |
352 | template<typename T, typename _DifferenceTp> | |
c2ba9709 JS |
353 | class pseudo_sequence |
354 | { | |
355 | typedef pseudo_sequence<T, _DifferenceTp> type; | |
356 | ||
357 | public: | |
358 | typedef _DifferenceTp difference_type; | |
c5654e49 BK |
359 | |
360 | // Better case down to uint64, than up to _DifferenceTp. | |
361 | typedef pseudo_sequence_iterator<T, uint64> iterator; | |
c2ba9709 JS |
362 | |
363 | /** @brief Constructor. | |
e683ee2a JS |
364 | * @param val Element of the sequence. |
365 | * @param count Number of (virtual) copies. | |
366 | */ | |
367 | pseudo_sequence(const T& val, difference_type count) | |
c2ba9709 JS |
368 | : val(val), count(count) { } |
369 | ||
370 | /** @brief Begin iterator. */ | |
371 | iterator | |
372 | begin() const | |
373 | { return iterator(val, 0); } | |
374 | ||
375 | /** @brief End iterator. */ | |
376 | iterator | |
377 | end() const | |
378 | { return iterator(val, count); } | |
379 | ||
380 | private: | |
381 | const T& val; | |
382 | difference_type count; | |
383 | }; | |
384 | ||
e683ee2a JS |
385 | /** @brief Functor that does nothing */ |
386 | template<typename _ValueTp> | |
c2ba9709 JS |
387 | class void_functor |
388 | { | |
e683ee2a | 389 | inline void |
c2ba9709 JS |
390 | operator()(const _ValueTp& v) const { } |
391 | }; | |
392 | ||
e683ee2a JS |
393 | /** @brief Compute the median of three referenced elements, |
394 | according to @c comp. | |
395 | * @param a First iterator. | |
396 | * @param b Second iterator. | |
397 | * @param c Third iterator. | |
398 | * @param comp Comparator. | |
399 | */ | |
400 | template<typename RandomAccessIterator, typename Comparator> | |
5817ff8e | 401 | RandomAccessIterator |
e683ee2a JS |
402 | median_of_three_iterators(RandomAccessIterator a, RandomAccessIterator b, |
403 | RandomAccessIterator c, Comparator& comp) | |
c2ba9709 JS |
404 | { |
405 | if (comp(*a, *b)) | |
406 | if (comp(*b, *c)) | |
e683ee2a | 407 | return b; |
c2ba9709 | 408 | else |
e683ee2a JS |
409 | if (comp(*a, *c)) |
410 | return c; | |
411 | else | |
412 | return a; | |
c2ba9709 JS |
413 | else |
414 | { | |
e683ee2a JS |
415 | // Just swap a and b. |
416 | if (comp(*a, *c)) | |
417 | return a; | |
418 | else | |
419 | if (comp(*b, *c)) | |
420 | return c; | |
421 | else | |
422 | return b; | |
c2ba9709 JS |
423 | } |
424 | } | |
425 | ||
e683ee2a JS |
426 | // Avoid the use of assert, because we're trying to keep the <cassert> |
427 | // include out of the mix. (Same as debug mode). | |
428 | inline void | |
429 | __replacement_assert(const char* __file, int __line, | |
430 | const char* __function, const char* __condition) | |
431 | { | |
432 | std::printf("%s:%d: %s: Assertion '%s' failed.\n", __file, __line, | |
433 | __function, __condition); | |
434 | __builtin_abort(); | |
435 | } | |
436 | ||
c2ba9709 | 437 | #define _GLIBCXX_PARALLEL_ASSERT(_Condition) \ |
e683ee2a JS |
438 | do \ |
439 | { \ | |
440 | if (!(_Condition)) \ | |
441 | __gnu_parallel::__replacement_assert(__FILE__, __LINE__, \ | |
442 | __PRETTY_FUNCTION__, #_Condition); \ | |
443 | } while (false) | |
444 | ||
c2ba9709 JS |
445 | } //namespace __gnu_parallel |
446 | ||
447 | #endif |