33 #ifndef _GLIBCXX_PARALLEL_FIND_H
34 #define _GLIBCXX_PARALLEL_FIND_H 1
43 namespace __gnu_parallel
55 template<
typename RandomAccessIterator1,
56 typename RandomAccessIterator2,
61 RandomAccessIterator2 begin2, Pred pred, Selector selector)
68 case CONSTANT_SIZE_BLOCKS:
75 _GLIBCXX_PARALLEL_ASSERT(
false);
76 return std::make_pair(begin1, begin2);
80 #if _GLIBCXX_FIND_EQUAL_SPLIT
92 template<
typename RandomAccessIterator1,
93 typename RandomAccessIterator2,
98 RandomAccessIterator1 end1,
99 RandomAccessIterator2 begin2,
106 typedef std::iterator_traits<RandomAccessIterator1> traits_type;
107 typedef typename traits_type::difference_type difference_type;
108 typedef typename traits_type::value_type value_type;
110 difference_type length = end1 - begin1;
111 difference_type result = length;
112 difference_type* borders;
114 omp_lock_t result_lock;
115 omp_init_lock(&result_lock);
118 # pragma omp parallel num_threads(num_threads)
122 num_threads = omp_get_num_threads();
123 borders =
new difference_type[num_threads + 1];
128 difference_type start = borders[iam], stop = borders[iam + 1];
130 RandomAccessIterator1 i1 = begin1 + start;
131 RandomAccessIterator2 i2 = begin2 + start;
132 for (difference_type pos = start; pos < stop; ++pos)
134 #pragma omp flush(result)
139 if (selector(i1, i2, pred))
141 omp_set_lock(&result_lock);
144 omp_unset_lock(&result_lock);
152 omp_destroy_lock(&result_lock);
162 #if _GLIBCXX_FIND_GROWING_BLOCKS
186 template<
typename RandomAccessIterator1,
187 typename RandomAccessIterator2,
191 find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
192 RandomAccessIterator2 begin2, Pred pred, Selector selector,
197 typedef std::iterator_traits<RandomAccessIterator1> traits_type;
198 typedef typename traits_type::difference_type difference_type;
199 typedef typename traits_type::value_type value_type;
201 const _Settings& __s = _Settings::get();
203 difference_type length = end1 - begin1;
205 difference_type sequential_search_size =
206 std::
min<difference_type>(length, __s.find_sequential_search_size);
209 std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result =
210 selector.sequential_algorithm(
211 begin1, begin1 + sequential_search_size, begin2, pred);
213 if (find_seq_result.first != (begin1 + sequential_search_size))
214 return find_seq_result;
217 difference_type next_block_start = sequential_search_size;
218 difference_type result = length;
220 omp_lock_t result_lock;
221 omp_init_lock(&result_lock);
224 # pragma omp parallel shared(result) num_threads(num_threads)
227 num_threads = omp_get_num_threads();
232 difference_type block_size = __s.find_initial_block_size;
233 difference_type start =
234 fetch_and_add<difference_type>(&next_block_start, block_size);
237 difference_type stop =
238 std::min<difference_type>(length, start + block_size);
242 while (start < length)
244 # pragma omp flush(result)
252 local_result = selector.sequential_algorithm(
253 begin1 + start, begin1 + stop, begin2 + start, pred);
254 if (local_result.first != (begin1 + stop))
256 omp_set_lock(&result_lock);
257 if ((local_result.first - begin1) < result)
259 result = local_result.first - begin1;
262 fetch_and_add<difference_type>(&next_block_start, length);
264 omp_unset_lock(&result_lock);
268 std::min<difference_type>(block_size * __s.find_increasing_factor,
269 __s.find_maximum_block_size);
273 fetch_and_add<difference_type>(&next_block_start, block_size);
274 stop = ((length < (start + block_size))
275 ? length : (start + block_size));
279 omp_destroy_lock(&result_lock);
289 #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS
309 template<
typename RandomAccessIterator1,
310 typename RandomAccessIterator2,
314 find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
315 RandomAccessIterator2 begin2, Pred pred, Selector selector,
316 constant_size_blocks_tag)
319 typedef std::iterator_traits<RandomAccessIterator1> traits_type;
320 typedef typename traits_type::difference_type difference_type;
321 typedef typename traits_type::value_type value_type;
323 const _Settings& __s = _Settings::get();
325 difference_type length = end1 - begin1;
327 difference_type sequential_search_size = std::
min<difference_type>(
328 length, __s.find_sequential_search_size);
331 std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result =
332 selector.sequential_algorithm(begin1, begin1 + sequential_search_size,
335 if (find_seq_result.first != (begin1 + sequential_search_size))
336 return find_seq_result;
338 difference_type result = length;
339 omp_lock_t result_lock;
340 omp_init_lock(&result_lock);
345 # pragma omp parallel shared(result) num_threads(num_threads)
348 num_threads = omp_get_num_threads();
351 difference_type block_size = __s.find_initial_block_size;
354 difference_type iteration_start = sequential_search_size;
357 difference_type start = iteration_start + iam * block_size;
358 difference_type stop =
359 std::min<difference_type>(length, start + block_size);
363 while (start < length)
366 # pragma omp flush(result)
370 local_result = selector.sequential_algorithm(
371 begin1 + start, begin1 + stop,
372 begin2 + start, pred);
373 if (local_result.first != (begin1 + stop))
375 omp_set_lock(&result_lock);
376 if ((local_result.first - begin1) < result)
377 result = local_result.first - begin1;
378 omp_unset_lock(&result_lock);
383 iteration_start += num_threads * block_size;
386 start = iteration_start + iam * block_size;
387 stop = std::min<difference_type>(length, start + block_size);
391 omp_destroy_lock(&result_lock);