// -*- C++ -*-
-// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
/** @brief Offsets to add to the found positions. */
_DifferenceType* _M_offsets;
- /** @brief Pieces of data to merge @__c [thread][__sequence] */
+ /** @brief Pieces of data to merge @c [thread][__sequence] */
std::vector<_Piece<_DifferenceType> >* _M_pieces;
};
/**
* @brief Select _M_samples from a sequence.
* @param __sd Pointer to algorithm data. _Result will be placed in
- * @__c __sd->_M_samples.
+ * @c __sd->_M_samples.
* @param __num_samples Number of _M_samples to select.
*/
template<typename _RAIter, typename _DifferenceTp>
_DifferenceType* __es = new _DifferenceType[__num_samples + 2];
- equally_split(__sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam],
- __num_samples + 1, __es);
+ __equally_split(__sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam],
+ __num_samples + 1, __es);
for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
::new(&(__sd->_M_samples[__iam * __num_samples + __i]))
/** @brief Split by exact splitting. */
template<typename _RAIter, typename _Compare,
typename _SortingPlacesIterator>
- struct _SplitConsistently<true, _RAIter,
- _Compare, _SortingPlacesIterator>
+ struct _SplitConsistently<true, _RAIter, _Compare, _SortingPlacesIterator>
{
void
operator()(const _ThreadIndex __iam,
std::vector<std::pair<_SortingPlacesIterator,
_SortingPlacesIterator> >
- seqs(__sd->_M_num_threads);
+ __seqs(__sd->_M_num_threads);
for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; __s++)
- seqs[__s] = std::make_pair(__sd->_M_temporary[__s],
- __sd->_M_temporary[__s]
- + (__sd->_M_starts[__s + 1]
- - __sd->_M_starts[__s]));
+ __seqs[__s] = std::make_pair(__sd->_M_temporary[__s],
+ __sd->_M_temporary[__s]
+ + (__sd->_M_starts[__s + 1]
+ - __sd->_M_starts[__s]));
- std::vector<_SortingPlacesIterator> _M_offsets(__sd->_M_num_threads);
+ std::vector<_SortingPlacesIterator> __offsets(__sd->_M_num_threads);
// if not last thread
if (__iam < __sd->_M_num_threads - 1)
- multiseq_partition(seqs.begin(), seqs.end(),
- __sd->_M_starts[__iam + 1], _M_offsets.begin(),
+ multiseq_partition(__seqs.begin(), __seqs.end(),
+ __sd->_M_starts[__iam + 1], __offsets.begin(),
__comp);
- for (int __seq = 0; __seq < __sd->_M_num_threads; __seq++)
+ for (_ThreadIndex __seq = 0; __seq < __sd->_M_num_threads; __seq++)
{
// for each sequence
if (__iam < (__sd->_M_num_threads - 1))
__sd->_M_pieces[__iam][__seq]._M_end
- = _M_offsets[__seq] - seqs[__seq].first;
+ = __offsets[__seq] - __seqs[__seq].first;
else
// very end of this sequence
__sd->_M_pieces[__iam][__seq]._M_end =
/** @brief Split by sampling. */
template<typename _RAIter, typename _Compare,
typename _SortingPlacesIterator>
- struct _SplitConsistently<false, _RAIter, _Compare,
- _SortingPlacesIterator>
+ struct _SplitConsistently<false, _RAIter, _Compare, _SortingPlacesIterator>
{
void
operator()(const _ThreadIndex __iam,
const _RAIter& __target,
_Compare& __comp,
_DiffType __length_am) const
- {
- stable_multiway_merge(__seqs_begin, __seqs_end, __target, __length_am,
- __comp, sequential_tag());
- }
+ { stable_multiway_merge(__seqs_begin, __seqs_end, __target,
+ __length_am, __comp, sequential_tag()); }
};
template<typename Seq_RAIter, typename _RAIter,
const _RAIter& __target,
_Compare& __comp,
_DiffType __length_am) const
- {
- multiway_merge(__seqs_begin, __seqs_end, __target, __length_am, __comp,
- sequential_tag());
- }
+ { multiway_merge(__seqs_begin, __seqs_end, __target, __length_am,
+ __comp, sequential_tag()); }
};
/** @brief PMWMS code executed by each thread.
_ThreadIndex __iam = omp_get_thread_num();
// Length of this thread's chunk, before merging.
- _DifferenceType __length_local
- = __sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam];
+ _DifferenceType __length_local =
+ __sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam];
// Sort in temporary storage, leave space for sentinel.
_DifferenceType __num_samples =
_Settings::get().sort_mwms_oversampling * __sd->_M_num_threads - 1;
- _SplitConsistently
- <__exact, _RAIter, _Compare, _SortingPlacesIterator>()
+ _SplitConsistently<__exact, _RAIter, _Compare, _SortingPlacesIterator>()
(__iam, __sd, __comp, __num_samples);
// Offset from __target __begin, __length after merging.
}
typedef std::vector<
- std::pair<_SortingPlacesIterator, _SortingPlacesIterator> >
+ std::pair<_SortingPlacesIterator, _SortingPlacesIterator> >
_SeqVector;
- _SeqVector seqs(__sd->_M_num_threads);
+ _SeqVector __seqs(__sd->_M_num_threads);
- for (int __s = 0; __s < __sd->_M_num_threads; ++__s)
+ for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; ++__s)
{
- seqs[__s] =
- std::make_pair
- (__sd->_M_temporary[__s] + __sd->_M_pieces[__iam][__s]._M_begin,
- __sd->_M_temporary[__s] + __sd->_M_pieces[__iam][__s]._M_end);
+ __seqs[__s] =
+ std::make_pair(__sd->_M_temporary[__s]
+ + __sd->_M_pieces[__iam][__s]._M_begin,
+ __sd->_M_temporary[__s]
+ + __sd->_M_pieces[__iam][__s]._M_end);
}
__possibly_stable_multiway_merge<
- __stable,
- typename _SeqVector::iterator,
- _RAIter,
- _Compare, _DifferenceType>()
- (seqs.begin(), seqs.end(),
- __sd->_M_source + __offset, __comp,
- __length_am);
+ __stable, typename _SeqVector::iterator,
+ _RAIter, _Compare, _DifferenceType>()(__seqs.begin(), __seqs.end(),
+ __sd->_M_source + __offset, __comp,
+ __length_am);
# pragma omp barrier
+ for (_DifferenceType __i = 0; __i < __length_local; ++__i)
+ __sd->_M_temporary[__iam][__i].~_ValueType();
::operator delete(__sd->_M_temporary[__iam]);
}
// shared variables
_PMWMSSortingData<_RAIter> __sd;
- _DifferenceType* _M_starts;
+ _DifferenceType* __starts;
+ _DifferenceType __size;
# pragma omp parallel num_threads(__num_threads)
{
if (!__exact)
{
- _DifferenceType __size =
+ __size =
(_Settings::get().sort_mwms_oversampling * __num_threads - 1)
* __num_threads;
__sd._M_samples = static_cast<_ValueType*>
(::operator new(__size * sizeof(_ValueType)));
}
else
- __sd._M_samples = NULL;
+ __sd._M_samples = 0;
__sd._M_offsets = new _DifferenceType[__num_threads - 1];
__sd._M_pieces
= new std::vector<_Piece<_DifferenceType> >[__num_threads];
- for (int __s = 0; __s < __num_threads; ++__s)
+ for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
__sd._M_pieces[__s].resize(__num_threads);
- _M_starts = __sd._M_starts
- = new _DifferenceType[__num_threads + 1];
+ __starts = __sd._M_starts = new _DifferenceType[__num_threads + 1];
_DifferenceType __chunk_length = __n / __num_threads;
_DifferenceType __split = __n % __num_threads;
_DifferenceType __pos = 0;
- for (int __i = 0; __i < __num_threads; ++__i)
+ for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
{
- _M_starts[__i] = __pos;
- __pos += (__i < __split)
- ? (__chunk_length + 1) : __chunk_length;
+ __starts[__i] = __pos;
+ __pos += ((__i < __split)
+ ? (__chunk_length + 1) : __chunk_length);
}
- _M_starts[__num_threads] = __pos;
+ __starts[__num_threads] = __pos;
} //single
// Now sort in parallel.
parallel_sort_mwms_pu<__stable, __exact>(&__sd, __comp);
} //parallel
- delete[] _M_starts;
+ delete[] __starts;
delete[] __sd._M_temporary;
if (!__exact)
- ::operator delete(__sd._M_samples);
+ {
+ for (_DifferenceType __i = 0; __i < __size; ++__i)
+ __sd._M_samples[__i].~_ValueType();
+ ::operator delete(__sd._M_samples);
+ }
delete[] __sd._M_offsets;
delete[] __sd._M_pieces;