]>
Commit | Line | Data |
---|---|---|
1 | // -*- C++ -*- | |
2 | ||
3 | // Copyright (C) 2007, 2008, 2009 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 3, 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 | // 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. | |
19 | ||
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/>. | |
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 | ||
35 | #include <bits/c++config.h> | |
36 | #include <bits/stl_function.h> | |
37 | #include <omp.h> | |
38 | #include <parallel/features.h> | |
39 | #include <parallel/basic_iterator.h> | |
40 | #include <parallel/parallel.h> | |
41 | ||
42 | // Parallel mode namespaces. | |
43 | ||
44 | /** | |
45 | * @namespace std::__parallel | |
46 | * @brief GNU parallel code, replaces standard behavior with parallel behavior. | |
47 | */ | |
48 | namespace std | |
49 | { | |
50 | namespace __parallel { } | |
51 | } | |
52 | ||
53 | /** | |
54 | * @namespace __gnu_parallel | |
55 | * @brief GNU parallel code for public use. | |
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 | { | |
69 | // Import whatever is the serial version. | |
70 | #ifdef _GLIBCXX_PARALLEL | |
71 | using namespace std::__norm; | |
72 | #else | |
73 | using namespace std; | |
74 | #endif | |
75 | } | |
76 | ||
77 | ||
78 | namespace __gnu_parallel | |
79 | { | |
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 _ThreadIndex | |
85 | __get_max_threads() | |
86 | { | |
87 | _ThreadIndex __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 | ||
96 | /** @brief Calculates the rounded-down logarithm of @c __n for base 2. | |
97 | * @param __n Argument. | |
98 | * @return Returns 0 for any argument <1. | |
99 | */ | |
100 | template<typename _Size> | |
101 | inline _Size | |
102 | __rd_log2(_Size __n) | |
103 | { | |
104 | _Size __k; | |
105 | for (__k = 0; __n > 1; __n >>= 1) | |
106 | ++__k; | |
107 | return __k; | |
108 | } | |
109 | ||
110 | /** @brief Encode two integers into one gnu_parallel::_CASable. | |
111 | * @param __a First integer, to be encoded in the most-significant @c | |
112 | * _CASable_bits/2 bits. | |
113 | * @param __b Second integer, to be encoded in the least-significant | |
114 | * @c _CASable_bits/2 bits. | |
115 | * @return value encoding @c __a and @c __b. | |
116 | * @see decode2 | |
117 | */ | |
118 | inline _CASable | |
119 | __encode2(int __a, int __b) //must all be non-negative, actually | |
120 | { | |
121 | return (((_CASable)__a) << (_CASable_bits / 2)) | (((_CASable)__b) << 0); | |
122 | } | |
123 | ||
124 | /** @brief Decode two integers from one gnu_parallel::_CASable. | |
125 | * @param __x __gnu_parallel::_CASable to decode integers from. | |
126 | * @param __a First integer, to be decoded from the most-significant | |
127 | * @c _CASable_bits/2 bits of @c __x. | |
128 | * @param __b Second integer, to be encoded in the least-significant | |
129 | * @c _CASable_bits/2 bits of @c __x. | |
130 | * @see __encode2 | |
131 | */ | |
132 | inline void | |
133 | decode2(_CASable __x, int& __a, int& __b) | |
134 | { | |
135 | __a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask); | |
136 | __b = (int)((__x >> 0 ) & _CASable_mask); | |
137 | } | |
138 | ||
139 | //needed for parallel "numeric", even if "algorithm" not included | |
140 | ||
141 | /** @brief Equivalent to std::min. */ | |
142 | template<typename _Tp> | |
143 | const _Tp& | |
144 | min(const _Tp& __a, const _Tp& __b) | |
145 | { return (__a < __b) ? __a : __b; } | |
146 | ||
147 | /** @brief Equivalent to std::max. */ | |
148 | template<typename _Tp> | |
149 | const _Tp& | |
150 | max(const _Tp& __a, const _Tp& __b) | |
151 | { return (__a > __b) ? __a : __b; } | |
152 | ||
153 | /** @brief Constructs predicate for equality from strict weak | |
154 | * ordering predicate | |
155 | */ | |
156 | template<typename _T1, typename _T2, typename _Compare> | |
157 | class _EqualFromLess : public std::binary_function<_T1, _T2, bool> | |
158 | { | |
159 | private: | |
160 | _Compare& _M_comp; | |
161 | ||
162 | public: | |
163 | _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { } | |
164 | ||
165 | bool operator()(const _T1& __a, const _T2& __b) | |
166 | { return !_M_comp(__a, __b) && !_M_comp(__b, __a); } | |
167 | }; | |
168 | ||
169 | ||
170 | /** @brief Similar to std::binder1st, | |
171 | * but giving the argument types explicitly. */ | |
172 | template<typename _Predicate, typename argument_type> | |
173 | class __unary_negate | |
174 | : public std::unary_function<argument_type, bool> | |
175 | { | |
176 | protected: | |
177 | _Predicate _M_pred; | |
178 | ||
179 | public: | |
180 | explicit | |
181 | __unary_negate(const _Predicate& __x) : _M_pred(__x) { } | |
182 | ||
183 | bool | |
184 | operator()(const argument_type& __x) | |
185 | { return !_M_pred(__x); } | |
186 | }; | |
187 | ||
188 | /** @brief Similar to std::binder1st, | |
189 | * but giving the argument types explicitly. */ | |
190 | template<typename _Operation, typename _FirstArgumentType, | |
191 | typename _SecondArgumentType, typename _ResultType> | |
192 | class __binder1st | |
193 | : public std::unary_function<_SecondArgumentType, _ResultType> | |
194 | { | |
195 | protected: | |
196 | _Operation _M_op; | |
197 | _FirstArgumentType _M_value; | |
198 | ||
199 | public: | |
200 | __binder1st(const _Operation& __x, const _FirstArgumentType& __y) | |
201 | : _M_op(__x), _M_value(__y) { } | |
202 | ||
203 | _ResultType | |
204 | operator()(const _SecondArgumentType& __x) | |
205 | { return _M_op(_M_value, __x); } | |
206 | ||
207 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
208 | // 109. Missing binders for non-const sequence elements | |
209 | _ResultType | |
210 | operator()(_SecondArgumentType& __x) const | |
211 | { return _M_op(_M_value, __x); } | |
212 | }; | |
213 | ||
214 | /** | |
215 | * @brief Similar to std::binder2nd, but giving the argument types | |
216 | * explicitly. | |
217 | */ | |
218 | template<typename _Operation, typename _FirstArgumentType, | |
219 | typename _SecondArgumentType, typename _ResultType> | |
220 | class binder2nd | |
221 | : public std::unary_function<_FirstArgumentType, _ResultType> | |
222 | { | |
223 | protected: | |
224 | _Operation _M_op; | |
225 | _SecondArgumentType _M_value; | |
226 | ||
227 | public: | |
228 | binder2nd(const _Operation& __x, const _SecondArgumentType& __y) | |
229 | : _M_op(__x), _M_value(__y) { } | |
230 | ||
231 | _ResultType | |
232 | operator()(const _FirstArgumentType& __x) const | |
233 | { return _M_op(__x, _M_value); } | |
234 | ||
235 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
236 | // 109. Missing binders for non-const sequence elements | |
237 | _ResultType | |
238 | operator()(_FirstArgumentType& __x) | |
239 | { return _M_op(__x, _M_value); } | |
240 | }; | |
241 | ||
242 | /** @brief Similar to std::equal_to, but allows two different types. */ | |
243 | template<typename _T1, typename _T2> | |
244 | struct _EqualTo : std::binary_function<_T1, _T2, bool> | |
245 | { | |
246 | bool operator()(const _T1& __t1, const _T2& __t2) const | |
247 | { return __t1 == __t2; } | |
248 | }; | |
249 | ||
250 | /** @brief Similar to std::less, but allows two different types. */ | |
251 | template<typename _T1, typename _T2> | |
252 | struct _Less : std::binary_function<_T1, _T2, bool> | |
253 | { | |
254 | bool | |
255 | operator()(const _T1& __t1, const _T2& __t2) const | |
256 | { return __t1 < __t2; } | |
257 | ||
258 | bool | |
259 | operator()(const _T2& __t2, const _T1& __t1) const | |
260 | { return __t2 < __t1; } | |
261 | }; | |
262 | ||
263 | // Partial specialization for one type. Same as std::less. | |
264 | template<typename _Tp> | |
265 | struct _Less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool> | |
266 | { | |
267 | bool | |
268 | operator()(const _Tp& __x, const _Tp& __y) const | |
269 | { return __x < __y; } | |
270 | }; | |
271 | ||
272 | ||
273 | /** @brief Similar to std::plus, but allows two different types. */ | |
274 | template<typename _Tp1, typename _Tp2> | |
275 | struct _Plus : public std::binary_function<_Tp1, _Tp2, _Tp1> | |
276 | { | |
277 | typedef __typeof__(*static_cast<_Tp1*>(NULL) | |
278 | + *static_cast<_Tp2*>(NULL)) __result; | |
279 | ||
280 | __result | |
281 | operator()(const _Tp1& __x, const _Tp2& __y) const | |
282 | { return __x + __y; } | |
283 | }; | |
284 | ||
285 | // Partial specialization for one type. Same as std::plus. | |
286 | template<typename _Tp> | |
287 | struct _Plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp> | |
288 | { | |
289 | typedef __typeof__(*static_cast<_Tp*>(NULL) | |
290 | + *static_cast<_Tp*>(NULL)) __result; | |
291 | ||
292 | __result | |
293 | operator()(const _Tp& __x, const _Tp& __y) const | |
294 | { return __x + __y; } | |
295 | }; | |
296 | ||
297 | ||
298 | /** @brief Similar to std::multiplies, but allows two different types. */ | |
299 | template<typename _Tp1, typename _Tp2> | |
300 | struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1> | |
301 | { | |
302 | typedef __typeof__(*static_cast<_Tp1*>(NULL) | |
303 | * *static_cast<_Tp2*>(NULL)) __result; | |
304 | ||
305 | __result | |
306 | operator()(const _Tp1& __x, const _Tp2& __y) const | |
307 | { return __x * __y; } | |
308 | }; | |
309 | ||
310 | // Partial specialization for one type. Same as std::multiplies. | |
311 | template<typename _Tp> | |
312 | struct _Multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp> | |
313 | { | |
314 | typedef __typeof__(*static_cast<_Tp*>(NULL) | |
315 | * *static_cast<_Tp*>(NULL)) __result; | |
316 | ||
317 | __result | |
318 | operator()(const _Tp& __x, const _Tp& __y) const | |
319 | { return __x * __y; } | |
320 | }; | |
321 | ||
322 | ||
323 | template<typename _Tp, typename _DifferenceTp> | |
324 | class _PseudoSequence; | |
325 | ||
326 | /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence. | |
327 | * If features the usual random-access iterator functionality. | |
328 | * @param _Tp Sequence _M_value type. | |
329 | * @param _DifferenceType Sequence difference type. | |
330 | */ | |
331 | template<typename _Tp, typename _DifferenceTp> | |
332 | class _PseudoSequenceIterator | |
333 | { | |
334 | public: | |
335 | typedef _DifferenceTp _DifferenceType; | |
336 | ||
337 | private: | |
338 | const _Tp& _M_val; | |
339 | _DifferenceType _M_pos; | |
340 | ||
341 | public: | |
342 | _PseudoSequenceIterator(const _Tp& __val, _DifferenceType __pos) | |
343 | : _M_val(__val), _M_pos(__pos) { } | |
344 | ||
345 | // Pre-increment operator. | |
346 | _PseudoSequenceIterator& | |
347 | operator++() | |
348 | { | |
349 | ++_M_pos; | |
350 | return *this; | |
351 | } | |
352 | ||
353 | // Post-increment operator. | |
354 | const _PseudoSequenceIterator | |
355 | operator++(int) | |
356 | { return _PseudoSequenceIterator(_M_pos++); } | |
357 | ||
358 | const _Tp& | |
359 | operator*() const | |
360 | { return _M_val; } | |
361 | ||
362 | const _Tp& | |
363 | operator[](_DifferenceType) const | |
364 | { return _M_val; } | |
365 | ||
366 | bool | |
367 | operator==(const _PseudoSequenceIterator& __i2) | |
368 | { return _M_pos == __i2._M_pos; } | |
369 | ||
370 | _DifferenceType | |
371 | operator!=(const _PseudoSequenceIterator& __i2) | |
372 | { return _M_pos != __i2._M_pos; } | |
373 | ||
374 | _DifferenceType | |
375 | operator-(const _PseudoSequenceIterator& __i2) | |
376 | { return _M_pos - __i2._M_pos; } | |
377 | }; | |
378 | ||
379 | /** @brief Sequence that conceptually consists of multiple copies of | |
380 | the same element. | |
381 | * The copies are not stored explicitly, of course. | |
382 | * @param _Tp Sequence _M_value type. | |
383 | * @param _DifferenceType Sequence difference type. | |
384 | */ | |
385 | template<typename _Tp, typename _DifferenceTp> | |
386 | class _PseudoSequence | |
387 | { | |
388 | public: | |
389 | typedef _DifferenceTp _DifferenceType; | |
390 | ||
391 | // Better cast down to uint64_t, than up to _DifferenceTp. | |
392 | typedef _PseudoSequenceIterator<_Tp, uint64_t> iterator; | |
393 | ||
394 | /** @brief Constructor. | |
395 | * @param _M_val Element of the sequence. | |
396 | * @param __count Number of (virtual) copies. | |
397 | */ | |
398 | _PseudoSequence(const _Tp& __val, _DifferenceType __count) | |
399 | : _M_val(__val), _M_count(__count) { } | |
400 | ||
401 | /** @brief Begin iterator. */ | |
402 | iterator | |
403 | begin() const | |
404 | { return iterator(_M_val, 0); } | |
405 | ||
406 | /** @brief End iterator. */ | |
407 | iterator | |
408 | end() const | |
409 | { return iterator(_M_val, _M_count); } | |
410 | ||
411 | private: | |
412 | const _Tp& _M_val; | |
413 | _DifferenceType _M_count; | |
414 | }; | |
415 | ||
416 | /** @brief Functor that does nothing */ | |
417 | template<typename _ValueTp> | |
418 | class _VoidFunctor | |
419 | { | |
420 | inline void | |
421 | operator()(const _ValueTp& __v) const { } | |
422 | }; | |
423 | ||
424 | /** @brief Compute the median of three referenced elements, | |
425 | according to @c __comp. | |
426 | * @param __a First iterator. | |
427 | * @param __b Second iterator. | |
428 | * @param __c Third iterator. | |
429 | * @param __comp Comparator. | |
430 | */ | |
431 | template<typename _RAIter, typename _Compare> | |
432 | _RAIter | |
433 | __median_of_three_iterators(_RAIter __a, _RAIter __b, | |
434 | _RAIter __c, _Compare& __comp) | |
435 | { | |
436 | if (__comp(*__a, *__b)) | |
437 | if (__comp(*__b, *__c)) | |
438 | return __b; | |
439 | else | |
440 | if (__comp(*__a, *__c)) | |
441 | return __c; | |
442 | else | |
443 | return __a; | |
444 | else | |
445 | { | |
446 | // Just swap __a and __b. | |
447 | if (__comp(*__a, *__c)) | |
448 | return __a; | |
449 | else | |
450 | if (__comp(*__b, *__c)) | |
451 | return __c; | |
452 | else | |
453 | return __b; | |
454 | } | |
455 | } | |
456 | ||
457 | #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition) | |
458 | ||
459 | } //namespace __gnu_parallel | |
460 | ||
461 | #endif /* _GLIBCXX_PARALLEL_BASE_H */ |