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