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