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 <ciso646>
17#include <functional>
18#include <future>
19#include <iterator>
20#include <memory>
21#include <type_traits>
22#include <vector>
23#include <boost/sort/sample_sort/sample_sort.hpp>
24#include <boost/sort/common/util/traits.hpp>
25
26
27namespace boost
28{
29namespace sort
30{
31namespace stable_detail
32{
33
34//---------------------------------------------------------------------------
35// USING SENTENCES
36//---------------------------------------------------------------------------
37namespace bsc = boost::sort::common;
38namespace bss = boost::sort::spin_detail;
39using bsc::range;
40using bsc::merge_half;
41using 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//----------------------------------------------------------------------------
48template <class Iter_t, class Compare = compare_iter <Iter_t> >
49struct 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::free (ptr: 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//-----------------------------------------------------------------------------
123template <class Iter_t, class Compare>
124parallel_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 using std::swap;
154 size_t nelem2 = nelem >> 1;
155 Iter_t it1 = first, it2 = last - 1;
156 for (size_t i = 0; i < nelem2; ++i)
157 swap(*(it1++), *(it2--));
158 return;
159 };
160
161 ptr = reinterpret_cast <value_t*>
162 (std::malloc (size: nptr * sizeof(value_t)));
163
164 if (ptr == nullptr) throw std::bad_alloc();
165
166 //---------------------------------------------------------------------
167 // Parallel Process
168 //---------------------------------------------------------------------
169 range<Iter_t> range_first(range_initial.first, range_initial.first + nptr);
170
171 range<Iter_t> range_second(range_initial.first + nptr, range_initial.last);
172
173 range<value_t *> range_buffer(ptr, ptr + nptr);
174
175 try
176 {
177 sample_sort<Iter_t, Compare>
178 (range_initial.first, range_initial.first + nptr,
179 comp, nthread, range_buffer);
180 } catch (std::bad_alloc &)
181 {
182 destroy_all();
183 throw std::bad_alloc();
184 };
185
186 try
187 {
188 sample_sort<Iter_t, Compare>
189 (range_initial.first + nptr,
190 range_initial.last, comp, nthread, range_buffer);
191 } catch (std::bad_alloc &)
192 {
193 destroy_all();
194 throw std::bad_alloc();
195 };
196
197 range_buffer = move_construct(range_buffer, range_first);
198 range_initial = merge_half(range_initial, range_buffer, range_second, comp);
199 destroy (range_buffer);
200
201
202
203}; // end of constructor
204
205//
206//****************************************************************************
207};// End namespace stable_detail
208//****************************************************************************
209//
210
211//---------------------------------------------------------------------------
212// USING SENTENCES
213//---------------------------------------------------------------------------
214namespace bsc = boost::sort::common;
215namespace bscu = bsc::util;
216namespace bss = boost::sort::spin_detail;
217using bsc::range;
218using bsc::merge_half;
219//
220//############################################################################
221// ##
222// ##
223// P A R A L L E L _ S T A B L E _ S O R T ##
224// ##
225// ##
226//############################################################################
227//
228//-----------------------------------------------------------------------------
229// function : parallel_stable_sort
230/// @brief : parallel stable sort with 2 parameters
231///
232/// @param first : iterator to the first element of the range to sort
233/// @param last : iterator after the last element to the range to sort
234//-----------------------------------------------------------------------------
235template<class Iter_t>
236void parallel_stable_sort(Iter_t first, Iter_t last)
237{
238 typedef bscu::compare_iter<Iter_t> Compare;
239 stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last);
240};
241//
242//-----------------------------------------------------------------------------
243// function : parallel_stable_sort
244/// @brief parallel stable sort with 3 parameters. The third is the number
245/// of threads
246///
247/// @param first : iterator to the first element of the range to sort
248/// @param last : iterator after the last element to the range to sort
249/// @param nthread : Number of threads to use in the process. When this value
250/// is lower than 2, the sorting is done with 1 thread
251//-----------------------------------------------------------------------------
252template<class Iter_t>
253void parallel_stable_sort(Iter_t first, Iter_t last, uint32_t nthread)
254{
255 typedef bscu::compare_iter<Iter_t> Compare;
256 stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last, nthread);
257};
258//
259//-----------------------------------------------------------------------------
260// function : parallel_stable_sort
261/// @brief : parallel stable sort with 3 parameters. The thisrd is the
262/// comparison object
263///
264/// @param first : iterator to the first element of the range to sort
265/// @param last : iterator after the last element to the range to sort
266/// @param comp : object for to compare two elements pointed by Iter_t
267/// iterators
268//-----------------------------------------------------------------------------
269template <class Iter_t, class Compare,
270 bscu::enable_if_not_integral<Compare> * = nullptr>
271void parallel_stable_sort(Iter_t first, Iter_t last, Compare comp)
272{
273 stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last, comp);
274};
275
276//
277//-----------------------------------------------------------------------------
278// function : parallel_stable_sort
279/// @brief : parallel stable sort with 3 parameters.
280///
281/// @param first : iterator to the first element of the range to sort
282/// @param last : iterator after the last element to the range to sort
283/// @param comp : object for to compare two elements pointed by Iter_t
284/// iterators
285/// @param nthread : Number of threads to use in the process. When this value
286/// is lower than 2, the sorting is done with 1 thread
287//-----------------------------------------------------------------------------
288template<class Iter_t, class Compare>
289void parallel_stable_sort (Iter_t first, Iter_t last, Compare comp,
290 uint32_t nthread)
291{
292 stable_detail::parallel_stable_sort<Iter_t, Compare>
293 (first, last, comp, nthread);
294}
295//
296//****************************************************************************
297};// End namespace sort
298};// End namespace boost
299//****************************************************************************
300//
301#endif
302

source code of boost/libs/sort/include/boost/sort/parallel_stable_sort/parallel_stable_sort.hpp