]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
83ffe9cd | 3 | // Copyright (C) 2007-2023 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 | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
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/quicksort.h | |
26 | * @brief Implementation of a unbalanced parallel quicksort (in-place). | |
27 | * This file is a GNU parallel extension to the Standard C++ Library. | |
28 | */ | |
29 | ||
30 | // Written by Johannes Singler. | |
31 | ||
32 | #ifndef _GLIBCXX_PARALLEL_QUICKSORT_H | |
33 | #define _GLIBCXX_PARALLEL_QUICKSORT_H 1 | |
34 | ||
35 | #include <parallel/parallel.h> | |
36 | #include <parallel/partition.h> | |
37 | ||
38 | namespace __gnu_parallel | |
39 | { | |
40 | /** @brief Unbalanced quicksort divide step. | |
1acba85b JS |
41 | * @param __begin Begin iterator of subsequence. |
42 | * @param __end End iterator of subsequence. | |
43 | * @param __comp Comparator. | |
44 | * @param __pivot_rank Desired __rank of the pivot. | |
45 | * @param __num_samples Choose pivot from that many samples. | |
46 | * @param __num_threads Number of threads that are allowed to work on | |
c2ba9709 JS |
47 | * this part. |
48 | */ | |
1acba85b JS |
49 | template<typename _RAIter, typename _Compare> |
50 | typename std::iterator_traits<_RAIter>::difference_type | |
77d16198 PC |
51 | __parallel_sort_qs_divide(_RAIter __begin, _RAIter __end, |
52 | _Compare __comp, typename std::iterator_traits | |
53 | <_RAIter>::difference_type __pivot_rank, | |
54 | typename std::iterator_traits | |
55 | <_RAIter>::difference_type | |
56 | __num_samples, _ThreadIndex __num_threads) | |
5817ff8e | 57 | { |
1acba85b JS |
58 | typedef std::iterator_traits<_RAIter> _TraitsType; |
59 | typedef typename _TraitsType::value_type _ValueType; | |
60 | typedef typename _TraitsType::difference_type _DifferenceType; | |
5817ff8e | 61 | |
1acba85b JS |
62 | _DifferenceType __n = __end - __begin; |
63 | __num_samples = std::min(__num_samples, __n); | |
5817ff8e PC |
64 | |
65 | // Allocate uninitialized, to avoid default constructor. | |
77d16198 PC |
66 | _ValueType* __samples = static_cast<_ValueType*> |
67 | (::operator new(__num_samples * sizeof(_ValueType))); | |
5817ff8e | 68 | |
1acba85b | 69 | for (_DifferenceType __s = 0; __s < __num_samples; ++__s) |
15ac3c72 | 70 | { |
77d16198 PC |
71 | const unsigned long long __index = static_cast<unsigned long long> |
72 | (__s) * __n / __num_samples; | |
15ac3c72 JS |
73 | ::new(&(__samples[__s])) _ValueType(__begin[__index]); |
74 | } | |
c2ba9709 | 75 | |
1acba85b | 76 | __gnu_sequential::sort(__samples, __samples + __num_samples, __comp); |
c2ba9709 | 77 | |
77d16198 | 78 | _ValueType& __pivot = __samples[__pivot_rank * __num_samples / __n]; |
c2ba9709 | 79 | |
31380bc4 | 80 | __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool> |
77d16198 PC |
81 | __pred(__comp, __pivot); |
82 | _DifferenceType __split = __parallel_partition(__begin, __end, | |
83 | __pred, __num_threads); | |
c2ba9709 | 84 | |
0ecca7a6 PC |
85 | for (_DifferenceType __s = 0; __s < __num_samples; ++__s) |
86 | __samples[__s].~_ValueType(); | |
1acba85b | 87 | ::operator delete(__samples); |
1661473b | 88 | |
1acba85b | 89 | return __split; |
5817ff8e | 90 | } |
c2ba9709 JS |
91 | |
92 | /** @brief Unbalanced quicksort conquer step. | |
1acba85b JS |
93 | * @param __begin Begin iterator of subsequence. |
94 | * @param __end End iterator of subsequence. | |
95 | * @param __comp Comparator. | |
96 | * @param __num_threads Number of threads that are allowed to work on | |
c2ba9709 JS |
97 | * this part. |
98 | */ | |
1acba85b | 99 | template<typename _RAIter, typename _Compare> |
5817ff8e | 100 | void |
77d16198 PC |
101 | __parallel_sort_qs_conquer(_RAIter __begin, _RAIter __end, |
102 | _Compare __comp, | |
103 | _ThreadIndex __num_threads) | |
5817ff8e | 104 | { |
1acba85b JS |
105 | typedef std::iterator_traits<_RAIter> _TraitsType; |
106 | typedef typename _TraitsType::value_type _ValueType; | |
107 | typedef typename _TraitsType::difference_type _DifferenceType; | |
5817ff8e | 108 | |
1acba85b | 109 | if (__num_threads <= 1) |
15ac3c72 JS |
110 | { |
111 | __gnu_sequential::sort(__begin, __end, __comp); | |
112 | return; | |
113 | } | |
c2ba9709 | 114 | |
1acba85b | 115 | _DifferenceType __n = __end - __begin, __pivot_rank; |
c2ba9709 | 116 | |
1acba85b | 117 | if (__n <= 1) |
15ac3c72 | 118 | return; |
c2ba9709 | 119 | |
1acba85b | 120 | _ThreadIndex __num_threads_left; |
c2ba9709 | 121 | |
1acba85b | 122 | if ((__num_threads % 2) == 1) |
15ac3c72 | 123 | __num_threads_left = __num_threads / 2 + 1; |
5817ff8e | 124 | else |
15ac3c72 | 125 | __num_threads_left = __num_threads / 2; |
c2ba9709 | 126 | |
1acba85b | 127 | __pivot_rank = __n * __num_threads_left / __num_threads; |
c2ba9709 | 128 | |
77d16198 PC |
129 | _DifferenceType __split = __parallel_sort_qs_divide |
130 | (__begin, __end, __comp, __pivot_rank, | |
131 | _Settings::get().sort_qs_num_samples_preset, __num_threads); | |
c2ba9709 | 132 | |
a273a425 | 133 | #pragma omp parallel sections num_threads(2) |
5817ff8e | 134 | { |
c2ba9709 | 135 | #pragma omp section |
15ac3c72 | 136 | __parallel_sort_qs_conquer(__begin, __begin + __split, |
77d16198 | 137 | __comp, __num_threads_left); |
c2ba9709 | 138 | #pragma omp section |
15ac3c72 | 139 | __parallel_sort_qs_conquer(__begin + __split, __end, |
77d16198 | 140 | __comp, __num_threads - __num_threads_left); |
5817ff8e | 141 | } |
c2ba9709 | 142 | } |
c2ba9709 JS |
143 | |
144 | ||
c2ba9709 | 145 | /** @brief Unbalanced quicksort main call. |
1acba85b JS |
146 | * @param __begin Begin iterator of input sequence. |
147 | * @param __end End iterator input sequence, ignored. | |
148 | * @param __comp Comparator. | |
149 | * @param __num_threads Number of threads that are allowed to work on | |
c2ba9709 JS |
150 | * this part. |
151 | */ | |
1acba85b | 152 | template<typename _RAIter, typename _Compare> |
5817ff8e | 153 | void |
77d16198 PC |
154 | __parallel_sort_qs(_RAIter __begin, _RAIter __end, |
155 | _Compare __comp, | |
156 | _ThreadIndex __num_threads) | |
5817ff8e | 157 | { |
1acba85b | 158 | _GLIBCXX_CALL(__n) |
5817ff8e | 159 | |
1acba85b JS |
160 | typedef std::iterator_traits<_RAIter> _TraitsType; |
161 | typedef typename _TraitsType::value_type _ValueType; | |
162 | typedef typename _TraitsType::difference_type _DifferenceType; | |
5817ff8e | 163 | |
1acba85b | 164 | _DifferenceType __n = __end - __begin; |
5817ff8e PC |
165 | |
166 | // At least one element per processor. | |
1acba85b JS |
167 | if (__num_threads > __n) |
168 | __num_threads = static_cast<_ThreadIndex>(__n); | |
5817ff8e | 169 | |
15ac3c72 JS |
170 | __parallel_sort_qs_conquer( |
171 | __begin, __begin + __n, __comp, __num_threads); | |
5817ff8e | 172 | } |
c2ba9709 | 173 | |
e683ee2a | 174 | } //namespace __gnu_parallel |
c2ba9709 | 175 | |
cbcd1e45 | 176 | #endif /* _GLIBCXX_PARALLEL_QUICKSORT_H */ |