__gnu_parallel Namespace Reference

GNU parallel code for public use. More...

Classes
struct	_QSBThreadLocal
	Information local to one thread in the parallel quicksort run. More...
class	_EqualFromLess
	Constructs predicate for equality from strict weak ordering predicate. More...
class	__unary_negate
	Similar to std::unary_negate, but giving the argument types explicitly. More...
class	__binder1st
	Similar to std::binder1st, but giving the argument types explicitly. More...
class	__binder2nd
	Similar to std::binder2nd, but giving the argument types explicitly. More...
struct	_EqualTo
	Similar to std::equal_to, but allows two different types. More...
struct	_Less
	Similar to std::less, but allows two different types. More...
struct	_Less< _Tp, _Tp >
struct	_Plus
	Similar to std::plus, but allows two different types. More...
struct	_Plus< _Tp, _Tp, _Tp >
struct	_Multiplies
	Similar to std::multiplies, but allows two different types. More...
struct	_Multiplies< _Tp, _Tp, _Tp >
class	_PseudoSequenceIterator
	_Iterator associated with __gnu_parallel::_PseudoSequence. If features the usual random-access iterator functionality. More...
class	_PseudoSequence
	Sequence that conceptually consists of multiple copies of the same element. The copies are not stored explicitly, of course. More...
struct	__generic_find_selector
	Base class of all __gnu_parallel::__find_template selectors. More...
struct	__find_if_selector
	Test predicate on a single element, used for std::find() and std::find_if (). More...
struct	__adjacent_find_selector
	Test predicate on two adjacent elements. More...
struct	__mismatch_selector
	Test inverted predicate on a single element. More...
struct	__find_first_of_selector
	Test predicate on several elements. More...
struct	__generic_for_each_selector
	Generic __selector for embarrassingly parallel functions. More...
struct	__for_each_selector
	std::for_each() selector. More...
struct	__generate_selector
	std::generate() selector. More...
struct	__fill_selector
	std::fill() selector. More...
struct	__transform1_selector
	std::transform() __selector, one input sequence variant. More...
struct	__transform2_selector
	std::transform() __selector, two input sequences variant. More...
struct	__replace_selector
	std::replace() selector. More...
struct	__replace_if_selector
	std::replace() selector. More...
struct	__count_selector
	std::count() selector. More...
struct	__count_if_selector
	std::count_if () selector. More...
struct	__accumulate_selector
	std::accumulate() selector. More...
struct	__inner_product_selector
	std::inner_product() selector. More...
struct	__identity_selector
	Selector that just returns the passed iterator. More...
struct	__adjacent_difference_selector
	Selector that returns the difference between two adjacent __elements. More...
struct	_Nothing
	Functor doing nothing. More...
struct	_DummyReduct
	Reduction function doing nothing. More...
struct	__min_element_reduct
	Reduction for finding the maximum element, using a comparator. More...
struct	__max_element_reduct
	Reduction for finding the maximum element, using a comparator. More...
struct	__accumulate_binop_reduct
	General reduction, using a binary operator. More...
class	_IteratorPair
	A pair of iterators. The usual iterator operations are applied to both child iterators. More...
class	_IteratorTriple
	A triple of iterators. The usual iterator operations are applied to all three child iterators. More...
class	_LoserTreeBase
	Guarded loser/tournament tree. More...
class	_LoserTree
	Stable _LoserTree variant. More...
class	_LoserTree< false, _Tp, _Compare >
	Unstable _LoserTree variant. More...
class	_LoserTreePointerBase
	Base class of _Loser Tree implementation using pointers. More...
class	_LoserTreePointer
	Stable _LoserTree implementation. More...
class	_LoserTreePointer< false, _Tp, _Compare >
	Unstable _LoserTree implementation. More...
class	_LoserTreeUnguardedBase
	Base class for unguarded _LoserTree implementation. More...
class	_LoserTreeUnguarded
	Stable implementation of unguarded _LoserTree. More...
class	_LoserTreeUnguarded< false, _Tp, _Compare >
	Non-Stable implementation of unguarded _LoserTree. More...
class	_LoserTreePointerUnguardedBase
	Unguarded loser tree, keeping only pointers to the elements in the tree structure. More...
class	_LoserTreePointerUnguarded
	Stable unguarded _LoserTree variant storing pointers. More...
class	_LoserTreePointerUnguarded< false, _Tp, _Compare >
	Unstable unguarded _LoserTree variant storing pointers. More...
class	_Lexicographic
	Compare __a pair of types lexicographically, ascending. More...
class	_LexicographicReverse
	Compare __a pair of types lexicographically, descending. More...
class	_GuardedIterator
	_Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. More...
class	_UnguardedIterator
struct	_LoserTreeTraits
	Traits for determining whether the loser tree should use pointers or copies. More...
struct	__multiway_merge_3_variant_sentinel_switch
	Switch for 3-way merging with __sentinels turned off. More...
struct	__multiway_merge_3_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
	Switch for 3-way merging with __sentinels turned on. More...
struct	__multiway_merge_4_variant_sentinel_switch
	Switch for 4-way merging with __sentinels turned off. More...
struct	__multiway_merge_4_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
	Switch for 4-way merging with __sentinels turned on. More...
struct	__multiway_merge_k_variant_sentinel_switch
	Switch for k-way merging with __sentinels turned on. More...
struct	__multiway_merge_k_variant_sentinel_switch< false, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >
	Switch for k-way merging with __sentinels turned off. More...
struct	_SamplingSorter
	Stable sorting functor. More...
struct	_SamplingSorter< false, _RAIter, _StrictWeakOrdering >
	Non-__stable sorting functor. More...
struct	_Piece
	Subsequence description. More...
struct	_PMWMSSortingData
	Data accessed by all threads. More...
struct	_SplitConsistently
	Split consistently. More...
struct	_SplitConsistently< true, _RAIter, _Compare, _SortingPlacesIterator >
	Split by exact splitting. More...
struct	_SplitConsistently< false, _RAIter, _Compare, _SortingPlacesIterator >
	Split by sampling. More...
struct	__possibly_stable_sort
struct	__possibly_stable_sort< true, _RAIter, _Compare >
struct	__possibly_stable_sort< false, _RAIter, _Compare >
struct	__possibly_stable_multiway_merge
struct	__possibly_stable_multiway_merge< true, Seq_RAIter, _RAIter, _Compare, _DiffType >
struct	__possibly_stable_multiway_merge< false, Seq_RAIter, _RAIter, _Compare, _DiffType >
class	_RestrictedBoundedConcurrentQueue
	Double-ended queue of bounded size, allowing lock-free atomic access. push_front() and pop_front() must not be called concurrently to each other, while pop_back() can be called concurrently at all times. empty(), size(), and top() are intentionally not provided. Calling them would not make sense in a concurrent setting. More...
class	_RandomNumber
	Random number generator, based on the Mersenne twister. More...
struct	_DRandomShufflingGlobalData
	Data known to every thread participating in __gnu_parallel::__parallel_random_shuffle(). More...
struct	_DRSSorterPU
	Local data for a thread participating in __gnu_parallel::__parallel_random_shuffle(). More...
struct	__symmetric_difference_func
struct	__difference_func
struct	__intersection_func
struct	__union_func
struct	_Settings
struct	sequential_tag
	Forces sequential execution at compile time. More...
struct	parallel_tag
	Recommends parallel execution at compile time, optionally using a user-specified number of threads. More...
struct	default_parallel_tag
	Recommends parallel execution using the default parallel algorithm. More...
struct	balanced_tag
	Recommends parallel execution using dynamic load-balancing at compile time. More...
struct	unbalanced_tag
	Recommends parallel execution using static load-balancing at compile time. More...
struct	omp_loop_tag
	Recommends parallel execution using OpenMP dynamic load-balancing at compile time. More...
struct	omp_loop_static_tag
	Recommends parallel execution using OpenMP static load-balancing at compile time. More...
struct	find_tag
	Base class for for std::find() variants. More...
struct	exact_tag
	Forces parallel merging with exact splitting, at compile time. More...
struct	sampling_tag
	Forces parallel merging with exact splitting, at compile time. More...
struct	multiway_mergesort_tag
	Forces parallel sorting using multiway mergesort at compile time. More...
struct	multiway_mergesort_exact_tag
	Forces parallel sorting using multiway mergesort with exact splitting at compile time. More...
struct	multiway_mergesort_sampling_tag
	Forces parallel sorting using multiway mergesort with splitting by sampling at compile time. More...
struct	quicksort_tag
	Forces parallel sorting using unbalanced quicksort at compile time. More...
struct	balanced_quicksort_tag
	Forces parallel sorting using balanced quicksort at compile time. More...
struct	growing_blocks_tag
	Selects the growing block size variant for std::find(). More...
struct	constant_size_blocks_tag
	Selects the constant block size variant for std::find(). More...
struct	equal_split_tag
	Selects the equal splitting variant for std::find(). More...
struct	_Job
	One __job for a certain thread. More...

Typedefs
typedef unsigned short	_BinIndex
	Type to hold the index of a bin. More...
typedef uint64_t	_SequenceIndex
	Unsigned integer to index __elements. The total number of elements for each algorithm must fit into this type. More...
typedef uint16_t	_ThreadIndex
	Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit into this type. More...
typedef int64_t	_CASable
	Longest compare-and-swappable integer type on this platform. More...

Enumerations
enum	_Parallelism {   sequential, parallel_unbalanced, parallel_balanced, parallel_omp_loop,   parallel_omp_loop_static, parallel_taskqueue }
	Run-time equivalents for the compile-time tags. More...
enum	_AlgorithmStrategy { heuristic, force_sequential, force_parallel }
	Strategies for run-time algorithm selection: More...
enum	_SortAlgorithm { MWMS, QS, QS_BALANCED }
	Sorting algorithms: More...
enum	_MultiwayMergeAlgorithm { LOSER_TREE }
	Merging algorithms: More...
enum	_PartialSumAlgorithm { RECURSIVE, LINEAR }
	Partial sum algorithms: recursive, linear. More...
enum	_SplittingAlgorithm { SAMPLING, EXACT }
	Sorting/merging algorithms: sampling, __exact. More...
enum	_FindAlgorithm { GROWING_BLOCKS, CONSTANT_SIZE_BLOCKS, EQUAL_SPLIT }
	Find algorithms: More...

Functions
template<typename _RAIter , typename _Compare >
std::iterator_traits< _RAIter > ::difference_type	__qsb_divide (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
	Balanced quicksort divide step. More...
template<typename _RAIter , typename _Compare >
void	__qsb_conquer (_QSBThreadLocal< _RAIter > **__tls, _RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __iam, _ThreadIndex __num_threads, bool __parent_wait)
	Quicksort conquer step. More...
template<typename _RAIter , typename _Compare >
void	__qsb_local_sort_with_helping (_QSBThreadLocal< _RAIter > **__tls, _Compare &__comp, _ThreadIndex __iam, bool __wait)
	Quicksort step doing load-balanced local sort. More...
template<typename _RAIter , typename _Compare >
void	__parallel_sort_qsb (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
	Top-level quicksort routine. More...
_ThreadIndex	__get_max_threads ()
bool	__is_parallel (const _Parallelism __p)
template<typename _Size >
_Size	__rd_log2 (_Size __n)
	Calculates the rounded-down logarithm of __n for base 2. More...
_CASable	__encode2 (int __a, int __b)
	Encode two integers into one gnu_parallel::_CASable. More...
void	__decode2 (_CASable __x, int &__a, int &__b)
	Decode two integers from one gnu_parallel::_CASable. More...
template<typename _Tp >
const _Tp &	min (const _Tp &__a, const _Tp &__b)
	Equivalent to std::min. More...
template<typename _Tp >
const _Tp &	max (const _Tp &__a, const _Tp &__b)
	Equivalent to std::max. More...
template<typename _RAIter , typename _Compare >
_RAIter	__median_of_three_iterators (_RAIter __a, _RAIter __b, _RAIter __c, _Compare __comp)
	Compute the median of three referenced elements, according to __comp. More...
template<typename _IIter , typename _Compare >
bool	__is_sorted (_IIter __begin, _IIter __end, _Compare __comp)
	Check whether [__begin, __end) is sorted according to __comp. More...
template<typename _Tp >
_Tp	__add_omp (volatile _Tp *__ptr, _Tp __addend)
template<typename _Tp >
_Tp	__fetch_and_add (volatile _Tp *__ptr, _Tp __addend)
	Add a value to a variable, atomically. More...
template<typename _Tp >
bool	__cas_omp (volatile _Tp *__ptr, _Tp __comparand, _Tp __replacement)
template<typename _Tp >
bool	__compare_and_swap (volatile _Tp *__ptr, _Tp __comparand, _Tp __replacement)
	Compare-and-swap. More...
void	__yield ()
	Yield control to another thread, without waiting for the end of the time slice. More...
template<typename _DifferenceType , typename _OutputIterator >
_OutputIterator	__equally_split (_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s)
	function to split a sequence into parts of almost equal size. More...
template<typename _DifferenceType >
_DifferenceType	__equally_split_point (_DifferenceType __n, _ThreadIndex __num_threads, _ThreadIndex __thread_no)
	function to split a sequence into parts of almost equal size. More...
template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector >
std::pair< _RAIter1, _RAIter2 >	__find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector)
	Parallel std::find, switch for different algorithms. More...
template<typename _IIter , typename _UserOp , typename _Functionality , typename _Red , typename _Result >
_UserOp	__for_each_template_random_access (_IIter __begin, _IIter __end, _UserOp __user_op, _Functionality &__functionality, _Red __reduction, _Result __reduction_start, _Result &__output, typename std::iterator_traits< _IIter >::difference_type __bound, _Parallelism __parallelism_tag)
	Chose the desired algorithm by evaluating __parallelism_tag. More...
template<typename _IIter >
void	__shrink_and_double (std::vector< _IIter > &__os_starts, size_t &__count_to_two, size_t &__range_length, const bool __make_twice)
	Shrinks and doubles the ranges. More...
template<typename _IIter >
void	__shrink (std::vector< _IIter > &__os_starts, size_t &__count_to_two, size_t &__range_length)
	Combines two ranges into one and thus halves the number of ranges. More...
template<typename _IIter , typename _FunctorType >
size_t	list_partition (const _IIter __begin, const _IIter __end, _IIter *__starts, size_t *__lengths, const int __num_parts, _FunctorType &__f, int __oversampling=0)
	Splits a sequence given by input iterators into parts of almost equal size. More...
template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare >
_OutputIterator	__merge_advance_usual (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp)
	Merge routine being able to merge only the __max_length smallest elements. More...
template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare >
_OutputIterator	__merge_advance_movc (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp)
	Merge routine being able to merge only the __max_length smallest elements. More...
template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare >
_OutputIterator	__merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp)
	Merge routine being able to merge only the __max_length smallest elements. More...
template<typename _RAIter1 , typename _RAIter2 , typename _RAIter3 , typename _Compare >
_RAIter3	__parallel_merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp)
	Merge routine fallback to sequential in case the iterators of the two input sequences are of different type. More...
template<typename _RAIter1 , typename _RAIter3 , typename _Compare >
_RAIter3	__parallel_merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter1 &__begin2, _RAIter1 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp)
	Parallel merge routine being able to merge only the __max_length smallest elements. More...
template<typename _RanSeqs , typename _RankType , typename _RankIterator , typename _Compare >
void	multiseq_partition (_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankIterator __begin_offsets, _Compare __comp=std::less< typename std::iterator_traits< typename std::iterator_traits< _RanSeqs >::value_type::first_type >::value_type >())
	Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each sequence. The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones on the __left side will be chosen from sequences with smaller number. More...
template<typename _Tp , typename _RanSeqs , typename _RankType , typename _Compare >
_Tp	multiseq_selection (_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankType &__offset, _Compare __comp=std::less< _Tp >())
	Selects the element at a certain global __rank from several sorted sequences. More...
template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	multiway_merge_3_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp)
	Highly efficient 3-way merging procedure. More...
template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	multiway_merge_4_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp)
	Highly efficient 4-way merging procedure. More...
template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	multiway_merge_loser_tree (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp)
	Multi-way merging procedure for a high branching factor, guarded case. More...
template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	multiway_merge_loser_tree_unguarded (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp)
	Multi-way merging procedure for a high branching factor, unguarded case. More...
template<typename UnguardedLoserTree , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	multiway_merge_loser_tree_sentinel (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp)
	Multi-way merging procedure for a high branching factor, requiring sentinels to exist. More...
template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3	__sequential_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp)
	Sequential multi-way merging switch. More...
template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType >
void	multiway_merge_sampling_splitting (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces)
	Sampling based splitting for parallel multiway-merge routine. More...
template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType >
void	multiway_merge_exact_splitting (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces)
	Exact splitting for parallel multiway-merge routine. More...
template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Splitter , typename _Compare >
_RAIter3	parallel_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _Splitter __splitter, _DifferenceTp __length, _Compare __comp, _ThreadIndex __num_threads)
	Parallel multi-way merge routine. More...
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
	Multiway Merge Frontend. More...
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
	Multiway Merge Frontend. More...
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag)
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut	stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
template<typename _RAIter , typename _DifferenceTp >
void	__determine_samples (_PMWMSSortingData< _RAIter > *__sd, _DifferenceTp __num_samples)
	Select _M_samples from a sequence. More...
template<bool __stable, bool __exact, typename _RAIter , typename _Compare >
void	parallel_sort_mwms_pu (_PMWMSSortingData< _RAIter > *__sd, _Compare &__comp)
	PMWMS code executed by each thread. More...
template<bool __stable, bool __exact, typename _RAIter , typename _Compare >
void	parallel_sort_mwms (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
	PMWMS main call. More...
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result >
_Op	__for_each_template_random_access_omp_loop (_RAIter __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound)
	Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop. More...
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result >
_Op	__for_each_template_random_access_omp_loop_static (_RAIter __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound)
	Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling. More...
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result >
_Op	__for_each_template_random_access_ed (_RAIter __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound)
	Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work. More...
template<typename _IIter , typename _OutputIterator , typename _BinaryOperation >
_OutputIterator	__parallel_partial_sum_basecase (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op, typename std::iterator_traits< _IIter >::value_type __value)
	Base case prefix sum routine. More...
template<typename _IIter , typename _OutputIterator , typename _BinaryOperation >
_OutputIterator	__parallel_partial_sum_linear (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op, typename std::iterator_traits< _IIter >::difference_type __n)
	Parallel partial sum implementation, two-phase approach, no recursion. More...
template<typename _IIter , typename _OutputIterator , typename _BinaryOperation >
_OutputIterator	__parallel_partial_sum (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op)
	Parallel partial sum front-__end. More...
template<typename _RAIter , typename _Predicate >
std::iterator_traits< _RAIter > ::difference_type	__parallel_partition (_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads)
	Parallel implementation of std::partition. More...
template<typename _RAIter , typename _Compare >
void	__parallel_nth_element (_RAIter __begin, _RAIter __nth, _RAIter __end, _Compare __comp)
	Parallel implementation of std::nth_element(). More...
template<typename _RAIter , typename _Compare >
void	__parallel_partial_sort (_RAIter __begin, _RAIter __middle, _RAIter __end, _Compare __comp)
	Parallel implementation of std::partial_sort(). More...
template<typename _RAIter , typename _Compare >
std::iterator_traits< _RAIter > ::difference_type	__parallel_sort_qs_divide (_RAIter __begin, _RAIter __end, _Compare __comp, typename std::iterator_traits< _RAIter >::difference_type __pivot_rank, typename std::iterator_traits< _RAIter >::difference_type __num_samples, _ThreadIndex __num_threads)
	Unbalanced quicksort divide step. More...
template<typename _RAIter , typename _Compare >
void	__parallel_sort_qs_conquer (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
	Unbalanced quicksort conquer step. More...
template<typename _RAIter , typename _Compare >
void	__parallel_sort_qs (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
	Unbalanced quicksort main call. More...
template<typename _RandomNumberGenerator >
int	__random_number_pow2 (int __logp, _RandomNumberGenerator &__rng)
	Generate a random number in [0,2^__logp). More...
template<typename _RAIter , typename _RandomNumberGenerator >
void	__parallel_random_shuffle_drs_pu (_DRSSorterPU< _RAIter, _RandomNumberGenerator > *__pus)
	Random shuffle code executed by each thread. More...
template<typename _Tp >
_Tp	__round_up_to_pow2 (_Tp __x)
	Round up to the next greater power of 2. More...
template<typename _RAIter , typename _RandomNumberGenerator >
void	__parallel_random_shuffle_drs (_RAIter __begin, _RAIter __end, typename std::iterator_traits< _RAIter >::difference_type __n, _ThreadIndex __num_threads, _RandomNumberGenerator &__rng)
	Main parallel random shuffle step. More...
template<typename _RAIter , typename _RandomNumberGenerator >
void	__sequential_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng)
	Sequential cache-efficient random shuffle. More...
template<typename _RAIter , typename _RandomNumberGenerator >
void	__parallel_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng=_RandomNumber())
	Parallel random public call. More...
template<typename _RAIter , typename _DifferenceTp >
void	__calc_borders (_RAIter __elements, _DifferenceTp __length, _DifferenceTp *__off)
	Precalculate __advances for Knuth-Morris-Pratt algorithm. More...
template<typename __RAIter1 , typename __RAIter2 , typename _Pred >
__RAIter1	__search_template (__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred)
	Parallel std::search. More...
template<typename _IIter , typename _OutputIterator >
_OutputIterator	__copy_tail (std::pair< _IIter, _IIter > __b, std::pair< _IIter, _IIter > __e, _OutputIterator __r)
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_union (_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 _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_symmetric_difference (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp)
template<bool __stable, typename _RAIter , typename _Compare , typename _Parallelism >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, _Parallelism __parallelism)
template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_tag __parallelism)
	Choose multiway mergesort, splitting variant at run-time, for parallel sorting. More...
template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_exact_tag __parallelism)
	Choose multiway mergesort with exact splitting, for parallel sorting. More...
template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_sampling_tag __parallelism)
	Choose multiway mergesort with splitting by sampling, for parallel sorting. More...
template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, quicksort_tag __parallelism)
	Choose quicksort for parallel sorting. More...
template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, balanced_quicksort_tag __parallelism)
	Choose balanced quicksort for parallel sorting. More...
template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, default_parallel_tag __parallelism)
	Choose multiway mergesort with exact splitting, for parallel sorting. More...
template<bool __stable, typename _RAIter , typename _Compare >
void	__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, parallel_tag __parallelism)
	Choose a parallel sorting algorithm. More...
template<typename _IIter , class _OutputIterator , class _BinaryPredicate >
_OutputIterator	__parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result, _BinaryPredicate __binary_pred)
	Parallel std::unique_copy(), w/__o explicit equality predicate. More...
template<typename _IIter , class _OutputIterator >
_OutputIterator	__parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result)
	Parallel std::unique_copy(), without explicit equality predicate. More...
template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result >
_Op	__for_each_template_random_access_workstealing (_RAIter __begin, _RAIter __end, _Op __op, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound)
	Work stealing algorithm for random access iterators. More...

Variables
static const int	_CASable_bits = std::numeric_limits<_CASable>::digits
	Number of bits of _CASable. More...
static const _CASable	_CASable_mask
	_CASable with the right half of bits set to 1. More...

Detailed Description

GNU parallel code for public use.

Typedef Documentation

typedef unsigned short __gnu_parallel::_BinIndex

Type to hold the index of a bin.

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

typedef int64_t __gnu_parallel::_CASable

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

typedef uint64_t __gnu_parallel::_SequenceIndex

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

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.

Enumeration Type Documentation

enum __gnu_parallel::_AlgorithmStrategy

Strategies for run-time algorithm selection:

Enumerator
heuristic
force_sequential
force_parallel

    {
      heuristic,
      force_sequential,
      force_parallel
    };

enum __gnu_parallel::_FindAlgorithm

Find algorithms:

Enumerator
GROWING_BLOCKS
CONSTANT_SIZE_BLOCKS
EQUAL_SPLIT

    { 
      GROWING_BLOCKS, 
      CONSTANT_SIZE_BLOCKS, 
      EQUAL_SPLIT 
    };

enum __gnu_parallel::_MultiwayMergeAlgorithm

Merging algorithms:

Enumerator
LOSER_TREE

    {
      LOSER_TREE
    };

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.

    {
      sequential,

      parallel_unbalanced,

      parallel_balanced,

      parallel_omp_loop,

      parallel_omp_loop_static,

      parallel_taskqueue
    };

enum __gnu_parallel::_PartialSumAlgorithm

Partial sum algorithms: recursive, linear.

Enumerator
RECURSIVE
LINEAR

    { 
      RECURSIVE, 
      LINEAR 
    };

enum __gnu_parallel::_SortAlgorithm

Sorting algorithms:

Enumerator
MWMS
QS
QS_BALANCED

    { 
      MWMS, 
      QS, 
      QS_BALANCED 
    };

enum __gnu_parallel::_SplittingAlgorithm

Sorting/merging algorithms: sampling, __exact.

Enumerator
SAMPLING
EXACT

    { 
      SAMPLING, 
      EXACT 
    };

Function Documentation

template<typename _Tp >

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

inline

    {
      int64_t __res;
#pragma omp critical
      {
    __res = *__ptr;
    *(__ptr) += __addend;
      }
      return __res;
    }

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.

    {
      typedef _DifferenceTp _DifferenceType;

      __off[0] = -1;
      if (__length > 1)
    __off[1] = 0;
      _DifferenceType __k = 0;
      for (_DifferenceType __j = 2; __j <= __length; __j++)
    {
          while ((__k >= 0) && !(__elements[__k] == __elements[__j-1]))
            __k = __off[__k];
          __off[__j] = ++__k;
    }
    }

template<typename _Tp >

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

inline

    {
      bool __res = false;
#pragma omp critical
      {
    if (*__ptr == __comparand)
      {
        *__ptr = __replacement;
        __res = true;
      }
      }
      return __res;
    }

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.

    {
      if (__atomic_always_lock_free(sizeof(_Tp), __ptr))
    return __atomic_compare_exchange_n(__ptr, &__comparand, __replacement,
                       false, __ATOMIC_ACQ_REL,
                       __ATOMIC_RELAXED);
      return __cas_omp(__ptr, __comparand, __replacement);
    }

template<typename _IIter , typename _OutputIterator >

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

    {
      if (__b.first != __e.first)
    {
          do
            {
              *__r++ = *__b.first++;
            }
          while (__b.first != __e.first);
    }
      else
    {
          while (__b.second != __e.second)
            *__r++ = *__b.second++;
    }
      return __r;
    }

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

  {
    __a = (int)((__x >> (_CASable_bits / 2)) & _CASable_mask);
    __b = (int)((__x >>               0 ) & _CASable_mask);
  }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef _DifferenceTp _DifferenceType;

      _ThreadIndex __iam = omp_get_thread_num();

      _DifferenceType* __es = new _DifferenceType[__num_samples + 2];

      __equally_split(__sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam], 
              __num_samples + 1, __es);

      for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
    ::new(&(__sd->_M_samples[__iam * __num_samples + __i]))
        _ValueType(__sd->_M_source[__sd->_M_starts[__iam]
                       + __es[__i + 1]]);

      delete[] __es;
    }

_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

  {
    return (((_CASable)__a) << (_CASable_bits / 2)) | (((_CASable)__b) << 0);
  }

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

    {
      _DifferenceType __chunk_length = __n / __num_threads;
      _DifferenceType __num_longer_chunks = __n % __num_threads;
      _DifferenceType __pos = 0;
      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
    {
      *__s++ = __pos;
      __pos += ((__i < __num_longer_chunks)
            ? (__chunk_length + 1) : __chunk_length);
    }
      *__s++ = __n;
      return __s;
    }

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

    {
      _DifferenceType __chunk_length = __n / __num_threads;
      _DifferenceType __num_longer_chunks = __n % __num_threads;
      if (__thread_no < __num_longer_chunks)
    return __thread_no * (__chunk_length + 1);
      else
    return __num_longer_chunks * (__chunk_length + 1)
          + (__thread_no - __num_longer_chunks) * __chunk_length;
    }

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.

    {
      if (__atomic_always_lock_free(sizeof(_Tp), __ptr))
    return __atomic_fetch_add(__ptr, __addend, __ATOMIC_ACQ_REL);
      return __add_omp(__ptr, __addend);
    }

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.

    {
      switch (_Settings::get().find_algorithm)
    {
    case GROWING_BLOCKS:
          return __find_template(__begin1, __end1, __begin2, __pred,
                 __selector, growing_blocks_tag());
    case CONSTANT_SIZE_BLOCKS:
          return __find_template(__begin1, __end1, __begin2, __pred,
                 __selector, constant_size_blocks_tag());
    case EQUAL_SPLIT:
          return __find_template(__begin1, __end1, __begin2, __pred,
                 __selector, equal_split_tag());
    default:
          _GLIBCXX_PARALLEL_ASSERT(false);
          return std::make_pair(__begin1, __begin2);
    }
    }

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

    {
      if (__parallelism_tag == parallel_unbalanced)
        return __for_each_template_random_access_ed
      (__begin, __end, __user_op, __functionality, __reduction,
       __reduction_start, __output, __bound);
      else if (__parallelism_tag == parallel_omp_loop)
        return __for_each_template_random_access_omp_loop
      (__begin, __end, __user_op, __functionality, __reduction,
       __reduction_start, __output, __bound);
      else if (__parallelism_tag == parallel_omp_loop_static)
        return __for_each_template_random_access_omp_loop
      (__begin, __end, __user_op, __functionality, __reduction,
       __reduction_start, __output, __bound);
      else      //e. g. parallel_balanced
        return __for_each_template_random_access_workstealing
      (__begin, __end, __user_op, __functionality, __reduction,
       __reduction_start, __output, __bound);
  }

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

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::difference_type _DifferenceType;
      const _DifferenceType __length = __end - __begin;
      _Result *__thread_results;
      bool* __constructed;

      _ThreadIndex __num_threads = __gnu_parallel::min<_DifferenceType>
    (__get_max_threads(), __length);

#     pragma omp parallel num_threads(__num_threads)
      {
#       pragma omp single
    {
      __num_threads = omp_get_num_threads();
      __thread_results = static_cast<_Result*>
        (::operator new(__num_threads * sizeof(_Result)));
      __constructed = new bool[__num_threads];
    }

    _ThreadIndex __iam = omp_get_thread_num();

    // Neutral element.
    _Result* __reduct;

    _DifferenceType
      __start = __equally_split_point(__length, __num_threads, __iam),
      __stop = __equally_split_point(__length, __num_threads, __iam + 1);

    if (__start < __stop)
      {
        __reduct = new _Result(__f(__o, __begin + __start));
        ++__start;
        __constructed[__iam] = true;
      }
    else
      __constructed[__iam] = false;

    for (; __start < __stop; ++__start)
      *__reduct = __r(*__reduct, __f(__o, __begin + __start));

    if (__constructed[__iam])
      {
        ::new(&__thread_results[__iam]) _Result(*__reduct);
        delete __reduct;
      }
      } //parallel

      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
    if (__constructed[__i])
      {
        __output = __r(__output, __thread_results[__i]);
        __thread_results[__i].~_Result();
      }

      // Points to last element processed (needed as return value for
      // some algorithms like transform).
      __f._M_finish_iterator = __begin + __length;

      ::operator delete(__thread_results);

      delete[] __constructed;

      return __o;
    }

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

    {
      typedef typename std::iterator_traits<_RAIter>::difference_type
        _DifferenceType;

      _DifferenceType __length = __end - __begin;
      _ThreadIndex __num_threads = __gnu_parallel::min<_DifferenceType>
    (__get_max_threads(), __length);

      _Result *__thread_results;

#     pragma omp parallel num_threads(__num_threads)
      {
#       pragma omp single
    {
      __num_threads = omp_get_num_threads();
      __thread_results = new _Result[__num_threads];

      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
        __thread_results[__i] = _Result();
    }

        _ThreadIndex __iam = omp_get_thread_num();

#pragma omp for schedule(dynamic, _Settings::get().workstealing_chunk_size)
        for (_DifferenceType __pos = 0; __pos < __length; ++__pos)
          __thread_results[__iam] = __r(__thread_results[__iam],
                    __f(__o, __begin+__pos));
      } //parallel

      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
        __output = __r(__output, __thread_results[__i]);

      delete [] __thread_results;

      // Points to last element processed (needed as return value for
      // some algorithms like transform).
      __f._M_finish_iterator = __begin + __length;

      return __o;
    }

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

    {
      typedef typename std::iterator_traits<_RAIter>::difference_type
    _DifferenceType;

      _DifferenceType __length = __end - __begin;
      _ThreadIndex __num_threads = std::min<_DifferenceType>
    (__get_max_threads(), __length);

      _Result *__thread_results;

#     pragma omp parallel num_threads(__num_threads)
      {
#       pragma omp single
    {
      __num_threads = omp_get_num_threads();
      __thread_results = new _Result[__num_threads];

      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
        __thread_results[__i] = _Result();
    }

        _ThreadIndex __iam = omp_get_thread_num();

#pragma omp for schedule(static, _Settings::get().workstealing_chunk_size)
        for (_DifferenceType __pos = 0; __pos < __length; ++__pos)
          __thread_results[__iam] = __r(__thread_results[__iam],
                                        __f(__o, __begin+__pos));
      } //parallel

      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
    __output = __r(__output, __thread_results[__i]);

      delete [] __thread_results;

      // Points to last element processed (needed as return value for
      // some algorithms like transform).
      __f.finish_iterator = __begin + __length;

      return __o;
    }

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

    {
      _GLIBCXX_CALL(__end - __begin)

      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      const _Settings& __s = _Settings::get();

      _DifferenceType __chunk_size =
          static_cast<_DifferenceType>(__s.workstealing_chunk_size);

      // How many jobs?
      _DifferenceType __length = (__bound < 0) ? (__end - __begin) : __bound;

      // To avoid false sharing in a cache line.
      const int __stride = (__s.cache_line_size * 10
                / sizeof(_Job<_DifferenceType>) + 1);

      // Total number of threads currently working.
      _ThreadIndex __busy = 0;

      _Job<_DifferenceType> *__job;

      omp_lock_t __output_lock;
      omp_init_lock(&__output_lock);

      // Write base value to output.
      __output = __base;

      // No more threads than jobs, at least one thread.
      _ThreadIndex __num_threads = __gnu_parallel::max<_ThreadIndex>
    (1, __gnu_parallel::min<_DifferenceType>(__length,
                         __get_max_threads()));

#     pragma omp parallel shared(__busy) num_threads(__num_threads)
      {
#       pragma omp single
    {
      __num_threads = omp_get_num_threads();

      // Create job description array.
      __job = new _Job<_DifferenceType>[__num_threads * __stride];
    }

    // Initialization phase.

    // Flags for every thread if it is doing productive work.
    bool __iam_working = false;

    // Thread id.
    _ThreadIndex __iam = omp_get_thread_num();

    // This job.
    _Job<_DifferenceType>& __my_job = __job[__iam * __stride];

    // Random number (for work stealing).
    _ThreadIndex __victim;

    // Local value for reduction.
    _Result __result = _Result();

    // Number of elements to steal in one attempt.
    _DifferenceType __steal;

    // Every thread has its own random number generator
    // (modulo __num_threads).
    _RandomNumber __rand_gen(__iam, __num_threads);

    // This thread is currently working.
#       pragma omp atomic
    ++__busy;

    __iam_working = true;

    // How many jobs per thread? last thread gets the rest.
    __my_job._M_first = static_cast<_DifferenceType>
      (__iam * (__length / __num_threads));

    __my_job._M_last = (__iam == (__num_threads - 1)
                ? (__length - 1)
                : ((__iam + 1) * (__length / __num_threads) - 1));
    __my_job._M_load = __my_job._M_last - __my_job._M_first + 1;

    // Init result with _M_first value (to have a base value for reduction)
    if (__my_job._M_first <= __my_job._M_last)
      {
        // Cannot use volatile variable directly.
        _DifferenceType __my_first = __my_job._M_first;
        __result = __f(__op, __begin + __my_first);
        ++__my_job._M_first;
        --__my_job._M_load;
      }

    _RAIter __current;

#       pragma omp barrier

    // Actual work phase
    // Work on own or stolen current start
    while (__busy > 0)
      {
        // Work until no productive thread left.
#           pragma omp flush(__busy)

        // Thread has own work to do
        while (__my_job._M_first <= __my_job._M_last)
          {
        // fetch-and-add call
        // Reserve current job block (size __chunk_size) in my queue.
        _DifferenceType __current_job =
          __fetch_and_add<_DifferenceType>(&(__my_job._M_first),
                           __chunk_size);

        // Update _M_load, to make the three values consistent,
        // _M_first might have been changed in the meantime
        __my_job._M_load = __my_job._M_last - __my_job._M_first + 1;
        for (_DifferenceType __job_counter = 0;
             __job_counter < __chunk_size
               && __current_job <= __my_job._M_last;
             ++__job_counter)
          {
            // Yes: process it!
            __current = __begin + __current_job;
            ++__current_job;

            // Do actual work.
            __result = __r(__result, __f(__op, __current));
          }

#               pragma omp flush(__busy)
          }

        // After reaching this point, a thread's __job list is empty.
        if (__iam_working)
          {
        // This thread no longer has work.
#               pragma omp atomic
        --__busy;

        __iam_working = false;
          }

        _DifferenceType __supposed_first, __supposed_last,
                        __supposed_load;
        do
          {
        // Find random nonempty deque (not own), do consistency check.
        __yield();
#               pragma omp flush(__busy)
        __victim = __rand_gen();
        __supposed_first = __job[__victim * __stride]._M_first;
        __supposed_last = __job[__victim * __stride]._M_last;
        __supposed_load = __job[__victim * __stride]._M_load;
          }
        while (__busy > 0
           && ((__supposed_load <= 0)
               || ((__supposed_first + __supposed_load - 1)
               != __supposed_last)));

        if (__busy == 0)
          break;

        if (__supposed_load > 0)
          {
        // Has work and work to do.
        // Number of elements to steal (at least one).
        __steal = (__supposed_load < 2) ? 1 : __supposed_load / 2;

        // Push __victim's current start forward.
        _DifferenceType __stolen_first =
          __fetch_and_add<_DifferenceType>
          (&(__job[__victim * __stride]._M_first), __steal);
        _DifferenceType __stolen_try = (__stolen_first + __steal
                        - _DifferenceType(1));

        __my_job._M_first = __stolen_first;
        __my_job._M_last = __gnu_parallel::min(__stolen_try,
                               __supposed_last);
        __my_job._M_load = __my_job._M_last - __my_job._M_first + 1;

        // Has potential work again.
#               pragma omp atomic
        ++__busy;
        __iam_working = true;

#               pragma omp flush(__busy)
          }
#           pragma omp flush(__busy)
      } // end while __busy > 0
    // Add accumulated result to output.
    omp_set_lock(&__output_lock);
    __output = __r(__output, __result);
    omp_unset_lock(&__output_lock);
      }

      delete[] __job;

      // Points to last element processed (needed as return value for
      // some algorithms like transform)
      __f._M_finish_iterator = __begin + __length;

      omp_destroy_lock(&__output_lock);

      return __op;
    }

_ThreadIndex __gnu_parallel::__get_max_threads ( )

inline

  { 
    _ThreadIndex __i = omp_get_max_threads();
    return __i > 1 ? __i : 1; 
  }

bool __gnu_parallel::__is_parallel ( const _Parallelism  __p )

inline

{ return __p != sequential; }

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.

    {
      if (__begin == __end)
        return true;

      _IIter __current(__begin), __recent(__begin);

      unsigned long long __position = 1;
      for (__current++; __current != __end; __current++)
        {
          if (__comp(*__current, *__recent))
            {
              return false;
            }
          __recent = __current;
          __position++;
        }

      return true;
    }

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.

    {
      if (__comp(*__a, *__b))
    if (__comp(*__b, *__c))
      return __b;
    else
      if (__comp(*__a, *__c))
        return __c;
      else
        return __a;
      else
    {
      // Just swap __a and __b.
      if (__comp(*__a, *__c))
        return __a;
      else
        if (__comp(*__b, *__c))
          return __c;
        else
          return __b;
    }
    }

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.

    {
      _GLIBCXX_CALL(__max_length)

      return __merge_advance_movc(__begin1, __end1, __begin2, __end2,
                  __target, __max_length, __comp);
    }

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.

    {
      typedef _DifferenceTp _DifferenceType;
      typedef typename std::iterator_traits<_RAIter1>::value_type
        _ValueType1;
      typedef typename std::iterator_traits<_RAIter2>::value_type
        _ValueType2;

#if _GLIBCXX_ASSERTIONS
      _GLIBCXX_PARALLEL_ASSERT(__max_length >= 0);
#endif

      while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0)
        {
          _RAIter1 __next1 = __begin1 + 1;
          _RAIter2 __next2 = __begin2 + 1;
          _ValueType1 __element1 = *__begin1;
          _ValueType2 __element2 = *__begin2;

          if (__comp(__element2, __element1))
            {
              __element1 = __element2;
              __begin2 = __next2;
            }
          else
            __begin1 = __next1;

          *__target = __element1;

          ++__target;
          --__max_length;
        }
      if (__begin1 != __end1)
        {
          __target = std::copy(__begin1, __begin1 + __max_length, __target);
          __begin1 += __max_length;
        }
      else
        {
          __target = std::copy(__begin2, __begin2 + __max_length, __target);
          __begin2 += __max_length;
        }
      return __target;
    }

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.

    {
      typedef _DifferenceTp _DifferenceType;
      while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0)
        {
          // array1[__i1] < array0[i0]
          if (__comp(*__begin2, *__begin1))
            *__target++ = *__begin2++;
          else
            *__target++ = *__begin1++;
          --__max_length;
        }

      if (__begin1 != __end1)
        {
          __target = std::copy(__begin1, __begin1 + __max_length, __target);
          __begin1 += __max_length;
        }
      else
        {
          __target = std::copy(__begin2, __begin2 + __max_length, __target);
          __begin2 += __max_length;
        }
      return __target;
    }

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.

    { return __merge_advance(__begin1, __end1, __begin2, __end2, __target,
                 __max_length, __comp); }

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.

    {
      typedef typename
          std::iterator_traits<_RAIter1>::value_type _ValueType;
      typedef typename std::iterator_traits<_RAIter1>::
        difference_type _DifferenceType1 /* == difference_type2 */;
      typedef typename std::iterator_traits<_RAIter3>::
        difference_type _DifferenceType3;
      typedef typename std::pair<_RAIter1, _RAIter1>
        _IteratorPair;

      _IteratorPair __seqs[2] = { std::make_pair(__begin1, __end1),
                  std::make_pair(__begin2, __end2) };
      _RAIter3 __target_end = parallel_multiway_merge
    < /* __stable = */ true, /* __sentinels = */ false>
    (__seqs, __seqs + 2, __target, multiway_merge_exact_splitting
     < /* __stable = */ true, _IteratorPair*,
     _Compare, _DifferenceType1>, __max_length, __comp,
     omp_get_max_threads());

      return __target_end;
    }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _GLIBCXX_CALL(__end - __begin)

      _RAIter __split;
      _RandomNumber __rng;

      const _Settings& __s = _Settings::get();
      _DifferenceType __minimum_length = std::max<_DifferenceType>(2,
        std::max(__s.nth_element_minimal_n, __s.partition_minimal_n));

      // Break if input range to small.
      while (static_cast<_SequenceIndex>(__end - __begin) >= __minimum_length)
    {
          _DifferenceType __n = __end - __begin;

          _RAIter __pivot_pos = __begin + __rng(__n);

          // Swap __pivot_pos value to end.
          if (__pivot_pos != (__end - 1))
            std::iter_swap(__pivot_pos, __end - 1);
          __pivot_pos = __end - 1;

          // _Compare must have first_value_type, second_value_type,
          // result_type
          // _Compare ==
          // __gnu_parallel::_Lexicographic<S, int,
      //                                __gnu_parallel::_Less<S, S> >
          // __pivot_pos == std::pair<S, int>*
          __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool>
            __pred(__comp, *__pivot_pos);

          // Divide, leave pivot unchanged in last place.
          _RAIter __split_pos1, __split_pos2;
          __split_pos1 = __begin + __parallel_partition(__begin, __end - 1,
                            __pred,
                            __get_max_threads());

          // Left side: < __pivot_pos; __right side: >= __pivot_pos

          // Swap pivot back to middle.
          if (__split_pos1 != __pivot_pos)
            std::iter_swap(__split_pos1, __pivot_pos);
          __pivot_pos = __split_pos1;

          // In case all elements are equal, __split_pos1 == 0
          if ((__split_pos1 + 1 - __begin) < (__n >> 7)
              || (__end - __split_pos1) < (__n >> 7))
            {
              // Very unequal split, one part smaller than one 128th
              // elements not strictly larger than the pivot.
              __gnu_parallel::__unary_negate<__gnu_parallel::
        	__binder1st<_Compare, _ValueType,
                    _ValueType, bool>, _ValueType>
            __pred(__gnu_parallel::__binder1st<_Compare, _ValueType,
               _ValueType, bool>(__comp, *__pivot_pos));

              // Find other end of pivot-equal range.
              __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1,
                             __end, __pred);
            }
          else
            // Only skip the pivot.
            __split_pos2 = __split_pos1 + 1;

          // Compare iterators.
          if (__split_pos2 <= __nth)
            __begin = __split_pos2;
          else if (__nth < __split_pos1)
            __end = __split_pos1;
          else
            break;
    }

      // Only at most _Settings::partition_minimal_n __elements __left.
      __gnu_sequential::nth_element(__begin, __nth, __end, __comp);
    }

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.

    {
      __parallel_nth_element(__begin, __middle, __end, __comp);
      std::sort(__begin, __middle, __comp);
    }

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.

    {
      _GLIBCXX_CALL(__begin - __end)

      typedef std::iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _DifferenceType __n = __end - __begin;

      switch (_Settings::get().partial_sum_algorithm)
    {
    case LINEAR:
      // Need an initial offset.
      return __parallel_partial_sum_linear(__begin, __end, __result,
                           __bin_op, __n);
    default:
      // Partial_sum algorithm not implemented.
      _GLIBCXX_PARALLEL_ASSERT(0);
      return __result + __n;
    }
    }

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.

    {
      if (__begin == __end)
    return __result;

      while (__begin != __end)
    {
      __value = __bin_op(__value, *__begin);
      *__result = __value;
      ++__result;
      ++__begin;
    }
      return __result;
    }

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.

    {
      typedef std::iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      if (__begin == __end)
    return __result;

      _ThreadIndex __num_threads =
        std::min<_DifferenceType>(__get_max_threads(), __n - 1);

      if (__num_threads < 2)
    {
      *__result = *__begin;
      return __parallel_partial_sum_basecase(__begin + 1, __end,
                         __result + 1, __bin_op,
                         *__begin);
    }

      _DifferenceType* __borders;
      _ValueType* __sums;

      const _Settings& __s = _Settings::get();

#     pragma omp parallel num_threads(__num_threads)
      {
#       pragma omp single
    {
      __num_threads = omp_get_num_threads();
        
      __borders = new _DifferenceType[__num_threads + 2];

      if (__s.partial_sum_dilation == 1.0f)
        __equally_split(__n, __num_threads + 1, __borders);
      else
        {
          _DifferenceType __first_part_length =
          std::max<_DifferenceType>(1,
            __n / (1.0f + __s.partial_sum_dilation * __num_threads));
          _DifferenceType __chunk_length =
          (__n - __first_part_length) / __num_threads;
          _DifferenceType __borderstart =
          __n - __num_threads * __chunk_length;
          __borders[0] = 0;
          for (_ThreadIndex __i = 1; __i < (__num_threads + 1); ++__i)
        {
          __borders[__i] = __borderstart;
          __borderstart += __chunk_length;
        }
          __borders[__num_threads + 1] = __n;
        }

      __sums = static_cast<_ValueType*>(::operator new(sizeof(_ValueType)
                                                           * __num_threads));
      _OutputIterator __target_end;
    } //single

        _ThreadIndex __iam = omp_get_thread_num();
        if (__iam == 0)
          {
            *__result = *__begin;
            __parallel_partial_sum_basecase(__begin + 1,
                        __begin + __borders[1],
                        __result + 1,
                        __bin_op, *__begin);
            ::new(&(__sums[__iam])) _ValueType(*(__result + __borders[1] - 1));
          }
        else
          {
            ::new(&(__sums[__iam]))
              _ValueType(__gnu_parallel::accumulate(
                                         __begin + __borders[__iam] + 1,
                                         __begin + __borders[__iam + 1],
                                         *(__begin + __borders[__iam]),
                                         __bin_op,
                                         __gnu_parallel::sequential_tag()));
          }

#       pragma omp barrier

#       pragma omp single
    __parallel_partial_sum_basecase(__sums + 1, __sums + __num_threads,
                    __sums + 1, __bin_op, __sums[0]);

#       pragma omp barrier

    // Still same team.
        __parallel_partial_sum_basecase(__begin + __borders[__iam + 1],
                    __begin + __borders[__iam + 2],
                    __result + __borders[__iam + 1],
                    __bin_op, __sums[__iam]);
      } //parallel

      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
    __sums[__i].~_ValueType();
      ::operator delete(__sums);

      delete[] __borders;

      return __result + __n;
    }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _DifferenceType __n = __end - __begin;

      _GLIBCXX_CALL(__n)

      const _Settings& __s = _Settings::get();

      // shared
      _GLIBCXX_VOLATILE _DifferenceType __left = 0, __right = __n - 1,
                                        __dist = __n,
                                        __leftover_left, __leftover_right,
                                        __leftnew, __rightnew;

      // just 0 or 1, but int to allow atomic operations
      int* __reserved_left = 0, * __reserved_right = 0;

      _DifferenceType __chunk_size = __s.partition_chunk_size;

      //at least two chunks per thread
      if (__dist >= 2 * __num_threads * __chunk_size)
#       pragma omp parallel num_threads(__num_threads)
    {
#         pragma omp single
      {
        __num_threads = omp_get_num_threads();
        __reserved_left = new int[__num_threads];
        __reserved_right = new int[__num_threads];

        if (__s.partition_chunk_share > 0.0)
          __chunk_size = std::max<_DifferenceType>
        (__s.partition_chunk_size, (double)__n 
         * __s.partition_chunk_share / (double)__num_threads);
        else
          __chunk_size = __s.partition_chunk_size;
      }

      while (__dist >= 2 * __num_threads * __chunk_size)
        {
#             pragma omp single
          {
        _DifferenceType __num_chunks = __dist / __chunk_size;

        for (_ThreadIndex __r = 0; __r < __num_threads; ++__r)
          {
            __reserved_left [__r] = 0; // false
            __reserved_right[__r] = 0; // false
          }
        __leftover_left = 0;
        __leftover_right = 0;
          } //implicit barrier

          // Private.
          _DifferenceType __thread_left, __thread_left_border,
                      __thread_right, __thread_right_border;

          __thread_left = __left + 1;
          // Just to satisfy the condition below.
          __thread_left_border = __thread_left - 1;

          __thread_right = __n - 1;
             // Just to satisfy the condition below.
          __thread_right_border = __thread_right + 1;

          bool __iam_finished = false;
          while (!__iam_finished)
        {
          if (__thread_left > __thread_left_border)
            {
                      _DifferenceType __former_dist =
                              __fetch_and_add(&__dist, -__chunk_size);
                      if (__former_dist < __chunk_size)
                        {
                          __fetch_and_add(&__dist, __chunk_size);
                          __iam_finished = true;
                          break;
                        }
                      else
                        {
                          __thread_left =
                                  __fetch_and_add(&__left, __chunk_size);
                          __thread_left_border =
                                  __thread_left + (__chunk_size - 1);
                        }
            }

          if (__thread_right < __thread_right_border)
            {
                      _DifferenceType __former_dist =
                              __fetch_and_add(&__dist, -__chunk_size);
                      if (__former_dist < __chunk_size)
                        {
                          __fetch_and_add(&__dist, __chunk_size);
                          __iam_finished = true;
                          break;
                        }
                      else
                        {
                          __thread_right =
                                  __fetch_and_add(&__right, -__chunk_size);
                          __thread_right_border =
                                  __thread_right - (__chunk_size - 1);
                        }
            }

          // Swap as usual.
          while (__thread_left < __thread_right)
            {
              while (__pred(__begin[__thread_left])
                 && __thread_left <= __thread_left_border)
            ++__thread_left;
              while (!__pred(__begin[__thread_right])
                 && __thread_right >= __thread_right_border)
            --__thread_right;

              if (__thread_left > __thread_left_border
              || __thread_right < __thread_right_border)
            // Fetch new chunk(__s).
            break;

              std::iter_swap(__begin + __thread_left,
                             __begin + __thread_right);
              ++__thread_left;
              --__thread_right;
            }
        }

          // Now swap the leftover chunks to the right places.
          if (__thread_left <= __thread_left_border)
#               pragma omp atomic
        ++__leftover_left;
          if (__thread_right >= __thread_right_border)
#               pragma omp atomic
        ++__leftover_right;

#             pragma omp barrier

              _DifferenceType
                    __leftold = __left,
                    __leftnew = __left - __leftover_left * __chunk_size,
                    __rightold = __right,
                    __rightnew = __right + __leftover_right * __chunk_size;

          // <=> __thread_left_border + (__chunk_size - 1) >= __leftnew
          if (__thread_left <= __thread_left_border
          && __thread_left_border >= __leftnew)
        {
          // Chunk already in place, reserve spot.
        __reserved_left[(__left - (__thread_left_border + 1))
                / __chunk_size] = 1;
        }

          // <=> __thread_right_border - (__chunk_size - 1) <= __rightnew
          if (__thread_right >= __thread_right_border
          && __thread_right_border <= __rightnew)
        {
          // Chunk already in place, reserve spot.
          __reserved_right[((__thread_right_border - 1) - __right)
                   / __chunk_size] = 1;
        }

#             pragma omp barrier

          if (__thread_left <= __thread_left_border
          && __thread_left_border < __leftnew)
        {
          // Find spot and swap.
          _DifferenceType __swapstart = -1;
                  for (int __r = 0; __r < __leftover_left; ++__r)
                    if (__reserved_left[__r] == 0
                        && __compare_and_swap(&(__reserved_left[__r]), 0, 1))
                      {
                        __swapstart = __leftold - (__r + 1) * __chunk_size;
                        break;
                      }

#if _GLIBCXX_ASSERTIONS
          _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
#endif

          std::swap_ranges(__begin + __thread_left_border
                   - (__chunk_size - 1),
                   __begin + __thread_left_border + 1,
                   __begin + __swapstart);
        }

          if (__thread_right >= __thread_right_border
          && __thread_right_border > __rightnew)
        {
          // Find spot and swap
          _DifferenceType __swapstart = -1;
                  for (int __r = 0; __r < __leftover_right; ++__r)
                    if (__reserved_right[__r] == 0
                        && __compare_and_swap(&(__reserved_right[__r]), 0, 1))
                      {
                        __swapstart = __rightold + __r * __chunk_size + 1;
                        break;
                      }

#if _GLIBCXX_ASSERTIONS
          _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
#endif

          std::swap_ranges(__begin + __thread_right_border,
                   __begin + __thread_right_border
                   + __chunk_size, __begin + __swapstart);
          }
#if _GLIBCXX_ASSERTIONS
#             pragma omp barrier

#             pragma omp single
          {
        for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)
          _GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r] == 1);
        for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)
          _GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r] == 1);
          }
#endif

          __left = __leftnew;
          __right = __rightnew;
              __dist = __right - __left + 1;
        }

#           pragma omp flush(__left, __right)
    } // end "recursion" //parallel

        _DifferenceType __final_left = __left, __final_right = __right;

    while (__final_left < __final_right)
      {
        // Go right until key is geq than pivot.
        while (__pred(__begin[__final_left])
           && __final_left < __final_right)
          ++__final_left;

        // Go left until key is less than pivot.
        while (!__pred(__begin[__final_right])
           && __final_left < __final_right)
          --__final_right;

        if (__final_left == __final_right)
          break;
        std::iter_swap(__begin + __final_left, __begin + __final_right);
        ++__final_left;
        --__final_right;
      }

    // All elements on the left side are < piv, all elements on the
    // right are >= piv
    delete[] __reserved_left;
    delete[] __reserved_right;

    // Element "between" __final_left and __final_right might not have
    // been regarded yet
    if (__final_left < __n && !__pred(__begin[__final_left]))
      // Really swapped.
      return __final_left;
    else
      return __final_left + 1;
    }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::difference_type _DifferenceType;
      _DifferenceType __n = __end - __begin;
      __parallel_random_shuffle_drs(__begin, __end, __n,
                    __get_max_threads(), __rng);
    }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _GLIBCXX_CALL(__n)

      const _Settings& __s = _Settings::get();

      if (__num_threads > __n)
    __num_threads = static_cast<_ThreadIndex>(__n);

      _BinIndex __num_bins, __num_bins_cache;

#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
      // Try the L1 cache first.

      // Must fit into L1.
      __num_bins_cache =
    std::max<_DifferenceType>(1, __n / (__s.L1_cache_size_lb
                        / sizeof(_ValueType)));
      __num_bins_cache = __round_up_to_pow2(__num_bins_cache);

      // No more buckets than TLB entries, power of 2
      // Power of 2 and at least one element per bin, at most the TLB size.
      __num_bins = std::min<_DifferenceType>(__n, __num_bins_cache);

#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
      // 2 TLB entries needed per bin.
      __num_bins = std::min<_DifferenceType>(__s.TLB_size / 2, __num_bins);
#endif
      __num_bins = __round_up_to_pow2(__num_bins);

      if (__num_bins < __num_bins_cache)
    {
#endif
          // Now try the L2 cache
          // Must fit into L2
          __num_bins_cache = static_cast<_BinIndex>
        (std::max<_DifferenceType>(1, __n / (__s.L2_cache_size
                         / sizeof(_ValueType))));
          __num_bins_cache = __round_up_to_pow2(__num_bins_cache);

          // No more buckets than TLB entries, power of 2.
          __num_bins = static_cast<_BinIndex>
        (std::min(__n, static_cast<_DifferenceType>(__num_bins_cache)));
          // Power of 2 and at least one element per bin, at most the TLB size.
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
          // 2 TLB entries needed per bin.
          __num_bins = std::min(static_cast<_DifferenceType>(__s.TLB_size / 2),
                __num_bins);
#endif
            __num_bins = __round_up_to_pow2(__num_bins);
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
    }
#endif

      __num_bins = __round_up_to_pow2(
                        std::max<_BinIndex>(__num_threads, __num_bins));

      if (__num_threads <= 1)
      {
        _RandomNumber __derived_rng(
                            __rng(std::numeric_limits<uint32_t>::max()));
    __sequential_random_shuffle(__begin, __end, __derived_rng);
        return;
      }

      _DRandomShufflingGlobalData<_RAIter> __sd(__begin);
      _DRSSorterPU<_RAIter, _RandomNumber >* __pus;
      _DifferenceType* __starts;

#     pragma omp parallel num_threads(__num_threads)
      {
    _ThreadIndex __num_threads = omp_get_num_threads();
#       pragma omp single
    {
      __pus = new _DRSSorterPU<_RAIter, _RandomNumber>[__num_threads];
      
      __sd._M_temporaries = new _ValueType*[__num_threads];
      __sd._M_dist = new _DifferenceType*[__num_bins + 1];
      __sd._M_bin_proc = new _ThreadIndex[__num_bins];
      for (_BinIndex __b = 0; __b < __num_bins + 1; ++__b)
        __sd._M_dist[__b] = new _DifferenceType[__num_threads + 1];
      for (_BinIndex __b = 0; __b < (__num_bins + 1); ++__b)
        {
          __sd._M_dist[0][0] = 0;
          __sd._M_dist[__b][0] = 0;
        }
      __starts = __sd._M_starts = new _DifferenceType[__num_threads + 1];
      int __bin_cursor = 0;
      __sd._M_num_bins = __num_bins;
      __sd._M_num_bits = __rd_log2(__num_bins);

      _DifferenceType __chunk_length = __n / __num_threads,
                             __split = __n % __num_threads,
                             __start = 0;
      _DifferenceType __bin_chunk_length = __num_bins / __num_threads,
                             __bin_split = __num_bins % __num_threads;
      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
        {
          __starts[__i] = __start;
          __start += (__i < __split
              ? (__chunk_length + 1) : __chunk_length);
          int __j = __pus[__i]._M_bins_begin = __bin_cursor;

          // Range of bins for this processor.
          __bin_cursor += (__i < __bin_split
                   ? (__bin_chunk_length + 1)
                   : __bin_chunk_length);
          __pus[__i].__bins_end = __bin_cursor;
          for (; __j < __bin_cursor; ++__j)
        __sd._M_bin_proc[__j] = __i;
          __pus[__i]._M_num_threads = __num_threads;
          __pus[__i]._M_seed = __rng(std::numeric_limits<uint32_t>::max());
          __pus[__i]._M_sd = &__sd;
        }
      __starts[__num_threads] = __start;
    } //single
          // Now shuffle in parallel.
    __parallel_random_shuffle_drs_pu(__pus);
      }  // parallel

      delete[] __starts;
      delete[] __sd._M_bin_proc;
      for (int __s = 0; __s < (__num_bins + 1); ++__s)
    delete[] __sd._M_dist[__s];
      delete[] __sd._M_dist;
      delete[] __sd._M_temporaries;

      delete[] __pus;
    }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _ThreadIndex __iam = omp_get_thread_num();
      _DRSSorterPU<_RAIter, _RandomNumberGenerator>* __d = &__pus[__iam];
      _DRandomShufflingGlobalData<_RAIter>* __sd = __d->_M_sd;

      // Indexing: _M_dist[bin][processor]
      _DifferenceType __length = (__sd->_M_starts[__iam + 1]
                  - __sd->_M_starts[__iam]);
      _BinIndex* __oracles = new _BinIndex[__length];
      _DifferenceType* __dist = new _DifferenceType[__sd->_M_num_bins + 1];
      _BinIndex* __bin_proc = new _BinIndex[__sd->_M_num_bins];
      _ValueType** __temporaries = new _ValueType*[__d->_M_num_threads];

      // Compute oracles and count appearances.
      for (_BinIndex __b = 0; __b < __sd->_M_num_bins + 1; ++__b)
    __dist[__b] = 0;
      int __num_bits = __sd->_M_num_bits;

      _RandomNumber __rng(__d->_M_seed);

      // First main loop.
      for (_DifferenceType __i = 0; __i < __length; ++__i)
    {
          _BinIndex __oracle = __random_number_pow2(__num_bits, __rng);
          __oracles[__i] = __oracle;

          // To allow prefix (partial) sum.
          ++(__dist[__oracle + 1]);
    }

      for (_BinIndex __b = 0; __b < __sd->_M_num_bins + 1; ++__b)
    __sd->_M_dist[__b][__iam + 1] = __dist[__b];

#     pragma omp barrier

#     pragma omp single
      {
    // Sum up bins, __sd->_M_dist[__s + 1][__d->_M_num_threads] now
    // contains the total number of items in bin __s
    for (_BinIndex __s = 0; __s < __sd->_M_num_bins; ++__s)
          __gnu_sequential::partial_sum(__sd->_M_dist[__s + 1],
                    __sd->_M_dist[__s + 1]
                    + __d->_M_num_threads + 1,
                    __sd->_M_dist[__s + 1]);
      }

#     pragma omp barrier

      _SequenceIndex __offset = 0, __global_offset = 0;
      for (_BinIndex __s = 0; __s < __d->_M_bins_begin; ++__s)
    __global_offset += __sd->_M_dist[__s + 1][__d->_M_num_threads];

#     pragma omp barrier

      for (_BinIndex __s = __d->_M_bins_begin; __s < __d->__bins_end; ++__s)
    {
          for (int __t = 0; __t < __d->_M_num_threads + 1; ++__t)
            __sd->_M_dist[__s + 1][__t] += __offset;
          __offset = __sd->_M_dist[__s + 1][__d->_M_num_threads];
    }

      __sd->_M_temporaries[__iam] = static_cast<_ValueType*>
    (::operator new(sizeof(_ValueType) * __offset));

#     pragma omp barrier

      // Draw local copies to avoid false sharing.
      for (_BinIndex __b = 0; __b < __sd->_M_num_bins + 1; ++__b)
    __dist[__b] = __sd->_M_dist[__b][__iam];
      for (_BinIndex __b = 0; __b < __sd->_M_num_bins; ++__b)
    __bin_proc[__b] = __sd->_M_bin_proc[__b];
      for (_ThreadIndex __t = 0; __t < __d->_M_num_threads; ++__t)
    __temporaries[__t] = __sd->_M_temporaries[__t];

      _RAIter __source = __sd->_M_source;
      _DifferenceType __start = __sd->_M_starts[__iam];

      // Distribute according to oracles, second main loop.
      for (_DifferenceType __i = 0; __i < __length; ++__i)
    {
          _BinIndex __target_bin = __oracles[__i];
          _ThreadIndex __target_p = __bin_proc[__target_bin];

          // Last column [__d->_M_num_threads] stays unchanged.
      ::new(&(__temporaries[__target_p][__dist[__target_bin + 1]++]))
              _ValueType(*(__source + __i + __start));
    }

      delete[] __oracles;
      delete[] __dist;
      delete[] __bin_proc;
      delete[] __temporaries;

#     pragma omp barrier

      // Shuffle bins internally.
      for (_BinIndex __b = __d->_M_bins_begin; __b < __d->__bins_end; ++__b)
    {
          _ValueType* __begin =
        (__sd->_M_temporaries[__iam]
         + (__b == __d->_M_bins_begin
        ? 0 : __sd->_M_dist[__b][__d->_M_num_threads])),
        *__end = (__sd->_M_temporaries[__iam]
              + __sd->_M_dist[__b + 1][__d->_M_num_threads]);

          __sequential_random_shuffle(__begin, __end, __rng);
          std::copy(__begin, __end, __sd->_M_source + __global_offset
            + (__b == __d->_M_bins_begin
               ? 0 : __sd->_M_dist[__b][__d->_M_num_threads]));
    }

      for (_SequenceIndex __i = 0; __i < __offset; ++__i)
    __sd->_M_temporaries[__iam][__i].~_ValueType();
      ::operator delete(__sd->_M_temporaries[__iam]);
    }

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

    {
      return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
                      __result,
                      __difference_func<_IIter,
                      _OutputIterator, _Compare>(__comp));
    }

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

    {
      return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
                      __result,
                      __intersection_func<_IIter,
                      _OutputIterator, _Compare>(__comp));
    }

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
	)

    {
      _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2))

      typedef std::iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::difference_type _DifferenceType;
      typedef typename std::pair<_IIter, _IIter> _IteratorPair;

      if (__begin1 == __end1)
    return __op.__first_empty(__begin2, __end2, __result);

      if (__begin2 == __end2)
    return __op.__second_empty(__begin1, __end1, __result);

      const _DifferenceType __size = (__end1 - __begin1) + (__end2 - __begin2);

      const _IteratorPair __sequence[2] = { std::make_pair(__begin1, __end1),
                        std::make_pair(__begin2, __end2) };
      _OutputIterator __return_value = __result;
      _DifferenceType *__borders;
      _IteratorPair *__block_begins;
      _DifferenceType* __lengths;

      _ThreadIndex __num_threads =
          std::min<_DifferenceType>(__get_max_threads(),
              std::min(__end1 - __begin1, __end2 - __begin2));

#     pragma omp parallel num_threads(__num_threads)
      {
#       pragma omp single
    {
      __num_threads = omp_get_num_threads();

      __borders = new _DifferenceType[__num_threads + 2];
      __equally_split(__size, __num_threads + 1, __borders);
      __block_begins = new _IteratorPair[__num_threads + 1];
      // Very __start.
      __block_begins[0] = std::make_pair(__begin1, __begin2);
      __lengths = new _DifferenceType[__num_threads];
    } //single

    _ThreadIndex __iam = omp_get_thread_num();

    // _Result from multiseq_partition.
    _IIter __offset[2];
    const _DifferenceType __rank = __borders[__iam + 1];

    multiseq_partition(__sequence, __sequence + 2,
               __rank, __offset, __op._M_comp);

    // allowed to read?
    // together
    // *(__offset[ 0 ] - 1) == *__offset[ 1 ]
    if (__offset[ 0 ] != __begin1 && __offset[1] != __end2
        && !__op._M_comp(*(__offset[0] - 1), *__offset[1])
        && !__op._M_comp(*__offset[1], *(__offset[0] - 1)))
      {
        // Avoid split between globally equal elements: move one to
        // front in first sequence.
              --__offset[0];
      }

    _IteratorPair __block_end = __block_begins[__iam + 1] =
      _IteratorPair(__offset[0], __offset[1]);

    // Make sure all threads have their block_begin result written out.
#       pragma omp barrier

    _IteratorPair __block_begin = __block_begins[__iam];

    // Begin working for the first block, while the others except
    // the last start to count.
    if (__iam == 0)
      {
        // The first thread can copy already.
        __lengths[ __iam ] =
          __op._M_invoke(__block_begin.first, __block_end.first,
                 __block_begin.second, __block_end.second,
                 __result) - __result;
      }
    else
      {
        __lengths[ __iam ] =
          __op.__count(__block_begin.first, __block_end.first,
               __block_begin.second, __block_end.second);
      }

    // Make sure everyone wrote their lengths.
#       pragma omp barrier

    _OutputIterator __r = __result;

    if (__iam == 0)
      {
        // Do the last block.
        for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
          __r += __lengths[__i];

        __block_begin = __block_begins[__num_threads];

        // Return the result iterator of the last block.
        __return_value =
          __op._M_invoke(__block_begin.first, __end1,
                 __block_begin.second, __end2, __r);

      }
          else
            {
              for (_ThreadIndex __i = 0; __i < __iam; ++__i)
            __r += __lengths[ __i ];

              // Reset begins for copy pass.
              __op._M_invoke(__block_begin.first, __block_end.first,
                 __block_begin.second, __block_end.second, __r);
            }
    }
      return __return_value;
    }

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

    {
      return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
                      __result,
                      __symmetric_difference_func<_IIter,
                      _OutputIterator, _Compare>(__comp));
    }

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

    {
      return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
                      __result,
                      __union_func< _IIter, _OutputIterator,
                      _Compare>(__comp));
    }

template<bool __stable, typename _RAIter , typename _Compare , typename _Parallelism >

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

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.

    {
      _GLIBCXX_CALL(__end - __begin)

      if(_Settings::get().sort_splitting == EXACT)
    parallel_sort_mwms<__stable, true>
      (__begin, __end, __comp, __parallelism.__get_num_threads());
      else
    parallel_sort_mwms<__stable, false>
      (__begin, __end, __comp, __parallelism.__get_num_threads());
    }

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.

    {
      _GLIBCXX_CALL(__end - __begin)

      parallel_sort_mwms<__stable, true>
        (__begin, __end, __comp, __parallelism.__get_num_threads());
    }

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.

    {
      _GLIBCXX_CALL(__end - __begin)

      parallel_sort_mwms<__stable, false>
      (__begin, __end, __comp, __parallelism.__get_num_threads());
    }

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.

    {
      _GLIBCXX_CALL(__end - __begin)

      _GLIBCXX_PARALLEL_ASSERT(__stable == false);

      __parallel_sort_qs(__begin, __end, __comp,
             __parallelism.__get_num_threads());
    }

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.

     {
       _GLIBCXX_CALL(__end - __begin)

       _GLIBCXX_PARALLEL_ASSERT(__stable == false);

       __parallel_sort_qsb(__begin, __end, __comp,
               __parallelism.__get_num_threads());
     }

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.

    {
      _GLIBCXX_CALL(__end - __begin)

      __parallel_sort<__stable>
    (__begin, __end, __comp,
     multiway_mergesort_exact_tag(__parallelism.__get_num_threads()));
    }

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.

    {
      _GLIBCXX_CALL(__end - __begin)
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      if (false) ;
#if _GLIBCXX_MERGESORT
      else if (__stable || _Settings::get().sort_algorithm == MWMS)
        {
          if(_Settings::get().sort_splitting == EXACT)
            parallel_sort_mwms<__stable, true>
              (__begin, __end, __comp, __parallelism.__get_num_threads());
          else
            parallel_sort_mwms<false, false>
              (__begin, __end, __comp, __parallelism.__get_num_threads());
        }
#endif
#if _GLIBCXX_QUICKSORT
      else if (_Settings::get().sort_algorithm == QS)
        __parallel_sort_qs(__begin, __end, __comp,
                           __parallelism.__get_num_threads());
#endif
#if _GLIBCXX_BAL_QUICKSORT
      else if (_Settings::get().sort_algorithm == QS_BALANCED)
        __parallel_sort_qsb(__begin, __end, __comp,
                            __parallelism.__get_num_threads());
#endif
      else
        __gnu_sequential::sort(__begin, __end, __comp);
    }

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.

    {
      _GLIBCXX_CALL(__n)

      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _DifferenceType __n = __end - __begin;

      // At least one element per processor.
      if (__num_threads > __n)
        __num_threads = static_cast<_ThreadIndex>(__n);

      __parallel_sort_qs_conquer(
        __begin, __begin + __n, __comp, __num_threads);
    }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      if (__num_threads <= 1)
        {
          __gnu_sequential::sort(__begin, __end, __comp);
          return;
        }

      _DifferenceType __n = __end - __begin, __pivot_rank;

      if (__n <= 1)
        return;

      _ThreadIndex __num_threads_left;

      if ((__num_threads % 2) == 1)
        __num_threads_left = __num_threads / 2 + 1;
      else
        __num_threads_left = __num_threads / 2;

      __pivot_rank = __n * __num_threads_left / __num_threads;

      _DifferenceType __split = __parallel_sort_qs_divide
    (__begin, __end, __comp, __pivot_rank,
     _Settings::get().sort_qs_num_samples_preset, __num_threads);

#pragma omp parallel sections num_threads(2)
      {
#pragma omp section
        __parallel_sort_qs_conquer(__begin, __begin + __split,
                   __comp, __num_threads_left);
#pragma omp section
        __parallel_sort_qs_conquer(__begin + __split, __end,
                   __comp, __num_threads - __num_threads_left);
      }
    }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _DifferenceType __n = __end - __begin;
      __num_samples = std::min(__num_samples, __n);

      // Allocate uninitialized, to avoid default constructor.
      _ValueType* __samples = static_cast<_ValueType*>
    (::operator new(__num_samples * sizeof(_ValueType)));

      for (_DifferenceType __s = 0; __s < __num_samples; ++__s)
        {
          const unsigned long long __index = static_cast<unsigned long long>
        (__s) * __n / __num_samples;
          ::new(&(__samples[__s])) _ValueType(__begin[__index]);
        }

      __gnu_sequential::sort(__samples, __samples + __num_samples, __comp);

      _ValueType& __pivot = __samples[__pivot_rank * __num_samples / __n];

      __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool>
        __pred(__comp, __pivot);
      _DifferenceType __split = __parallel_partition(__begin, __end,
                             __pred, __num_threads);

      for (_DifferenceType __s = 0; __s < __num_samples; ++__s)
    __samples[__s].~_ValueType();
      ::operator delete(__samples);

      return __split;
    }

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.

    {
      _GLIBCXX_CALL(__end - __begin)

      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;
      typedef std::pair<_RAIter, _RAIter> _Piece;

      typedef _QSBThreadLocal<_RAIter> _TLSType;

      _DifferenceType __n = __end - __begin;

      if (__n <= 1)
    return;

      // At least one element per processor.
      if (__num_threads > __n)
    __num_threads = static_cast<_ThreadIndex>(__n);

      // Initialize thread local storage
      _TLSType** __tls = new _TLSType*[__num_threads];
      _DifferenceType __queue_size = (__num_threads
                      * (_ThreadIndex)(__rd_log2(__n) + 1));
      for (_ThreadIndex __t = 0; __t < __num_threads; ++__t)
    __tls[__t] = new _QSBThreadLocal<_RAIter>(__queue_size);

      // There can never be more than ceil(__rd_log2(__n)) ranges on the
      // stack, because
      // 1. Only one processor pushes onto the stack
      // 2. The largest range has at most length __n
      // 3. Each range is larger than half of the range remaining
      volatile _DifferenceType __elements_leftover = __n;
      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
    {
          __tls[__i]->_M_elements_leftover = &__elements_leftover;
          __tls[__i]->_M_num_threads = __num_threads;
          __tls[__i]->_M_global = std::make_pair(__begin, __end);

          // Just in case nothing is left to assign.
          __tls[__i]->_M_initial = std::make_pair(__end, __end);
    }

      // Main recursion call.
      __qsb_conquer(__tls, __begin, __begin + __n, __comp, 0,
            __num_threads, true);

#if _GLIBCXX_ASSERTIONS
      // All stack must be empty.
      _Piece __dummy;
      for (_ThreadIndex __i = 1; __i < __num_threads; ++__i)
    _GLIBCXX_PARALLEL_ASSERT(
          !__tls[__i]->_M_leftover_parts.pop_back(__dummy));
#endif

      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
    delete __tls[__i];
      delete[] __tls;
    }

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.

    {
      _GLIBCXX_CALL(__last - __first)

      typedef std::iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _DifferenceType __size = __last - __first;

      if (__size == 0)
    return __result;

      // Let the first thread process two parts.
      _DifferenceType *__counter;
      _DifferenceType *__borders;

      _ThreadIndex __num_threads = __get_max_threads();
      // First part contains at least one element.
#     pragma omp parallel num_threads(__num_threads)
      {
#       pragma omp single
    {
      __num_threads = omp_get_num_threads();
      __borders = new _DifferenceType[__num_threads + 2];
      __equally_split(__size, __num_threads + 1, __borders);
      __counter = new _DifferenceType[__num_threads + 1];
    }

    _ThreadIndex __iam = omp_get_thread_num();

    _DifferenceType __begin, __end;

    // Check for length without duplicates
    // Needed for position in output
    _DifferenceType __i = 0;
    _OutputIterator __out = __result;

    if (__iam == 0)
          {
            __begin = __borders[0] + 1;   // == 1
            __end = __borders[__iam + 1];

            ++__i;
            *__out++ = *__first;

            for (_IIter __iter = __first + __begin; __iter < __first + __end;
         ++__iter)
              {
            if (!__binary_pred(*__iter, *(__iter - 1)))
                  {
                    ++__i;
                    *__out++ = *__iter;
                  }
              }
          }
    else
          {
            __begin = __borders[__iam]; //one part
            __end = __borders[__iam + 1];

            for (_IIter __iter = __first + __begin; __iter < __first + __end;
         ++__iter)
              {
            if (!__binary_pred(*__iter, *(__iter - 1)))
                  ++__i;
              }
          }
    __counter[__iam] = __i;

    // Last part still untouched.
    _DifferenceType __begin_output;

#       pragma omp barrier

    // Store result in output on calculated positions.
    __begin_output = 0;

    if (__iam == 0)
          {
            for (_ThreadIndex __t = 0; __t < __num_threads; ++__t)
              __begin_output += __counter[__t];

            __i = 0;

            _OutputIterator __iter_out = __result + __begin_output;

            __begin = __borders[__num_threads];
            __end = __size;

            for (_IIter __iter = __first + __begin; __iter < __first + __end;
         ++__iter)
              {
            if (__iter == __first
            || !__binary_pred(*__iter, *(__iter - 1)))
                  {
                    ++__i;
                    *__iter_out++ = *__iter;
                  }
              }

            __counter[__num_threads] = __i;
          }
    else
          {
            for (_ThreadIndex __t = 0; __t < __iam; __t++)
              __begin_output += __counter[__t];

            _OutputIterator __iter_out = __result + __begin_output;
            for (_IIter __iter = __first + __begin; __iter < __first + __end;
         ++__iter)
              {
            if (!__binary_pred(*__iter, *(__iter - 1)))
                  *__iter_out++ = *__iter;
              }
          }
      }

      _DifferenceType __end_output = 0;
      for (_ThreadIndex __t = 0; __t < __num_threads + 1; __t++)
    __end_output += __counter[__t];

      delete[] __borders;

      return __result + __end_output;
    }

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.

    {
      typedef typename std::iterator_traits<_IIter>::value_type
    _ValueType;
      return __parallel_unique_copy(__first, __last, __result,
                    std::equal_to<_ValueType>());
    }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _DifferenceType __n = __end - __begin;

      if (__num_threads <= 1 || __n <= 1)
    {
          __tls[__iam]->_M_initial.first  = __begin;
          __tls[__iam]->_M_initial.second = __end;

          __qsb_local_sort_with_helping(__tls, __comp, __iam, __parent_wait);

          return;
    }

      // Divide step.
      _DifferenceType __split_pos =
    __qsb_divide(__begin, __end, __comp, __num_threads);

#if _GLIBCXX_ASSERTIONS
      _GLIBCXX_PARALLEL_ASSERT(0 <= __split_pos &&
                               __split_pos < (__end - __begin));
#endif

      _ThreadIndex
    __num_threads_leftside = std::max<_ThreadIndex>
    (1, std::min<_ThreadIndex>(__num_threads - 1, __split_pos
                   * __num_threads / __n));

#     pragma omp atomic
      *__tls[__iam]->_M_elements_leftover -= (_DifferenceType)1;

      // Conquer step.
#     pragma omp parallel num_threads(2)
      {
    bool __wait;
    if(omp_get_num_threads() < 2)
          __wait = false;
    else
          __wait = __parent_wait;

#       pragma omp sections
    {
#         pragma omp section
      {
        __qsb_conquer(__tls, __begin, __begin + __split_pos, __comp,
              __iam, __num_threads_leftside, __wait);
        __wait = __parent_wait;
      }
      // The pivot_pos is left in place, to ensure termination.
#         pragma omp section
      {
        __qsb_conquer(__tls, __begin + __split_pos + 1, __end, __comp,
              __iam + __num_threads_leftside,
              __num_threads - __num_threads_leftside, __wait);
        __wait = __parent_wait;
      }
    }
      }
    }

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

    {
      _GLIBCXX_PARALLEL_ASSERT(__num_threads > 0);

      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _RAIter __pivot_pos =
    __median_of_three_iterators(__begin, __begin + (__end - __begin) / 2,
                    __end  - 1, __comp);

#if defined(_GLIBCXX_ASSERTIONS)
      // Must be in between somewhere.
      _DifferenceType __n = __end - __begin;

      _GLIBCXX_PARALLEL_ASSERT((!__comp(*__pivot_pos, *__begin)
                && !__comp(*(__begin + __n / 2),
                       *__pivot_pos))
                   || (!__comp(*__pivot_pos, *__begin)
                   && !__comp(*(__end - 1), *__pivot_pos))
                   || (!__comp(*__pivot_pos, *(__begin + __n / 2))
                   && !__comp(*__begin, *__pivot_pos))
                   || (!__comp(*__pivot_pos, *(__begin + __n / 2))
                   && !__comp(*(__end - 1), *__pivot_pos))
                   || (!__comp(*__pivot_pos, *(__end - 1))
                   && !__comp(*__begin, *__pivot_pos))
                   || (!__comp(*__pivot_pos, *(__end - 1))
                   && !__comp(*(__begin + __n / 2),
                          *__pivot_pos)));
#endif

      // Swap pivot value to end.
      if (__pivot_pos != (__end - 1))
    std::iter_swap(__pivot_pos, __end - 1);
      __pivot_pos = __end - 1;

      __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool>
    __pred(__comp, *__pivot_pos);

      // Divide, returning __end - __begin - 1 in the worst case.
      _DifferenceType __split_pos = __parallel_partition(__begin, __end - 1,
                             __pred,
                             __num_threads);

      // Swap back pivot to middle.
      std::iter_swap(__begin + __split_pos, __pivot_pos);
      __pivot_pos = __begin + __split_pos;

#if _GLIBCXX_ASSERTIONS
      _RAIter __r;
      for (__r = __begin; __r != __pivot_pos; ++__r)
    _GLIBCXX_PARALLEL_ASSERT(__comp(*__r, *__pivot_pos));
      for (; __r != __end; ++__r)
    _GLIBCXX_PARALLEL_ASSERT(!__comp(*__r, *__pivot_pos));
#endif

      return __split_pos;
    }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;
      typedef std::pair<_RAIter, _RAIter> _Piece;

      _QSBThreadLocal<_RAIter>& __tl = *__tls[__iam];

      _DifferenceType
    __base_case_n = _Settings::get().sort_qsb_base_case_maximal_n;
      if (__base_case_n < 2)
    __base_case_n = 2;
      _ThreadIndex __num_threads = __tl._M_num_threads;

      // Every thread has its own random number generator.
      _RandomNumber __rng(__iam + 1);

      _Piece __current = __tl._M_initial;

      _DifferenceType __elements_done = 0;
#if _GLIBCXX_ASSERTIONS
      _DifferenceType __total_elements_done = 0;
#endif

      for (;;)
    {
          // Invariant: __current must be a valid (maybe empty) range.
          _RAIter __begin = __current.first, __end = __current.second;
          _DifferenceType __n = __end - __begin;

          if (__n > __base_case_n)
            {
              // Divide.
              _RAIter __pivot_pos = __begin +  __rng(__n);

              // Swap __pivot_pos value to end.
              if (__pivot_pos != (__end - 1))
            std::iter_swap(__pivot_pos, __end - 1);
              __pivot_pos = __end - 1;

              __gnu_parallel::__binder2nd
        <_Compare, _ValueType, _ValueType, bool>
        __pred(__comp, *__pivot_pos);

              // Divide, leave pivot unchanged in last place.
              _RAIter __split_pos1, __split_pos2;
              __split_pos1 = __gnu_sequential::partition(__begin, __end - 1,
                             __pred);

              // Left side: < __pivot_pos; __right side: >= __pivot_pos.
#if _GLIBCXX_ASSERTIONS
              _GLIBCXX_PARALLEL_ASSERT(__begin <= __split_pos1
                                       && __split_pos1 < __end);
#endif
              // Swap pivot back to middle.
              if (__split_pos1 != __pivot_pos)
            std::iter_swap(__split_pos1, __pivot_pos);
              __pivot_pos = __split_pos1;

              // In case all elements are equal, __split_pos1 == 0.
              if ((__split_pos1 + 1 - __begin) < (__n >> 7)
          || (__end - __split_pos1) < (__n >> 7))
            {
                  // Very unequal split, one part smaller than one 128th
                  // elements not strictly larger than the pivot.
                  __gnu_parallel::__unary_negate<__gnu_parallel::__binder1st
                    <_Compare, _ValueType, _ValueType, bool>, _ValueType>
                    __pred(__gnu_parallel::__binder1st
                     <_Compare, _ValueType, _ValueType, bool>
               (__comp, *__pivot_pos));

                  // Find other end of pivot-equal range.
                  __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1,
                                 __end, __pred);
            }
              else
            // Only skip the pivot.
            __split_pos2 = __split_pos1 + 1;

              // Elements equal to pivot are done.
              __elements_done += (__split_pos2 - __split_pos1);
#if _GLIBCXX_ASSERTIONS
              __total_elements_done += (__split_pos2 - __split_pos1);
#endif
              // Always push larger part onto stack.
              if (((__split_pos1 + 1) - __begin) < (__end - (__split_pos2)))
            {
                  // Right side larger.
                  if ((__split_pos2) != __end)
                    __tl._M_leftover_parts.push_front
              (std::make_pair(__split_pos2, __end));

                  //__current.first = __begin;    //already set anyway
                  __current.second = __split_pos1;
                  continue;
            }
              else
            {
                  // Left side larger.
                  if (__begin != __split_pos1)
                    __tl._M_leftover_parts.push_front(std::make_pair
                              (__begin, __split_pos1));

                  __current.first = __split_pos2;
                  //__current.second = __end;     //already set anyway
                  continue;
            }
            }
          else
            {
              __gnu_sequential::sort(__begin, __end, __comp);
              __elements_done += __n;
#if _GLIBCXX_ASSERTIONS
              __total_elements_done += __n;
#endif

              // Prefer own stack, small pieces.
              if (__tl._M_leftover_parts.pop_front(__current))
            continue;

#             pragma omp atomic
              *__tl._M_elements_leftover -= __elements_done;

              __elements_done = 0;

#if _GLIBCXX_ASSERTIONS
              double __search_start = omp_get_wtime();
#endif

              // Look for new work.
              bool __successfully_stolen = false;
              while (__wait && *__tl._M_elements_leftover > 0
                     && !__successfully_stolen
#if _GLIBCXX_ASSERTIONS
                      // Possible dead-lock.
                     && (omp_get_wtime() < (__search_start + 1.0))
#endif
             )
            {
                  _ThreadIndex __victim;
                  __victim = __rng(__num_threads);

                  // Large pieces.
                  __successfully_stolen = (__victim != __iam)
            && __tls[__victim]->_M_leftover_parts.pop_back(__current);
                  if (!__successfully_stolen)
                    __yield();
#if !defined(__ICC) && !defined(__ECC)
#                 pragma omp flush
#endif
            }

#if _GLIBCXX_ASSERTIONS
              if (omp_get_wtime() >= (__search_start + 1.0))
            {
                  sleep(1);
                  _GLIBCXX_PARALLEL_ASSERT(omp_get_wtime()
                                           < (__search_start + 1.0));
            }
#endif
              if (!__successfully_stolen)
            {
#if _GLIBCXX_ASSERTIONS
                  _GLIBCXX_PARALLEL_ASSERT(*__tl._M_elements_leftover == 0);
#endif
                  return;
            }
            }
    }
    }

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.

    { return __rng.__genrand_bits(__logp); }

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.

    {
      _Size __k;
      for (__k = 0; __n > 1; __n >>= 1)
        ++__k;
      return __k;
    }

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

    {
      if (__x <= 1)
    return 1;
      else
    return (_Tp)1 << (__rd_log2(__x - 1) + 1);
    }

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.

    {
      typedef std::iterator_traits<__RAIter1> _TraitsType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2));

      _DifferenceType __pattern_length = __end2 - __begin2;

      // Pattern too short.
      if(__pattern_length <= 0)
    return __end1;

      // Last point to start search.
      _DifferenceType __input_length = (__end1 - __begin1) - __pattern_length;

      // Where is first occurrence of pattern? defaults to end.
      _DifferenceType __result = (__end1 - __begin1);
      _DifferenceType *__splitters;

      // Pattern too long.
      if (__input_length < 0)
    return __end1;

      omp_lock_t __result_lock;
      omp_init_lock(&__result_lock);

      _ThreadIndex __num_threads = std::max<_DifferenceType>
    (1, std::min<_DifferenceType>(__input_length,
                      __get_max_threads()));

      _DifferenceType __advances[__pattern_length];
      __calc_borders(__begin2, __pattern_length, __advances);

#     pragma omp parallel num_threads(__num_threads)
      {
#       pragma omp single
    {
      __num_threads = omp_get_num_threads();
      __splitters = new _DifferenceType[__num_threads + 1];
      __equally_split(__input_length, __num_threads, __splitters);
    }

    _ThreadIndex __iam = omp_get_thread_num();

    _DifferenceType __start = __splitters[__iam],
                     __stop = __splitters[__iam + 1];

    _DifferenceType __pos_in_pattern = 0;
    bool __found_pattern = false;

    while (__start <= __stop && !__found_pattern)
      {
        // Get new value of result.
#pragma omp flush(__result)
        // No chance for this thread to find first occurrence.
        if (__result < __start)
          break;
        while (__pred(__begin1[__start + __pos_in_pattern],
              __begin2[__pos_in_pattern]))
          {
        ++__pos_in_pattern;
        if (__pos_in_pattern == __pattern_length)
          {
            // Found new candidate for result.
            omp_set_lock(&__result_lock);
            __result = std::min(__result, __start);
            omp_unset_lock(&__result_lock);

            __found_pattern = true;
            break;
          }
          }
        // Make safe jump.
        __start += (__pos_in_pattern - __advances[__pos_in_pattern]);
        __pos_in_pattern = (__advances[__pos_in_pattern] < 0
                ? 0 : __advances[__pos_in_pattern]);
      }
      } //parallel

      omp_destroy_lock(&__result_lock);

      delete[] __splitters;
      
      // Return iterator on found element.
      return (__begin1 + __result);
    }

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.

    {
      _GLIBCXX_CALL(__length)

      typedef _DifferenceTp _DifferenceType;
      typedef typename std::iterator_traits<_RAIterIterator>
    ::difference_type _SeqNumber;
      typedef typename std::iterator_traits<_RAIterIterator>
    ::value_type::first_type
    _RAIter1;
      typedef typename std::iterator_traits<_RAIter1>::value_type
    _ValueType;

#if _GLIBCXX_ASSERTIONS
      for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
    {
          _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first,
                           (*__s).second, __comp));
    }
#endif

      _DifferenceTp __total_length = 0;
      for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
    __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);

      __length = std::min<_DifferenceTp>(__length, __total_length);

      if(__length == 0)
    return __target;

      _RAIter3 __return_target = __target;
      _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);

      switch (__k)
    {
    case 0:
          break;
    case 1:
          __return_target = std::copy(__seqs_begin[0].first,
                      __seqs_begin[0].first + __length,
                      __target);
          __seqs_begin[0].first += __length;
          break;
    case 2:
          __return_target = __merge_advance(__seqs_begin[0].first,
                        __seqs_begin[0].second,
                        __seqs_begin[1].first,
                        __seqs_begin[1].second,
                        __target, __length, __comp);
          break;
    case 3:
          __return_target = __multiway_merge_3_variant_sentinel_switch
        <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
        (__seqs_begin, __seqs_end, __target, __length, __comp);
          break;
    case 4:
          __return_target = __multiway_merge_4_variant_sentinel_switch
        <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
        (__seqs_begin, __seqs_end, __target, __length, __comp);
          break;
    default:
      __return_target = __multiway_merge_k_variant_sentinel_switch
        <__sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp,
         _Compare>()
        (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
      break;
    }
#if _GLIBCXX_ASSERTIONS
      _GLIBCXX_PARALLEL_ASSERT(
    __is_sorted(__target, __target + __length, __comp));
#endif

      return __return_target;
    }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _DifferenceType __n = __end - __begin;
      const _Settings& __s = _Settings::get();

      _BinIndex __num_bins, __num_bins_cache;

#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
      // Try the L1 cache first, must fit into L1.
      __num_bins_cache = std::max<_DifferenceType>
    (1, __n / (__s.L1_cache_size_lb / sizeof(_ValueType)));
      __num_bins_cache = __round_up_to_pow2(__num_bins_cache);

      // No more buckets than TLB entries, power of 2
      // Power of 2 and at least one element per bin, at most the TLB size
      __num_bins = std::min(__n, (_DifferenceType)__num_bins_cache);
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
      // 2 TLB entries needed per bin
      __num_bins = std::min((_DifferenceType)__s.TLB_size / 2, __num_bins);
#endif
      __num_bins = __round_up_to_pow2(__num_bins);

      if (__num_bins < __num_bins_cache)
    {
#endif
          // Now try the L2 cache, must fit into L2.
          __num_bins_cache = static_cast<_BinIndex>
        (std::max<_DifferenceType>(1, __n / (__s.L2_cache_size
                         / sizeof(_ValueType))));
          __num_bins_cache = __round_up_to_pow2(__num_bins_cache);

          // No more buckets than TLB entries, power of 2
          // Power of 2 and at least one element per bin, at most the TLB size.
          __num_bins = static_cast<_BinIndex>
        (std::min(__n, static_cast<_DifferenceType>(__num_bins_cache)));

#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB
          // 2 TLB entries needed per bin
          __num_bins = std::min<_DifferenceType>(__s.TLB_size / 2, __num_bins);
#endif
          __num_bins = __round_up_to_pow2(__num_bins);
#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1
    }
#endif

      int __num_bits = __rd_log2(__num_bins);

      if (__num_bins > 1)
    {
          _ValueType* __target =
        static_cast<_ValueType*>(::operator new(sizeof(_ValueType) * __n));
          _BinIndex* __oracles = new _BinIndex[__n];
          _DifferenceType* __dist0 = new _DifferenceType[__num_bins + 1],
                     * __dist1 = new _DifferenceType[__num_bins + 1];

          for (int __b = 0; __b < __num_bins + 1; ++__b)
            __dist0[__b] = 0;

          _RandomNumber __bitrng(__rng(0xFFFFFFFF));

          for (_DifferenceType __i = 0; __i < __n; ++__i)
            {
              _BinIndex __oracle = __random_number_pow2(__num_bits, __bitrng);
              __oracles[__i] = __oracle;

              // To allow prefix (partial) sum.
              ++(__dist0[__oracle + 1]);
            }

          // Sum up bins.
          __gnu_sequential::partial_sum(__dist0, __dist0 + __num_bins + 1,
                    __dist0);

          for (int __b = 0; __b < __num_bins + 1; ++__b)
            __dist1[__b] = __dist0[__b];

          // Distribute according to oracles.
          for (_DifferenceType __i = 0; __i < __n; ++__i)
            ::new(&(__target[(__dist0[__oracles[__i]])++])) 
        _ValueType(*(__begin + __i));

          for (int __b = 0; __b < __num_bins; ++__b)
        __sequential_random_shuffle(__target + __dist1[__b],
                    __target + __dist1[__b + 1], __rng);

          // Copy elements back.
          std::copy(__target, __target + __n, __begin);

          delete[] __dist0;
          delete[] __dist1;
          delete[] __oracles;
      
      for (_DifferenceType __i = 0; __i < __n; ++__i)
        __target[__i].~_ValueType();
          ::operator delete(__target);
    }
      else
    __gnu_sequential::random_shuffle(__begin, __end, __rng);
    }

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.

    {
      for (typename std::vector<_IIter>::size_type __i = 0;
           __i <= (__os_starts.size() / 2); ++__i)
        __os_starts[__i] = __os_starts[__i * 2];
      __range_length *= 2;
    }

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

    {
      ++__count_to_two;
      if (!__make_twice || __count_to_two < 2)
        __shrink(__os_starts, __count_to_two, __range_length);
      else
        {
          __os_starts.resize((__os_starts.size() - 1) * 2 + 1);
          __count_to_two = 0;
        }
    }

void __gnu_parallel::__yield ( )

inline

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

  {
#if defined (_WIN32) && !defined (__CYGWIN__)
    Sleep(0);
#else
    sched_yield();
#endif
  }

template<typename _IIter , typename _FunctorType >

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

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

The function needs only one pass over the sequence.

Parameters

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

Returns

Length of the whole sequence.

    {
      bool __make_twice = false;

      // The resizing algorithm is chosen according to the oversampling factor.
      if (__oversampling == 0)
        {
          __make_twice = true;
          __oversampling = 1;
        }

      std::vector<_IIter> __os_starts(2 * __oversampling * __num_parts + 1);

      __os_starts[0] = __begin;
      _IIter __prev  = __begin, __it = __begin;
      size_t __dist_limit = 0, __dist = 0;
      size_t __cur = 1, __next = 1;
      size_t __range_length = 1;
      size_t __count_to_two = 0;
      while (__it != __end)
        {
          __cur = __next;
          for (; __cur < __os_starts.size() and __it != __end; ++__cur)
            {
              for (__dist_limit += __range_length;
                   __dist < __dist_limit and __it != __end; ++__dist)
                {
                  __f(__it);
                  ++__it;
                }
              __os_starts[__cur] = __it;
            }

          // Must compare for end and not __cur < __os_starts.size() , because
          // __cur could be == __os_starts.size() as well
          if (__it == __end)
            break;

          __shrink_and_double(__os_starts, __count_to_two, __range_length,
                              __make_twice);
          __next = __os_starts.size() / 2 + 1;
        }

      // Calculation of the parts (one must be extracted from __current
      // because the partition beginning at end, consists only of
      // itself).
      size_t __size_part = (__cur - 1) / __num_parts;
      int __size_greater = static_cast<int>((__cur - 1) % __num_parts);
      __starts[0] = __os_starts[0];

      size_t __index = 0;

      // Smallest partitions.
      for (int __i = 1; __i < (__num_parts + 1 - __size_greater); ++__i)
        {
          __lengths[__i - 1] =  __size_part * __range_length;
          __index += __size_part;
          __starts[__i] = __os_starts[__index];
        }

      // Biggest partitions.
      for (int __i = __num_parts + 1 - __size_greater; __i <= __num_parts;
           ++__i)
        {
          __lengths[__i - 1] =  (__size_part+1) * __range_length;
          __index += (__size_part+1);
          __starts[__i] = __os_starts[__index];
        }

      // Correction of the end size (the end iteration has not finished).
      __lengths[__num_parts - 1] -= (__dist_limit - __dist);

      return __dist;
    }

template<typename _Tp >

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

inline

Equivalent to std::max.

    { return (__a > __b) ? __a : __b; }

template<typename _Tp >

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

inline

Equivalent to std::min.

    { return (__a < __b) ? __a : __b; }

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

    {
      _GLIBCXX_CALL(__end_seqs - __begin_seqs)

      typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type
        _It;
      typedef typename std::iterator_traits<_RanSeqs>::difference_type
        _SeqNumber;
      typedef typename std::iterator_traits<_It>::difference_type
               _DifferenceType;
      typedef typename std::iterator_traits<_It>::value_type _ValueType;

      _Lexicographic<_ValueType, _SeqNumber, _Compare> __lcomp(__comp);
      _LexicographicReverse<_ValueType, _SeqNumber, _Compare> __lrcomp(__comp);

      // Number of sequences, number of elements in total (possibly
      // including padding).
      _DifferenceType __m = std::distance(__begin_seqs, __end_seqs), __nn = 0,
                      __nmax, __n, __r;

      for (_SeqNumber __i = 0; __i < __m; __i++)
        {
          __nn += std::distance(__begin_seqs[__i].first,
                               __begin_seqs[__i].second);
          _GLIBCXX_PARALLEL_ASSERT(
            std::distance(__begin_seqs[__i].first,
                          __begin_seqs[__i].second) > 0);
        }

      if (__rank == __nn)
        {
          for (_SeqNumber __i = 0; __i < __m; __i++)
            __begin_offsets[__i] = __begin_seqs[__i].second; // Very end.
          // Return __m - 1;
          return;
        }

      _GLIBCXX_PARALLEL_ASSERT(__m != 0);
      _GLIBCXX_PARALLEL_ASSERT(__nn != 0);
      _GLIBCXX_PARALLEL_ASSERT(__rank >= 0);
      _GLIBCXX_PARALLEL_ASSERT(__rank < __nn);

      _DifferenceType* __ns = new _DifferenceType[__m];
      _DifferenceType* __a = new _DifferenceType[__m];
      _DifferenceType* __b = new _DifferenceType[__m];
      _DifferenceType __l;

      __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second);
      __nmax = __ns[0];
      for (_SeqNumber __i = 0; __i < __m; __i++)
        {
          __ns[__i] = std::distance(__begin_seqs[__i].first,
                                    __begin_seqs[__i].second);
          __nmax = std::max(__nmax, __ns[__i]);
        }

      __r = __rd_log2(__nmax) + 1;

      // Pad all lists to this length, at least as long as any ns[__i],
      // equality iff __nmax = 2^__k - 1.
      __l = (1ULL << __r) - 1;

      for (_SeqNumber __i = 0; __i < __m; __i++)
        {
          __a[__i] = 0;
          __b[__i] = __l;
        }
      __n = __l / 2;

      // Invariants:
      // 0 <= __a[__i] <= __ns[__i], 0 <= __b[__i] <= __l

#define __S(__i) (__begin_seqs[__i].first)

      // Initial partition.
      std::vector<std::pair<_ValueType, _SeqNumber> > __sample;

      for (_SeqNumber __i = 0; __i < __m; __i++)
        if (__n < __ns[__i])    //__sequence long enough
          __sample.push_back(std::make_pair(__S(__i)[__n], __i));
      __gnu_sequential::sort(__sample.begin(), __sample.end(), __lcomp);

      for (_SeqNumber __i = 0; __i < __m; __i++)       //conceptual infinity
        if (__n >= __ns[__i])   //__sequence too short, conceptual infinity
          __sample.push_back(
            std::make_pair(__S(__i)[0] /*__dummy element*/, __i));

      _DifferenceType __localrank = __rank / __l;

      _SeqNumber __j;
      for (__j = 0;
           __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]);
           ++__j)
        __a[__sample[__j].second] += __n + 1;
      for (; __j < __m; __j++)
        __b[__sample[__j].second] -= __n + 1;
      
      // Further refinement.
      while (__n > 0)
        {
          __n /= 2;

          _SeqNumber __lmax_seq = -1;  // to avoid warning
          const _ValueType* __lmax = 0; // impossible to avoid the warning?
          for (_SeqNumber __i = 0; __i < __m; __i++)
            {
              if (__a[__i] > 0)
                {
                  if (!__lmax)
                    {
                      __lmax = &(__S(__i)[__a[__i] - 1]);
                      __lmax_seq = __i;
                    }
                  else
                    {
                      // Max, favor rear sequences.
                      if (!__comp(__S(__i)[__a[__i] - 1], *__lmax))
                        {
                          __lmax = &(__S(__i)[__a[__i] - 1]);
                          __lmax_seq = __i;
                        }
                    }
                }
            }

          _SeqNumber __i;
          for (__i = 0; __i < __m; __i++)
            {
              _DifferenceType __middle = (__b[__i] + __a[__i]) / 2;
              if (__lmax && __middle < __ns[__i] &&
                  __lcomp(std::make_pair(__S(__i)[__middle], __i),
                        std::make_pair(*__lmax, __lmax_seq)))
                __a[__i] = std::min(__a[__i] + __n + 1, __ns[__i]);
              else
                __b[__i] -= __n + 1;
            }

          _DifferenceType __leftsize = 0;
          for (_SeqNumber __i = 0; __i < __m; __i++)
              __leftsize += __a[__i] / (__n + 1);

          _DifferenceType __skew = __rank / (__n + 1) - __leftsize;

          if (__skew > 0)
            {
              // Move to the left, find smallest.
              std::priority_queue<std::pair<_ValueType, _SeqNumber>,
                std::vector<std::pair<_ValueType, _SeqNumber> >,
                _LexicographicReverse<_ValueType, _SeqNumber, _Compare> >
                __pq(__lrcomp);
              
              for (_SeqNumber __i = 0; __i < __m; __i++)
                if (__b[__i] < __ns[__i])
                  __pq.push(std::make_pair(__S(__i)[__b[__i]], __i));

              for (; __skew != 0 && !__pq.empty(); --__skew)
                {
                  _SeqNumber __source = __pq.top().second;
                  __pq.pop();

                  __a[__source]
                      = std::min(__a[__source] + __n + 1, __ns[__source]);
                  __b[__source] += __n + 1;

                  if (__b[__source] < __ns[__source])
                    __pq.push(
                      std::make_pair(__S(__source)[__b[__source]], __source));
                }
            }
          else if (__skew < 0)
            {
              // Move to the right, find greatest.
              std::priority_queue<std::pair<_ValueType, _SeqNumber>,
                std::vector<std::pair<_ValueType, _SeqNumber> >,
                _Lexicographic<_ValueType, _SeqNumber, _Compare> >
                  __pq(__lcomp);

              for (_SeqNumber __i = 0; __i < __m; __i++)
                if (__a[__i] > 0)
                  __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i));

              for (; __skew != 0; ++__skew)
                {
                  _SeqNumber __source = __pq.top().second;
                  __pq.pop();

                  __a[__source] -= __n + 1;
                  __b[__source] -= __n + 1;

                  if (__a[__source] > 0)
                    __pq.push(std::make_pair(
                        __S(__source)[__a[__source] - 1], __source));
                }
            }
        }

      // Postconditions:
      // __a[__i] == __b[__i] in most cases, except when __a[__i] has been
      // clamped because of having reached the boundary

      // Now return the result, calculate the offset.

      // Compare the keys on both edges of the border.

      // Maximum of left edge, minimum of right edge.
      _ValueType* __maxleft = 0;
      _ValueType* __minright = 0;
      for (_SeqNumber __i = 0; __i < __m; __i++)
        {
          if (__a[__i] > 0)
            {
              if (!__maxleft)
                __maxleft = &(__S(__i)[__a[__i] - 1]);
              else
                {
                  // Max, favor rear sequences.
                  if (!__comp(__S(__i)[__a[__i] - 1], *__maxleft))
                    __maxleft = &(__S(__i)[__a[__i] - 1]);
                }
            }
          if (__b[__i] < __ns[__i])
            {
              if (!__minright)
                __minright = &(__S(__i)[__b[__i]]);
              else
                {
                  // Min, favor fore sequences.
                  if (__comp(__S(__i)[__b[__i]], *__minright))
                    __minright = &(__S(__i)[__b[__i]]);
                }
            }
        }

      _SeqNumber __seq = 0;
      for (_SeqNumber __i = 0; __i < __m; __i++)
        __begin_offsets[__i] = __S(__i) + __a[__i];

      delete[] __ns;
      delete[] __a;
      delete[] __b;
    }

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.

    {
      _GLIBCXX_CALL(__end_seqs - __begin_seqs)

      typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type
        _It;
      typedef typename std::iterator_traits<_RanSeqs>::difference_type
        _SeqNumber;
      typedef typename std::iterator_traits<_It>::difference_type
        _DifferenceType;

      _Lexicographic<_Tp, _SeqNumber, _Compare> __lcomp(__comp);
      _LexicographicReverse<_Tp, _SeqNumber, _Compare> __lrcomp(__comp);

      // Number of sequences, number of elements in total (possibly
      // including padding).
      _DifferenceType __m = std::distance(__begin_seqs, __end_seqs);
      _DifferenceType __nn = 0;
      _DifferenceType __nmax, __n, __r;

      for (_SeqNumber __i = 0; __i < __m; __i++)
        __nn += std::distance(__begin_seqs[__i].first,
                  __begin_seqs[__i].second);

      if (__m == 0 || __nn == 0 || __rank < 0 || __rank >= __nn)
        {
          // result undefined if there is no data or __rank is outside bounds
          throw std::exception();
        }


      _DifferenceType* __ns = new _DifferenceType[__m];
      _DifferenceType* __a = new _DifferenceType[__m];
      _DifferenceType* __b = new _DifferenceType[__m];
      _DifferenceType __l;

      __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second);
      __nmax = __ns[0];
      for (_SeqNumber __i = 0; __i < __m; ++__i)
        {
          __ns[__i] = std::distance(__begin_seqs[__i].first,
                                    __begin_seqs[__i].second);
          __nmax = std::max(__nmax, __ns[__i]);
        }

      __r = __rd_log2(__nmax) + 1;

      // Pad all lists to this length, at least as long as any ns[__i],
      // equality iff __nmax = 2^__k - 1
      __l = __round_up_to_pow2(__r) - 1;

      for (_SeqNumber __i = 0; __i < __m; ++__i)
        {
          __a[__i] = 0;
          __b[__i] = __l;
        }
      __n = __l / 2;

      // Invariants:
      // 0 <= __a[__i] <= __ns[__i], 0 <= __b[__i] <= __l

#define __S(__i) (__begin_seqs[__i].first)

      // Initial partition.
      std::vector<std::pair<_Tp, _SeqNumber> > __sample;

      for (_SeqNumber __i = 0; __i < __m; __i++)
        if (__n < __ns[__i])
          __sample.push_back(std::make_pair(__S(__i)[__n], __i));
      __gnu_sequential::sort(__sample.begin(), __sample.end(),
                             __lcomp, sequential_tag());

      // Conceptual infinity.
      for (_SeqNumber __i = 0; __i < __m; __i++)
        if (__n >= __ns[__i])
          __sample.push_back(
            std::make_pair(__S(__i)[0] /*__dummy element*/, __i));

      _DifferenceType __localrank = __rank / __l;

      _SeqNumber __j;
      for (__j = 0;
           __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]);
           ++__j)
        __a[__sample[__j].second] += __n + 1;
      for (; __j < __m; ++__j)
        __b[__sample[__j].second] -= __n + 1;

      // Further refinement.
      while (__n > 0)
        {
          __n /= 2;

          const _Tp* __lmax = 0;
          for (_SeqNumber __i = 0; __i < __m; ++__i)
            {
              if (__a[__i] > 0)
                {
                  if (!__lmax)
                    __lmax = &(__S(__i)[__a[__i] - 1]);
                  else
                    {
                      if (__comp(*__lmax, __S(__i)[__a[__i] - 1]))      //max
                        __lmax = &(__S(__i)[__a[__i] - 1]);
                    }
                }
            }

          _SeqNumber __i;
          for (__i = 0; __i < __m; __i++)
            {
              _DifferenceType __middle = (__b[__i] + __a[__i]) / 2;
              if (__lmax && __middle < __ns[__i]
                  && __comp(__S(__i)[__middle], *__lmax))
                __a[__i] = std::min(__a[__i] + __n + 1, __ns[__i]);
              else
                __b[__i] -= __n + 1;
            }

          _DifferenceType __leftsize = 0;
          for (_SeqNumber __i = 0; __i < __m; ++__i)
              __leftsize += __a[__i] / (__n + 1);

          _DifferenceType __skew = __rank / (__n + 1) - __leftsize;

          if (__skew > 0)
            {
              // Move to the left, find smallest.
              std::priority_queue<std::pair<_Tp, _SeqNumber>,
                std::vector<std::pair<_Tp, _SeqNumber> >,
                _LexicographicReverse<_Tp, _SeqNumber, _Compare> >
                  __pq(__lrcomp);

              for (_SeqNumber __i = 0; __i < __m; ++__i)
                if (__b[__i] < __ns[__i])
                  __pq.push(std::make_pair(__S(__i)[__b[__i]], __i));

              for (; __skew != 0 && !__pq.empty(); --__skew)
                {
                  _SeqNumber __source = __pq.top().second;
                  __pq.pop();

                  __a[__source]
                      = std::min(__a[__source] + __n + 1, __ns[__source]);
                  __b[__source] += __n + 1;

                  if (__b[__source] < __ns[__source])
                    __pq.push(
                      std::make_pair(__S(__source)[__b[__source]], __source));
                }
            }
          else if (__skew < 0)
            {
              // Move to the right, find greatest.
              std::priority_queue<std::pair<_Tp, _SeqNumber>,
                std::vector<std::pair<_Tp, _SeqNumber> >,
                _Lexicographic<_Tp, _SeqNumber, _Compare> > __pq(__lcomp);

              for (_SeqNumber __i = 0; __i < __m; ++__i)
                if (__a[__i] > 0)
                  __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i));

              for (; __skew != 0; ++__skew)
                {
                  _SeqNumber __source = __pq.top().second;
                  __pq.pop();

                  __a[__source] -= __n + 1;
                  __b[__source] -= __n + 1;

                  if (__a[__source] > 0)
                    __pq.push(std::make_pair(
                        __S(__source)[__a[__source] - 1], __source));
                }
            }
        }

      // Postconditions:
      // __a[__i] == __b[__i] in most cases, except when __a[__i] has been
      // clamped because of having reached the boundary

      // Now return the result, calculate the offset.

      // Compare the keys on both edges of the border.

      // Maximum of left edge, minimum of right edge.
      bool __maxleftset = false, __minrightset = false;

      // Impossible to avoid the warning?
      _Tp __maxleft, __minright;
      for (_SeqNumber __i = 0; __i < __m; ++__i)
        {
          if (__a[__i] > 0)
            {
              if (!__maxleftset)
                {
                  __maxleft = __S(__i)[__a[__i] - 1];
                  __maxleftset = true;
                }
              else
                {
                  // Max.
                  if (__comp(__maxleft, __S(__i)[__a[__i] - 1]))
                    __maxleft = __S(__i)[__a[__i] - 1];
                }
            }
          if (__b[__i] < __ns[__i])
            {
              if (!__minrightset)
                {
                  __minright = __S(__i)[__b[__i]];
                  __minrightset = true;
                }
              else
                {
                  // Min.
                  if (__comp(__S(__i)[__b[__i]], __minright))
                    __minright = __S(__i)[__b[__i]];
                }
            }
      }

      // Minright is the __splitter, in any case.

      if (!__maxleftset || __comp(__minright, __maxleft))
        {
          // Good luck, everything is split unambiguously.
          __offset = 0;
        }
      else
        {
          // We have to calculate an offset.
          __offset = 0;

          for (_SeqNumber __i = 0; __i < __m; ++__i)
            {
              _DifferenceType lb
                = std::lower_bound(__S(__i), __S(__i) + __ns[__i],
                                   __minright,
                                   __comp) - __S(__i);
              __offset += __a[__i] - lb;
            }
        }

      delete[] __ns;
      delete[] __a;
      delete[] __b;

      return __minright;
    }

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

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute multiway merge *sequentially*.
      return __sequential_multiway_merge
    </* __stable = */ false, /* __sentinels = */ false>
    (__seqs_begin, __seqs_end, __target,
     *(__seqs_begin->second), __length, __comp);
    }

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
	)

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute merge; maybe parallel, depending on the number of merged
      // elements and the number of sequences and global thresholds in
      // Settings.
      if ((__seqs_end - __seqs_begin > 1)
      && _GLIBCXX_PARALLEL_CONDITION(
            ((__seqs_end - __seqs_begin) >=
               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
            && ((_SequenceIndex)__length >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
    return parallel_multiway_merge
      </* __stable = */ false, /* __sentinels = */ false>
      (__seqs_begin, __seqs_end, __target,
       multiway_merge_exact_splitting</* __stable = */ false,
       typename std::iterator_traits<_RAIterPairIterator>
       ::value_type*, _Compare, _DifferenceTp>,
       static_cast<_DifferenceType>(__length), __comp,
       __tag.__get_num_threads());
      else
    return __sequential_multiway_merge
      </* __stable = */ false, /* __sentinels = */ false>
      (__seqs_begin, __seqs_end, __target,
       *(__seqs_begin->second), __length, __comp);
    }

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
	)

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute merge; maybe parallel, depending on the number of merged
      // elements and the number of sequences and global thresholds in
      // Settings.
      if ((__seqs_end - __seqs_begin > 1)
      && _GLIBCXX_PARALLEL_CONDITION(
            ((__seqs_end - __seqs_begin) >=
               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
            && ((_SequenceIndex)__length >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
    return parallel_multiway_merge
      </* __stable = */ false, /* __sentinels = */ false>
      (__seqs_begin, __seqs_end, __target,
       multiway_merge_exact_splitting</* __stable = */ false,
       typename std::iterator_traits<_RAIterPairIterator>
       ::value_type*, _Compare, _DifferenceTp>,
       static_cast<_DifferenceType>(__length), __comp,
       __tag.__get_num_threads());
      else
    return __sequential_multiway_merge
      </* __stable = */ false, /* __sentinels = */ false>
      (__seqs_begin, __seqs_end, __target,
       *(__seqs_begin->second), __length, __comp);
    }

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

    { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
                __comp, exact_tag(__tag.__get_num_threads())); }

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
	)

    { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
                __comp, exact_tag(__tag.__get_num_threads())); }

template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >

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

Highly efficient 3-way merging procedure.

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

This works well for merging up to 4 sequences.

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

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

Parameters

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

Returns

End iterator of output sequence.

    {
      _GLIBCXX_CALL(__length);

      typedef _DifferenceTp _DifferenceType;

      typedef typename std::iterator_traits<_RAIterIterator>
    ::value_type::first_type
    _RAIter1;
      typedef typename std::iterator_traits<_RAIter1>::value_type
    _ValueType;

      if (__length == 0)
    return __target;

#if _GLIBCXX_ASSERTIONS
      _DifferenceTp __orig_length = __length;
#endif

      iterator<_RAIter1, _Compare>
    __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
    __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
    __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp);

      if (__seq0 <= __seq1)
    {
          if (__seq1 <= __seq2)
            goto __s012;
          else
            if (__seq2 <  __seq0)
              goto __s201;
            else
              goto __s021;
    }
      else
    {
          if (__seq1 <= __seq2)
            {
              if (__seq0 <= __seq2)
            goto __s102;
              else
            goto __s120;
            }
          else
            goto __s210;
    }
#define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1) \
      __s ## __a ## __b ## __c :                            \
    *__target = *__seq ## __a;                          \
    ++__target;                                         \
    --__length;                                         \
    ++__seq ## __a;                                     \
    if (__length == 0) goto __finish;                   \
    if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \
    if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \
    goto __s ## __b ## __c ## __a;

      _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
      _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
      _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
      _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
      _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
      _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );

#undef _GLIBCXX_PARALLEL_MERGE_3_CASE

    __finish:
      ;

#if _GLIBCXX_ASSERTIONS
    _GLIBCXX_PARALLEL_ASSERT(
    ((_RAIter1)__seq0 - __seqs_begin[0].first) +
    ((_RAIter1)__seq1 - __seqs_begin[1].first) +
    ((_RAIter1)__seq2 - __seqs_begin[2].first)
    == __orig_length);
#endif

      __seqs_begin[0].first = __seq0;
      __seqs_begin[1].first = __seq1;
      __seqs_begin[2].first = __seq2;

      return __target;
    }

template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >

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

Highly efficient 4-way merging procedure.

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

This works well for merging up to 4 sequences.

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

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

Parameters

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

Returns

End iterator of output sequence.

    {
      _GLIBCXX_CALL(__length);
      typedef _DifferenceTp _DifferenceType;

      typedef typename std::iterator_traits<_RAIterIterator>
    ::value_type::first_type
    _RAIter1;
      typedef typename std::iterator_traits<_RAIter1>::value_type
    _ValueType;

      iterator<_RAIter1, _Compare>
    __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
    __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
    __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp),
    __seq3(__seqs_begin[3].first, __seqs_begin[3].second, __comp);

#define _GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d) {  \
    if (__seq ## __d < __seq ## __a)          \
      goto __s ## __d ## __a ## __b ## __c;       \
    if (__seq ## __d < __seq ## __b)          \
      goto __s ## __a ## __d ## __b ## __c;       \
    if (__seq ## __d < __seq ## __c)          \
      goto __s ## __a ## __b ## __d ## __c;       \
    goto __s ## __a ## __b ## __c ## __d;  }

      if (__seq0 <= __seq1)
    {
          if (__seq1 <= __seq2)
            _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
            else
              if (__seq2 < __seq0)
            _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
            else
                  _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
                    }
      else
    {
          if (__seq1 <= __seq2)
            {
              if (__seq0 <= __seq2)
            _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
            else
                  _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
                    }
          else
            _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
              }

#define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d,  \
                       __c0, __c1, __c2)    \
      __s ## __a ## __b ## __c ## __d:                      \
      if (__length == 0) goto __finish;                     \
      *__target = *__seq ## __a;                            \
      ++__target;                                           \
      --__length;                                           \
      ++__seq ## __a;                                       \
      if (__seq ## __a __c0 __seq ## __b)      \
    goto __s ## __a ## __b ## __c ## __d;  \
      if (__seq ## __a __c1 __seq ## __c)      \
    goto __s ## __b ## __a ## __c ## __d;  \
      if (__seq ## __a __c2 __seq ## __d)      \
    goto __s ## __b ## __c ## __a ## __d;  \
      goto __s ## __b ## __c ## __d ## __a;

      _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
      _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
      _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
      _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
      _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
      _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
      _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
      _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
      _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
      _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
      _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
      _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
      _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );

#undef _GLIBCXX_PARALLEL_MERGE_4_CASE
#undef _GLIBCXX_PARALLEL_DECISION

    __finish:
      ;

      __seqs_begin[0].first = __seq0;
      __seqs_begin[1].first = __seq1;
      __seqs_begin[2].first = __seq2;
      __seqs_begin[3].first = __seq3;

      return __target;
    }

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.

    {
      typedef typename std::iterator_traits<_RAIterIterator>
    ::difference_type _SeqNumber;
      typedef typename std::iterator_traits<_RAIterIterator>
    ::value_type::first_type
    _RAIter1;

      const bool __tight = (__total_length == __length);

      // __k sequences.
      const _SeqNumber __k = __seqs_end - __seqs_begin;

      const _ThreadIndex __num_threads = omp_get_num_threads();

      // (Settings::multiway_merge_splitting
      //  == __gnu_parallel::_Settings::EXACT).
      std::vector<_RAIter1>* __offsets = 
    new std::vector<_RAIter1>[__num_threads];
      std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k);

      copy(__seqs_begin, __seqs_end, __se.begin());

      _DifferenceType* __borders =
    new _DifferenceType[__num_threads + 1];
      __equally_split(__length, __num_threads, __borders);

      for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s)
    {
      __offsets[__s].resize(__k);
      multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1],
                 __offsets[__s].begin(), __comp);

      // Last one also needed and available.
      if (!__tight)
        {
          __offsets[__num_threads - 1].resize(__k);
          multiseq_partition(__se.begin(), __se.end(),
                 _DifferenceType(__length),
                 __offsets[__num_threads - 1].begin(),
                 __comp);
        }
    }
      delete[] __borders;

      for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
    {
      // For each slab / processor.
      for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
        {
          // For each sequence.
          if (__slab == 0)
        {
          // Absolute beginning.
          __pieces[__slab][__seq].first = 0;
        }
          else
        __pieces[__slab][__seq].first =
          __pieces[__slab - 1][__seq].second;
          if (!__tight || __slab < (__num_threads - 1))
        __pieces[__slab][__seq].second =
          __offsets[__slab][__seq] - __seqs_begin[__seq].first;
          else
        {
          // __slab == __num_threads - 1
          __pieces[__slab][__seq].second =
                    _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
        }
        }
    }
      delete[] __offsets;
    }

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.

    {
      _GLIBCXX_CALL(__length)

      typedef _DifferenceTp _DifferenceType;
      typedef typename std::iterator_traits<_RAIterIterator>
    ::difference_type _SeqNumber;
      typedef typename std::iterator_traits<_RAIterIterator>
    ::value_type::first_type
    _RAIter1;
      typedef typename std::iterator_traits<_RAIter1>::value_type
    _ValueType;

      _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);

      _LT __lt(__k, __comp);

      // Default value for potentially non-default-constructible types.
      _ValueType* __arbitrary_element = 0;

      for (_SeqNumber __t = 0; __t < __k; ++__t)
    {
          if(!__arbitrary_element
         && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
            __arbitrary_element = &(*__seqs_begin[__t].first);
    }

      for (_SeqNumber __t = 0; __t < __k; ++__t)
    {
          if (__seqs_begin[__t].first == __seqs_begin[__t].second)
            __lt.__insert_start(*__arbitrary_element, __t, true);
          else
            __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
    }

      __lt.__init();

      _SeqNumber __source;

      for (_DifferenceType __i = 0; __i < __length; ++__i)
    {
          //take out
          __source = __lt.__get_min_source();

          *(__target++) = *(__seqs_begin[__source].first++);

          // Feed.
          if (__seqs_begin[__source].first == __seqs_begin[__source].second)
            __lt.__delete_min_insert(*__arbitrary_element, true);
          else
            // Replace from same __source.
            __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
    }

      return __target;
    }

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.

    {
      _GLIBCXX_CALL(__length)

      typedef _DifferenceTp _DifferenceType;
      typedef std::iterator_traits<_RAIterIterator> _TraitsType;
      typedef typename std::iterator_traits<_RAIterIterator>
    ::value_type::first_type
    _RAIter1;
      typedef typename std::iterator_traits<_RAIter1>::value_type
    _ValueType;

      _RAIter3 __target_end;

      for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
    // Move the sequence ends to the sentinel.  This has the
    // effect that the sentinel appears to be within the sequence. Then,
    // we can use the unguarded variant if we merge out as many
    // non-sentinel elements as we have.
    ++((*__s).second);

      __target_end = multiway_merge_loser_tree_unguarded<UnguardedLoserTree>
    (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);

#if _GLIBCXX_ASSERTIONS
      _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
      _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
#endif

      // Restore the sequence ends so the sentinels are not contained in the
      // sequence any more (see comment in loop above).
      for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
    --((*__s).second);

      return __target_end;
    }

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.

    {
      _GLIBCXX_CALL(__length)
      typedef _DifferenceTp _DifferenceType;

      typedef typename std::iterator_traits<_RAIterIterator>
    ::difference_type _SeqNumber;
      typedef typename std::iterator_traits<_RAIterIterator>
    ::value_type::first_type
    _RAIter1;
      typedef typename std::iterator_traits<_RAIter1>::value_type
    _ValueType;

      _SeqNumber __k = __seqs_end - __seqs_begin;

      _LT __lt(__k, __sentinel, __comp);

      for (_SeqNumber __t = 0; __t < __k; ++__t)
    {
#if _GLIBCXX_ASSERTIONS
          _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first
                                   != __seqs_begin[__t].second);
#endif
          __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
    }

      __lt.__init();

      _SeqNumber __source;

#if _GLIBCXX_ASSERTIONS
      _DifferenceType __i = 0;
#endif

      _RAIter3 __target_end = __target + __length;
      while (__target < __target_end)
    {
          // Take out.
          __source = __lt.__get_min_source();

#if _GLIBCXX_ASSERTIONS
          _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k);
          _GLIBCXX_PARALLEL_ASSERT(__i == 0
              || !__comp(*(__seqs_begin[__source].first), *(__target - 1)));
#endif

          // Feed.
          *(__target++) = *(__seqs_begin[__source].first++);

#if _GLIBCXX_ASSERTIONS
          ++__i;
#endif
          // Replace from same __source.
          __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
    }

      return __target;
    }

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.

    {
      typedef typename std::iterator_traits<_RAIterIterator>
    ::difference_type _SeqNumber;
      typedef typename std::iterator_traits<_RAIterIterator>
    ::value_type::first_type
    _RAIter1;
      typedef typename std::iterator_traits<_RAIter1>::value_type
    _ValueType;

      // __k sequences.
      const _SeqNumber __k
    = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);

      const _ThreadIndex __num_threads = omp_get_num_threads();

      const _DifferenceType __num_samples =
    __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;

      _ValueType* __samples = static_cast<_ValueType*>
    (::operator new(sizeof(_ValueType) * __k * __num_samples));
      // Sample.
      for (_SeqNumber __s = 0; __s < __k; ++__s)
    for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
      {
        _DifferenceType sample_index = static_cast<_DifferenceType>
          (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s])
           * (double(__i + 1) / (__num_samples + 1))
           * (double(__length) / __total_length));
        new(&(__samples[__s * __num_samples + __i]))
              _ValueType(__seqs_begin[__s].first[sample_index]);
      }

      // Sort stable or non-stable, depending on value of template parameter
      // "__stable".
      _SamplingSorter<__stable, _ValueType*, _Compare>()
    (__samples, __samples + (__num_samples * __k), __comp);

      for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
    // For each slab / processor.
    for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
      {
        // For each sequence.
        if (__slab > 0)
          __pieces[__slab][__seq].first = std::upper_bound
        (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
         __samples[__num_samples * __k * __slab / __num_threads],
         __comp)
        - __seqs_begin[__seq].first;
        else
          // Absolute beginning.
          __pieces[__slab][__seq].first = 0;
        if ((__slab + 1) < __num_threads)
          __pieces[__slab][__seq].second = std::upper_bound
        (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
         __samples[__num_samples * __k * (__slab + 1) / __num_threads],
         __comp)
        - __seqs_begin[__seq].first;
        else
              // Absolute end.
          __pieces[__slab][__seq].second =
        _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
      }

      for (_SeqNumber __s = 0; __s < __k; ++__s)
    for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
      __samples[__s * __num_samples + __i].~_ValueType();
      ::operator delete(__samples);
    }

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

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute multiway merge *sequentially*.
      return __sequential_multiway_merge
    </* __stable = */ false, /* __sentinels = */ true>
          (__seqs_begin, __seqs_end,
           __target, *(__seqs_begin->second), __length, __comp);
    }

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
	)

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute merge; maybe parallel, depending on the number of merged
      // elements and the number of sequences and global thresholds in
      // Settings.
      if ((__seqs_end - __seqs_begin > 1)
      && _GLIBCXX_PARALLEL_CONDITION(
            ((__seqs_end - __seqs_begin) >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
            && ((_SequenceIndex)__length >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
    return parallel_multiway_merge
          </* __stable = */ false, /* __sentinels = */ true>
      (__seqs_begin, __seqs_end, __target,
       multiway_merge_exact_splitting</* __stable = */ false,
       typename std::iterator_traits<_RAIterPairIterator>
       ::value_type*, _Compare, _DifferenceTp>,
       static_cast<_DifferenceType>(__length), __comp,
       __tag.__get_num_threads());
      else
    return __sequential_multiway_merge
          </* __stable = */ false, /* __sentinels = */ true>
      (__seqs_begin, __seqs_end, __target,
       *(__seqs_begin->second), __length, __comp);
    }

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
	)

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute merge; maybe parallel, depending on the number of merged
      // elements and the number of sequences and global thresholds in
      // Settings.
      if ((__seqs_end - __seqs_begin > 1)
      && _GLIBCXX_PARALLEL_CONDITION(
            ((__seqs_end - __seqs_begin) >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
            && ((_SequenceIndex)__length >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
    return parallel_multiway_merge
          </* __stable = */ false, /* __sentinels = */ true>
      (__seqs_begin, __seqs_end, __target,
       multiway_merge_sampling_splitting</* __stable = */ false,
       typename std::iterator_traits<_RAIterPairIterator>
       ::value_type*, _Compare, _DifferenceTp>,
       static_cast<_DifferenceType>(__length), __comp,
       __tag.__get_num_threads());
      else
    return __sequential_multiway_merge
          </* __stable = */false, /* __sentinels = */ true>(
            __seqs_begin, __seqs_end, __target,
        *(__seqs_begin->second), __length, __comp);
    }

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

    {
      return multiway_merge_sentinels
    (__seqs_begin, __seqs_end, __target, __length, __comp,
     exact_tag(__tag.__get_num_threads()));
    }

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
	)

    {
      return multiway_merge_sentinels
    (__seqs_begin, __seqs_end, __target, __length, __comp,
     exact_tag(__tag.__get_num_threads()));
    }

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.

      {
#if _GLIBCXX_ASSERTIONS
    _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
#endif

    _GLIBCXX_CALL(__length)

    typedef _DifferenceTp _DifferenceType;
        typedef typename std::iterator_traits<_RAIterIterator>
      ::difference_type _SeqNumber;
    typedef typename std::iterator_traits<_RAIterIterator>
          ::value_type::first_type
          _RAIter1;
    typedef typename
          std::iterator_traits<_RAIter1>::value_type _ValueType;

    // Leave only non-empty sequences.
    typedef std::pair<_RAIter1, _RAIter1> seq_type;
    seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
    _SeqNumber __k = 0;
    _DifferenceType __total_length = 0;
    for (_RAIterIterator __raii = __seqs_begin;
             __raii != __seqs_end; ++__raii)
          {
            _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
            if(__seq_length > 0)
              {
            __total_length += __seq_length;
            __ne_seqs[__k++] = *__raii;
              }
          }

    _GLIBCXX_CALL(__total_length)

    __length = std::min<_DifferenceTp>(__length, __total_length);

    if (__total_length == 0 || __k == 0)
      {
        delete[] __ne_seqs;
        return __target;
      }

    std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;

    __num_threads = static_cast<_ThreadIndex>
          (std::min<_DifferenceType>(__num_threads, __total_length));

#       pragma omp parallel num_threads (__num_threads)
    {
#         pragma omp single
      {
        __num_threads = omp_get_num_threads();
        // Thread __t will have to merge pieces[__iam][0..__k - 1]
        __pieces = new std::vector<
        std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
        for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
          __pieces[__s].resize(__k);

        _DifferenceType __num_samples =
          __gnu_parallel::_Settings::get().merge_oversampling
          * __num_threads;

        __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
               __comp, __pieces);
      } //single

      _ThreadIndex __iam = omp_get_thread_num();

      _DifferenceType __target_position = 0;

      for (_SeqNumber __c = 0; __c < __k; ++__c)
        __target_position += __pieces[__iam][__c].first;

      seq_type* __chunks = new seq_type[__k];

      for (_SeqNumber __s = 0; __s < __k; ++__s)
        __chunks[__s] = std::make_pair(__ne_seqs[__s].first
                       + __pieces[__iam][__s].first,
                       __ne_seqs[__s].first
                       + __pieces[__iam][__s].second);

      if(__length > __target_position)
        __sequential_multiway_merge<__stable, __sentinels>
          (__chunks, __chunks + __k, __target + __target_position,
           *(__seqs_begin->second), __length - __target_position, __comp);

      delete[] __chunks;
    } // parallel

#if _GLIBCXX_ASSERTIONS
    _GLIBCXX_PARALLEL_ASSERT(
          __is_sorted(__target, __target + __length, __comp));
#endif

    __k = 0;
    // Update ends of sequences.
    for (_RAIterIterator __raii = __seqs_begin;
             __raii != __seqs_end; ++__raii)
          {
            _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
            if(__length > 0)
              (*__raii).first += __pieces[__num_threads - 1][__k++].second;
          }

    delete[] __pieces;
    delete[] __ne_seqs;

    return __target + __length;
      }

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.

    {
      _GLIBCXX_CALL(__end - __begin)

      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _DifferenceType __n = __end - __begin;

      if (__n <= 1)
    return;

      // at least one element per thread
      if (__num_threads > __n)
    __num_threads = static_cast<_ThreadIndex>(__n);

      // shared variables
      _PMWMSSortingData<_RAIter> __sd;
      _DifferenceType* __starts;
      _DifferenceType __size;

#     pragma omp parallel num_threads(__num_threads)
      {
        __num_threads = omp_get_num_threads(); //no more threads than requested

#       pragma omp single
    {
      __sd._M_num_threads = __num_threads;
      __sd._M_source = __begin;
      
      __sd._M_temporary = new _ValueType*[__num_threads];

      if (!__exact)
        {
          __size =
        (_Settings::get().sort_mwms_oversampling * __num_threads - 1)
        * __num_threads;
          __sd._M_samples = static_cast<_ValueType*>
        (::operator new(__size * sizeof(_ValueType)));
        }
      else
        __sd._M_samples = 0;

      __sd._M_offsets = new _DifferenceType[__num_threads - 1];
      __sd._M_pieces
        = new std::vector<_Piece<_DifferenceType> >[__num_threads];
      for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
        __sd._M_pieces[__s].resize(__num_threads);
      __starts = __sd._M_starts = new _DifferenceType[__num_threads + 1];

      _DifferenceType __chunk_length = __n / __num_threads;
      _DifferenceType __split = __n % __num_threads;
      _DifferenceType __pos = 0;
      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
        {
          __starts[__i] = __pos;
          __pos += ((__i < __split)
            ? (__chunk_length + 1) : __chunk_length);
        }
      __starts[__num_threads] = __pos;
    } //single

        // Now sort in parallel.
        parallel_sort_mwms_pu<__stable, __exact>(&__sd, __comp);
      } //parallel

      delete[] __starts;
      delete[] __sd._M_temporary;

      if (!__exact)
    {
      for (_DifferenceType __i = 0; __i < __size; ++__i)
        __sd._M_samples[__i].~_ValueType();
      ::operator delete(__sd._M_samples);
    }

      delete[] __sd._M_offsets;
      delete[] __sd._M_pieces;
    }

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.

    {
      typedef std::iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;

      _ThreadIndex __iam = omp_get_thread_num();

      // Length of this thread's chunk, before merging.
      _DifferenceType __length_local =
    __sd->_M_starts[__iam + 1] - __sd->_M_starts[__iam];

      // Sort in temporary storage, leave space for sentinel.

      typedef _ValueType* _SortingPlacesIterator;

      __sd->_M_temporary[__iam] =
        static_cast<_ValueType*>(::operator new(sizeof(_ValueType)
                        * (__length_local + 1)));

      // Copy there.
      std::uninitialized_copy(__sd->_M_source + __sd->_M_starts[__iam],
                  __sd->_M_source + __sd->_M_starts[__iam]
                  + __length_local,
                  __sd->_M_temporary[__iam]);

      __possibly_stable_sort<__stable, _SortingPlacesIterator, _Compare>()
        (__sd->_M_temporary[__iam],
     __sd->_M_temporary[__iam] + __length_local,
         __comp);

      // Invariant: locally sorted subsequence in sd->_M_temporary[__iam],
      // __sd->_M_temporary[__iam] + __length_local.

      // No barrier here: Synchronization is done by the splitting routine.

      _DifferenceType __num_samples =
        _Settings::get().sort_mwms_oversampling * __sd->_M_num_threads - 1;
      _SplitConsistently<__exact, _RAIter, _Compare, _SortingPlacesIterator>()
        (__iam, __sd, __comp, __num_samples);

      // Offset from __target __begin, __length after merging.
      _DifferenceType __offset = 0, __length_am = 0;
      for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; __s++)
    {
      __length_am += (__sd->_M_pieces[__iam][__s]._M_end
              - __sd->_M_pieces[__iam][__s]._M_begin);
      __offset += __sd->_M_pieces[__iam][__s]._M_begin;
    }

      typedef std::vector<
        std::pair<_SortingPlacesIterator, _SortingPlacesIterator> >
        _SeqVector;
      _SeqVector __seqs(__sd->_M_num_threads);

      for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; ++__s)
    {
      __seqs[__s] =
        std::make_pair(__sd->_M_temporary[__s]
               + __sd->_M_pieces[__iam][__s]._M_begin,
               __sd->_M_temporary[__s]
               + __sd->_M_pieces[__iam][__s]._M_end);
    }

      __possibly_stable_multiway_merge<
        __stable, typename _SeqVector::iterator,
    _RAIter, _Compare, _DifferenceType>()(__seqs.begin(), __seqs.end(),
                     __sd->_M_source + __offset, __comp,
                     __length_am);

#     pragma omp barrier

      for (_DifferenceType __i = 0; __i < __length_local; ++__i)
    __sd->_M_temporary[__iam][__i].~_ValueType();
      ::operator delete(__sd->_M_temporary[__iam]);
    }

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
	)

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute multiway merge *sequentially*.
      return __sequential_multiway_merge
    </* __stable = */ true, /* __sentinels = */ false>
          (__seqs_begin, __seqs_end, __target,
       *(__seqs_begin->second), __length, __comp);
    }

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
	)

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute merge; maybe parallel, depending on the number of merged
      // elements and the number of sequences and global thresholds in
      // Settings.
      if ((__seqs_end - __seqs_begin > 1)
      && _GLIBCXX_PARALLEL_CONDITION(
            ((__seqs_end - __seqs_begin) >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
            && ((_SequenceIndex)__length >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
    return parallel_multiway_merge
          </* __stable = */ true, /* __sentinels = */ false>
      (__seqs_begin, __seqs_end, __target,
       multiway_merge_exact_splitting</* __stable = */ true,
       typename std::iterator_traits<_RAIterPairIterator>
       ::value_type*, _Compare, _DifferenceTp>,
       static_cast<_DifferenceType>(__length), __comp,
       __tag.__get_num_threads());
      else
    return __sequential_multiway_merge
      </* __stable = */ true, /* __sentinels = */ false>
      (__seqs_begin, __seqs_end, __target,
       *(__seqs_begin->second), __length, __comp);
    }

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
	)

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute merge; maybe parallel, depending on the number of merged
      // elements and the number of sequences and global thresholds in
      // Settings.
      if ((__seqs_end - __seqs_begin > 1)
      && _GLIBCXX_PARALLEL_CONDITION(
            ((__seqs_end - __seqs_begin) >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
            && ((_SequenceIndex)__length >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
    return parallel_multiway_merge
          </* __stable = */ true, /* __sentinels = */ false>
      (__seqs_begin, __seqs_end, __target,
       multiway_merge_sampling_splitting</* __stable = */ true,
       typename std::iterator_traits<_RAIterPairIterator>
       ::value_type*, _Compare, _DifferenceTp>,
       static_cast<_DifferenceType>(__length), __comp,
       __tag.__get_num_threads());
      else
    return __sequential_multiway_merge
          </* __stable = */ true, /* __sentinels = */ false>
      (__seqs_begin, __seqs_end, __target,
       *(__seqs_begin->second), __length, __comp);
    }

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

    {
      return stable_multiway_merge
    (__seqs_begin, __seqs_end, __target, __length, __comp,
     exact_tag(__tag.__get_num_threads()));
    }

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
	)

    {
      return stable_multiway_merge
    (__seqs_begin, __seqs_end, __target, __length, __comp,
     exact_tag(__tag.__get_num_threads()));
    }

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
	)

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute multiway merge *sequentially*.
      return __sequential_multiway_merge
    </* __stable = */ true, /* __sentinels = */ true>
    (__seqs_begin, __seqs_end, __target,
     *(__seqs_begin->second), __length, __comp);
    }

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
	)

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute merge; maybe parallel, depending on the number of merged
      // elements and the number of sequences and global thresholds in
      // Settings.
      if ((__seqs_end - __seqs_begin > 1)
      && _GLIBCXX_PARALLEL_CONDITION(
            ((__seqs_end - __seqs_begin) >=
            __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
            && ((_SequenceIndex)__length >=
            __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
    return parallel_multiway_merge
          </* __stable = */ true, /* __sentinels = */ true>
      (__seqs_begin, __seqs_end, __target,
       multiway_merge_exact_splitting</* __stable = */ true,
       typename std::iterator_traits<_RAIterPairIterator>
       ::value_type*, _Compare, _DifferenceTp>,
       static_cast<_DifferenceType>(__length), __comp,
       __tag.__get_num_threads());
      else
    return __sequential_multiway_merge
          </* __stable = */ true, /* __sentinels = */ true>
      (__seqs_begin, __seqs_end, __target,
       *(__seqs_begin->second), __length, __comp);
    }

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
	)

    {
      typedef _DifferenceTp _DifferenceType;
      _GLIBCXX_CALL(__seqs_end - __seqs_begin)

      // catch special case: no sequences
      if (__seqs_begin == __seqs_end)
    return __target;

      // Execute merge; maybe parallel, depending on the number of merged
      // elements and the number of sequences and global thresholds in
      // Settings.
      if ((__seqs_end - __seqs_begin > 1)
      && _GLIBCXX_PARALLEL_CONDITION(
            ((__seqs_end - __seqs_begin) >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
            && ((_SequenceIndex)__length >=
              __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
    return parallel_multiway_merge
          </* __stable = */ true, /* __sentinels = */ true>
      (__seqs_begin, __seqs_end, __target,
       multiway_merge_sampling_splitting</* __stable = */ true,
       typename std::iterator_traits<_RAIterPairIterator>
       ::value_type*, _Compare, _DifferenceTp>,
       static_cast<_DifferenceType>(__length), __comp,
       __tag.__get_num_threads());
      else
    return __sequential_multiway_merge
          </* __stable = */ true, /* __sentinels = */ true>
      (__seqs_begin, __seqs_end, __target,
       *(__seqs_begin->second), __length, __comp);
    }

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

    {
      return stable_multiway_merge_sentinels
    (__seqs_begin, __seqs_end, __target, __length, __comp,
     exact_tag(__tag.__get_num_threads()));
    }

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
	)

    {
      return stable_multiway_merge_sentinels
    (__seqs_begin, __seqs_end, __target, __length, __comp,
     exact_tag(__tag.__get_num_threads()));
    }

Variable Documentation

const int __gnu_parallel::_CASable_bits = std::numeric_limits<_CASable>::digits

static

Number of bits of _CASable.

const _CASable __gnu_parallel::_CASable_mask

static

Initial value:

=
                            ((_CASable(1) << (_CASable_bits / 2)) - 1)

_CASable with the right half of bits set to 1.