1 // -*- C++ -*-
2
3 // Copyright (C) 2007-2023 Free Software Foundation, Inc.
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
8 // Foundation; either version 3, or (at your option) any later
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
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15
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/>.
24
25 /** @file parallel/find.h
26 * @brief Parallel implementation base for std::find(), std::equal()
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 {
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 }
79
80 #if _GLIBCXX_FIND_EQUAL_SPLIT
81
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)
116 {
117 # pragma omp single
118 {
119 __num_threads = omp_get_num_threads();
120 __borders = new _DifferenceType[__num_threads + 1];
121 __equally_split(__length, __num_threads, __borders);
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 }
148 } //parallel
149
150 omp_destroy_lock(&__result_lock);
151 delete[] __borders;
152
153 return std::pair<_RAIter1, _RAIter2>(__begin1 + __result,
154 __begin2 + __result);
155 }
156
157 #endif
158
159 #if _GLIBCXX_FIND_GROWING_BLOCKS
160
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
171 * @see __gnu_parallel::_Settings::find_scale_factor
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
219 const float __scale_factor = __s.find_scale_factor;
220
221 _ThreadIndex __num_threads = __get_max_threads();
222 # pragma omp parallel shared(__result) num_threads(__num_threads)
223 {
224 # pragma omp single
225 __num_threads = omp_get_num_threads();
226
227 // Not within first __k elements -> start parallel.
228 _ThreadIndex __iam = omp_get_thread_num();
229
230 _DifferenceType __block_size =
231 std::max<_DifferenceType>(1, __scale_factor * __next_block_start);
232 _DifferenceType __start = __fetch_and_add<_DifferenceType>
233 (&__next_block_start, __block_size);
234
235 // Get new block, update pointer to next block.
236 _DifferenceType __stop =
237 std::min<_DifferenceType>(__length, __start + __block_size);
238
239 std::pair<_RAIter1, _RAIter2> __local_result;
240
241 while (__start < __length)
242 {
243 # pragma omp flush(__result)
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
269 _DifferenceType __block_size =
270 std::max<_DifferenceType>(1, __scale_factor * __next_block_start);
271
272 // Get new block, update pointer to next block.
273 __start = __fetch_and_add<_DifferenceType>(&__next_block_start,
274 __block_size);
275 __stop =
276 std::min<_DifferenceType>(__length, __start + __block_size);
277 }
278 } //parallel
279
280 omp_destroy_lock(&__result_lock);
281
282 // Return iterator on found element.
283 return
284 std::pair<_RAIter1, _RAIter2>(__begin1 + __result,
285 __begin2 + __result);
286 }
287
288 #endif
289
290 #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS
291
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)
347 {
348 # pragma omp single
349 __num_threads = omp_get_num_threads();
350
351 _ThreadIndex __iam = omp_get_thread_num();
352 _DifferenceType __block_size = __s.find_initial_block_size;
353
354 // First element of thread's current iteration.
355 _DifferenceType __iteration_start = __sequential_search_size;
356
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);
362
363 std::pair<_RAIter1, _RAIter2> __local_result;
364
365 while (__start < __length)
366 {
367 // Get new value of result.
368 # pragma omp flush(__result)
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 }
394 } //parallel
395
396 omp_destroy_lock(&__result_lock);
397
398 // Return iterator on found element.
399 return std::pair<_RAIter1, _RAIter2>(__begin1 + __result,
400 __begin2 + __result);
401 }
402 #endif
403 } // end namespace
404
405 #endif /* _GLIBCXX_PARALLEL_FIND_H */