// -*- 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 Compare two elements referenced by guarded iterators.
* @param __bi1 First iterator.
* @param __bi2 Second iterator.
- * @return @__c true if less. */
+ * @return @c true if less. */
friend bool
operator<(_GuardedIterator<_RAIter, _Compare>& __bi1,
_GuardedIterator<_RAIter, _Compare>& __bi2)
/** @brief Compare two elements referenced by guarded iterators.
* @param __bi1 First iterator.
* @param __bi2 Second iterator.
- * @return @__c True if less equal. */
+ * @return @c True if less equal. */
friend bool
operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1,
_GuardedIterator<_RAIter, _Compare>& __bi2)
/** @brief Current iterator __position. */
_RAIter _M_current;
/** @brief _Compare. */
- mutable _Compare& __comp;
+ _Compare& __comp;
public:
/** @brief Constructor. Sets iterator to beginning of sequence.
/** @brief Compare two elements referenced by unguarded iterators.
* @param __bi1 First iterator.
* @param __bi2 Second iterator.
- * @return @__c true if less. */
+ * @return @c true if less. */
friend bool
operator<(_UnguardedIterator<_RAIter, _Compare>& __bi1,
_UnguardedIterator<_RAIter, _Compare>& __bi2)
/** @brief Compare two elements referenced by unguarded iterators.
* @param __bi1 First iterator.
* @param __bi2 Second iterator.
- * @return @__c True if less equal. */
+ * @return @c True if less equal. */
friend bool
operator<=(_UnguardedIterator<_RAIter, _Compare>& __bi1,
_UnguardedIterator<_RAIter, _Compare>& __bi2)
*
* This works well for merging up to 4 sequences.
*
- * Note that making the merging stable does <em>not</em> come at a
+ * Note that making the merging stable does @a not come at a
* performance hit.
*
* Whether the merging is done guarded or unguarded is selected by the
*
* This works well for merging up to 4 sequences.
*
- * Note that making the merging stable does <em>not</em> come at a
+ * Note that making the merging stable does @a not come at a
* performance hit.
*
* Whether the merging is done guarded or unguarded is selected by the
_GLIBCXX_CALL(__length)
typedef _DifferenceTp _DifferenceType;
+ typedef typename std::iterator_traits<_RAIterIterator>
+ ::difference_type _SeqNumber;
typedef typename std::iterator_traits<_RAIterIterator>
::value_type::first_type
_RAIter1;
typedef typename std::iterator_traits<_RAIter1>::value_type
_ValueType;
- int __k = static_cast<int>(__seqs_end - __seqs_begin);
+ _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
_LT __lt(__k, __comp);
// Default value for potentially non-default-constructible types.
- _ValueType* __arbitrary_element = NULL;
+ _ValueType* __arbitrary_element = 0;
- for (int __t = 0; __t < __k; ++__t)
+ for (_SeqNumber __t = 0; __t < __k; ++__t)
{
- if(__arbitrary_element == NULL
+ if(!__arbitrary_element
&& _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
__arbitrary_element = &(*__seqs_begin[__t].first);
}
- for (int __t = 0; __t < __k; ++__t)
+ for (_SeqNumber __t = 0; __t < __k; ++__t)
{
if (__seqs_begin[__t].first == __seqs_begin[__t].second)
__lt.__insert_start(*__arbitrary_element, __t, true);
__lt.__init();
- int __source;
+ _SeqNumber __source;
for (_DifferenceType __i = 0; __i < __length; ++__i)
{
_GLIBCXX_CALL(__length)
typedef _DifferenceTp _DifferenceType;
+ typedef typename std::iterator_traits<_RAIterIterator>
+ ::difference_type _SeqNumber;
typedef typename std::iterator_traits<_RAIterIterator>
::value_type::first_type
_RAIter1;
typedef typename std::iterator_traits<_RAIter1>::value_type
_ValueType;
- int __k = __seqs_end - __seqs_begin;
+ _SeqNumber __k = __seqs_end - __seqs_begin;
_LT __lt(__k, __sentinel, __comp);
- for (int __t = 0; __t < __k; ++__t)
+ for (_SeqNumber __t = 0; __t < __k; ++__t)
{
#if _GLIBCXX_ASSERTIONS
_GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first
__lt.__init();
- int __source;
+ _SeqNumber __source;
#if _GLIBCXX_ASSERTIONS
_DifferenceType __i = 0;
typename _DifferenceTp,
typename _Compare>
struct __multiway_merge_k_variant_sentinel_switch<false, __stable,
- _RAIterIterator, _RAIter3,
- _DifferenceTp, _Compare>
+ _RAIterIterator,
+ _RAIter3, _DifferenceTp,
+ _Compare>
{
_RAIter3
operator()(_RAIterIterator __seqs_begin,
_GLIBCXX_CALL(__length)
typedef _DifferenceTp _DifferenceType;
+ typedef typename std::iterator_traits<_RAIterIterator>
+ ::difference_type _SeqNumber;
typedef typename std::iterator_traits<_RAIterIterator>
::value_type::first_type
_RAIter1;
return __target;
_RAIter3 __return_target = __target;
- int __k = static_cast<int>(__seqs_end - __seqs_begin);
+ _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
switch (__k)
{
_Compare __comp,
std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
{
+ typedef typename std::iterator_traits<_RAIterIterator>
+ ::difference_type _SeqNumber;
typedef typename std::iterator_traits<_RAIterIterator>
::value_type::first_type
_RAIter1;
_ValueType;
// __k sequences.
- int __k = static_cast<int>(__seqs_end - __seqs_begin);
+ const _SeqNumber __k
+ = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
- int __num_threads = omp_get_num_threads();
+ const _ThreadIndex __num_threads = omp_get_num_threads();
- _DifferenceType __num_samples =
+ const _DifferenceType __num_samples =
__gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
_ValueType* __samples = static_cast<_ValueType*>
(::operator new(sizeof(_ValueType) * __k * __num_samples));
// Sample.
- for (int __s = 0; __s < __k; ++__s)
+ for (_SeqNumber __s = 0; __s < __k; ++__s)
for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
{
_DifferenceType sample_index = static_cast<_DifferenceType>
_SamplingSorter<__stable, _ValueType*, _Compare>()
(__samples, __samples + (__num_samples * __k), __comp);
- for (int __slab = 0; __slab < __num_threads; ++__slab)
+ for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
// For each slab / processor.
- for (int __seq = 0; __seq < __k; ++__seq)
+ for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
{
// For each sequence.
if (__slab > 0)
__pieces[__slab][__seq].second =
_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
}
+
+ for (_SeqNumber __s = 0; __s < __k; ++__s)
+ for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
+ __samples[__s * __num_samples + __i].~_ValueType();
::operator delete(__samples);
}
_Compare __comp,
std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
{
+ typedef typename std::iterator_traits<_RAIterIterator>
+ ::difference_type _SeqNumber;
typedef typename std::iterator_traits<_RAIterIterator>
::value_type::first_type
_RAIter1;
const bool __tight = (__total_length == __length);
// __k sequences.
- const int __k = static_cast<int>(__seqs_end - __seqs_begin);
+ const _SeqNumber __k = __seqs_end - __seqs_begin;
- const int __num_threads = omp_get_num_threads();
+ const _ThreadIndex __num_threads = omp_get_num_threads();
// (Settings::multiway_merge_splitting
// == __gnu_parallel::_Settings::EXACT).
_DifferenceType* __borders =
new _DifferenceType[__num_threads + 1];
- equally_split(__length, __num_threads, __borders);
+ __equally_split(__length, __num_threads, __borders);
- for (int __s = 0; __s < (__num_threads - 1); ++__s)
+ for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s)
{
__offsets[__s].resize(__k);
multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1],
}
delete[] __borders;
- for (int __slab = 0; __slab < __num_threads; ++__slab)
+ for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
{
// For each slab / processor.
- for (int __seq = 0; __seq < __k; ++__seq)
+ for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
{
// For each sequence.
if (__slab == 0)
_GLIBCXX_CALL(__length)
typedef _DifferenceTp _DifferenceType;
+ typedef typename std::iterator_traits<_RAIterIterator>
+ ::difference_type _SeqNumber;
typedef typename std::iterator_traits<_RAIterIterator>
::value_type::first_type
_RAIter1;
// Leave only non-empty sequences.
typedef std::pair<_RAIter1, _RAIter1> seq_type;
seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
- int __k = 0;
+ _SeqNumber __k = 0;
_DifferenceType __total_length = 0;
for (_RAIterIterator __raii = __seqs_begin;
__raii != __seqs_end; ++__raii)
__length = std::min<_DifferenceTp>(__length, __total_length);
if (__total_length == 0 || __k == 0)
- {
- delete[] __ne_seqs;
- return __target;
- }
+ {
+ delete[] __ne_seqs;
+ return __target;
+ }
std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
// Thread __t will have to merge pieces[__iam][0..__k - 1]
__pieces = new std::vector<
std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
- for (int __s = 0; __s < __num_threads; ++__s)
+ for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
__pieces[__s].resize(__k);
_DifferenceType __num_samples =
_DifferenceType __target_position = 0;
- for (int __c = 0; __c < __k; ++__c)
+ for (_SeqNumber __c = 0; __c < __k; ++__c)
__target_position += __pieces[__iam][__c].first;
seq_type* __chunks = new seq_type[__k];
- for (int __s = 0; __s < __k; ++__s)
+ for (_SeqNumber __s = 0; __s < __k; ++__s)
__chunks[__s] = std::make_pair(__ne_seqs[__s].first
+ __pieces[__iam][__s].first,
__ne_seqs[__s].first
* @pre All input sequences must be sorted.
* @pre Target must provide enough space to merge out length elements or
* the number of elements in all sequences, whichever is smaller.
- * @pre For each @__c __i, @__c __seqs_begin[__i].second must be the end
+ * @pre For each @c __i, @c __seqs_begin[__i].second must be the end
* marker of the sequence, but also reference the one more __sentinel
* element.
*
projects / gcc.git / blobdiff