GNU g++  v5.2.1
GNU Standard C++
__gnu_parallel Namespace Reference

GNU parallel code for public use. More...

Classes

struct  __accumulate_binop_reduct
 General reduction, using a binary operator. More...
 
struct  __accumulate_selector
 std::accumulate() selector. More...
 
struct  __adjacent_difference_selector
 Selector that returns the difference between two adjacent __elements. More...
 
struct  __adjacent_find_selector
 Test predicate on two adjacent elements. 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  __count_if_selector
 std::count_if () selector. More...
 
struct  __count_selector
 std::count() selector. More...
 
struct  __difference_func
 
struct  __fill_selector
 std::fill() selector. More...
 
struct  __find_first_of_selector
 Test predicate on several elements. More...
 
struct  __find_if_selector
 Test predicate on a single element, used for std::find() and std::find_if (). More...
 
struct  __for_each_selector
 std::for_each() selector. More...
 
struct  __generate_selector
 std::generate() selector. More...
 
struct  __generic_find_selector
 Base class of all __gnu_parallel::__find_template selectors. More...
 
struct  __generic_for_each_selector
 Generic __selector for embarrassingly parallel functions. More...
 
struct  __identity_selector
 Selector that just returns the passed iterator. More...
 
struct  __inner_product_selector
 std::inner_product() selector. More...
 
struct  __intersection_func
 
struct  __max_element_reduct
 Reduction for finding the maximum element, using a comparator. More...
 
struct  __min_element_reduct
 Reduction for finding the maximum element, using a comparator. More...
 
struct  __mismatch_selector
 Test inverted predicate on a single element. 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  __possibly_stable_multiway_merge
 
struct  __possibly_stable_multiway_merge< false, Seq_RAIter, _RAIter, _Compare, _DiffType >
 
struct  __possibly_stable_multiway_merge< true, Seq_RAIter, _RAIter, _Compare, _DiffType >
 
struct  __possibly_stable_sort
 
struct  __possibly_stable_sort< false, _RAIter, _Compare >
 
struct  __possibly_stable_sort< true, _RAIter, _Compare >
 
struct  __replace_if_selector
 std::replace() selector. More...
 
struct  __replace_selector
 std::replace() selector. More...
 
struct  __symmetric_difference_func
 
struct  __transform1_selector
 std::transform() __selector, one input sequence variant. More...
 
struct  __transform2_selector
 std::transform() __selector, two input sequences variant. More...
 
class  __unary_negate
 Similar to std::unary_negate, but giving the argument types explicitly. More...
 
struct  __union_func
 
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  _DummyReduct
 Reduction function doing nothing. More...
 
class  _EqualFromLess
 Constructs predicate for equality from strict weak ordering predicate. More...
 
struct  _EqualTo
 Similar to std::equal_to, but allows two different types. More...
 
class  _GuardedIterator
 _Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. More...
 
class  _IteratorPair
 A pair of iterators. More...
 
class  _IteratorTriple
 A triple of iterators. More...
 
struct  _Job
 One __job for a certain thread. More...
 
struct  _Less
 Similar to std::less, but allows two different types. More...
 
struct  _Less< _Tp, _Tp >
 
class  _Lexicographic
 Compare __a pair of types lexicographically, ascending. More...
 
class  _LexicographicReverse
 Compare __a pair of types lexicographically, descending. More...
 
class  _LoserTree
 Stable _LoserTree variant. More...
 
class  _LoserTree< false, _Tp, _Compare >
 Unstable _LoserTree variant. More...
 
class  _LoserTreeBase
 Guarded loser/tournament tree. More...
 
class  _LoserTreePointer
 Stable _LoserTree implementation. More...
 
class  _LoserTreePointer< false, _Tp, _Compare >
 Unstable _LoserTree implementation. More...
 
class  _LoserTreePointerBase
 Base class of _Loser Tree implementation using pointers. More...
 
class  _LoserTreePointerUnguarded
 Stable unguarded _LoserTree variant storing pointers. More...
 
class  _LoserTreePointerUnguarded< false, _Tp, _Compare >
 Unstable unguarded _LoserTree variant storing pointers. More...
 
class  _LoserTreePointerUnguardedBase
 Unguarded loser tree, keeping only pointers to the elements in the tree structure. More...
 
struct  _LoserTreeTraits
 Traits for determining whether the loser tree should use pointers or copies. More...
 
class  _LoserTreeUnguarded
 Stable implementation of unguarded _LoserTree. More...
 
class  _LoserTreeUnguarded< false, _Tp, _Compare >
 Non-Stable implementation of unguarded _LoserTree. More...
 
class  _LoserTreeUnguardedBase
 Base class for unguarded _LoserTree implementation. More...
 
struct  _Multiplies
 Similar to std::multiplies, but allows two different types. More...
 
struct  _Multiplies< _Tp, _Tp, _Tp >
 
struct  _Nothing
 Functor doing nothing. More...
 
struct  _Piece
 Subsequence description. More...
 
struct  _Plus
 Similar to std::plus, but allows two different types. More...
 
struct  _Plus< _Tp, _Tp, _Tp >
 
struct  _PMWMSSortingData
 Data accessed by all threads. More...
 
class  _PseudoSequence
 Sequence that conceptually consists of multiple copies of the same element. More...
 
class  _PseudoSequenceIterator
 _Iterator associated with __gnu_parallel::_PseudoSequence. More...
 
struct  _QSBThreadLocal
 Information local to one thread in the parallel quicksort run. More...
 
class  _RandomNumber
 Random number generator, based on the Mersenne twister. More...
 
class  _RestrictedBoundedConcurrentQueue
 Double-ended queue of bounded size, allowing lock-free atomic access. More...
 
struct  _SamplingSorter
 Stable sorting functor. More...
 
struct  _SamplingSorter< false, _RAIter, _StrictWeakOrdering >
 Non-__stable sorting functor. More...
 
struct  _Settings
 class _Settings Run-time settings for the parallel mode including all tunable parameters. More...
 
struct  _SplitConsistently
 Split consistently. More...
 
struct  _SplitConsistently< false, _RAIter, _Compare, _SortingPlacesIterator >
 Split by sampling. More...
 
struct  _SplitConsistently< true, _RAIter, _Compare, _SortingPlacesIterator >
 Split by exact splitting. More...
 
class  _UnguardedIterator
 
struct  balanced_quicksort_tag
 Forces parallel sorting using balanced quicksort at compile time. More...
 
struct  balanced_tag
 Recommends parallel execution using dynamic load-balancing at compile time. More...
 
struct  constant_size_blocks_tag
 Selects the constant block size variant for std::find(). More...
 
struct  default_parallel_tag
 Recommends parallel execution using the default parallel algorithm. More...
 
struct  equal_split_tag
 Selects the equal splitting variant for std::find(). More...
 
struct  exact_tag
 Forces parallel merging with exact splitting, at compile time. More...
 
struct  find_tag
 Base class for for std::find() variants. More...
 
struct  growing_blocks_tag
 Selects the growing block size variant for std::find(). 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  multiway_mergesort_tag
 Forces parallel sorting using multiway mergesort at compile time. More...
 
struct  omp_loop_static_tag
 Recommends parallel execution using OpenMP static load-balancing at compile time. More...
 
struct  omp_loop_tag
 Recommends parallel execution using OpenMP dynamic load-balancing at compile time. More...
 
struct  parallel_tag
 Recommends parallel execution at compile time, optionally using a user-specified number of threads. More...
 
struct  quicksort_tag
 Forces parallel sorting using unbalanced quicksort at compile time. More...
 
struct  sampling_tag
 Forces parallel merging with exact splitting, at compile time. More...
 
struct  sequential_tag
 Forces sequential execution at compile time. More...
 
struct  unbalanced_tag
 Recommends parallel execution using static load-balancing at compile time. More...
 

Typedefs

typedef unsigned short _BinIndex
 Type to hold the index of a bin. More...
 
typedef int64_t _CASable
 Longest compare-and-swappable integer type on this platform. More...
 
typedef uint64_t _SequenceIndex
 Unsigned integer to index __elements. More...
 
typedef uint16_t _ThreadIndex
 Unsigned integer to index a thread number. More...
 

Enumerations

enum  _AlgorithmStrategy {
  heuristic,
  force_sequential,
  force_parallel
}
 Strategies for run-time algorithm selection: More...
 
enum  _FindAlgorithm {
  GROWING_BLOCKS,
  CONSTANT_SIZE_BLOCKS,
  EQUAL_SPLIT
}
 Find algorithms: More...
 
enum  _MultiwayMergeAlgorithm { LOSER_TREE }
 Merging algorithms: More...
 
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  _PartialSumAlgorithm {
  RECURSIVE,
  LINEAR
}
 Partial sum algorithms: recursive, linear. More...
 
enum  _SortAlgorithm {
  MWMS,
  QS,
  QS_BALANCED
}
 Sorting algorithms: More...
 
enum  _SplittingAlgorithm {
  SAMPLING,
  EXACT
}
 Sorting/merging algorithms: sampling, __exact. More...
 

Functions

template<typename _Tp >
_Tp __add_omp (volatile _Tp *__ptr, _Tp __addend)
 
template<typename _RAIter , typename _DifferenceTp >
void __calc_borders (_RAIter __elements, _DifferenceTp __length, _DifferenceTp *__off)
 Precalculate __advances for Knuth-Morris-Pratt algorithm. 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...
 
template<typename _IIter , typename _OutputIterator >
_OutputIterator __copy_tail (std::pair< _IIter, _IIter > __b, std::pair< _IIter, _IIter > __e, _OutputIterator __r)
 
void __decode2 (_CASable __x, int &__a, int &__b)
 Decode two integers from one gnu_parallel::_CASable. More...
 
template<typename _RAIter , typename _DifferenceTp >
void __determine_samples (_PMWMSSortingData< _RAIter > *__sd, _DifferenceTp __num_samples)
 Select _M_samples from a sequence. More...
 
_CASable __encode2 (int __a, int __b)
 Encode two integers into one gnu_parallel::_CASable. 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 _Tp >
_Tp __fetch_and_add (volatile _Tp *__ptr, _Tp __addend)
 Add a value to a variable, atomically. 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 _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 _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_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...
 
_ThreadIndex __get_max_threads ()
 
bool __is_parallel (const _Parallelism __p)
 
template<typename _IIter , typename _Compare >
bool __is_sorted (_IIter __begin, _IIter __end, _Compare __comp)
 Check whether [__begin, __end) is sorted according to __comp. 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 _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 _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_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 _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 _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 _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 _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 _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 _RandomNumberGenerator >
void __parallel_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng=_RandomNumber())
 Parallel random public call. 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 __parallel_random_shuffle_drs_pu (_DRSSorterPU< _RAIter, _RandomNumberGenerator > *__pus)
 Random shuffle code executed by each thread. More...
 
template<typename _IIter , typename _OutputIterator , typename _Compare >
_OutputIterator __parallel_set_difference (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp)
 
template<typename _IIter , typename _OutputIterator , typename _Compare >
_OutputIterator __parallel_set_intersection (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp)
 
template<typename _IIter , typename _OutputIterator , typename _Operation >
_OutputIterator __parallel_set_operation (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Operation __op)
 
template<typename _IIter , typename _OutputIterator , typename _Compare >
_OutputIterator __parallel_set_symmetric_difference (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp)
 
template<typename _IIter , typename _OutputIterator , typename _Compare >
_OutputIterator __parallel_set_union (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp)
 
template<bool __stable, typename _RAIter , typename _Compare , typename _Parallelism >
void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, _Parallelism __parallelism)
 
template<bool __stable, typename _RAIter , typename _Compare >
void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_tag __parallelism)
 Choose multiway mergesort, splitting variant at run-time, for parallel sorting. 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 _RAIter , typename _Compare >
void __parallel_sort_qs (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
 Unbalanced quicksort main call. 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 >
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_qsb (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)
 Top-level quicksort routine. 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 _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 >
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_local_sort_with_helping (_QSBThreadLocal< _RAIter > **__tls, _Compare &__comp, _ThreadIndex __iam, bool __wait)
 Quicksort step doing load-balanced local sort. More...
 
template<typename _RandomNumberGenerator >
int __random_number_pow2 (int __logp, _RandomNumberGenerator &__rng)
 Generate a random number in [0,2^__logp). More...
 
template<typename _Size >
_Size __rd_log2 (_Size __n)
 Calculates the rounded-down logarithm of __n for base 2. More...
 
template<typename _Tp >
_Tp __round_up_to_pow2 (_Tp __x)
 Round up to the next greater power of 2. 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<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<typename _RAIter , typename _RandomNumberGenerator >
void __sequential_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng)
 Sequential cache-efficient random shuffle. 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 >
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...
 
void __yield ()
 Yield control to another thread, without waiting for the end of the time slice. 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 _Tp >
const _Tp & max (const _Tp &__a, const _Tp &__b)
 Equivalent to std::max. More...
 
template<typename _Tp >
const _Tp & min (const _Tp &__a, const _Tp &__b)
 Equivalent to std::min. 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. 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<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<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<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<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 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<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<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<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<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<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<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<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
 
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
 
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag)
 
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
 
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
 
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)
 
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)
 
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag)
 
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))
 
template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare >
_RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)
 

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.

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

Strategies for run-time algorithm selection:

Enumerator
heuristic 
force_sequential 
force_parallel 

Find algorithms:

Enumerator
GROWING_BLOCKS 
CONSTANT_SIZE_BLOCKS 
EQUAL_SPLIT 

Merging algorithms:

Enumerator
LOSER_TREE 

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.

Partial sum algorithms: recursive, linear.

Enumerator
RECURSIVE 
LINEAR 

Sorting algorithms:

Enumerator
MWMS 
QS 
QS_BALANCED 

Sorting/merging algorithms: sampling, __exact.

Enumerator
SAMPLING 
EXACT 

Function Documentation

template<typename _Tp >
_Tp __gnu_parallel::__add_omp ( volatile _Tp *  __ptr,
_Tp  __addend 
)
inline

Referenced by __fetch_and_add().

Here is the caller graph for this function:

template<typename _RAIter , typename _DifferenceTp >
void __gnu_parallel::__calc_borders ( _RAIter  __elements,
_DifferenceTp  __length,
_DifferenceTp *  __off 
)

Precalculate __advances for Knuth-Morris-Pratt algorithm.

Parameters
__elementsBegin iterator of sequence to search for.
__lengthLength of sequence to search for.
__offReturned __offsets.

Referenced by __search_template().

Here is the caller graph for this function:

template<typename _Tp >
bool __gnu_parallel::__cas_omp ( volatile _Tp *  __ptr,
_Tp  __comparand,
_Tp  __replacement 
)
inline

Referenced by __compare_and_swap().

Here is the caller graph for this function:

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

References __cas_omp().

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

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename _IIter , typename _OutputIterator >
_OutputIterator __gnu_parallel::__copy_tail ( std::pair< _IIter, _IIter >  __b,
std::pair< _IIter, _IIter >  __e,
_OutputIterator  __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.
__aFirst integer, to be decoded from the most-significant _CASable_bits/2 bits of __x.
__bSecond integer, to be encoded in the least-significant _CASable_bits/2 bits of __x.
See also
__encode2

References _CASable_bits, and _CASable_mask.

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

Here is the caller graph for this function:

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

Select _M_samples from a sequence.

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

References __equally_split(), __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_samples, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, and __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts.

Referenced by __gnu_parallel::_SplitConsistently< false, _RAIter, _Compare, _SortingPlacesIterator >::operator()().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Encode two integers into one gnu_parallel::_CASable.

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

References _CASable_bits.

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

Here is the caller graph for this function:

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

function to split a sequence into parts of almost equal size.

The resulting sequence __s of length __num_threads+1 contains the splitting positions when splitting the range [0,__n) into parts of almost equal size (plus minus 1). The first entry is 0, the last one n. There may result empty parts.

Parameters
__nNumber of elements
__num_threadsNumber of parts
__sSplitters
Returns
End of __splitter sequence, i.e. __s+__num_threads+1

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

Here is the caller graph for this function:

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

function to split a sequence into parts of almost equal size.

Returns the position of the splitting point between thread number __thread_no (included) and thread number __thread_no+1 (excluded).

Parameters
__nNumber of elements
__num_threadsNumber of parts
__thread_noNumber of threads
Returns
splitting point

Referenced by __for_each_template_random_access_ed().

Here is the caller graph for this function:

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

Add a value to a variable, atomically.

Parameters
__ptrPointer to a signed integer.
__addendValue to add.

References __add_omp().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Parallel std::find, switch for different algorithms.

Parameters
__begin1Begin iterator of first sequence.
__end1End iterator of first sequence.
__begin2Begin iterator of second sequence. Must have same length as first sequence.
__predFind predicate.
__selector_Functionality (e. g. std::find_if(), std::equal(),...)
Returns
Place of finding in both sequences.

References _GLIBCXX_PARALLEL_ASSERT, CONSTANT_SIZE_BLOCKS, EQUAL_SPLIT, __gnu_parallel::_Settings::get(), and GROWING_BLOCKS.

Referenced by _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Chose the desired algorithm by evaluating __parallelism_tag.

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__user_opA user-specified functor (comparator, predicate, associative operator,...)
__functionalityfunctor to process an element with __user_op (depends on desired functionality, e. g. accumulate, for_each,...
__reductionReduction functor.
__reduction_startInitial value for reduction.
__outputOutput iterator.
__boundMaximum number of elements processed.
__parallelism_tagParallelization method

References __for_each_template_random_access_ed(), __for_each_template_random_access_omp_loop(), __for_each_template_random_access_workstealing(), parallel_omp_loop, parallel_omp_loop_static, and parallel_unbalanced.

Referenced by _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Parameters
__beginBegin iterator of element sequence.
__endEnd iterator of element sequence.
__oUser-supplied functor (comparator, predicate, adding functor, ...)
__fFunctor to "process" an element with __op (depends on desired functionality, e. g. for std::for_each(), ...).
__rFunctor to "add" a single __result to the already processed elements (depends on functionality).
__baseBase value for reduction.
__outputPointer to position where final result is written to
__boundMaximum number of elements processed (e. g. for std::count_n()).
Returns
User-supplied functor (that may contain a part of the result).

References __equally_split_point(), and __get_max_threads().

Referenced by __for_each_template_random_access().

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Parameters
__beginBegin iterator of element sequence.
__endEnd iterator of element sequence.
__oUser-supplied functor (comparator, predicate, adding functor, etc.).
__fFunctor to process an element with __op (depends on desired functionality, e. g. for std::for_each(), ...).
__rFunctor to add a single __result to the already processed elements (depends on functionality).
__baseBase value for reduction.
__outputPointer to position where final result is written to
__boundMaximum number of elements processed (e. g. for std::count_n()).
Returns
User-supplied functor (that may contain a part of the result).

References __get_max_threads().

Referenced by __for_each_template_random_access().

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Parameters
__beginBegin iterator of element sequence.
__endEnd iterator of element sequence.
__oUser-supplied functor (comparator, predicate, adding functor, ...).
__fFunctor to process an element with __op (depends on desired functionality, e. g. for std::for_each(), ...).
__rFunctor to add a single __result to the already processed __elements (depends on functionality).
__baseBase value for reduction.
__outputPointer to position where final result is written to
__boundMaximum number of elements processed (e. g. for std::count_n()).
Returns
User-supplied functor (that may contain a part of the result).

References __get_max_threads().

Here is the call graph for this function:

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

Work stealing algorithm for random access iterators.

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

Parameters
__beginBegin iterator of element sequence.
__endEnd iterator of element sequence.
__opUser-supplied functor (comparator, predicate, adding functor, ...).
__fFunctor to process an element with __op (depends on desired functionality, e. g. for std::for_each(), ...).
__rFunctor to add a single __result to the already processed elements (depends on functionality).
__baseBase value for reduction.
__outputPointer to position where final result is written to
__boundMaximum number of elements processed (e. g. for std::count_n()).
Returns
User-supplied functor (that may contain a part of the result).

References __gnu_debug::__base(), __get_max_threads(), __yield(), _GLIBCXX_CALL, __gnu_parallel::_Job< _DifferenceTp >::_M_first, __gnu_parallel::_Job< _DifferenceTp >::_M_last, __gnu_parallel::_Job< _DifferenceTp >::_M_load, __gnu_parallel::_Settings::cache_line_size, __gnu_parallel::_Settings::get(), min(), and __gnu_parallel::_Settings::workstealing_chunk_size.

Referenced by __for_each_template_random_access().

Here is the call graph for this function:

Here is the caller graph for this function:

bool __gnu_parallel::__is_parallel ( const _Parallelism  __p)
inline

References sequential.

Referenced by _GLIBCXX_VISIBILITY().

Here is the caller graph for this function:

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

Check whether [__begin, __end) is sorted according to __comp.

Parameters
__beginBegin iterator of sequence.
__endEnd iterator of sequence.
__compComparator.
Returns
true if sorted, false otherwise.

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

Here is the caller graph for this function:

template<typename _RAIter , typename _Compare >
_RAIter __gnu_parallel::__median_of_three_iterators ( _RAIter  __a,
_RAIter  __b,
_RAIter  __c,
_Compare  __comp 
)

Compute the median of three referenced elements, according to __comp.

Parameters
__aFirst iterator.
__bSecond iterator.
__cThird iterator.
__compComparator.

Referenced by __qsb_divide().

Here is the caller graph for this function:

template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare >
_OutputIterator __gnu_parallel::__merge_advance ( _RAIter1 &  __begin1,
_RAIter1  __end1,
_RAIter2 &  __begin2,
_RAIter2  __end2,
_OutputIterator  __target,
_DifferenceTp  __max_length,
_Compare  __comp 
)
inline

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

The __begin iterators are advanced accordingly, they might not reach __end, in contrast to the usual variant. Static switch on whether to use the conditional-move variant.

Parameters
__begin1Begin iterator of first sequence.
__end1End iterator of first sequence.
__begin2Begin iterator of second sequence.
__end2End iterator of second sequence.
__targetTarget begin iterator.
__max_lengthMaximum number of elements to merge.
__compComparator.
Returns
Output end iterator.

References __merge_advance_movc(), and _GLIBCXX_CALL.

Referenced by __parallel_merge_advance(), __sequential_multiway_merge(), and _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare >
_OutputIterator __gnu_parallel::__merge_advance_movc ( _RAIter1 &  __begin1,
_RAIter1  __end1,
_RAIter2 &  __begin2,
_RAIter2  __end2,
_OutputIterator  __target,
_DifferenceTp  __max_length,
_Compare  __comp 
)

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

The __begin iterators are advanced accordingly, they might not reach __end, in contrast to the usual variant. Specially designed code should allow the compiler to generate conditional moves instead of branches.

Parameters
__begin1Begin iterator of first sequence.
__end1End iterator of first sequence.
__begin2Begin iterator of second sequence.
__end2End iterator of second sequence.
__targetTarget begin iterator.
__max_lengthMaximum number of elements to merge.
__compComparator.
Returns
Output end iterator.

References _GLIBCXX_PARALLEL_ASSERT.

Referenced by __merge_advance().

Here is the caller graph for this function:

template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare >
_OutputIterator __gnu_parallel::__merge_advance_usual ( _RAIter1 &  __begin1,
_RAIter1  __end1,
_RAIter2 &  __begin2,
_RAIter2  __end2,
_OutputIterator  __target,
_DifferenceTp  __max_length,
_Compare  __comp 
)

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

The __begin iterators are advanced accordingly, they might not reach __end, in contrast to the usual variant.

Parameters
__begin1Begin iterator of first sequence.
__end1End iterator of first sequence.
__begin2Begin iterator of second sequence.
__end2End iterator of second sequence.
__targetTarget begin iterator.
__max_lengthMaximum number of elements to merge.
__compComparator.
Returns
Output end iterator.
template<typename _RAIter1 , typename _RAIter2 , typename _RAIter3 , typename _Compare >
_RAIter3 __gnu_parallel::__parallel_merge_advance ( _RAIter1 &  __begin1,
_RAIter1  __end1,
_RAIter2 &  __begin2,
_RAIter2  __end2,
_RAIter3  __target,
typename std::iterator_traits< _RAIter1 >::difference_type  __max_length,
_Compare  __comp 
)
inline

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

Parameters
__begin1Begin iterator of first sequence.
__end1End iterator of first sequence.
__begin2Begin iterator of second sequence.
__end2End iterator of second sequence.
__targetTarget begin iterator.
__max_lengthMaximum number of elements to merge.
__compComparator.
Returns
Output end iterator.

References __merge_advance().

Referenced by _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

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

Parameters
__begin1Begin iterator of first sequence.
__end1End iterator of first sequence.
__begin2Begin iterator of second sequence.
__end2End iterator of second sequence.
__targetTarget begin iterator.
__max_lengthMaximum number of elements to merge.
__compComparator.
Returns
Output end iterator.

References multiway_merge_exact_splitting(), and parallel_multiway_merge().

Here is the call graph for this function:

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

Parallel implementation of std::nth_element().

Parameters
__beginBegin iterator of input sequence.
__nth_Iterator of element that must be in position afterwards.
__endEnd iterator of input sequence.
__compComparator.

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

Referenced by __parallel_partial_sort(), and _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Parallel implementation of std::partial_sort().

Parameters
__beginBegin iterator of input sequence.
__middleSort until this position.
__endEnd iterator of input sequence.
__compComparator.

References __parallel_nth_element().

Referenced by _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Parallel partial sum front-__end.

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__resultBegin iterator of output sequence.
__bin_opAssociative binary function.
Returns
End iterator of output sequence.

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

Here is the call graph for this function:

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

Base case prefix sum routine.

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__resultBegin iterator of output sequence.
__bin_opAssociative binary function.
__valueStart value. Must be passed since the neutral element is unknown in general.
Returns
End iterator of output sequence.

Referenced by __parallel_partial_sum_linear().

Here is the caller graph for this function:

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

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

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__resultBegin iterator of output sequence.
__bin_opAssociative binary function.
__nLength of sequence.
Returns
End iterator of output sequence.

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

Referenced by __parallel_partial_sum().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Parallel implementation of std::partition.

Parameters
__beginBegin iterator of input sequence to split.
__endEnd iterator of input sequence to split.
__predPartition predicate, possibly including some kind of pivot.
__num_threadsMaximum number of threads to use for this task.
Returns
Number of elements not fulfilling the predicate.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Parallel random public call.

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

References __get_max_threads(), and __parallel_random_shuffle_drs().

Referenced by _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename _RAIter , typename _RandomNumberGenerator >
void __gnu_parallel::__parallel_random_shuffle_drs ( _RAIter  __begin,
_RAIter  __end,
typename std::iterator_traits< _RAIter >::difference_type  __n,
_ThreadIndex  __num_threads,
_RandomNumberGenerator &  __rng 
)
template<typename _RAIter , typename _RandomNumberGenerator >
void __gnu_parallel::__parallel_random_shuffle_drs_pu ( _DRSSorterPU< _RAIter, _RandomNumberGenerator > *  __pus)
template<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

References __parallel_set_operation().

Referenced by _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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

References __parallel_set_operation().

Referenced by _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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

References __parallel_set_operation().

Referenced by _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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

References __parallel_set_operation().

Referenced by _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__compComparator.
Template Parameters
__stableSort stable.

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

Here is the call graph for this function:

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

Choose multiway mergesort with exact splitting, for parallel sorting.

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__compComparator.
Template Parameters
__stableSort stable.

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

Here is the call graph for this function:

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

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

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__compComparator.
Template Parameters
__stableSort stable.

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

Here is the call graph for this function:

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

Choose quicksort for parallel sorting.

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__compComparator.
Template Parameters
__stableSort stable.

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

Here is the call graph for this function:

template<bool __stable, typename _RAIter , typename _Compare >
void __gnu_parallel::__parallel_sort ( _RAIter  __begin,
_RAIter  __end,
_Compare  __comp,
balanced_quicksort_tag  __parallelism 
)
inline

Choose balanced quicksort for parallel sorting.

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__compComparator.
Template Parameters
__stableSort stable.

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

Here is the call graph for this function:

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

Choose multiway mergesort with exact splitting, for parallel sorting.

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__compComparator.
Template Parameters
__stableSort stable.

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

Here is the call graph for this function:

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

Choose a parallel sorting algorithm.

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__compComparator.
Template Parameters
__stableSort stable.

References __gnu_parallel::parallel_tag::__get_num_threads(), __parallel_sort_qs(), __parallel_sort_qsb(), _GLIBCXX_CALL, EXACT, __gnu_parallel::_Settings::get(), MWMS, QS, QS_BALANCED, and __gnu_parallel::_Settings::sort_algorithm.

Here is the call graph for this function:

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

Unbalanced quicksort main call.

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator input sequence, ignored.
__compComparator.
__num_threadsNumber of threads that are allowed to work on this part.

References __parallel_sort_qs_conquer(), and _GLIBCXX_CALL.

Referenced by __parallel_sort().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Unbalanced quicksort conquer step.

Parameters
__beginBegin iterator of subsequence.
__endEnd iterator of subsequence.
__compComparator.
__num_threadsNumber of threads that are allowed to work on this part.

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

Referenced by __parallel_sort_qs().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Unbalanced quicksort divide step.

Parameters
__beginBegin iterator of subsequence.
__endEnd iterator of subsequence.
__compComparator.
__pivot_rankDesired __rank of the pivot.
__num_samplesChoose pivot from that many samples.
__num_threadsNumber of threads that are allowed to work on this part.

References __parallel_partition(), and min().

Referenced by __parallel_sort_qs_conquer().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Top-level quicksort routine.

Parameters
__beginBegin iterator of sequence.
__endEnd iterator of sequence.
__compComparator.
__num_threadsNumber of threads that are allowed to work on this part.

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

Referenced by __parallel_sort().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Parallel std::unique_copy(), w/__o explicit equality predicate.

Parameters
__firstBegin iterator of input sequence.
__lastEnd iterator of input sequence.
__resultBegin iterator of result __sequence.
__binary_predEquality predicate.
Returns
End iterator of result __sequence.

References __equally_split(), __get_max_threads(), __gnu_profile::__size(), and _GLIBCXX_CALL.

Referenced by __parallel_unique_copy(), and _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Parallel std::unique_copy(), without explicit equality predicate.

Parameters
__firstBegin iterator of input sequence.
__lastEnd iterator of input sequence.
__resultBegin iterator of result __sequence.
Returns
End iterator of result __sequence.

References __parallel_unique_copy().

Here is the call graph for this function:

template<typename _RAIter , typename _Compare >
void __gnu_parallel::__qsb_conquer ( _QSBThreadLocal< _RAIter > **  __tls,
_RAIter  __begin,
_RAIter  __end,
_Compare  __comp,
_ThreadIndex  __iam,
_ThreadIndex  __num_threads,
bool  __parent_wait 
)

Quicksort conquer step.

Parameters
__tlsArray of thread-local storages.
__beginBegin iterator of subsequence.
__endEnd iterator of subsequence.
__compComparator.
__iamNumber of the thread processing this function.
__num_threadsNumber of threads that are allowed to work on this part.

References __qsb_divide(), __qsb_local_sort_with_helping(), _GLIBCXX_PARALLEL_ASSERT, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_elements_leftover, and __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_initial.

Referenced by __parallel_sort_qsb().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Balanced quicksort divide step.

Parameters
__beginBegin iterator of subsequence.
__endEnd iterator of subsequence.
__compComparator.
__num_threadsNumber of threads that are allowed to work on this part.
Precondition
(__end-__begin)>=1

References __median_of_three_iterators(), __parallel_partition(), and _GLIBCXX_PARALLEL_ASSERT.

Referenced by __qsb_conquer().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename _RAIter , typename _Compare >
void __gnu_parallel::__qsb_local_sort_with_helping ( _QSBThreadLocal< _RAIter > **  __tls,
_Compare &  __comp,
_ThreadIndex  __iam,
bool  __wait 
)
template<typename _RandomNumberGenerator >
int __gnu_parallel::__random_number_pow2 ( int  __logp,
_RandomNumberGenerator &  __rng 
)
inline

Generate a random number in [0,2^__logp).

Parameters
__logpLogarithm (basis 2) of the upper range __bound.
__rngRandom number generator to use.

Referenced by __parallel_random_shuffle_drs_pu(), and __sequential_random_shuffle().

Here is the caller graph for this function:

template<typename _Tp >
_Tp __gnu_parallel::__round_up_to_pow2 ( _Tp  __x)

Round up to the next greater power of 2.

Parameters
__x_Integer to round up

References __rd_log2().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Parallel std::search.

Parameters
__begin1Begin iterator of first sequence.
__end1End iterator of first sequence.
__begin2Begin iterator of second sequence.
__end2End iterator of second sequence.
__predFind predicate.
Returns
Place of finding in first sequences.

References __calc_borders(), __equally_split(), __get_max_threads(), _GLIBCXX_CALL, and min().

Referenced by _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Sequential multi-way merging switch.

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

Parameters
__seqs_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of output sequence.
__compComparator.
__lengthMaximum length to merge, possibly larger than the number of elements available.
__sentinelThe sequences have __a __sentinel element.
Returns
End iterator of output sequence.

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

Referenced by multiway_merge(), multiway_merge_sentinels(), stable_multiway_merge(), and stable_multiway_merge_sentinels().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Sequential cache-efficient random shuffle.

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

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

Referenced by __parallel_random_shuffle_drs(), and _GLIBCXX_VISIBILITY().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Combines two ranges into one and thus halves the number of ranges.

Parameters
__os_startsStart positions worked on (oversampled).
__count_to_twoCounts up to 2.
__range_lengthCurrent length of a chunk.

Referenced by __shrink_and_double().

Here is the caller graph for this function:

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

Shrinks and doubles the ranges.

Parameters
__os_startsStart positions worked on (oversampled).
__count_to_twoCounts up to 2.
__range_lengthCurrent length of a chunk.
__make_twiceWhether the __os_starts is allowed to be grown or not

References __shrink().

Referenced by list_partition().

Here is the call graph for this function:

Here is the caller graph for this function:

void __gnu_parallel::__yield ( )
inline

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

Referenced by __for_each_template_random_access_workstealing(), and __qsb_local_sort_with_helping().

Here is the caller graph for this function:

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

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

The function needs only one pass over the sequence.

Parameters
__beginBegin iterator of input sequence.
__endEnd iterator of input sequence.
__startsStart iterators for the resulting parts, dimension __num_parts+1. For convenience, __starts [__num_parts] contains the end iterator of the sequence.
__lengthsLength of the resulting parts.
__num_partsNumber of parts to split the sequence into.
__fFunctor to be applied to each element by traversing __it
__oversamplingOversampling factor. If 0, then the partitions will differ in at most $\sqrt{\mathrm{end} - \mathrm{begin}}$ elements. Otherwise, the ratio between the longest and the shortest part is bounded by $1/(\mathrm{oversampling} \cdot \mathrm{num\_parts})$
Returns
Length of the whole sequence.

References __shrink_and_double().

Here is the call graph for this function:

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

Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each sequence.

The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones on the __left side will be chosen from sequences with smaller number.

Parameters
__begin_seqsBegin of the sequence of iterator pairs.
__end_seqsEnd of the sequence of iterator pairs.
__rankThe global rank to partition at.
__begin_offsetsA random-access __sequence __begin where the __result will be stored in. Each element of the sequence is an iterator that points to the first element on the greater part of the respective __sequence.
__compThe ordering functor, defaults to std::less<_Tp>.

References __rd_log2(), __S, _GLIBCXX_CALL, _GLIBCXX_PARALLEL_ASSERT, max(), and min().

Referenced by __parallel_set_operation(), multiway_merge_exact_splitting(), and __gnu_parallel::_SplitConsistently< true, _RAIter, _Compare, _SortingPlacesIterator >::operator()().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename _Tp , typename _RanSeqs , typename _RankType , typename _Compare >
_Tp __gnu_parallel::multiseq_selection ( _RanSeqs  __begin_seqs,
_RanSeqs  __end_seqs,
_RankType  __rank,
_RankType &  __offset,
_Compare  __comp = std::less<_Tp>() 
)

Selects the element at a certain global __rank from several sorted sequences.

The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty.

Parameters
__begin_seqsBegin of the sequence of iterator pairs.
__end_seqsEnd of the sequence of iterator pairs.
__rankThe global rank to partition at.
__offsetThe rank of the selected element in the global subsequence of elements equal to the selected element. If the selected element is unique, this number is 0.
__compThe ordering functor, defaults to std::less.

References __rd_log2(), __round_up_to_pow2(), __S, _GLIBCXX_CALL, max(), and min().

Here is the call graph for this function:

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
_RAIterPairIteratoriterator over sequence of pairs of iterators
_RAIterOutiterator over target sequence
_DifferenceTpdifference type for the sequence
_Comparestrict weak ordering type to compare elements in sequences
Parameters
__seqs_begin__begin of sequence __sequence
__seqs_end_M_end of sequence __sequence
__targettarget sequence to merge to.
__compstrict weak ordering to use for element comparison.
__lengthMaximum length to merge, possibly larger than the number of elements available.
Returns
_M_end iterator of output sequence

References __sequential_multiway_merge(), and _GLIBCXX_CALL.

Referenced by multiway_merge(), and __gnu_parallel::__possibly_stable_multiway_merge< false, Seq_RAIter, _RAIter, _Compare, _DiffType >::operator()().

Here is the call graph for this function:

Here is the caller graph for this function:

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

References multiway_merge().

Here is the call graph for this function:

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 
)

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

Here is the call graph for this function:

template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3 __gnu_parallel::multiway_merge_3_variant ( _RAIterIterator  __seqs_begin,
_RAIterIterator  __seqs_end,
_RAIter3  __target,
_DifferenceTp  __length,
_Compare  __comp 
)

Highly efficient 3-way merging procedure.

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

This works well for merging up to 4 sequences.

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

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

Parameters
__seqs_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of output sequence.
__compComparator.
__lengthMaximum length to merge, less equal than the total number of elements available.
Returns
End iterator of output sequence.

References _GLIBCXX_CALL, _GLIBCXX_PARALLEL_ASSERT, and _GLIBCXX_PARALLEL_MERGE_3_CASE.

template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3 __gnu_parallel::multiway_merge_4_variant ( _RAIterIterator  __seqs_begin,
_RAIterIterator  __seqs_end,
_RAIter3  __target,
_DifferenceTp  __length,
_Compare  __comp 
)

Highly efficient 4-way merging procedure.

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

This works well for merging up to 4 sequences.

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

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

Parameters
__seqs_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of output sequence.
__compComparator.
__lengthMaximum length to merge, less equal than the total number of elements available.
Returns
End iterator of output sequence.

References _GLIBCXX_CALL, _GLIBCXX_PARALLEL_DECISION, and _GLIBCXX_PARALLEL_MERGE_4_CASE.

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

Exact splitting for parallel multiway-merge routine.

None of the passed sequences may be empty.

References __equally_split(), _GLIBCXX_PARALLEL_LENGTH, and multiseq_partition().

Referenced by __parallel_merge_advance(), multiway_merge(), multiway_merge_sentinels(), stable_multiway_merge(), and stable_multiway_merge_sentinels().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare >
_RAIter3 __gnu_parallel::multiway_merge_loser_tree ( _RAIterIterator  __seqs_begin,
_RAIterIterator  __seqs_end,
_RAIter3  __target,
_DifferenceTp  __length,
_Compare  __comp 
)

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

This merging variant uses a LoserTree class as selected by _LT.

Stability is selected through the used LoserTree class _LT.

At least one non-empty sequence is required.

Parameters
__seqs_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of output sequence.
__compComparator.
__lengthMaximum length to merge, less equal than the total number of elements available.
Returns
End iterator of output sequence.

References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_LENGTH.

Referenced by __gnu_parallel::__multiway_merge_k_variant_sentinel_switch< false, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >::operator()().

Here is the caller graph for this function:

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_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of output sequence.
__compComparator.
__lengthMaximum length to merge, less equal than the total number of elements available.
Returns
End iterator of output sequence.

References __is_sorted(), _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_ASSERT.

Referenced by __gnu_parallel::__multiway_merge_k_variant_sentinel_switch< __sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare >::operator()().

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Merging is done using the LoserTree class _LT.

Stability is selected by the used LoserTrees.

Precondition
No input will run out of elements during the merge.
Parameters
__seqs_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of output sequence.
__compComparator.
__lengthMaximum length to merge, less equal than the total number of elements available.
Returns
End iterator of output sequence.

References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_ASSERT.

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

Sampling based splitting for parallel multiway-merge routine.

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

Referenced by multiway_merge_sentinels(), stable_multiway_merge(), and stable_multiway_merge_sentinels().

Here is the call graph for this function:

Here is the caller graph for this function:

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
_RAIterPairIteratoriterator over sequence of pairs of iterators
_RAIterOutiterator over target sequence
_DifferenceTpdifference type for the sequence
_Comparestrict weak ordering type to compare elements in sequences
Parameters
__seqs_begin__begin of sequence __sequence
__seqs_end_M_end of sequence __sequence
__targettarget sequence to merge to.
__compstrict weak ordering to use for element comparison.
__lengthMaximum length to merge, possibly larger than the number of elements available.
Returns
_M_end iterator of output sequence

References __sequential_multiway_merge(), and _GLIBCXX_CALL.

Referenced by multiway_merge_sentinels().

Here is the call graph for this function:

Here is the caller graph for this function:

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

References multiway_merge_sentinels().

Here is the call graph for this function:

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 
)

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

Here is the call graph for this function:

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
_Splitterfunctor to split input (either __exact or sampling based)
__stableStable merging incurs a performance penalty.
__sentinelIgnored.
Parameters
__seqs_beginBegin iterator of iterator pair input sequence.
__seqs_endEnd iterator of iterator pair input sequence.
__targetBegin iterator of output sequence.
__compComparator.
__lengthMaximum length to merge, possibly larger than the number of elements available.
Returns
End iterator of output sequence.

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

Referenced by __parallel_merge_advance(), multiway_merge(), multiway_merge_sentinels(), stable_multiway_merge(), and stable_multiway_merge_sentinels().

Here is the call graph for this function:

Here is the caller graph for this function:

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

References __sequential_multiway_merge(), and _GLIBCXX_CALL.

Referenced by __gnu_parallel::__possibly_stable_multiway_merge< true, Seq_RAIter, _RAIter, _Compare, _DiffType >::operator()(), and stable_multiway_merge().

Here is the call graph for this function:

Here is the caller graph for this function:

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

References stable_multiway_merge().

Here is the call graph for this function:

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 
)

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

Here is the call graph for this function:

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   
)

References __sequential_multiway_merge(), and _GLIBCXX_CALL.

Referenced by stable_multiway_merge_sentinels().

Here is the call graph for this function:

Here is the caller graph for this function:

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

References stable_multiway_merge_sentinels().

Here is the call graph for this function:

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 
)

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

Here is the call graph for this function:

Variable Documentation

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

Number of bits of _CASable.

Referenced by __decode2(), and __encode2().

const _CASable __gnu_parallel::_CASable_mask
static
Initial value:
=
((_CASable(1) << (_CASable_bits / 2)) - 1)
static const int _CASable_bits
Number of bits of _CASable.
Definition: types.h:130
int64_t _CASable
Longest compare-and-swappable integer type on this platform.
Definition: types.h:127

_CASable with the right half of bits set to 1.

Referenced by __decode2().