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_FIND_H
00034 #define _GLIBCXX_PARALLEL_FIND_H 1
00035
00036 #include <bits/stl_algobase.h>
00037
00038 #include <parallel/features.h>
00039 #include <parallel/parallel.h>
00040 #include <parallel/compatibility.h>
00041 #include <parallel/equally_split.h>
00042
00043 namespace __gnu_parallel
00044 {
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055 template<typename _RAIter1,
00056 typename _RAIter2,
00057 typename _Pred,
00058 typename _Selector>
00059 inline std::pair<_RAIter1, _RAIter2>
00060 __find_template(_RAIter1 __begin1, _RAIter1 __end1,
00061 _RAIter2 __begin2, _Pred __pred, _Selector __selector)
00062 {
00063 switch (_Settings::get().find_algorithm)
00064 {
00065 case GROWING_BLOCKS:
00066 return __find_template(__begin1, __end1, __begin2, __pred,
00067 __selector, growing_blocks_tag());
00068 case CONSTANT_SIZE_BLOCKS:
00069 return __find_template(__begin1, __end1, __begin2, __pred,
00070 __selector, constant_size_blocks_tag());
00071 case EQUAL_SPLIT:
00072 return __find_template(__begin1, __end1, __begin2, __pred,
00073 __selector, equal_split_tag());
00074 default:
00075 _GLIBCXX_PARALLEL_ASSERT(false);
00076 return std::make_pair(__begin1, __begin2);
00077 }
00078 }
00079
00080 #if _GLIBCXX_FIND_EQUAL_SPLIT
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092 template<typename _RAIter1,
00093 typename _RAIter2,
00094 typename _Pred,
00095 typename _Selector>
00096 std::pair<_RAIter1, _RAIter2>
00097 __find_template(_RAIter1 __begin1, _RAIter1 __end1,
00098 _RAIter2 __begin2, _Pred __pred,
00099 _Selector __selector, equal_split_tag)
00100 {
00101 _GLIBCXX_CALL(__end1 - __begin1)
00102
00103 typedef std::iterator_traits<_RAIter1> _TraitsType;
00104 typedef typename _TraitsType::difference_type _DifferenceType;
00105 typedef typename _TraitsType::value_type _ValueType;
00106
00107 _DifferenceType __length = __end1 - __begin1;
00108 _DifferenceType __result = __length;
00109 _DifferenceType* __borders;
00110
00111 omp_lock_t __result_lock;
00112 omp_init_lock(&__result_lock);
00113
00114 _ThreadIndex __num_threads = __get_max_threads();
00115 # pragma omp parallel num_threads(__num_threads)
00116 {
00117 # pragma omp single
00118 {
00119 __num_threads = omp_get_num_threads();
00120 __borders = new _DifferenceType[__num_threads + 1];
00121 equally_split(__length, __num_threads, __borders);
00122 }
00123
00124 _ThreadIndex __iam = omp_get_thread_num();
00125 _DifferenceType __start = __borders[__iam],
00126 __stop = __borders[__iam + 1];
00127
00128 _RAIter1 __i1 = __begin1 + __start;
00129 _RAIter2 __i2 = __begin2 + __start;
00130 for (_DifferenceType __pos = __start; __pos < __stop; ++__pos)
00131 {
00132 # pragma omp flush(__result)
00133
00134 if (__result < __pos)
00135 break;
00136
00137 if (__selector(__i1, __i2, __pred))
00138 {
00139 omp_set_lock(&__result_lock);
00140 if (__pos < __result)
00141 __result = __pos;
00142 omp_unset_lock(&__result_lock);
00143 break;
00144 }
00145 ++__i1;
00146 ++__i2;
00147 }
00148 }
00149
00150 omp_destroy_lock(&__result_lock);
00151 delete[] __borders;
00152
00153 return std::pair<_RAIter1, _RAIter2>(__begin1 + __result,
00154 __begin2 + __result);
00155 }
00156
00157 #endif
00158
00159 #if _GLIBCXX_FIND_GROWING_BLOCKS
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180 template<typename _RAIter1,
00181 typename _RAIter2,
00182 typename _Pred,
00183 typename _Selector>
00184 std::pair<_RAIter1, _RAIter2>
00185 __find_template(_RAIter1 __begin1, _RAIter1 __end1,
00186 _RAIter2 __begin2, _Pred __pred, _Selector __selector,
00187 growing_blocks_tag)
00188 {
00189 _GLIBCXX_CALL(__end1 - __begin1)
00190
00191 typedef std::iterator_traits<_RAIter1> _TraitsType;
00192 typedef typename _TraitsType::difference_type _DifferenceType;
00193 typedef typename _TraitsType::value_type _ValueType;
00194
00195 const _Settings& __s = _Settings::get();
00196
00197 _DifferenceType __length = __end1 - __begin1;
00198
00199 _DifferenceType
00200 __sequential_search_size = std::min<_DifferenceType>
00201 (__length, __s.find_sequential_search_size);
00202
00203
00204 std::pair<_RAIter1, _RAIter2>
00205 __find_seq_result = __selector._M_sequential_algorithm
00206 (__begin1, __begin1 + __sequential_search_size,
00207 __begin2, __pred);
00208
00209 if (__find_seq_result.first != (__begin1 + __sequential_search_size))
00210 return __find_seq_result;
00211
00212
00213 _DifferenceType __next_block_start = __sequential_search_size;
00214 _DifferenceType __result = __length;
00215
00216 omp_lock_t __result_lock;
00217 omp_init_lock(&__result_lock);
00218
00219 const float __scale_factor = __s.find_scale_factor;
00220
00221 _ThreadIndex __num_threads = __get_max_threads();
00222 # pragma omp parallel shared(__result) num_threads(__num_threads)
00223 {
00224 # pragma omp single
00225 __num_threads = omp_get_num_threads();
00226
00227
00228 _ThreadIndex __iam = omp_get_thread_num();
00229
00230 _DifferenceType __block_size =
00231 std::max<_DifferenceType>(1, __scale_factor * __next_block_start);
00232 _DifferenceType __start = __fetch_and_add<_DifferenceType>
00233 (&__next_block_start, __block_size);
00234
00235
00236 _DifferenceType __stop =
00237 std::min<_DifferenceType>(__length, __start + __block_size);
00238
00239 std::pair<_RAIter1, _RAIter2> __local_result;
00240
00241 while (__start < __length)
00242 {
00243 # pragma omp flush(__result)
00244
00245 if (__result < __start)
00246 {
00247
00248 break;
00249 }
00250
00251 __local_result = __selector._M_sequential_algorithm
00252 (__begin1 + __start, __begin1 + __stop,
00253 __begin2 + __start, __pred);
00254
00255 if (__local_result.first != (__begin1 + __stop))
00256 {
00257 omp_set_lock(&__result_lock);
00258 if ((__local_result.first - __begin1) < __result)
00259 {
00260 __result = __local_result.first - __begin1;
00261
00262
00263 __fetch_and_add<_DifferenceType>(&__next_block_start,
00264 __length);
00265 }
00266 omp_unset_lock(&__result_lock);
00267 }
00268
00269 _DifferenceType __block_size =
00270 std::max<_DifferenceType>(1, __scale_factor * __next_block_start);
00271
00272
00273 __start = __fetch_and_add<_DifferenceType>(&__next_block_start,
00274 __block_size);
00275 __stop =
00276 std::min<_DifferenceType>(__length, __start + __block_size);
00277 }
00278 }
00279
00280 omp_destroy_lock(&__result_lock);
00281
00282
00283 return
00284 std::pair<_RAIter1, _RAIter2>(__begin1 + __result,
00285 __begin2 + __result);
00286 }
00287
00288 #endif
00289
00290 #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310 template<typename _RAIter1,
00311 typename _RAIter2,
00312 typename _Pred,
00313 typename _Selector>
00314 std::pair<_RAIter1, _RAIter2>
00315 __find_template(_RAIter1 __begin1, _RAIter1 __end1,
00316 _RAIter2 __begin2, _Pred __pred, _Selector __selector,
00317 constant_size_blocks_tag)
00318 {
00319 _GLIBCXX_CALL(__end1 - __begin1)
00320 typedef std::iterator_traits<_RAIter1> _TraitsType;
00321 typedef typename _TraitsType::difference_type _DifferenceType;
00322 typedef typename _TraitsType::value_type _ValueType;
00323
00324 const _Settings& __s = _Settings::get();
00325
00326 _DifferenceType __length = __end1 - __begin1;
00327
00328 _DifferenceType __sequential_search_size = std::min<_DifferenceType>
00329 (__length, __s.find_sequential_search_size);
00330
00331
00332 std::pair<_RAIter1, _RAIter2>
00333 __find_seq_result = __selector._M_sequential_algorithm
00334 (__begin1, __begin1 + __sequential_search_size, __begin2, __pred);
00335
00336 if (__find_seq_result.first != (__begin1 + __sequential_search_size))
00337 return __find_seq_result;
00338
00339 _DifferenceType __result = __length;
00340 omp_lock_t __result_lock;
00341 omp_init_lock(&__result_lock);
00342
00343
00344
00345 _ThreadIndex __num_threads = __get_max_threads();
00346 # pragma omp parallel shared(__result) num_threads(__num_threads)
00347 {
00348 # pragma omp single
00349 __num_threads = omp_get_num_threads();
00350
00351 _ThreadIndex __iam = omp_get_thread_num();
00352 _DifferenceType __block_size = __s.find_initial_block_size;
00353
00354
00355 _DifferenceType __iteration_start = __sequential_search_size;
00356
00357
00358 _DifferenceType __start = __iteration_start + __iam * __block_size;
00359 _DifferenceType __stop = std::min<_DifferenceType>(__length,
00360 __start
00361 + __block_size);
00362
00363 std::pair<_RAIter1, _RAIter2> __local_result;
00364
00365 while (__start < __length)
00366 {
00367
00368 # pragma omp flush(__result)
00369
00370 if (__result < __start)
00371 break;
00372
00373 __local_result = __selector._M_sequential_algorithm
00374 (__begin1 + __start, __begin1 + __stop,
00375 __begin2 + __start, __pred);
00376
00377 if (__local_result.first != (__begin1 + __stop))
00378 {
00379 omp_set_lock(&__result_lock);
00380 if ((__local_result.first - __begin1) < __result)
00381 __result = __local_result.first - __begin1;
00382 omp_unset_lock(&__result_lock);
00383
00384 break;
00385 }
00386
00387 __iteration_start += __num_threads * __block_size;
00388
00389
00390 __start = __iteration_start + __iam * __block_size;
00391 __stop = std::min<_DifferenceType>(__length,
00392 __start + __block_size);
00393 }
00394 }
00395
00396 omp_destroy_lock(&__result_lock);
00397
00398
00399 return std::pair<_RAIter1, _RAIter2>(__begin1 + __result,
00400 __begin2 + __result);
00401 }
00402 #endif
00403 }
00404
00405 #endif