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
>(__s
.partition_chunk_size
,
92 (double)__n
* __s
.partition_chunk_share
93 / (double)__num_threads
);
95 __chunk_size
= __s
.partition_chunk_size
;
98 while (__right
- __left
+ 1 >= 2 * __num_threads
* __chunk_size
)
102 _DifferenceType __num_chunks
= (__right
- __left
+ 1) / __chunk_size
;
104 for (int __r
= 0; __r
< __num_threads
; ++__r
)
106 __reserved_left
[__r
] = false;
107 __reserved_right
[__r
] = false;
110 __leftover_right
= 0;
114 _DifferenceType __thread_left
, __thread_left_border
,
115 thread_right
, __thread_right_border
;
116 __thread_left
= __left
+ 1;
118 // Just to satisfy the condition below.
119 __thread_left_border
= __thread_left
- 1;
120 thread_right
= __n
- 1;
121 __thread_right_border
= thread_right
+ 1;
123 bool __iam_finished
= false;
124 while (!__iam_finished
)
126 if (__thread_left
> __thread_left_border
)
128 omp_set_lock(&__result_lock
);
129 if (__left
+ (__chunk_size
- 1) > __right
)
130 __iam_finished
= true;
133 __thread_left
= __left
;
134 __thread_left_border
= __left
+ (__chunk_size
- 1);
135 __left
+= __chunk_size
;
137 omp_unset_lock(&__result_lock
);
140 if (thread_right
< __thread_right_border
)
142 omp_set_lock(&__result_lock
);
143 if (__left
> __right
- (__chunk_size
- 1))
144 __iam_finished
= true;
147 thread_right
= __right
;
148 __thread_right_border
= __right
- (__chunk_size
- 1);
149 __right
-= __chunk_size
;
151 omp_unset_lock(&__result_lock
);
158 while (__thread_left
< thread_right
)
160 while (__pred(__begin
[__thread_left
])
161 && __thread_left
<= __thread_left_border
)
163 while (!__pred(__begin
[thread_right
])
164 && thread_right
>= __thread_right_border
)
167 if (__thread_left
> __thread_left_border
168 || thread_right
< __thread_right_border
)
169 // Fetch new chunk(__s).
172 std::swap(__begin
[__thread_left
], __begin
[thread_right
]);
178 // Now swap the leftover chunks to the right places.
179 if (__thread_left
<= __thread_left_border
)
182 if (thread_right
>= __thread_right_border
)
190 __leftnew
= __left
- __leftover_left
* __chunk_size
;
191 __rightnew
= __right
+ __leftover_right
* __chunk_size
;
196 // <=> __thread_left_border + (__chunk_size - 1) >= __leftnew
197 if (__thread_left
<= __thread_left_border
198 && __thread_left_border
>= __leftnew
)
200 // Chunk already in place, reserve spot.
201 __reserved_left
[(__left
- (__thread_left_border
+ 1)) / __chunk_size
]
205 // <=> __thread_right_border - (__chunk_size - 1) <= __rightnew
206 if (thread_right
>= __thread_right_border
207 && __thread_right_border
<= __rightnew
)
209 // Chunk already in place, reserve spot.
210 __reserved_right
[((__thread_right_border
- 1) - __right
)
211 / __chunk_size
] = true;
216 if (__thread_left
<= __thread_left_border
217 && __thread_left_border
< __leftnew
)
219 // Find spot and swap.
220 _DifferenceType __swapstart
= -1;
221 omp_set_lock(&__result_lock
);
222 for (int __r
= 0; __r
< __leftover_left
; ++__r
)
223 if (!__reserved_left
[__r
])
225 __reserved_left
[__r
] = true;
226 __swapstart
= __left
- (__r
+ 1) * __chunk_size
;
229 omp_unset_lock(&__result_lock
);
231 #if _GLIBCXX_ASSERTIONS
232 _GLIBCXX_PARALLEL_ASSERT(__swapstart
!= -1);
235 std::swap_ranges(__begin
+ __thread_left_border
236 - (__chunk_size
- 1),
237 __begin
+ __thread_left_border
+ 1,
238 __begin
+ __swapstart
);
241 if (thread_right
>= __thread_right_border
242 && __thread_right_border
> __rightnew
)
244 // Find spot and swap
245 _DifferenceType __swapstart
= -1;
246 omp_set_lock(&__result_lock
);
247 for (int __r
= 0; __r
< __leftover_right
; ++__r
)
248 if (!__reserved_right
[__r
])
250 __reserved_right
[__r
] = true;
251 __swapstart
= __right
+ __r
* __chunk_size
+ 1;
254 omp_unset_lock(&__result_lock
);
256 #if _GLIBCXX_ASSERTIONS
257 _GLIBCXX_PARALLEL_ASSERT(__swapstart
!= -1);
260 std::swap_ranges(__begin
+ __thread_right_border
,
261 __begin
+ __thread_right_border
+ __chunk_size
,
262 __begin
+ __swapstart
);
264 #if _GLIBCXX_ASSERTIONS
269 for (int __r
= 0; __r
< __leftover_left
; ++__r
)
270 _GLIBCXX_PARALLEL_ASSERT(__reserved_left
[__r
]);
271 for (int __r
= 0; __r
< __leftover_right
; ++__r
)
272 _GLIBCXX_PARALLEL_ASSERT(__reserved_right
[__r
]);
281 __right
= __rightnew
;
283 # pragma omp flush(__left, __right)
284 } // end "recursion" //parallel
286 _DifferenceType __final_left
= __left
, __final_right
= __right
;
288 while (__final_left
< __final_right
)
290 // Go right until key is geq than pivot.
291 while (__pred(__begin
[__final_left
]) && __final_left
< __final_right
)
294 // Go left until key is less than pivot.
295 while (!__pred(__begin
[__final_right
]) && __final_left
< __final_right
)
298 if (__final_left
== __final_right
)
300 std::swap(__begin
[__final_left
], __begin
[__final_right
]);
305 // All elements on the left side are < piv, all elements on the
307 delete[] __reserved_left
;
308 delete[] __reserved_right
;
310 omp_destroy_lock(&__result_lock
);
312 // Element "between" __final_left and __final_right might not have
314 if (__final_left
< __n
&& !__pred(__begin
[__final_left
]))
318 return __final_left
+ 1;
322 * @brief Parallel implementation of std::nth_element().
323 * @param __begin Begin iterator of input sequence.
324 * @param __nth _Iterator of element that must be in position afterwards.
325 * @param __end End iterator of input sequence.
326 * @param __comp Comparator.
328 template<typename _RAIter
, typename _Compare
>
330 parallel_nth_element(_RAIter __begin
, _RAIter __nth
,
331 _RAIter __end
, _Compare __comp
)
333 typedef std::iterator_traits
<_RAIter
> _TraitsType
;
334 typedef typename
_TraitsType::value_type _ValueType
;
335 typedef typename
_TraitsType::difference_type _DifferenceType
;
337 _GLIBCXX_CALL(__end
- __begin
)
342 _DifferenceType minimum_length
=
343 std::max
<_DifferenceType
>(2, _Settings::get().partition_minimal_n
);
345 // Break if input range to small.
346 while (static_cast<_SequenceIndex
>(__end
- __begin
) >= minimum_length
)
348 _DifferenceType __n
= __end
- __begin
;
350 _RAIter __pivot_pos
= __begin
+ __rng(__n
);
352 // Swap __pivot_pos value to end.
353 if (__pivot_pos
!= (__end
- 1))
354 std::swap(*__pivot_pos
, *(__end
- 1));
355 __pivot_pos
= __end
- 1;
357 // XXX _Compare must have first__ValueType, second__ValueType,
359 // _Compare == __gnu_parallel::_Lexicographic<S, int,
360 // __gnu_parallel::_Less<S, S> >
361 // __pivot_pos == std::pair<S, int>*
362 // XXX binder2nd only for _RAIters??
363 __gnu_parallel::binder2nd
<_Compare
, _ValueType
, _ValueType
, bool>
364 __pred(__comp
, *__pivot_pos
);
366 // Divide, leave pivot unchanged in last place.
367 _RAIter __split_pos1
, __split_pos2
;
368 __split_pos1
= __begin
+ __parallel_partition(__begin
, __end
- 1, __pred
,
369 __get_max_threads());
371 // Left side: < __pivot_pos; __right side: >= __pivot_pos
373 // Swap pivot back to middle.
374 if (__split_pos1
!= __pivot_pos
)
375 std::swap(*__split_pos1
, *__pivot_pos
);
376 __pivot_pos
= __split_pos1
;
378 // In case all elements are equal, __split_pos1 == 0
379 if ((__split_pos1
+ 1 - __begin
) < (__n
>> 7)
380 || (__end
- __split_pos1
) < (__n
>> 7))
382 // Very unequal split, one part smaller than one 128th
383 // elements not strictly larger than the pivot.
384 __gnu_parallel::__unary_negate
<__gnu_parallel::
385 __binder1st
<_Compare
, _ValueType
, _ValueType
, bool>, _ValueType
>
386 __pred(__gnu_parallel::__binder1st
<_Compare
, _ValueType
,
387 _ValueType
, bool>(__comp
, *__pivot_pos
));
389 // Find other end of pivot-equal range.
390 __split_pos2
= __gnu_sequential::partition(__split_pos1
+ 1,
394 // Only skip the pivot.
395 __split_pos2
= __split_pos1
+ 1;
397 // Compare iterators.
398 if (__split_pos2
<= __nth
)
399 __begin
= __split_pos2
;
400 else if (__nth
< __split_pos1
)
401 __end
= __split_pos1
;
406 // Only at most _Settings::partition_minimal_n __elements __left.
407 __gnu_sequential::sort(__begin
, __end
, __comp
);
410 /** @brief Parallel implementation of std::partial_sort().
411 * @param __begin Begin iterator of input sequence.
412 * @param __middle Sort until this position.
413 * @param __end End iterator of input sequence.
414 * @param __comp Comparator. */
415 template<typename _RAIter
, typename _Compare
>
417 parallel_partial_sort(_RAIter __begin
,
419 _RAIter __end
, _Compare __comp
)
421 parallel_nth_element(__begin
, __middle
, __end
, __comp
);
422 std::sort(__begin
, __middle
, __comp
);
425 } //namespace __gnu_parallel
427 #undef _GLIBCXX_VOLATILE
429 #endif /* _GLIBCXX_PARALLEL_PARTITION_H */