]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | //---------------------------------------------------------------------------- |
2 | /// @file parallel_stable_sort.hpp | |
3 | /// @brief This file contains the class parallel_stable_sort | |
4 | /// | |
5 | /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n | |
6 | /// Distributed under the Boost Software License, Version 1.0.\n | |
7 | /// ( See accompanying file LICENSE_1_0.txt or copy at | |
8 | /// http://www.boost.org/LICENSE_1_0.txt ) | |
9 | /// @version 0.1 | |
10 | /// | |
11 | /// @remarks | |
12 | //----------------------------------------------------------------------------- | |
13 | #ifndef __BOOST_SORT_PARALLEL_DETAIL_PARALLEL_STABLE_SORT_HPP | |
14 | #define __BOOST_SORT_PARALLEL_DETAIL_PARALLEL_STABLE_SORT_HPP | |
15 | ||
1e59de90 | 16 | #include <ciso646> |
11fdf7f2 TL |
17 | #include <functional> |
18 | #include <future> | |
19 | #include <iterator> | |
20 | #include <memory> | |
21 | #include <type_traits> | |
22 | #include <vector> | |
1e59de90 TL |
23 | #include <boost/sort/sample_sort/sample_sort.hpp> |
24 | #include <boost/sort/common/util/traits.hpp> | |
25 | ||
11fdf7f2 TL |
26 | |
27 | namespace boost | |
28 | { | |
29 | namespace sort | |
30 | { | |
31 | namespace stable_detail | |
32 | { | |
33 | ||
34 | //--------------------------------------------------------------------------- | |
35 | // USING SENTENCES | |
36 | //--------------------------------------------------------------------------- | |
37 | namespace bsc = boost::sort::common; | |
38 | namespace bss = boost::sort::spin_detail; | |
39 | using bsc::range; | |
40 | using bsc::merge_half; | |
41 | using boost::sort::sample_detail::sample_sort; | |
42 | // | |
43 | ///--------------------------------------------------------------------------- | |
44 | /// @struct parallel_stable_sort | |
45 | /// @brief This a structure for to implement a parallel stable sort, exception | |
46 | /// safe | |
47 | //---------------------------------------------------------------------------- | |
48 | template <class Iter_t, class Compare = compare_iter <Iter_t> > | |
49 | struct parallel_stable_sort | |
50 | { | |
51 | //------------------------------------------------------------------------- | |
52 | // DEFINITIONS | |
53 | //------------------------------------------------------------------------- | |
54 | typedef value_iter<Iter_t> value_t; | |
55 | ||
56 | //------------------------------------------------------------------------- | |
57 | // VARIABLES | |
58 | //------------------------------------------------------------------------- | |
59 | // Number of elements to sort | |
60 | size_t nelem; | |
61 | // Pointer to the auxiliary memory needed for the algorithm | |
62 | value_t *ptr; | |
63 | // Minimal number of elements for to be sorted in parallel mode | |
64 | const size_t nelem_min = 1 << 16; | |
65 | ||
66 | //------------------------------------------------------------------------ | |
67 | // F U N C T I O N S | |
68 | //------------------------------------------------------------------------ | |
69 | parallel_stable_sort (Iter_t first, Iter_t last) | |
70 | : parallel_stable_sort (first, last, Compare(), | |
71 | std::thread::hardware_concurrency()) { }; | |
72 | ||
73 | parallel_stable_sort (Iter_t first, Iter_t last, Compare cmp) | |
74 | : parallel_stable_sort (first, last, cmp, | |
75 | std::thread::hardware_concurrency()) { }; | |
76 | ||
77 | parallel_stable_sort (Iter_t first, Iter_t last, uint32_t num_thread) | |
78 | : parallel_stable_sort (first, last, Compare(), num_thread) { }; | |
79 | ||
80 | parallel_stable_sort (Iter_t first, Iter_t last, Compare cmp, | |
81 | uint32_t num_thread); | |
82 | ||
83 | // | |
84 | //----------------------------------------------------------------------------- | |
85 | // function : destroy_all | |
86 | /// @brief The utility is to destroy the temporary buffer used in the | |
87 | /// sorting process | |
88 | //----------------------------------------------------------------------------- | |
89 | void destroy_all() | |
90 | { | |
91 | if (ptr != nullptr) std::return_temporary_buffer(ptr); | |
92 | }; | |
93 | // | |
94 | //----------------------------------------------------------------------------- | |
95 | // function :~parallel_stable_sort | |
96 | /// @brief destructor of the class. The utility is to destroy the temporary | |
97 | /// buffer used in the sorting process | |
98 | //----------------------------------------------------------------------------- | |
99 | ~parallel_stable_sort() {destroy_all(); } ; | |
100 | }; | |
101 | // end struct parallel_stable_sort | |
102 | ||
103 | // | |
104 | //############################################################################ | |
105 | // ## | |
106 | // ## | |
107 | // N O N I N L I N E F U N C T I O N S ## | |
108 | // ## | |
109 | // ## | |
110 | //############################################################################ | |
111 | // | |
112 | //----------------------------------------------------------------------------- | |
113 | // function : parallel_stable_sort | |
114 | /// @brief constructor of the class | |
115 | /// | |
116 | /// @param first : iterator to the first element of the range to sort | |
117 | /// @param last : iterator after the last element to the range to sort | |
118 | /// @param comp : object for to compare two elements pointed by Iter_t | |
119 | /// iterators | |
120 | /// @param nthread : Number of threads to use in the process. When this value | |
121 | /// is lower than 2, the sorting is done with 1 thread | |
122 | //----------------------------------------------------------------------------- | |
123 | template <class Iter_t, class Compare> | |
124 | parallel_stable_sort <Iter_t, Compare> | |
125 | ::parallel_stable_sort (Iter_t first, Iter_t last, Compare comp, | |
126 | uint32_t nthread) : nelem(0), ptr(nullptr) | |
127 | { | |
128 | range<Iter_t> range_initial(first, last); | |
129 | assert(range_initial.valid()); | |
130 | ||
131 | nelem = range_initial.size(); | |
132 | size_t nptr = (nelem + 1) >> 1; | |
133 | ||
134 | if (nelem < nelem_min or nthread < 2) | |
135 | { | |
136 | bss::spinsort<Iter_t, Compare> | |
137 | (range_initial.first, range_initial.last, comp); | |
138 | return; | |
139 | }; | |
140 | ||
141 | //------------------- check if sort -------------------------------------- | |
142 | bool sw = true; | |
143 | for (Iter_t it1 = first, it2 = first + 1; | |
144 | it2 != last and (sw = not comp(*it2, *it1)); it1 = it2++); | |
145 | if (sw) return; | |
146 | ||
147 | //------------------- check if reverse sort --------------------------- | |
148 | sw = true; | |
149 | for (Iter_t it1 = first, it2 = first + 1; | |
150 | it2 != last and (sw = comp(*it2, *it1)); it1 = it2++); | |
151 | if (sw) | |
152 | { | |
153 | size_t nelem2 = nelem >> 1; | |
154 | Iter_t it1 = first, it2 = last - 1; | |
155 | for (size_t i = 0; i < nelem2; ++i) | |
156 | std::swap(*(it1++), *(it2--)); | |
157 | return; | |
158 | }; | |
159 | ||
160 | ptr = std::get_temporary_buffer<value_t>(nptr).first; | |
161 | if (ptr == nullptr) throw std::bad_alloc(); | |
162 | ||
163 | //--------------------------------------------------------------------- | |
164 | // Parallel Process | |
165 | //--------------------------------------------------------------------- | |
166 | range<Iter_t> range_first(range_initial.first, range_initial.first + nptr); | |
167 | ||
168 | range<Iter_t> range_second(range_initial.first + nptr, range_initial.last); | |
169 | ||
170 | range<value_t *> range_buffer(ptr, ptr + nptr); | |
171 | ||
172 | try | |
173 | { | |
174 | sample_sort<Iter_t, Compare> | |
175 | (range_initial.first, range_initial.first + nptr, | |
176 | comp, nthread, range_buffer); | |
177 | } catch (std::bad_alloc &) | |
178 | { | |
179 | destroy_all(); | |
180 | throw std::bad_alloc(); | |
181 | }; | |
182 | ||
183 | try | |
184 | { | |
185 | sample_sort<Iter_t, Compare> | |
186 | (range_initial.first + nptr, | |
187 | range_initial.last, comp, nthread, range_buffer); | |
188 | } catch (std::bad_alloc &) | |
189 | { | |
190 | destroy_all(); | |
191 | throw std::bad_alloc(); | |
192 | }; | |
193 | ||
1e59de90 | 194 | range_buffer = move_construct(range_buffer, range_first); |
11fdf7f2 | 195 | range_initial = merge_half(range_initial, range_buffer, range_second, comp); |
1e59de90 TL |
196 | destroy (range_buffer); |
197 | ||
198 | ||
199 | ||
11fdf7f2 TL |
200 | }; // end of constructor |
201 | ||
202 | // | |
203 | //**************************************************************************** | |
204 | };// End namespace stable_detail | |
205 | //**************************************************************************** | |
206 | // | |
207 | ||
208 | //--------------------------------------------------------------------------- | |
209 | // USING SENTENCES | |
210 | //--------------------------------------------------------------------------- | |
211 | namespace bsc = boost::sort::common; | |
212 | namespace bscu = bsc::util; | |
213 | namespace bss = boost::sort::spin_detail; | |
214 | using bsc::range; | |
215 | using bsc::merge_half; | |
216 | // | |
217 | //############################################################################ | |
218 | // ## | |
219 | // ## | |
220 | // P A R A L L E L _ S T A B L E _ S O R T ## | |
221 | // ## | |
222 | // ## | |
223 | //############################################################################ | |
224 | // | |
225 | //----------------------------------------------------------------------------- | |
226 | // function : parallel_stable_sort | |
92f5a8d4 | 227 | /// @brief : parallel stable sort with 2 parameters |
11fdf7f2 TL |
228 | /// |
229 | /// @param first : iterator to the first element of the range to sort | |
230 | /// @param last : iterator after the last element to the range to sort | |
231 | //----------------------------------------------------------------------------- | |
232 | template<class Iter_t> | |
233 | void parallel_stable_sort(Iter_t first, Iter_t last) | |
234 | { | |
235 | typedef bscu::compare_iter<Iter_t> Compare; | |
236 | stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last); | |
237 | }; | |
238 | // | |
239 | //----------------------------------------------------------------------------- | |
240 | // function : parallel_stable_sort | |
92f5a8d4 TL |
241 | /// @brief parallel stable sort with 3 parameters. The third is the number |
242 | /// of threads | |
11fdf7f2 TL |
243 | /// |
244 | /// @param first : iterator to the first element of the range to sort | |
245 | /// @param last : iterator after the last element to the range to sort | |
246 | /// @param nthread : Number of threads to use in the process. When this value | |
247 | /// is lower than 2, the sorting is done with 1 thread | |
248 | //----------------------------------------------------------------------------- | |
249 | template<class Iter_t> | |
250 | void parallel_stable_sort(Iter_t first, Iter_t last, uint32_t nthread) | |
251 | { | |
252 | typedef bscu::compare_iter<Iter_t> Compare; | |
253 | stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last, nthread); | |
254 | }; | |
255 | // | |
256 | //----------------------------------------------------------------------------- | |
257 | // function : parallel_stable_sort | |
92f5a8d4 TL |
258 | /// @brief : parallel stable sort with 3 parameters. The thisrd is the |
259 | /// comparison object | |
11fdf7f2 TL |
260 | /// |
261 | /// @param first : iterator to the first element of the range to sort | |
262 | /// @param last : iterator after the last element to the range to sort | |
263 | /// @param comp : object for to compare two elements pointed by Iter_t | |
264 | /// iterators | |
265 | //----------------------------------------------------------------------------- | |
266 | template <class Iter_t, class Compare, | |
267 | bscu::enable_if_not_integral<Compare> * = nullptr> | |
268 | void parallel_stable_sort(Iter_t first, Iter_t last, Compare comp) | |
269 | { | |
270 | stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last, comp); | |
271 | }; | |
92f5a8d4 TL |
272 | |
273 | // | |
274 | //----------------------------------------------------------------------------- | |
275 | // function : parallel_stable_sort | |
276 | /// @brief : parallel stable sort with 3 parameters. | |
277 | /// | |
278 | /// @param first : iterator to the first element of the range to sort | |
279 | /// @param last : iterator after the last element to the range to sort | |
280 | /// @param comp : object for to compare two elements pointed by Iter_t | |
281 | /// iterators | |
282 | /// @param nthread : Number of threads to use in the process. When this value | |
283 | /// is lower than 2, the sorting is done with 1 thread | |
284 | //----------------------------------------------------------------------------- | |
285 | template<class Iter_t, class Compare> | |
286 | void parallel_stable_sort (Iter_t first, Iter_t last, Compare comp, | |
287 | uint32_t nthread) | |
288 | { | |
289 | stable_detail::parallel_stable_sort<Iter_t, Compare> | |
290 | (first, last, comp, nthread); | |
291 | } | |
11fdf7f2 TL |
292 | // |
293 | //**************************************************************************** | |
294 | };// End namespace sort | |
295 | };// End namespace boost | |
296 | //**************************************************************************** | |
297 | // | |
298 | #endif |