libstdc++

__gnu_parallel Namespace Reference

GNU parallel code for public use. More...

Classes

Typedefs

Enumerations

Functions

Variables


Detailed Description

GNU parallel code for public use.


Typedef Documentation

typedef unsigned short __gnu_parallel::bin_index

Type to hold the index of a bin.

Since many variables of this type are allocated, it should be chosen as small as possible.

Definition at line 47 of file random_shuffle.h.

typedef short __gnu_parallel::int16

Integer Types.

16-bit signed integer.

Definition at line 114 of file types.h.

typedef int __gnu_parallel::int32

32-bit signed integer.

Definition at line 120 of file types.h.

typedef long long __gnu_parallel::int64

64-bit signed integer.

Definition at line 126 of file types.h.

Longest compare-and-swappable integer type on this platform.

Definition at line 145 of file types.h.

Unsigned integer to index elements. The total number of elements for each algorithm must fit into this type.

Definition at line 135 of file types.h.

Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit into this type.

Definition at line 141 of file types.h.

typedef unsigned short __gnu_parallel::uint16

16-bit unsigned integer.

Definition at line 117 of file types.h.

typedef unsigned int __gnu_parallel::uint32

32-bit unsigned integer.

Definition at line 123 of file types.h.

typedef unsigned long long __gnu_parallel::uint64

64-bit unsigned integer.

Definition at line 129 of file types.h.


Enumeration Type Documentation

Strategies for run-time algorithm selection:

Definition at line 65 of file types.h.

Find algorithms:

Definition at line 104 of file types.h.

Merging algorithms:

Definition at line 83 of file types.h.

Run-time equivalents for the compile-time tags.

Enumerator:
sequential 

Not parallel.

parallel_unbalanced 

Parallel unbalanced (equal-sized chunks).

parallel_balanced 

Parallel balanced (work-stealing).

parallel_omp_loop 

Parallel with OpenMP dynamic load-balancing.

parallel_omp_loop_static 

Parallel with OpenMP static load-balancing.

parallel_taskqueue 

Parallel with OpenMP taskqueue construct.

Definition at line 42 of file types.h.

Partial sum algorithms: recursive, linear.

Definition at line 89 of file types.h.

Sorting algorithms:

Definition at line 74 of file types.h.

Sorting/merging algorithms: sampling, exact.

Definition at line 96 of file types.h.


Function Documentation

template<typename Size >
Size __gnu_parallel::__log2 ( Size  n) [inline]

Calculates the rounded-down logarithm of n for base 2.

Parameters:
nArgument.
Returns:
Returns 0 for any argument <1.

Definition at line 105 of file base.h.

Referenced by __gnu_parallel::LoserTreeBase< T, Comparator >::LoserTreeBase(), multiseq_partition(), multiseq_selection(), parallel_random_shuffle_drs(), round_up_to_pow2(), and sequential_random_shuffle().

template<typename RandomAccessIterator , typename _DifferenceTp >
void __gnu_parallel::calc_borders ( RandomAccessIterator  elements,
_DifferenceTp  length,
_DifferenceTp *  off 
)

Precalculate advances for Knuth-Morris-Pratt algorithm.

Parameters:
elementsBegin iterator of sequence to search for.
lengthLength of sequence to search for.
advancesReturned offsets.

Definition at line 52 of file search.h.

Referenced by search_template().

template<typename T >
bool __gnu_parallel::compare_and_swap ( volatile T *  ptr,
comparand,
replacement 
) [inline]

Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise.

Implementation is heavily platform-dependent.

Parameters:
ptrPointer to signed integer.
comparandCompare value.
replacementReplacement value.

Definition at line 327 of file parallel/compatibility.h.

References compare_and_swap_32(), and compare_and_swap_64().

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_back(), and __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_front().

bool __gnu_parallel::compare_and_swap_32 ( volatile int32 *  ptr,
int32  comparand,
int32  replacement 
) [inline]

Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise.

Implementation is heavily platform-dependent.

Parameters:
ptrPointer to 32-bit signed integer.
comparandCompare value.
replacementReplacement value.

Definition at line 235 of file parallel/compatibility.h.

Referenced by compare_and_swap().

bool __gnu_parallel::compare_and_swap_64 ( volatile int64 *  ptr,
int64  comparand,
int64  replacement 
) [inline]

Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise.

Implementation is heavily platform-dependent.

Parameters:
ptrPointer to 64-bit signed integer.
comparandCompare value.
replacementReplacement value.

Definition at line 275 of file parallel/compatibility.h.

Referenced by compare_and_swap().

void __gnu_parallel::decode2 ( lcas_t  x,
int &  a,
int &  b 
) [inline]

Decode two integers from one __gnu_parallel::lcas_t.

Parameters:
x__gnu_parallel::lcas_t to decode integers from.
aFirst integer, to be decoded from the most-significant lcas_t_bits/2 bits of x.
bSecond integer, to be encoded in the least-significant lcas_t_bits/2 bits of x.
See also:
encode2

Definition at line 136 of file base.h.

References lcas_t_bits, and lcas_t_mask.

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_back(), __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_front(), and __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::push_front().

template<typename RandomAccessIterator , typename _DifferenceTp >
void __gnu_parallel::determine_samples ( PMWMSSortingData< RandomAccessIterator > *  sd,
_DifferenceTp  num_samples 
)

Select samples from a sequence.

Parameters:
sdPointer to algorithm data. Result will be placed in sd->samples.
num_samplesNumber of samples to select.

Definition at line 98 of file multiway_mergesort.h.

References equally_split(), __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::samples, __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::source, and __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::starts.

lcas_t __gnu_parallel::encode2 ( int  a,
int  b 
) [inline]

Encode two integers into one __gnu_parallel::lcas_t.

Parameters:
aFirst integer, to be encoded in the most-significant lcas_t_bits/2 bits.
bSecond integer, to be encoded in the least-significant lcas_t_bits/2 bits.
Returns:
__gnu_parallel::lcas_t value encoding a and b.
See also:
decode2

Definition at line 122 of file base.h.

References lcas_t_bits.

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_back(), __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_front(), __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::push_front(), and __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::RestrictedBoundedConcurrentQueue().

template<typename difference_type , typename OutputIterator >
OutputIterator __gnu_parallel::equally_split ( difference_type  n,
thread_index_t  num_threads,
OutputIterator  s 
)

Function to split a sequence into parts of almost equal size.

The resulting sequence s of length num_threads+1 contains the splitting positions when splitting the range [0,n) into parts of almost equal size (plus minus 1). The first entry is 0, the last one n. There may result empty parts.

Parameters:
nNumber of elements
num_threadsNumber of parts
sSplitters
Returns:
End of splitter sequence, i. e. s+num_threads+1

Definition at line 48 of file equally_split.h.

Referenced by determine_samples(), multiway_merge_exact_splitting(), parallel_partial_sum_linear(), parallel_unique_copy(), and search_template().

template<typename difference_type >
difference_type __gnu_parallel::equally_split_point ( difference_type  n,
thread_index_t  num_threads,
thread_index_t  thread_no 
)

Function to split a sequence into parts of almost equal size.

Returns the position of the splitting point between thread number thread_no (included) and thread number thread_no+1 (excluded).

Parameters:
nNumber of elements
num_threadsNumber of parts
Returns:
_SplittingAlgorithm point

Definition at line 73 of file equally_split.h.

Referenced by for_each_template_random_access_ed().

template<typename T >
T __gnu_parallel::fetch_and_add ( volatile T *  ptr,
addend 
) [inline]

Add a value to a variable, atomically.

Implementation is heavily platform-dependent.

Parameters:
ptrPointer to a signed integer.
addendValue to add.

Definition at line 185 of file parallel/compatibility.h.

References fetch_and_add_32(), and fetch_and_add_64().

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::push_front().

int32 __gnu_parallel::fetch_and_add_32 ( volatile int32 *  ptr,
int32  addend 
) [inline]

Add a value to a variable, atomically.

Implementation is heavily platform-dependent.

Parameters:
ptrPointer to a 32-bit signed integer.
addendValue to add.

Definition at line 95 of file parallel/compatibility.h.

Referenced by fetch_and_add().

int64 __gnu_parallel::fetch_and_add_64 ( volatile int64 *  ptr,
int64  addend 
) [inline]

Add a value to a variable, atomically.

Implementation is heavily platform-dependent.

Parameters:
ptrPointer to a 64-bit signed integer.
addendValue to add.

Definition at line 134 of file parallel/compatibility.h.

Referenced by fetch_and_add().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename Pred , typename Selector >
std::pair<RandomAccessIterator1, RandomAccessIterator2> __gnu_parallel::find_template ( RandomAccessIterator1  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2  begin2,
Pred  pred,
Selector  selector 
) [inline]

Parallel std::find, switch for different algorithms.

Parameters:
begin1Begin iterator of first sequence.
end1End iterator of first sequence.
begin2Begin iterator of second sequence. Must have same length as first sequence.
predFind predicate.
selectorFunctionality (e. g. std::find_if (), std::equal(),...)
Returns:
Place of finding in both sequences.

Definition at line 60 of file find.h.

References __gnu_parallel::_Settings::get().

template<typename InputIterator , typename UserOp , typename Functionality , typename Red , typename Result >
UserOp __gnu_parallel::for_each_template_random_access ( InputIterator  begin,
InputIterator  end,
UserOp  user_op,
Functionality &  functionality,
Red  reduction,
Result  reduction_start,
Result &  output,
typename std::iterator_traits< InputIterator >::difference_type  bound,
_Parallelism  parallelism_tag 
)

Chose the desired algorithm by evaluating parallelism_tag.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
user_opA user-specified functor (comparator, predicate, associative operator,...)
functionalityfunctor to "process" an element with user_op (depends on desired functionality, e. g. accumulate, for_each,...
reductionReduction functor.
reduction_startInitial value for reduction.
outputOutput iterator.
boundMaximum number of elements processed.
parallelism_tagParallelization method

Definition at line 61 of file for_each.h.

References for_each_template_random_access_ed(), for_each_template_random_access_omp_loop(), for_each_template_random_access_workstealing(), parallel_omp_loop, parallel_omp_loop_static, and parallel_unbalanced.

template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result >
Op __gnu_parallel::for_each_template_random_access_ed ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Op  o,
Fu &  f,
Red  r,
Result  base,
Result &  output,
typename std::iterator_traits< RandomAccessIterator >::difference_type  bound 
)

Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work.

Parameters:
beginBegin iterator of element sequence.
endEnd iterator of element sequence.
oUser-supplied functor (comparator, predicate, adding functor, ...)
fFunctor to "process" an element with op (depends on desired functionality, e. g. for std::for_each(), ...).
rFunctor to "add" a single result to the already processed elements (depends on functionality).
baseBase value for reduction.
outputPointer to position where final result is written to
boundMaximum number of elements processed (e. g. for std::count_n()).
Returns:
User-supplied functor (that may contain a part of the result).

Definition at line 68 of file par_loop.h.

References equally_split_point().

Referenced by for_each_template_random_access().

template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result >
Op __gnu_parallel::for_each_template_random_access_omp_loop ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Op  o,
Fu &  f,
Red  r,
Result  base,
Result &  output,
typename std::iterator_traits< RandomAccessIterator >::difference_type  bound 
)

Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop.

Parameters:
beginBegin iterator of element sequence.
endEnd iterator of element sequence.
oUser-supplied functor (comparator, predicate, adding functor, etc.).
fFunctor to "process" an element with op (depends on desired functionality, e. g. for std::for_each(), ...).
rFunctor to "add" a single result to the already processed elements (depends on functionality).
baseBase value for reduction.
outputPointer to position where final result is written to
boundMaximum number of elements processed (e. g. for std::count_n()).
Returns:
User-supplied functor (that may contain a part of the result).

Definition at line 67 of file omp_loop.h.

Referenced by for_each_template_random_access().

template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result >
Op __gnu_parallel::for_each_template_random_access_omp_loop_static ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Op  o,
Fu &  f,
Red  r,
Result  base,
Result &  output,
typename std::iterator_traits< RandomAccessIterator >::difference_type  bound 
)

Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling.

Parameters:
beginBegin iterator of element sequence.
endEnd iterator of element sequence.
oUser-supplied functor (comparator, predicate, adding functor, ...).
fFunctor to "process" an element with op (depends on desired functionality, e. g. for std::for_each(), ...).
rFunctor to "add" a single result to the already processed elements (depends on functionality).
baseBase value for reduction.
outputPointer to position where final result is written to
boundMaximum number of elements processed (e. g. for std::count_n()).
Returns:
User-supplied functor (that may contain a part of the result).

Definition at line 67 of file omp_loop_static.h.

template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result >
Op __gnu_parallel::for_each_template_random_access_workstealing ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Op  op,
Fu &  f,
Red  r,
Result  base,
Result &  output,
typename std::iterator_traits< RandomAccessIterator >::difference_type  bound 
)

Work stealing algorithm for random access iterators.

Uses O(1) additional memory. Synchronization at job lists is done with atomic operations.

Parameters:
beginBegin iterator of element sequence.
endEnd iterator of element sequence.
opUser-supplied functor (comparator, predicate, adding functor, ...).
fFunctor to "process" an element with op (depends on desired functionality, e. g. for std::for_each(), ...).
rFunctor to "add" a single result to the already processed elements (depends on functionality).
baseBase value for reduction.
outputPointer to position where final result is written to
boundMaximum number of elements processed (e. g. for std::count_n()).
Returns:
User-supplied functor (that may contain a part of the result).

Definition at line 99 of file workstealing.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::cache_line_size, __gnu_parallel::Job< _DifferenceTp >::first, __gnu_parallel::_Settings::get(), __gnu_parallel::Job< _DifferenceTp >::last, __gnu_parallel::Job< _DifferenceTp >::load, min(), and yield().

Referenced by for_each_template_random_access().

template<typename InputIterator , typename Comparator >
bool __gnu_parallel::is_sorted ( InputIterator  begin,
InputIterator  end,
Comparator  comp = std::less<typename std::iterator_traits<InputIterator>:: value_type>() 
)

Check whether [begin, end) is sorted according to comp.

Parameters:
beginBegin iterator of sequence.
endEnd iterator of sequence.
compComparator.
Returns:
true if sorted, false otherwise.

Definition at line 51 of file checkers.h.

Referenced by multiway_merge_loser_tree_sentinel(), parallel_multiway_merge(), and sequential_multiway_merge().

template<typename InputIterator , typename Comparator >
bool __gnu_parallel::is_sorted_failure ( InputIterator  begin,
InputIterator  end,
InputIterator &  first_failure,
Comparator  comp = std::less<typename std::iterator_traits<InputIterator>:: value_type>() 
)

Check whether [begin, end) is sorted according to comp. Prints the position in case an unordered pair is found.

Parameters:
beginBegin iterator of sequence.
endEnd iterator of sequence.
first_failureThe first failure is returned in this variable.
compComparator.
Returns:
true if sorted, false otherwise.

Definition at line 89 of file checkers.h.

template<typename InputIterator , typename Comparator >
bool __gnu_parallel::is_sorted_print_failures ( InputIterator  begin,
InputIterator  end,
Comparator  comp = std::less<typename std::iterator_traits <InputIterator>::value_type>() 
)

Check whether [begin, end) is sorted according to comp. Prints all unordered pair, including the surrounding two elements.

Parameters:
beginBegin iterator of sequence.
endEnd iterator of sequence.
compComparator.
Returns:
true if sorted, false otherwise.

Definition at line 129 of file checkers.h.

template<typename InputIterator , typename FunctorType >
size_t __gnu_parallel::list_partition ( const InputIterator  begin,
const InputIterator  end,
InputIterator *  starts,
size_t *  lengths,
const int  num_parts,
FunctorType &  f,
int  oversampling = 0 
)

Splits a sequence given by input iterators into parts of almost equal size.

The function needs only one pass over the sequence.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
startsStart iterators for the resulting parts, dimension num_parts+1. For convenience, starts [num_parts] contains the end iterator of the sequence.
lengthsLength of the resulting parts.
num_partsNumber of parts to split the sequence into.
fFunctor to be applied to each element by traversing it
oversamplingOversampling factor. If 0, then the partitions will differ in at most $ \sqrt{\mathrm{end} - \mathrm{begin}} $ elements. Otherwise, the ratio between the longest and the shortest part is bounded by $ 1/(\mathrm{oversampling} \cdot \mathrm{num\_parts}) $.
Returns:
Length of the whole sequence.

Definition at line 100 of file list_partition.h.

References shrink_and_double(), and std::vector< _Tp, _Alloc >::size().

template<typename T >
const T& __gnu_parallel::max ( const T &  a,
const T &  b 
)

Equivalent to std::max.

Definition at line 151 of file base.h.

Referenced by multiseq_partition(), multiseq_selection(), and parallel_nth_element().

template<typename RandomAccessIterator , typename Comparator >
RandomAccessIterator __gnu_parallel::median_of_three_iterators ( RandomAccessIterator  a,
RandomAccessIterator  b,
RandomAccessIterator  c,
Comparator &  comp 
)

Compute the median of three referenced elements, according to comp.

Parameters:
aFirst iterator.
bSecond iterator.
cThird iterator.
compComparator.

Definition at line 443 of file base.h.

Referenced by qsb_divide().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator >
OutputIterator __gnu_parallel::merge_advance ( RandomAccessIterator1 &  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2 &  begin2,
RandomAccessIterator2  end2,
OutputIterator  target,
_DifferenceTp  max_length,
Comparator  comp 
) [inline]

Merge routine being able to merge only the max_length smallest elements.

The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. Static switch on whether to use the conditional-move variant.

Parameters:
begin1Begin iterator of first sequence.
end1End iterator of first sequence.
begin2Begin iterator of second sequence.
end2End iterator of second sequence.
targetTarget begin iterator.
max_lengthMaximum number of elements to merge.
compComparator.
Returns:
Output end iterator.

Definition at line 174 of file merge.h.

References _GLIBCXX_CALL, and merge_advance_movc().

Referenced by parallel_merge_advance(), and sequential_multiway_merge().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator >
OutputIterator __gnu_parallel::merge_advance_movc ( RandomAccessIterator1 &  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2 &  begin2,
RandomAccessIterator2  end2,
OutputIterator  target,
_DifferenceTp  max_length,
Comparator  comp 
)

Merge routine being able to merge only the max_length smallest elements.

The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. Specially designed code should allow the compiler to generate conditional moves instead of branches.

Parameters:
begin1Begin iterator of first sequence.
end1End iterator of first sequence.
begin2Begin iterator of second sequence.
end2End iterator of second sequence.
targetTarget begin iterator.
max_lengthMaximum number of elements to merge.
compComparator.
Returns:
Output end iterator.

Definition at line 106 of file merge.h.

Referenced by merge_advance().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator >
OutputIterator __gnu_parallel::merge_advance_usual ( RandomAccessIterator1 &  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2 &  begin2,
RandomAccessIterator2  end2,
OutputIterator  target,
_DifferenceTp  max_length,
Comparator  comp 
)

Merge routine being able to merge only the max_length smallest elements.

The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant.

Parameters:
begin1Begin iterator of first sequence.
end1End iterator of first sequence.
begin2Begin iterator of second sequence.
end2End iterator of second sequence.
targetTarget begin iterator.
max_lengthMaximum number of elements to merge.
compComparator.
Returns:
Output end iterator.

Definition at line 57 of file merge.h.

template<typename T >
const T& __gnu_parallel::min ( const T &  a,
const T &  b 
)
template<typename RanSeqs , typename RankType , typename RankIterator , typename Comparator >
void __gnu_parallel::multiseq_partition ( RanSeqs  begin_seqs,
RanSeqs  end_seqs,
RankType  rank,
RankIterator  begin_offsets,
Comparator  comp = std::less< typename std::iterator_traits<typename std::iterator_traits<RanSeqs>::value_type:: first_type>::value_type>() 
)

Splits several sorted sequences at a certain global rank, resulting in a splitting point for each sequence. The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones on the left side will be chosen from sequences with smaller number.

Parameters:
begin_seqsBegin of the sequence of iterator pairs.
end_seqsEnd of the sequence of iterator pairs.
rankThe global rank to partition at.
begin_offsetsA random-access sequence begin where the result will be stored in. Each element of the sequence is an iterator that points to the first element on the greater part of the respective sequence.
compThe ordering functor, defaults to std::less<T>.

Definition at line 123 of file multiseq_selection.h.

References __log2(), _GLIBCXX_CALL, std::vector< _Tp, _Alloc >::begin(), std::distance(), __gnu_cxx::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::vector< _Tp, _Alloc >::end(), max(), min(), std::priority_queue< _Tp, _Sequence, _Compare >::pop(), std::priority_queue< _Tp, _Sequence, _Compare >::push(), std::vector< _Tp, _Alloc >::push_back(), and std::priority_queue< _Tp, _Sequence, _Compare >::top().

Referenced by multiway_merge_exact_splitting().

template<typename T , typename RanSeqs , typename RankType , typename Comparator >
T __gnu_parallel::multiseq_selection ( RanSeqs  begin_seqs,
RanSeqs  end_seqs,
RankType  rank,
RankType &  offset,
Comparator  comp = std::less<T>() 
)

Selects the element at a certain global rank from several sorted sequences.

The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty.

Parameters:
begin_seqsBegin of the sequence of iterator pairs.
end_seqsEnd of the sequence of iterator pairs.
rankThe global rank to partition at.
offsetThe rank of the selected element in the global subsequence of elements equal to the selected element. If the selected element is unique, this number is 0.
compThe ordering functor, defaults to std::less.

Definition at line 377 of file multiseq_selection.h.

References __log2(), _GLIBCXX_CALL, std::vector< _Tp, _Alloc >::begin(), std::distance(), __gnu_cxx::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::vector< _Tp, _Alloc >::end(), max(), min(), std::priority_queue< _Tp, _Sequence, _Compare >::pop(), std::priority_queue< _Tp, _Sequence, _Compare >::push(), std::vector< _Tp, _Alloc >::push_back(), and std::priority_queue< _Tp, _Sequence, _Compare >::top().

template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator >
RandomAccessIteratorOut __gnu_parallel::multiway_merge ( RandomAccessIteratorPairIterator  seqs_begin,
RandomAccessIteratorPairIterator  seqs_end,
RandomAccessIteratorOut  target,
_DifferenceTp  length,
Comparator  comp,
__gnu_parallel::sequential_tag   
)

Multiway Merge Frontend.

Merge the sequences specified by seqs_begin and seqs_end into target. seqs_begin and seqs_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the end of the same sequence in their second entry.

Ties are broken arbitrarily. See stable_multiway_merge for a variant that breaks ties by sequence number but is slower.

The first entries of the pairs (i.e. the begin iterators) will be moved forward.

The output sequence has to provide enough space for all elements that are written to it.

This function will merge the input sequences:

  • not stable
  • parallel, depending on the input size and Settings
  • using sampling for splitting
  • not using sentinels

Example:

   int sequences[10][10];
   for (int i = 0; i < 10; ++i)
     for (int j = 0; i < 10; ++j)
       sequences[i][j] = j;
   int out[33];
   std::vector<std::pair<int*> > seqs;
   for (int i = 0; i < 10; ++i)
     { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
   multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
 
See also:
stable_multiway_merge
Precondition:
All input sequences must be sorted.
Target must provide enough space to merge out length elements or the number of elements in all sequences, whichever is smaller.
Postcondition:
[target, return value) contains merged elements from the input sequences.
return value - target = min(length, number of elements in all sequences).
Parameters:
RandomAccessIteratorPairIteratoriterator over sequence of pairs of iterators
RandomAccessIteratorOutiterator over target sequence
_DifferenceTpdifference type for the sequence
Comparatorstrict weak ordering type to compare elements in sequences
seqs_beginbegin of sequence sequence
seqs_endend of sequence sequence
targettarget sequence to merge to.
compstrict weak ordering to use for element comparison.
lengthMaximum length to merge, possibly larger than the number of elements available.
Returns:
end iterator of output sequence

Definition at line 1477 of file multiway_merge.h.

References _GLIBCXX_CALL, and sequential_multiway_merge().

template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator >
RandomAccessIterator3 __gnu_parallel::multiway_merge_3_variant ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
_DifferenceTp  length,
Comparator  comp 
)

Highly efficient 3-way merging procedure.

Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging out an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into labels in C++).

This works well for merging up to 4 sequences.

Note that making the merging stable does not come at a performance hit.

Whether the merging is done guarded or unguarded is selected by the used iterator class.

Parameters:
seqs_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
compComparator.
lengthMaximum length to merge, less equal than the total number of elements available.
Returns:
End iterator of output sequence.

Definition at line 290 of file multiway_merge.h.

References _GLIBCXX_CALL.

template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator >
RandomAccessIterator3 __gnu_parallel::multiway_merge_4_variant ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
_DifferenceTp  length,
Comparator  comp 
)

Highly efficient 4-way merging procedure.

Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging out an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into goto labels in C++).

This works well for merging up to 4 sequences.

Note that making the merging stable does not come at a performance hit.

Whether the merging is done guarded or unguarded is selected by the used iterator class.

Parameters:
seqs_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
compComparator.
lengthMaximum length to merge, less equal than the total number of elements available.
Returns:
End iterator of output sequence.

Definition at line 410 of file multiway_merge.h.

References _GLIBCXX_CALL.

template<bool stable, typename RandomAccessIteratorIterator , typename Comparator , typename difference_type >
void __gnu_parallel::multiway_merge_exact_splitting ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
difference_type  length,
difference_type  total_length,
Comparator  comp,
std::vector< std::pair< difference_type, difference_type > > *  pieces 
)

Exact splitting for parallel multiway-merge routine.

None of the passed sequences may be empty.

Definition at line 1181 of file multiway_merge.h.

References _GLIBCXX_PARALLEL_LENGTH, std::vector< _Tp, _Alloc >::begin(), equally_split(), multiseq_partition(), and std::vector< _Tp, _Alloc >::resize().

Referenced by parallel_merge_advance().

template<typename LT , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator >
RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
_DifferenceTp  length,
Comparator  comp 
)

Multi-way merging procedure for a high branching factor, guarded case.

This merging variant uses a LoserTree class as selected by LT.

Stability is selected through the used LoserTree class LT.

At least one non-empty sequence is required.

Parameters:
seqs_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
compComparator.
lengthMaximum length to merge, less equal than the total number of elements available.
Returns:
End iterator of output sequence.

Definition at line 534 of file multiway_merge.h.

References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_LENGTH.

template<typename UnguardedLoserTree , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator >
RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree_sentinel ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &  sentinel,
_DifferenceTp  length,
Comparator  comp 
)

Multi-way merging procedure for a high branching factor, requiring sentinels to exist.

Parameters:
stableThe value must the same as for the used LoserTrees.
UnguardedLoserTreeLoser Tree variant to use for the unguarded merging.
GuardedLoserTreeLoser Tree variant to use for the guarded merging.
seqs_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
compComparator.
lengthMaximum length to merge, less equal than the total number of elements available.
Returns:
End iterator of output sequence.

Definition at line 705 of file multiway_merge.h.

References _GLIBCXX_CALL, is_sorted(), and multiway_merge_loser_tree_unguarded().

template<typename LT , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator >
RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree_unguarded ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &  sentinel,
_DifferenceTp  length,
Comparator  comp 
)

Multi-way merging procedure for a high branching factor, unguarded case.

Merging is done using the LoserTree class LT.

Stability is selected by the used LoserTrees.

Precondition:
No input will run out of elements during the merge.
Parameters:
seqs_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
compComparator.
lengthMaximum length to merge, less equal than the total number of elements available.
Returns:
End iterator of output sequence.

Definition at line 615 of file multiway_merge.h.

References _GLIBCXX_CALL.

Referenced by multiway_merge_loser_tree_sentinel().

template<bool stable, typename RandomAccessIteratorIterator , typename Comparator , typename difference_type >
void __gnu_parallel::multiway_merge_sampling_splitting ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
difference_type  length,
difference_type  total_length,
Comparator  comp,
std::vector< std::pair< difference_type, difference_type > > *  pieces 
)

Sampling based splitting for parallel multiway-merge routine.

Definition at line 1100 of file multiway_merge.h.

References _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::merge_oversampling.

template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator >
RandomAccessIteratorOut __gnu_parallel::multiway_merge_sentinels ( RandomAccessIteratorPairIterator  seqs_begin,
RandomAccessIteratorPairIterator  seqs_end,
RandomAccessIteratorOut  target,
_DifferenceTp  length,
Comparator  comp,
__gnu_parallel::sequential_tag   
)

Multiway Merge Frontend.

Merge the sequences specified by seqs_begin and seqs_end into target. seqs_begin and seqs_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the end of the same sequence in their second entry.

Ties are broken arbitrarily. See stable_multiway_merge for a variant that breaks ties by sequence number but is slower.

The first entries of the pairs (i.e. the begin iterators) will be moved forward accordingly.

The output sequence has to provide enough space for all elements that are written to it.

This function will merge the input sequences:

  • not stable
  • parallel, depending on the input size and Settings
  • using sampling for splitting
  • using sentinels

You have to take care that the element the end iterator points to is readable and contains a value that is greater than any other non-sentinel value in all sequences.

Example:

   int sequences[10][11];
   for (int i = 0; i < 10; ++i)
     for (int j = 0; i < 11; ++j)
       sequences[i][j] = j; // last one is sentinel!
   int out[33];
   std::vector<std::pair<int*> > seqs;
   for (int i = 0; i < 10; ++i)
     { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
   multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
 
Precondition:
All input sequences must be sorted.
Target must provide enough space to merge out length elements or the number of elements in all sequences, whichever is smaller.
For each i, seqs_begin[i].second must be the end marker of the sequence, but also reference the one more sentinel element.
Postcondition:
[target, return value) contains merged elements from the input sequences.
return value - target = min(length, number of elements in all sequences).
See also:
stable_multiway_merge_sentinels
Parameters:
RandomAccessIteratorPairIteratoriterator over sequence of pairs of iterators
RandomAccessIteratorOutiterator over target sequence
_DifferenceTpdifference type for the sequence
Comparatorstrict weak ordering type to compare elements in sequences
seqs_beginbegin of sequence sequence
seqs_endend of sequence sequence
targettarget sequence to merge to.
compstrict weak ordering to use for element comparison.
lengthMaximum length to merge, possibly larger than the number of elements available.
Returns:
end iterator of output sequence

Definition at line 1849 of file multiway_merge.h.

References _GLIBCXX_CALL, and sequential_multiway_merge().

template<typename RandomAccessIterator , typename Comparator >
bool __gnu_parallel::operator< ( guarded_iterator< RandomAccessIterator, Comparator > &  bi1,
guarded_iterator< RandomAccessIterator, Comparator > &  bi2 
) [inline]

Compare two elements referenced by guarded iterators.

Parameters:
bi1First iterator.
bi2Second iterator.
Returns:
True if less.

Definition at line 144 of file multiway_merge.h.

template<typename RandomAccessIterator , typename Comparator >
bool __gnu_parallel::operator< ( unguarded_iterator< RandomAccessIterator, Comparator > &  bi1,
unguarded_iterator< RandomAccessIterator, Comparator > &  bi2 
) [inline]

Compare two elements referenced by unguarded iterators.

Parameters:
bi1First iterator.
bi2Second iterator.
Returns:
True if less.

Definition at line 239 of file multiway_merge.h.

template<typename RandomAccessIterator , typename Comparator >
bool __gnu_parallel::operator<= ( guarded_iterator< RandomAccessIterator, Comparator > &  bi1,
guarded_iterator< RandomAccessIterator, Comparator > &  bi2 
) [inline]

Compare two elements referenced by guarded iterators.

Parameters:
bi1First iterator.
bi2Second iterator.
Returns:
True if less equal.

Definition at line 160 of file multiway_merge.h.

template<typename RandomAccessIterator , typename Comparator >
bool __gnu_parallel::operator<= ( unguarded_iterator< RandomAccessIterator, Comparator > &  bi1,
unguarded_iterator< RandomAccessIterator, Comparator > &  bi2 
) [inline]

Compare two elements referenced by unguarded iterators.

Parameters:
bi1First iterator.
bi2Second iterator.
Returns:
True if less equal.

Definition at line 252 of file multiway_merge.h.

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename RandomAccessIterator3 , typename Comparator >
RandomAccessIterator3 __gnu_parallel::parallel_merge_advance ( RandomAccessIterator1 &  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2 &  begin2,
RandomAccessIterator2  end2,
RandomAccessIterator3  target,
typename std::iterator_traits< RandomAccessIterator1 >::difference_type  max_length,
Comparator  comp 
) [inline]

Merge routine fallback to sequential in case the iterators of the two input sequences are of different type.

Parameters:
begin1Begin iterator of first sequence.
end1End iterator of first sequence.
begin2Begin iterator of second sequence.
end2End iterator of second sequence.
targetTarget begin iterator.
max_lengthMaximum number of elements to merge.
compComparator.
Returns:
Output end iterator.

Definition at line 198 of file merge.h.

References merge_advance().

template<typename RandomAccessIterator1 , typename RandomAccessIterator3 , typename Comparator >
RandomAccessIterator3 __gnu_parallel::parallel_merge_advance ( RandomAccessIterator1 &  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator1 &  begin2,
RandomAccessIterator1  end2,
RandomAccessIterator3  target,
typename std::iterator_traits< RandomAccessIterator1 >::difference_type  max_length,
Comparator  comp 
) [inline]

Parallel merge routine being able to merge only the max_length smallest elements.

The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. The functionality is projected onto parallel_multiway_merge.

Parameters:
begin1Begin iterator of first sequence.
end1End iterator of first sequence.
begin2Begin iterator of second sequence.
end2End iterator of second sequence.
targetTarget begin iterator.
max_lengthMaximum number of elements to merge.
compComparator.
Returns:
Output end iterator.

Definition at line 228 of file merge.h.

References multiway_merge_exact_splitting(), and parallel_multiway_merge().

template<bool stable, bool sentinels, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Splitter , typename Comparator >
RandomAccessIterator3 __gnu_parallel::parallel_multiway_merge ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Splitter  splitter,
_DifferenceTp  length,
Comparator  comp,
thread_index_t  num_threads 
)

Parallel multi-way merge routine.

The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings.

Must not be called if the number of sequences is 1.

Parameters:
Splitterfunctor to split input (either exact or sampling based)
seqs_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
compComparator.
lengthMaximum length to merge, possibly larger than the number of elements available.
stableStable merging incurs a performance penalty.
sentinelIgnored.
Returns:
End iterator of output sequence.

Definition at line 1286 of file multiway_merge.h.

References _GLIBCXX_CALL, _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), is_sorted(), and __gnu_parallel::_Settings::merge_oversampling.

Referenced by parallel_merge_advance().

template<typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_nth_element ( RandomAccessIterator  begin,
RandomAccessIterator  nth,
RandomAccessIterator  end,
Comparator  comp 
)

Parallel implementation of std::nth_element().

Parameters:
beginBegin iterator of input sequence.
nthIterator of element that must be in position afterwards.
endEnd iterator of input sequence.
compComparator.

Definition at line 330 of file partition.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), max(), __gnu_parallel::_Settings::nth_element_minimal_n, parallel_partition(), and __gnu_parallel::_Settings::partition_minimal_n.

Referenced by parallel_partial_sort().

template<typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_partial_sort ( RandomAccessIterator  begin,
RandomAccessIterator  middle,
RandomAccessIterator  end,
Comparator  comp 
)

Parallel implementation of std::partial_sort().

Parameters:
beginBegin iterator of input sequence.
middleSort until this position.
endEnd iterator of input sequence.
compComparator.

Definition at line 418 of file partition.h.

References parallel_nth_element().

template<typename InputIterator , typename OutputIterator , typename BinaryOperation >
OutputIterator __gnu_parallel::parallel_partial_sum ( InputIterator  begin,
InputIterator  end,
OutputIterator  result,
BinaryOperation  bin_op 
)

Parallel partial sum front-end.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
resultBegin iterator of output sequence.
bin_opAssociative binary function.
Returns:
End iterator of output sequence.

Definition at line 196 of file partial_sum.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), and parallel_partial_sum_linear().

template<typename InputIterator , typename OutputIterator , typename BinaryOperation >
OutputIterator __gnu_parallel::parallel_partial_sum_basecase ( InputIterator  begin,
InputIterator  end,
OutputIterator  result,
BinaryOperation  bin_op,
typename std::iterator_traits< InputIterator >::value_type  value 
)

Base case prefix sum routine.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
resultBegin iterator of output sequence.
bin_opAssociative binary function.
valueStart value. Must be passed since the neutral element is unknown in general.
Returns:
End iterator of output sequence.

Definition at line 58 of file partial_sum.h.

Referenced by parallel_partial_sum_linear().

template<typename InputIterator , typename OutputIterator , typename BinaryOperation >
OutputIterator __gnu_parallel::parallel_partial_sum_linear ( InputIterator  begin,
InputIterator  end,
OutputIterator  result,
BinaryOperation  bin_op,
typename std::iterator_traits< InputIterator >::difference_type  n 
)

Parallel partial sum implementation, two-phase approach, no recursion.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
resultBegin iterator of output sequence.
bin_opAssociative binary function.
nLength of sequence.
num_threadsNumber of threads to use.
Returns:
End iterator of output sequence.

Definition at line 90 of file partial_sum.h.

References equally_split(), __gnu_parallel::_Settings::get(), parallel_partial_sum_basecase(), and __gnu_parallel::_Settings::partial_sum_dilation.

Referenced by parallel_partial_sum().

template<typename RandomAccessIterator , typename Predicate >
std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::parallel_partition ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Predicate  pred,
thread_index_t  num_threads 
)

Parallel implementation of std::partition.

Parameters:
beginBegin iterator of input sequence to split.
endEnd iterator of input sequence to split.
predPartition predicate, possibly including some kind of pivot.
num_threadsMaximum number of threads to use for this task.
Returns:
Number of elements not fulfilling the predicate.

Definition at line 55 of file partition.h.

References _GLIBCXX_CALL, _GLIBCXX_VOLATILE, __gnu_parallel::_Settings::get(), std::left(), __gnu_parallel::_Settings::partition_chunk_share, __gnu_parallel::_Settings::partition_chunk_size, and std::right().

Referenced by parallel_nth_element(), parallel_sort_qs_divide(), and qsb_divide().

template<typename RandomAccessIterator , typename RandomNumberGenerator >
void __gnu_parallel::parallel_random_shuffle ( RandomAccessIterator  begin,
RandomAccessIterator  end,
RandomNumberGenerator  rng = random_number() 
) [inline]

Parallel random public call.

Parameters:
beginBegin iterator of sequence.
endEnd iterator of sequence.
rngRandom number generator to use.

Definition at line 507 of file random_shuffle.h.

References parallel_random_shuffle_drs().

template<typename RandomAccessIterator , typename RandomNumberGenerator >
void __gnu_parallel::parallel_random_shuffle_drs ( RandomAccessIterator  begin,
RandomAccessIterator  end,
typename std::iterator_traits< RandomAccessIterator >::difference_type  n,
thread_index_t  num_threads,
RandomNumberGenerator &  rng 
)
template<bool stable, typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
balanced_quicksort_tag  parallelism 
) [inline]

Choose balanced quicksort for parallel sorting.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
compComparator.
stableSort stable.

Definition at line 154 of file sort.h.

References _GLIBCXX_CALL, __gnu_parallel::parallel_tag::get_num_threads(), and parallel_sort_qsb().

Here is the call graph for this function:

template<bool stable, typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
multiway_mergesort_exact_tag  parallelism 
) [inline]

Choose multiway mergesort with exact splitting, for parallel sorting.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
compComparator.

Definition at line 97 of file sort.h.

References _GLIBCXX_CALL, and __gnu_parallel::parallel_tag::get_num_threads().

Here is the call graph for this function:

template<bool stable, typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
multiway_mergesort_tag  parallelism 
) [inline]

Choose multiway mergesort, splitting variant at run-time, for parallel sorting.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
compComparator.

Definition at line 74 of file sort.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), and __gnu_parallel::parallel_tag::get_num_threads().

Here is the call graph for this function:

template<bool stable, typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
multiway_mergesort_sampling_tag  parallelism 
) [inline]

Choose multiway mergesort with splitting by sampling, for parallel sorting.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
compComparator.

Definition at line 116 of file sort.h.

References _GLIBCXX_CALL, and __gnu_parallel::parallel_tag::get_num_threads().

Here is the call graph for this function:

template<bool stable, typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
default_parallel_tag  parallelism 
) [inline]

Choose multiway mergesort with exact splitting, for parallel sorting.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
compComparator.

Definition at line 175 of file sort.h.

References _GLIBCXX_CALL, and __gnu_parallel::parallel_tag::get_num_threads().

Here is the call graph for this function:

template<bool stable, typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
parallel_tag  parallelism 
) [inline]

Choose a parallel sorting algorithm.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
compComparator.
stableSort stable.

Definition at line 196 of file sort.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), __gnu_parallel::parallel_tag::get_num_threads(), parallel_sort_qs(), and parallel_sort_qsb().

Here is the call graph for this function:

template<bool stable, typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
quicksort_tag  parallelism 
) [inline]

Choose quicksort for parallel sorting.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator of input sequence.
compComparator.

Definition at line 134 of file sort.h.

References _GLIBCXX_CALL, __gnu_parallel::parallel_tag::get_num_threads(), and parallel_sort_qs().

Here is the call graph for this function:

template<bool stable, bool exact, typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort_mwms ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
thread_index_t  num_threads 
)
template<bool stable, bool exact, typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort_mwms_pu ( PMWMSSortingData< RandomAccessIterator > *  sd,
Comparator &  comp 
)
template<typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort_qs ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
thread_index_t  num_threads 
)

Unbalanced quicksort main call.

Parameters:
beginBegin iterator of input sequence.
endEnd iterator input sequence, ignored.
compComparator.
num_threadsNumber of threads that are allowed to work on this part.

Definition at line 157 of file quicksort.h.

References _GLIBCXX_CALL, and parallel_sort_qs_conquer().

Referenced by parallel_sort().

template<typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort_qs_conquer ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
thread_index_t  num_threads 
)

Unbalanced quicksort conquer step.

Parameters:
beginBegin iterator of subsequence.
endEnd iterator of subsequence.
compComparator.
num_threadsNumber of threads that are allowed to work on this part.

Definition at line 101 of file quicksort.h.

References __gnu_parallel::_Settings::get(), and parallel_sort_qs_divide().

Referenced by parallel_sort_qs().

template<typename RandomAccessIterator , typename Comparator >
std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::parallel_sort_qs_divide ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
typename std::iterator_traits< RandomAccessIterator >::difference_type  pivot_rank,
typename std::iterator_traits< RandomAccessIterator >::difference_type  num_samples,
thread_index_t  num_threads 
)

Unbalanced quicksort divide step.

Parameters:
beginBegin iterator of subsequence.
endEnd iterator of subsequence.
compComparator.
pivot_rankDesired rank of the pivot.
num_samplesChoose pivot from that many samples.
num_threadsNumber of threads that are allowed to work on this part.

Definition at line 51 of file quicksort.h.

References min(), and parallel_partition().

Referenced by parallel_sort_qs_conquer().

template<typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::parallel_sort_qsb ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
thread_index_t  num_threads 
)

Top-level quicksort routine.

Parameters:
beginBegin iterator of sequence.
endEnd iterator of sequence.
compComparator.
num_threadsNumber of threads that are allowed to work on this part.

Definition at line 418 of file balanced_quicksort.h.

References _GLIBCXX_CALL, __gnu_parallel::QSBThreadLocal< RandomAccessIterator >::elements_leftover, and qsb_conquer().

Referenced by parallel_sort().

template<typename InputIterator , class OutputIterator >
OutputIterator __gnu_parallel::parallel_unique_copy ( InputIterator  first,
InputIterator  last,
OutputIterator  result 
) [inline]

Parallel std::unique_copy(), without explicit equality predicate.

Parameters:
firstBegin iterator of input sequence.
lastEnd iterator of input sequence.
resultBegin iterator of result sequence.
Returns:
End iterator of result sequence.

Definition at line 181 of file unique_copy.h.

References parallel_unique_copy().

template<typename InputIterator , class OutputIterator , class BinaryPredicate >
OutputIterator __gnu_parallel::parallel_unique_copy ( InputIterator  first,
InputIterator  last,
OutputIterator  result,
BinaryPredicate  binary_pred 
)

Parallel std::unique_copy(), w/o explicit equality predicate.

Parameters:
firstBegin iterator of input sequence.
lastEnd iterator of input sequence.
resultBegin iterator of result sequence.
binary_predEquality predicate.
Returns:
End iterator of result sequence.

Definition at line 51 of file unique_copy.h.

References _GLIBCXX_CALL, and equally_split().

Referenced by parallel_unique_copy().

template<typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::qsb_conquer ( QSBThreadLocal< RandomAccessIterator > **  tls,
RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
thread_index_t  iam,
thread_index_t  num_threads,
bool  parent_wait 
)

Quicksort conquer step.

Parameters:
tlsArray of thread-local storages.
beginBegin iterator of subsequence.
endEnd iterator of subsequence.
compComparator.
iamNumber of the thread processing this function.
num_threadsNumber of threads that are allowed to work on this part.

Definition at line 163 of file balanced_quicksort.h.

References __gnu_parallel::QSBThreadLocal< RandomAccessIterator >::elements_leftover, __gnu_parallel::QSBThreadLocal< RandomAccessIterator >::initial, qsb_divide(), and qsb_local_sort_with_helping().

Referenced by parallel_sort_qsb().

template<typename RandomAccessIterator , typename Comparator >
std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::qsb_divide ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
thread_index_t  num_threads 
)

Balanced quicksort divide step.

Parameters:
beginBegin iterator of subsequence.
endEnd iterator of subsequence.
compComparator.
num_threadsNumber of threads that are allowed to work on this part.
Precondition:
(end-begin)>=1

Definition at line 100 of file balanced_quicksort.h.

References median_of_three_iterators(), and parallel_partition().

Referenced by qsb_conquer().

template<typename RandomAccessIterator , typename Comparator >
void __gnu_parallel::qsb_local_sort_with_helping ( QSBThreadLocal< RandomAccessIterator > **  tls,
Comparator &  comp,
int  iam,
bool  wait 
)
template<typename RandomNumberGenerator >
int __gnu_parallel::random_number_pow2 ( int  logp,
RandomNumberGenerator &  rng 
) [inline]

Generate a random number in [0,2^logp).

Parameters:
logpLogarithm (basis 2) of the upper range bound.
rngRandom number generator to use.

Definition at line 115 of file random_shuffle.h.

Referenced by parallel_random_shuffle_drs_pu(), and sequential_random_shuffle().

template<typename T >
T __gnu_parallel::round_up_to_pow2 ( x)

Round up to the next greater power of 2.

Parameters:
xInteger to round up

Definition at line 241 of file random_shuffle.h.

References __log2().

Referenced by parallel_random_shuffle_drs(), and sequential_random_shuffle().

template<typename _RandomAccessIterator1 , typename _RandomAccessIterator2 , typename Pred >
_RandomAccessIterator1 __gnu_parallel::search_template ( _RandomAccessIterator1  begin1,
_RandomAccessIterator1  end1,
_RandomAccessIterator2  begin2,
_RandomAccessIterator2  end2,
Pred  pred 
)

Parallel std::search.

Parameters:
begin1Begin iterator of first sequence.
end1End iterator of first sequence.
begin2Begin iterator of second sequence.
end2End iterator of second sequence.
predFind predicate.
Returns:
Place of finding in first sequences.

Definition at line 82 of file search.h.

References _GLIBCXX_CALL, calc_borders(), equally_split(), and min().

template<bool stable, bool sentinels, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator >
RandomAccessIterator3 __gnu_parallel::sequential_multiway_merge ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &  sentinel,
_DifferenceTp  length,
Comparator  comp 
)

Sequential multi-way merging switch.

The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings.

Parameters:
seqs_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
compComparator.
lengthMaximum length to merge, possibly larger than the number of elements available.
stableStable merging incurs a performance penalty.
sentinelThe sequences have a sentinel element.
Returns:
End iterator of output sequence.

Definition at line 979 of file multiway_merge.h.

References _GLIBCXX_CALL, _GLIBCXX_PARALLEL_LENGTH, is_sorted(), and merge_advance().

Referenced by multiway_merge(), and multiway_merge_sentinels().

template<typename RandomAccessIterator , typename RandomNumberGenerator >
void __gnu_parallel::sequential_random_shuffle ( RandomAccessIterator  begin,
RandomAccessIterator  end,
RandomNumberGenerator &  rng 
)

Sequential cache-efficient random shuffle.

Parameters:
beginBegin iterator of sequence.
endEnd iterator of sequence.
rngRandom number generator to use.

Definition at line 394 of file random_shuffle.h.

References __log2(), __gnu_parallel::_Settings::L2_cache_size, std::min(), random_number_pow2(), round_up_to_pow2(), and __gnu_parallel::_Settings::TLB_size.

Referenced by parallel_random_shuffle_drs().

template<typename InputIterator >
void __gnu_parallel::shrink ( std::vector< InputIterator > &  os_starts,
size_t &  count_to_two,
size_t &  range_length 
)

Combines two ranges into one and thus halves the number of ranges.

Parameters:
os_startsStart positions worked on (oversampled).
count_to_twoCounts up to 2.
range_lengthCurrent length of a chunk.

Definition at line 70 of file list_partition.h.

References std::vector< _Tp, _Alloc >::size().

Referenced by shrink_and_double().

template<typename InputIterator >
void __gnu_parallel::shrink_and_double ( std::vector< InputIterator > &  os_starts,
size_t &  count_to_two,
size_t &  range_length,
const bool  make_twice 
)

Shrinks and doubles the ranges.

Parameters:
os_startsStart positions worked on (oversampled).
count_to_twoCounts up to 2.
range_lengthCurrent length of a chunk.
make_twiceWhether the os_starts is allowed to be grown or not

Definition at line 50 of file list_partition.h.

References std::vector< _Tp, _Alloc >::resize(), shrink(), and std::vector< _Tp, _Alloc >::size().

Referenced by list_partition().

void __gnu_parallel::yield ( ) [inline]

Yield the control to another thread, without waiting for the end to the time slice.

Definition at line 340 of file parallel/compatibility.h.

Referenced by for_each_template_random_access_workstealing(), and qsb_local_sort_with_helping().


Variable Documentation

const int __gnu_parallel::lcas_t_bits [static]

Number of bits of lcas_t.

Definition at line 149 of file types.h.

Referenced by decode2(), and encode2().

lcas_t with the right half of bits set to 1.

Definition at line 152 of file types.h.

Referenced by decode2().