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 RandomAccessIterator1,
00056 typename RandomAccessIterator2,
00057 typename Pred,
00058 typename Selector>
00059 inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
00060 find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
00061 RandomAccessIterator2 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, selector,
00067 growing_blocks_tag());
00068 case CONSTANT_SIZE_BLOCKS:
00069 return find_template(begin1, end1, begin2, pred, selector,
00070 constant_size_blocks_tag());
00071 case EQUAL_SPLIT:
00072 return find_template(begin1, end1, begin2, pred, selector,
00073 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 RandomAccessIterator1,
00093 typename RandomAccessIterator2,
00094 typename Pred,
00095 typename Selector>
00096 std::pair<RandomAccessIterator1, RandomAccessIterator2>
00097 find_template(RandomAccessIterator1 begin1,
00098 RandomAccessIterator1 end1,
00099 RandomAccessIterator2 begin2,
00100 Pred pred,
00101 Selector selector,
00102 equal_split_tag)
00103 {
00104 _GLIBCXX_CALL(end1 - begin1)
00105
00106 typedef std::iterator_traits<RandomAccessIterator1> traits_type;
00107 typedef typename traits_type::difference_type difference_type;
00108 typedef typename traits_type::value_type value_type;
00109
00110 difference_type length = end1 - begin1;
00111 difference_type result = length;
00112 difference_type* borders;
00113
00114 omp_lock_t result_lock;
00115 omp_init_lock(&result_lock);
00116
00117 thread_index_t num_threads = get_max_threads();
00118 # pragma omp parallel num_threads(num_threads)
00119 {
00120 # pragma omp single
00121 {
00122 num_threads = omp_get_num_threads();
00123 borders = new difference_type[num_threads + 1];
00124 equally_split(length, num_threads, borders);
00125 }
00126
00127 thread_index_t iam = omp_get_thread_num();
00128 difference_type start = borders[iam], stop = borders[iam + 1];
00129
00130 RandomAccessIterator1 i1 = begin1 + start;
00131 RandomAccessIterator2 i2 = begin2 + start;
00132 for (difference_type pos = start; pos < stop; ++pos)
00133 {
00134 #pragma omp flush(result)
00135
00136 if (result < pos)
00137 break;
00138
00139 if (selector(i1, i2, pred))
00140 {
00141 omp_set_lock(&result_lock);
00142 if (pos < result)
00143 result = pos;
00144 omp_unset_lock(&result_lock);
00145 break;
00146 }
00147 ++i1;
00148 ++i2;
00149 }
00150 }
00151
00152 omp_destroy_lock(&result_lock);
00153 delete[] borders;
00154
00155 return
00156 std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result,
00157 begin2 + result);
00158 }
00159
00160 #endif
00161
00162 #if _GLIBCXX_FIND_GROWING_BLOCKS
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186 template<typename RandomAccessIterator1,
00187 typename RandomAccessIterator2,
00188 typename Pred,
00189 typename Selector>
00190 std::pair<RandomAccessIterator1, RandomAccessIterator2>
00191 find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
00192 RandomAccessIterator2 begin2, Pred pred, Selector selector,
00193 growing_blocks_tag)
00194 {
00195 _GLIBCXX_CALL(end1 - begin1)
00196
00197 typedef std::iterator_traits<RandomAccessIterator1> traits_type;
00198 typedef typename traits_type::difference_type difference_type;
00199 typedef typename traits_type::value_type value_type;
00200
00201 const _Settings& __s = _Settings::get();
00202
00203 difference_type length = end1 - begin1;
00204
00205 difference_type sequential_search_size =
00206 std::min<difference_type>(length, __s.find_sequential_search_size);
00207
00208
00209 std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result =
00210 selector.sequential_algorithm(
00211 begin1, begin1 + sequential_search_size, begin2, pred);
00212
00213 if (find_seq_result.first != (begin1 + sequential_search_size))
00214 return find_seq_result;
00215
00216
00217 difference_type next_block_start = sequential_search_size;
00218 difference_type result = length;
00219
00220 omp_lock_t result_lock;
00221 omp_init_lock(&result_lock);
00222
00223 thread_index_t num_threads = get_max_threads();
00224 # pragma omp parallel shared(result) num_threads(num_threads)
00225 {
00226 # pragma omp single
00227 num_threads = omp_get_num_threads();
00228
00229
00230 thread_index_t iam = omp_get_thread_num();
00231
00232 difference_type block_size = __s.find_initial_block_size;
00233 difference_type start =
00234 fetch_and_add<difference_type>(&next_block_start, block_size);
00235
00236
00237 difference_type stop =
00238 std::min<difference_type>(length, start + block_size);
00239
00240 std::pair<RandomAccessIterator1, RandomAccessIterator2> local_result;
00241
00242 while (start < length)
00243 {
00244 # pragma omp flush(result)
00245
00246 if (result < start)
00247 {
00248
00249 break;
00250 }
00251
00252 local_result = selector.sequential_algorithm(
00253 begin1 + start, begin1 + stop, begin2 + start, pred);
00254 if (local_result.first != (begin1 + stop))
00255 {
00256 omp_set_lock(&result_lock);
00257 if ((local_result.first - begin1) < result)
00258 {
00259 result = local_result.first - begin1;
00260
00261
00262 fetch_and_add<difference_type>(&next_block_start, length);
00263 }
00264 omp_unset_lock(&result_lock);
00265 }
00266
00267 block_size =
00268 std::min<difference_type>(block_size * __s.find_increasing_factor,
00269 __s.find_maximum_block_size);
00270
00271
00272 start =
00273 fetch_and_add<difference_type>(&next_block_start, block_size);
00274 stop = ((length < (start + block_size))
00275 ? length : (start + block_size));
00276 }
00277 }
00278
00279 omp_destroy_lock(&result_lock);
00280
00281
00282 return
00283 std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result,
00284 begin2 + result);
00285 }
00286
00287 #endif
00288
00289 #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309 template<typename RandomAccessIterator1,
00310 typename RandomAccessIterator2,
00311 typename Pred,
00312 typename Selector>
00313 std::pair<RandomAccessIterator1, RandomAccessIterator2>
00314 find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
00315 RandomAccessIterator2 begin2, Pred pred, Selector selector,
00316 constant_size_blocks_tag)
00317 {
00318 _GLIBCXX_CALL(end1 - begin1)
00319 typedef std::iterator_traits<RandomAccessIterator1> traits_type;
00320 typedef typename traits_type::difference_type difference_type;
00321 typedef typename traits_type::value_type value_type;
00322
00323 const _Settings& __s = _Settings::get();
00324
00325 difference_type length = end1 - begin1;
00326
00327 difference_type sequential_search_size = std::min<difference_type>(
00328 length, __s.find_sequential_search_size);
00329
00330
00331 std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result =
00332 selector.sequential_algorithm(begin1, begin1 + sequential_search_size,
00333 begin2, pred);
00334
00335 if (find_seq_result.first != (begin1 + sequential_search_size))
00336 return find_seq_result;
00337
00338 difference_type result = length;
00339 omp_lock_t result_lock;
00340 omp_init_lock(&result_lock);
00341
00342
00343
00344 thread_index_t num_threads = get_max_threads();
00345 # pragma omp parallel shared(result) num_threads(num_threads)
00346 {
00347 # pragma omp single
00348 num_threads = omp_get_num_threads();
00349
00350 thread_index_t iam = omp_get_thread_num();
00351 difference_type block_size = __s.find_initial_block_size;
00352
00353
00354 difference_type iteration_start = sequential_search_size;
00355
00356
00357 difference_type start = iteration_start + iam * block_size;
00358 difference_type stop =
00359 std::min<difference_type>(length, start + block_size);
00360
00361 std::pair<RandomAccessIterator1, RandomAccessIterator2> local_result;
00362
00363 while (start < length)
00364 {
00365
00366 # pragma omp flush(result)
00367
00368 if (result < start)
00369 break;
00370 local_result = selector.sequential_algorithm(
00371 begin1 + start, begin1 + stop,
00372 begin2 + start, pred);
00373 if (local_result.first != (begin1 + stop))
00374 {
00375 omp_set_lock(&result_lock);
00376 if ((local_result.first - begin1) < result)
00377 result = local_result.first - begin1;
00378 omp_unset_lock(&result_lock);
00379
00380 break;
00381 }
00382
00383 iteration_start += num_threads * block_size;
00384
00385
00386 start = iteration_start + iam * block_size;
00387 stop = std::min<difference_type>(length, start + block_size);
00388 }
00389 }
00390
00391 omp_destroy_lock(&result_lock);
00392
00393
00394 return
00395 std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result,
00396 begin2 + result);
00397 }
00398 #endif
00399 }
00400
00401 #endif