3 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 2, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 /** @file parallel/find.h
32 * @brief Parallel implementation base for std::find(), std::equal()
33 * and related functions.
34 * This file is a GNU parallel extension to the Standard C++ Library.
37 // Written by Felix Putze and Johannes Singler.
39 #ifndef _GLIBCXX_PARALLEL_FIND_H
40 #define _GLIBCXX_PARALLEL_FIND_H 1
42 #include <bits/stl_algobase.h>
44 #include <parallel/features.h>
45 #include <parallel/parallel.h>
46 #include <parallel/compatibility.h>
47 #include <parallel/equally_split.h>
49 namespace __gnu_parallel
52 * @brief Parallel std::find, switch for different algorithms.
53 * @param begin1 Begin iterator of first sequence.
54 * @param end1 End iterator of first sequence.
55 * @param begin2 Begin iterator of second sequence. Must have same
56 * length as first sequence.
57 * @param pred Find predicate.
58 * @param selector Functionality (e. g. std::find_if (), std::equal(),...)
59 * @return Place of finding in both sequences.
61 template<typename RandomAccessIterator1
,
62 typename RandomAccessIterator2
,
65 inline std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
66 find_template(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
,
67 RandomAccessIterator2 begin2
, Pred pred
, Selector selector
)
69 switch (_Settings::get().find_algorithm
)
72 return find_template(begin1
, end1
, begin2
, pred
, selector
,
73 growing_blocks_tag());
74 case CONSTANT_SIZE_BLOCKS
:
75 return find_template(begin1
, end1
, begin2
, pred
, selector
,
76 constant_size_blocks_tag());
78 return find_template(begin1
, end1
, begin2
, pred
, selector
,
81 _GLIBCXX_PARALLEL_ASSERT(false);
82 return std::make_pair(begin1
, begin2
);
86 #if _GLIBCXX_FIND_EQUAL_SPLIT
89 * @brief Parallel std::find, equal splitting variant.
90 * @param begin1 Begin iterator of first sequence.
91 * @param end1 End iterator of first sequence.
92 * @param begin2 Begin iterator of second sequence. Second sequence
93 * must have same length as first sequence.
94 * @param pred Find predicate.
95 * @param selector Functionality (e. g. std::find_if (), std::equal(),...)
96 * @return Place of finding in both sequences.
98 template<typename RandomAccessIterator1
,
99 typename RandomAccessIterator2
,
102 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
103 find_template(RandomAccessIterator1 begin1
,
104 RandomAccessIterator1 end1
,
105 RandomAccessIterator2 begin2
,
110 _GLIBCXX_CALL(end1
- begin1
)
112 typedef std::iterator_traits
<RandomAccessIterator1
> traits_type
;
113 typedef typename
traits_type::difference_type difference_type
;
114 typedef typename
traits_type::value_type value_type
;
116 difference_type length
= end1
- begin1
;
117 difference_type result
= length
;
118 difference_type
* borders
;
120 omp_lock_t result_lock
;
121 omp_init_lock(&result_lock
);
123 thread_index_t num_threads
= get_max_threads();
124 # pragma omp parallel num_threads(num_threads)
128 num_threads
= omp_get_num_threads();
129 borders
= new difference_type
[num_threads
+ 1];
130 equally_split(length
, num_threads
, borders
);
133 thread_index_t iam
= omp_get_thread_num();
134 difference_type start
= borders
[iam
], stop
= borders
[iam
+ 1];
136 RandomAccessIterator1 i1
= begin1
+ start
;
137 RandomAccessIterator2 i2
= begin2
+ start
;
138 for (difference_type pos
= start
; pos
< stop
; ++pos
)
140 #pragma omp flush(result)
141 // Result has been set to something lower.
145 if (selector(i1
, i2
, pred
))
147 omp_set_lock(&result_lock
);
150 omp_unset_lock(&result_lock
);
158 omp_destroy_lock(&result_lock
);
162 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>(begin1
+ result
,
168 #if _GLIBCXX_FIND_GROWING_BLOCKS
171 * @brief Parallel std::find, growing block size variant.
172 * @param begin1 Begin iterator of first sequence.
173 * @param end1 End iterator of first sequence.
174 * @param begin2 Begin iterator of second sequence. Second sequence
175 * must have same length as first sequence.
176 * @param pred Find predicate.
177 * @param selector Functionality (e. g. std::find_if (), std::equal(),...)
178 * @return Place of finding in both sequences.
179 * @see __gnu_parallel::_Settings::find_sequential_search_size
180 * @see __gnu_parallel::_Settings::find_initial_block_size
181 * @see __gnu_parallel::_Settings::find_maximum_block_size
182 * @see __gnu_parallel::_Settings::find_increasing_factor
184 * There are two main differences between the growing blocks and
185 * the constant-size blocks variants.
186 * 1. For GB, the block size grows; for CSB, the block size is fixed.
188 * 2. For GB, the blocks are allocated dynamically;
189 * for CSB, the blocks are allocated in a predetermined manner,
190 * namely spacial round-robin.
192 template<typename RandomAccessIterator1
,
193 typename RandomAccessIterator2
,
196 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
197 find_template(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
,
198 RandomAccessIterator2 begin2
, Pred pred
, Selector selector
,
201 _GLIBCXX_CALL(end1
- begin1
)
203 typedef std::iterator_traits
<RandomAccessIterator1
> traits_type
;
204 typedef typename
traits_type::difference_type difference_type
;
205 typedef typename
traits_type::value_type value_type
;
207 const _Settings
& __s
= _Settings::get();
209 difference_type length
= end1
- begin1
;
211 difference_type sequential_search_size
=
212 std::min
<difference_type
>(length
, __s
.find_sequential_search_size
);
214 // Try it sequentially first.
215 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
> find_seq_result
=
216 selector
.sequential_algorithm(
217 begin1
, begin1
+ sequential_search_size
, begin2
, pred
);
219 if (find_seq_result
.first
!= (begin1
+ sequential_search_size
))
220 return find_seq_result
;
222 // Index of beginning of next free block (after sequential find).
223 difference_type next_block_start
= sequential_search_size
;
224 difference_type result
= length
;
226 omp_lock_t result_lock
;
227 omp_init_lock(&result_lock
);
229 thread_index_t num_threads
= get_max_threads();
230 # pragma omp parallel shared(result) num_threads(num_threads)
233 num_threads
= omp_get_num_threads();
235 // Not within first k elements -> start parallel.
236 thread_index_t iam
= omp_get_thread_num();
238 difference_type block_size
= __s
.find_initial_block_size
;
239 difference_type start
=
240 fetch_and_add
<difference_type
>(&next_block_start
, block_size
);
242 // Get new block, update pointer to next block.
243 difference_type stop
=
244 std::min
<difference_type
>(length
, start
+ block_size
);
246 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
> local_result
;
248 while (start
< length
)
250 # pragma omp flush(result)
251 // Get new value of result.
254 // No chance to find first element.
258 local_result
= selector
.sequential_algorithm(
259 begin1
+ start
, begin1
+ stop
, begin2
+ start
, pred
);
260 if (local_result
.first
!= (begin1
+ stop
))
262 omp_set_lock(&result_lock
);
263 if ((local_result
.first
- begin1
) < result
)
265 result
= local_result
.first
- begin1
;
267 // Result cannot be in future blocks, stop algorithm.
268 fetch_and_add
<difference_type
>(&next_block_start
, length
);
270 omp_unset_lock(&result_lock
);
274 std::min
<difference_type
>(block_size
* __s
.find_increasing_factor
,
275 __s
.find_maximum_block_size
);
277 // Get new block, update pointer to next block.
279 fetch_and_add
<difference_type
>(&next_block_start
, block_size
);
280 stop
= ((length
< (start
+ block_size
))
281 ? length
: (start
+ block_size
));
285 omp_destroy_lock(&result_lock
);
287 // Return iterator on found element.
289 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>(begin1
+ result
,
295 #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS
298 * @brief Parallel std::find, constant block size variant.
299 * @param begin1 Begin iterator of first sequence.
300 * @param end1 End iterator of first sequence.
301 * @param begin2 Begin iterator of second sequence. Second sequence
302 * must have same length as first sequence.
303 * @param pred Find predicate.
304 * @param selector Functionality (e. g. std::find_if (), std::equal(),...)
305 * @return Place of finding in both sequences.
306 * @see __gnu_parallel::_Settings::find_sequential_search_size
307 * @see __gnu_parallel::_Settings::find_block_size
308 * There are two main differences between the growing blocks and the
309 * constant-size blocks variants.
310 * 1. For GB, the block size grows; for CSB, the block size is fixed.
311 * 2. For GB, the blocks are allocated dynamically; for CSB, the
312 * blocks are allocated in a predetermined manner, namely spacial
315 template<typename RandomAccessIterator1
,
316 typename RandomAccessIterator2
,
319 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
320 find_template(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
,
321 RandomAccessIterator2 begin2
, Pred pred
, Selector selector
,
322 constant_size_blocks_tag
)
324 _GLIBCXX_CALL(end1
- begin1
)
325 typedef std::iterator_traits
<RandomAccessIterator1
> traits_type
;
326 typedef typename
traits_type::difference_type difference_type
;
327 typedef typename
traits_type::value_type value_type
;
329 const _Settings
& __s
= _Settings::get();
331 difference_type length
= end1
- begin1
;
333 difference_type sequential_search_size
= std::min
<difference_type
>(
334 length
, __s
.find_sequential_search_size
);
336 // Try it sequentially first.
337 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
> find_seq_result
=
338 selector
.sequential_algorithm(begin1
, begin1
+ sequential_search_size
,
341 if (find_seq_result
.first
!= (begin1
+ sequential_search_size
))
342 return find_seq_result
;
344 difference_type result
= length
;
345 omp_lock_t result_lock
;
346 omp_init_lock(&result_lock
);
348 // Not within first sequential_search_size elements -> start parallel.
350 thread_index_t num_threads
= get_max_threads();
351 # pragma omp parallel shared(result) num_threads(num_threads)
354 num_threads
= omp_get_num_threads();
356 thread_index_t iam
= omp_get_thread_num();
357 difference_type block_size
= __s
.find_initial_block_size
;
359 // First element of thread's current iteration.
360 difference_type iteration_start
= sequential_search_size
;
362 // Where to work (initialization).
363 difference_type start
= iteration_start
+ iam
* block_size
;
364 difference_type stop
=
365 std::min
<difference_type
>(length
, start
+ block_size
);
367 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
> local_result
;
369 while (start
< length
)
371 // Get new value of result.
372 # pragma omp flush(result)
373 // No chance to find first element.
376 local_result
= selector
.sequential_algorithm(
377 begin1
+ start
, begin1
+ stop
,
378 begin2
+ start
, pred
);
379 if (local_result
.first
!= (begin1
+ stop
))
381 omp_set_lock(&result_lock
);
382 if ((local_result
.first
- begin1
) < result
)
383 result
= local_result
.first
- begin1
;
384 omp_unset_lock(&result_lock
);
385 // Will not find better value in its interval.
389 iteration_start
+= num_threads
* block_size
;
392 start
= iteration_start
+ iam
* block_size
;
393 stop
= std::min
<difference_type
>(length
, start
+ block_size
);
397 omp_destroy_lock(&result_lock
);
399 // Return iterator on found element.
401 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>(begin1
+ result
,