libstdc++
__gnu_parallel Namespace Reference

Classes

Typedefs

Enumerations

Functions

Variables


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.

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

Strategies for run-time algorithm selection:

Definition at line 67 of file types.h.

Find algorithms:

Definition at line 106 of file types.h.

Merging algorithms:

Definition at line 85 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 44 of file types.h.

Partial sum algorithms: recursive, linear.

Definition at line 91 of file types.h.

Sorting algorithms:

Definition at line 76 of file types.h.

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:
__elementsBegin iterator of sequence to search for.
__lengthLength of sequence to search for.
__advancesReturned __offsets.

Definition at line 51 of file search.h.

Referenced by __search_template().

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:
__ptrPointer to signed integer.
__comparandCompare value.
__replacementReplacement value.

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

References __compare_and_swap_32(), and __compare_and_swap_64().

Referenced by __parallel_partition(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_front(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_back().

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:
__ptrPointer to 32-bit signed integer.
__comparandCompare value.
__replacementReplacement value.

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

Referenced by __compare_and_swap().

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:
__ptrPointer to 64-bit signed integer.
__comparandCompare value.
__replacementReplacement value.

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

Referenced by __compare_and_swap().

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.
__aFirst integer, to be decoded from the most-significant _CASable_bits/2 bits of __x.
__bSecond integer, to be encoded in the least-significant _CASable_bits/2 bits of __x.
See also:
__encode2

Definition at line 133 of file parallel/base.h.

References _CASable_bits, and _CASable_mask.

Referenced by __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::push_front(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_front(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_back().

template<typename _RAIter , typename _DifferenceTp >
void __gnu_parallel::__determine_samples ( _PMWMSSortingData< _RAIter > *  __sd,
_DifferenceTp  __num_samples 
)

Select _M_samples from a sequence.

Parameters:
__sdPointer to algorithm data. _Result will be placed in __sd->_M_samples.
__num_samplesNumber of _M_samples to select.

Definition at line 97 of file multiway_mergesort.h.

References equally_split(), __gnu_parallel::_PMWMSSortingData::_M_starts, __gnu_parallel::_PMWMSSortingData::_M_samples, and __gnu_parallel::_PMWMSSortingData::_M_source.

_CASable __gnu_parallel::__encode2 ( int  __a,
int  __b 
) [inline]

Encode two integers into one gnu_parallel::_CASable.

Parameters:
__aFirst integer, to be encoded in the most-significant _CASable_bits/2 bits.
__bSecond integer, to be encoded in the least-significant _CASable_bits/2 bits.
Returns:
value encoding __a and __b.
See also:
__decode2

Definition at line 119 of file parallel/base.h.

References _CASable_bits.

Referenced by __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::_RestrictedBoundedConcurrentQueue(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::push_front(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_front(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_back().

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:
__ptrPointer to a signed integer.
__addendValue to add.

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

References __fetch_and_add_32(), and __fetch_and_add_64().

Referenced by __parallel_partition(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::push_front().

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:
__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_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:
__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 _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:
__begin1Begin iterator of first sequence.
__end1End iterator of first sequence.
__begin2Begin iterator of second sequence. Must have same length as first sequence.
__predFind predicate.
__selector_Functionality (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(), and std::make_pair().

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:
__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 parallel_unbalanced, __for_each_template_random_access_ed(), parallel_omp_loop, __for_each_template_random_access_omp_loop(), parallel_omp_loop_static, and __for_each_template_random_access_workstealing().

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:
__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 par_loop.h.

References equally_split_point().

Referenced by __for_each_template_random_access().

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:
__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 _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:
__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 66 of file omp_loop_static.h.

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:
__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::get(), __gnu_parallel::_Settings::cache_line_size, __gnu_debug::__base(), __yield(), and min().

Referenced by __for_each_template_random_access().

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:
__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(), __sequential_multiway_merge(), and parallel_multiway_merge().

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:
__aFirst iterator.
__bSecond iterator.
__cThird iterator.
__compComparator.

Definition at line 398 of file parallel/base.h.

Referenced by __qsb_divide().

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:
__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 171 of file merge.h.

References _GLIBCXX_CALL, and __merge_advance_movc().

Referenced by __parallel_merge_advance(), and __sequential_multiway_merge().

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:
__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 105 of file merge.h.

Referenced by __merge_advance().

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:
__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 _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:
__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 195 of file merge.h.

References __merge_advance().

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:
__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 223 of file merge.h.

References std::make_pair(), parallel_multiway_merge(), and multiway_merge_exact_splitting().

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:
__beginBegin iterator of input sequence.
__nth_Iterator of element that must be in position afterwards.
__endEnd iterator of input sequence.
__compComparator.

Definition at line 332 of file partition.h.

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

Referenced by __parallel_partial_sort().

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:
__beginBegin iterator of input sequence.
__middleSort until this position.
__endEnd iterator of input sequence.
__compComparator.

Definition at line 422 of file partition.h.

References __parallel_nth_element().

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:
__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 206 of file partial_sum.h.

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

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:
__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 _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:
__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 __parallel_partial_sum_basecase(), __gnu_parallel::_Settings::get(), __gnu_parallel::_Settings::partial_sum_dilation, and equally_split().

Referenced by __parallel_partial_sum().

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:
__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 56 of file partition.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), _GLIBCXX_VOLATILE, __gnu_parallel::_Settings::partition_chunk_size, __gnu_parallel::_Settings::partition_chunk_share, __fetch_and_add(), and __compare_and_swap().

Referenced by __qsb_divide(), __parallel_nth_element(), and __parallel_sort_qs_divide().

template<typename _RAIter , typename _RandomNumberGenerator >
void __gnu_parallel::__parallel_random_shuffle ( _RAIter  __begin,
_RAIter  __end,
_RandomNumberGenerator  __rng = _RandomNumber() 
) [inline]

Parallel random public call.

Parameters:
__beginBegin iterator of sequence.
__endEnd iterator of sequence.
__rngRandom number generator to use.

Definition at line 522 of file random_shuffle.h.

References __parallel_random_shuffle_drs().

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 
)
template<typename _RAIter , typename _RandomNumberGenerator >
void __gnu_parallel::__parallel_random_shuffle_drs_pu ( _DRSSorterPU< _RAIter, _RandomNumberGenerator > *  __pus)
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:
__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 _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:
__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 _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:
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__compComparator.

Definition at line 117 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 _RAIter , typename _Compare >
void __gnu_parallel::__parallel_sort ( _RAIter  __begin,
_RAIter  __end,
_Compare  __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 136 of file sort.h.

References _GLIBCXX_CALL, __parallel_sort_qs(), and __gnu_parallel::parallel_tag::__get_num_threads().

Here is the call graph for this function:

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:
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__compComparator.
__stableSort __stable.

Definition at line 157 of file sort.h.

References _GLIBCXX_CALL, __parallel_sort_qsb(), and __gnu_parallel::parallel_tag::__get_num_threads().

Here is the call graph for this function:

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:
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__compComparator.

Definition at line 178 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 _RAIter , typename _Compare >
void __gnu_parallel::__parallel_sort ( _RAIter  __begin,
_RAIter  __end,
_Compare  __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 198 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<typename _RAIter , typename _Compare >
void __gnu_parallel::__parallel_sort_qs ( _RAIter  __begin,
_RAIter  __end,
_Compare  __comp,
_ThreadIndex  __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 154 of file quicksort.h.

References _GLIBCXX_CALL, and __parallel_sort_qs_conquer().

Referenced by __parallel_sort().

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:
__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 __parallel_sort_qs_divide(), and __gnu_parallel::_Settings::get().

Referenced by __parallel_sort_qs().

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:
__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 _RAIter , typename _Compare >
void __gnu_parallel::__parallel_sort_qsb ( _RAIter  __begin,
_RAIter  __end,
_Compare  __comp,
_ThreadIndex  __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 430 of file balanced_quicksort.h.

References _GLIBCXX_CALL, __rd_log2(), __gnu_parallel::_QSBThreadLocal::_M_elements_leftover, std::make_pair(), and __qsb_conquer().

Referenced by __parallel_sort().

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:
__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 50 of file unique_copy.h.

References _GLIBCXX_CALL, and equally_split().

Referenced by __parallel_unique_copy().

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:
__firstBegin iterator of input sequence.
__lastEnd iterator of input sequence.
__resultBegin iterator of result __sequence.
Returns:
End iterator of result __sequence.

Definition at line 186 of file unique_copy.h.

References __parallel_unique_copy().

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:
__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 171 of file balanced_quicksort.h.

References __gnu_parallel::_QSBThreadLocal::_M_initial, __qsb_local_sort_with_helping(), __qsb_divide(), and __gnu_parallel::_QSBThreadLocal::_M_elements_leftover.

Referenced by __parallel_sort_qsb().

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:
__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 _RAIter , typename _Compare >
void __gnu_parallel::__qsb_local_sort_with_helping ( _QSBThreadLocal< _RAIter > **  __tls,
_Compare &  __comp,
_ThreadIndex  __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 _Size >
_Size __gnu_parallel::__rd_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 102 of file parallel/base.h.

Referenced by __parallel_sort_qsb(), __gnu_parallel::_LoserTreeBase< _Tp, _Compare >::_LoserTreeBase(), multiseq_partition(), multiseq_selection(), __round_up_to_pow2(), __parallel_random_shuffle_drs(), and __sequential_random_shuffle().

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

Definition at line 248 of file random_shuffle.h.

References __rd_log2().

Referenced by multiseq_selection(), __parallel_random_shuffle_drs(), and __sequential_random_shuffle().

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:
__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 81 of file search.h.

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

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_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of 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 917 of file multiway_merge.h.

References _GLIBCXX_CALL, __is_sorted(), _GLIBCXX_PARALLEL_LENGTH, and __merge_advance().

Referenced by multiway_merge(), and multiway_merge_sentinels().

template<typename _RAIter , typename _RandomNumberGenerator >
void __gnu_parallel::__sequential_random_shuffle ( _RAIter  __begin,
_RAIter  __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 410 of file random_shuffle.h.

References __gnu_parallel::_Settings::get(), __round_up_to_pow2(), min(), __gnu_parallel::_Settings::TLB_size, __gnu_parallel::_Settings::L2_cache_size, __rd_log2(), and __random_number_pow2().

Referenced by __parallel_random_shuffle_drs().

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_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::size().

Referenced by __shrink_and_double().

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_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 __shrink(), std::vector::resize(), and std::vector::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 354 of file parallel/compatibility.h.

Referenced by __qsb_local_sort_with_helping(), and __for_each_template_random_access_workstealing().

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:
__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 multiway_merge_exact_splitting(), __determine_samples(), __parallel_partial_sum_linear(), __search_template(), and __parallel_unique_copy().

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:
__nNumber of elements
__num_threadsNumber of parts
Returns:
splitting point

Definition at line 74 of file equally_split.h.

Referenced by __for_each_template_random_access_ed().

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:
__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 {{__end} - {__begin}} __elements. Otherwise, the ratio between the longest and the shortest part is bounded by 1/({__oversampling} {num})
Returns:
Length of the whole sequence.

Definition at line 101 of file list_partition.h.

References std::vector::size(), and __shrink_and_double().

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.

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

template<typename _Tp >
const _Tp& __gnu_parallel::min ( const _Tp &  __a,
const _Tp &  __b 
) [inline]
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_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<_Tp>.

Definition at line 124 of file multiseq_selection.h.

References _GLIBCXX_CALL, __gnu_cxx::distance(), std::distance(), max(), __rd_log2(), std::vector::push_back(), std::make_pair(), std::vector::begin(), std::vector::end(), and min().

Referenced by multiway_merge_exact_splitting().

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_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 390 of file multiseq_selection.h.

References _GLIBCXX_CALL, __gnu_cxx::distance(), std::distance(), max(), __rd_log2(), __round_up_to_pow2(), std::vector::push_back(), std::make_pair(), std::vector::begin(), std::vector::end(), and min().

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

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:
_RAIterPairIteratoriterator over sequence of pairs of iterators
_RAIterOutiterator over target sequence
_DifferenceTpdifference type for the sequence
_Comparestrict weak ordering type to compare elements in sequences
__seqs_begin__begin of sequence __sequence
__seqs_end_M_end 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:
_M_end iterator of output sequence

Definition at line 1415 of file multiway_merge.h.

References _GLIBCXX_CALL, and __sequential_multiway_merge().

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_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of 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 234 of file multiway_merge.h.

References _GLIBCXX_CALL.

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_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of 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 353 of file multiway_merge.h.

References _GLIBCXX_CALL.

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 1117 of file multiway_merge.h.

References std::vector::begin(), equally_split(), std::vector::resize(), multiseq_partition(), std::vector::end(), and _GLIBCXX_PARALLEL_LENGTH.

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_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of 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 484 of file multiway_merge.h.

References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_LENGTH.

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.

Parameters:
__stableThe value must the same as for the used LoserTrees.
UnguardedLoserTree_Loser Tree variant to use for the unguarded merging.
GuardedLoserTree_Loser 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 of 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 658 of file multiway_merge.h.

References _GLIBCXX_CALL, and __is_sorted().

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_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of 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 567 of file multiway_merge.h.

References _GLIBCXX_CALL.

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 1032 of file multiway_merge.h.

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

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

You have to take care that the element the _M_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:
_RAIterPairIteratoriterator over sequence of pairs of iterators
_RAIterOutiterator over target sequence
_DifferenceTpdifference type for the sequence
_Comparestrict weak ordering type to compare elements in sequences
__seqs_begin__begin of sequence __sequence
__seqs_end_M_end 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:
_M_end iterator of output sequence

Definition at line 1779 of file multiway_merge.h.

References _GLIBCXX_CALL, and __sequential_multiway_merge().

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.

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 of 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 1222 of file multiway_merge.h.

References _GLIBCXX_CALL, _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), __gnu_parallel::_Settings::merge_oversampling, std::make_pair(), and __is_sorted().

Referenced by __parallel_merge_advance().

template<bool __stable, bool __exact, typename _RAIter , typename _Compare >
void __gnu_parallel::parallel_sort_mwms ( _RAIter  __begin,
_RAIter  __end,
_Compare  __comp,
_ThreadIndex  __num_threads 
)
template<bool __stable, bool __exact, typename _RAIter , typename _Compare >
void __gnu_parallel::parallel_sort_mwms_pu ( _PMWMSSortingData< _RAIter > *  __sd,
_Compare &  __comp 
)

Variable Documentation

const int __gnu_parallel::_CASable_bits [static]

Number of bits of _CASable.

Definition at line 130 of file types.h.

Referenced by __encode2(), and __decode2().

_CASable with the right half of bits set to 1.

Definition at line 133 of file types.h.

Referenced by __decode2().