__gnu_parallel(3cxx) | __gnu_parallel(3cxx) |
NAME¶
__gnu_parallel -SYNOPSIS¶
Classes¶
struct __accumulate_binop_reduct
Typedefs¶
typedef unsigned short _BinIndex
Enumerations¶
enum _AlgorithmStrategy { heuristic, force_sequential, force_parallel }
Functions¶
template<typename _RAIter , typename _DifferenceTp > void __calc_borders (_RAIter __elements, _DifferenceTp __length, _DifferenceTp *__off)
Variables¶
static const int _CASable_bits
Detailed Description¶
GNU parallel code for public use.Typedef Documentation¶
typedef unsigned short __gnu_parallel::_BinIndex¶
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 int64_t __gnu_parallel::_CASable¶
Longest compare-and-swappable integer type on this platform. Definition at line 127 of file types.h.typedef uint64_t __gnu_parallel::_SequenceIndex¶
Unsigned integer to index __elements. The total number of elements for each algorithm must fit into this type. Definition at line 117 of file types.h.typedef uint16_t __gnu_parallel::_ThreadIndex¶
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit into this type. Definition at line 123 of file types.h.Enumeration Type Documentation¶
enum __gnu_parallel::_AlgorithmStrategy¶
Strategies for run-time algorithm selection: Definition at line 67 of file types.h.enum __gnu_parallel::_FindAlgorithm¶
Find algorithms: Definition at line 106 of file types.h.enum __gnu_parallel::_MultiwayMergeAlgorithm¶
Merging algorithms: Definition at line 85 of file types.h.enum __gnu_parallel::_Parallelism¶
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.
enum __gnu_parallel::_PartialSumAlgorithm¶
Partial sum algorithms: recursive, linear. Definition at line 91 of file types.h.enum __gnu_parallel::_SortAlgorithm¶
Sorting algorithms: Definition at line 76 of file types.h.enum __gnu_parallel::_SplittingAlgorithm¶
Sorting/merging algorithms: sampling, __exact. Definition at line 98 of file types.h.Function Documentation¶
template<typename _RAIter , typename _DifferenceTp > void __gnu_parallel::__calc_borders (_RAIter__elements, _DifferenceTp__length, _DifferenceTp *__off)¶
Precalculate __advances for Knuth-Morris-Pratt algorithm. Parameters:__elements Begin iterator of sequence
to search for.
__length Length of sequence to search for.
__off Returned __offsets.
template<typename _Tp > bool __gnu_parallel::__compare_and_swap (volatile _Tp *__ptr, _Tp__comparand, _Tp__replacement) [inline]¶
Compare *__ptr and comparand. If equal, let *ptr=__replacement and return true, return false otherwise. Implementation is heavily platform-dependent. Parameters:__ptr Pointer to signed integer.
__comparand Compare value.
__replacement Replacement value.
bool __gnu_parallel::__compare_and_swap_32 (volatile int32_t *__ptr, int32_t__comparand, int32_t__replacement) [inline]¶
Compare *__ptr and comparand. If equal, let *ptr=__replacement and return true, return false otherwise. Implementation is heavily platform-dependent. Parameters:__ptr Pointer to 32-bit signed integer.
__comparand Compare value.
__replacement Replacement value.
bool __gnu_parallel::__compare_and_swap_64 (volatile int64_t *__ptr, int64_t__comparand, int64_t__replacement) [inline]¶
Compare *__ptr and comparand. If equal, let *ptr=__replacement and return true, return false otherwise. Implementation is heavily platform-dependent. Parameters:__ptr Pointer to 64-bit signed integer.
__comparand Compare value.
__replacement Replacement value.
void __gnu_parallel::__decode2 (_CASable__x, int &__a, int &__b) [inline]¶
Decode two integers from one gnu_parallel::_CASable. Parameters:__x __gnu_parallel::_CASable to
decode integers from.
__a First integer, to be decoded from the most-significant
_CASable_bits/2 bits of __x.
__b Second integer, to be encoded in the least-significant
_CASable_bits/2 bits of __x.
See Also:
__encode2
template<typename _RAIter , typename _DifferenceTp > void __gnu_parallel::__determine_samples (_PMWMSSortingData< _RAIter > *__sd, _DifferenceTp__num_samples)¶
Select _M_samples from a sequence. Parameters:__sd Pointer to algorithm data. _Result
will be placed in __sd->_M_samples.
__num_samples Number of _M_samples to select.
_CASable __gnu_parallel::__encode2 (int__a, int__b) [inline]¶
Encode two integers into one gnu_parallel::_CASable. Parameters:__a First integer, to be encoded in the
most-significant _CASable_bits/2 bits.
__b Second integer, to be encoded in the least-significant
_CASable_bits/2 bits.
Returns:
value encoding __a and __b.
See Also:
__decode2
template<typename _DifferenceType , typename _OutputIterator > _OutputIterator __gnu_parallel::__equally_split (_DifferenceType__n, _ThreadIndex__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:__n Number of elements
__num_threads Number of parts
__s Splitters
Returns:
End of __splitter sequence, i.e.
__s+__num_threads+1
template<typename _DifferenceType > _DifferenceType __gnu_parallel::__equally_split_point (_DifferenceType__n, _ThreadIndex__num_threads, _ThreadIndex__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:__n Number of elements
__num_threads Number of parts
__thread_no Number of threads
Returns:
splitting point
template<typename _Tp > _Tp __gnu_parallel::__fetch_and_add (volatile _Tp *__ptr, _Tp__addend) [inline]¶
Add a value to a variable, atomically. Implementation is heavily platform-dependent. Parameters:__ptr Pointer to a signed integer.
__addend Value to add.
int32_t __gnu_parallel::__fetch_and_add_32 (volatile int32_t *__ptr, int32_t__addend) [inline]¶
Add a value to a variable, atomically. Implementation is heavily platform-dependent. Parameters:__ptr Pointer to a 32-bit signed
integer.
__addend Value to add.
int64_t __gnu_parallel::__fetch_and_add_64 (volatile int64_t *__ptr, int64_t__addend) [inline]¶
Add a value to a variable, atomically. Implementation is heavily platform-dependent. Parameters:__ptr Pointer to a 64-bit signed
integer.
__addend Value to add.
template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector > std::pair<_RAIter1, _RAIter2> __gnu_parallel::__find_template (_RAIter1__begin1, _RAIter1__end1, _RAIter2__begin2, _Pred__pred, _Selector__selector) [inline]¶
Parallel std::find, switch for different algorithms. Parameters:__begin1 Begin iterator of first
sequence.
__end1 End iterator of first sequence.
__begin2 Begin iterator of second sequence. Must have same length as
first sequence.
__pred Find predicate.
__selector _Functionality (e. g. std::find_if(), std::equal(),...)
Returns:
Place of finding in both sequences.
template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector > std::pair<_RAIter1, _RAIter2> __gnu_parallel::__find_template (_RAIter1__begin1, _RAIter1__end1, _RAIter2__begin2, _Pred__pred, _Selector__selector, equal_split_tag)¶
Parallel std::find, equal splitting variant. Parameters:__begin1 Begin iterator of first
sequence.
__end1 End iterator of first sequence.
__begin2 Begin iterator of second sequence. Second __sequence must have
same length as first sequence.
__pred Find predicate.
__selector _Functionality (e. g. std::find_if(), std::equal(),...)
Returns:
Place of finding in both sequences.
template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector > std::pair<_RAIter1, _RAIter2> __gnu_parallel::__find_template (_RAIter1__begin1, _RAIter1__end1, _RAIter2__begin2, _Pred__pred, _Selector__selector, growing_blocks_tag)¶
Parallel std::find, growing block size variant. Parameters:__begin1 Begin iterator of first
sequence.
__end1 End iterator of first sequence.
__begin2 Begin iterator of second sequence. Second __sequence must have
same length as first sequence.
__pred Find predicate.
__selector _Functionality (e. g. std::find_if(), std::equal(),...)
Returns:
Place of finding in both sequences.
See Also:
__gnu_parallel::_Settings::find_sequential_search_size
__gnu_parallel::_Settings::find_scale_factor
There are two main differences between the growing blocks and the constant-size
blocks variants.
- 1.
- For GB, the block size grows; for CSB, the block size is fixed.
- 2.
- For GB, the blocks are allocated dynamically; for CSB, the blocks are allocated in a predetermined manner, namely spacial round-robin.
template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector > std::pair<_RAIter1, _RAIter2> __gnu_parallel::__find_template (_RAIter1__begin1, _RAIter1__end1, _RAIter2__begin2, _Pred__pred, _Selector__selector, constant_size_blocks_tag)¶
Parallel std::find, constant block size variant. Parameters:__begin1 Begin iterator of first
sequence.
__end1 End iterator of first sequence.
__begin2 Begin iterator of second sequence. Second __sequence must have
same length as first sequence.
__pred Find predicate.
__selector _Functionality (e. g. std::find_if(), std::equal(),...)
Returns:
Place of finding in both sequences.
See Also:
__gnu_parallel::_Settings::find_sequential_search_size
__gnu_parallel::_Settings::find_block_size There are two main differences
between the growing blocks and the constant-size blocks variants.
- 1.
- For GB, the block size grows; for CSB, the block size is fixed.
- 2.
- For GB, the blocks are allocated dynamically; for CSB, the blocks are allocated in a predetermined manner, namely spacial round-robin.
template<typename _IIter , typename _UserOp , typename _Functionality , typename _Red , typename _Result > _UserOp __gnu_parallel::__for_each_template_random_access (_IIter__begin, _IIter__end, _UserOp__user_op, _Functionality &__functionality, _Red__reduction, _Result__reduction_start, _Result &__output, typename std::iterator_traits< _IIter >::difference_type__bound, _Parallelism__parallelism_tag)¶
Chose the desired algorithm by evaluating __parallelism_tag. Parameters:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__user_op A user-specified functor (comparator, predicate, associative
operator,...)
__functionality functor to process an element with __user_op
(depends on desired functionality, e. g. accumulate, for_each,...
__reduction Reduction functor.
__reduction_start Initial value for reduction.
__output Output iterator.
__bound Maximum number of elements processed.
__parallelism_tag Parallelization method
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > _Op __gnu_parallel::__for_each_template_random_access_ed (_RAIter__begin, _RAIter__end, _Op__o, _Fu &__f, _Red__r, _Result__base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type__bound)¶
Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work. Parameters:__begin Begin iterator of element
sequence.
__end End iterator of element sequence.
__o User-supplied functor (comparator, predicate, adding functor, ...)
__f Functor to 'process' an element with __op (depends on desired
functionality, e. g. for std::for_each(), ...).
__r Functor to 'add' a single __result to the already processed elements
(depends on functionality).
__base Base value for reduction.
__output Pointer to position where final result is written to
__bound Maximum number of elements processed (e. g. for
std::count_n()).
Returns:
User-supplied functor (that may contain a part
of the result).
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > _Op __gnu_parallel::__for_each_template_random_access_omp_loop (_RAIter__begin, _RAIter__end, _Op__o, _Fu &__f, _Red__r, _Result__base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type__bound)¶
Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop. Parameters:__begin Begin iterator of element
sequence.
__end End iterator of element sequence.
__o User-supplied functor (comparator, predicate, adding functor, etc.).
__f Functor to process an element with __op (depends on desired
functionality, e. g. for std::for_each(), ...).
__r Functor to add a single __result to the already processed
elements (depends on functionality).
__base Base value for reduction.
__output Pointer to position where final result is written to
__bound Maximum number of elements processed (e. g. for
std::count_n()).
Returns:
User-supplied functor (that may contain a part
of the result).
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > _Op __gnu_parallel::__for_each_template_random_access_omp_loop_static (_RAIter__begin, _RAIter__end, _Op__o, _Fu &__f, _Red__r, _Result__base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type__bound)¶
Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling. Parameters:__begin Begin iterator of element
sequence.
__end End iterator of element sequence.
__o User-supplied functor (comparator, predicate, adding functor, ...).
__f Functor to process an element with __op (depends on desired
functionality, e. g. for std::for_each(), ...).
__r Functor to add a single __result to the already processed
__elements (depends on functionality).
__base Base value for reduction.
__output Pointer to position where final result is written to
__bound Maximum number of elements processed (e. g. for
std::count_n()).
Returns:
User-supplied functor (that may contain a part
of the result).
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > _Op __gnu_parallel::__for_each_template_random_access_workstealing (_RAIter__begin, _RAIter__end, _Op__op, _Fu &__f, _Red__r, _Result__base, _Result &__output, typename std::iterator_traits< _RAIter >::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:__begin Begin iterator of element
sequence.
__end End iterator of element sequence.
__op User-supplied functor (comparator, predicate, adding functor, ...).
__f Functor to process an element with __op (depends on desired
functionality, e. g. for std::for_each(), ...).
__r Functor to add a single __result to the already processed
elements (depends on functionality).
__base Base value for reduction.
__output Pointer to position where final result is written to
__bound Maximum number of elements processed (e. g. for
std::count_n()).
Returns:
User-supplied functor (that may contain a part
of the result).
template<typename _IIter , typename _Compare > bool __gnu_parallel::__is_sorted (_IIter__begin, _IIter__end, _Compare__comp)¶
Check whether [__begin, __end) is sorted according to __comp. Parameters:__begin Begin iterator of sequence.
__end End iterator of sequence.
__comp Comparator.
Returns:
true if sorted, false otherwise.
template<typename _RAIter , typename _Compare > _RAIter __gnu_parallel::__median_of_three_iterators (_RAIter__a, _RAIter__b, _RAIter__c, _Compare__comp)¶
Compute the median of three referenced elements, according to __comp. Parameters:__a First iterator.
__b Second iterator.
__c Third iterator.
__comp Comparator.
template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare > _OutputIterator __gnu_parallel::__merge_advance (_RAIter1 &__begin1, _RAIter1__end1, _RAIter2 &__begin2, _RAIter2__end2, _OutputIterator__target, _DifferenceTp__max_length, _Compare__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:__begin1 Begin iterator of first
sequence.
__end1 End iterator of first sequence.
__begin2 Begin iterator of second sequence.
__end2 End iterator of second sequence.
__target Target begin iterator.
__max_length Maximum number of elements to merge.
__comp Comparator.
Returns:
Output end iterator.
template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare > _OutputIterator __gnu_parallel::__merge_advance_movc (_RAIter1 &__begin1, _RAIter1__end1, _RAIter2 &__begin2, _RAIter2__end2, _OutputIterator__target, _DifferenceTp__max_length, _Compare__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:__begin1 Begin iterator of first
sequence.
__end1 End iterator of first sequence.
__begin2 Begin iterator of second sequence.
__end2 End iterator of second sequence.
__target Target begin iterator.
__max_length Maximum number of elements to merge.
__comp Comparator.
Returns:
Output end iterator.
template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare > _OutputIterator __gnu_parallel::__merge_advance_usual (_RAIter1 &__begin1, _RAIter1__end1, _RAIter2 &__begin2, _RAIter2__end2, _OutputIterator__target, _DifferenceTp__max_length, _Compare__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:__begin1 Begin iterator of first
sequence.
__end1 End iterator of first sequence.
__begin2 Begin iterator of second sequence.
__end2 End iterator of second sequence.
__target Target begin iterator.
__max_length Maximum number of elements to merge.
__comp Comparator.
Returns:
Output end iterator.
template<typename _RAIter1 , typename _RAIter2 , typename _RAIter3 , typename _Compare > _RAIter3 __gnu_parallel::__parallel_merge_advance (_RAIter1 &__begin1, _RAIter1__end1, _RAIter2 &__begin2, _RAIter2__end2, _RAIter3__target, typename std::iterator_traits< _RAIter1 >::difference_type__max_length, _Compare__comp) [inline]¶
Merge routine fallback to sequential in case the iterators of the two input sequences are of different type. Parameters:__begin1 Begin iterator of first
sequence.
__end1 End iterator of first sequence.
__begin2 Begin iterator of second sequence.
__end2 End iterator of second sequence.
__target Target begin iterator.
__max_length Maximum number of elements to merge.
__comp Comparator.
Returns:
Output end iterator.
template<typename _RAIter1 , typename _RAIter3 , typename _Compare > _RAIter3 __gnu_parallel::__parallel_merge_advance (_RAIter1 &__begin1, _RAIter1__end1, _RAIter1 &__begin2, _RAIter1__end2, _RAIter3__target, typename std::iterator_traits< _RAIter1 >::difference_type__max_length, _Compare__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:__begin1 Begin iterator of first
sequence.
__end1 End iterator of first sequence.
__begin2 Begin iterator of second sequence.
__end2 End iterator of second sequence.
__target Target begin iterator.
__max_length Maximum number of elements to merge.
__comp Comparator.
Returns:
Output end iterator.
template<typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_nth_element (_RAIter__begin, _RAIter__nth, _RAIter__end, _Compare__comp)¶
Parallel implementation of std::nth_element(). Parameters:__begin Begin iterator of input
sequence.
__nth _Iterator of element that must be in position afterwards.
__end End iterator of input sequence.
__comp Comparator.
template<typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_partial_sort (_RAIter__begin, _RAIter__middle, _RAIter__end, _Compare__comp)¶
Parallel implementation of std::partial_sort(). Parameters:__begin Begin iterator of input
sequence.
__middle Sort until this position.
__end End iterator of input sequence.
__comp Comparator.
template<typename _IIter , typename _OutputIterator , typename _BinaryOperation > _OutputIterator __gnu_parallel::__parallel_partial_sum (_IIter__begin, _IIter__end, _OutputIterator__result, _BinaryOperation__bin_op)¶
Parallel partial sum front-__end. Parameters:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__result Begin iterator of output sequence.
__bin_op Associative binary function.
Returns:
End iterator of output sequence.
template<typename _IIter , typename _OutputIterator , typename _BinaryOperation > _OutputIterator __gnu_parallel::__parallel_partial_sum_basecase (_IIter__begin, _IIter__end, _OutputIterator__result, _BinaryOperation__bin_op, typename std::iterator_traits< _IIter >::value_type__value)¶
Base case prefix sum routine. Parameters:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__result Begin iterator of output sequence.
__bin_op Associative binary function.
__value Start value. Must be passed since the neutral element is unknown
in general.
Returns:
End iterator of output sequence.
template<typename _IIter , typename _OutputIterator , typename _BinaryOperation > _OutputIterator __gnu_parallel::__parallel_partial_sum_linear (_IIter__begin, _IIter__end, _OutputIterator__result, _BinaryOperation__bin_op, typename std::iterator_traits< _IIter >::difference_type__n)¶
Parallel partial sum implementation, two-phase approach, no recursion. Parameters:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__result Begin iterator of output sequence.
__bin_op Associative binary function.
__n Length of sequence.
Returns:
End iterator of output sequence.
template<typename _RAIter , typename _Predicate > std::iterator_traits<_RAIter>::difference_type __gnu_parallel::__parallel_partition (_RAIter__begin, _RAIter__end, _Predicate__pred, _ThreadIndex__num_threads)¶
Parallel implementation of std::partition. Parameters:__begin Begin iterator of input
sequence to split.
__end End iterator of input sequence to split.
__pred Partition predicate, possibly including some kind of pivot.
__num_threads Maximum number of threads to use for this task.
Returns:
Number of elements not fulfilling the
predicate.
template<typename _RAIter , typename _RandomNumberGenerator > void __gnu_parallel::__parallel_random_shuffle (_RAIter__begin, _RAIter__end, _RandomNumberGenerator__rng = _RandomNumber()) [inline]¶
Parallel random public call. Parameters:__begin Begin iterator of sequence.
__end End iterator of sequence.
__rng Random number generator to use.
template<typename _RAIter , typename _RandomNumberGenerator > void __gnu_parallel::__parallel_random_shuffle_drs (_RAIter__begin, _RAIter__end, typename std::iterator_traits< _RAIter >::difference_type__n, _ThreadIndex__num_threads, _RandomNumberGenerator &__rng)¶
Main parallel random shuffle step. Parameters:__begin Begin iterator of sequence.
__end End iterator of sequence.
__n Length of sequence.
__num_threads Number of threads to use.
__rng Random number generator to use.
template<typename _RAIter , typename _RandomNumberGenerator > void __gnu_parallel::__parallel_random_shuffle_drs_pu (_DRSSorterPU< _RAIter, _RandomNumberGenerator > *__pus)¶
Random shuffle code executed by each thread. Parameters:__pus Array of thread-local data
records.
template<bool __stable, typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_sort (_RAIter__begin, _RAIter__end, _Compare__comp, multiway_mergesort_tag__parallelism) [inline]¶
Choose multiway mergesort, splitting variant at run-time, for parallel sorting. Parameters:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__comp Comparator.
Template Parameters:
__stable Sort stable.
template<bool __stable, typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_sort (_RAIter__begin, _RAIter__end, _Compare__comp, multiway_mergesort_exact_tag__parallelism) [inline]¶
Choose multiway mergesort with exact splitting, for parallel sorting. Parameters:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__comp Comparator.
Template Parameters:
__stable Sort stable.
template<bool __stable, typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_sort (_RAIter__begin, _RAIter__end, _Compare__comp, multiway_mergesort_sampling_tag__parallelism) [inline]¶
Choose multiway mergesort with splitting by sampling, for parallel sorting. Parameters:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__comp Comparator.
Template Parameters:
__stable Sort stable.
template<bool __stable, typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_sort (_RAIter__begin, _RAIter__end, _Compare__comp, quicksort_tag__parallelism) [inline]¶
Choose quicksort for parallel sorting. Parameters:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__comp Comparator.
Template Parameters:
__stable Sort stable.
template<bool __stable, typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_sort (_RAIter__begin, _RAIter__end, _Compare__comp, balanced_quicksort_tag__parallelism) [inline]¶
Choose balanced quicksort for parallel sorting. Parameters:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__comp Comparator.
Template Parameters:
__stable Sort stable.
template<bool __stable, typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_sort (_RAIter__begin, _RAIter__end, _Compare__comp, default_parallel_tag__parallelism) [inline]¶
Choose multiway mergesort with exact splitting, for parallel sorting. Parameters:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__comp Comparator.
Template Parameters:
__stable Sort stable.
template<bool __stable, typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_sort (_RAIter__begin, _RAIter__end, _Compare__comp, parallel_tag__parallelism) [inline]¶
Choose a parallel sorting algorithm. Parameters:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__comp Comparator.
Template Parameters:
__stable Sort stable.
template<typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_sort_qs (_RAIter__begin, _RAIter__end, _Compare__comp, _ThreadIndex__num_threads)¶
Unbalanced quicksort main call. Parameters:__begin Begin iterator of input
sequence.
__end End iterator input sequence, ignored.
__comp Comparator.
__num_threads Number of threads that are allowed to work on this
part.
template<typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_sort_qs_conquer (_RAIter__begin, _RAIter__end, _Compare__comp, _ThreadIndex__num_threads)¶
Unbalanced quicksort conquer step. Parameters:__begin Begin iterator of subsequence.
__end End iterator of subsequence.
__comp Comparator.
__num_threads Number of threads that are allowed to work on this
part.
template<typename _RAIter , typename _Compare > std::iterator_traits<_RAIter>::difference_type __gnu_parallel::__parallel_sort_qs_divide (_RAIter__begin, _RAIter__end, _Compare__comp, typename std::iterator_traits< _RAIter >::difference_type__pivot_rank, typename std::iterator_traits< _RAIter >::difference_type__num_samples, _ThreadIndex__num_threads)¶
Unbalanced quicksort divide step. Parameters:__begin Begin iterator of subsequence.
__end End iterator of subsequence.
__comp Comparator.
__pivot_rank Desired __rank of the pivot.
__num_samples Choose pivot from that many samples.
__num_threads Number of threads that are allowed to work on this
part.
template<typename _RAIter , typename _Compare > void __gnu_parallel::__parallel_sort_qsb (_RAIter__begin, _RAIter__end, _Compare__comp, _ThreadIndex__num_threads)¶
Top-level quicksort routine. Parameters:__begin Begin iterator of sequence.
__end End iterator of sequence.
__comp Comparator.
__num_threads Number of threads that are allowed to work on this
part.
template<typename _IIter , class _OutputIterator , class _BinaryPredicate > _OutputIterator __gnu_parallel::__parallel_unique_copy (_IIter__first, _IIter__last, _OutputIterator__result, _BinaryPredicate__binary_pred)¶
Parallel std::unique_copy(), w/__o explicit equality predicate. Parameters:__first Begin iterator of input
sequence.
__last End iterator of input sequence.
__result Begin iterator of result __sequence.
__binary_pred Equality predicate.
Returns:
End iterator of result __sequence.
template<typename _IIter , class _OutputIterator > _OutputIterator __gnu_parallel::__parallel_unique_copy (_IIter__first, _IIter__last, _OutputIterator__result) [inline]¶
Parallel std::unique_copy(), without explicit equality predicate. Parameters:__first Begin iterator of input
sequence.
__last End iterator of input sequence.
__result Begin iterator of result __sequence.
Returns:
End iterator of result __sequence.
template<typename _RAIter , typename _Compare > void __gnu_parallel::__qsb_conquer (_QSBThreadLocal< _RAIter > **__tls, _RAIter__begin, _RAIter__end, _Compare__comp, _ThreadIndex__iam, _ThreadIndex__num_threads, bool__parent_wait)¶
Quicksort conquer step. Parameters:__tls Array of thread-local storages.
__begin Begin iterator of subsequence.
__end End iterator of subsequence.
__comp Comparator.
__iam Number of the thread processing this function.
__num_threads Number of threads that are allowed to work on this
part.
template<typename _RAIter , typename _Compare > std::iterator_traits<_RAIter>::difference_type __gnu_parallel::__qsb_divide (_RAIter__begin, _RAIter__end, _Compare__comp, _ThreadIndex__num_threads)¶
Balanced quicksort divide step. Parameters:__begin Begin iterator of subsequence.
__end End iterator of subsequence.
__comp Comparator.
__num_threads Number of threads that are allowed to work on this
part.
Precondition:
(__end-__begin)>=1
template<typename _RAIter , typename _Compare > void __gnu_parallel::__qsb_local_sort_with_helping (_QSBThreadLocal< _RAIter > **__tls, _Compare &__comp, _ThreadIndex__iam, bool__wait)¶
Quicksort step doing load-balanced local sort. Parameters:__tls Array of thread-local storages.
__comp Comparator.
__iam Number of the thread processing this function.
template<typename _RandomNumberGenerator > int __gnu_parallel::__random_number_pow2 (int__logp, _RandomNumberGenerator &__rng) [inline]¶
Generate a random number in [0,2^__logp). Parameters:__logp Logarithm (basis 2) of the upper
range __bound.
__rng Random number generator to use.
template<typename _Size > _Size __gnu_parallel::__rd_log2 (_Size__n) [inline]¶
Calculates the rounded-down logarithm of __n for base 2. Parameters:__n Argument.
Returns:
Returns 0 for any argument <1.
template<typename _Tp > _Tp __gnu_parallel::__round_up_to_pow2 (_Tp__x)¶
Round up to the next greater power of 2. Parameters:__x _Integer to round up
template<typename __RAIter1 , typename __RAIter2 , typename _Pred > __RAIter1 __gnu_parallel::__search_template (__RAIter1__begin1, __RAIter1__end1, __RAIter2__begin2, __RAIter2__end2, _Pred__pred)¶
Parallel std::search. Parameters:__begin1 Begin iterator of first
sequence.
__end1 End iterator of first sequence.
__begin2 Begin iterator of second sequence.
__end2 End iterator of second sequence.
__pred Find predicate.
Returns:
Place of finding in first sequences.
template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 __gnu_parallel::__sequential_multiway_merge (_RAIterIterator__seqs_begin, _RAIterIterator__seqs_end, _RAIter3__target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp__length, _Compare__comp)¶
Sequential multi-way merging switch. The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings. Parameters:__seqs_begin Begin iterator of iterator
pair input sequence.
__seqs_end End iterator of iterator pair input sequence.
__target Begin iterator of output sequence.
__comp Comparator.
__length Maximum length to merge, possibly larger than the number of
elements available.
__sentinel The sequences have __a __sentinel element.
Returns:
End iterator of output sequence.
template<typename _RAIter , typename _RandomNumberGenerator > void __gnu_parallel::__sequential_random_shuffle (_RAIter__begin, _RAIter__end, _RandomNumberGenerator &__rng)¶
Sequential cache-efficient random shuffle. Parameters:__begin Begin iterator of sequence.
__end End iterator of sequence.
__rng Random number generator to use.
template<typename _IIter > void __gnu_parallel::__shrink (std::vector< _IIter > &__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_starts Start positions worked on
(oversampled).
__count_to_two Counts up to 2.
__range_length Current length of a chunk.
template<typename _IIter > void __gnu_parallel::__shrink_and_double ( std::vector< _IIter > &__os_starts, size_t &__count_to_two, size_t &__range_length, const bool__make_twice)¶
Shrinks and doubles the ranges. Parameters:__os_starts Start positions worked on
(oversampled).
__count_to_two Counts up to 2.
__range_length Current length of a chunk.
__make_twice Whether the __os_starts is allowed to be grown or not
void __gnu_parallel::__yield () [inline]¶
Yield the control to another thread, without waiting for the end to the time slice. Definition at line 360 of file parallel/compatibility.h. Referenced by __for_each_template_random_access_workstealing(), and __qsb_local_sort_with_helping().template<typename _IIter , typename _FunctorType > size_t __gnu_parallel::list_partition (const _IIter__begin, const _IIter__end, _IIter *__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:__begin Begin iterator of input
sequence.
__end End iterator of input sequence.
__starts Start iterators for the resulting parts, dimension
__num_parts+1. For convenience, __starts [__num_parts] contains the end
iterator of the sequence.
__lengths Length of the resulting parts.
__num_parts Number of parts to split the sequence into.
__f Functor to be applied to each element by traversing __it
__oversampling Oversampling factor. If 0, then the partitions will differ
in at most {{__end} - {__begin}} __elements. Otherwise, the ratio between the
longest and the shortest part is bounded by 1/({__oversampling}
{num_parts})
Returns:
Length of the whole sequence.
template<typename _Tp > const _Tp& __gnu_parallel::max (const _Tp &__a, const _Tp &__b) [inline]¶
Equivalent to std::max. Definition at line 150 of file parallel/base.h.template<typename _Tp > const _Tp& __gnu_parallel::min (const _Tp &__a, const _Tp &__b) [inline]¶
Equivalent to std::min. Definition at line 144 of file parallel/base.h. Referenced by __for_each_template_random_access_workstealing().template<typename _RanSeqs , typename _RankType , typename _RankIterator , typename _Compare > void __gnu_parallel::multiseq_partition (_RanSeqs__begin_seqs, _RanSeqs__end_seqs, _RankType__rank, _RankIterator__begin_offsets, _Compare__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_seqs Begin of the sequence of
iterator pairs.
__end_seqs End of the sequence of iterator pairs.
__rank The global rank to partition at.
__begin_offsets A 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.
__comp The ordering functor, defaults to std::less<_Tp>.
template<typename _Tp , typename _RanSeqs , typename _RankType , typename _Compare > _Tp __gnu_parallel::multiseq_selection (_RanSeqs__begin_seqs, _RanSeqs__end_seqs, _RankType__rank, _RankType &__offset, _Compare__comp = std::less<_Tp>())¶
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_seqs Begin of the sequence of
iterator pairs.
__end_seqs End of the sequence of iterator pairs.
__rank The global rank to partition at.
__offset The 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.
__comp The ordering functor, defaults to std::less.
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut __gnu_parallel::multiway_merge (_RAIterPairIterator__seqs_begin, _RAIterPairIterator__seqs_end, _RAIterOut__target, _DifferenceTp__length, _Compare__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 _M_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
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).
Template Parameters:
_RAIterPairIterator iterator over
sequence of pairs of iterators
_RAIterOut iterator over target sequence
_DifferenceTp difference type for the sequence
_Compare strict weak ordering type to compare elements in sequences
Parameters:
__seqs_begin __begin of sequence
__sequence
__seqs_end _M_end of sequence __sequence
__target target sequence to merge to.
__comp strict weak ordering to use for element comparison.
__length Maximum length to merge, possibly larger than the number of
elements available.
Returns:
_M_end iterator of output sequence
template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 __gnu_parallel::multiway_merge_3_variant (_RAIterIterator__seqs_begin, _RAIterIterator__seqs_end, _RAIter3__target, _DifferenceTp__length, _Compare__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 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_begin Begin iterator of iterator
pair input sequence.
__seqs_end End iterator of iterator pair input sequence.
__target Begin iterator of output sequence.
__comp Comparator.
__length Maximum length to merge, less equal than the total number of
elements available.
Returns:
End iterator of output sequence.
template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 __gnu_parallel::multiway_merge_4_variant (_RAIterIterator__seqs_begin, _RAIterIterator__seqs_end, _RAIter3__target, _DifferenceTp__length, _Compare__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 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_begin Begin iterator of iterator
pair input sequence.
__seqs_end End iterator of iterator pair input sequence.
__target Begin iterator of output sequence.
__comp Comparator.
__length Maximum length to merge, less equal than the total number of
elements available.
Returns:
End iterator of output sequence.
template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType > void __gnu_parallel::multiway_merge_exact_splitting (_RAIterIterator__seqs_begin, _RAIterIterator__seqs_end, _DifferenceType__length, _DifferenceType__total_length, _Compare__comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces)¶
Exact splitting for parallel multiway-merge routine. None of the passed sequences may be empty. Definition at line 1120 of file multiway_merge.h. References __equally_split(), _GLIBCXX_PARALLEL_LENGTH, std::vector< _Tp, _Alloc >::begin(), std::vector< _Tp, _Alloc >::end(), multiseq_partition(), and std::vector< _Tp, _Alloc >::resize(). Referenced by __parallel_merge_advance().template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 __gnu_parallel::multiway_merge_loser_tree (_RAIterIterator__seqs_begin, _RAIterIterator__seqs_end, _RAIter3__target, _DifferenceTp__length, _Compare__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_begin Begin iterator of iterator
pair input sequence.
__seqs_end End iterator of iterator pair input sequence.
__target Begin iterator of output sequence.
__comp Comparator.
__length Maximum length to merge, less equal than the total number of
elements available.
Returns:
End iterator of output sequence.
template<typename UnguardedLoserTree , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 __gnu_parallel::multiway_merge_loser_tree_sentinel (_RAIterIterator__seqs_begin, _RAIterIterator__seqs_end, _RAIter3__target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp__length, _Compare__comp)¶
Multi-way merging procedure for a high branching factor, requiring sentinels to exist. Template Parameters:UnguardedLoserTree _Loser Tree variant
to use for the unguarded merging.
Parameters:
__seqs_begin Begin iterator of iterator
pair input sequence.
__seqs_end End iterator of iterator pair input sequence.
__target Begin iterator of output sequence.
__comp Comparator.
__length Maximum length to merge, less equal than the total number of
elements available.
Returns:
End iterator of output sequence.
template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 __gnu_parallel::multiway_merge_loser_tree_unguarded (_RAIterIterator__seqs_begin, _RAIterIterator__seqs_end, _RAIter3__target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp__length, _Compare__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_begin Begin iterator of iterator
pair input sequence.
__seqs_end End iterator of iterator pair input sequence.
__target Begin iterator of output sequence.
__comp Comparator.
__length Maximum length to merge, less equal than the total number of
elements available.
Returns:
End iterator of output sequence.
template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType > void __gnu_parallel::multiway_merge_sampling_splitting (_RAIterIterator__seqs_begin, _RAIterIterator__seqs_end, _DifferenceType__length, _DifferenceType__total_length, _Compare__comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces)¶
Sampling based splitting for parallel multiway-merge routine. Definition at line 1035 of file multiway_merge.h. References _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::merge_oversampling.template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut __gnu_parallel::multiway_merge_sentinels (_RAIterPairIterator__seqs_begin, _RAIterPairIterator__seqs_end, _RAIterOut__target, _DifferenceTp__length, _Compare__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 _M_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
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
Template Parameters:
_RAIterPairIterator iterator over
sequence of pairs of iterators
_RAIterOut iterator over target sequence
_DifferenceTp difference type for the sequence
_Compare strict weak ordering type to compare elements in sequences
Parameters:
__seqs_begin __begin of sequence
__sequence
__seqs_end _M_end of sequence __sequence
__target target sequence to merge to.
__comp strict weak ordering to use for element comparison.
__length Maximum length to merge, possibly larger than the number of
elements available.
Returns:
_M_end iterator of output sequence
template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Splitter , typename _Compare > _RAIter3 __gnu_parallel::parallel_multiway_merge (_RAIterIterator__seqs_begin, _RAIterIterator__seqs_end, _RAIter3__target, _Splitter__splitter, _DifferenceTp__length, _Compare__comp, _ThreadIndex__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. Template Parameters:_Splitter functor to split input
(either __exact or sampling based)
__stable Stable merging incurs a performance penalty.
__sentinel Ignored.
Parameters:
__seqs_begin Begin iterator of iterator
pair input sequence.
__seqs_end End iterator of iterator pair input sequence.
__target Begin iterator of output sequence.
__comp Comparator.
__length Maximum length to merge, possibly larger than the number of
elements available.
Returns:
End iterator of output sequence.
template<bool __stable, bool __exact, typename _RAIter , typename _Compare > void __gnu_parallel::parallel_sort_mwms (_RAIter__begin, _RAIter__end, _Compare__comp, _ThreadIndex__num_threads)¶
PMWMS main call. Parameters:__begin Begin iterator of sequence.
__end End iterator of sequence.
__comp Comparator.
__num_threads Number of threads to use.
template<bool __stable, bool __exact, typename _RAIter , typename _Compare > void __gnu_parallel::parallel_sort_mwms_pu (_PMWMSSortingData< _RAIter > *__sd, _Compare &__comp)¶
PMWMS code executed by each thread. Parameters:__sd Pointer to algorithm data.
__comp Comparator.
Variable Documentation¶
const int __gnu_parallel::_CASable_bits [static]¶
Number of bits of _CASable. Definition at line 130 of file types.h. Referenced by __decode2(), and __encode2().const _CASable __gnu_parallel::_CASable_mask [static]¶
_CASable with the right half of bits set to 1. Definition at line 133 of file types.h. Referenced by __decode2().Author¶
Generated automatically by Doxygen for libstdc++ from the source code.Sun Jan 6 2013 | libstdc++ |