Classes
struct	__accumulate_binop_reduct

struct	__accumulate_selector

struct	__adjacent_difference_selector

struct	__adjacent_find_selector

class	__binder1st

class	__binder2nd

struct	__count_if_selector

struct	__count_selector

struct	__fill_selector

struct	__find_first_of_selector

struct	__find_if_selector

struct	__for_each_selector

struct	__generate_selector

struct	__generic_find_selector

struct	__generic_for_each_selector

struct	__identity_selector

struct	__inner_product_selector

struct	__max_element_reduct

struct	__min_element_reduct

struct	__mismatch_selector

struct	__multiway_merge_3_variant_sentinel_switch

struct	__multiway_merge_3_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >

struct	__multiway_merge_4_variant_sentinel_switch

struct	__multiway_merge_4_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >

struct	__multiway_merge_k_variant_sentinel_switch

struct	__multiway_merge_k_variant_sentinel_switch< false, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >

struct	__replace_if_selector

struct	__replace_selector

struct	__transform1_selector

struct	__transform2_selector

class	__unary_negate

struct	_DRandomShufflingGlobalData

struct	_DRSSorterPU

struct	_DummyReduct

class	_EqualFromLess

struct	_EqualTo

class	_GuardedIterator

class	_IteratorPair

class	_IteratorTriple

struct	_Job

struct	_Less

class	_Lexicographic

class	_LexicographicReverse

class	_LoserTree

class	_LoserTree< false, _Tp, _Compare >

class	_LoserTreeBase

class	_LoserTreePointer

class	_LoserTreePointer< false, _Tp, _Compare >

class	_LoserTreePointerBase

class	_LoserTreePointerUnguarded

class	_LoserTreePointerUnguarded< false, _Tp, _Compare >

class	_LoserTreePointerUnguardedBase

struct	_LoserTreeTraits

class	_LoserTreeUnguarded

class	_LoserTreeUnguarded< false, _Tp, _Compare >

class	_LoserTreeUnguardedBase

struct	_Multiplies

struct	_Nothing

struct	_Piece

struct	_Plus

struct	_PMWMSSortingData

class	_PseudoSequence

class	_PseudoSequenceIterator

struct	_QSBThreadLocal

class	_RandomNumber

class	_RestrictedBoundedConcurrentQueue

struct	_SamplingSorter

struct	_SamplingSorter< false, _RAIter, _StrictWeakOrdering >

struct	_Settings

struct	_SplitConsistently

struct	_SplitConsistently< false, _RAIter, _Compare, _SortingPlacesIterator >

struct	_SplitConsistently< true, _RAIter, _Compare, _SortingPlacesIterator >

struct	balanced_quicksort_tag

struct	balanced_tag

struct	constant_size_blocks_tag

struct	default_parallel_tag

struct	equal_split_tag

struct	exact_tag

struct	find_tag

struct	growing_blocks_tag

struct	multiway_mergesort_exact_tag

struct	multiway_mergesort_sampling_tag

struct	multiway_mergesort_tag

struct	omp_loop_static_tag

struct	omp_loop_tag

struct	parallel_tag

struct	quicksort_tag

struct	sampling_tag

struct	sequential_tag

struct	unbalanced_tag

Typedefs
typedef unsigned short	_BinIndex

typedef int64_t	_CASable

typedef uint64_t	_SequenceIndex

typedef uint16_t	_ThreadIndex

Enumerations
enum	_AlgorithmStrategy { heuristic , force_sequential , force_parallel }

enum	_FindAlgorithm { GROWING_BLOCKS , CONSTANT_SIZE_BLOCKS , EQUAL_SPLIT }

enum	_MultiwayMergeAlgorithm { LOSER_TREE }

enum	_Parallelism { sequential , parallel_unbalanced , parallel_balanced , parallel_omp_loop , parallel_omp_loop_static , parallel_taskqueue }

enum	_PartialSumAlgorithm { RECURSIVE , LINEAR }

enum	_SortAlgorithm { MWMS , QS , QS_BALANCED }

enum	_SplittingAlgorithm { SAMPLING , EXACT }

Functions
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)

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)

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)

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

_CASable	__encode2 (int __a, int __b)

template<typename _DifferenceType , typename _OutputIterator >
_OutputIterator	__equally_split (_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s)

template<typename _DifferenceType >
_DifferenceType	__equally_split_point (_DifferenceType __n, _ThreadIndex __num_threads, _ThreadIndex __thread_no)

template<typename _Tp >
_Tp	__fetch_and_add (volatile _Tp *__ptr, _Tp __addend)

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)

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)

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)

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)

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)

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)

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)

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)

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)

_ThreadIndex	__get_max_threads ()

bool	__is_parallel (const _Parallelism __p)

template<typename _IIter , typename _Compare >
bool	__is_sorted (_IIter __begin, _IIter __end, _Compare __comp)

template<typename _RAIter , typename _Compare >
_RAIter	__median_of_three_iterators (_RAIter __a, _RAIter __b, _RAIter __c, _Compare __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)

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)

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)

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)

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)

template<typename _RAIter , typename _Compare >
void	__parallel_nth_element (_RAIter __begin, _RAIter __nth, _RAIter __end, _Compare __comp)

template<typename _RAIter , typename _Compare >
void	__parallel_partial_sort (_RAIter __begin, _RAIter __middle, _RAIter __end, _Compare __comp)

template<typename _IIter , typename _OutputIterator , typename _BinaryOperation >
_OutputIterator	__parallel_partial_sum (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op)

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)

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)

template<typename _RAIter , typename _Predicate >
std::iterator_traits< _RAIter >::difference_type	__parallel_partition (_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads)

template<typename _RAIter , typename _RandomNumberGenerator >
void	__parallel_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng=_RandomNumber())

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)

template<typename _RAIter , typename _RandomNumberGenerator >
void	__parallel_random_shuffle_drs_pu (_DRSSorterPU< _RAIter, _RandomNumberGenerator > *__pus)

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, balanced_quicksort_tag __parallelism)

template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, default_parallel_tag __parallelism)

template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_exact_tag __parallelism)

template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_sampling_tag __parallelism)

template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_tag __parallelism)

template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, parallel_tag __parallelism)

template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, quicksort_tag __parallelism)

template<typename _RAIter , typename _Compare >
void	__parallel_sort_qs (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)

template<typename _RAIter , typename _Compare >
void	__parallel_sort_qs_conquer (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)

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)

template<typename _RAIter , typename _Compare >
void	__parallel_sort_qsb (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)

template<typename _IIter , class _OutputIterator >
_OutputIterator	__parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result)

template<typename _IIter , class _OutputIterator , class _BinaryPredicate >
_OutputIterator	__parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result, _BinaryPredicate __binary_pred)

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)

template<typename _RAIter , typename _Compare >
std::iterator_traits< _RAIter >::difference_type	__qsb_divide (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)

template<typename _RAIter , typename _Compare >
void	__qsb_local_sort_with_helping (_QSBThreadLocal< _RAIter > **__tls, _Compare &__comp, _ThreadIndex __iam, bool __wait)

template<typename _RandomNumberGenerator >
int	__random_number_pow2 (int __logp, _RandomNumberGenerator &__rng)

template<typename _Size >
_Size	__rd_log2 (_Size __n)

template<typename _Tp >
_Tp	__round_up_to_pow2 (_Tp __x)

template<typename __RAIter1 , typename __RAIter2 , typename _Pred >
__RAIter1	__search_template (__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred)

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)

template<typename _RAIter , typename _RandomNumberGenerator >
void	__sequential_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng)

template<typename _IIter >
void	__shrink (std::vector< _IIter > &__os_starts, size_t &__count_to_two, size_t &__range_length)

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)

void	__yield ()

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)

template<typename _Tp >
const _Tp &	max (const _Tp &__a, const _Tp &__b)

template<typename _Tp >
const _Tp &	min (const _Tp &__a, const _Tp &__b)

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 >())

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 >())

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, __gnu_parallel::sequential_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, default_parallel_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<template< typename _RAI, typename _Cp > 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)

template<template< typename _RAI, typename _Cp > 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)

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)

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)

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)

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)

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)

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, __gnu_parallel::sequential_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, default_parallel_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, sampling_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)

template<bool __stable, bool __exact, typename _RAIter , typename _Compare >
void	parallel_sort_mwms (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)

template<bool __stable, bool __exact, typename _RAIter , typename _Compare >
void	parallel_sort_mwms_pu (_PMWMSSortingData< _RAIter > *__sd, _Compare &__comp)

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, __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, default_parallel_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, 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, __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, __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, 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, 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, sampling_tag __tag)

Variables
static const int	_CASable_bits

static const _CASable	_CASable_mask

Detailed Description

GNU parallel code for public use.

Typedef Documentation

◆ _BinIndex

typedef unsigned short __gnu_parallel::_BinIndex

Type to hold the index of a bin.

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

Definition at line 47 of file random_shuffle.h.

◆ _CASable

typedef int64_t __gnu_parallel::_CASable

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

Definition at line 127 of file types.h.

◆ _SequenceIndex

typedef uint64_t __gnu_parallel::_SequenceIndex

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

Definition at line 117 of file types.h.

◆ _ThreadIndex

typedef uint16_t __gnu_parallel::_ThreadIndex

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

Definition at line 123 of file types.h.

Enumeration Type Documentation

◆ _AlgorithmStrategy

enum __gnu_parallel::_AlgorithmStrategy

Strategies for run-time algorithm selection:

Definition at line 67 of file types.h.

◆ _FindAlgorithm

enum __gnu_parallel::_FindAlgorithm

Find algorithms:

Definition at line 106 of file types.h.

◆ _MultiwayMergeAlgorithm

enum __gnu_parallel::_MultiwayMergeAlgorithm

Merging algorithms:

Definition at line 85 of file types.h.

◆ _Parallelism

enum __gnu_parallel::_Parallelism

Run-time equivalents for the compile-time tags.

Enumerator
sequential	Not parallel.
parallel_unbalanced	Parallel unbalanced (equal-sized chunks).
parallel_balanced	Parallel balanced (work-stealing).
parallel_omp_loop	Parallel with OpenMP dynamic load-balancing.
parallel_omp_loop_static	Parallel with OpenMP static load-balancing.
parallel_taskqueue	Parallel with OpenMP taskqueue construct.

Definition at line 44 of file types.h.

◆ _PartialSumAlgorithm

enum __gnu_parallel::_PartialSumAlgorithm

Partial sum algorithms: recursive, linear.

Definition at line 91 of file types.h.

◆ _SortAlgorithm

enum __gnu_parallel::_SortAlgorithm

Sorting algorithms:

Definition at line 76 of file types.h.

◆ _SplittingAlgorithm

enum __gnu_parallel::_SplittingAlgorithm

Sorting/merging algorithms: sampling, __exact.

Definition at line 98 of file types.h.

Function Documentation

◆ __add_omp()

template<typename _Tp >

_Tp __gnu_parallel::__add_omp	(	volatile _Tp *	__ptr,
		_Tp	__addend
	)

inline

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

◆ __calc_borders()

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.

Definition at line 51 of file search.h.

Referenced by __search_template().

◆ __cas_omp()

template<typename _Tp >

bool __gnu_parallel::__cas_omp	(	volatile _Tp *	__ptr,
		_Tp	__comparand,
		_Tp	__replacement
	)

inline

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

◆ __compare_and_swap()

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.

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

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

◆ __copy_tail()

template<typename _IIter , typename _OutputIterator >

_OutputIterator __gnu_parallel::__copy_tail	(	std::pair< _IIter, _IIter >	__b,
		std::pair< _IIter, _IIter >	__e,
		_OutputIterator	__r
	)

Definition at line 46 of file set_operations.h.

◆ __decode2()

void __gnu_parallel::__decode2	(	_CASable	__x,
		int &	__a,
		int &	__b
	)

inline

Decode two integers from one gnu_parallel::_CASable.

Parameters

__x	__gnu_parallel::_CASable to decode integers from.
__a	First integer, to be decoded from the most-significant `_CASable_bits/2` bits of `__x`.
__b	Second integer, to be encoded in the least-significant `_CASable_bits/2` bits of `__x`.

See also: __encode2

Definition at line 133 of file base.h.

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().

◆ __determine_samples()

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.

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.

◆ __encode2()

_CASable __gnu_parallel::__encode2	(	int	__a,
		int	__b
	)

inline

Encode two integers into one gnu_parallel::_CASable.

Parameters

__a	First integer, to be encoded in the most-significant `_CASable_bits/2` bits.
__b	Second integer, to be encoded in the least-significant `_CASable_bits/2` bits.

Returns: value encoding __a and __b.

See also: __decode2

Definition at line 119 of file base.h.

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().

◆ __equally_split()

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

Definition at line 48 of file equally_split.h.

Referenced by __determine_samples(), __find_template(), __parallel_partial_sum_linear(), __parallel_unique_copy(), __search_template(), and multiway_merge_exact_splitting().

◆ __equally_split_point()

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

Definition at line 75 of file equally_split.h.

Referenced by __for_each_template_random_access_ed().

◆ __fetch_and_add()

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.

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

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

◆ __find_template() [1/4]

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.

Definition at line 60 of file find.h.

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

Referenced by __find_template().

◆ __find_template() [2/4]

template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector >

std::pair< _RAIter1, _RAIter2 > __gnu_parallel::__find_template	(	_RAIter1	__begin1,
		_RAIter1	__end1,
		_RAIter2	__begin2,
		_Pred	__pred,
		_Selector	__selector,
		constant_size_blocks_tag
	)

Parallel std::find, constant block size variant.

Parameters

__begin1	Begin iterator of first sequence.
__end1	End iterator of first sequence.
__begin2	Begin iterator of second sequence. Second __sequence must have same length as first sequence.
__pred	Find predicate.
__selector	_Functionality (e. g. std::find_if(), std::equal(),...)

Returns: Place of finding in both sequences.

See also

__gnu_parallel::_Settings::find_sequential_search_size

__gnu_parallel::_Settings::find_block_size There are two main differences between the growing blocks and the constant-size blocks variants.

For GB, the block size grows; for CSB, the block size is fixed.
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().

◆ __find_template() [3/4]

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.

Definition at line 97 of file find.h.

References __equally_split(), and _GLIBCXX_CALL.

◆ __find_template() [4/4]

template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector >

std::pair< _RAIter1, _RAIter2 > __gnu_parallel::__find_template	(	_RAIter1	__begin1,
		_RAIter1	__end1,
		_RAIter2	__begin2,
		_Pred	__pred,
		_Selector	__selector,
		growing_blocks_tag
	)

Parallel std::find, growing block size variant.

Parameters

__begin1	Begin iterator of first sequence.
__end1	End iterator of first sequence.
__begin2	Begin iterator of second sequence. Second __sequence must have same length as first sequence.
__pred	Find predicate.
__selector	_Functionality (e. g. std::find_if(), std::equal(),...)

Returns: Place of finding in both sequences.

See also: __gnu_parallel::_Settings::find_sequential_search_size; __gnu_parallel::_Settings::find_scale_factor

There are two main differences between the growing blocks and the constant-size blocks variants.

For GB, the block size grows; for CSB, the block size is fixed.
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().

◆ __for_each_template_random_access()

template<typename _IIter , typename _UserOp , typename _Functionality , typename _Red , typename _Result >

_UserOp __gnu_parallel::__for_each_template_random_access	(	_IIter	__begin,
		_IIter	__end,
		_UserOp	__user_op,
		_Functionality &	__functionality,
		_Red	__reduction,
		_Result	__reduction_start,
		_Result &	__output,
		typename std::iterator_traits< _IIter >::difference_type	__bound,
		_Parallelism	__parallelism_tag
	)

Chose the desired algorithm by evaluating __parallelism_tag.

Parameters

__begin	Begin iterator of input sequence.
__end	End iterator of input sequence.
__user_op	A user-specified functor (comparator, predicate, associative operator,...)
__functionality	functor to process an element with __user_op (depends on desired functionality, e. g. accumulate, for_each,...
__reduction	Reduction functor.
__reduction_start	Initial value for reduction.
__output	Output iterator.
__bound	Maximum number of elements processed.
__parallelism_tag	Parallelization method

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.

◆ __for_each_template_random_access_ed()

template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result >

_Op __gnu_parallel::__for_each_template_random_access_ed	(	_RAIter	__begin,
		_RAIter	__end,
		_Op	__o,
		_Fu &	__f,
		_Red	__r,
		_Result	__base,
		_Result &	__output,
		typename std::iterator_traits< _RAIter >::difference_type	__bound
	)

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

Parameters

__begin	Begin iterator of element sequence.
__end	End iterator of element sequence.
__o	User-supplied functor (comparator, predicate, adding functor, ...)
__f	Functor to "process" an element with __op (depends on desired functionality, e. g. for std::for_each(), ...).
__r	Functor to "add" a single __result to the already processed elements (depends on functionality).
__base	Base value for reduction.
__output	Pointer to position where final result is written to
__bound	Maximum number of elements processed (e. g. for std::count_n()).

Returns: User-supplied functor (that may contain a part of the result).

Definition at line 67 of file par_loop.h.

References __equally_split_point().

Referenced by __for_each_template_random_access().

◆ __for_each_template_random_access_omp_loop()

template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result >

_Op __gnu_parallel::__for_each_template_random_access_omp_loop	(	_RAIter	__begin,
		_RAIter	__end,
		_Op	__o,
		_Fu &	__f,
		_Red	__r,
		_Result	__base,
		_Result &	__output,
		typename std::iterator_traits< _RAIter >::difference_type	__bound
	)

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

Parameters

__begin	Begin iterator of element sequence.
__end	End iterator of element sequence.
__o	User-supplied functor (comparator, predicate, adding functor, etc.).
__f	Functor to process an element with __op (depends on desired functionality, e. g. for std::for_each(), ...).
__r	Functor to add a single __result to the already processed elements (depends on functionality).
__base	Base value for reduction.
__output	Pointer to position where final result is written to
__bound	Maximum number of elements processed (e. g. for std::count_n()).

Returns: User-supplied functor (that may contain a part of the result).

Definition at line 67 of file omp_loop.h.

Referenced by __for_each_template_random_access().

◆ __for_each_template_random_access_omp_loop_static()

template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result >

_Op __gnu_parallel::__for_each_template_random_access_omp_loop_static	(	_RAIter	__begin,
		_RAIter	__end,
		_Op	__o,
		_Fu &	__f,
		_Red	__r,
		_Result	__base,
		_Result &	__output,
		typename std::iterator_traits< _RAIter >::difference_type	__bound
	)

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

Parameters

__begin	Begin iterator of element sequence.
__end	End iterator of element sequence.
__o	User-supplied functor (comparator, predicate, adding functor, ...).
__f	Functor to process an element with __op (depends on desired functionality, e. g. for std::for_each(), ...).
__r	Functor to add a single __result to the already processed __elements (depends on functionality).
__base	Base value for reduction.
__output	Pointer to position where final result is written to
__bound	Maximum number of elements processed (e. g. for std::count_n()).

Returns: User-supplied functor (that may contain a part of the result).

Definition at line 66 of file omp_loop_static.h.

◆ __for_each_template_random_access_workstealing()

template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result >

_Op __gnu_parallel::__for_each_template_random_access_workstealing	(	_RAIter	__begin,
		_RAIter	__end,
		_Op	__op,
		_Fu &	__f,
		_Red	__r,
		_Result	__base,
		_Result &	__output,
		typename std::iterator_traits< _RAIter >::difference_type	__bound
	)

Work stealing algorithm for random access iterators.

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

Parameters

__begin	Begin iterator of element sequence.
__end	End iterator of element sequence.
__op	User-supplied functor (comparator, predicate, adding functor, ...).
__f	Functor to process an element with __op (depends on desired functionality, e. g. for std::for_each(), ...).
__r	Functor to add a single __result to the already processed elements (depends on functionality).
__base	Base value for reduction.
__output	Pointer to position where final result is written to
__bound	Maximum number of elements processed (e. g. for std::count_n()).

Returns: User-supplied functor (that may contain a part of the result).

Definition at line 99 of file workstealing.h.

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().

◆ __get_max_threads()

_ThreadIndex __gnu_parallel::__get_max_threads ( )

inline

Definition at line 85 of file base.h.

◆ __is_parallel()

bool __gnu_parallel::__is_parallel ( const _Parallelism __p )

inline

Definition at line 93 of file base.h.

◆ __is_sorted()

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.

Definition at line 51 of file checkers.h.

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

◆ __median_of_three_iterators()

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.

Definition at line 398 of file base.h.

Referenced by __qsb_divide().

◆ __merge_advance()

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.

Definition at line 171 of file merge.h.

References __merge_advance_movc(), and _GLIBCXX_CALL.

Referenced by __parallel_merge_advance(), and __sequential_multiway_merge().

◆ __merge_advance_movc()

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.

Definition at line 105 of file merge.h.

Referenced by __merge_advance().

◆ __merge_advance_usual()

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.

Definition at line 57 of file merge.h.

◆ __parallel_merge_advance() [1/2]

template<typename _RAIter1 , typename _RAIter3 , typename _Compare >

_RAIter3 __gnu_parallel::__parallel_merge_advance	(	_RAIter1 &	__begin1,
		_RAIter1	__end1,
		_RAIter1 &	__begin2,
		_RAIter1	__end2,
		_RAIter3	__target,
		typename std::iterator_traits< _RAIter1 >::difference_type	__max_length,
		_Compare	__comp
	)

inline

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

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

Parameters

__begin1	Begin iterator of first sequence.
__end1	End iterator of first sequence.
__begin2	Begin iterator of second sequence.
__end2	End iterator of second sequence.
__target	Target begin iterator.
__max_length	Maximum number of elements to merge.
__comp	Comparator.

Returns: Output end iterator.

Definition at line 223 of file merge.h.

References multiway_merge_exact_splitting(), and parallel_multiway_merge().

◆ __parallel_merge_advance() [2/2]

template<typename _RAIter1 , typename _RAIter2 , typename _RAIter3 , typename _Compare >

_RAIter3 __gnu_parallel::__parallel_merge_advance	(	_RAIter1 &	__begin1,
		_RAIter1	__end1,
		_RAIter2 &	__begin2,
		_RAIter2	__end2,
		_RAIter3	__target,
		typename std::iterator_traits< _RAIter1 >::difference_type	__max_length,
		_Compare	__comp
	)

inline

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

Parameters

__begin1	Begin iterator of first sequence.
__end1	End iterator of first sequence.
__begin2	Begin iterator of second sequence.
__end2	End iterator of second sequence.
__target	Target begin iterator.
__max_length	Maximum number of elements to merge.
__comp	Comparator.

Returns: Output end iterator.

Definition at line 195 of file merge.h.

References __merge_advance().

◆ __parallel_nth_element()

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.

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_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.

Definition at line 422 of file partition.h.

References __parallel_nth_element().

◆ __parallel_partial_sum()

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.

Definition at line 205 of file partial_sum.h.

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

◆ __parallel_partial_sum_basecase()

template<typename _IIter , typename _OutputIterator , typename _BinaryOperation >

_OutputIterator __gnu_parallel::__parallel_partial_sum_basecase	(	_IIter	__begin,
		_IIter	__end,
		_OutputIterator	__result,
		_BinaryOperation	__bin_op,
		typename std::iterator_traits< _IIter >::value_type	__value
	)

Base case prefix sum routine.

Parameters

__begin	Begin iterator of input sequence.
__end	End iterator of input sequence.
__result	Begin iterator of output sequence.
__bin_op	Associative binary function.
__value	Start value. Must be passed since the neutral element is unknown in general.

Returns: End iterator of output sequence.

Definition at line 58 of file partial_sum.h.

Referenced by __parallel_partial_sum_linear().

◆ __parallel_partial_sum_linear()

template<typename _IIter , typename _OutputIterator , typename _BinaryOperation >

_OutputIterator __gnu_parallel::__parallel_partial_sum_linear	(	_IIter	__begin,
		_IIter	__end,
		_OutputIterator	__result,
		_BinaryOperation	__bin_op,
		typename std::iterator_traits< _IIter >::difference_type	__n
	)

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

Parameters

__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.

Definition at line 89 of file partial_sum.h.

References __equally_split(), __parallel_partial_sum_basecase(), __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::partial_sum_dilation.

Referenced by __parallel_partial_sum().

◆ __parallel_partition()

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.

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_sort_qs_divide(), and __qsb_divide().

◆ __parallel_random_shuffle()

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.

Definition at line 522 of file random_shuffle.h.

References __parallel_random_shuffle_drs().

◆ __parallel_random_shuffle_drs()

template<typename _RAIter , typename _RandomNumberGenerator >

void __gnu_parallel::__parallel_random_shuffle_drs	(	_RAIter	__begin,
		_RAIter	__end,
		typename std::iterator_traits< _RAIter >::difference_type	__n,
		_ThreadIndex	__num_threads,
		_RandomNumberGenerator &	__rng
	)

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.

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().

◆ __parallel_random_shuffle_drs_pu()

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.

Definition at line 122 of file random_shuffle.h.

Referenced by __parallel_random_shuffle_drs().

◆ __parallel_set_difference()

template<typename _IIter , typename _OutputIterator , typename _Compare >

_OutputIterator __gnu_parallel::__parallel_set_difference	(	_IIter	__begin1,
		_IIter	__end1,
		_IIter	__begin2,
		_IIter	__end2,
		_OutputIterator	__result,
		_Compare	__comp
	)

inline

Definition at line 503 of file set_operations.h.

◆ __parallel_set_intersection()

template<typename _IIter , typename _OutputIterator , typename _Compare >

_OutputIterator __gnu_parallel::__parallel_set_intersection	(	_IIter	__begin1,
		_IIter	__end1,
		_IIter	__begin2,
		_IIter	__end2,
		_OutputIterator	__result,
		_Compare	__comp
	)

inline

Definition at line 489 of file set_operations.h.

◆ __parallel_set_operation()

template<typename _IIter , typename _OutputIterator , typename _Operation >

_OutputIterator __gnu_parallel::__parallel_set_operation	(	_IIter	__begin1,
		_IIter	__end1,
		_IIter	__begin2,
		_IIter	__end2,
		_OutputIterator	__result,
		_Operation	__op
	)

Definition at line 350 of file set_operations.h.

◆ __parallel_set_symmetric_difference()

template<typename _IIter , typename _OutputIterator , typename _Compare >

_OutputIterator __gnu_parallel::__parallel_set_symmetric_difference	(	_IIter	__begin1,
		_IIter	__end1,
		_IIter	__begin2,
		_IIter	__end2,
		_OutputIterator	__result,
		_Compare	__comp
	)

inline

Definition at line 517 of file set_operations.h.

◆ __parallel_set_union()

template<typename _IIter , typename _OutputIterator , typename _Compare >

_OutputIterator __gnu_parallel::__parallel_set_union	(	_IIter	__begin1,
		_IIter	__end1,
		_IIter	__begin2,
		_IIter	__end2,
		_OutputIterator	__result,
		_Compare	__comp
	)

inline

Definition at line 475 of file set_operations.h.

◆ __parallel_sort() [1/7]

template<bool __stable, typename _RAIter , typename _Compare >

void __gnu_parallel::__parallel_sort	(	_RAIter	__begin,
		_RAIter	__end,
		_Compare	__comp,
		balanced_quicksort_tag	__parallelism
	)

inline

Choose balanced quicksort for parallel sorting.

Parameters

__begin	Begin iterator of input sequence.
__end	End iterator of input sequence.
__comp	Comparator.

Template Parameters

__stable Sort stable.

Definition at line 161 of file sort.h.

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

Here is the call graph for this function:

◆ __parallel_sort() [2/7]

template<bool __stable, typename _RAIter , typename _Compare >

void __gnu_parallel::__parallel_sort	(	_RAIter	__begin,
		_RAIter	__end,
		_Compare	__comp,
		default_parallel_tag	__parallelism
	)

inline

Choose multiway mergesort with exact splitting, for parallel sorting.

Parameters

__begin	Begin iterator of input sequence.
__end	End iterator of input sequence.
__comp	Comparator.

Template Parameters

__stable Sort stable.

Definition at line 183 of file sort.h.

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

Here is the call graph for this function:

◆ __parallel_sort() [3/7]

template<bool __stable, typename _RAIter , typename _Compare >

void __gnu_parallel::__parallel_sort	(	_RAIter	__begin,
		_RAIter	__end,
		_Compare	__comp,
		multiway_mergesort_exact_tag	__parallelism
	)

inline

Choose multiway mergesort with exact splitting, for parallel sorting.

Parameters

__begin	Begin iterator of input sequence.
__end	End iterator of input sequence.
__comp	Comparator.

Template Parameters

__stable Sort stable.

Definition at line 99 of file sort.h.

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

Here is the call graph for this function:

◆ __parallel_sort() [4/7]

template<bool __stable, typename _RAIter , typename _Compare >

void __gnu_parallel::__parallel_sort	(	_RAIter	__begin,
		_RAIter	__end,
		_Compare	__comp,
		multiway_mergesort_sampling_tag	__parallelism
	)

inline

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

Parameters

__begin	Begin iterator of input sequence.
__end	End iterator of input sequence.
__comp	Comparator.

Template Parameters

__stable Sort stable.

Definition at line 120 of file sort.h.

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

Here is the call graph for this function:

◆ __parallel_sort() [5/7]

template<bool __stable, typename _RAIter , typename _Compare >

void __gnu_parallel::__parallel_sort	(	_RAIter	__begin,
		_RAIter	__end,
		_Compare	__comp,
		multiway_mergesort_tag	__parallelism
	)

inline

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

Parameters

__begin	Begin iterator of input sequence.
__end	End iterator of input sequence.
__comp	Comparator.

Template Parameters

__stable Sort stable.

Definition at line 75 of file sort.h.

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

Here is the call graph for this function:

◆ __parallel_sort() [6/7]

template<bool __stable, typename _RAIter , typename _Compare >

void __gnu_parallel::__parallel_sort	(	_RAIter	__begin,
		_RAIter	__end,
		_Compare	__comp,
		parallel_tag	__parallelism
	)

inline

Choose a parallel sorting algorithm.

Parameters

__begin	Begin iterator of input sequence.
__end	End iterator of input sequence.
__comp	Comparator.

Template Parameters

__stable Sort stable.

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().

Here is the call graph for this function:

◆ __parallel_sort() [7/7]

template<bool __stable, typename _RAIter , typename _Compare >

void __gnu_parallel::__parallel_sort	(	_RAIter	__begin,
		_RAIter	__end,
		_Compare	__comp,
		quicksort_tag	__parallelism
	)

inline

Choose quicksort for parallel sorting.

Parameters

__begin	Begin iterator of input sequence.
__end	End iterator of input sequence.
__comp	Comparator.

Template Parameters

__stable Sort stable.

Definition at line 140 of file sort.h.

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

Here is the call graph for this function:

◆ __parallel_sort_qs()

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.

Definition at line 154 of file quicksort.h.

References __parallel_sort_qs_conquer(), and _GLIBCXX_CALL.

Referenced by __parallel_sort(), and __parallel_sort().

◆ __parallel_sort_qs_conquer()

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.

Definition at line 101 of file quicksort.h.

References __parallel_sort_qs_conquer(), __parallel_sort_qs_divide(), and __gnu_parallel::_Settings::get().

Referenced by __parallel_sort_qs(), and __parallel_sort_qs_conquer().

◆ __parallel_sort_qs_divide()

template<typename _RAIter , typename _Compare >

std::iterator_traits< _RAIter >::difference_type __gnu_parallel::__parallel_sort_qs_divide	(	_RAIter	__begin,
		_RAIter	__end,
		_Compare	__comp,
		typename std::iterator_traits< _RAIter >::difference_type	__pivot_rank,
		typename std::iterator_traits< _RAIter >::difference_type	__num_samples,
		_ThreadIndex	__num_threads
	)

Unbalanced quicksort divide step.

Parameters

__begin	Begin iterator of subsequence.
__end	End iterator of subsequence.
__comp	Comparator.
__pivot_rank	Desired __rank of the pivot.
__num_samples	Choose pivot from that many samples.
__num_threads	Number of threads that are allowed to work on this part.

Definition at line 51 of file quicksort.h.

References __parallel_partition(), and std::min().

Referenced by __parallel_sort_qs_conquer().

◆ __parallel_sort_qsb()

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.

Definition at line 433 of file balanced_quicksort.h.

References __qsb_conquer(), __rd_log2(), _GLIBCXX_CALL, and __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_elements_leftover.

Referenced by __parallel_sort(), and __parallel_sort().

◆ __parallel_unique_copy() [1/2]

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.

Definition at line 186 of file unique_copy.h.

References __parallel_unique_copy().

◆ __parallel_unique_copy() [2/2]

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.

Definition at line 50 of file unique_copy.h.

References __equally_split(), and _GLIBCXX_CALL.

Referenced by __parallel_unique_copy().

◆ __qsb_conquer()

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.

Definition at line 174 of file balanced_quicksort.h.

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().

◆ __qsb_divide()

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

Definition at line 103 of file balanced_quicksort.h.

References __median_of_three_iterators(), and __parallel_partition().

Referenced by __qsb_conquer().

◆ __qsb_local_sort_with_helping()

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.

Definition at line 250 of file balanced_quicksort.h.

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().

◆ __random_number_pow2()

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.

Definition at line 115 of file random_shuffle.h.

Referenced by __parallel_random_shuffle_drs_pu(), and __sequential_random_shuffle().

◆ __rd_log2()

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.

Definition at line 102 of file base.h.

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().

◆ __round_up_to_pow2()

template<typename _Tp >

_Tp __gnu_parallel::__round_up_to_pow2 ( _Tp __x )

Round up to the next greater power of 2.

Parameters

__x	_Integer to round up

Definition at line 248 of file random_shuffle.h.

References __rd_log2().

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

◆ __search_template()

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.

Definition at line 81 of file search.h.

References __calc_borders(), __equally_split(), _GLIBCXX_CALL, and std::min().

◆ __sequential_multiway_merge()

template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >

_RAIter3 __gnu_parallel::__sequential_multiway_merge	(	_RAIterIterator	__seqs_begin,
		_RAIterIterator	__seqs_end,
		_RAIter3	__target,
		const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &	__sentinel,
		_DifferenceTp	__length,
		_Compare	__comp
	)

Sequential multi-way merging switch.

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

Parameters

__seqs_begin	Begin iterator of iterator pair input sequence.
__seqs_end	End iterator of iterator pair input sequence.
__target	Begin iterator of output sequence.
__comp	Comparator.
__length	Maximum length to merge, possibly larger than the number of elements available.
__sentinel	The sequences have __a __sentinel element.

Returns: End iterator of output sequence.

Definition at line 920 of file multiway_merge.h.

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

Referenced by multiway_merge(), and multiway_merge_sentinels().

◆ __sequential_random_shuffle()

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.

Definition at line 410 of file random_shuffle.h.

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().

◆ __shrink()

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.

Definition at line 70 of file list_partition.h.

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

Referenced by __shrink_and_double().

◆ __shrink_and_double()

template<typename _IIter >

void __gnu_parallel::__shrink_and_double	(	std::vector< _IIter > &	__os_starts,
		size_t &	__count_to_two,
		size_t &	__range_length,
		const bool	__make_twice
	)

Shrinks and doubles the ranges.

Parameters

__os_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

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()

void __gnu_parallel::__yield ( )

inline

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

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

Referenced by __for_each_template_random_access_workstealing(), and __qsb_local_sort_with_helping().

◆ list_partition()

template<typename _IIter , typename _FunctorType >

size_t __gnu_parallel::list_partition	(	const _IIter	__begin,
		const _IIter	__end,
		_IIter *	__starts,
		size_t *	__lengths,
		const int	__num_parts,
		_FunctorType &	__f,
		int	__oversampling = `0`
	)

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

The function needs only one pass over the sequence.

Parameters

__begin	Begin iterator of input sequence.
__end	End iterator of input sequence.
__starts	Start iterators for the resulting parts, dimension `__num_parts+1`. For convenience, `__starts` [__num_parts] contains the end iterator of the sequence.
__lengths	Length of the resulting parts.
__num_parts	Number of parts to split the sequence into.
__f	Functor to be applied to each element by traversing __it
__oversampling	Oversampling factor. If 0, then the partitions will differ in at most $\sqrt{\mathrm{end} - \mathrm{begin}}$ elements. Otherwise, the ratio between the longest and the shortest part is bounded by $1/(\mathrm{oversampling} \cdot \mathrm{num\_parts})$

Returns: Length of the whole sequence.

Definition at line 101 of file list_partition.h.

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

◆ max()

template<typename _Tp >

const _Tp & __gnu_parallel::max	(	const _Tp &	__a,
		const _Tp &	__b
	)

inline

Equivalent to std::max.

Definition at line 150 of file base.h.

◆ min()

template<typename _Tp >

const _Tp & __gnu_parallel::min	(	const _Tp &	__a,
		const _Tp &	__b
	)

inline

Equivalent to std::min.

Definition at line 144 of file base.h.

Referenced by __for_each_template_random_access_workstealing().

◆ multiseq_partition()

template<typename _RanSeqs , typename _RankType , typename _RankIterator , typename _Compare >

void __gnu_parallel::multiseq_partition	(	_RanSeqs	__begin_seqs,
		_RanSeqs	__end_seqs,
		_RankType	__rank,
		_RankIterator	__begin_offsets,
		_Compare	__comp = `std::less< typename std::iterator_traits<typename std::iterator_traits<_RanSeqs>::value_type:: first_type>::value_type>()`
	)

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

Parameters

__begin_seqs	Begin of the sequence of iterator pairs.
__end_seqs	End of the sequence of iterator pairs.
__rank	The global rank to partition at.
__begin_offsets	A random-access __sequence __begin where the __result will be stored in. Each element of the sequence is an iterator that points to the first element on the greater part of the respective __sequence.
__comp	The ordering functor, defaults to std::less<_Tp>.

Definition at line 122 of file multiseq_selection.h.

References __rd_log2(), _GLIBCXX_CALL, std::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::max(), std::min(), std::priority_queue< _Tp, _Sequence, _Compare >::pop(), std::priority_queue< _Tp, _Sequence, _Compare >::push(), and std::priority_queue< _Tp, _Sequence, _Compare >::top().

Referenced by multiway_merge_exact_splitting().

◆ multiseq_selection()

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.

Definition at line 388 of file multiseq_selection.h.

References __rd_log2(), __round_up_to_pow2(), _GLIBCXX_CALL, std::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::max(), std::min(), std::priority_queue< _Tp, _Sequence, _Compare >::pop(), std::priority_queue< _Tp, _Sequence, _Compare >::push(), and std::priority_queue< _Tp, _Sequence, _Compare >::top().

◆ multiway_merge() [1/5]

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::exact_tag	__tag
	)

Definition at line 1444 of file multiway_merge.h.

◆ multiway_merge() [2/5]

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::sampling_tag	__tag
	)

Definition at line 1487 of file multiway_merge.h.

◆ multiway_merge() [3/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::multiway_merge	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		__gnu_parallel::sequential_tag
	)

Multiway Merge Frontend.

Merge the sequences specified by seqs_begin and __seqs_end into __target. __seqs_begin and __seqs_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the _M_end of the same sequence in their second entry.

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

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

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

This function will merge the input sequences:

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

Example:

  int sequences[10][10];
  for (int __i = 0; __i < 10; ++__i)
    for (int __j = 0; __i < 10; ++__j)
      sequences[__i][__j] = __j;

  int __out[33];
  std::vector<std::pair<int*> > seqs;
  for (int __i = 0; __i < 10; ++__i)
    { seqs.push(std::make_pair<int*>(sequences[__i],
                                     sequences[__i] + 10)) }

  multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);

See also: stable_multiway_merge

Precondition: All input sequences must be sorted.; Target must provide enough space to merge out length elements or the number of elements in all sequences, whichever is smaller.

Postcondition: [__target, return __value) contains merged __elements from the input sequences.; return __value - __target = min(__length, number of elements in all sequences).

Template Parameters

_RAIterPairIterator	iterator over sequence of pairs of iterators
_RAIterOut	iterator over target sequence
_DifferenceTp	difference type for the sequence
_Compare	strict weak ordering type to compare elements in sequences

Parameters

__seqs_begin	__begin of sequence __sequence
__seqs_end	_M_end of sequence __sequence
__target	target sequence to merge to.
__comp	strict weak ordering to use for element comparison.
__length	Maximum length to merge, possibly larger than the number of elements available.

Returns: _M_end iterator of output sequence

Definition at line 1418 of file multiway_merge.h.

References __sequential_multiway_merge(), and _GLIBCXX_CALL.

◆ multiway_merge() [4/5]

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,
		default_parallel_tag	__tag
	)

Definition at line 1544 of file multiway_merge.h.

◆ multiway_merge() [5/5]

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,
		parallel_tag	__tag = `parallel_tag(0)`
	)

Definition at line 1530 of file multiway_merge.h.

◆ multiway_merge_3_variant()

template<template< typename _RAI, typename _Cp > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >

_RAIter3 __gnu_parallel::multiway_merge_3_variant	(	_RAIterIterator	__seqs_begin,
		_RAIterIterator	__seqs_end,
		_RAIter3	__target,
		_DifferenceTp	__length,
		_Compare	__comp
	)

Highly efficient 3-way merging procedure.

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

This works well for merging up to 4 sequences.

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

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

Parameters

__seqs_begin	Begin iterator of iterator pair input sequence.
__seqs_end	End iterator of iterator pair input sequence.
__target	Begin iterator of output sequence.
__comp	Comparator.
__length	Maximum length to merge, less equal than the total number of elements available.

Returns: End iterator of output sequence.

Definition at line 241 of file multiway_merge.h.

References _GLIBCXX_CALL.

◆ multiway_merge_4_variant()

template<template< typename _RAI, typename _Cp > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >

_RAIter3 __gnu_parallel::multiway_merge_4_variant	(	_RAIterIterator	__seqs_begin,
		_RAIterIterator	__seqs_end,
		_RAIter3	__target,
		_DifferenceTp	__length,
		_Compare	__comp
	)

Highly efficient 4-way merging procedure.

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

This works well for merging up to 4 sequences.

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

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

Parameters

__seqs_begin	Begin iterator of iterator pair input sequence.
__seqs_end	End iterator of iterator pair input sequence.
__target	Begin iterator of output sequence.
__comp	Comparator.
__length	Maximum length to merge, less equal than the total number of elements available.

Returns: End iterator of output sequence.

Definition at line 360 of file multiway_merge.h.

References _GLIBCXX_CALL.

◆ multiway_merge_exact_splitting()

template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType >

void __gnu_parallel::multiway_merge_exact_splitting	(	_RAIterIterator	__seqs_begin,
		_RAIterIterator	__seqs_end,
		_DifferenceType	__length,
		_DifferenceType	__total_length,
		_Compare	__comp,
		std::vector< std::pair< _DifferenceType, _DifferenceType > > *	__pieces
	)

Exact splitting for parallel multiway-merge routine.

None of the passed sequences may be empty.

Definition at line 1120 of file multiway_merge.h.

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

Referenced by __parallel_merge_advance().

◆ multiway_merge_loser_tree()

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.

Definition at line 491 of file multiway_merge.h.

References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_LENGTH.

◆ multiway_merge_loser_tree_sentinel()

template<typename _UnguardedLoserTree , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >

_RAIter3 __gnu_parallel::multiway_merge_loser_tree_sentinel	(	_RAIterIterator	__seqs_begin,
		_RAIterIterator	__seqs_end,
		_RAIter3	__target,
		const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &	__sentinel,
		_DifferenceTp	__length,
		_Compare	__comp
	)

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

Template Parameters

_UnguardedLoserTree Loser Tree variant to use for the unguarded merging.

Parameters

__seqs_begin	Begin iterator of iterator pair input sequence.
__seqs_end	End iterator of iterator pair input sequence.
__target	Begin iterator of output sequence.
__comp	Comparator.
__length	Maximum length to merge, less equal than the total number of elements available.

Returns: End iterator of output sequence.

Definition at line 662 of file multiway_merge.h.

References __is_sorted(), and _GLIBCXX_CALL.

◆ multiway_merge_loser_tree_unguarded()

template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >

_RAIter3 __gnu_parallel::multiway_merge_loser_tree_unguarded	(	_RAIterIterator	__seqs_begin,
		_RAIterIterator	__seqs_end,
		_RAIter3	__target,
		const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &	__sentinel,
		_DifferenceTp	__length,
		_Compare	__comp
	)

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

Merging is done using the LoserTree class _LT.

Stability is selected by the used LoserTrees.

Precondition: No input will run out of elements during the merge.

Parameters

__seqs_begin	Begin iterator of iterator pair input sequence.
__seqs_end	End iterator of iterator pair input sequence.
__target	Begin iterator of output sequence.
__comp	Comparator.
__length	Maximum length to merge, less equal than the total number of elements available.

Returns: End iterator of output sequence.

Definition at line 574 of file multiway_merge.h.

References _GLIBCXX_CALL.

◆ multiway_merge_sampling_splitting()

template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType >

void __gnu_parallel::multiway_merge_sampling_splitting	(	_RAIterIterator	__seqs_begin,
		_RAIterIterator	__seqs_end,
		_DifferenceType	__length,
		_DifferenceType	__total_length,
		_Compare	__comp,
		std::vector< std::pair< _DifferenceType, _DifferenceType > > *	__pieces
	)

Sampling based splitting for parallel multiway-merge routine.

Definition at line 1035 of file multiway_merge.h.

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

◆ multiway_merge_sentinels() [1/5]

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::exact_tag	__tag
	)

Definition at line 1808 of file multiway_merge.h.

◆ multiway_merge_sentinels() [2/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::multiway_merge_sentinels	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		__gnu_parallel::sequential_tag
	)

Multiway Merge Frontend.

Merge the sequences specified by seqs_begin and __seqs_end into __target. __seqs_begin and __seqs_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the _M_end of the same sequence in their second entry.

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

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

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

This function will merge the input sequences:

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

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

Example:

  int sequences[10][11];
  for (int __i = 0; __i < 10; ++__i)
    for (int __j = 0; __i < 11; ++__j)
      sequences[__i][__j] = __j; // __last one is sentinel!

  int __out[33];
  std::vector<std::pair<int*> > seqs;
  for (int __i = 0; __i < 10; ++__i)
    { seqs.push(std::make_pair<int*>(sequences[__i],
                                     sequences[__i] + 10)) }

  multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);

Precondition: All input sequences must be sorted.; Target must provide enough space to merge out length elements or the number of elements in all sequences, whichever is smaller.; For each __i, __seqs_begin[__i].second must be the end marker of the sequence, but also reference the one more __sentinel element.

Postcondition: [__target, return __value) contains merged __elements from the input sequences.; return __value - __target = min(__length, number of elements in all sequences).

See also: stable_multiway_merge_sentinels

Template Parameters

_RAIterPairIterator	iterator over sequence of pairs of iterators
_RAIterOut	iterator over target sequence
_DifferenceTp	difference type for the sequence
_Compare	strict weak ordering type to compare elements in sequences

Parameters

__seqs_begin	__begin of sequence __sequence
__seqs_end	_M_end of sequence __sequence
__target	target sequence to merge to.
__comp	strict weak ordering to use for element comparison.
__length	Maximum length to merge, possibly larger than the number of elements available.

Returns: _M_end iterator of output sequence

Definition at line 1782 of file multiway_merge.h.

References __sequential_multiway_merge(), and _GLIBCXX_CALL.

◆ multiway_merge_sentinels() [3/5]

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,
		default_parallel_tag	__tag
	)

Definition at line 1911 of file multiway_merge.h.

◆ multiway_merge_sentinels() [4/5]

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,
		parallel_tag	__tag = `parallel_tag(0)`
	)

Definition at line 1894 of file multiway_merge.h.

◆ multiway_merge_sentinels() [5/5]

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,
		sampling_tag	__tag
	)

Definition at line 1851 of file multiway_merge.h.

◆ parallel_multiway_merge()

template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Splitter , typename _Compare >

_RAIter3 __gnu_parallel::parallel_multiway_merge	(	_RAIterIterator	__seqs_begin,
		_RAIterIterator	__seqs_end,
		_RAIter3	__target,
		_Splitter	__splitter,
		_DifferenceTp	__length,
		_Compare	__comp,
		_ThreadIndex	__num_threads
	)

Parallel multi-way merge routine.

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

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

Template Parameters

_Splitter	functor to split input (either __exact or sampling based)
__stable	Stable merging incurs a performance penalty.
__sentinel	Ignored.

Parameters

__seqs_begin	Begin iterator of iterator pair input sequence.
__seqs_end	End iterator of iterator pair input sequence.
__target	Begin iterator of output sequence.
__comp	Comparator.
__length	Maximum length to merge, possibly larger than the number of elements available.

Returns: End iterator of output sequence.

Definition at line 1225 of file multiway_merge.h.

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

Referenced by __parallel_merge_advance().

◆ parallel_sort_mwms()

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.

Definition at line 395 of file multiway_mergesort.h.

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.

◆ parallel_sort_mwms_pu()

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.

Definition at line 308 of file multiway_mergesort.h.

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().

◆ stable_multiway_merge() [1/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::stable_multiway_merge	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		__gnu_parallel::exact_tag	__tag
	)

Definition at line 1585 of file multiway_merge.h.

◆ stable_multiway_merge() [2/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::stable_multiway_merge	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		__gnu_parallel::sequential_tag
	)

Definition at line 1559 of file multiway_merge.h.

◆ stable_multiway_merge() [3/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::stable_multiway_merge	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		default_parallel_tag	__tag
	)

Definition at line 1688 of file multiway_merge.h.

◆ stable_multiway_merge() [4/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::stable_multiway_merge	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		parallel_tag	__tag = `parallel_tag(0)`
	)

Definition at line 1671 of file multiway_merge.h.

◆ stable_multiway_merge() [5/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::stable_multiway_merge	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		sampling_tag	__tag
	)

Definition at line 1628 of file multiway_merge.h.

◆ stable_multiway_merge_sentinels() [1/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::stable_multiway_merge_sentinels	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		__gnu_parallel::exact_tag	__tag
	)

Definition at line 1955 of file multiway_merge.h.

◆ stable_multiway_merge_sentinels() [2/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::stable_multiway_merge_sentinels	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		__gnu_parallel::sequential_tag
	)

Definition at line 1929 of file multiway_merge.h.

◆ stable_multiway_merge_sentinels() [3/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::stable_multiway_merge_sentinels	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		default_parallel_tag	__tag
	)

Definition at line 2060 of file multiway_merge.h.

◆ stable_multiway_merge_sentinels() [4/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::stable_multiway_merge_sentinels	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		parallel_tag	__tag = `parallel_tag(0)`
	)

Definition at line 2042 of file multiway_merge.h.

◆ stable_multiway_merge_sentinels() [5/5]

template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >

_RAIterOut __gnu_parallel::stable_multiway_merge_sentinels	(	_RAIterPairIterator	__seqs_begin,
		_RAIterPairIterator	__seqs_end,
		_RAIterOut	__target,
		_DifferenceTp	__length,
		_Compare	__comp,
		sampling_tag	__tag
	)

Definition at line 1998 of file multiway_merge.h.

Variable Documentation

◆ _CASable_bits

const int __gnu_parallel::_CASable_bits

static

Number of bits of _CASable.

Definition at line 130 of file types.h.

Referenced by __decode2(), and __encode2().

◆ _CASable_mask

const _CASable __gnu_parallel::_CASable_mask

static

_CASable with the right half of bits set to 1.

Definition at line 133 of file types.h.

Referenced by __decode2().

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ _BinIndex

◆ _CASable

◆ _SequenceIndex

◆ _ThreadIndex

Enumeration Type Documentation

◆ _AlgorithmStrategy

◆ _FindAlgorithm

◆ _MultiwayMergeAlgorithm

◆ _Parallelism

◆ _PartialSumAlgorithm

◆ _SortAlgorithm

◆ _SplittingAlgorithm

Function Documentation

◆ __add_omp()

◆ __calc_borders()

◆ __cas_omp()

◆ __compare_and_swap()

◆ __copy_tail()

◆ __decode2()

◆ __determine_samples()

◆ __encode2()

◆ __equally_split()

◆ __equally_split_point()

◆ __fetch_and_add()

◆ __find_template() [1/4]

◆ __find_template() [2/4]

◆ __find_template() [3/4]

◆ __find_template() [4/4]

◆ __for_each_template_random_access()

◆ __for_each_template_random_access_ed()

◆ __for_each_template_random_access_omp_loop()

◆ __for_each_template_random_access_omp_loop_static()

◆ __for_each_template_random_access_workstealing()

◆ __get_max_threads()

◆ __is_parallel()

◆ __is_sorted()

◆ __median_of_three_iterators()

◆ __merge_advance()

◆ __merge_advance_movc()

◆ __merge_advance_usual()

◆ __parallel_merge_advance() [1/2]

◆ __parallel_merge_advance() [2/2]

◆ __parallel_nth_element()

◆ __parallel_partial_sort()

◆ __parallel_partial_sum()

◆ __parallel_partial_sum_basecase()

◆ __parallel_partial_sum_linear()

◆ __parallel_partition()

◆ __parallel_random_shuffle()

◆ __parallel_random_shuffle_drs()

◆ __parallel_random_shuffle_drs_pu()

◆ __parallel_set_difference()

◆ __parallel_set_intersection()

◆ __parallel_set_operation()

◆ __parallel_set_symmetric_difference()

◆ __parallel_set_union()

◆ __parallel_sort() [1/7]

◆ __parallel_sort() [2/7]

◆ __parallel_sort() [3/7]

◆ __parallel_sort() [4/7]

◆ __parallel_sort() [5/7]

◆ __parallel_sort() [6/7]

◆ __parallel_sort() [7/7]

◆ __parallel_sort_qs()

◆ __parallel_sort_qs_conquer()

◆ __parallel_sort_qs_divide()

◆ __parallel_sort_qsb()

◆ __parallel_unique_copy() [1/2]

◆ __parallel_unique_copy() [2/2]

◆ __qsb_conquer()

◆ __qsb_divide()

◆ __qsb_local_sort_with_helping()

◆ __random_number_pow2()