3 // Copyright (C) 2007, 2008, 2009 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 3, 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 // 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.
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/>.
25 /** @file parallel/partition.h
26 * @brief Parallel implementation of std::partition(),
27 * std::nth_element(), and std::partial_sort().
28 * This file is a GNU parallel extension to the Standard C++ Library.
31 // Written by Johannes Singler and Felix Putze.
33 #ifndef _GLIBCXX_PARALLEL_PARTITION_H
34 #define _GLIBCXX_PARALLEL_PARTITION_H 1
36 #include <parallel/basic_iterator.h>
37 #include <parallel/sort.h>
38 #include <parallel/random_number.h>
39 #include <bits/stl_algo.h>
40 #include <parallel/parallel.h>
42 /** @brief Decide whether to declare certain variables volatile. */
43 #define _GLIBCXX_VOLATILE volatile
45 namespace __gnu_parallel
47 /** @brief Parallel implementation of std::partition.
48 * @param __begin Begin iterator of input sequence to split.
49 * @param __end End iterator of input sequence to split.
50 * @param __pred Partition predicate, possibly including some kind of pivot.
51 * @param __num_threads Maximum number of threads to use for this task.
52 * @return Number of elements not fulfilling the predicate. */
53 template<typename _RAIter, typename _Predicate>
54 typename std::iterator_traits<_RAIter>::difference_type
55 __parallel_partition(_RAIter __begin, _RAIter __end,
56 _Predicate __pred, _ThreadIndex __num_threads)
58 typedef std::iterator_traits<_RAIter> _TraitsType;
59 typedef typename _TraitsType::value_type _ValueType;
60 typedef typename _TraitsType::difference_type _DifferenceType;
62 _DifferenceType __n = __end - __begin;
66 const _Settings& __s = _Settings::get();
69 _GLIBCXX_VOLATILE _DifferenceType __left = 0, __right = __n - 1;
70 _GLIBCXX_VOLATILE _DifferenceType __leftover_left, __leftover_right;
71 _GLIBCXX_VOLATILE _DifferenceType __leftnew, __rightnew;
73 bool* __reserved_left = NULL, * __reserved_right = NULL;
75 _DifferenceType __chunk_size;
77 omp_lock_t __result_lock;
78 omp_init_lock(&__result_lock);
80 //at least two chunks per thread
81 if(__right - __left + 1 >= 2 * __num_threads * __chunk_size)
82 # pragma omp parallel num_threads(__num_threads)
86 __num_threads = omp_get_num_threads();
87 __reserved_left = new bool[__num_threads];
88 __reserved_right = new bool[__num_threads];
90 if (__s.partition_chunk_share > 0.0)
91 __chunk_size = std::max<_DifferenceType>(
92 __s.partition_chunk_size,
93 (double)__n * __s.partition_chunk_share /
94 (double)__num_threads);
96 __chunk_size = __s.partition_chunk_size;
99 while (__right - __left + 1 >= 2 * __num_threads * __chunk_size)
103 _DifferenceType __num_chunks
104 = (__right - __left + 1) / __chunk_size;
106 for (int __r = 0; __r < __num_threads; ++__r)
108 __reserved_left[__r] = false;
109 __reserved_right[__r] = false;
112 __leftover_right = 0;
116 _DifferenceType __thread_left, __thread_left_border,
117 thread_right, __thread_right_border;
118 __thread_left = __left + 1;
120 // Just to satisfy the condition below.
121 __thread_left_border = __thread_left - 1;
122 thread_right = __n - 1;
123 __thread_right_border = thread_right + 1;
125 bool __iam_finished = false;
126 while (!__iam_finished)
128 if (__thread_left > __thread_left_border)
130 omp_set_lock(&__result_lock);
131 if (__left + (__chunk_size - 1) > __right)
132 __iam_finished = true;
135 __thread_left = __left;
136 __thread_left_border = __left + (__chunk_size - 1);
137 __left += __chunk_size;
139 omp_unset_lock(&__result_lock);
142 if (thread_right < __thread_right_border)
144 omp_set_lock(&__result_lock);
145 if (__left > __right - (__chunk_size - 1))
146 __iam_finished = true;
149 thread_right = __right;
150 __thread_right_border = __right - (__chunk_size - 1);
151 __right -= __chunk_size;
153 omp_unset_lock(&__result_lock);
160 while (__thread_left < thread_right)
162 while (__pred(__begin[__thread_left])
163 && __thread_left <= __thread_left_border)
165 while (!__pred(__begin[thread_right])
166 && thread_right >= __thread_right_border)
169 if (__thread_left > __thread_left_border
170 || thread_right < __thread_right_border)
171 // Fetch new chunk(__s).
174 std::swap(__begin[__thread_left], __begin[thread_right]);
180 // Now swap the leftover chunks to the right places.
181 if (__thread_left <= __thread_left_border)
184 if (thread_right >= __thread_right_border)
192 __leftnew = __left - __leftover_left * __chunk_size;
193 __rightnew = __right + __leftover_right * __chunk_size;
198 // <=> __thread_left_border + (__chunk_size - 1) >= __leftnew
199 if (__thread_left <= __thread_left_border
200 && __thread_left_border >= __leftnew)
202 // Chunk already in place, reserve spot.
204 [(__left - (__thread_left_border + 1)) / __chunk_size]
208 // <=> __thread_right_border - (__chunk_size - 1) <= __rightnew
209 if (thread_right >= __thread_right_border
210 && __thread_right_border <= __rightnew)
212 // Chunk already in place, reserve spot.
213 __reserved_right[((__thread_right_border - 1) - __right)
214 / __chunk_size] = true;
219 if (__thread_left <= __thread_left_border
220 && __thread_left_border < __leftnew)
222 // Find spot and swap.
223 _DifferenceType __swapstart = -1;
224 omp_set_lock(&__result_lock);
225 for (int __r = 0; __r < __leftover_left; ++__r)
226 if (!__reserved_left[__r])
228 __reserved_left[__r] = true;
229 __swapstart = __left - (__r + 1) * __chunk_size;
232 omp_unset_lock(&__result_lock);
234 #if _GLIBCXX_ASSERTIONS
235 _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
238 std::swap_ranges(__begin + __thread_left_border
239 - (__chunk_size - 1),
240 __begin + __thread_left_border + 1,
241 __begin + __swapstart);
244 if (thread_right >= __thread_right_border
245 && __thread_right_border > __rightnew)
247 // Find spot and swap
248 _DifferenceType __swapstart = -1;
249 omp_set_lock(&__result_lock);
250 for (int __r = 0; __r < __leftover_right; ++__r)
251 if (!__reserved_right[__r])
253 __reserved_right[__r] = true;
254 __swapstart = __right + __r * __chunk_size + 1;
257 omp_unset_lock(&__result_lock);
259 #if _GLIBCXX_ASSERTIONS
260 _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
264 __begin + __thread_right_border,
265 __begin + __thread_right_border + __chunk_size,
266 __begin + __swapstart);
268 #if _GLIBCXX_ASSERTIONS
273 for (int __r = 0; __r < __leftover_left; ++__r)
274 _GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r]);
275 for (int __r = 0; __r < __leftover_right; ++__r)
276 _GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r]);
285 __right = __rightnew;
287 # pragma omp flush(__left, __right)
288 } // end "recursion" //parallel
290 _DifferenceType __final_left = __left, __final_right = __right;
292 while (__final_left < __final_right)
294 // Go right until key is geq than pivot.
295 while (__pred(__begin[__final_left]) && __final_left < __final_right)
298 // Go left until key is less than pivot.
299 while (!__pred(__begin[__final_right]) && __final_left < __final_right)
302 if (__final_left == __final_right)
304 std::swap(__begin[__final_left], __begin[__final_right]);
309 // All elements on the left side are < piv, all elements on the
311 delete[] __reserved_left;
312 delete[] __reserved_right;
314 omp_destroy_lock(&__result_lock);
316 // Element "between" __final_left and __final_right might not have
318 if (__final_left < __n && !__pred(__begin[__final_left]))
322 return __final_left + 1;
326 * @brief Parallel implementation of std::nth_element().
327 * @param __begin Begin iterator of input sequence.
328 * @param __nth _Iterator of element that must be in position afterwards.
329 * @param __end End iterator of input sequence.
330 * @param __comp Comparator.
332 template<typename _RAIter, typename _Compare>
334 parallel_nth_element(_RAIter __begin, _RAIter __nth,
335 _RAIter __end, _Compare __comp)
337 typedef std::iterator_traits<_RAIter> _TraitsType;
338 typedef typename _TraitsType::value_type _ValueType;
339 typedef typename _TraitsType::difference_type _DifferenceType;
341 _GLIBCXX_CALL(__end - __begin)
346 _DifferenceType minimum_length =
347 std::max<_DifferenceType>(2, _Settings::get().partition_minimal_n);
349 // Break if input range to small.
350 while (static_cast<_SequenceIndex>(__end - __begin) >= minimum_length)
352 _DifferenceType __n = __end - __begin;
354 _RAIter __pivot_pos = __begin + __rng(__n);
356 // Swap __pivot_pos value to end.
357 if (__pivot_pos != (__end - 1))
358 std::swap(*__pivot_pos, *(__end - 1));
359 __pivot_pos = __end - 1;
361 // XXX _Compare must have first__ValueType, second__ValueType,
363 // _Compare == __gnu_parallel::_Lexicographic<S, int,
364 // __gnu_parallel::_Less<S, S> >
365 // __pivot_pos == std::pair<S, int>*
366 // XXX binder2nd only for _RAIters??
367 __gnu_parallel::binder2nd<_Compare, _ValueType, _ValueType, bool>
368 __pred(__comp, *__pivot_pos);
370 // Divide, leave pivot unchanged in last place.
371 _RAIter __split_pos1, __split_pos2;
372 __split_pos1 = __begin
373 + __parallel_partition(__begin, __end - 1, __pred,
374 __get_max_threads());
376 // Left side: < __pivot_pos; __right side: >= __pivot_pos
378 // Swap pivot back to middle.
379 if (__split_pos1 != __pivot_pos)
380 std::swap(*__split_pos1, *__pivot_pos);
381 __pivot_pos = __split_pos1;
383 // In case all elements are equal, __split_pos1 == 0
384 if ((__split_pos1 + 1 - __begin) < (__n >> 7)
385 || (__end - __split_pos1) < (__n >> 7))
387 // Very unequal split, one part smaller than one 128th
388 // elements not strictly larger than the pivot.
389 __gnu_parallel::__unary_negate<__gnu_parallel::
390 __binder1st<_Compare, _ValueType, _ValueType, bool>, _ValueType>
391 __pred(__gnu_parallel::__binder1st<_Compare, _ValueType,
392 _ValueType, bool>(__comp, *__pivot_pos));
394 // Find other end of pivot-equal range.
395 __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1,
399 // Only skip the pivot.
400 __split_pos2 = __split_pos1 + 1;
402 // Compare iterators.
403 if (__split_pos2 <= __nth)
404 __begin = __split_pos2;
405 else if (__nth < __split_pos1)
406 __end = __split_pos1;
411 // Only at most _Settings::partition_minimal_n __elements __left.
412 __gnu_sequential::sort(__begin, __end, __comp);
415 /** @brief Parallel implementation of std::partial_sort().
416 * @param __begin Begin iterator of input sequence.
417 * @param __middle Sort until this position.
418 * @param __end End iterator of input sequence.
419 * @param __comp Comparator. */
420 template<typename _RAIter, typename _Compare>
422 parallel_partial_sort(_RAIter __begin,
424 _RAIter __end, _Compare __comp)
426 parallel_nth_element(__begin, __middle, __end, __comp);
427 std::sort(__begin, __middle, __comp);
430 } //namespace __gnu_parallel
432 #undef _GLIBCXX_VOLATILE
434 #endif /* _GLIBCXX_PARALLEL_PARTITION_H */