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