00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032 #ifndef _GLIBCXX_PARALLEL_BASE_H
00033 #define _GLIBCXX_PARALLEL_BASE_H 1
00034
00035 #include <bits/c++config.h>
00036 #include <bits/stl_function.h>
00037 #include <omp.h>
00038 #include <parallel/features.h>
00039 #include <parallel/basic_iterator.h>
00040 #include <parallel/parallel.h>
00041
00042
00043
00044
00045
00046
00047
00048 namespace std
00049 {
00050 namespace __parallel { }
00051 }
00052
00053
00054
00055
00056
00057 namespace __gnu_parallel
00058 {
00059
00060 using namespace std::__parallel;
00061 }
00062
00063
00064
00065
00066
00067 namespace __gnu_sequential
00068 {
00069
00070 #ifdef _GLIBCXX_PARALLEL
00071 using namespace std::__norm;
00072 #else
00073 using namespace std;
00074 #endif
00075 }
00076
00077
00078 namespace __gnu_parallel
00079 {
00080
00081
00082
00083
00084 inline _ThreadIndex
00085 __get_max_threads()
00086 {
00087 _ThreadIndex __i = omp_get_max_threads();
00088 return __i > 1 ? __i : 1;
00089 }
00090
00091
00092 inline bool
00093 __is_parallel(const _Parallelism __p) { return __p != sequential; }
00094
00095
00096
00097
00098
00099
00100 template<typename _Size>
00101 inline _Size
00102 __rd_log2(_Size __n)
00103 {
00104 _Size __k;
00105 for (__k = 0; __n > 1; __n >>= 1)
00106 ++__k;
00107 return __k;
00108 }
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118 inline _CASable
00119 __encode2(int __a, int __b)
00120 {
00121 return (((_CASable)__a) << (_CASable_bits / 2)) | (((_CASable)__b) << 0);
00122 }
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132 inline void
00133 __decode2(_CASable __x, int& __a, int& __b)
00134 {
00135 __a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask);
00136 __b = (int)((__x >> 0 ) & _CASable_mask);
00137 }
00138
00139
00140
00141
00142 template<typename _Tp>
00143 const _Tp&
00144 min(const _Tp& __a, const _Tp& __b)
00145 { return (__a < __b) ? __a : __b; }
00146
00147
00148 template<typename _Tp>
00149 const _Tp&
00150 max(const _Tp& __a, const _Tp& __b)
00151 { return (__a > __b) ? __a : __b; }
00152
00153
00154
00155
00156 template<typename _T1, typename _T2, typename _Compare>
00157 class _EqualFromLess : public std::binary_function<_T1, _T2, bool>
00158 {
00159 private:
00160 _Compare& _M_comp;
00161
00162 public:
00163 _EqualFromLess(_Compare& __comp) : _M_comp(__comp) { }
00164
00165 bool operator()(const _T1& __a, const _T2& __b)
00166 { return !_M_comp(__a, __b) && !_M_comp(__b, __a); }
00167 };
00168
00169
00170
00171
00172 template<typename _Predicate, typename argument_type>
00173 class __unary_negate
00174 : public std::unary_function<argument_type, bool>
00175 {
00176 protected:
00177 _Predicate _M_pred;
00178
00179 public:
00180 explicit
00181 __unary_negate(const _Predicate& __x) : _M_pred(__x) { }
00182
00183 bool
00184 operator()(const argument_type& __x)
00185 { return !_M_pred(__x); }
00186 };
00187
00188
00189
00190 template<typename _Operation, typename _FirstArgumentType,
00191 typename _SecondArgumentType, typename _ResultType>
00192 class __binder1st
00193 : public std::unary_function<_SecondArgumentType, _ResultType>
00194 {
00195 protected:
00196 _Operation _M_op;
00197 _FirstArgumentType _M_value;
00198
00199 public:
00200 __binder1st(const _Operation& __x, const _FirstArgumentType& __y)
00201 : _M_op(__x), _M_value(__y) { }
00202
00203 _ResultType
00204 operator()(const _SecondArgumentType& __x)
00205 { return _M_op(_M_value, __x); }
00206
00207
00208
00209 _ResultType
00210 operator()(_SecondArgumentType& __x) const
00211 { return _M_op(_M_value, __x); }
00212 };
00213
00214
00215
00216
00217
00218 template<typename _Operation, typename _FirstArgumentType,
00219 typename _SecondArgumentType, typename _ResultType>
00220 class __binder2nd
00221 : public std::unary_function<_FirstArgumentType, _ResultType>
00222 {
00223 protected:
00224 _Operation _M_op;
00225 _SecondArgumentType _M_value;
00226
00227 public:
00228 __binder2nd(const _Operation& __x, const _SecondArgumentType& __y)
00229 : _M_op(__x), _M_value(__y) { }
00230
00231 _ResultType
00232 operator()(const _FirstArgumentType& __x) const
00233 { return _M_op(__x, _M_value); }
00234
00235
00236
00237 _ResultType
00238 operator()(_FirstArgumentType& __x)
00239 { return _M_op(__x, _M_value); }
00240 };
00241
00242
00243 template<typename _T1, typename _T2>
00244 struct _EqualTo : std::binary_function<_T1, _T2, bool>
00245 {
00246 bool operator()(const _T1& __t1, const _T2& __t2) const
00247 { return __t1 == __t2; }
00248 };
00249
00250
00251 template<typename _T1, typename _T2>
00252 struct _Less : std::binary_function<_T1, _T2, bool>
00253 {
00254 bool
00255 operator()(const _T1& __t1, const _T2& __t2) const
00256 { return __t1 < __t2; }
00257
00258 bool
00259 operator()(const _T2& __t2, const _T1& __t1) const
00260 { return __t2 < __t1; }
00261 };
00262
00263
00264 template<typename _Tp>
00265 struct _Less<_Tp, _Tp>
00266 : public std::less<_Tp> { };
00267
00268
00269 template<typename _Tp1, typename _Tp2, typename _Result
00270 = __typeof__(*static_cast<_Tp1*>(NULL)
00271 + *static_cast<_Tp2*>(NULL))>
00272 struct _Plus : public std::binary_function<_Tp1, _Tp2, _Result>
00273 {
00274 _Result
00275 operator()(const _Tp1& __x, const _Tp2& __y) const
00276 { return __x + __y; }
00277 };
00278
00279
00280 template<typename _Tp>
00281 struct _Plus<_Tp, _Tp, _Tp>
00282 : public std::plus<_Tp> { };
00283
00284
00285 template<typename _Tp1, typename _Tp2, typename _Result
00286 = __typeof__(*static_cast<_Tp1*>(NULL)
00287 * *static_cast<_Tp2*>(NULL))>
00288 struct _Multiplies : public std::binary_function<_Tp1, _Tp2, _Result>
00289 {
00290 _Result
00291 operator()(const _Tp1& __x, const _Tp2& __y) const
00292 { return __x * __y; }
00293 };
00294
00295
00296 template<typename _Tp>
00297 struct _Multiplies<_Tp, _Tp, _Tp>
00298 : public std::multiplies<_Tp> { };
00299
00300
00301
00302
00303
00304
00305 template<typename _Tp, typename _DifferenceTp>
00306 class _PseudoSequenceIterator
00307 {
00308 public:
00309 typedef _DifferenceTp _DifferenceType;
00310
00311 _PseudoSequenceIterator(const _Tp& __val, _DifferenceType __pos)
00312 : _M_val(__val), _M_pos(__pos) { }
00313
00314
00315 _PseudoSequenceIterator&
00316 operator++()
00317 {
00318 ++_M_pos;
00319 return *this;
00320 }
00321
00322
00323 _PseudoSequenceIterator
00324 operator++(int)
00325 { return _PseudoSequenceIterator(_M_pos++); }
00326
00327 const _Tp&
00328 operator*() const
00329 { return _M_val; }
00330
00331 const _Tp&
00332 operator[](_DifferenceType) const
00333 { return _M_val; }
00334
00335 bool
00336 operator==(const _PseudoSequenceIterator& __i2)
00337 { return _M_pos == __i2._M_pos; }
00338
00339 bool
00340 operator!=(const _PseudoSequenceIterator& __i2)
00341 { return _M_pos != __i2._M_pos; }
00342
00343 _DifferenceType
00344 operator-(const _PseudoSequenceIterator& __i2)
00345 { return _M_pos - __i2._M_pos; }
00346
00347 private:
00348 const _Tp& _M_val;
00349 _DifferenceType _M_pos;
00350 };
00351
00352
00353
00354
00355
00356
00357
00358 template<typename _Tp, typename _DifferenceTp>
00359 class _PseudoSequence
00360 {
00361 public:
00362 typedef _DifferenceTp _DifferenceType;
00363
00364
00365 typedef _PseudoSequenceIterator<_Tp, uint64_t> iterator;
00366
00367
00368
00369
00370
00371 _PseudoSequence(const _Tp& __val, _DifferenceType __count)
00372 : _M_val(__val), _M_count(__count) { }
00373
00374
00375 iterator
00376 begin() const
00377 { return iterator(_M_val, 0); }
00378
00379
00380 iterator
00381 end() const
00382 { return iterator(_M_val, _M_count); }
00383
00384 private:
00385 const _Tp& _M_val;
00386 _DifferenceType _M_count;
00387 };
00388
00389
00390
00391
00392
00393
00394
00395
00396 template<typename _RAIter, typename _Compare>
00397 _RAIter
00398 __median_of_three_iterators(_RAIter __a, _RAIter __b,
00399 _RAIter __c, _Compare __comp)
00400 {
00401 if (__comp(*__a, *__b))
00402 if (__comp(*__b, *__c))
00403 return __b;
00404 else
00405 if (__comp(*__a, *__c))
00406 return __c;
00407 else
00408 return __a;
00409 else
00410 {
00411
00412 if (__comp(*__a, *__c))
00413 return __a;
00414 else
00415 if (__comp(*__b, *__c))
00416 return __c;
00417 else
00418 return __b;
00419 }
00420 }
00421
00422 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) __glibcxx_assert(_Condition)
00423
00424 }
00425
00426 #endif