OSDN Git Service

6656b2caabb17a935920a64f4b92270aa854965a
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / parallel / base.h
1 // -*- C++ -*-
2
3 // Copyright (C) 2007, 2008, 2009, 2010 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::unary_negate,
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>
266     : public std::less<_Tp> { };
267
268   /** @brief Similar to std::plus, but allows two different types. */
269   template<typename _Tp1, typename _Tp2, typename _Result
270            = __typeof__(*static_cast<_Tp1*>(NULL)
271                         + *static_cast<_Tp2*>(NULL))>
272     struct _Plus : public std::binary_function<_Tp1, _Tp2, _Result>
273     {
274       _Result
275       operator()(const _Tp1& __x, const _Tp2& __y) const
276       { return __x + __y; }
277     };
278
279   // Partial specialization for one type. Same as std::plus.
280   template<typename _Tp>
281     struct _Plus<_Tp, _Tp, _Tp>
282     : public std::plus<_Tp> { };
283
284   /** @brief Similar to std::multiplies, but allows two different types. */
285   template<typename _Tp1, typename _Tp2, typename _Result
286            = __typeof__(*static_cast<_Tp1*>(NULL)
287                         * *static_cast<_Tp2*>(NULL))>
288     struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Result>
289     {
290       _Result
291       operator()(const _Tp1& __x, const _Tp2& __y) const
292       { return __x * __y; }
293     };
294
295   // Partial specialization for one type. Same as std::multiplies.
296   template<typename _Tp>
297     struct _Multiplies<_Tp, _Tp, _Tp>
298     : public std::multiplies<_Tp> { };
299
300   template<typename _Tp, typename _DifferenceTp>
301     class _PseudoSequence;
302
303   /** @brief _Iterator associated with __gnu_parallel::_PseudoSequence.
304    *  If features the usual random-access iterator functionality.
305    *  @param _Tp Sequence _M_value type.
306    *  @param _DifferenceType Sequence difference type.
307    */
308   template<typename _Tp, typename _DifferenceTp>
309     class _PseudoSequenceIterator
310     {
311     public:
312       typedef _DifferenceTp _DifferenceType;
313
314     private:
315       const _Tp& _M_val;
316       _DifferenceType _M_pos;
317
318     public:
319       _PseudoSequenceIterator(const _Tp& __val, _DifferenceType __pos)
320       : _M_val(__val), _M_pos(__pos) { }
321
322       // Pre-increment operator.
323       _PseudoSequenceIterator&
324       operator++()
325       {
326         ++_M_pos;
327         return *this;
328       }
329
330       // Post-increment operator.
331       const _PseudoSequenceIterator
332       operator++(int)
333       { return _PseudoSequenceIterator(_M_pos++); }
334
335       const _Tp&
336       operator*() const
337       { return _M_val; }
338
339       const _Tp&
340       operator[](_DifferenceType) const
341       { return _M_val; }
342
343       bool
344       operator==(const _PseudoSequenceIterator& __i2)
345       { return _M_pos == __i2._M_pos; }
346
347       _DifferenceType
348       operator!=(const _PseudoSequenceIterator& __i2)
349       { return _M_pos != __i2._M_pos; }
350
351       _DifferenceType
352       operator-(const _PseudoSequenceIterator& __i2)
353       { return _M_pos - __i2._M_pos; }
354     };
355
356   /** @brief Sequence that conceptually consists of multiple copies of
357       the same element.
358       *  The copies are not stored explicitly, of course.
359       *  @param _Tp Sequence _M_value type.
360       *  @param _DifferenceType Sequence difference type.
361       */
362   template<typename _Tp, typename _DifferenceTp>
363     class _PseudoSequence
364     {
365     public:
366       typedef _DifferenceTp _DifferenceType;
367
368       // Better cast down to uint64_t, than up to _DifferenceTp.
369       typedef _PseudoSequenceIterator<_Tp, uint64_t> iterator;
370
371       /** @brief Constructor.
372        *  @param _M_val Element of the sequence.
373        *  @param __count Number of (virtual) copies.
374        */
375       _PseudoSequence(const _Tp& __val, _DifferenceType __count)
376       : _M_val(__val), _M_count(__count)  { }
377
378       /** @brief Begin iterator. */
379       iterator
380       begin() const
381       { return iterator(_M_val, 0); }
382
383       /** @brief End iterator. */
384       iterator
385       end() const
386       { return iterator(_M_val, _M_count); }
387
388     private:
389       const _Tp& _M_val;
390       _DifferenceType _M_count;
391     };
392
393   /** @brief Functor that does nothing */
394   template<typename _ValueTp>
395     class _VoidFunctor
396     {
397       inline void
398       operator()(const _ValueTp& __v) const { }
399     };
400
401   /** @brief Compute the median of three referenced elements,
402       according to @c __comp.
403       *  @param __a First iterator.
404       *  @param __b Second iterator.
405       *  @param __c Third iterator.
406       *  @param __comp Comparator.
407       */
408   template<typename _RAIter, typename _Compare>
409     _RAIter
410     __median_of_three_iterators(_RAIter __a, _RAIter __b,
411                                 _RAIter __c, _Compare& __comp)
412     {
413       if (__comp(*__a, *__b))
414         if (__comp(*__b, *__c))
415           return __b;
416         else
417           if (__comp(*__a, *__c))
418             return __c;
419           else
420             return __a;
421       else
422         {
423           // Just swap __a and __b.
424           if (__comp(*__a, *__c))
425             return __a;
426           else
427             if (__comp(*__b, *__c))
428               return __c;
429             else
430               return __b;
431         }
432     }
433
434 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition)
435
436 } //namespace __gnu_parallel
437
438 #endif /* _GLIBCXX_PARALLEL_BASE_H */