]>
Commit | Line | Data |
---|---|---|
94dabea7 | 1 | // -*- C++ -*- |
c2ba9709 | 2 | |
7adcbafe | 3 | // Copyright (C) 2007-2022 Free Software Foundation, Inc. |
c2ba9709 JS |
4 | // |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
c2ba9709 JS |
9 | // version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
28dac70a | 13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
c2ba9709 JS |
14 | // General Public License for more details. |
15 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
c2ba9709 JS |
24 | |
25 | /** @file parallel/find.h | |
4459d22e | 26 | * @brief Parallel implementation base for std::find(), std::equal() |
c2ba9709 JS |
27 | * and related functions. |
28 | * This file is a GNU parallel extension to the Standard C++ Library. | |
29 | */ | |
30 | ||
31 | // Written by Felix Putze and Johannes Singler. | |
32 | ||
33 | #ifndef _GLIBCXX_PARALLEL_FIND_H | |
34 | #define _GLIBCXX_PARALLEL_FIND_H 1 | |
35 | ||
36 | #include <bits/stl_algobase.h> | |
37 | ||
38 | #include <parallel/features.h> | |
39 | #include <parallel/parallel.h> | |
40 | #include <parallel/compatibility.h> | |
41 | #include <parallel/equally_split.h> | |
42 | ||
43 | namespace __gnu_parallel | |
44 | { | |
77d16198 PC |
45 | /** |
46 | * @brief Parallel std::find, switch for different algorithms. | |
47 | * @param __begin1 Begin iterator of first sequence. | |
48 | * @param __end1 End iterator of first sequence. | |
49 | * @param __begin2 Begin iterator of second sequence. Must have same | |
50 | * length as first sequence. | |
51 | * @param __pred Find predicate. | |
52 | * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) | |
53 | * @return Place of finding in both sequences. | |
54 | */ | |
55 | template<typename _RAIter1, | |
56 | typename _RAIter2, | |
57 | typename _Pred, | |
58 | typename _Selector> | |
59 | inline std::pair<_RAIter1, _RAIter2> | |
60 | __find_template(_RAIter1 __begin1, _RAIter1 __end1, | |
61 | _RAIter2 __begin2, _Pred __pred, _Selector __selector) | |
62 | { | |
63 | switch (_Settings::get().find_algorithm) | |
64 | { | |
65 | case GROWING_BLOCKS: | |
66 | return __find_template(__begin1, __end1, __begin2, __pred, | |
67 | __selector, growing_blocks_tag()); | |
68 | case CONSTANT_SIZE_BLOCKS: | |
69 | return __find_template(__begin1, __end1, __begin2, __pred, | |
70 | __selector, constant_size_blocks_tag()); | |
71 | case EQUAL_SPLIT: | |
72 | return __find_template(__begin1, __end1, __begin2, __pred, | |
73 | __selector, equal_split_tag()); | |
74 | default: | |
75 | _GLIBCXX_PARALLEL_ASSERT(false); | |
76 | return std::make_pair(__begin1, __begin2); | |
77 | } | |
78 | } | |
c2ba9709 JS |
79 | |
80 | #if _GLIBCXX_FIND_EQUAL_SPLIT | |
81 | ||
77d16198 PC |
82 | /** |
83 | * @brief Parallel std::find, equal splitting variant. | |
84 | * @param __begin1 Begin iterator of first sequence. | |
85 | * @param __end1 End iterator of first sequence. | |
86 | * @param __begin2 Begin iterator of second sequence. Second __sequence | |
87 | * must have same length as first sequence. | |
88 | * @param __pred Find predicate. | |
89 | * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) | |
90 | * @return Place of finding in both sequences. | |
91 | */ | |
92 | template<typename _RAIter1, | |
93 | typename _RAIter2, | |
94 | typename _Pred, | |
95 | typename _Selector> | |
96 | std::pair<_RAIter1, _RAIter2> | |
97 | __find_template(_RAIter1 __begin1, _RAIter1 __end1, | |
98 | _RAIter2 __begin2, _Pred __pred, | |
99 | _Selector __selector, equal_split_tag) | |
100 | { | |
101 | _GLIBCXX_CALL(__end1 - __begin1) | |
102 | ||
103 | typedef std::iterator_traits<_RAIter1> _TraitsType; | |
104 | typedef typename _TraitsType::difference_type _DifferenceType; | |
105 | typedef typename _TraitsType::value_type _ValueType; | |
106 | ||
107 | _DifferenceType __length = __end1 - __begin1; | |
108 | _DifferenceType __result = __length; | |
109 | _DifferenceType* __borders; | |
110 | ||
111 | omp_lock_t __result_lock; | |
112 | omp_init_lock(&__result_lock); | |
113 | ||
114 | _ThreadIndex __num_threads = __get_max_threads(); | |
115 | # pragma omp parallel num_threads(__num_threads) | |
e683ee2a | 116 | { |
77d16198 PC |
117 | # pragma omp single |
118 | { | |
119 | __num_threads = omp_get_num_threads(); | |
120 | __borders = new _DifferenceType[__num_threads + 1]; | |
6b77089f | 121 | __equally_split(__length, __num_threads, __borders); |
77d16198 PC |
122 | } //single |
123 | ||
124 | _ThreadIndex __iam = omp_get_thread_num(); | |
125 | _DifferenceType __start = __borders[__iam], | |
126 | __stop = __borders[__iam + 1]; | |
127 | ||
128 | _RAIter1 __i1 = __begin1 + __start; | |
129 | _RAIter2 __i2 = __begin2 + __start; | |
130 | for (_DifferenceType __pos = __start; __pos < __stop; ++__pos) | |
131 | { | |
132 | # pragma omp flush(__result) | |
133 | // Result has been set to something lower. | |
134 | if (__result < __pos) | |
135 | break; | |
136 | ||
137 | if (__selector(__i1, __i2, __pred)) | |
138 | { | |
139 | omp_set_lock(&__result_lock); | |
140 | if (__pos < __result) | |
141 | __result = __pos; | |
142 | omp_unset_lock(&__result_lock); | |
143 | break; | |
144 | } | |
145 | ++__i1; | |
146 | ++__i2; | |
147 | } | |
e683ee2a | 148 | } //parallel |
59b567fb | 149 | |
77d16198 PC |
150 | omp_destroy_lock(&__result_lock); |
151 | delete[] __borders; | |
e683ee2a | 152 | |
77d16198 PC |
153 | return std::pair<_RAIter1, _RAIter2>(__begin1 + __result, |
154 | __begin2 + __result); | |
155 | } | |
c2ba9709 JS |
156 | |
157 | #endif | |
158 | ||
159 | #if _GLIBCXX_FIND_GROWING_BLOCKS | |
160 | ||
77d16198 PC |
161 | /** |
162 | * @brief Parallel std::find, growing block size variant. | |
163 | * @param __begin1 Begin iterator of first sequence. | |
164 | * @param __end1 End iterator of first sequence. | |
165 | * @param __begin2 Begin iterator of second sequence. Second __sequence | |
166 | * must have same length as first sequence. | |
167 | * @param __pred Find predicate. | |
168 | * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) | |
169 | * @return Place of finding in both sequences. | |
170 | * @see __gnu_parallel::_Settings::find_sequential_search_size | |
22a2af95 | 171 | * @see __gnu_parallel::_Settings::find_scale_factor |
77d16198 PC |
172 | * |
173 | * There are two main differences between the growing blocks and | |
174 | * the constant-size blocks variants. | |
175 | * 1. For GB, the block size grows; for CSB, the block size is fixed. | |
176 | * 2. For GB, the blocks are allocated dynamically; | |
177 | * for CSB, the blocks are allocated in a predetermined manner, | |
178 | * namely spacial round-robin. | |
179 | */ | |
180 | template<typename _RAIter1, | |
181 | typename _RAIter2, | |
182 | typename _Pred, | |
183 | typename _Selector> | |
184 | std::pair<_RAIter1, _RAIter2> | |
185 | __find_template(_RAIter1 __begin1, _RAIter1 __end1, | |
186 | _RAIter2 __begin2, _Pred __pred, _Selector __selector, | |
187 | growing_blocks_tag) | |
188 | { | |
189 | _GLIBCXX_CALL(__end1 - __begin1) | |
190 | ||
191 | typedef std::iterator_traits<_RAIter1> _TraitsType; | |
192 | typedef typename _TraitsType::difference_type _DifferenceType; | |
193 | typedef typename _TraitsType::value_type _ValueType; | |
194 | ||
195 | const _Settings& __s = _Settings::get(); | |
196 | ||
197 | _DifferenceType __length = __end1 - __begin1; | |
198 | ||
199 | _DifferenceType | |
200 | __sequential_search_size = std::min<_DifferenceType> | |
201 | (__length, __s.find_sequential_search_size); | |
202 | ||
203 | // Try it sequentially first. | |
204 | std::pair<_RAIter1, _RAIter2> | |
205 | __find_seq_result = __selector._M_sequential_algorithm | |
206 | (__begin1, __begin1 + __sequential_search_size, | |
207 | __begin2, __pred); | |
208 | ||
209 | if (__find_seq_result.first != (__begin1 + __sequential_search_size)) | |
210 | return __find_seq_result; | |
211 | ||
212 | // Index of beginning of next free block (after sequential find). | |
213 | _DifferenceType __next_block_start = __sequential_search_size; | |
214 | _DifferenceType __result = __length; | |
215 | ||
216 | omp_lock_t __result_lock; | |
217 | omp_init_lock(&__result_lock); | |
218 | ||
22a2af95 JS |
219 | const float __scale_factor = __s.find_scale_factor; |
220 | ||
77d16198 PC |
221 | _ThreadIndex __num_threads = __get_max_threads(); |
222 | # pragma omp parallel shared(__result) num_threads(__num_threads) | |
e683ee2a JS |
223 | { |
224 | # pragma omp single | |
77d16198 | 225 | __num_threads = omp_get_num_threads(); |
e683ee2a | 226 | |
77d16198 PC |
227 | // Not within first __k elements -> start parallel. |
228 | _ThreadIndex __iam = omp_get_thread_num(); | |
e683ee2a | 229 | |
22a2af95 JS |
230 | _DifferenceType __block_size = |
231 | std::max<_DifferenceType>(1, __scale_factor * __next_block_start); | |
77d16198 PC |
232 | _DifferenceType __start = __fetch_and_add<_DifferenceType> |
233 | (&__next_block_start, __block_size); | |
e683ee2a | 234 | |
77d16198 PC |
235 | // Get new block, update pointer to next block. |
236 | _DifferenceType __stop = | |
237 | std::min<_DifferenceType>(__length, __start + __block_size); | |
e683ee2a | 238 | |
77d16198 | 239 | std::pair<_RAIter1, _RAIter2> __local_result; |
e683ee2a | 240 | |
77d16198 PC |
241 | while (__start < __length) |
242 | { | |
1acba85b | 243 | # pragma omp flush(__result) |
77d16198 PC |
244 | // Get new value of result. |
245 | if (__result < __start) | |
246 | { | |
247 | // No chance to find first element. | |
248 | break; | |
249 | } | |
250 | ||
251 | __local_result = __selector._M_sequential_algorithm | |
252 | (__begin1 + __start, __begin1 + __stop, | |
253 | __begin2 + __start, __pred); | |
254 | ||
255 | if (__local_result.first != (__begin1 + __stop)) | |
256 | { | |
257 | omp_set_lock(&__result_lock); | |
258 | if ((__local_result.first - __begin1) < __result) | |
259 | { | |
260 | __result = __local_result.first - __begin1; | |
261 | ||
262 | // Result cannot be in future blocks, stop algorithm. | |
263 | __fetch_and_add<_DifferenceType>(&__next_block_start, | |
264 | __length); | |
265 | } | |
266 | omp_unset_lock(&__result_lock); | |
267 | } | |
268 | ||
22a2af95 JS |
269 | _DifferenceType __block_size = |
270 | std::max<_DifferenceType>(1, __scale_factor * __next_block_start); | |
77d16198 PC |
271 | |
272 | // Get new block, update pointer to next block. | |
273 | __start = __fetch_and_add<_DifferenceType>(&__next_block_start, | |
274 | __block_size); | |
22a2af95 JS |
275 | __stop = |
276 | std::min<_DifferenceType>(__length, __start + __block_size); | |
77d16198 | 277 | } |
e683ee2a | 278 | } //parallel |
c2ba9709 | 279 | |
77d16198 | 280 | omp_destroy_lock(&__result_lock); |
59b567fb | 281 | |
77d16198 PC |
282 | // Return iterator on found element. |
283 | return | |
284 | std::pair<_RAIter1, _RAIter2>(__begin1 + __result, | |
285 | __begin2 + __result); | |
286 | } | |
c2ba9709 JS |
287 | |
288 | #endif | |
289 | ||
290 | #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS | |
291 | ||
77d16198 PC |
292 | /** |
293 | * @brief Parallel std::find, constant block size variant. | |
294 | * @param __begin1 Begin iterator of first sequence. | |
295 | * @param __end1 End iterator of first sequence. | |
296 | * @param __begin2 Begin iterator of second sequence. Second __sequence | |
297 | * must have same length as first sequence. | |
298 | * @param __pred Find predicate. | |
299 | * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) | |
300 | * @return Place of finding in both sequences. | |
301 | * @see __gnu_parallel::_Settings::find_sequential_search_size | |
302 | * @see __gnu_parallel::_Settings::find_block_size | |
303 | * There are two main differences between the growing blocks and the | |
304 | * constant-size blocks variants. | |
305 | * 1. For GB, the block size grows; for CSB, the block size is fixed. | |
306 | * 2. For GB, the blocks are allocated dynamically; for CSB, the | |
307 | * blocks are allocated in a predetermined manner, namely spacial | |
308 | * round-robin. | |
309 | */ | |
310 | template<typename _RAIter1, | |
311 | typename _RAIter2, | |
312 | typename _Pred, | |
313 | typename _Selector> | |
314 | std::pair<_RAIter1, _RAIter2> | |
315 | __find_template(_RAIter1 __begin1, _RAIter1 __end1, | |
316 | _RAIter2 __begin2, _Pred __pred, _Selector __selector, | |
317 | constant_size_blocks_tag) | |
318 | { | |
319 | _GLIBCXX_CALL(__end1 - __begin1) | |
320 | typedef std::iterator_traits<_RAIter1> _TraitsType; | |
321 | typedef typename _TraitsType::difference_type _DifferenceType; | |
322 | typedef typename _TraitsType::value_type _ValueType; | |
323 | ||
324 | const _Settings& __s = _Settings::get(); | |
325 | ||
326 | _DifferenceType __length = __end1 - __begin1; | |
327 | ||
328 | _DifferenceType __sequential_search_size = std::min<_DifferenceType> | |
329 | (__length, __s.find_sequential_search_size); | |
330 | ||
331 | // Try it sequentially first. | |
332 | std::pair<_RAIter1, _RAIter2> | |
333 | __find_seq_result = __selector._M_sequential_algorithm | |
334 | (__begin1, __begin1 + __sequential_search_size, __begin2, __pred); | |
335 | ||
336 | if (__find_seq_result.first != (__begin1 + __sequential_search_size)) | |
337 | return __find_seq_result; | |
338 | ||
339 | _DifferenceType __result = __length; | |
340 | omp_lock_t __result_lock; | |
341 | omp_init_lock(&__result_lock); | |
342 | ||
343 | // Not within first __sequential_search_size elements -> start parallel. | |
344 | ||
345 | _ThreadIndex __num_threads = __get_max_threads(); | |
346 | # pragma omp parallel shared(__result) num_threads(__num_threads) | |
e683ee2a JS |
347 | { |
348 | # pragma omp single | |
77d16198 | 349 | __num_threads = omp_get_num_threads(); |
e683ee2a | 350 | |
77d16198 PC |
351 | _ThreadIndex __iam = omp_get_thread_num(); |
352 | _DifferenceType __block_size = __s.find_initial_block_size; | |
e683ee2a | 353 | |
77d16198 PC |
354 | // First element of thread's current iteration. |
355 | _DifferenceType __iteration_start = __sequential_search_size; | |
e683ee2a | 356 | |
77d16198 PC |
357 | // Where to work (initialization). |
358 | _DifferenceType __start = __iteration_start + __iam * __block_size; | |
359 | _DifferenceType __stop = std::min<_DifferenceType>(__length, | |
360 | __start | |
361 | + __block_size); | |
e683ee2a | 362 | |
77d16198 | 363 | std::pair<_RAIter1, _RAIter2> __local_result; |
e683ee2a | 364 | |
77d16198 PC |
365 | while (__start < __length) |
366 | { | |
367 | // Get new value of result. | |
1acba85b | 368 | # pragma omp flush(__result) |
77d16198 PC |
369 | // No chance to find first element. |
370 | if (__result < __start) | |
371 | break; | |
372 | ||
373 | __local_result = __selector._M_sequential_algorithm | |
374 | (__begin1 + __start, __begin1 + __stop, | |
375 | __begin2 + __start, __pred); | |
376 | ||
377 | if (__local_result.first != (__begin1 + __stop)) | |
378 | { | |
379 | omp_set_lock(&__result_lock); | |
380 | if ((__local_result.first - __begin1) < __result) | |
381 | __result = __local_result.first - __begin1; | |
382 | omp_unset_lock(&__result_lock); | |
383 | // Will not find better value in its interval. | |
384 | break; | |
385 | } | |
386 | ||
387 | __iteration_start += __num_threads * __block_size; | |
388 | ||
389 | // Where to work. | |
390 | __start = __iteration_start + __iam * __block_size; | |
391 | __stop = std::min<_DifferenceType>(__length, | |
392 | __start + __block_size); | |
393 | } | |
e683ee2a | 394 | } //parallel |
c2ba9709 | 395 | |
77d16198 | 396 | omp_destroy_lock(&__result_lock); |
59b567fb | 397 | |
77d16198 PC |
398 | // Return iterator on found element. |
399 | return std::pair<_RAIter1, _RAIter2>(__begin1 + __result, | |
400 | __begin2 + __result); | |
401 | } | |
c2ba9709 JS |
402 | #endif |
403 | } // end namespace | |
404 | ||
cbcd1e45 | 405 | #endif /* _GLIBCXX_PARALLEL_FIND_H */ |