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
00033
00034
00035
00036
00037
00038 #ifndef _GLIBCXX_PARALLEL_BASE_H
00039 #define _GLIBCXX_PARALLEL_BASE_H 1
00040
00041 #include <cstdio>
00042 #include <functional>
00043 #include <omp.h>
00044 #include <parallel/features.h>
00045 #include <parallel/basic_iterator.h>
00046 #include <parallel/parallel.h>
00047
00048
00049
00050
00051
00052
00053
00054
00055 namespace std
00056 {
00057 namespace __parallel { }
00058 }
00059
00060
00061
00062
00063
00064 namespace __gnu_parallel
00065 {
00066
00067 using namespace std::__parallel;
00068 }
00069
00070
00071
00072
00073
00074 namespace __gnu_sequential
00075 {
00076
00077 #ifdef _GLIBCXX_PARALLEL
00078 using namespace std::__norm;
00079 #else
00080 using namespace std;
00081 #endif
00082 }
00083
00084
00085 namespace __gnu_parallel
00086 {
00087
00088
00089
00090
00091 inline int
00092 get_max_threads()
00093 {
00094 int __i = omp_get_max_threads();
00095 return __i > 1 ? __i : 1;
00096 }
00097
00098
00099 inline bool
00100 is_parallel(const _Parallelism __p) { return __p != sequential; }
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110 template<typename Size>
00111 inline Size
00112 log2(Size n)
00113 {
00114 Size k;
00115 for (k = 0; n != 1; n >>= 1)
00116 ++k;
00117 return k;
00118 }
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128 inline lcas_t
00129 encode2(int a, int b)
00130 {
00131 return (((lcas_t)a) << (lcas_t_bits / 2)) | (((lcas_t)b) << 0);
00132 }
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142 inline void
00143 decode2(lcas_t x, int& a, int& b)
00144 {
00145 a = (int)((x >> (lcas_t_bits / 2)) & lcas_t_mask);
00146 b = (int)((x >> 0 ) & lcas_t_mask);
00147 }
00148
00149
00150 template<typename T>
00151 const T&
00152 min(const T& a, const T& b)
00153 { return (a < b) ? a : b; }
00154
00155
00156 template<typename T>
00157 const T&
00158 max(const T& a, const T& b)
00159 { return (a > b) ? a : b; }
00160
00161
00162
00163
00164
00165 template<typename Comparator, typename T1, typename T2>
00166 class equal_from_less : public std::binary_function<T1, T2, bool>
00167 {
00168 private:
00169 Comparator& comp;
00170
00171 public:
00172 equal_from_less(Comparator& _comp) : comp(_comp) { }
00173
00174 bool operator()(const T1& a, const T2& b)
00175 {
00176 return !comp(a, b) && !comp(b, a);
00177 }
00178 };
00179
00180
00181
00182
00183 template<typename _Predicate, typename argument_type>
00184 class unary_negate
00185 : public std::unary_function<argument_type, bool>
00186 {
00187 protected:
00188 _Predicate _M_pred;
00189
00190 public:
00191 explicit
00192 unary_negate(const _Predicate& __x) : _M_pred(__x) { }
00193
00194 bool
00195 operator()(const argument_type& __x)
00196 { return !_M_pred(__x); }
00197 };
00198
00199
00200
00201 template<typename _Operation, typename first_argument_type,
00202 typename second_argument_type, typename result_type>
00203 class binder1st
00204 : public std::unary_function<second_argument_type, result_type>
00205 {
00206 protected:
00207 _Operation op;
00208 first_argument_type value;
00209
00210 public:
00211 binder1st(const _Operation& __x,
00212 const first_argument_type& __y)
00213 : op(__x), value(__y) { }
00214
00215 result_type
00216 operator()(const second_argument_type& __x)
00217 { return op(value, __x); }
00218
00219
00220
00221 result_type
00222 operator()(second_argument_type& __x) const
00223 { return op(value, __x); }
00224 };
00225
00226
00227
00228
00229
00230 template<typename _Operation, typename first_argument_type,
00231 typename second_argument_type, typename result_type>
00232 class binder2nd
00233 : public std::unary_function<first_argument_type, result_type>
00234 {
00235 protected:
00236 _Operation op;
00237 second_argument_type value;
00238
00239 public:
00240 binder2nd(const _Operation& __x,
00241 const second_argument_type& __y)
00242 : op(__x), value(__y) { }
00243
00244 result_type
00245 operator()(const first_argument_type& __x) const
00246 { return op(__x, value); }
00247
00248
00249
00250 result_type
00251 operator()(first_argument_type& __x)
00252 { return op(__x, value); }
00253 };
00254
00255
00256 template<typename T1, typename T2>
00257 struct equal_to : std::binary_function<T1, T2, bool>
00258 {
00259 bool operator()(const T1& t1, const T2& t2) const
00260 { return t1 == t2; }
00261 };
00262
00263
00264 template<typename T1, typename T2>
00265 struct less : std::binary_function<T1, T2, bool>
00266 {
00267 bool
00268 operator()(const T1& t1, const T2& t2) const
00269 { return t1 < t2; }
00270
00271 bool
00272 operator()(const T2& t2, const T1& t1) const
00273 { return t2 < t1; }
00274 };
00275
00276
00277 template<typename _Tp>
00278 struct less<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, bool>
00279 {
00280 bool
00281 operator()(const _Tp& __x, const _Tp& __y) const
00282 { return __x < __y; }
00283 };
00284
00285
00286
00287 template<typename _Tp1, typename _Tp2>
00288 struct plus : public std::binary_function<_Tp1, _Tp2, _Tp1>
00289 {
00290 typedef typeof(*static_cast<_Tp1*>(NULL)
00291 + *static_cast<_Tp2*>(NULL)) result;
00292
00293 result
00294 operator()(const _Tp1& __x, const _Tp2& __y) const
00295 { return __x + __y; }
00296 };
00297
00298
00299 template<typename _Tp>
00300 struct plus<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
00301 {
00302 typedef typeof(*static_cast<_Tp*>(NULL)
00303 + *static_cast<_Tp*>(NULL)) result;
00304
00305 result
00306 operator()(const _Tp& __x, const _Tp& __y) const
00307 { return __x + __y; }
00308 };
00309
00310
00311
00312 template<typename _Tp1, typename _Tp2>
00313 struct multiplies : public std::binary_function<_Tp1, _Tp2, _Tp1>
00314 {
00315 typedef typeof(*static_cast<_Tp1*>(NULL)
00316 * *static_cast<_Tp2*>(NULL)) result;
00317
00318 result
00319 operator()(const _Tp1& __x, const _Tp2& __y) const
00320 { return __x * __y; }
00321 };
00322
00323
00324 template<typename _Tp>
00325 struct multiplies<_Tp, _Tp> : public std::binary_function<_Tp, _Tp, _Tp>
00326 {
00327 typedef typeof(*static_cast<_Tp*>(NULL)
00328 * *static_cast<_Tp*>(NULL)) result;
00329
00330 result
00331 operator()(const _Tp& __x, const _Tp& __y) const
00332 { return __x * __y; }
00333 };
00334
00335
00336 template<typename T, typename _DifferenceTp>
00337 class pseudo_sequence;
00338
00339
00340
00341
00342
00343
00344 template<typename T, typename _DifferenceTp>
00345 class pseudo_sequence_iterator
00346 {
00347 public:
00348 typedef _DifferenceTp difference_type;
00349
00350 private:
00351 typedef pseudo_sequence_iterator<T, _DifferenceTp> type;
00352
00353 const T& val;
00354 difference_type pos;
00355
00356 public:
00357 pseudo_sequence_iterator(const T& val, difference_type pos)
00358 : val(val), pos(pos) { }
00359
00360
00361 type&
00362 operator++()
00363 {
00364 ++pos;
00365 return *this;
00366 }
00367
00368
00369 const type
00370 operator++(int)
00371 { return type(pos++); }
00372
00373 const T&
00374 operator*() const
00375 { return val; }
00376
00377 const T&
00378 operator[](difference_type) const
00379 { return val; }
00380
00381 bool
00382 operator==(const type& i2)
00383 { return pos == i2.pos; }
00384
00385 difference_type
00386 operator!=(const type& i2)
00387 { return pos != i2.pos; }
00388
00389 difference_type
00390 operator-(const type& i2)
00391 { return pos - i2.pos; }
00392 };
00393
00394
00395
00396
00397
00398
00399
00400 template<typename T, typename _DifferenceTp>
00401 class pseudo_sequence
00402 {
00403 typedef pseudo_sequence<T, _DifferenceTp> type;
00404
00405 public:
00406 typedef _DifferenceTp difference_type;
00407
00408
00409 typedef pseudo_sequence_iterator<T, uint64> iterator;
00410
00411
00412
00413
00414
00415 pseudo_sequence(const T& val, difference_type count)
00416 : val(val), count(count) { }
00417
00418
00419 iterator
00420 begin() const
00421 { return iterator(val, 0); }
00422
00423
00424 iterator
00425 end() const
00426 { return iterator(val, count); }
00427
00428 private:
00429 const T& val;
00430 difference_type count;
00431 };
00432
00433
00434 template<typename _ValueTp>
00435 class void_functor
00436 {
00437 inline void
00438 operator()(const _ValueTp& v) const { }
00439 };
00440
00441
00442
00443
00444
00445
00446
00447
00448 template<typename RandomAccessIterator, typename Comparator>
00449 RandomAccessIterator
00450 median_of_three_iterators(RandomAccessIterator a, RandomAccessIterator b,
00451 RandomAccessIterator c, Comparator& comp)
00452 {
00453 if (comp(*a, *b))
00454 if (comp(*b, *c))
00455 return b;
00456 else
00457 if (comp(*a, *c))
00458 return c;
00459 else
00460 return a;
00461 else
00462 {
00463
00464 if (comp(*a, *c))
00465 return a;
00466 else
00467 if (comp(*b, *c))
00468 return c;
00469 else
00470 return b;
00471 }
00472 }
00473
00474
00475
00476 inline void
00477 __replacement_assert(const char* __file, int __line,
00478 const char* __function, const char* __condition)
00479 {
00480 std::printf("%s:%d: %s: Assertion '%s' failed.\n", __file, __line,
00481 __function, __condition);
00482 __builtin_abort();
00483 }
00484
00485 #define _GLIBCXX_PARALLEL_ASSERT(_Condition) \
00486 do \
00487 { \
00488 if (!(_Condition)) \
00489 __gnu_parallel::__replacement_assert(__FILE__, __LINE__, \
00490 __PRETTY_FUNCTION__, #_Condition); \
00491 } while (false)
00492
00493 }
00494
00495 #endif