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 #ifndef _GLIBCXX_PARALLEL_PARTITION_H
00034 #define _GLIBCXX_PARALLEL_PARTITION_H 1
00035
00036 #include <parallel/basic_iterator.h>
00037 #include <parallel/sort.h>
00038 #include <parallel/random_number.h>
00039 #include <bits/stl_algo.h>
00040 #include <parallel/parallel.h>
00041
00042
00043 #define _GLIBCXX_VOLATILE volatile
00044
00045 namespace __gnu_parallel
00046 {
00047
00048
00049
00050
00051
00052
00053
00054 template<typename _RAIter, typename _Predicate>
00055 typename std::iterator_traits<_RAIter>::difference_type
00056 __parallel_partition(_RAIter __begin, _RAIter __end,
00057 _Predicate __pred, _ThreadIndex __num_threads)
00058 {
00059 typedef std::iterator_traits<_RAIter> _TraitsType;
00060 typedef typename _TraitsType::value_type _ValueType;
00061 typedef typename _TraitsType::difference_type _DifferenceType;
00062
00063 _DifferenceType __n = __end - __begin;
00064
00065 _GLIBCXX_CALL(__n)
00066
00067 const _Settings& __s = _Settings::get();
00068
00069
00070 _GLIBCXX_VOLATILE _DifferenceType __left = 0, __right = __n - 1,
00071 __dist = __n,
00072 __leftover_left, __leftover_right,
00073 __leftnew, __rightnew;
00074
00075
00076 int* __reserved_left = 0, * __reserved_right = 0;
00077
00078 _DifferenceType __chunk_size = __s.partition_chunk_size;
00079
00080
00081 if (__dist >= 2 * __num_threads * __chunk_size)
00082 # pragma omp parallel num_threads(__num_threads)
00083 {
00084 # pragma omp single
00085 {
00086 __num_threads = omp_get_num_threads();
00087 __reserved_left = new int[__num_threads];
00088 __reserved_right = new int[__num_threads];
00089
00090 if (__s.partition_chunk_share > 0.0)
00091 __chunk_size = std::max<_DifferenceType>
00092 (__s.partition_chunk_size, (double)__n
00093 * __s.partition_chunk_share / (double)__num_threads);
00094 else
00095 __chunk_size = __s.partition_chunk_size;
00096 }
00097
00098 while (__dist >= 2 * __num_threads * __chunk_size)
00099 {
00100 # pragma omp single
00101 {
00102 _DifferenceType __num_chunks = __dist / __chunk_size;
00103
00104 for (_ThreadIndex __r = 0; __r < __num_threads; ++__r)
00105 {
00106 __reserved_left [__r] = 0;
00107 __reserved_right[__r] = 0;
00108 }
00109 __leftover_left = 0;
00110 __leftover_right = 0;
00111 }
00112
00113
00114 _DifferenceType __thread_left, __thread_left_border,
00115 __thread_right, __thread_right_border;
00116
00117 __thread_left = __left + 1;
00118
00119 __thread_left_border = __thread_left - 1;
00120
00121 __thread_right = __n - 1;
00122
00123 __thread_right_border = __thread_right + 1;
00124
00125 bool __iam_finished = false;
00126 while (!__iam_finished)
00127 {
00128 if (__thread_left > __thread_left_border)
00129 {
00130 _DifferenceType __former_dist =
00131 __fetch_and_add(&__dist, -__chunk_size);
00132 if (__former_dist < __chunk_size)
00133 {
00134 __fetch_and_add(&__dist, __chunk_size);
00135 __iam_finished = true;
00136 break;
00137 }
00138 else
00139 {
00140 __thread_left =
00141 __fetch_and_add(&__left, __chunk_size);
00142 __thread_left_border =
00143 __thread_left + (__chunk_size - 1);
00144 }
00145 }
00146
00147 if (__thread_right < __thread_right_border)
00148 {
00149 _DifferenceType __former_dist =
00150 __fetch_and_add(&__dist, -__chunk_size);
00151 if (__former_dist < __chunk_size)
00152 {
00153 __fetch_and_add(&__dist, __chunk_size);
00154 __iam_finished = true;
00155 break;
00156 }
00157 else
00158 {
00159 __thread_right =
00160 __fetch_and_add(&__right, -__chunk_size);
00161 __thread_right_border =
00162 __thread_right - (__chunk_size - 1);
00163 }
00164 }
00165
00166
00167 while (__thread_left < __thread_right)
00168 {
00169 while (__pred(__begin[__thread_left])
00170 && __thread_left <= __thread_left_border)
00171 ++__thread_left;
00172 while (!__pred(__begin[__thread_right])
00173 && __thread_right >= __thread_right_border)
00174 --__thread_right;
00175
00176 if (__thread_left > __thread_left_border
00177 || __thread_right < __thread_right_border)
00178
00179 break;
00180
00181 std::iter_swap(__begin + __thread_left,
00182 __begin + __thread_right);
00183 ++__thread_left;
00184 --__thread_right;
00185 }
00186 }
00187
00188
00189 if (__thread_left <= __thread_left_border)
00190 # pragma omp atomic
00191 ++__leftover_left;
00192 if (__thread_right >= __thread_right_border)
00193 # pragma omp atomic
00194 ++__leftover_right;
00195
00196 # pragma omp barrier
00197
00198 _DifferenceType
00199 __leftold = __left,
00200 __leftnew = __left - __leftover_left * __chunk_size,
00201 __rightold = __right,
00202 __rightnew = __right + __leftover_right * __chunk_size;
00203
00204
00205 if (__thread_left <= __thread_left_border
00206 && __thread_left_border >= __leftnew)
00207 {
00208
00209 __reserved_left[(__left - (__thread_left_border + 1))
00210 / __chunk_size] = 1;
00211 }
00212
00213
00214 if (__thread_right >= __thread_right_border
00215 && __thread_right_border <= __rightnew)
00216 {
00217
00218 __reserved_right[((__thread_right_border - 1) - __right)
00219 / __chunk_size] = 1;
00220 }
00221
00222 # pragma omp barrier
00223
00224 if (__thread_left <= __thread_left_border
00225 && __thread_left_border < __leftnew)
00226 {
00227
00228 _DifferenceType __swapstart = -1;
00229 for (int __r = 0; __r < __leftover_left; ++__r)
00230 if (__reserved_left[__r] == 0
00231 && __compare_and_swap(&(__reserved_left[__r]), 0, 1))
00232 {
00233 __swapstart = __leftold - (__r + 1) * __chunk_size;
00234 break;
00235 }
00236
00237 #if _GLIBCXX_ASSERTIONS
00238 _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
00239 #endif
00240
00241 std::swap_ranges(__begin + __thread_left_border
00242 - (__chunk_size - 1),
00243 __begin + __thread_left_border + 1,
00244 __begin + __swapstart);
00245 }
00246
00247 if (__thread_right >= __thread_right_border
00248 && __thread_right_border > __rightnew)
00249 {
00250
00251 _DifferenceType __swapstart = -1;
00252 for (int __r = 0; __r < __leftover_right; ++__r)
00253 if (__reserved_right[__r] == 0
00254 && __compare_and_swap(&(__reserved_right[__r]), 0, 1))
00255 {
00256 __swapstart = __rightold + __r * __chunk_size + 1;
00257 break;
00258 }
00259
00260 #if _GLIBCXX_ASSERTIONS
00261 _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
00262 #endif
00263
00264 std::swap_ranges(__begin + __thread_right_border,
00265 __begin + __thread_right_border
00266 + __chunk_size, __begin + __swapstart);
00267 }
00268 #if _GLIBCXX_ASSERTIONS
00269 # pragma omp barrier
00270
00271 # pragma omp single
00272 {
00273 for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)
00274 _GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r] == 1);
00275 for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)
00276 _GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r] == 1);
00277 }
00278 #endif
00279
00280 __left = __leftnew;
00281 __right = __rightnew;
00282 __dist = __right - __left + 1;
00283 }
00284
00285 # pragma omp flush(__left, __right)
00286 }
00287
00288 _DifferenceType __final_left = __left, __final_right = __right;
00289
00290 while (__final_left < __final_right)
00291 {
00292
00293 while (__pred(__begin[__final_left])
00294 && __final_left < __final_right)
00295 ++__final_left;
00296
00297
00298 while (!__pred(__begin[__final_right])
00299 && __final_left < __final_right)
00300 --__final_right;
00301
00302 if (__final_left == __final_right)
00303 break;
00304 std::iter_swap(__begin + __final_left, __begin + __final_right);
00305 ++__final_left;
00306 --__final_right;
00307 }
00308
00309
00310
00311 delete[] __reserved_left;
00312 delete[] __reserved_right;
00313
00314
00315
00316 if (__final_left < __n && !__pred(__begin[__final_left]))
00317
00318 return __final_left;
00319 else
00320 return __final_left + 1;
00321 }
00322
00323
00324
00325
00326
00327
00328
00329
00330 template<typename _RAIter, typename _Compare>
00331 void
00332 __parallel_nth_element(_RAIter __begin, _RAIter __nth,
00333 _RAIter __end, _Compare __comp)
00334 {
00335 typedef std::iterator_traits<_RAIter> _TraitsType;
00336 typedef typename _TraitsType::value_type _ValueType;
00337 typedef typename _TraitsType::difference_type _DifferenceType;
00338
00339 _GLIBCXX_CALL(__end - __begin)
00340
00341 _RAIter __split;
00342 _RandomNumber __rng;
00343
00344 const _Settings& __s = _Settings::get();
00345 _DifferenceType __minimum_length = std::max<_DifferenceType>(2,
00346 std::max(__s.nth_element_minimal_n, __s.partition_minimal_n));
00347
00348
00349 while (static_cast<_SequenceIndex>(__end - __begin) >= __minimum_length)
00350 {
00351 _DifferenceType __n = __end - __begin;
00352
00353 _RAIter __pivot_pos = __begin + __rng(__n);
00354
00355
00356 if (__pivot_pos != (__end - 1))
00357 std::iter_swap(__pivot_pos, __end - 1);
00358 __pivot_pos = __end - 1;
00359
00360
00361
00362
00363
00364
00365
00366 __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool>
00367 __pred(__comp, *__pivot_pos);
00368
00369
00370 _RAIter __split_pos1, __split_pos2;
00371 __split_pos1 = __begin + __parallel_partition(__begin, __end - 1,
00372 __pred,
00373 __get_max_threads());
00374
00375
00376
00377
00378 if (__split_pos1 != __pivot_pos)
00379 std::iter_swap(__split_pos1, __pivot_pos);
00380 __pivot_pos = __split_pos1;
00381
00382
00383 if ((__split_pos1 + 1 - __begin) < (__n >> 7)
00384 || (__end - __split_pos1) < (__n >> 7))
00385 {
00386
00387
00388 __gnu_parallel::__unary_negate<__gnu_parallel::
00389 __binder1st<_Compare, _ValueType,
00390 _ValueType, bool>, _ValueType>
00391 __pred(__gnu_parallel::__binder1st<_Compare, _ValueType,
00392 _ValueType, bool>(__comp, *__pivot_pos));
00393
00394
00395 __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1,
00396 __end, __pred);
00397 }
00398 else
00399
00400 __split_pos2 = __split_pos1 + 1;
00401
00402
00403 if (__split_pos2 <= __nth)
00404 __begin = __split_pos2;
00405 else if (__nth < __split_pos1)
00406 __end = __split_pos1;
00407 else
00408 break;
00409 }
00410
00411
00412 __gnu_sequential::nth_element(__begin, __nth, __end, __comp);
00413 }
00414
00415
00416
00417
00418
00419
00420 template<typename _RAIter, typename _Compare>
00421 void
00422 __parallel_partial_sort(_RAIter __begin,
00423 _RAIter __middle,
00424 _RAIter __end, _Compare __comp)
00425 {
00426 __parallel_nth_element(__begin, __middle, __end, __comp);
00427 std::sort(__begin, __middle, __comp);
00428 }
00429
00430 }
00431
00432 #undef _GLIBCXX_VOLATILE
00433
00434 #endif