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