Classes¶

struct _Settings
class _Settings Run-time settings for the parallel mode, including all tunable parameters. struct accumulate_binop_reduct
General reduction, using a binary operator. struct accumulate_selector
std::accumulate() selector. struct adjacent_difference_selector
Selector that returns the difference between two adjacent elements. struct adjacent_find_selector
Test predicate on two adjacent elements. struct balanced_quicksort_tag
Forces parallel sorting using balanced quicksort at compile time. struct balanced_tag
Recommends parallel execution using dynamic load-balancing at compile time. class binder1st
Similar to std::binder1st, but giving the argument types explicitly. class binder2nd
Similar to std::binder2nd, but giving the argument types explicitly. struct constant_size_blocks_tag
Selects the constant block size variant for std::find(). struct count_if_selector
std::count_if () selector. struct count_selector
std::count() selector. struct default_parallel_tag
Recommends parallel execution using the default parallel algorithm. struct DRandomShufflingGlobalData
Data known to every thread participating in __gnu_parallel::parallel_random_shuffle(). struct DRSSorterPU
Local data for a thread participating in __gnu_parallel::parallel_random_shuffle(). struct dummy_reduct
Reduction function doing nothing. class equal_from_less
Constructs predicate for equality from strict weak ordering predicate. struct equal_split_tag
Selects the equal splitting variant for std::find(). struct equal_to
Similar to std::equal_to, but allows two different types. struct exact_tag
Forces parallel merging with exact splitting, at compile time. struct fill_selector
std::fill() selector. struct find_first_of_selector
Test predicate on several elements. struct find_if_selector
Test predicate on a single element, used for std::find() and std::find_if (). struct find_tag
Base class for for std::find() variants. struct for_each_selector
std::for_each() selector. struct generate_selector
std::generate() selector. struct generic_find_selector
Base class of all __gnu_parallel::find_template selectors. struct generic_for_each_selector
Generic selector for embarrassingly parallel functions. struct growing_blocks_tag
Selects the growing block size variant for std::find(). class guarded_iterator
Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. struct identity_selector
Selector that just returns the passed iterator. struct inner_product_selector
std::inner_product() selector. class iterator_pair
A pair of iterators. The usual iterator operations are applied to both child iterators. class iterator_triple
A triple of iterators. The usual iterator operations are applied to all three child iterators. struct Job
One job for a certain thread. struct less
Similar to std::less, but allows two different types. class lexicographic
Compare a pair of types lexicographically, ascending. class lexicographic_reverse
Compare a pair of types lexicographically, descending. struct loser_tree_traits
Traits for determining whether the loser tree should use pointers or copies. class LoserTree
Stable LoserTree variant. class LoserTree< false, T, Comparator >
Unstable LoserTree variant. class LoserTreeBase
Guarded loser/tournament tree. class LoserTreePointer
Stable LoserTree implementation. class LoserTreePointer< false, T, Comparator >
Unstable LoserTree implementation. class LoserTreePointerBase
Base class of Loser Tree implementation using pointers. class LoserTreePointerUnguarded
Stable unguarded LoserTree variant storing pointers. class LoserTreePointerUnguarded< false, T, Comparator >
Unstable unguarded LoserTree variant storing pointers. class LoserTreePointerUnguardedBase
Unguarded loser tree, keeping only pointers to the elements in the tree structure. class LoserTreeUnguarded
Stable implementation of unguarded LoserTree. class LoserTreeUnguarded< false, T, Comparator >
Non-Stable implementation of unguarded LoserTree. class LoserTreeUnguardedBase
Base class for unguarded LoserTree implementation. struct max_element_reduct
Reduction for finding the maximum element, using a comparator. struct min_element_reduct
Reduction for finding the maximum element, using a comparator. struct mismatch_selector
Test inverted predicate on a single element. struct multiplies
Similar to std::multiplies, but allows two different types. struct multiway_merge_3_variant_sentinel_switch
Switch for 3-way merging with sentinels turned off. struct multiway_merge_3_variant_sentinel_switch< true, RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp, Comparator >
Switch for 3-way merging with sentinels turned on. struct multiway_merge_4_variant_sentinel_switch
Switch for 4-way merging with sentinels turned off. struct multiway_merge_4_variant_sentinel_switch< true, RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp, Comparator >
Switch for 4-way merging with sentinels turned on. struct multiway_merge_k_variant_sentinel_switch
Switch for k-way merging with sentinels turned on. struct multiway_merge_k_variant_sentinel_switch< false, stable, RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp, Comparator >
Switch for k-way merging with sentinels turned off. struct multiway_mergesort_exact_tag
Forces parallel sorting using multiway mergesort with exact splitting at compile time. struct multiway_mergesort_sampling_tag
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time. struct multiway_mergesort_tag
Forces parallel sorting using multiway mergesort at compile time. struct nothing
Functor doing nothing. struct omp_loop_static_tag
Recommends parallel execution using OpenMP static load-balancing at compile time. struct omp_loop_tag
Recommends parallel execution using OpenMP dynamic load-balancing at compile time. struct parallel_tag
Recommends parallel execution at compile time, optionally using a user-specified number of threads. struct Piece
Subsequence description. struct plus
Similar to std::plus, but allows two different types. struct PMWMSSortingData
Data accessed by all threads. class pseudo_sequence
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored explicitly, of course. class pseudo_sequence_iterator
Iterator associated with __gnu_parallel::pseudo_sequence. If features the usual random-access iterator functionality. struct QSBThreadLocal
Information local to one thread in the parallel quicksort run. struct quicksort_tag
Forces parallel sorting using unbalanced quicksort at compile time. class random_number
Random number generator, based on the Mersenne twister. struct replace_if_selector
std::replace() selector. struct replace_selector
std::replace() selector. class RestrictedBoundedConcurrentQueue
Double-ended queue of bounded size, allowing lock-free atomic access. push_front() and pop_front() must not be called concurrently to each other, while pop_back() can be called concurrently at all times. empty(), size(), and top() are intentionally not provided. Calling them would not make sense in a concurrent setting. struct sampling_sorter
Stable sorting functor. struct sampling_sorter< false, RandomAccessIterator, StrictWeakOrdering >
Non-stable sorting functor. struct sampling_tag
Forces parallel merging with exact splitting, at compile time. struct sequential_tag
Forces sequential execution at compile time. struct split_consistently
Split consistently. struct split_consistently< false, RandomAccessIterator, Comparator, SortingPlacesIterator >
Split by sampling. struct split_consistently< true, RandomAccessIterator, Comparator, SortingPlacesIterator >
Split by exact splitting. struct transform1_selector
std::transform() selector, one input sequence variant. struct transform2_selector
std::transform() selector, two input sequences variant. class unary_negate
Similar to std::binder1st, but giving the argument types explicitly. struct unbalanced_tag
Recommends parallel execution using static load-balancing at compile time. class void_functor
Functor that does nothing.

Typedefs¶

typedef unsigned short bin_index
typedef short int16
typedef int int32
typedef long long int64
typedef int64 lcas_t
typedef uint64 sequence_index_t
typedef uint16 thread_index_t
typedef unsigned short uint16
typedef unsigned int uint32
typedef unsigned long long uint64

Enumerations¶

enum _AlgorithmStrategy { heuristic, force_sequential, force_parallel }
enum _FindAlgorithm { GROWING_BLOCKS, CONSTANT_SIZE_BLOCKS, EQUAL_SPLIT }
enum _MultiwayMergeAlgorithm { LOSER_TREE }
enum _Parallelism { sequential, parallel_unbalanced, parallel_balanced, parallel_omp_loop, parallel_omp_loop_static, parallel_taskqueue }
enum _PartialSumAlgorithm { RECURSIVE, LINEAR }
enum _SortAlgorithm { MWMS, QS, QS_BALANCED }
enum _SplittingAlgorithm { SAMPLING, EXACT }

Functions¶

template<typename Size > Size __log2 (Size n)
template<typename RandomAccessIterator , typename _DifferenceTp > void calc_borders (RandomAccessIterator elements, _DifferenceTp length, _DifferenceTp *off)
template<typename T > bool compare_and_swap (volatile T *ptr, T comparand, T replacement)
bool compare_and_swap_32 (volatile int32 *ptr, int32 comparand, int32 replacement)
bool compare_and_swap_64 (volatile int64 *ptr, int64 comparand, int64 replacement)
template<typename InputIterator , typename OutputIterator > OutputIterator copy_tail (std::pair< InputIterator, InputIterator > b, std::pair< InputIterator, InputIterator > e, OutputIterator r)
void decode2 (lcas_t x, int &a, int &b)
template<typename RandomAccessIterator , typename _DifferenceTp > void determine_samples (PMWMSSortingData< RandomAccessIterator > *sd, _DifferenceTp num_samples)
lcas_t encode2 (int a, int b)
template<typename difference_type , typename OutputIterator > OutputIterator equally_split (difference_type n, thread_index_t num_threads, OutputIterator s)
template<typename difference_type > difference_type equally_split_point (difference_type n, thread_index_t num_threads, thread_index_t thread_no)
template<typename T > T fetch_and_add (volatile T *ptr, T addend)
int32 fetch_and_add_32 (volatile int32 *ptr, int32 addend)
int64 fetch_and_add_64 (volatile int64 *ptr, int64 addend)
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename Pred , typename Selector > std::pair< RandomAccessIterator1, RandomAccessIterator2 > find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector, constant_size_blocks_tag)
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename Pred , typename Selector > std::pair< RandomAccessIterator1, RandomAccessIterator2 > find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector, growing_blocks_tag)
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename Pred , typename Selector > std::pair< RandomAccessIterator1, RandomAccessIterator2 > find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector, equal_split_tag)
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename Pred , typename Selector > std::pair< RandomAccessIterator1, RandomAccessIterator2 > find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector)
template<typename InputIterator , typename UserOp , typename Functionality , typename Red , typename Result > UserOp for_each_template_random_access (InputIterator begin, InputIterator end, UserOp user_op, Functionality &functionality, Red reduction, Result reduction_start, Result &output, typename std::iterator_traits< InputIterator >::difference_type bound, _Parallelism parallelism_tag)
template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op for_each_template_random_access_ed (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu &f, Red r, Result base, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound)
template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op for_each_template_random_access_omp_loop (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu &f, Red r, Result base, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound)
template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op for_each_template_random_access_omp_loop_static (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu &f, Red r, Result base, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound)
template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op for_each_template_random_access_workstealing (RandomAccessIterator begin, RandomAccessIterator end, Op op, Fu &f, Red r, Result base, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound)
int get_max_threads ()
bool is_parallel (const _Parallelism __p)
template<typename InputIterator , typename Comparator > bool is_sorted (InputIterator begin, InputIterator end, Comparator comp=std::less< typename std::iterator_traits< InputIterator >::value_type >())
template<typename InputIterator , typename Comparator > bool is_sorted_failure (InputIterator begin, InputIterator end, InputIterator &first_failure, Comparator comp=std::less< typename std::iterator_traits< InputIterator >::value_type >())
template<typename InputIterator , typename Comparator > bool is_sorted_print_failures (InputIterator begin, InputIterator end, Comparator comp=std::less< typename std::iterator_traits< InputIterator >::value_type >())
template<typename InputIterator , typename FunctorType > size_t list_partition (const InputIterator begin, const InputIterator end, InputIterator *starts, size_t *lengths, const int num_parts, FunctorType &f, int oversampling=0)
template<typename T > const T & max (const T &a, const T &b)
template<typename RandomAccessIterator , typename Comparator > RandomAccessIterator median_of_three_iterators (RandomAccessIterator a, RandomAccessIterator b, RandomAccessIterator c, Comparator &comp)
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator > OutputIterator merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator > OutputIterator merge_advance_movc (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator > OutputIterator merge_advance_usual (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
template<typename T > const T & min (const T &a, const T &b)
template<typename RanSeqs , typename RankType , typename RankIterator , typename Comparator > void multiseq_partition (RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, RankIterator begin_offsets, Comparator comp=std::less< typename std::iterator_traits< typename std::iterator_traits< RanSeqs >::value_type::first_type >::value_type >())
template<typename T , typename RanSeqs , typename RankType , typename Comparator > T multiseq_selection (RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, RankType &offset, Comparator comp=std::less< T >())
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, default_parallel_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, parallel_tag tag=parallel_tag(0))
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::sampling_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::exact_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::sequential_tag)
template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 multiway_merge_3_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, _DifferenceTp length, Comparator comp)
template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 multiway_merge_4_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, _DifferenceTp length, Comparator comp)
template<bool stable, typename RandomAccessIteratorIterator , typename Comparator , typename difference_type > void multiway_merge_exact_splitting (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, difference_type length, difference_type total_length, Comparator comp, std::vector< std::pair< difference_type, difference_type > > *pieces)
template<typename LT , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 multiway_merge_loser_tree (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, _DifferenceTp length, Comparator comp)
template<typename UnguardedLoserTree , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 multiway_merge_loser_tree_sentinel (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, _DifferenceTp length, Comparator comp)
template<typename LT , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 multiway_merge_loser_tree_unguarded (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, _DifferenceTp length, Comparator comp)
template<bool stable, typename RandomAccessIteratorIterator , typename Comparator , typename difference_type > void multiway_merge_sampling_splitting (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, difference_type length, difference_type total_length, Comparator comp, std::vector< std::pair< difference_type, difference_type > > *pieces)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, default_parallel_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, parallel_tag tag=parallel_tag(0))
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, sampling_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::exact_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::sequential_tag)
template<typename RandomAccessIterator , typename Comparator > bool operator< (unguarded_iterator< RandomAccessIterator, Comparator > &bi1, unguarded_iterator< RandomAccessIterator, Comparator > &bi2)
template<typename RandomAccessIterator , typename Comparator > bool operator< (guarded_iterator< RandomAccessIterator, Comparator > &bi1, guarded_iterator< RandomAccessIterator, Comparator > &bi2)
template<typename RandomAccessIterator , typename Comparator > bool operator<= (unguarded_iterator< RandomAccessIterator, Comparator > &bi1, unguarded_iterator< RandomAccessIterator, Comparator > &bi2)
template<typename RandomAccessIterator , typename Comparator > bool operator<= (guarded_iterator< RandomAccessIterator, Comparator > &bi1, guarded_iterator< RandomAccessIterator, Comparator > &bi2)
template<typename RandomAccessIterator1 , typename RandomAccessIterator3 , typename Comparator > RandomAccessIterator3 parallel_merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator1 &begin2, RandomAccessIterator1 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp)
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename RandomAccessIterator3 , typename Comparator > RandomAccessIterator3 parallel_merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp)
template<bool stable, bool sentinels, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Splitter , typename Comparator > RandomAccessIterator3 parallel_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Splitter splitter, _DifferenceTp length, Comparator comp, thread_index_t num_threads)
template<typename RandomAccessIterator , typename Comparator > void parallel_nth_element (RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, Comparator comp)
template<typename RandomAccessIterator , typename Comparator > void parallel_partial_sort (RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, Comparator comp)
template<typename InputIterator , typename OutputIterator , typename BinaryOperation > OutputIterator parallel_partial_sum (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op)
template<typename InputIterator , typename OutputIterator , typename BinaryOperation > OutputIterator parallel_partial_sum_basecase (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename std::iterator_traits< InputIterator >::value_type value)
template<typename InputIterator , typename OutputIterator , typename BinaryOperation > OutputIterator parallel_partial_sum_linear (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename std::iterator_traits< InputIterator >::difference_type n)
template<typename RandomAccessIterator , typename Predicate > std::iterator_traits< RandomAccessIterator >::difference_type parallel_partition (RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, thread_index_t num_threads)
template<typename RandomAccessIterator , typename RandomNumberGenerator > void parallel_random_shuffle (RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator rng=random_number())
template<typename RandomAccessIterator , typename RandomNumberGenerator > void parallel_random_shuffle_drs (RandomAccessIterator begin, RandomAccessIterator end, typename std::iterator_traits< RandomAccessIterator >::difference_type n, thread_index_t num_threads, RandomNumberGenerator &rng)
template<typename RandomAccessIterator , typename RandomNumberGenerator > void parallel_random_shuffle_drs_pu (DRSSorterPU< RandomAccessIterator, RandomNumberGenerator > *pus)
template<typename InputIterator , typename OutputIterator , typename Comparator > OutputIterator parallel_set_difference (InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result, Comparator comp)
template<typename InputIterator , typename OutputIterator , typename Comparator > OutputIterator parallel_set_intersection (InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result, Comparator comp)
template<typename InputIterator , typename OutputIterator , typename Operation > OutputIterator parallel_set_operation (InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result, Operation op)
template<typename InputIterator , typename OutputIterator , typename Comparator > OutputIterator parallel_set_symmetric_difference (InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result, Comparator comp)
template<typename InputIterator , typename OutputIterator , typename Comparator > OutputIterator parallel_set_union (InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result, Comparator comp)
template<bool stable, typename RandomAccessIterator , typename Comparator > void parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, parallel_tag parallelism)
template<bool stable, typename RandomAccessIterator , typename Comparator > void parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, default_parallel_tag parallelism)
template<bool stable, typename RandomAccessIterator , typename Comparator > void parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, balanced_quicksort_tag parallelism)
template<bool stable, typename RandomAccessIterator , typename Comparator > void parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, quicksort_tag parallelism)
template<bool stable, typename RandomAccessIterator , typename Comparator > void parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, multiway_mergesort_sampling_tag parallelism)
template<bool stable, typename RandomAccessIterator , typename Comparator > void parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, multiway_mergesort_exact_tag parallelism)
template<bool stable, typename RandomAccessIterator , typename Comparator > void parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, multiway_mergesort_tag parallelism)
template<bool stable, typename RandomAccessIterator , typename Comparator , typename Parallelism > void parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, Parallelism parallelism)
template<bool stable, bool exact, typename RandomAccessIterator , typename Comparator > void parallel_sort_mwms (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads)
template<bool stable, bool exact, typename RandomAccessIterator , typename Comparator > void parallel_sort_mwms_pu (PMWMSSortingData< RandomAccessIterator > *sd, Comparator &comp)
template<typename RandomAccessIterator , typename Comparator > void parallel_sort_qs (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads)
template<typename RandomAccessIterator , typename Comparator > void parallel_sort_qs_conquer (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads)
template<typename RandomAccessIterator , typename Comparator > std::iterator_traits< RandomAccessIterator >::difference_type parallel_sort_qs_divide (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, typename std::iterator_traits< RandomAccessIterator >::difference_type pivot_rank, typename std::iterator_traits< RandomAccessIterator >::difference_type num_samples, thread_index_t num_threads)
template<typename RandomAccessIterator , typename Comparator > void parallel_sort_qsb (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads)
template<typename InputIterator , class OutputIterator > OutputIterator parallel_unique_copy (InputIterator first, InputIterator last, OutputIterator result)
template<typename InputIterator , class OutputIterator , class BinaryPredicate > OutputIterator parallel_unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred)
template<typename RandomAccessIterator , typename Comparator > void qsb_conquer (QSBThreadLocal< RandomAccessIterator > **tls, RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t iam, thread_index_t num_threads, bool parent_wait)
template<typename RandomAccessIterator , typename Comparator > std::iterator_traits< RandomAccessIterator >::difference_type qsb_divide (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads)
template<typename RandomAccessIterator , typename Comparator > void qsb_local_sort_with_helping (QSBThreadLocal< RandomAccessIterator > **tls, Comparator &comp, int iam, bool wait)
template<typename RandomNumberGenerator > int random_number_pow2 (int logp, RandomNumberGenerator &rng)
template<typename T > T round_up_to_pow2 (T x)
template<typename _RandomAccessIterator1 , typename _RandomAccessIterator2 , typename Pred > _RandomAccessIterator1 search_template (_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1, _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2, Pred pred)
template<bool stable, bool sentinels, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 sequential_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, _DifferenceTp length, Comparator comp)
template<typename RandomAccessIterator , typename RandomNumberGenerator > void sequential_random_shuffle (RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator &rng)
template<typename InputIterator > void shrink (std::vector< InputIterator > &os_starts, size_t &count_to_two, size_t &range_length)
template<typename InputIterator > void shrink_and_double (std::vector< InputIterator > &os_starts, size_t &count_to_two, size_t &range_length, const bool make_twice)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut stable_multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, default_parallel_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut stable_multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, parallel_tag tag=parallel_tag(0))
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut stable_multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, sampling_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut stable_multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::exact_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut stable_multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::sequential_tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut stable_multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, default_parallel_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut stable_multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, parallel_tag tag=parallel_tag(0))
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut stable_multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, sampling_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut stable_multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::exact_tag tag)
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut stable_multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::sequential_tag)
void yield ()

Variables¶

static const int lcas_t_bits
static const lcas_t lcas_t_mask

typedef unsigned short __gnu_parallel::bin_index¶

Type to hold the index of a bin. Since many variables of this type are allocated, it should be chosen as small as possible.

Definition at line 47 of file random_shuffle.h.

typedef short __gnu_parallel::int16¶

Integer Types. 16-bit signed integer.

Definition at line 114 of file types.h.

typedef int __gnu_parallel::int32¶

32-bit signed integer.

Definition at line 120 of file types.h.

typedef long long __gnu_parallel::int64¶

64-bit signed integer.

Definition at line 126 of file types.h.

typedef int64 __gnu_parallel::lcas_t¶

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

Definition at line 145 of file types.h.

typedef uint64 __gnu_parallel::sequence_index_t¶

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

Definition at line 135 of file types.h.

typedef uint16 __gnu_parallel::thread_index_t¶

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

Definition at line 141 of file types.h.

typedef unsigned short __gnu_parallel::uint16¶

16-bit unsigned integer.

Definition at line 117 of file types.h.

typedef unsigned int __gnu_parallel::uint32¶

32-bit unsigned integer.

Definition at line 123 of file types.h.

typedef unsigned long long __gnu_parallel::uint64¶

64-bit unsigned integer.

Definition at line 129 of file types.h.

enum __gnu_parallel::_AlgorithmStrategy¶

Strategies for run-time algorithm selection:.

Definition at line 65 of file types.h.

enum __gnu_parallel::_FindAlgorithm¶

Find algorithms:.

Definition at line 104 of file types.h.

enum __gnu_parallel::_MultiwayMergeAlgorithm¶

Merging algorithms:.

Definition at line 83 of file types.h.

enum __gnu_parallel::_Parallelism¶

Run-time equivalents for the compile-time tags.

Enumerator:

sequential

Not parallel.

parallel_unbalanced

Parallel unbalanced (equal-sized chunks).

parallel_balanced

Parallel balanced (work-stealing).

parallel_omp_loop

Parallel with OpenMP dynamic load-balancing.

parallel_omp_loop_static

Parallel with OpenMP static load-balancing.

parallel_taskqueue

Parallel with OpenMP taskqueue construct.

Definition at line 42 of file types.h.

enum __gnu_parallel::_PartialSumAlgorithm¶

Partial sum algorithms: recursive, linear.

Definition at line 89 of file types.h.

enum __gnu_parallel::_SortAlgorithm¶

Sorting algorithms:.

Definition at line 74 of file types.h.

enum __gnu_parallel::_SplittingAlgorithm¶

Sorting/merging algorithms: sampling, exact.

Definition at line 96 of file types.h.

template<typename Size > Size __gnu_parallel::__log2 (Size n) [inline]¶

Calculates the rounded-down logarithm of n for base 2. Parameters:

Returns:

Definition at line 105 of file base.h.

Referenced by __gnu_parallel::LoserTreeBase< T, Comparator >::LoserTreeBase(), multiseq_partition(), multiseq_selection(), parallel_random_shuffle_drs(), round_up_to_pow2(), and sequential_random_shuffle().

template<typename RandomAccessIterator , typename _DifferenceTp > void __gnu_parallel::calc_borders (RandomAccessIterator elements, _DifferenceTp length, _DifferenceTp * off) [inline]¶

Precalculate advances for Knuth-Morris-Pratt algorithm. Parameters:

Definition at line 52 of file search.h.

Referenced by search_template().

template<typename T > bool __gnu_parallel::compare_and_swap (volatile T * ptr, T comparand, T replacement) [inline]¶

Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise. Implementation is heavily platform-dependent.

Parameters:

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

References compare_and_swap_32(), and compare_and_swap_64().

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_back(), and __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_front().

bool __gnu_parallel::compare_and_swap_32 (volatile int32 * ptr, int32 comparand, int32 replacement) [inline]¶

Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise. Implementation is heavily platform-dependent.

Parameters:

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

Referenced by compare_and_swap().

bool __gnu_parallel::compare_and_swap_64 (volatile int64 * ptr, int64 comparand, int64 replacement) [inline]¶

Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise. Implementation is heavily platform-dependent.

Parameters:

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

Referenced by compare_and_swap().

void __gnu_parallel::decode2 (lcas_t x, int & a, int & b) [inline]¶

Decode two integers from one __gnu_parallel::lcas_t. Parameters:

See also:

Definition at line 136 of file base.h.

References lcas_t_bits, and lcas_t_mask.

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_back(), __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_front(), and __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::push_front().

template<typename RandomAccessIterator , typename _DifferenceTp > void __gnu_parallel::determine_samples (PMWMSSortingData< RandomAccessIterator > * sd, _DifferenceTp num_samples) [inline]¶

Select samples from a sequence. Parameters:

Definition at line 98 of file multiway_mergesort.h.

References equally_split(), __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::samples, __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::source, and __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::starts.

lcas_t __gnu_parallel::encode2 (int a, int b) [inline]¶

Encode two integers into one __gnu_parallel::lcas_t. Parameters:

Returns:

See also:

Definition at line 122 of file base.h.

References lcas_t_bits.

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_back(), __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::pop_front(), __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::push_front(), and __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::RestrictedBoundedConcurrentQueue().

template<typename difference_type , typename OutputIterator > OutputIterator __gnu_parallel::equally_split (difference_type n, thread_index_t num_threads, OutputIterator s) [inline]¶

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

Parameters:

Returns:

Definition at line 48 of file equally_split.h.

Referenced by determine_samples(), find_template(), multiway_merge_exact_splitting(), parallel_partial_sum_linear(), parallel_unique_copy(), and search_template().

template<typename difference_type > difference_type __gnu_parallel::equally_split_point (difference_type n, thread_index_t num_threads, thread_index_t thread_no) [inline]¶

Function to split a sequence into parts of almost equal size. Returns the position of the splitting point between thread number thread_no (included) and thread number thread_no+1 (excluded).

Parameters:

Returns:

Definition at line 73 of file equally_split.h.

Referenced by for_each_template_random_access_ed().

template<typename T > T __gnu_parallel::fetch_and_add (volatile T * ptr, T addend) [inline]¶

Add a value to a variable, atomically. Implementation is heavily platform-dependent.

Parameters:

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

References fetch_and_add_32(), and fetch_and_add_64().

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< Piece >::push_front().

int32 __gnu_parallel::fetch_and_add_32 (volatile int32 * ptr, int32 addend) [inline]¶

Add a value to a variable, atomically. Implementation is heavily platform-dependent.

Parameters:

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

Referenced by fetch_and_add().

int64 __gnu_parallel::fetch_and_add_64 (volatile int64 * ptr, int64 addend) [inline]¶

Add a value to a variable, atomically. Implementation is heavily platform-dependent.

Parameters:

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

Referenced by fetch_and_add().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename Pred , typename Selector > std::pair<RandomAccessIterator1, RandomAccessIterator2> __gnu_parallel::find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector, constant_size_blocks_tag) [inline]¶

Parallel std::find, constant block size variant. Parameters:

Returns:

See also:

Definition at line 314 of file find.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::find_initial_block_size, __gnu_parallel::_Settings::find_sequential_search_size, and __gnu_parallel::_Settings::get().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename Pred , typename Selector > std::pair<RandomAccessIterator1, RandomAccessIterator2> __gnu_parallel::find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector, growing_blocks_tag) [inline]¶

Parallel std::find, growing block size variant. Parameters:

Returns:

See also:

There are two main differences between the growing blocks and the constant-size blocks variants. 1. For GB, the block size grows; for CSB, the block size is fixed.

2. For GB, the blocks are allocated dynamically; for CSB, the blocks are allocated in a predetermined manner, namely spacial round-robin.

Definition at line 191 of file find.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::find_increasing_factor, __gnu_parallel::_Settings::find_initial_block_size, __gnu_parallel::_Settings::find_maximum_block_size, __gnu_parallel::_Settings::find_sequential_search_size, and __gnu_parallel::_Settings::get().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename Pred , typename Selector > std::pair<RandomAccessIterator1, RandomAccessIterator2> __gnu_parallel::find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector, equal_split_tag) [inline]¶

Parallel std::find, equal splitting variant. Parameters:

Returns:

Definition at line 97 of file find.h.

References _GLIBCXX_CALL, and equally_split().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename Pred , typename Selector > std::pair<RandomAccessIterator1, RandomAccessIterator2> __gnu_parallel::find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector) [inline]¶

Parallel std::find, switch for different algorithms. Parameters:

Returns:

Definition at line 60 of file find.h.

References __gnu_parallel::_Settings::get().

template<typename InputIterator , typename UserOp , typename Functionality , typename Red , typename Result > UserOp __gnu_parallel::for_each_template_random_access (InputIterator begin, InputIterator end, UserOp user_op, Functionality & functionality, Red reduction, Result reduction_start, Result & output, typename std::iterator_traits< InputIterator >::difference_type bound, _Parallelism parallelism_tag) [inline]¶

Chose the desired algorithm by evaluating parallelism_tag. Parameters:

Definition at line 61 of file for_each.h.

References for_each_template_random_access_ed(), for_each_template_random_access_omp_loop(), for_each_template_random_access_workstealing(), parallel_omp_loop, parallel_omp_loop_static, and parallel_unbalanced.

template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op __gnu_parallel::for_each_template_random_access_ed (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu & f, Red r, Result base, Result & output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound) [inline]¶

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

Returns:

Definition at line 68 of file par_loop.h.

References equally_split_point().

Referenced by for_each_template_random_access().

template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op __gnu_parallel::for_each_template_random_access_omp_loop (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu & f, Red r, Result base, Result & output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound) [inline]¶

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

Returns:

Definition at line 67 of file omp_loop.h.

Referenced by for_each_template_random_access().

template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op __gnu_parallel::for_each_template_random_access_omp_loop_static (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu & f, Red r, Result base, Result & output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound) [inline]¶

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

Returns:

Definition at line 67 of file omp_loop_static.h.

template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op __gnu_parallel::for_each_template_random_access_workstealing (RandomAccessIterator begin, RandomAccessIterator end, Op op, Fu & f, Red r, Result base, Result & output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound) [inline]¶

Work stealing algorithm for random access iterators. Uses O(1) additional memory. Synchronization at job lists is done with atomic operations.

Parameters:

Returns:

Definition at line 99 of file workstealing.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::cache_line_size, __gnu_parallel::Job< _DifferenceTp >::first, __gnu_parallel::_Settings::get(), __gnu_parallel::Job< _DifferenceTp >::last, __gnu_parallel::Job< _DifferenceTp >::load, min(), and yield().

Referenced by for_each_template_random_access().

template<typename InputIterator , typename Comparator > bool __gnu_parallel::is_sorted (InputIterator begin, InputIterator end, Comparator comp = std::less<typename std::iterator_traits<InputIterator>:: value_type>()) [inline]¶

Check whether [begin, end) is sorted according to comp. Parameters:

Returns:

Definition at line 51 of file checkers.h.

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

template<typename InputIterator , typename Comparator > bool __gnu_parallel::is_sorted_failure (InputIterator begin, InputIterator end, InputIterator & first_failure, Comparator comp = std::less<typename std::iterator_traits<InputIterator>:: value_type>()) [inline]¶

Check whether [begin, end) is sorted according to comp. Prints the position in case an unordered pair is found. Parameters:

Returns:

Definition at line 89 of file checkers.h.

template<typename InputIterator , typename Comparator > bool __gnu_parallel::is_sorted_print_failures (InputIterator begin, InputIterator end, Comparator comp = std::less<typename std::iterator_traits <InputIterator>::value_type>()) [inline]¶

Check whether [begin, end) is sorted according to comp. Prints all unordered pair, including the surrounding two elements. Parameters:

Returns:

Definition at line 129 of file checkers.h.

template<typename InputIterator , typename FunctorType > size_t __gnu_parallel::list_partition (const InputIterator begin, const InputIterator end, InputIterator * starts, size_t * lengths, const int num_parts, FunctorType & f, int oversampling = 0) [inline]¶

Splits a sequence given by input iterators into parts of almost equal size. The function needs only one pass over the sequence.

Parameters:

Returns:

Definition at line 100 of file list_partition.h.

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

template<typename T > const T& __gnu_parallel::max (const T & a, const T & b) [inline]¶

Equivalent to std::max.

Definition at line 151 of file base.h.

Referenced by multiseq_partition(), multiseq_selection(), and parallel_nth_element().

template<typename RandomAccessIterator , typename Comparator > RandomAccessIterator __gnu_parallel::median_of_three_iterators (RandomAccessIterator a, RandomAccessIterator b, RandomAccessIterator c, Comparator & comp) [inline]¶

Compute the median of three referenced elements, according to comp. Parameters:

Definition at line 443 of file base.h.

Referenced by qsb_divide().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator > OutputIterator __gnu_parallel::merge_advance (RandomAccessIterator1 & begin1, RandomAccessIterator1 end1, RandomAccessIterator2 & begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator 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:

Returns:

Definition at line 174 of file merge.h.

References _GLIBCXX_CALL, and merge_advance_movc().

Referenced by parallel_merge_advance(), and sequential_multiway_merge().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator > OutputIterator __gnu_parallel::merge_advance_movc (RandomAccessIterator1 & begin1, RandomAccessIterator1 end1, RandomAccessIterator2 & begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator 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. Specially designed code should allow the compiler to generate conditional moves instead of branches.

Parameters:

Returns:

Definition at line 106 of file merge.h.

Referenced by merge_advance().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator > OutputIterator __gnu_parallel::merge_advance_usual (RandomAccessIterator1 & begin1, RandomAccessIterator1 end1, RandomAccessIterator2 & begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator 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.

Parameters:

Returns:

Definition at line 57 of file merge.h.

template<typename T > const T& __gnu_parallel::min (const T & a, const T & b) [inline]¶

Equivalent to std::min.

Definition at line 145 of file base.h.

Referenced by for_each_template_random_access_workstealing(), multiseq_partition(), multiseq_selection(), parallel_sort_qs_divide(), and search_template().

template<typename RanSeqs , typename RankType , typename RankIterator , typename Comparator > void __gnu_parallel::multiseq_partition (RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, RankIterator begin_offsets, Comparator comp = std::less< typename std::iterator_traits<typename std::iterator_traits<RanSeqs>::value_type:: first_type>::value_type>()) [inline]¶

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

Definition at line 123 of file multiseq_selection.h.

References __log2(), _GLIBCXX_CALL, std::vector< _Tp, _Alloc >::begin(), std::distance(), __gnu_cxx::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::vector< _Tp, _Alloc >::end(), max(), min(), std::priority_queue< _Tp, _Sequence, _Compare >::pop(), std::priority_queue< _Tp, _Sequence, _Compare >::push(), std::vector< _Tp, _Alloc >::push_back(), and std::priority_queue< _Tp, _Sequence, _Compare >::top().

Referenced by multiway_merge_exact_splitting().

template<typename T , typename RanSeqs , typename RankType , typename Comparator > T __gnu_parallel::multiseq_selection (RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, RankType & offset, Comparator comp = std::less<T>()) [inline]¶

Selects the element at a certain global rank from several sorted sequences. The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty.

Parameters:

Definition at line 377 of file multiseq_selection.h.

References __log2(), _GLIBCXX_CALL, std::vector< _Tp, _Alloc >::begin(), std::distance(), __gnu_cxx::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::vector< _Tp, _Alloc >::end(), max(), min(), std::priority_queue< _Tp, _Sequence, _Compare >::pop(), std::priority_queue< _Tp, _Sequence, _Compare >::push(), std::vector< _Tp, _Alloc >::push_back(), and std::priority_queue< _Tp, _Sequence, _Compare >::top().

template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut __gnu_parallel::multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::sequential_tag) [inline]¶

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

Precondition:

Postcondition:

Parameters:

Returns:

Definition at line 1477 of file multiway_merge.h.

References _GLIBCXX_CALL, and sequential_multiway_merge().

template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::multiway_merge_3_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, _DifferenceTp length, Comparator comp) [inline]¶

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 out an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into labels in C++).

This works well for merging up to 4 sequences.

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

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

Parameters:

Returns:

Definition at line 290 of file multiway_merge.h.

References _GLIBCXX_CALL.

template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::multiway_merge_4_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, _DifferenceTp length, Comparator comp) [inline]¶

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 out an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into goto labels in C++).

This works well for merging up to 4 sequences.

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

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

Parameters:

Returns:

Definition at line 410 of file multiway_merge.h.

References _GLIBCXX_CALL.

template<bool stable, typename RandomAccessIteratorIterator , typename Comparator , typename difference_type > void __gnu_parallel::multiway_merge_exact_splitting (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, difference_type length, difference_type total_length, Comparator comp, std::vector< std::pair< difference_type, difference_type > > * pieces) [inline]¶

Exact splitting for parallel multiway-merge routine. None of the passed sequences may be empty.

Definition at line 1181 of file multiway_merge.h.

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

Referenced by parallel_merge_advance().

template<typename LT , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, _DifferenceTp length, Comparator comp) [inline]¶

Multi-way merging procedure for a high branching factor, guarded case. This merging variant uses a LoserTree class as selected by LT.

Stability is selected through the used LoserTree class LT.

At least one non-empty sequence is required.

Parameters:

Returns:

Definition at line 534 of file multiway_merge.h.

References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_LENGTH.

template<typename UnguardedLoserTree , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree_sentinel (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type & sentinel, _DifferenceTp length, Comparator comp) [inline]¶

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

Returns:

Definition at line 705 of file multiway_merge.h.

References _GLIBCXX_CALL, is_sorted(), and multiway_merge_loser_tree_unguarded().

template<typename LT , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree_unguarded (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type & sentinel, _DifferenceTp length, Comparator comp) [inline]¶

Multi-way merging procedure for a high branching factor, unguarded case. Merging is done using the LoserTree class LT.

Stability is selected by the used LoserTrees.

Precondition:

Parameters:

Returns:

Definition at line 615 of file multiway_merge.h.

References _GLIBCXX_CALL.

Referenced by multiway_merge_loser_tree_sentinel().

template<bool stable, typename RandomAccessIteratorIterator , typename Comparator , typename difference_type > void __gnu_parallel::multiway_merge_sampling_splitting (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, difference_type length, difference_type total_length, Comparator comp, std::vector< std::pair< difference_type, difference_type > > * pieces) [inline]¶

Sampling based splitting for parallel multiway-merge routine.

Definition at line 1100 of file multiway_merge.h.

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

template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut __gnu_parallel::multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, _DifferenceTp length, Comparator comp, __gnu_parallel::sequential_tag) [inline]¶

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

Postcondition:

See also:

Parameters:

Returns:

Definition at line 1849 of file multiway_merge.h.

References _GLIBCXX_CALL, and sequential_multiway_merge().

template<typename RandomAccessIterator , typename Comparator > bool __gnu_parallel::operator< (unguarded_iterator< RandomAccessIterator, Comparator > & bi1, unguarded_iterator< RandomAccessIterator, Comparator > & bi2) [inline]¶

Compare two elements referenced by unguarded iterators. Parameters:

Returns:

Definition at line 239 of file multiway_merge.h.

template<typename RandomAccessIterator , typename Comparator > bool __gnu_parallel::operator< (guarded_iterator< RandomAccessIterator, Comparator > & bi1, guarded_iterator< RandomAccessIterator, Comparator > & bi2) [inline]¶

Compare two elements referenced by guarded iterators. Parameters:

Returns:

Definition at line 144 of file multiway_merge.h.

template<typename RandomAccessIterator , typename Comparator > bool __gnu_parallel::operator<= (unguarded_iterator< RandomAccessIterator, Comparator > & bi1, unguarded_iterator< RandomAccessIterator, Comparator > & bi2) [inline]¶

Compare two elements referenced by unguarded iterators. Parameters:

Returns:

Definition at line 252 of file multiway_merge.h.

template<typename RandomAccessIterator , typename Comparator > bool __gnu_parallel::operator<= (guarded_iterator< RandomAccessIterator, Comparator > & bi1, guarded_iterator< RandomAccessIterator, Comparator > & bi2) [inline]¶

Compare two elements referenced by guarded iterators. Parameters:

Returns:

Definition at line 160 of file multiway_merge.h.

template<typename RandomAccessIterator1 , typename RandomAccessIterator3 , typename Comparator > RandomAccessIterator3 __gnu_parallel::parallel_merge_advance (RandomAccessIterator1 & begin1, RandomAccessIterator1 end1, RandomAccessIterator1 & begin2, RandomAccessIterator1 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator 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:

Returns:

Definition at line 228 of file merge.h.

References multiway_merge_exact_splitting(), and parallel_multiway_merge().

template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename RandomAccessIterator3 , typename Comparator > RandomAccessIterator3 __gnu_parallel::parallel_merge_advance (RandomAccessIterator1 & begin1, RandomAccessIterator1 end1, RandomAccessIterator2 & begin2, RandomAccessIterator2 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp) [inline]¶

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

Returns:

Definition at line 198 of file merge.h.

References merge_advance().

template<bool stable, bool sentinels, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Splitter , typename Comparator > RandomAccessIterator3 __gnu_parallel::parallel_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Splitter splitter, _DifferenceTp length, Comparator comp, thread_index_t num_threads) [inline]¶

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.

Parameters:

Returns:

Definition at line 1286 of file multiway_merge.h.

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

Referenced by parallel_merge_advance().

template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_nth_element (RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, Comparator comp) [inline]¶

Parallel implementation of std::nth_element(). Parameters:

Definition at line 330 of file partition.h.

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

Referenced by parallel_partial_sort().

template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_partial_sort (RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, Comparator comp) [inline]¶

Parallel implementation of std::partial_sort(). Parameters:

Definition at line 418 of file partition.h.

References parallel_nth_element().

template<typename InputIterator , typename OutputIterator , typename BinaryOperation > OutputIterator __gnu_parallel::parallel_partial_sum (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op) [inline]¶

Parallel partial sum front-end. Parameters:

Returns:

Definition at line 196 of file partial_sum.h.

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

template<typename InputIterator , typename OutputIterator , typename BinaryOperation > OutputIterator __gnu_parallel::parallel_partial_sum_basecase (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename std::iterator_traits< InputIterator >::value_type value) [inline]¶

Base case prefix sum routine. Parameters:

Returns:

Definition at line 58 of file partial_sum.h.

Referenced by parallel_partial_sum_linear().

template<typename InputIterator , typename OutputIterator , typename BinaryOperation > OutputIterator __gnu_parallel::parallel_partial_sum_linear (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename std::iterator_traits< InputIterator >::difference_type n) [inline]¶

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

Returns:

Definition at line 90 of file partial_sum.h.

References equally_split(), __gnu_parallel::_Settings::get(), parallel_partial_sum_basecase(), and __gnu_parallel::_Settings::partial_sum_dilation.

Referenced by parallel_partial_sum().

template<typename RandomAccessIterator , typename Predicate > std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::parallel_partition (RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, thread_index_t num_threads) [inline]¶

Parallel implementation of std::partition. Parameters:

Returns:

Definition at line 55 of file partition.h.

References _GLIBCXX_CALL, _GLIBCXX_VOLATILE, __gnu_parallel::_Settings::get(), std::left(), __gnu_parallel::_Settings::partition_chunk_share, __gnu_parallel::_Settings::partition_chunk_size, and std::right().

Referenced by parallel_nth_element(), parallel_sort_qs_divide(), and qsb_divide().

template<typename RandomAccessIterator , typename RandomNumberGenerator > void __gnu_parallel::parallel_random_shuffle (RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator rng = random_number()) [inline]¶

Parallel random public call. Parameters:

Definition at line 507 of file random_shuffle.h.

References parallel_random_shuffle_drs().

template<typename RandomAccessIterator , typename RandomNumberGenerator > void __gnu_parallel::parallel_random_shuffle_drs (RandomAccessIterator begin, RandomAccessIterator end, typename std::iterator_traits< RandomAccessIterator >::difference_type n, thread_index_t num_threads, RandomNumberGenerator & rng) [inline]¶

Main parallel random shuffle step. Parameters:

Definition at line 258 of file random_shuffle.h.

References __log2(), _GLIBCXX_CALL, __gnu_parallel::DRandomShufflingGlobalData< RandomAccessIterator >::bin_proc, __gnu_parallel::DRSSorterPU< RandomAccessIterator, RandomNumberGenerator >::bins_begin, __gnu_parallel::DRSSorterPU< RandomAccessIterator, RandomNumberGenerator >::bins_end, __gnu_parallel::DRandomShufflingGlobalData< RandomAccessIterator >::dist, __gnu_parallel::_Settings::L2_cache_size, std::min(), __gnu_parallel::DRandomShufflingGlobalData< RandomAccessIterator >::num_bins, __gnu_parallel::DRandomShufflingGlobalData< RandomAccessIterator >::num_bits, __gnu_parallel::DRSSorterPU< RandomAccessIterator, RandomNumberGenerator >::num_threads, parallel_random_shuffle_drs_pu(), round_up_to_pow2(), __gnu_parallel::DRSSorterPU< RandomAccessIterator, RandomNumberGenerator >::sd, __gnu_parallel::DRSSorterPU< RandomAccessIterator, RandomNumberGenerator >::seed, sequential_random_shuffle(), __gnu_parallel::DRandomShufflingGlobalData< RandomAccessIterator >::starts, __gnu_parallel::DRandomShufflingGlobalData< RandomAccessIterator >::temporaries, and __gnu_parallel::_Settings::TLB_size.

Referenced by parallel_random_shuffle().

template<typename RandomAccessIterator , typename RandomNumberGenerator > void __gnu_parallel::parallel_random_shuffle_drs_pu (DRSSorterPU< RandomAccessIterator, RandomNumberGenerator > * pus) [inline]¶

Random shuffle code executed by each thread. Parameters:

Definition at line 122 of file random_shuffle.h.

References __gnu_parallel::DRandomShufflingGlobalData< RandomAccessIterator >::dist, __gnu_parallel::DRandomShufflingGlobalData< RandomAccessIterator >::num_bins, __gnu_parallel::DRandomShufflingGlobalData< RandomAccessIterator >::num_bits, __gnu_parallel::DRSSorterPU< RandomAccessIterator, RandomNumberGenerator >::num_threads, random_number_pow2(), __gnu_parallel::DRSSorterPU< RandomAccessIterator, RandomNumberGenerator >::sd, __gnu_parallel::DRSSorterPU< RandomAccessIterator, RandomNumberGenerator >::seed, and __gnu_parallel::DRandomShufflingGlobalData< RandomAccessIterator >::starts.

Referenced by parallel_random_shuffle_drs().

template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, parallel_tag parallelism) [inline]¶

Choose a parallel sorting algorithm. Parameters:

Definition at line 196 of file sort.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), __gnu_parallel::parallel_tag::get_num_threads(), parallel_sort_qs(), and parallel_sort_qsb().

template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, default_parallel_tag parallelism) [inline]¶

Choose multiway mergesort with exact splitting, for parallel sorting. Parameters:

Definition at line 175 of file sort.h.

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

template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, balanced_quicksort_tag parallelism) [inline]¶

Choose balanced quicksort for parallel sorting. Parameters:

Definition at line 154 of file sort.h.

References _GLIBCXX_CALL, __gnu_parallel::parallel_tag::get_num_threads(), and parallel_sort_qsb().

template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, quicksort_tag parallelism) [inline]¶

Choose quicksort for parallel sorting. Parameters:

Definition at line 134 of file sort.h.

References _GLIBCXX_CALL, __gnu_parallel::parallel_tag::get_num_threads(), and parallel_sort_qs().

template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, multiway_mergesort_sampling_tag parallelism) [inline]¶

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

Definition at line 116 of file sort.h.

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

template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, multiway_mergesort_exact_tag parallelism) [inline]¶

Choose multiway mergesort with exact splitting, for parallel sorting. Parameters:

Definition at line 97 of file sort.h.

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

template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, multiway_mergesort_tag parallelism) [inline]¶

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

Definition at line 74 of file sort.h.

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

template<bool stable, bool exact, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort_mwms (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads) [inline]¶

PMWMS main call. Parameters:

Definition at line 398 of file multiway_mergesort.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::num_threads, __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::offsets, __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::pieces, std::vector< _Tp, _Alloc >::resize(), __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::samples, __gnu_parallel::_Settings::sort_mwms_oversampling, __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::source, __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::starts, and __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::temporary.

template<bool stable, bool exact, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort_mwms_pu (PMWMSSortingData< RandomAccessIterator > * sd, Comparator & comp) [inline]¶

PMWMS code executed by each thread. Parameters:

Definition at line 315 of file multiway_mergesort.h.

References std::vector< _Tp, _Alloc >::begin(), std::vector< _Tp, _Alloc >::end(), __gnu_parallel::_Settings::get(), __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::num_threads, __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::pieces, __gnu_parallel::_Settings::sort_mwms_oversampling, __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::source, __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::starts, __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::temporary, and std::uninitialized_copy().

template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort_qs (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads) [inline]¶

Unbalanced quicksort main call. Parameters:

Definition at line 157 of file quicksort.h.

References _GLIBCXX_CALL, and parallel_sort_qs_conquer().

Referenced by parallel_sort().

template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort_qs_conquer (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads) [inline]¶

Unbalanced quicksort conquer step. Parameters:

Definition at line 101 of file quicksort.h.

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

Referenced by parallel_sort_qs().

template<typename RandomAccessIterator , typename Comparator > std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::parallel_sort_qs_divide (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, typename std::iterator_traits< RandomAccessIterator >::difference_type pivot_rank, typename std::iterator_traits< RandomAccessIterator >::difference_type num_samples, thread_index_t num_threads) [inline]¶

Unbalanced quicksort divide step. Parameters:

Definition at line 51 of file quicksort.h.

References min(), and parallel_partition().

Referenced by parallel_sort_qs_conquer().

template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort_qsb (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads) [inline]¶

Top-level quicksort routine. Parameters:

Definition at line 418 of file balanced_quicksort.h.

References _GLIBCXX_CALL, and qsb_conquer().

Referenced by parallel_sort().

template<typename InputIterator , class OutputIterator > OutputIterator __gnu_parallel::parallel_unique_copy (InputIterator first, InputIterator last, OutputIterator result) [inline]¶

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

Returns:

Definition at line 181 of file unique_copy.h.

References parallel_unique_copy().

template<typename InputIterator , class OutputIterator , class BinaryPredicate > OutputIterator __gnu_parallel::parallel_unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred) [inline]¶

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

Returns:

Definition at line 51 of file unique_copy.h.

References _GLIBCXX_CALL, and equally_split().

Referenced by parallel_unique_copy().

template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::qsb_conquer (QSBThreadLocal< RandomAccessIterator > ** tls, RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t iam, thread_index_t num_threads, bool parent_wait) [inline]¶

Quicksort conquer step. Parameters:

Definition at line 163 of file balanced_quicksort.h.

References __gnu_parallel::QSBThreadLocal< RandomAccessIterator >::elements_leftover, __gnu_parallel::QSBThreadLocal< RandomAccessIterator >::initial, qsb_divide(), and qsb_local_sort_with_helping().

Referenced by parallel_sort_qsb().

template<typename RandomAccessIterator , typename Comparator > std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::qsb_divide (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads) [inline]¶

Balanced quicksort divide step. Parameters:

Precondition:

Definition at line 100 of file balanced_quicksort.h.

References median_of_three_iterators(), and parallel_partition().

Referenced by qsb_conquer().

template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::qsb_local_sort_with_helping (QSBThreadLocal< RandomAccessIterator > ** tls, Comparator & comp, int iam, bool wait) [inline]¶

Quicksort step doing load-balanced local sort. Parameters:

Definition at line 239 of file balanced_quicksort.h.

References _GLIBCXX_ASSERTIONS, __gnu_parallel::QSBThreadLocal< RandomAccessIterator >::elements_leftover, __gnu_parallel::_Settings::get(), __gnu_parallel::QSBThreadLocal< RandomAccessIterator >::initial, __gnu_parallel::QSBThreadLocal< RandomAccessIterator >::leftover_parts, __gnu_parallel::QSBThreadLocal< RandomAccessIterator >::num_threads, __gnu_parallel::RestrictedBoundedConcurrentQueue< T >::pop_front(), __gnu_parallel::RestrictedBoundedConcurrentQueue< T >::push_front(), __gnu_parallel::_Settings::sort_qsb_base_case_maximal_n, and yield().

Referenced by qsb_conquer().

template<typename RandomNumberGenerator > int __gnu_parallel::random_number_pow2 (int logp, RandomNumberGenerator & rng) [inline]¶

Generate a random number in [0,2^logp). Parameters:

Definition at line 115 of file random_shuffle.h.

Referenced by parallel_random_shuffle_drs_pu(), and sequential_random_shuffle().

template<typename T > T __gnu_parallel::round_up_to_pow2 (T x) [inline]¶

Round up to the next greater power of 2. Parameters:

Definition at line 241 of file random_shuffle.h.

References __log2().

Referenced by parallel_random_shuffle_drs(), and sequential_random_shuffle().

template<typename _RandomAccessIterator1 , typename _RandomAccessIterator2 , typename Pred > _RandomAccessIterator1 __gnu_parallel::search_template (_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1, _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2, Pred pred) [inline]¶

Parallel std::search. Parameters:

Returns:

Definition at line 82 of file search.h.

References _GLIBCXX_CALL, calc_borders(), equally_split(), and min().

template<bool stable, bool sentinels, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::sequential_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type & sentinel, _DifferenceTp length, Comparator comp) [inline]¶

Sequential multi-way merging switch. The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings.

Parameters:

Returns:

Definition at line 979 of file multiway_merge.h.

References _GLIBCXX_CALL, _GLIBCXX_PARALLEL_LENGTH, is_sorted(), and merge_advance().

Referenced by multiway_merge(), and multiway_merge_sentinels().

template<typename RandomAccessIterator , typename RandomNumberGenerator > void __gnu_parallel::sequential_random_shuffle (RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator & rng) [inline]¶

Sequential cache-efficient random shuffle. Parameters:

Definition at line 394 of file random_shuffle.h.

References __log2(), __gnu_parallel::_Settings::L2_cache_size, std::min(), random_number_pow2(), round_up_to_pow2(), and __gnu_parallel::_Settings::TLB_size.

Referenced by parallel_random_shuffle_drs().

template<typename InputIterator > void __gnu_parallel::shrink (std::vector< InputIterator > & os_starts, size_t & count_to_two, size_t & range_length) [inline]¶

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

Definition at line 70 of file list_partition.h.

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

Referenced by shrink_and_double().

template<typename InputIterator > void __gnu_parallel::shrink_and_double (std::vector< InputIterator > & os_starts, size_t & count_to_two, size_t & range_length, const bool make_twice) [inline]¶

Shrinks and doubles the ranges. Parameters:

Definition at line 50 of file list_partition.h.

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

Referenced by list_partition().

void __gnu_parallel::yield () [inline]¶

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

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

Referenced by for_each_template_random_access_workstealing(), and qsb_local_sort_with_helping().

const int __gnu_parallel::lcas_t_bits [static]¶

Number of bits of lcas_t.

Definition at line 149 of file types.h.

Referenced by decode2(), and encode2().

const lcas_t __gnu_parallel::lcas_t_mask [static]¶

lcas_t with the right half of bits set to 1.

Definition at line 152 of file types.h.

Referenced by decode2().