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