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