3 // Copyright (C) 2007, 2008, 2009, 2010 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
52 * @param __num_threads Maximum number of threads to use for this task.
53 * @return Number of elements not fulfilling the predicate. */
54 template<typename _RAIter
, typename _Predicate
>
55 typename
std::iterator_traits
<_RAIter
>::difference_type
56 __parallel_partition(_RAIter __begin
, _RAIter __end
,
57 _Predicate __pred
, _ThreadIndex __num_threads
)
59 typedef std::iterator_traits
<_RAIter
> _TraitsType
;
60 typedef typename
_TraitsType::value_type _ValueType
;
61 typedef typename
_TraitsType::difference_type _DifferenceType
;
63 _DifferenceType __n
= __end
- __begin
;
67 const _Settings
& __s
= _Settings::get();
70 _GLIBCXX_VOLATILE _DifferenceType __left
= 0, __right
= __n
- 1;
71 _GLIBCXX_VOLATILE _DifferenceType __leftover_left
, __leftover_right
;
72 _GLIBCXX_VOLATILE _DifferenceType __leftnew
, __rightnew
;
74 bool* __reserved_left
= NULL
, * __reserved_right
= NULL
;
76 _DifferenceType __chunk_size
= __s
.partition_chunk_size
;
78 omp_lock_t __result_lock
;
79 omp_init_lock(&__result_lock
);
81 //at least two chunks per thread
82 if (__right
- __left
+ 1 >= 2 * __num_threads
* __chunk_size
)
83 # pragma omp parallel num_threads(__num_threads)
87 __num_threads
= omp_get_num_threads();
88 __reserved_left
= new bool[__num_threads
];
89 __reserved_right
= new bool[__num_threads
];
91 if (__s
.partition_chunk_share
> 0.0)
92 __chunk_size
= std::max
<_DifferenceType
>
93 (__s
.partition_chunk_size
, (double)__n
94 * __s
.partition_chunk_share
/ (double)__num_threads
);
96 __chunk_size
= __s
.partition_chunk_size
;
99 while (__right
- __left
+ 1 >= 2 * __num_threads
* __chunk_size
)
103 _DifferenceType __num_chunks
= ((__right
- __left
+ 1)
106 for (_ThreadIndex __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
],
175 __begin
[__thread_right
]);
181 // Now swap the leftover chunks to the right places.
182 if (__thread_left
<= __thread_left_border
)
185 if (__thread_right
>= __thread_right_border
)
193 __leftnew
= __left
- __leftover_left
* __chunk_size
;
194 __rightnew
= __right
+ __leftover_right
* __chunk_size
;
199 // <=> __thread_left_border + (__chunk_size - 1) >= __leftnew
200 if (__thread_left
<= __thread_left_border
201 && __thread_left_border
>= __leftnew
)
203 // Chunk already in place, reserve spot.
204 __reserved_left
[(__left
- (__thread_left_border
+ 1))
205 / __chunk_size
] = true;
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 (_DifferenceType __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 (_DifferenceType __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);
263 std::swap_ranges(__begin
+ __thread_right_border
,
264 __begin
+ __thread_right_border
265 + __chunk_size
, __begin
+ __swapstart
);
267 #if _GLIBCXX_ASSERTIONS
272 for (_DifferenceType __r
= 0; __r
< __leftover_left
; ++__r
)
273 _GLIBCXX_PARALLEL_ASSERT(__reserved_left
[__r
]);
274 for (_DifferenceType __r
= 0; __r
< __leftover_right
; ++__r
)
275 _GLIBCXX_PARALLEL_ASSERT(__reserved_right
[__r
]);
284 __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
])
296 && __final_left
< __final_right
)
299 // Go left until key is less than pivot.
300 while (!__pred(__begin
[__final_right
])
301 && __final_left
< __final_right
)
304 if (__final_left
== __final_right
)
306 std::swap(__begin
[__final_left
], __begin
[__final_right
]);
311 // All elements on the left side are < piv, all elements on the
313 delete[] __reserved_left
;
314 delete[] __reserved_right
;
316 omp_destroy_lock(&__result_lock
);
318 // Element "between" __final_left and __final_right might not have
320 if (__final_left
< __n
&& !__pred(__begin
[__final_left
]))
324 return __final_left
+ 1;
328 * @brief Parallel implementation of std::nth_element().
329 * @param __begin Begin iterator of input sequence.
330 * @param __nth _Iterator of element that must be in position afterwards.
331 * @param __end End iterator of input sequence.
332 * @param __comp Comparator.
334 template<typename _RAIter
, typename _Compare
>
336 __parallel_nth_element(_RAIter __begin
, _RAIter __nth
,
337 _RAIter __end
, _Compare __comp
)
339 typedef std::iterator_traits
<_RAIter
> _TraitsType
;
340 typedef typename
_TraitsType::value_type _ValueType
;
341 typedef typename
_TraitsType::difference_type _DifferenceType
;
343 _GLIBCXX_CALL(__end
- __begin
)
348 const _Settings
& __s
= _Settings::get();
349 _DifferenceType __minimum_length
= std::max
<_DifferenceType
>(2,
350 std::max(__s
.nth_element_minimal_n
, __s
.partition_minimal_n
));
352 // Break if input range to small.
353 while (static_cast<_SequenceIndex
>(__end
- __begin
) >= __minimum_length
)
355 _DifferenceType __n
= __end
- __begin
;
357 _RAIter __pivot_pos
= __begin
+ __rng(__n
);
359 // Swap __pivot_pos value to end.
360 if (__pivot_pos
!= (__end
- 1))
361 std::swap(*__pivot_pos
, *(__end
- 1));
362 __pivot_pos
= __end
- 1;
364 // _Compare must have first_value_type, second_value_type,
367 // __gnu_parallel::_Lexicographic<S, int,
368 // __gnu_parallel::_Less<S, S> >
369 // __pivot_pos == std::pair<S, int>*
370 __gnu_parallel::__binder2nd
<_Compare
, _ValueType
, _ValueType
, bool>
371 __pred(__comp
, *__pivot_pos
);
373 // Divide, leave pivot unchanged in last place.
374 _RAIter __split_pos1
, __split_pos2
;
375 __split_pos1
= __begin
+ __parallel_partition(__begin
, __end
- 1,
377 __get_max_threads());
379 // Left side: < __pivot_pos; __right side: >= __pivot_pos
381 // Swap pivot back to middle.
382 if (__split_pos1
!= __pivot_pos
)
383 std::swap(*__split_pos1
, *__pivot_pos
);
384 __pivot_pos
= __split_pos1
;
386 // In case all elements are equal, __split_pos1 == 0
387 if ((__split_pos1
+ 1 - __begin
) < (__n
>> 7)
388 || (__end
- __split_pos1
) < (__n
>> 7))
390 // Very unequal split, one part smaller than one 128th
391 // elements not strictly larger than the pivot.
392 __gnu_parallel::__unary_negate
<__gnu_parallel::
393 __binder1st
<_Compare
, _ValueType
,
394 _ValueType
, bool>, _ValueType
>
395 __pred(__gnu_parallel::__binder1st
<_Compare
, _ValueType
,
396 _ValueType
, bool>(__comp
, *__pivot_pos
));
398 // Find other end of pivot-equal range.
399 __split_pos2
= __gnu_sequential::partition(__split_pos1
+ 1,
403 // Only skip the pivot.
404 __split_pos2
= __split_pos1
+ 1;
406 // Compare iterators.
407 if (__split_pos2
<= __nth
)
408 __begin
= __split_pos2
;
409 else if (__nth
< __split_pos1
)
410 __end
= __split_pos1
;
415 // Only at most _Settings::partition_minimal_n __elements __left.
416 __gnu_sequential::nth_element(__begin
, __nth
, __end
, __comp
);
419 /** @brief Parallel implementation of std::partial_sort().
420 * @param __begin Begin iterator of input sequence.
421 * @param __middle Sort until this position.
422 * @param __end End iterator of input sequence.
423 * @param __comp Comparator. */
424 template<typename _RAIter
, typename _Compare
>
426 __parallel_partial_sort(_RAIter __begin
,
428 _RAIter __end
, _Compare __comp
)
430 __parallel_nth_element(__begin
, __middle
, __end
, __comp
);
431 std::sort(__begin
, __middle
, __comp
);
434 } //namespace __gnu_parallel
436 #undef _GLIBCXX_VOLATILE
438 #endif /* _GLIBCXX_PARALLEL_PARTITION_H */