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.
Referenced by __search_template().
template<typename_Tp>bool__gnu_parallel::__compare_and_swap(volatile_Tp*__ptr,_Tp__comparand,_Tp__replacement)[inline]
Compare-and-swap. Compare *__ptr and __comparand. If equal, let *__ptr=__replacement and return true,
return false otherwise.
Parameters__ptr Pointer to signed integer.
__comparand Compare value.
__replacement Replacement value.
Referenced by __parallel_partition(), __gnu_parallel::_RestrictedBoundedConcurrentQueue<_Tp>::pop_back(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue<_Tp>::pop_front().
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.
Seealso
__encode2
References _CASable_bits, and _CASable_mask.
Referenced by __gnu_parallel::_RestrictedBoundedConcurrentQueue<_Tp>::pop_back(),
__gnu_parallel::_RestrictedBoundedConcurrentQueue<_Tp>::pop_front(), and
__gnu_parallel::_RestrictedBoundedConcurrentQueue<_Tp>::push_front().
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.
References __equally_split(), __gnu_parallel::_PMWMSSortingData<_RAIter>::_M_samples,
__gnu_parallel::_PMWMSSortingData<_RAIter>::_M_source, and __gnu_parallel::_PMWMSSortingData<_RAIter>::_M_starts.
_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.
Seealso
__decode2
References _CASable_bits.
Referenced by __gnu_parallel::_RestrictedBoundedConcurrentQueue<_Tp>::_RestrictedBoundedConcurrentQueue(), __gnu_parallel::_RestrictedBoundedConcurrentQueue<_Tp>::pop_back(), __gnu_parallel::_RestrictedBoundedConcurrentQueue<_Tp>::pop_front(), and
__gnu_parallel::_RestrictedBoundedConcurrentQueue<_Tp>::push_front().
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
Referenced by __determine_samples(), __find_template(), __parallel_partial_sum_linear(),
__parallel_unique_copy(), __search_template(), and multiway_merge_exact_splitting().
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
Referenced by __for_each_template_random_access_ed().
template<typename_Tp>_Tp__gnu_parallel::__fetch_and_add(volatile_Tp*__ptr,_Tp__addend)[inline]
Add a value to a variable, atomically.
Parameters__ptr Pointer to a signed integer.
__addend Value to add.
Referenced by __parallel_partition(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue<_Tp>::push_front().
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.
References __find_template(), and __gnu_parallel::_Settings::get().
Referenced by __find_template().
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.
Seealso
__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.
References _GLIBCXX_CALL, __gnu_parallel::_Settings::find_initial_block_size,
__gnu_parallel::_Settings::find_sequential_search_size, and __gnu_parallel::_Settings::get().
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.
References __equally_split(), and _GLIBCXX_CALL.
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.
Seealso
__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.
References _GLIBCXX_CALL, __gnu_parallel::_Settings::find_scale_factor,
__gnu_parallel::_Settings::find_sequential_search_size, and __gnu_parallel::_Settings::get().
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,typenamestd::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
References __for_each_template_random_access_ed(), __for_each_template_random_access_omp_loop(),
__for_each_template_random_access_workstealing(), parallel_omp_loop, parallel_omp_loop_static, and
parallel_unbalanced.
template<typename_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,typenamestd::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).
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,typenamestd::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).
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,typenamestd::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,typenamestd::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).
References __yield(), _GLIBCXX_CALL, __gnu_parallel::_Job<_DifferenceTp>::_M_first,
__gnu_parallel::_Job<_DifferenceTp>::_M_last, __gnu_parallel::_Job<_DifferenceTp>::_M_load,
__gnu_parallel::_Settings::cache_line_size, __gnu_parallel::_Settings::get(), 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__begin Begin iterator of sequence.
__end End iterator of sequence.
__comp Comparator.
Returns
true if sorted, false otherwise.
Referenced by __sequential_multiway_merge(), multiway_merge_loser_tree_sentinel(), 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__a First iterator.
__b Second iterator.
__c Third iterator.
__comp Comparator.
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__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.
References __merge_advance_movc(), and _GLIBCXX_CALL.
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__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.
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__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,typenamestd::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.
References multiway_merge_exact_splitting(), and parallel_multiway_merge().
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,typenamestd::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.
References __merge_advance().
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.
References __parallel_partition(), _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), std::max(),
__gnu_parallel::_Settings::nth_element_minimal_n, and __gnu_parallel::_Settings::partition_minimal_n.
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__begin Begin iterator of input sequence.
__middle Sort until this position.
__end End iterator of input sequence.
__comp Comparator.
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__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.
References __parallel_partial_sum_linear(), _GLIBCXX_CALL, and __gnu_parallel::_Settings::get().
template<typename_IIter,typename_OutputIterator,typename_BinaryOperation>_OutputIterator__gnu_parallel::__parallel_partial_sum_basecase(_IIter__begin,_IIter__end,_OutputIterator__result,_BinaryOperation__bin_op,typenamestd::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.
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,typenamestd::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.
References __equally_split(), __parallel_partial_sum_basecase(), __gnu_parallel::_Settings::get(), and
__gnu_parallel::_Settings::partial_sum_dilation.
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__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.
References __compare_and_swap(), __fetch_and_add(), _GLIBCXX_CALL, _GLIBCXX_VOLATILE,
__gnu_parallel::_Settings::get(), __gnu_parallel::_Settings::partition_chunk_share, and
__gnu_parallel::_Settings::partition_chunk_size.
Referenced by __parallel_nth_element(), __parallel_sort_qs_divide(), and __qsb_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__begin Begin iterator of sequence.
__end End iterator of sequence.
__rng Random number generator to use.
References __parallel_random_shuffle_drs().
template<typename_RAIter,typename_RandomNumberGenerator>void__gnu_parallel::__parallel_random_shuffle_drs(_RAIter__begin,_RAIter__end,typenamestd::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.
References __gnu_parallel::_DRSSorterPU<_RAIter,_RandomNumberGenerator>::__bins_end,
__parallel_random_shuffle_drs_pu(), __rd_log2(), __round_up_to_pow2(), __sequential_random_shuffle(),
_GLIBCXX_CALL, __gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_bin_proc,
__gnu_parallel::_DRSSorterPU<_RAIter,_RandomNumberGenerator>::_M_bins_begin,
__gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_dist,
__gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_num_bins,
__gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_num_bits, __gnu_parallel::_DRSSorterPU<_RAIter,_RandomNumberGenerator>::_M_num_threads, __gnu_parallel::_DRSSorterPU<_RAIter,_RandomNumberGenerator>::_M_sd, __gnu_parallel::_DRSSorterPU<_RAIter,_RandomNumberGenerator>::_M_seed, __gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_starts,
__gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_temporaries, __gnu_parallel::_Settings::get(),
__gnu_parallel::_Settings::L2_cache_size, std::min(), and __gnu_parallel::_Settings::TLB_size.
Referenced by __parallel_random_shuffle().
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.
References __gnu_parallel::_DRSSorterPU<_RAIter,_RandomNumberGenerator>::__bins_end,
__random_number_pow2(), __sequential_random_shuffle(), __gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_bin_proc, __gnu_parallel::_DRSSorterPU<_RAIter,_RandomNumberGenerator>::_M_bins_begin,
__gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_dist,
__gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_num_bins,
__gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_num_bits, __gnu_parallel::_DRSSorterPU<_RAIter,_RandomNumberGenerator>::_M_num_threads, __gnu_parallel::_DRSSorterPU<_RAIter,_RandomNumberGenerator>::_M_sd, __gnu_parallel::_DRSSorterPU<_RAIter,_RandomNumberGenerator>::_M_seed, __gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_source,
__gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_starts,
__gnu_parallel::_DRandomShufflingGlobalData<_RAIter>::_M_temporaries, and std::partial_sum().
Referenced by __parallel_random_shuffle_drs().
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.
TemplateParameters__stable Sort stable.
References __gnu_parallel::parallel_tag::__get_num_threads(), __parallel_sort_qsb(), and _GLIBCXX_CALL.
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.
TemplateParameters__stable Sort stable.
References __gnu_parallel::parallel_tag::__get_num_threads(), and _GLIBCXX_CALL.
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.
TemplateParameters__stable Sort stable.
References __gnu_parallel::parallel_tag::__get_num_threads(), and _GLIBCXX_CALL.
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.
TemplateParameters__stable Sort stable.
References __gnu_parallel::parallel_tag::__get_num_threads(), and _GLIBCXX_CALL.
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.
TemplateParameters__stable Sort stable.
References __gnu_parallel::parallel_tag::__get_num_threads(), _GLIBCXX_CALL, and
__gnu_parallel::_Settings::get().
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.
TemplateParameters__stable Sort stable.
References __gnu_parallel::parallel_tag::__get_num_threads(), __parallel_sort_qs(),
__parallel_sort_qsb(), _GLIBCXX_CALL, and __gnu_parallel::_Settings::get().
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.
TemplateParameters__stable Sort stable.
References __gnu_parallel::parallel_tag::__get_num_threads(), __parallel_sort_qs(), and _GLIBCXX_CALL.
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.
References __parallel_sort_qs_conquer(), and _GLIBCXX_CALL.
Referenced by __parallel_sort(), and __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__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.
References __parallel_sort_qs_conquer(), __parallel_sort_qs_divide(), and
__gnu_parallel::_Settings::get().
Referenced by __parallel_sort_qs(), and __parallel_sort_qs_conquer().
template<typename_RAIter,typename_Compare>std::iterator_traits<_RAIter>::difference_type__gnu_parallel::__parallel_sort_qs_divide(_RAIter__begin,_RAIter__end,_Compare__comp,typenamestd::iterator_traits<_RAIter>::difference_type__pivot_rank,typenamestd::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.
References __parallel_partition(), and std::min().
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__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.
References __qsb_conquer(), __rd_log2(), _GLIBCXX_CALL, and __gnu_parallel::_QSBThreadLocal<_RAIter>::_M_elements_leftover.
Referenced by __parallel_sort(), and __parallel_sort().
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.
References __parallel_unique_copy().
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.
References __equally_split(), and _GLIBCXX_CALL.
Referenced by __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__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.
References __qsb_conquer(), __qsb_divide(), __qsb_local_sort_with_helping(),
__gnu_parallel::_QSBThreadLocal<_RAIter>::_M_elements_leftover, and __gnu_parallel::_QSBThreadLocal<_RAIter>::_M_initial.
Referenced by __parallel_sort_qsb(), and __qsb_conquer().
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
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)
Quicksort step doing load-balanced local sort.
Parameters__tls Array of thread-local storages.
__comp Comparator.
__iam Number of the thread processing this function.
References __yield(), _GLIBCXX_PARALLEL_ASSERTIONS, __gnu_parallel::_QSBThreadLocal<_RAIter>::_M_elements_leftover, __gnu_parallel::_QSBThreadLocal<_RAIter>::_M_initial,
__gnu_parallel::_QSBThreadLocal<_RAIter>::_M_leftover_parts, __gnu_parallel::_QSBThreadLocal<_RAIter>::_M_num_threads, __gnu_parallel::_Settings::get(), and
__gnu_parallel::_Settings::sort_qsb_base_case_maximal_n.
Referenced by __qsb_conquer().
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.
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__n Argument.
Returns
Returns 0 for any argument <1.
Referenced by __gnu_parallel::_LoserTreeBase<_Tp,_Compare>::_LoserTreeBase(),
__parallel_random_shuffle_drs(), __parallel_sort_qsb(), __round_up_to_pow2(),
__sequential_random_shuffle(), multiseq_partition(), and multiseq_selection().
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
References __rd_log2().
Referenced by __parallel_random_shuffle_drs(), __sequential_random_shuffle(), and multiseq_selection().
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.
References __calc_borders(), __equally_split(), _GLIBCXX_CALL, and std::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,consttypenamestd::iterator_traits<typenamestd::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.
References __is_sorted(), __merge_advance(), _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_LENGTH.
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__begin Begin iterator of sequence.
__end End iterator of sequence.
__rng Random number generator to use.
References __random_number_pow2(), __rd_log2(), __round_up_to_pow2(), __sequential_random_shuffle(),
__gnu_parallel::_Settings::get(), __gnu_parallel::_Settings::L2_cache_size, std::min(),
std::partial_sum(), and __gnu_parallel::_Settings::TLB_size.
Referenced by __parallel_random_shuffle_drs(), __parallel_random_shuffle_drs_pu(), and
__sequential_random_shuffle().
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.
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,constbool__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
References __shrink().
Referenced by list_partition().
void__gnu_parallel::__yield()[inline]
Yield control to another thread, without waiting for the end of the time slice.
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,constint__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 $t{thrm{end} -
thrm{begin}}$ elements. Otherwise, the ratio between the longest and the shortest part is bounded by
$1/(thrm{oversampling}
Returns
Length of the whole sequence.
References __shrink_and_double().
template<typename_Tp>const_Tp&__gnu_parallel::max(const_Tp&__a,const_Tp&__b)[inline]
Equivalent to std::max.
template<typename_Tp>const_Tp&__gnu_parallel::min(const_Tp&__a,const_Tp&__b)[inline]
Equivalent to std::min.
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<typenamestd::iterator_traits<typenamestd::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>.
References __rd_log2(), _GLIBCXX_CALL, std::distance(), std::max(), and std::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_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.
References __rd_log2(), __round_up_to_pow2(), _GLIBCXX_CALL, std::distance(), std::max(), and std::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);
Seealso
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).
TemplateParameters_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
References __sequential_multiway_merge(), and _GLIBCXX_CALL.
template<template<typename_RAI,typename_Cp>classiterator,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.
References _GLIBCXX_CALL.
template<template<typename_RAI,typename_Cp>classiterator,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.
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.
References __equally_split(), _GLIBCXX_PARALLEL_LENGTH, and multiseq_partition().
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.
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,consttypenamestd::iterator_traits<typenamestd::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.
TemplateParameters_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.
References __is_sorted(), and _GLIBCXX_CALL.
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,consttypenamestd::iterator_traits<typenamestd::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.
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.
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
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).
Seealso
stable_multiway_merge_sentinels
TemplateParameters_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
References __sequential_multiway_merge(), and _GLIBCXX_CALL.
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.
TemplateParameters_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.
References __is_sorted(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), and
__gnu_parallel::_Settings::merge_oversampling.
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)
PMWMS main call.
Parameters__begin Begin iterator of sequence.
__end End iterator of sequence.
__comp Comparator.
__num_threads Number of threads to use.
References _GLIBCXX_CALL, __gnu_parallel::_PMWMSSortingData<_RAIter>::_M_num_threads,
__gnu_parallel::_PMWMSSortingData<_RAIter>::_M_offsets, __gnu_parallel::_PMWMSSortingData<_RAIter>::_M_pieces, __gnu_parallel::_PMWMSSortingData<_RAIter>::_M_samples,
__gnu_parallel::_PMWMSSortingData<_RAIter>::_M_source, __gnu_parallel::_PMWMSSortingData<_RAIter>::_M_starts, __gnu_parallel::_PMWMSSortingData<_RAIter>::_M_temporary,
__gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::sort_mwms_oversampling.
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.
References __gnu_parallel::_PMWMSSortingData<_RAIter>::_M_num_threads,
__gnu_parallel::_PMWMSSortingData<_RAIter>::_M_pieces, __gnu_parallel::_PMWMSSortingData<_RAIter>::_M_source, __gnu_parallel::_PMWMSSortingData<_RAIter>::_M_starts, __gnu_parallel::_PMWMSSortingData<_RAIter>::_M_temporary, __gnu_parallel::_Settings::get(),
__gnu_parallel::_Settings::sort_mwms_oversampling, and std::uninitialized_copy().
Install Now
PNG Icons
