1 |
424 |
jeremybenn |
// -*- C++ -*-
|
2 |
|
|
|
3 |
|
|
// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
|
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
|
8 |
|
|
// Foundation; either version 3, or (at your option) any later
|
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 |
|
|
|
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/>.
|
24 |
|
|
|
25 |
|
|
/** @file parallel/multiway_mergesort.h
|
26 |
|
|
* @brief Parallel multiway merge sort.
|
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_MULTIWAY_MERGESORT_H
|
33 |
|
|
#define _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H 1
|
34 |
|
|
|
35 |
|
|
#include <vector>
|
36 |
|
|
|
37 |
|
|
#include <parallel/basic_iterator.h>
|
38 |
|
|
#include <bits/stl_algo.h>
|
39 |
|
|
#include <parallel/parallel.h>
|
40 |
|
|
#include <parallel/multiway_merge.h>
|
41 |
|
|
|
42 |
|
|
namespace __gnu_parallel
|
43 |
|
|
{
|
44 |
|
|
/** @brief Subsequence description. */
|
45 |
|
|
template<typename _DifferenceTp>
|
46 |
|
|
struct _Piece
|
47 |
|
|
{
|
48 |
|
|
typedef _DifferenceTp _DifferenceType;
|
49 |
|
|
|
50 |
|
|
/** @brief Begin of subsequence. */
|
51 |
|
|
_DifferenceType _M_begin;
|
52 |
|
|
|
53 |
|
|
/** @brief End of subsequence. */
|
54 |
|
|
_DifferenceType _M_end;
|
55 |
|
|
};
|
56 |
|
|
|
57 |
|
|
/** @brief Data accessed by all threads.
|
58 |
|
|
*
|
59 |
|
|
* PMWMS = parallel multiway mergesort */
|
60 |
|
|
template<typename _RAIter>
|
61 |
|
|
struct _PMWMSSortingData
|
62 |
|
|
{
|
63 |
|
|
typedef std::iterator_traits<_RAIter> _TraitsType;
|
64 |
|
|
typedef typename _TraitsType::value_type _ValueType;
|
65 |
|
|
typedef typename _TraitsType::difference_type _DifferenceType;
|
66 |
|
|
|
67 |
|
|
/** @brief Number of threads involved. */
|
68 |
|
|
_ThreadIndex _M_num_threads;
|
69 |
|
|
|
70 |
|
|
/** @brief Input __begin. */
|
71 |
|
|
_RAIter _M_source;
|
72 |
|
|
|
73 |
|
|
/** @brief Start indices, per thread. */
|
74 |
|
|
_DifferenceType* _M_starts;
|
75 |
|
|
|
76 |
|
|
/** @brief Storage in which to sort. */
|
77 |
|
|
_ValueType** _M_temporary;
|
78 |
|
|
|
79 |
|
|
/** @brief Samples. */
|
80 |
|
|
_ValueType* _M_samples;
|
81 |
|
|
|
82 |
|
|
/** @brief Offsets to add to the found positions. */
|
83 |
|
|
_DifferenceType* _M_offsets;
|
84 |
|
|
|
85 |
|
|
/** @brief Pieces of data to merge @c [thread][__sequence] */
|
86 |
|
|
std::vector<_Piece<_DifferenceType> >* _M_pieces;
|
87 |
|
|
};
|
88 |
|
|
|
89 |
|
|
/**
|
90 |
|
|
* @brief Select _M_samples from a sequence.
|
91 |
|
|
* @param __sd Pointer to algorithm data. _Result will be placed in
|
92 |
|
|
* @c __sd->_M_samples.
|
93 |
|
|
* @param __num_samples Number of _M_samples to select.
|
94 |
|
|
*/
|
95 |
|
|
template<typename _RAIter, typename _DifferenceTp>
|
96 |
|
|
void
|
97 |
|
|
__determine_samples(_PMWMSSortingData<_RAIter>* __sd,
|
98 |
|
|
_DifferenceTp __num_samples)
|
99 |
|
|
{
|
100 |
|
|
typedef std::iterator_traits<_RAIter> _TraitsType;
|
101 |
|
|
typedef typename _TraitsType::value_type _ValueType;
|
102 |
|
|
typedef _DifferenceTp _DifferenceType;
|
103 |
|
|
|
104 |
|
|
_ThreadIndex __iam = omp_get_thread_num();
|
105 |
|
|
|
106 |
|
|
_DifferenceType* __es = new _DifferenceType[__num_samples + 2];
|
107 |
|
|
|
108 |
|
|
equally_split(__sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam],
|
109 |
|
|
__num_samples + 1, __es);
|
110 |
|
|
|
111 |
|
|
for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
|
112 |
|
|
::new(&(__sd->_M_samples[__iam * __num_samples + __i]))
|
113 |
|
|
_ValueType(__sd->_M_source[__sd->_M_starts[__iam]
|
114 |
|
|
+ __es[__i + 1]]);
|
115 |
|
|
|
116 |
|
|
delete[] __es;
|
117 |
|
|
}
|
118 |
|
|
|
119 |
|
|
/** @brief Split consistently. */
|
120 |
|
|
template<bool __exact, typename _RAIter,
|
121 |
|
|
typename _Compare, typename _SortingPlacesIterator>
|
122 |
|
|
struct _SplitConsistently
|
123 |
|
|
{ };
|
124 |
|
|
|
125 |
|
|
/** @brief Split by exact splitting. */
|
126 |
|
|
template<typename _RAIter, typename _Compare,
|
127 |
|
|
typename _SortingPlacesIterator>
|
128 |
|
|
struct _SplitConsistently<true, _RAIter, _Compare, _SortingPlacesIterator>
|
129 |
|
|
{
|
130 |
|
|
void
|
131 |
|
|
operator()(const _ThreadIndex __iam,
|
132 |
|
|
_PMWMSSortingData<_RAIter>* __sd,
|
133 |
|
|
_Compare& __comp,
|
134 |
|
|
const typename
|
135 |
|
|
std::iterator_traits<_RAIter>::difference_type
|
136 |
|
|
__num_samples) const
|
137 |
|
|
{
|
138 |
|
|
# pragma omp barrier
|
139 |
|
|
|
140 |
|
|
std::vector<std::pair<_SortingPlacesIterator,
|
141 |
|
|
_SortingPlacesIterator> >
|
142 |
|
|
__seqs(__sd->_M_num_threads);
|
143 |
|
|
for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; __s++)
|
144 |
|
|
__seqs[__s] = std::make_pair(__sd->_M_temporary[__s],
|
145 |
|
|
__sd->_M_temporary[__s]
|
146 |
|
|
+ (__sd->_M_starts[__s + 1]
|
147 |
|
|
- __sd->_M_starts[__s]));
|
148 |
|
|
|
149 |
|
|
std::vector<_SortingPlacesIterator> __offsets(__sd->_M_num_threads);
|
150 |
|
|
|
151 |
|
|
// if not last thread
|
152 |
|
|
if (__iam < __sd->_M_num_threads - 1)
|
153 |
|
|
multiseq_partition(__seqs.begin(), __seqs.end(),
|
154 |
|
|
__sd->_M_starts[__iam + 1], __offsets.begin(),
|
155 |
|
|
__comp);
|
156 |
|
|
|
157 |
|
|
for (_ThreadIndex __seq = 0; __seq < __sd->_M_num_threads; __seq++)
|
158 |
|
|
{
|
159 |
|
|
// for each sequence
|
160 |
|
|
if (__iam < (__sd->_M_num_threads - 1))
|
161 |
|
|
__sd->_M_pieces[__iam][__seq]._M_end
|
162 |
|
|
= __offsets[__seq] - __seqs[__seq].first;
|
163 |
|
|
else
|
164 |
|
|
// very end of this sequence
|
165 |
|
|
__sd->_M_pieces[__iam][__seq]._M_end =
|
166 |
|
|
__sd->_M_starts[__seq + 1] - __sd->_M_starts[__seq];
|
167 |
|
|
}
|
168 |
|
|
|
169 |
|
|
# pragma omp barrier
|
170 |
|
|
|
171 |
|
|
for (_ThreadIndex __seq = 0; __seq < __sd->_M_num_threads; __seq++)
|
172 |
|
|
{
|
173 |
|
|
// For each sequence.
|
174 |
|
|
if (__iam > 0)
|
175 |
|
|
__sd->_M_pieces[__iam][__seq]._M_begin =
|
176 |
|
|
__sd->_M_pieces[__iam - 1][__seq]._M_end;
|
177 |
|
|
else
|
178 |
|
|
// Absolute beginning.
|
179 |
|
|
__sd->_M_pieces[__iam][__seq]._M_begin = 0;
|
180 |
|
|
}
|
181 |
|
|
}
|
182 |
|
|
};
|
183 |
|
|
|
184 |
|
|
/** @brief Split by sampling. */
|
185 |
|
|
template<typename _RAIter, typename _Compare,
|
186 |
|
|
typename _SortingPlacesIterator>
|
187 |
|
|
struct _SplitConsistently<false, _RAIter, _Compare, _SortingPlacesIterator>
|
188 |
|
|
{
|
189 |
|
|
void
|
190 |
|
|
operator()(const _ThreadIndex __iam,
|
191 |
|
|
_PMWMSSortingData<_RAIter>* __sd,
|
192 |
|
|
_Compare& __comp,
|
193 |
|
|
const typename
|
194 |
|
|
std::iterator_traits<_RAIter>::difference_type
|
195 |
|
|
__num_samples) const
|
196 |
|
|
{
|
197 |
|
|
typedef std::iterator_traits<_RAIter> _TraitsType;
|
198 |
|
|
typedef typename _TraitsType::value_type _ValueType;
|
199 |
|
|
typedef typename _TraitsType::difference_type _DifferenceType;
|
200 |
|
|
|
201 |
|
|
__determine_samples(__sd, __num_samples);
|
202 |
|
|
|
203 |
|
|
# pragma omp barrier
|
204 |
|
|
|
205 |
|
|
# pragma omp single
|
206 |
|
|
__gnu_sequential::sort(__sd->_M_samples,
|
207 |
|
|
__sd->_M_samples
|
208 |
|
|
+ (__num_samples * __sd->_M_num_threads),
|
209 |
|
|
__comp);
|
210 |
|
|
|
211 |
|
|
# pragma omp barrier
|
212 |
|
|
|
213 |
|
|
for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; ++__s)
|
214 |
|
|
{
|
215 |
|
|
// For each sequence.
|
216 |
|
|
if (__num_samples * __iam > 0)
|
217 |
|
|
__sd->_M_pieces[__iam][__s]._M_begin =
|
218 |
|
|
std::lower_bound(__sd->_M_temporary[__s],
|
219 |
|
|
__sd->_M_temporary[__s]
|
220 |
|
|
+ (__sd->_M_starts[__s + 1]
|
221 |
|
|
- __sd->_M_starts[__s]),
|
222 |
|
|
__sd->_M_samples[__num_samples * __iam],
|
223 |
|
|
__comp)
|
224 |
|
|
- __sd->_M_temporary[__s];
|
225 |
|
|
else
|
226 |
|
|
// Absolute beginning.
|
227 |
|
|
__sd->_M_pieces[__iam][__s]._M_begin = 0;
|
228 |
|
|
|
229 |
|
|
if ((__num_samples * (__iam + 1)) <
|
230 |
|
|
(__num_samples * __sd->_M_num_threads))
|
231 |
|
|
__sd->_M_pieces[__iam][__s]._M_end =
|
232 |
|
|
std::lower_bound(__sd->_M_temporary[__s],
|
233 |
|
|
__sd->_M_temporary[__s]
|
234 |
|
|
+ (__sd->_M_starts[__s + 1]
|
235 |
|
|
- __sd->_M_starts[__s]),
|
236 |
|
|
__sd->_M_samples[__num_samples * (__iam + 1)],
|
237 |
|
|
__comp)
|
238 |
|
|
- __sd->_M_temporary[__s];
|
239 |
|
|
else
|
240 |
|
|
// Absolute end.
|
241 |
|
|
__sd->_M_pieces[__iam][__s]._M_end = (__sd->_M_starts[__s + 1]
|
242 |
|
|
- __sd->_M_starts[__s]);
|
243 |
|
|
}
|
244 |
|
|
}
|
245 |
|
|
};
|
246 |
|
|
|
247 |
|
|
template<bool __stable, typename _RAIter, typename _Compare>
|
248 |
|
|
struct __possibly_stable_sort
|
249 |
|
|
{ };
|
250 |
|
|
|
251 |
|
|
template<typename _RAIter, typename _Compare>
|
252 |
|
|
struct __possibly_stable_sort<true, _RAIter, _Compare>
|
253 |
|
|
{
|
254 |
|
|
void operator()(const _RAIter& __begin,
|
255 |
|
|
const _RAIter& __end, _Compare& __comp) const
|
256 |
|
|
{ __gnu_sequential::stable_sort(__begin, __end, __comp); }
|
257 |
|
|
};
|
258 |
|
|
|
259 |
|
|
template<typename _RAIter, typename _Compare>
|
260 |
|
|
struct __possibly_stable_sort<false, _RAIter, _Compare>
|
261 |
|
|
{
|
262 |
|
|
void operator()(const _RAIter __begin,
|
263 |
|
|
const _RAIter __end, _Compare& __comp) const
|
264 |
|
|
{ __gnu_sequential::sort(__begin, __end, __comp); }
|
265 |
|
|
};
|
266 |
|
|
|
267 |
|
|
template<bool __stable, typename Seq_RAIter,
|
268 |
|
|
typename _RAIter, typename _Compare,
|
269 |
|
|
typename DiffType>
|
270 |
|
|
struct __possibly_stable_multiway_merge
|
271 |
|
|
{ };
|
272 |
|
|
|
273 |
|
|
template<typename Seq_RAIter, typename _RAIter,
|
274 |
|
|
typename _Compare, typename _DiffType>
|
275 |
|
|
struct __possibly_stable_multiway_merge<true, Seq_RAIter,
|
276 |
|
|
_RAIter, _Compare, _DiffType>
|
277 |
|
|
{
|
278 |
|
|
void operator()(const Seq_RAIter& __seqs_begin,
|
279 |
|
|
const Seq_RAIter& __seqs_end,
|
280 |
|
|
const _RAIter& __target,
|
281 |
|
|
_Compare& __comp,
|
282 |
|
|
_DiffType __length_am) const
|
283 |
|
|
{ stable_multiway_merge(__seqs_begin, __seqs_end, __target,
|
284 |
|
|
__length_am, __comp, sequential_tag()); }
|
285 |
|
|
};
|
286 |
|
|
|
287 |
|
|
template<typename Seq_RAIter, typename _RAIter,
|
288 |
|
|
typename _Compare, typename _DiffType>
|
289 |
|
|
struct __possibly_stable_multiway_merge<false, Seq_RAIter,
|
290 |
|
|
_RAIter, _Compare, _DiffType>
|
291 |
|
|
{
|
292 |
|
|
void operator()(const Seq_RAIter& __seqs_begin,
|
293 |
|
|
const Seq_RAIter& __seqs_end,
|
294 |
|
|
const _RAIter& __target,
|
295 |
|
|
_Compare& __comp,
|
296 |
|
|
_DiffType __length_am) const
|
297 |
|
|
{ multiway_merge(__seqs_begin, __seqs_end, __target, __length_am,
|
298 |
|
|
__comp, sequential_tag()); }
|
299 |
|
|
};
|
300 |
|
|
|
301 |
|
|
/** @brief PMWMS code executed by each thread.
|
302 |
|
|
* @param __sd Pointer to algorithm data.
|
303 |
|
|
* @param __comp Comparator.
|
304 |
|
|
*/
|
305 |
|
|
template<bool __stable, bool __exact, typename _RAIter,
|
306 |
|
|
typename _Compare>
|
307 |
|
|
void
|
308 |
|
|
parallel_sort_mwms_pu(_PMWMSSortingData<_RAIter>* __sd,
|
309 |
|
|
_Compare& __comp)
|
310 |
|
|
{
|
311 |
|
|
typedef std::iterator_traits<_RAIter> _TraitsType;
|
312 |
|
|
typedef typename _TraitsType::value_type _ValueType;
|
313 |
|
|
typedef typename _TraitsType::difference_type _DifferenceType;
|
314 |
|
|
|
315 |
|
|
_ThreadIndex __iam = omp_get_thread_num();
|
316 |
|
|
|
317 |
|
|
// Length of this thread's chunk, before merging.
|
318 |
|
|
_DifferenceType __length_local =
|
319 |
|
|
__sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam];
|
320 |
|
|
|
321 |
|
|
// Sort in temporary storage, leave space for sentinel.
|
322 |
|
|
|
323 |
|
|
typedef _ValueType* _SortingPlacesIterator;
|
324 |
|
|
|
325 |
|
|
__sd->_M_temporary[__iam] =
|
326 |
|
|
static_cast<_ValueType*>(::operator new(sizeof(_ValueType)
|
327 |
|
|
* (__length_local + 1)));
|
328 |
|
|
|
329 |
|
|
// Copy there.
|
330 |
|
|
std::uninitialized_copy(__sd->_M_source + __sd->_M_starts[__iam],
|
331 |
|
|
__sd->_M_source + __sd->_M_starts[__iam]
|
332 |
|
|
+ __length_local,
|
333 |
|
|
__sd->_M_temporary[__iam]);
|
334 |
|
|
|
335 |
|
|
__possibly_stable_sort<__stable, _SortingPlacesIterator, _Compare>()
|
336 |
|
|
(__sd->_M_temporary[__iam],
|
337 |
|
|
__sd->_M_temporary[__iam] + __length_local,
|
338 |
|
|
__comp);
|
339 |
|
|
|
340 |
|
|
// Invariant: locally sorted subsequence in sd->_M_temporary[__iam],
|
341 |
|
|
// __sd->_M_temporary[__iam] + __length_local.
|
342 |
|
|
|
343 |
|
|
// No barrier here: Synchronization is done by the splitting routine.
|
344 |
|
|
|
345 |
|
|
_DifferenceType __num_samples =
|
346 |
|
|
_Settings::get().sort_mwms_oversampling * __sd->_M_num_threads - 1;
|
347 |
|
|
_SplitConsistently<__exact, _RAIter, _Compare, _SortingPlacesIterator>()
|
348 |
|
|
(__iam, __sd, __comp, __num_samples);
|
349 |
|
|
|
350 |
|
|
// Offset from __target __begin, __length after merging.
|
351 |
|
|
_DifferenceType __offset = 0, __length_am = 0;
|
352 |
|
|
for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; __s++)
|
353 |
|
|
{
|
354 |
|
|
__length_am += (__sd->_M_pieces[__iam][__s]._M_end
|
355 |
|
|
- __sd->_M_pieces[__iam][__s]._M_begin);
|
356 |
|
|
__offset += __sd->_M_pieces[__iam][__s]._M_begin;
|
357 |
|
|
}
|
358 |
|
|
|
359 |
|
|
typedef std::vector<
|
360 |
|
|
std::pair<_SortingPlacesIterator, _SortingPlacesIterator> >
|
361 |
|
|
_SeqVector;
|
362 |
|
|
_SeqVector __seqs(__sd->_M_num_threads);
|
363 |
|
|
|
364 |
|
|
for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; ++__s)
|
365 |
|
|
{
|
366 |
|
|
__seqs[__s] =
|
367 |
|
|
std::make_pair(__sd->_M_temporary[__s]
|
368 |
|
|
+ __sd->_M_pieces[__iam][__s]._M_begin,
|
369 |
|
|
__sd->_M_temporary[__s]
|
370 |
|
|
+ __sd->_M_pieces[__iam][__s]._M_end);
|
371 |
|
|
}
|
372 |
|
|
|
373 |
|
|
__possibly_stable_multiway_merge<
|
374 |
|
|
__stable, typename _SeqVector::iterator,
|
375 |
|
|
_RAIter, _Compare, _DifferenceType>()(__seqs.begin(), __seqs.end(),
|
376 |
|
|
__sd->_M_source + __offset, __comp,
|
377 |
|
|
__length_am);
|
378 |
|
|
|
379 |
|
|
# pragma omp barrier
|
380 |
|
|
|
381 |
|
|
::operator delete(__sd->_M_temporary[__iam]);
|
382 |
|
|
}
|
383 |
|
|
|
384 |
|
|
/** @brief PMWMS main call.
|
385 |
|
|
* @param __begin Begin iterator of sequence.
|
386 |
|
|
* @param __end End iterator of sequence.
|
387 |
|
|
* @param __comp Comparator.
|
388 |
|
|
* @param __n Length of sequence.
|
389 |
|
|
* @param __num_threads Number of threads to use.
|
390 |
|
|
*/
|
391 |
|
|
template<bool __stable, bool __exact, typename _RAIter,
|
392 |
|
|
typename _Compare>
|
393 |
|
|
void
|
394 |
|
|
parallel_sort_mwms(_RAIter __begin, _RAIter __end,
|
395 |
|
|
_Compare __comp,
|
396 |
|
|
_ThreadIndex __num_threads)
|
397 |
|
|
{
|
398 |
|
|
_GLIBCXX_CALL(__end - __begin)
|
399 |
|
|
|
400 |
|
|
typedef std::iterator_traits<_RAIter> _TraitsType;
|
401 |
|
|
typedef typename _TraitsType::value_type _ValueType;
|
402 |
|
|
typedef typename _TraitsType::difference_type _DifferenceType;
|
403 |
|
|
|
404 |
|
|
_DifferenceType __n = __end - __begin;
|
405 |
|
|
|
406 |
|
|
if (__n <= 1)
|
407 |
|
|
return;
|
408 |
|
|
|
409 |
|
|
// at least one element per thread
|
410 |
|
|
if (__num_threads > __n)
|
411 |
|
|
__num_threads = static_cast<_ThreadIndex>(__n);
|
412 |
|
|
|
413 |
|
|
// shared variables
|
414 |
|
|
_PMWMSSortingData<_RAIter> __sd;
|
415 |
|
|
_DifferenceType* __starts;
|
416 |
|
|
|
417 |
|
|
# pragma omp parallel num_threads(__num_threads)
|
418 |
|
|
{
|
419 |
|
|
__num_threads = omp_get_num_threads(); //no more threads than requested
|
420 |
|
|
|
421 |
|
|
# pragma omp single
|
422 |
|
|
{
|
423 |
|
|
__sd._M_num_threads = __num_threads;
|
424 |
|
|
__sd._M_source = __begin;
|
425 |
|
|
|
426 |
|
|
__sd._M_temporary = new _ValueType*[__num_threads];
|
427 |
|
|
|
428 |
|
|
if (!__exact)
|
429 |
|
|
{
|
430 |
|
|
_DifferenceType __size =
|
431 |
|
|
(_Settings::get().sort_mwms_oversampling * __num_threads - 1)
|
432 |
|
|
* __num_threads;
|
433 |
|
|
__sd._M_samples = static_cast<_ValueType*>
|
434 |
|
|
(::operator new(__size * sizeof(_ValueType)));
|
435 |
|
|
}
|
436 |
|
|
else
|
437 |
|
|
__sd._M_samples = NULL;
|
438 |
|
|
|
439 |
|
|
__sd._M_offsets = new _DifferenceType[__num_threads - 1];
|
440 |
|
|
__sd._M_pieces
|
441 |
|
|
= new std::vector<_Piece<_DifferenceType> >[__num_threads];
|
442 |
|
|
for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
|
443 |
|
|
__sd._M_pieces[__s].resize(__num_threads);
|
444 |
|
|
__starts = __sd._M_starts = new _DifferenceType[__num_threads + 1];
|
445 |
|
|
|
446 |
|
|
_DifferenceType __chunk_length = __n / __num_threads;
|
447 |
|
|
_DifferenceType __split = __n % __num_threads;
|
448 |
|
|
_DifferenceType __pos = 0;
|
449 |
|
|
for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
|
450 |
|
|
{
|
451 |
|
|
__starts[__i] = __pos;
|
452 |
|
|
__pos += ((__i < __split)
|
453 |
|
|
? (__chunk_length + 1) : __chunk_length);
|
454 |
|
|
}
|
455 |
|
|
__starts[__num_threads] = __pos;
|
456 |
|
|
} //single
|
457 |
|
|
|
458 |
|
|
// Now sort in parallel.
|
459 |
|
|
parallel_sort_mwms_pu<__stable, __exact>(&__sd, __comp);
|
460 |
|
|
} //parallel
|
461 |
|
|
|
462 |
|
|
delete[] __starts;
|
463 |
|
|
delete[] __sd._M_temporary;
|
464 |
|
|
|
465 |
|
|
if (!__exact)
|
466 |
|
|
::operator delete(__sd._M_samples);
|
467 |
|
|
|
468 |
|
|
delete[] __sd._M_offsets;
|
469 |
|
|
delete[] __sd._M_pieces;
|
470 |
|
|
}
|
471 |
|
|
|
472 |
|
|
} //namespace __gnu_parallel
|
473 |
|
|
|
474 |
|
|
#endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H */
|