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 //------------------------------------------------------------------------
parallel_stable_sortboost::sort::stable_detail::parallel_stable_sort67 parallel_stable_sort (Iter_t first, Iter_t last)
68 : parallel_stable_sort (first, last, Compare(),
69 std::thread::hardware_concurrency()) { };
70
parallel_stable_sortboost::sort::stable_detail::parallel_stable_sort71 parallel_stable_sort (Iter_t first, Iter_t last, Compare cmp)
72 : parallel_stable_sort (first, last, cmp,
73 std::thread::hardware_concurrency()) { };
74
parallel_stable_sortboost::sort::stable_detail::parallel_stable_sort75 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 //-----------------------------------------------------------------------------
destroy_allboost::sort::stable_detail::parallel_stable_sort87 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 //-----------------------------------------------------------------------------
~parallel_stable_sortboost::sort::stable_detail::parallel_stable_sort97 ~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>
parallel_stable_sort(Iter_t first,Iter_t last,Compare comp,uint32_t nthread)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
221 /// @brief : parallel stable sort with 2 parameters
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>
parallel_stable_sort(Iter_t first,Iter_t last)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
235 /// @brief parallel stable sort with 3 parameters. The third is the number
236 /// of threads
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>
parallel_stable_sort(Iter_t first,Iter_t last,uint32_t nthread)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
252 /// @brief : parallel stable sort with 3 parameters. The thisrd is the
253 /// comparison object
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>
parallel_stable_sort(Iter_t first,Iter_t last,Compare comp)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 };
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>
parallel_stable_sort(Iter_t first,Iter_t last,Compare comp,uint32_t nthread)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 }
286 //
287 //****************************************************************************
288 };// End namespace sort
289 };// End namespace boost
290 //****************************************************************************
291 //
292 #endif
293