struct __accumulate_binop_reduct
General reduction, using a binary operator.
struct __accumulate_selector
std::accumulate() selector.
struct __adjacent_difference_selector
Selector that returns the difference between two adjacent __elements.
struct __adjacent_find_selector
Test predicate on two adjacent elements.
class __binder1st
Similar to std::binder1st, but giving the argument types explicitly.
class __binder2nd
Similar to std::binder2nd, but giving the argument types explicitly.
struct __count_if_selector
std::count_if () selector.
struct __count_selector
std::count() selector.
struct __fill_selector
std::fill() selector.
struct __find_first_of_selector
Test predicate on several elements.
struct __find_if_selector
Test predicate on a single element, used for std::find() and std::find_if ().
struct __for_each_selector
std::for_each() selector.
struct __generate_selector
std::generate() selector.
struct __generic_find_selector
Base class of all __gnu_parallel::__find_template selectors.
struct __generic_for_each_selector
Generic __selector for embarrassingly parallel functions.
struct __identity_selector
Selector that just returns the passed iterator.
struct __inner_product_selector
std::inner_product() selector.
struct __max_element_reduct
Reduction for finding the maximum element, using a comparator.
struct __min_element_reduct
Reduction for finding the maximum element, using a comparator.
struct __mismatch_selector
Test inverted predicate on a single element.
struct __multiway_merge_3_variant_sentinel_switch
Switch for 3-way merging with __sentinels turned off.
struct __multiway_merge_3_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
Switch for 3-way merging with __sentinels turned on.
struct __multiway_merge_4_variant_sentinel_switch
Switch for 4-way merging with __sentinels turned off.
struct __multiway_merge_4_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
Switch for 4-way merging with __sentinels turned on.
struct __multiway_merge_k_variant_sentinel_switch
Switch for k-way merging with __sentinels turned on.
struct __multiway_merge_k_variant_sentinel_switch< false, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
Switch for k-way merging with __sentinels turned off.
struct __replace_if_selector
std::replace() selector.
struct __replace_selector
std::replace() selector.
struct __transform1_selector
std::transform() __selector, one input sequence variant.
struct __transform2_selector
std::transform() __selector, two input sequences variant.
class __unary_negate
Similar to std::unary_negate, but giving the argument types explicitly.
struct _DRandomShufflingGlobalData
Data known to every thread participating in __gnu_parallel::__parallel_random_shuffle().
struct _DRSSorterPU
Local data for a thread participating in __gnu_parallel::__parallel_random_shuffle().
struct _DummyReduct
Reduction function doing nothing.
class _EqualFromLess
Constructs predicate for equality from strict weak ordering predicate.
struct _EqualTo
Similar to std::equal_to, but allows two different types.
class _GuardedIterator
_Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons.
class _IteratorPair
A pair of iterators. The usual iterator operations are applied to both child iterators.
class _IteratorTriple
A triple of iterators. The usual iterator operations are applied to all three child iterators.
struct _Job
One __job for a certain thread.
struct _Less
Similar to std::less, but allows two different types.
class _Lexicographic
Compare __a pair of types lexicographically, ascending.
class _LexicographicReverse
Compare __a pair of types lexicographically, descending.
class _LoserTree
Stable _LoserTree variant.
class _LoserTree< false, _Tp, _Compare >
Unstable _LoserTree variant.
class _LoserTreeBase
Guarded loser/tournament tree.
class _LoserTreePointer
Stable _LoserTree implementation.
class _LoserTreePointer< false, _Tp, _Compare >
Unstable _LoserTree implementation.
class _LoserTreePointerBase
Base class of _Loser Tree implementation using pointers.
class _LoserTreePointerUnguarded
Stable unguarded _LoserTree variant storing pointers.
class _LoserTreePointerUnguarded< false, _Tp, _Compare >
Unstable unguarded _LoserTree variant storing pointers.
class _LoserTreePointerUnguardedBase
Unguarded loser tree, keeping only pointers to the elements in the tree structure.
struct _LoserTreeTraits
Traits for determining whether the loser tree should use pointers or copies.
class _LoserTreeUnguarded
Stable implementation of unguarded _LoserTree.
class _LoserTreeUnguarded< false, _Tp, _Compare >
Non-Stable implementation of unguarded _LoserTree.
class _LoserTreeUnguardedBase
Base class for unguarded _LoserTree implementation.
struct _Multiplies
Similar to std::multiplies, but allows two different types.
struct _Nothing
Functor doing nothing.
struct _Piece
Subsequence description.
struct _Plus
Similar to std::plus, but allows two different types.
struct _PMWMSSortingData
Data accessed by all threads.
class _PseudoSequence
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored explicitly, of course.
class _PseudoSequenceIterator
_Iterator associated with __gnu_parallel::_PseudoSequence. If features the usual random-access iterator functionality.
struct _QSBThreadLocal
Information local to one thread in the parallel quicksort run.
class _RandomNumber
Random number generator, based on the Mersenne twister.
class _RestrictedBoundedConcurrentQueue
Double-ended queue of bounded size, allowing lock-free atomic access. push_front() and pop_front() must not be called concurrently to each other, while pop_back() can be called concurrently at all times. empty(), size(), and top() are intentionally not provided. Calling them would not make sense in a concurrent setting.
struct _SamplingSorter
Stable sorting functor.
struct _SamplingSorter< false, _RAIter, _StrictWeakOrdering >
Non-__stable sorting functor.
struct _Settings
class _Settings Run-time settings for the parallel mode including all tunable parameters.
struct _SplitConsistently
Split consistently.
struct _SplitConsistently< false, _RAIter, _Compare, _SortingPlacesIterator >
Split by sampling.
struct _SplitConsistently< true, _RAIter, _Compare, _SortingPlacesIterator >
Split by exact splitting.
struct balanced_quicksort_tag
Forces parallel sorting using balanced quicksort at compile time.
struct balanced_tag
Recommends parallel execution using dynamic load-balancing at compile time.
struct constant_size_blocks_tag
Selects the constant block size variant for std::find().
struct default_parallel_tag
Recommends parallel execution using the default parallel algorithm.
struct equal_split_tag
Selects the equal splitting variant for std::find().
struct exact_tag
Forces parallel merging with exact splitting, at compile time.
struct find_tag
Base class for for std::find() variants.
struct growing_blocks_tag
Selects the growing block size variant for std::find().
struct multiway_mergesort_exact_tag
Forces parallel sorting using multiway mergesort with exact splitting at compile time.
struct multiway_mergesort_sampling_tag
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time.
struct multiway_mergesort_tag
Forces parallel sorting using multiway mergesort at compile time.
struct omp_loop_static_tag
Recommends parallel execution using OpenMP static load-balancing at compile time.
struct omp_loop_tag
Recommends parallel execution using OpenMP dynamic load-balancing at compile time.
struct parallel_tag
Recommends parallel execution at compile time, optionally using a user-specified number of threads.
struct quicksort_tag
Forces parallel sorting using unbalanced quicksort at compile time.
struct sampling_tag
Forces parallel merging with exact splitting, at compile time.
struct sequential_tag
Forces sequential execution at compile time.
struct unbalanced_tag
Recommends parallel execution using static load-balancing at compile time.
typedef unsigned short _BinIndex
Type to hold the index of a bin.
typedef int64_t _CASable
Longest compare-and-swappable integer type on this platform.
typedef uint64_t _SequenceIndex
Unsigned integer to index __elements. The total number of elements for each algorithm must fit into this type.
typedef uint16_t _ThreadIndex
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit into this type.
enum _AlgorithmStrategy { heuristic, force_sequential, force_parallel }
Strategies for run-time algorithm selection:
enum _FindAlgorithm { GROWING_BLOCKS, CONSTANT_SIZE_BLOCKS, EQUAL_SPLIT }
Find algorithms:
enum _MultiwayMergeAlgorithm { LOSER_TREE }
Merging algorithms:
enum _Parallelism { sequential, parallel_unbalanced, parallel_balanced, parallel_omp_loop, parallel_omp_loop_static, parallel_taskqueue }
Run-time equivalents for the compile-time tags.
enum _PartialSumAlgorithm { RECURSIVE, LINEAR }
Partial sum algorithms: recursive, linear.
enum _SortAlgorithm { MWMS, QS, QS_BALANCED }
Sorting algorithms:
enum _SplittingAlgorithm { SAMPLING, EXACT }
Sorting/merging algorithms: sampling, __exact.
template<typename _Tp > _Tp __add_omp (volatile _Tp *__ptr, _Tp __addend)
template<typename _RAIter , typename _DifferenceTp > void __calc_borders (_RAIter __elements, _DifferenceTp __length, _DifferenceTp *__off)
Precalculate __advances for Knuth-Morris-Pratt algorithm.
template<typename _Tp > bool __cas_omp (volatile _Tp *__ptr, _Tp __comparand, _Tp __replacement)
template<typename _Tp > bool __compare_and_swap (volatile _Tp *__ptr, _Tp __comparand, _Tp __replacement)
Compare-and-swap.
template<typename _IIter , typename _OutputIterator > _OutputIterator __copy_tail (std::pair< _IIter, _IIter > __b, std::pair< _IIter, _IIter > __e, _OutputIterator __r)
void __decode2 (_CASable __x, int &__a, int &__b)
Decode two integers from one gnu_parallel::_CASable.
template<typename _RAIter , typename _DifferenceTp > void __determine_samples (_PMWMSSortingData< _RAIter > *__sd, _DifferenceTp __num_samples)
Select _M_samples from a sequence.
_CASable __encode2 (int __a, int __b)
Encode two integers into one gnu_parallel::_CASable.
template<typename _DifferenceType , typename _OutputIterator > _OutputIterator __equally_split (_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s)
function to split a sequence into parts of almost equal size.
template<typename _DifferenceType > _DifferenceType __equally_split_point (_DifferenceType __n, _ThreadIndex __num_threads, _ThreadIndex __thread_no)
function to split a sequence into parts of almost equal size.
template<typename _Tp > _Tp __fetch_and_add (volatile _Tp *__ptr, _Tp __addend)
Add a value to a variable, atomically.
template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector > std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector)
Parallel std::find, switch for different algorithms.
template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector > std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector, equal_split_tag)
Parallel std::find, equal splitting variant.
template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector > std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector, growing_blocks_tag)
Parallel std::find, growing block size variant.
template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector > std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector, constant_size_blocks_tag)
Parallel std::find, constant block size variant.
template<typename _IIter , typename _UserOp , typename _Functionality , typename _Red , typename _Result > _UserOp __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.
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > _Op __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.
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > _Op __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.
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > _Op __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.
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > _Op __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.
_ThreadIndex __get_max_threads ()
bool __is_parallel (const _Parallelism __p)
template<typename _IIter , typename _Compare > bool __is_sorted (_IIter __begin, _IIter __end, _Compare __comp)
Check whether [__begin, __end) is sorted according to __comp.
template<typename _RAIter , typename _Compare > _RAIter __median_of_three_iterators (_RAIter __a, _RAIter __b, _RAIter __c, _Compare __comp)
Compute the median of three referenced elements, according to __comp.
template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare > _OutputIterator __merge_advance (_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.
template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare > _OutputIterator __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.
template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare > _OutputIterator __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.
template<typename _RAIter1 , typename _RAIter2 , typename _RAIter3 , typename _Compare > _RAIter3 __parallel_merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp)
Merge routine fallback to sequential in case the iterators of the two input sequences are of different type.
template<typename _RAIter1 , typename _RAIter3 , typename _Compare > _RAIter3 __parallel_merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter1 &__begin2, _RAIter1 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp)
Parallel merge routine being able to merge only the __max_length smallest elements.
template<typename _RAIter , typename _Compare > void __parallel_nth_element (_RAIter __begin, _RAIter __nth, _RAIter __end, _Compare __comp)
Parallel implementation of std::nth_element().
template<typename _RAIter , typename _Compare > void __parallel_partial_sort (_RAIter __begin, _RAIter __middle, _RAIter __end, _Compare __comp)
Parallel implementation of std::partial_sort().
template<typename _IIter , typename _OutputIterator , typename _BinaryOperation > _OutputIterator __parallel_partial_sum (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op)
Parallel partial sum front-__end.
template<typename _IIter , typename _OutputIterator , typename _BinaryOperation > _OutputIterator __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.
template<typename _IIter , typename _OutputIterator , typename _BinaryOperation > _OutputIterator __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.
template<typename _RAIter , typename _Predicate > std::iterator_traits< _RAIter >::difference_type __parallel_partition (_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads)
Parallel implementation of std::partition.
template<typename _RAIter , typename _RandomNumberGenerator > void __parallel_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng=_RandomNumber())
Parallel random public call.
template<typename _RAIter , typename _RandomNumberGenerator > void __parallel_random_shuffle_drs (_RAIter __begin, _RAIter __end, typename std::iterator_traits< _RAIter >::difference_type __n, _ThreadIndex __num_threads, _RandomNumberGenerator &__rng)
Main parallel random shuffle step.
template<typename _RAIter , typename _RandomNumberGenerator > void __parallel_random_shuffle_drs_pu (_DRSSorterPU< _RAIter, _RandomNumberGenerator > *__pus)
Random shuffle code executed by each thread.
template<typename _IIter , typename _OutputIterator , typename _Compare > _OutputIterator __parallel_set_difference (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp)
template<typename _IIter , typename _OutputIterator , typename _Compare > _OutputIterator __parallel_set_intersection (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp)
template<typename _IIter , typename _OutputIterator , typename _Operation > _OutputIterator __parallel_set_operation (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Operation __op)
template<typename _IIter , typename _OutputIterator , typename _Compare > _OutputIterator __parallel_set_symmetric_difference (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp)
template<typename _IIter , typename _OutputIterator , typename _Compare > _OutputIterator __parallel_set_union (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp)
template<bool __stable, typename _RAIter , typename _Compare , typename _Parallelism > void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, _Parallelism __parallelism)
template<bool __stable, typename _RAIter , typename _Compare > void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_tag __parallelism)
Choose multiway mergesort, splitting variant at run-time, for parallel sorting.
template<bool __stable, typename _RAIter , typename _Compare > void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_exact_tag __parallelism)
Choose multiway mergesort with exact splitting, for parallel sorting.
template<bool __stable, typename _RAIter , typename _Compare > void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_sampling_tag __parallelism)
Choose multiway mergesort with splitting by sampling, for parallel sorting.
template<bool __stable, typename _RAIter , typename _Compare > void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, quicksort_tag __parallelism)
Choose quicksort for parallel sorting.
template<bool __stable, typename _RAIter , typename _Compare > void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, balanced_quicksort_tag __parallelism)
Choose balanced quicksort for parallel sorting.
template<bool __stable, typename _RAIter , typename _Compare > void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, default_parallel_tag __parallelism)
Choose multiway mergesort with exact splitting, for parallel sorting.
template<bool __stable, typename _RAIter , typename _Compare > void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, parallel_tag __parallelism)
Choose a parallel sorting algorithm.
template<typename _RAIter , typename _Compare > void __parallel_sort_qs (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Unbalanced quicksort main call.
template<typename _RAIter , typename _Compare > void __parallel_sort_qs_conquer (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Unbalanced quicksort conquer step.
template<typename _RAIter , typename _Compare > std::iterator_traits< _RAIter >::difference_type __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.
template<typename _RAIter , typename _Compare > void __parallel_sort_qsb (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Top-level quicksort routine.
template<typename _IIter , class _OutputIterator , class _BinaryPredicate > _OutputIterator __parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result, _BinaryPredicate __binary_pred)
Parallel std::unique_copy(), w/__o explicit equality predicate.
template<typename _IIter , class _OutputIterator > _OutputIterator __parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result)
Parallel std::unique_copy(), without explicit equality predicate.
template<typename _RAIter , typename _Compare > void __qsb_conquer (_QSBThreadLocal< _RAIter > **__tls, _RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __iam, _ThreadIndex __num_threads, bool __parent_wait)
Quicksort conquer step.
template<typename _RAIter , typename _Compare > std::iterator_traits< _RAIter >::difference_type __qsb_divide (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
Balanced quicksort divide step.
template<typename _RAIter , typename _Compare > void __qsb_local_sort_with_helping (_QSBThreadLocal< _RAIter > **__tls, _Compare &__comp, _ThreadIndex __iam, bool __wait)
Quicksort step doing load-balanced local sort.
template<typename _RandomNumberGenerator > int __random_number_pow2 (int __logp, _RandomNumberGenerator &__rng)
Generate a random number in [0,2^__logp).
template<typename _Size > _Size __rd_log2 (_Size __n)
Calculates the rounded-down logarithm of __n for base 2.
template<typename _Tp > _Tp __round_up_to_pow2 (_Tp __x)
Round up to the next greater power of 2.
template<typename __RAIter1 , typename __RAIter2 , typename _Pred > __RAIter1 __search_template (__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred)
Parallel std::search.
template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 __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.
template<typename _RAIter , typename _RandomNumberGenerator > void __sequential_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng)
Sequential cache-efficient random shuffle.
template<typename _IIter > void __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.
template<typename _IIter > void __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.
void __yield ()
Yield control to another thread, without waiting for the end of the time slice.
template<typename _IIter , typename _FunctorType > size_t 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.
template<typename _Tp > const _Tp & max (const _Tp &__a, const _Tp &__b)
Equivalent to std::max.
template<typename _Tp > const _Tp & min (const _Tp &__a, const _Tp &__b)
Equivalent to std::min.
template<typename _RanSeqs , typename _RankType , typename _RankIterator , typename _Compare > void 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.
template<typename _Tp , typename _RanSeqs , typename _RankType , typename _Compare > _Tp 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.
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
Multiway Merge Frontend.
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 multiway_merge_3_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp)
Highly efficient 3-way merging procedure.
template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 multiway_merge_4_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp)
Highly efficient 4-way merging procedure.
template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType > void 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.
template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 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.
template<typename UnguardedLoserTree , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 multiway_merge_loser_tree_sentinel (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp)
Multi-way merging procedure for a high branching factor, requiring sentinels to exist.
template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 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.
template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType > void 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.
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
Multiway Merge Frontend.
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Splitter , typename _Compare > _RAIter3 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.
template<bool __stable, bool __exact, typename _RAIter , typename _Compare > void parallel_sort_mwms (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
PMWMS main call.
template<bool __stable, bool __exact, typename _RAIter , typename _Compare > void parallel_sort_mwms_pu (_PMWMSSortingData< _RAIter > *__sd, _Compare &__comp)
PMWMS code executed by each thread.
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > _RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
static const int _CASable_bits
Number of bits of _CASable.
static const _CASable _CASable_mask
_CASable with the right half of bits set to 1.
GNU parallel code for public use.
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.
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.
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.
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
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.
Precalculate __advances for Knuth-Morris-Pratt algorithm.
Parameters:
Definition at line 51 of file search.h.
Referenced by __search_template().
Compare-and-swap. Compare *__ptr and __comparand. If equal, let *__ptr=__replacement and return true, return false otherwise.
Parameters:
Definition at line 108 of file parallel/compatibility.h.
Referenced by __parallel_partition(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< pair< _RAIter, _RAIter > >::pop_back(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< pair< _RAIter, _RAIter > >::pop_front().
Decode two integers from one gnu_parallel::_CASable.
Parameters:
See also:
Definition at line 133 of file parallel/base.h.
References _CASable_bits, and _CASable_mask.
Referenced by __gnu_parallel::_RestrictedBoundedConcurrentQueue< pair< _RAIter, _RAIter > >::pop_back(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< pair< _RAIter, _RAIter > >::pop_front(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< pair< _RAIter, _RAIter > >::push_front().
Select _M_samples from a sequence.
Parameters:
Definition at line 97 of file multiway_mergesort.h.
References __equally_split(), __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_samples, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, and __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts.
Encode two integers into one gnu_parallel::_CASable.
Parameters:
Returns:
See also:
Definition at line 119 of file parallel/base.h.
References _CASable_bits.
Referenced by __gnu_parallel::_RestrictedBoundedConcurrentQueue< pair< _RAIter, _RAIter > >::_RestrictedBoundedConcurrentQueue(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< pair< _RAIter, _RAIter > >::pop_back(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< pair< _RAIter, _RAIter > >::pop_front().
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:
Returns:
Definition at line 48 of file equally_split.h.
Referenced by __determine_samples(), __find_template(), __parallel_partial_sum_linear(), and __search_template().
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:
Returns:
Definition at line 75 of file equally_split.h.
Add a value to a variable, atomically.
Parameters:
Definition at line 74 of file parallel/compatibility.h.
Referenced by __parallel_partition().
Parallel std::find, switch for different algorithms.
Parameters:
Returns:
Definition at line 60 of file find.h.
References __gnu_parallel::_Settings::get().
Parallel std::find, equal splitting variant.
Parameters:
Returns:
Definition at line 97 of file find.h.
References __equally_split(), and _GLIBCXX_CALL.
Parallel std::find, growing block size variant.
Parameters:
Returns:
See also:
__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.
Definition at line 185 of file find.h.
References _GLIBCXX_CALL, __gnu_parallel::_Settings::find_scale_factor, __gnu_parallel::_Settings::find_sequential_search_size, std::pair< _T1, _T2 >::first, and __gnu_parallel::_Settings::get().
Parallel std::find, constant block size variant.
Parameters:
Returns:
See also:
__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.
Definition at line 315 of file find.h.
References _GLIBCXX_CALL, __gnu_parallel::_Settings::find_initial_block_size, __gnu_parallel::_Settings::find_sequential_search_size, std::pair< _T1, _T2 >::first, and __gnu_parallel::_Settings::get().
Chose the desired algorithm by evaluating __parallelism_tag.
Parameters:
Definition at line 61 of file for_each.h.
References __for_each_template_random_access_ed(), __for_each_template_random_access_omp_loop(), __for_each_template_random_access_workstealing(), parallel_omp_loop, parallel_omp_loop_static, and parallel_unbalanced.
Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work.
Parameters:
Returns:
Definition at line 67 of file par_loop.h.
Referenced by __for_each_template_random_access().
Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop.
Parameters:
Returns:
Definition at line 67 of file omp_loop.h.
Referenced by __for_each_template_random_access().
Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling.
Parameters:
Returns:
Definition at line 66 of file omp_loop_static.h.
Work stealing algorithm for random access iterators. Uses O(1) additional memory. Synchronization at job lists is done with atomic operations.
Parameters:
Returns:
Definition at line 99 of file workstealing.h.
Referenced by __for_each_template_random_access().
Check whether [__begin, __end) is sorted according to __comp.
Parameters:
Returns:
Definition at line 51 of file checkers.h.
Compute the median of three referenced elements, according to __comp.
Parameters:
Definition at line 398 of file parallel/base.h.
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:
Returns:
Definition at line 171 of file merge.h.
References __merge_advance_movc(), and _GLIBCXX_CALL.
Referenced by __parallel_merge_advance().
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:
Returns:
Definition at line 105 of file merge.h.
Referenced by __merge_advance().
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:
Returns:
Definition at line 57 of file merge.h.
Merge routine fallback to sequential in case the iterators of the two input sequences are of different type.
Parameters:
Returns:
Definition at line 195 of file merge.h.
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:
Returns:
Definition at line 223 of file merge.h.
References std::make_pair(), multiway_merge_exact_splitting(), and parallel_multiway_merge().
Parallel implementation of std::nth_element().
Parameters:
Definition at line 332 of file partition.h.
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().
Parallel implementation of std::partial_sort().
Parameters:
Definition at line 422 of file partition.h.
References __parallel_nth_element().
Parallel partial sum front-__end.
Parameters:
Returns:
Definition at line 205 of file partial_sum.h.
References __parallel_partial_sum_linear(), _GLIBCXX_CALL, and __gnu_parallel::_Settings::get().
Base case prefix sum routine.
Parameters:
Returns:
Definition at line 58 of file partial_sum.h.
Referenced by __parallel_partial_sum_linear().
Parallel partial sum implementation, two-phase approach, no recursion.
Parameters:
Returns:
Definition at line 89 of file partial_sum.h.
References __equally_split(), __parallel_partial_sum_basecase(), std::accumulate(), __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::partial_sum_dilation.
Referenced by __parallel_partial_sum().
Parallel implementation of std::partition.
Parameters:
Returns:
Definition at line 56 of file partition.h.
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 random public call.
Parameters:
Definition at line 522 of file random_shuffle.h.
References __parallel_random_shuffle_drs().
Main parallel random shuffle step.
Parameters:
Definition at line 265 of file random_shuffle.h.
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().
Random shuffle code executed by each thread.
Parameters:
Definition at line 122 of file random_shuffle.h.
References __random_number_pow2(), __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, and std::partial_sum().
Referenced by __parallel_random_shuffle_drs().
Choose multiway mergesort, splitting variant at run-time, for parallel sorting.
Parameters:
Template Parameters:
Definition at line 75 of file sort.h.
References __gnu_parallel::parallel_tag::__get_num_threads(), _GLIBCXX_CALL, and __gnu_parallel::_Settings::get().
Choose multiway mergesort with exact splitting, for parallel sorting.
Parameters:
Template Parameters:
Definition at line 99 of file sort.h.
References __gnu_parallel::parallel_tag::__get_num_threads(), and _GLIBCXX_CALL.
Choose multiway mergesort with splitting by sampling, for parallel sorting.
Parameters:
Template Parameters:
Definition at line 120 of file sort.h.
References __gnu_parallel::parallel_tag::__get_num_threads(), and _GLIBCXX_CALL.
Choose quicksort for parallel sorting.
Parameters:
Template Parameters:
Definition at line 140 of file sort.h.
Choose balanced quicksort for parallel sorting.
Parameters:
Template Parameters:
Definition at line 161 of file sort.h.
Choose multiway mergesort with exact splitting, for parallel sorting.
Parameters:
Template Parameters:
Definition at line 183 of file sort.h.
References __gnu_parallel::parallel_tag::__get_num_threads(), and _GLIBCXX_CALL.
Choose a parallel sorting algorithm.
Parameters:
Template Parameters:
Definition at line 203 of file sort.h.
References __gnu_parallel::parallel_tag::__get_num_threads(), __parallel_sort_qs(), __parallel_sort_qsb(), _GLIBCXX_CALL, and __gnu_parallel::_Settings::get().
Unbalanced quicksort main call.
Parameters:
Definition at line 154 of file quicksort.h.
References __parallel_sort_qs_conquer(), and _GLIBCXX_CALL.
Referenced by __parallel_sort().
Unbalanced quicksort conquer step.
Parameters:
Definition at line 101 of file quicksort.h.
Referenced by __parallel_sort_qs().
Unbalanced quicksort divide step.
Parameters:
Definition at line 51 of file quicksort.h.
Top-level quicksort routine.
Parameters:
Definition at line 433 of file balanced_quicksort.h.
References __qsb_conquer(), __rd_log2(), _GLIBCXX_CALL, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_elements_leftover, and std::make_pair().
Referenced by __parallel_sort().
Parallel std::unique_copy(), w/__o explicit equality predicate.
Parameters:
Returns:
Definition at line 50 of file unique_copy.h.
References _GLIBCXX_CALL.
Referenced by __parallel_unique_copy().
Parallel std::unique_copy(), without explicit equality predicate.
Parameters:
Returns:
Definition at line 186 of file unique_copy.h.
References __parallel_unique_copy().
Quicksort conquer step.
Parameters:
Definition at line 174 of file balanced_quicksort.h.
References __qsb_divide(), __qsb_local_sort_with_helping(), and __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_initial.
Referenced by __parallel_sort_qsb().
Balanced quicksort divide step.
Parameters:
Precondition:
Definition at line 103 of file balanced_quicksort.h.
Referenced by __qsb_conquer().
Quicksort step doing load-balanced local sort.
Parameters:
Definition at line 250 of file balanced_quicksort.h.
References __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_initial, __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().
Generate a random number in [0,2^__logp).
Parameters:
Definition at line 115 of file random_shuffle.h.
Referenced by __parallel_random_shuffle_drs_pu(), and __sequential_random_shuffle().
Calculates the rounded-down logarithm of __n for base 2.
Parameters:
Returns:
Definition at line 102 of file parallel/base.h.
Referenced by __parallel_random_shuffle_drs(), __parallel_sort_qsb(), __round_up_to_pow2(), __sequential_random_shuffle(), __gnu_parallel::_LoserTreeBase< _Tp, _Compare >::_LoserTreeBase(), and multiseq_selection().
Round up to the next greater power of 2.
Parameters:
Definition at line 248 of file random_shuffle.h.
References __rd_log2().
Referenced by __parallel_random_shuffle_drs(), __sequential_random_shuffle(), and multiseq_selection().
Parallel std::search.
Parameters:
Returns:
Definition at line 81 of file search.h.
References __calc_borders(), __equally_split(), _GLIBCXX_CALL, and std::min().
Sequential multi-way merging switch. The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings.
Parameters:
Returns:
Definition at line 920 of file multiway_merge.h.
References _GLIBCXX_CALL.
Referenced by multiway_merge(), and multiway_merge_sentinels().
Sequential cache-efficient random shuffle.
Parameters:
Definition at line 410 of file random_shuffle.h.
References __random_number_pow2(), __rd_log2(), __round_up_to_pow2(), __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().
Combines two ranges into one and thus halves the number of ranges.
Parameters:
Definition at line 70 of file list_partition.h.
References std::vector< _Tp, _Alloc >::size().
Referenced by __shrink_and_double().
Shrinks and doubles the ranges.
Parameters:
Definition at line 50 of file list_partition.h.
References __shrink(), std::vector< _Tp, _Alloc >::resize(), and std::vector< _Tp, _Alloc >::size().
Referenced by list_partition().
Yield control to another thread, without waiting for the end of the time slice.
Definition at line 121 of file parallel/compatibility.h.
Splits a sequence given by input iterators into parts of almost equal size. The function needs only one pass over the sequence.
Parameters:
Returns:
Definition at line 101 of file list_partition.h.
References __shrink_and_double(), and std::vector< _Tp, _Alloc >::size().
Equivalent to std::max.
Definition at line 150 of file parallel/base.h.
Equivalent to std::min.
Definition at line 144 of file parallel/base.h.
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:
Definition at line 122 of file multiseq_selection.h.
References _GLIBCXX_CALL, and std::distance().
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:
Definition at line 388 of file multiseq_selection.h.
References __rd_log2(), __round_up_to_pow2(), std::__sample(), _GLIBCXX_CALL, std::distance(), std::make_pair(), and std::max().
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:
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:
Precondition:
Target must provide enough space to merge out length elements or the number of elements in all sequences, whichever is smaller.
Postcondition:
return __value - __target = min(__length, number of elements in all sequences).
Template Parameters:
Parameters:
Returns:
Definition at line 1418 of file multiway_merge.h.
References __sequential_multiway_merge(), and _GLIBCXX_CALL.
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:
Returns:
Definition at line 241 of file multiway_merge.h.
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:
Returns:
Definition at line 360 of file multiway_merge.h.
Exact splitting for parallel multiway-merge routine. None of the passed sequences may be empty.
Definition at line 1120 of file multiway_merge.h.
Referenced by __parallel_merge_advance().
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:
Returns:
Definition at line 491 of file multiway_merge.h.
References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_LENGTH.
Multi-way merging procedure for a high branching factor, requiring sentinels to exist.
Template Parameters:
Parameters:
Returns:
Definition at line 662 of file multiway_merge.h.
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:
Parameters:
Returns:
Definition at line 574 of file multiway_merge.h.
Sampling based splitting for parallel multiway-merge routine.
Definition at line 1035 of file multiway_merge.h.
References _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::merge_oversampling.
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:
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:
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:
return __value - __target = min(__length, number of elements in all sequences).
See also:
Template Parameters:
Parameters:
Returns:
Definition at line 1782 of file multiway_merge.h.
References __sequential_multiway_merge(), and _GLIBCXX_CALL.
Parallel multi-way merge routine. The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings.
Must not be called if the number of sequences is 1.
Template Parameters:
Parameters:
Returns:
Definition at line 1225 of file multiway_merge.h.
Referenced by __parallel_merge_advance().
PMWMS main call.
Parameters:
Definition at line 395 of file multiway_mergesort.h.
PMWMS code executed by each thread.
Parameters:
Definition at line 308 of file multiway_mergesort.h.
References __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_num_threads, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_temporary, __gnu_parallel::_Settings::get(), std::make_pair(), __gnu_parallel::_Settings::sort_mwms_oversampling, and std::uninitialized_copy().
Number of bits of _CASable.
Definition at line 130 of file types.h.
Referenced by __decode2(), and __encode2().
_CASable with the right half of bits set to 1.
Definition at line 133 of file types.h.
Generated automatically by Doxygen for libstdc++ from the source code.