libstdc++
|
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) |
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, __gnu_parallel::sequential_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::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, 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, default_parallel_tag 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, __gnu_parallel::sequential_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, 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, 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, default_parallel_tag tag) |
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 RandomAccessIterator , typename Comparator > | |
bool | operator<= (unguarded_iterator< RandomAccessIterator, Comparator > &bi1, unguarded_iterator< RandomAccessIterator, Comparator > &bi2) |
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<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<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 , typename Parallelism > | |
void | parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, Parallelism 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 > | |
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_sampling_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, balanced_quicksort_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, parallel_tag 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 , class BinaryPredicate > | |
OutputIterator | parallel_unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred) |
template<typename InputIterator , class OutputIterator > | |
OutputIterator | parallel_unique_copy (InputIterator first, InputIterator last, OutputIterator result) |
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, __gnu_parallel::sequential_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, 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, 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, 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, __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, __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, 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, 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, default_parallel_tag tag) |
void | yield () |
Variables | |
static const int | lcas_t_bits |
static const lcas_t | lcas_t_mask |
GNU parallel code for public use.
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 |
typedef int __gnu_parallel::int32 |
typedef long long __gnu_parallel::int64 |
typedef int64 __gnu_parallel::lcas_t |
typedef uint16 __gnu_parallel::thread_index_t |
typedef unsigned short __gnu_parallel::uint16 |
typedef unsigned int __gnu_parallel::uint32 |
typedef unsigned long long __gnu_parallel::uint64 |
Run-time equivalents for the compile-time tags.
|
inline |
Calculates the rounded-down logarithm of n
for base 2.
n | Argument. |
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().
void __gnu_parallel::calc_borders | ( | RandomAccessIterator | elements, |
_DifferenceTp | length, | ||
_DifferenceTp * | off | ||
) |
Precalculate advances for Knuth-Morris-Pratt algorithm.
elements | Begin iterator of sequence to search for. |
length | Length of sequence to search for. |
advances | Returned offsets. |
Definition at line 52 of file search.h.
Referenced by search_template().
|
inline |
Compare *ptr
and comparand
. If equal, let *ptr=replacement
and return true
, return false
otherwise.
Implementation is heavily platform-dependent.
ptr | Pointer to signed integer. |
comparand | Compare value. |
replacement | Replacement value. |
Definition at line 327 of file parallel/compatibility.h.
References compare_and_swap_32(), and compare_and_swap_64().
Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< pair< RandomAccessIterator, RandomAccessIterator > >::pop_back(), and __gnu_parallel::RestrictedBoundedConcurrentQueue< pair< RandomAccessIterator, RandomAccessIterator > >::pop_front().
|
inline |
Compare *ptr
and comparand
. If equal, let *ptr=replacement
and return true
, return false
otherwise.
Implementation is heavily platform-dependent.
ptr | Pointer to 32-bit signed integer. |
comparand | Compare value. |
replacement | Replacement value. |
Definition at line 235 of file parallel/compatibility.h.
Referenced by compare_and_swap().
|
inline |
Compare *ptr
and comparand
. If equal, let *ptr=replacement
and return true
, return false
otherwise.
Implementation is heavily platform-dependent.
ptr | Pointer to 64-bit signed integer. |
comparand | Compare value. |
replacement | Replacement value. |
Definition at line 275 of file parallel/compatibility.h.
Referenced by compare_and_swap().
|
inline |
Decode two integers from one __gnu_parallel::lcas_t.
x | __gnu_parallel::lcas_t to decode integers from. |
a | First integer, to be decoded from the most-significant lcas_t_bits/2 bits of x . |
b | Second integer, to be encoded in the least-significant lcas_t_bits/2 bits of x . |
Definition at line 136 of file base.h.
References lcas_t_bits, and lcas_t_mask.
Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< pair< RandomAccessIterator, RandomAccessIterator > >::pop_back(), __gnu_parallel::RestrictedBoundedConcurrentQueue< pair< RandomAccessIterator, RandomAccessIterator > >::pop_front(), and __gnu_parallel::RestrictedBoundedConcurrentQueue< pair< RandomAccessIterator, RandomAccessIterator > >::push_front().
void __gnu_parallel::determine_samples | ( | PMWMSSortingData< RandomAccessIterator > * | sd, |
_DifferenceTp | num_samples | ||
) |
Select samples from a sequence.
sd | Pointer to algorithm data. Result will be placed in sd->samples . |
num_samples | Number of samples to select. |
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.
|
inline |
Encode two integers into one __gnu_parallel::lcas_t.
a | First integer, to be encoded in the most-significant lcas_t_bits/2 bits. |
b | Second integer, to be encoded in the least-significant lcas_t_bits/2 bits. |
a
and b
. Definition at line 122 of file base.h.
References lcas_t_bits.
Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< pair< RandomAccessIterator, RandomAccessIterator > >::pop_back(), __gnu_parallel::RestrictedBoundedConcurrentQueue< pair< RandomAccessIterator, RandomAccessIterator > >::pop_front(), __gnu_parallel::RestrictedBoundedConcurrentQueue< pair< RandomAccessIterator, RandomAccessIterator > >::push_front(), and __gnu_parallel::RestrictedBoundedConcurrentQueue< pair< RandomAccessIterator, RandomAccessIterator > >::RestrictedBoundedConcurrentQueue().
OutputIterator __gnu_parallel::equally_split | ( | difference_type | n, |
thread_index_t | 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.
n | Number of elements |
num_threads | Number of parts |
s | Splitters |
s+num_threads+1
Definition at line 48 of file equally_split.h.
Referenced by determine_samples(), multiway_merge_exact_splitting(), parallel_partial_sum_linear(), parallel_unique_copy(), and search_template().
difference_type __gnu_parallel::equally_split_point | ( | difference_type | n, |
thread_index_t | num_threads, | ||
thread_index_t | 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).
n | Number of elements |
num_threads | Number of parts |
Definition at line 73 of file equally_split.h.
Referenced by for_each_template_random_access_ed().
|
inline |
Add a value to a variable, atomically.
Implementation is heavily platform-dependent.
ptr | Pointer to a signed integer. |
addend | Value to add. |
Definition at line 185 of file parallel/compatibility.h.
References fetch_and_add_32(), and fetch_and_add_64().
Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue< pair< RandomAccessIterator, RandomAccessIterator > >::push_front().
Add a value to a variable, atomically.
Implementation is heavily platform-dependent.
ptr | Pointer to a 32-bit signed integer. |
addend | Value to add. |
Definition at line 95 of file parallel/compatibility.h.
Referenced by fetch_and_add().
Add a value to a variable, atomically.
Implementation is heavily platform-dependent.
ptr | Pointer to a 64-bit signed integer. |
addend | Value to add. |
Definition at line 134 of file parallel/compatibility.h.
Referenced by fetch_and_add().
|
inline |
Parallel std::find, switch for different algorithms.
begin1 | Begin iterator of first sequence. |
end1 | End iterator of first sequence. |
begin2 | Begin iterator of second sequence. Must have same length as first sequence. |
pred | Find predicate. |
selector | Functionality (e. g. std::find_if (), std::equal(),...) |
Definition at line 60 of file find.h.
References __gnu_parallel::_Settings::get().
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 | ||
) |
Chose the desired algorithm by evaluating parallelism_tag
.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
user_op | A user-specified functor (comparator, predicate, associative operator,...) |
functionality | functor to "process" an element with user_op (depends on desired functionality, e. g. accumulate, for_each,... |
reduction | Reduction functor. |
reduction_start | Initial value for reduction. |
output | Output iterator. |
bound | Maximum number of elements processed. |
parallelism_tag | Parallelization method |
Definition at line 61 of file for_each.h.
References for_each_template_random_access_ed(), for_each_template_random_access_omp_loop(), for_each_template_random_access_workstealing(), parallel_omp_loop, parallel_omp_loop_static, and parallel_unbalanced.
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 | ||
) |
Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work.
begin | Begin iterator of element sequence. |
end | End iterator of element sequence. |
o | User-supplied functor (comparator, predicate, adding functor, ...) |
f | Functor to "process" an element with op (depends on desired functionality, e. g. for std::for_each(), ...). |
r | Functor to "add" a single result to the already processed elements (depends on functionality). |
base | Base value for reduction. |
output | Pointer to position where final result is written to |
bound | Maximum number of elements processed (e. g. for std::count_n()). |
Definition at line 68 of file par_loop.h.
References equally_split_point().
Referenced by for_each_template_random_access().
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 | ||
) |
Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop.
begin | Begin iterator of element sequence. |
end | End iterator of element sequence. |
o | User-supplied functor (comparator, predicate, adding functor, etc.). |
f | Functor to "process" an element with op (depends on desired functionality, e. g. for std::for_each(), ...). |
r | Functor to "add" a single result to the already processed elements (depends on functionality). |
base | Base value for reduction. |
output | Pointer to position where final result is written to |
bound | Maximum number of elements processed (e. g. for std::count_n()). |
Definition at line 67 of file omp_loop.h.
Referenced by for_each_template_random_access().
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 | ||
) |
Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling.
begin | Begin iterator of element sequence. |
end | End iterator of element sequence. |
o | User-supplied functor (comparator, predicate, adding functor, ...). |
f | Functor to "process" an element with op (depends on desired functionality, e. g. for std::for_each(), ...). |
r | Functor to "add" a single result to the already processed elements (depends on functionality). |
base | Base value for reduction. |
output | Pointer to position where final result is written to |
bound | Maximum number of elements processed (e. g. for std::count_n()). |
Definition at line 67 of file omp_loop_static.h.
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 | ||
) |
Work stealing algorithm for random access iterators.
Uses O(1) additional memory. Synchronization at job lists is done with atomic operations.
begin | Begin iterator of element sequence. |
end | End iterator of element sequence. |
op | User-supplied functor (comparator, predicate, adding functor, ...). |
f | Functor to "process" an element with op (depends on desired functionality, e. g. for std::for_each(), ...). |
r | Functor to "add" a single result to the already processed elements (depends on functionality). |
base | Base value for reduction. |
output | Pointer to position where final result is written to |
bound | Maximum number of elements processed (e. g. for std::count_n()). |
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().
bool __gnu_parallel::is_sorted | ( | InputIterator | begin, |
InputIterator | end, | ||
Comparator | comp = std::less<typename std::iterator_traits<InputIterator>:: value_type>() |
||
) |
Check whether [begin,
end
) is sorted according to comp
.
begin | Begin iterator of sequence. |
end | End iterator of sequence. |
comp | Comparator. |
true
if sorted, false
otherwise. Definition at line 51 of file checkers.h.
Referenced by multiway_merge_loser_tree_sentinel(), parallel_multiway_merge(), and sequential_multiway_merge().
bool __gnu_parallel::is_sorted_failure | ( | InputIterator | begin, |
InputIterator | end, | ||
InputIterator & | first_failure, | ||
Comparator | comp = std::less<typename std::iterator_traits<InputIterator>:: value_type>() |
||
) |
Check whether [begin,
end
) is sorted according to comp
. Prints the position in case an unordered pair is found.
begin | Begin iterator of sequence. |
end | End iterator of sequence. |
first_failure | The first failure is returned in this variable. |
comp | Comparator. |
true
if sorted, false
otherwise. Definition at line 89 of file checkers.h.
bool __gnu_parallel::is_sorted_print_failures | ( | InputIterator | begin, |
InputIterator | end, | ||
Comparator | comp = std::less<typename std::iterator_traits <InputIterator>::value_type>() |
||
) |
Check whether [begin,
end
) is sorted according to comp
. Prints all unordered pair, including the surrounding two elements.
begin | Begin iterator of sequence. |
end | End iterator of sequence. |
comp | Comparator. |
true
if sorted, false
otherwise. Definition at line 129 of file checkers.h.
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 |
||
) |
Splits a sequence given by input iterators into parts of almost equal size.
The function needs only one pass over the sequence.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
starts | Start iterators for the resulting parts, dimension num_parts+1 . For convenience, starts [num_parts] contains the end iterator of the sequence. |
lengths | Length of the resulting parts. |
num_parts | Number of parts to split the sequence into. |
f | Functor to be applied to each element by traversing it |
oversampling | Oversampling factor. If 0, then the partitions will differ in at most ![]() ![]() |
Definition at line 100 of file list_partition.h.
References shrink_and_double(), and std::vector< _Tp, _Alloc >::size().
const T& __gnu_parallel::max | ( | const T & | a, |
const T & | b | ||
) |
RandomAccessIterator __gnu_parallel::median_of_three_iterators | ( | RandomAccessIterator | a, |
RandomAccessIterator | b, | ||
RandomAccessIterator | c, | ||
Comparator & | comp | ||
) |
Compute the median of three referenced elements, according to comp
.
a | First iterator. |
b | Second iterator. |
c | Third iterator. |
comp | Comparator. |
Definition at line 443 of file base.h.
Referenced by qsb_divide().
|
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.
begin1 | Begin iterator of first sequence. |
end1 | End iterator of first sequence. |
begin2 | Begin iterator of second sequence. |
end2 | End iterator of second sequence. |
target | Target begin iterator. |
max_length | Maximum number of elements to merge. |
comp | Comparator. |
Definition at line 174 of file merge.h.
References _GLIBCXX_CALL, and merge_advance_movc().
Referenced by parallel_merge_advance(), and sequential_multiway_merge().
OutputIterator __gnu_parallel::merge_advance_movc | ( | RandomAccessIterator1 & | begin1, |
RandomAccessIterator1 | end1, | ||
RandomAccessIterator2 & | begin2, | ||
RandomAccessIterator2 | end2, | ||
OutputIterator | target, | ||
_DifferenceTp | max_length, | ||
Comparator | 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.
begin1 | Begin iterator of first sequence. |
end1 | End iterator of first sequence. |
begin2 | Begin iterator of second sequence. |
end2 | End iterator of second sequence. |
target | Target begin iterator. |
max_length | Maximum number of elements to merge. |
comp | Comparator. |
Definition at line 106 of file merge.h.
Referenced by merge_advance().
OutputIterator __gnu_parallel::merge_advance_usual | ( | RandomAccessIterator1 & | begin1, |
RandomAccessIterator1 | end1, | ||
RandomAccessIterator2 & | begin2, | ||
RandomAccessIterator2 | end2, | ||
OutputIterator | target, | ||
_DifferenceTp | max_length, | ||
Comparator | 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.
begin1 | Begin iterator of first sequence. |
end1 | End iterator of first sequence. |
begin2 | Begin iterator of second sequence. |
end2 | End iterator of second sequence. |
target | Target begin iterator. |
max_length | Maximum number of elements to merge. |
comp | Comparator. |
const T& __gnu_parallel::min | ( | const T & | a, |
const T & | b | ||
) |
Equivalent to std::min.
Definition at line 145 of file base.h.
Referenced by for_each_template_random_access_workstealing().
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>() |
||
) |
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.
begin_seqs | Begin of the sequence of iterator pairs. |
end_seqs | End of the sequence of iterator pairs. |
rank | The global rank to partition at. |
begin_offsets | A random-access sequence begin where the result will be stored in. Each element of the sequence is an iterator that points to the first element on the greater part of the respective sequence. |
comp | The ordering functor, defaults to std::less<T>. |
Definition at line 123 of file multiseq_selection.h.
References __log2(), _GLIBCXX_CALL, std::vector< _Tp, _Alloc >::begin(), std::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::vector< _Tp, _Alloc >::end(), std::max(), std::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().
T __gnu_parallel::multiseq_selection | ( | RanSeqs | begin_seqs, |
RanSeqs | end_seqs, | ||
RankType | rank, | ||
RankType & | offset, | ||
Comparator | comp = std::less<T>() |
||
) |
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.
begin_seqs | Begin of the sequence of iterator pairs. |
end_seqs | End of the sequence of iterator pairs. |
rank | The global rank to partition at. |
offset | The rank of the selected element in the global subsequence of elements equal to the selected element. If the selected element is unique, this number is 0. |
comp | The ordering functor, defaults to std::less. |
Definition at line 377 of file multiseq_selection.h.
References __log2(), _GLIBCXX_CALL, std::vector< _Tp, _Alloc >::begin(), std::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::vector< _Tp, _Alloc >::end(), std::max(), std::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().
RandomAccessIteratorOut __gnu_parallel::multiway_merge | ( | RandomAccessIteratorPairIterator | seqs_begin, |
RandomAccessIteratorPairIterator | seqs_end, | ||
RandomAccessIteratorOut | target, | ||
_DifferenceTp | length, | ||
Comparator | 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 end of the same sequence in their second entry.
Ties are broken arbitrarily. See stable_multiway_merge for a variant that breaks ties by sequence number but is slower.
The first entries of the pairs (i.e. the begin iterators) will be moved forward.
The output sequence has to provide enough space for all elements that are written to it.
This function will merge the input sequences:
Example:
int sequences[10][10]; for (int i = 0; i < 10; ++i) for (int j = 0; i < 10; ++j) sequences[i][j] = j;
int out[33]; std::vector<std::pair<int*> > seqs; for (int i = 0; i < 10; ++i) { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
RandomAccessIteratorPairIterator | iterator over sequence of pairs of iterators |
RandomAccessIteratorOut | iterator over target sequence |
_DifferenceTp | difference type for the sequence |
Comparator | strict weak ordering type to compare elements in sequences |
seqs_begin | begin of sequence sequence |
seqs_end | end of sequence sequence |
target | target sequence to merge to. |
comp | strict weak ordering to use for element comparison. |
length | Maximum length to merge, possibly larger than the number of elements available. |
Definition at line 1477 of file multiway_merge.h.
References _GLIBCXX_CALL, and sequential_multiway_merge().
RandomAccessIterator3 __gnu_parallel::multiway_merge_3_variant | ( | RandomAccessIteratorIterator | seqs_begin, |
RandomAccessIteratorIterator | seqs_end, | ||
RandomAccessIterator3 | target, | ||
_DifferenceTp | length, | ||
Comparator | 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 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.
seqs_begin | Begin iterator of iterator pair input sequence. |
seqs_end | End iterator of iterator pair input sequence. |
target | Begin iterator out output sequence. |
comp | Comparator. |
length | Maximum length to merge, less equal than the total number of elements available. |
Definition at line 290 of file multiway_merge.h.
References _GLIBCXX_CALL.
RandomAccessIterator3 __gnu_parallel::multiway_merge_4_variant | ( | RandomAccessIteratorIterator | seqs_begin, |
RandomAccessIteratorIterator | seqs_end, | ||
RandomAccessIterator3 | target, | ||
_DifferenceTp | length, | ||
Comparator | 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 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.
seqs_begin | Begin iterator of iterator pair input sequence. |
seqs_end | End iterator of iterator pair input sequence. |
target | Begin iterator out output sequence. |
comp | Comparator. |
length | Maximum length to merge, less equal than the total number of elements available. |
Definition at line 410 of file multiway_merge.h.
References _GLIBCXX_CALL.
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 | ||
) |
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().
RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree | ( | RandomAccessIteratorIterator | seqs_begin, |
RandomAccessIteratorIterator | seqs_end, | ||
RandomAccessIterator3 | target, | ||
_DifferenceTp | length, | ||
Comparator | 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.
seqs_begin | Begin iterator of iterator pair input sequence. |
seqs_end | End iterator of iterator pair input sequence. |
target | Begin iterator out output sequence. |
comp | Comparator. |
length | Maximum length to merge, less equal than the total number of elements available. |
Definition at line 534 of file multiway_merge.h.
References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_LENGTH.
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 | ||
) |
Multi-way merging procedure for a high branching factor, requiring sentinels to exist.
stable | The value must the same as for the used LoserTrees. |
UnguardedLoserTree | Loser Tree variant to use for the unguarded merging. |
GuardedLoserTree | Loser Tree variant to use for the guarded merging. |
seqs_begin | Begin iterator of iterator pair input sequence. |
seqs_end | End iterator of iterator pair input sequence. |
target | Begin iterator out output sequence. |
comp | Comparator. |
length | Maximum length to merge, less equal than the total number of elements available. |
Definition at line 705 of file multiway_merge.h.
References _GLIBCXX_CALL, is_sorted(), and multiway_merge_loser_tree_unguarded().
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 | ||
) |
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.
seqs_begin | Begin iterator of iterator pair input sequence. |
seqs_end | End iterator of iterator pair input sequence. |
target | Begin iterator out output sequence. |
comp | Comparator. |
length | Maximum length to merge, less equal than the total number of elements available. |
Definition at line 615 of file multiway_merge.h.
References _GLIBCXX_CALL.
Referenced by multiway_merge_loser_tree_sentinel().
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 | ||
) |
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.
RandomAccessIteratorOut __gnu_parallel::multiway_merge_sentinels | ( | RandomAccessIteratorPairIterator | seqs_begin, |
RandomAccessIteratorPairIterator | seqs_end, | ||
RandomAccessIteratorOut | target, | ||
_DifferenceTp | length, | ||
Comparator | 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 end of the same sequence in their second entry.
Ties are broken arbitrarily. See stable_multiway_merge for a variant that breaks ties by sequence number but is slower.
The first entries of the pairs (i.e. the begin iterators) will be moved forward accordingly.
The output sequence has to provide enough space for all elements that are written to it.
This function will merge the input sequences:
You have to take care that the element the 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);
i
, seqs_begin
[i].second must be the end marker of the sequence, but also reference the one more sentinel element.RandomAccessIteratorPairIterator | iterator over sequence of pairs of iterators |
RandomAccessIteratorOut | iterator over target sequence |
_DifferenceTp | difference type for the sequence |
Comparator | strict weak ordering type to compare elements in sequences |
seqs_begin | begin of sequence sequence |
seqs_end | end of sequence sequence |
target | target sequence to merge to. |
comp | strict weak ordering to use for element comparison. |
length | Maximum length to merge, possibly larger than the number of elements available. |
Definition at line 1849 of file multiway_merge.h.
References _GLIBCXX_CALL, and sequential_multiway_merge().
|
inline |
Compare two elements referenced by guarded iterators.
bi1 | First iterator. |
bi2 | Second iterator. |
True
if less. Definition at line 144 of file multiway_merge.h.
|
inline |
Compare two elements referenced by unguarded iterators.
bi1 | First iterator. |
bi2 | Second iterator. |
True
if less. Definition at line 239 of file multiway_merge.h.
|
inline |
Compare two elements referenced by guarded iterators.
bi1 | First iterator. |
bi2 | Second iterator. |
True
if less equal. Definition at line 160 of file multiway_merge.h.
|
inline |
Compare two elements referenced by unguarded iterators.
bi1 | First iterator. |
bi2 | Second iterator. |
True
if less equal. Definition at line 252 of file multiway_merge.h.
|
inline |
Merge routine fallback to sequential in case the iterators of the two input sequences are of different type.
begin1 | Begin iterator of first sequence. |
end1 | End iterator of first sequence. |
begin2 | Begin iterator of second sequence. |
end2 | End iterator of second sequence. |
target | Target begin iterator. |
max_length | Maximum number of elements to merge. |
comp | Comparator. |
Definition at line 198 of file merge.h.
References merge_advance().
|
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.
begin1 | Begin iterator of first sequence. |
end1 | End iterator of first sequence. |
begin2 | Begin iterator of second sequence. |
end2 | End iterator of second sequence. |
target | Target begin iterator. |
max_length | Maximum number of elements to merge. |
comp | Comparator. |
Definition at line 228 of file merge.h.
References multiway_merge_exact_splitting(), and parallel_multiway_merge().
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 | ||
) |
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.
Splitter | functor to split input (either exact or sampling based) |
seqs_begin | Begin iterator of iterator pair input sequence. |
seqs_end | End iterator of iterator pair input sequence. |
target | Begin iterator out output sequence. |
comp | Comparator. |
length | Maximum length to merge, possibly larger than the number of elements available. |
stable | Stable merging incurs a performance penalty. |
sentinel | Ignored. |
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().
void __gnu_parallel::parallel_nth_element | ( | RandomAccessIterator | begin, |
RandomAccessIterator | nth, | ||
RandomAccessIterator | end, | ||
Comparator | comp | ||
) |
Parallel implementation of std::nth_element().
begin | Begin iterator of input sequence. |
nth | Iterator of element that must be in position afterwards. |
end | End iterator of input sequence. |
comp | Comparator. |
Definition at line 330 of file partition.h.
References _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), std::max(), __gnu_parallel::_Settings::nth_element_minimal_n, parallel_partition(), __gnu_parallel::_Settings::partition_minimal_n, and std::swap().
Referenced by parallel_partial_sort().
void __gnu_parallel::parallel_partial_sort | ( | RandomAccessIterator | begin, |
RandomAccessIterator | middle, | ||
RandomAccessIterator | end, | ||
Comparator | comp | ||
) |
Parallel implementation of std::partial_sort().
begin | Begin iterator of input sequence. |
middle | Sort until this position. |
end | End iterator of input sequence. |
comp | Comparator. |
Definition at line 418 of file partition.h.
References parallel_nth_element().
OutputIterator __gnu_parallel::parallel_partial_sum | ( | InputIterator | begin, |
InputIterator | end, | ||
OutputIterator | result, | ||
BinaryOperation | bin_op | ||
) |
Parallel partial sum front-end.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
result | Begin iterator of output sequence. |
bin_op | Associative binary function. |
Definition at line 196 of file partial_sum.h.
References _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), and parallel_partial_sum_linear().
OutputIterator __gnu_parallel::parallel_partial_sum_basecase | ( | InputIterator | begin, |
InputIterator | end, | ||
OutputIterator | result, | ||
BinaryOperation | bin_op, | ||
typename std::iterator_traits< InputIterator >::value_type | value | ||
) |
Base case prefix sum routine.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
result | Begin iterator of output sequence. |
bin_op | Associative binary function. |
value | Start value. Must be passed since the neutral element is unknown in general. |
Definition at line 58 of file partial_sum.h.
Referenced by parallel_partial_sum_linear().
OutputIterator __gnu_parallel::parallel_partial_sum_linear | ( | InputIterator | begin, |
InputIterator | end, | ||
OutputIterator | result, | ||
BinaryOperation | bin_op, | ||
typename std::iterator_traits< InputIterator >::difference_type | n | ||
) |
Parallel partial sum implementation, two-phase approach, no recursion.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
result | Begin iterator of output sequence. |
bin_op | Associative binary function. |
n | Length of sequence. |
num_threads | Number of threads to use. |
Definition at line 90 of file partial_sum.h.
References std::accumulate(), equally_split(), __gnu_parallel::_Settings::get(), parallel_partial_sum_basecase(), and __gnu_parallel::_Settings::partial_sum_dilation.
Referenced by parallel_partial_sum().
std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::parallel_partition | ( | RandomAccessIterator | begin, |
RandomAccessIterator | end, | ||
Predicate | pred, | ||
thread_index_t | num_threads | ||
) |
Parallel implementation of std::partition.
begin | Begin iterator of input sequence to split. |
end | End iterator of input sequence to split. |
pred | Partition predicate, possibly including some kind of pivot. |
num_threads | Maximum number of threads to use for this task. |
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, std::right(), and std::swap().
Referenced by parallel_nth_element(), parallel_sort_qs_divide(), and qsb_divide().
|
inline |
Parallel random public call.
begin | Begin iterator of sequence. |
end | End iterator of sequence. |
rng | Random number generator to use. |
Definition at line 507 of file random_shuffle.h.
References parallel_random_shuffle_drs().
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 | ||
) |
Main parallel random shuffle step.
begin | Begin iterator of sequence. |
end | End iterator of sequence. |
n | Length of sequence. |
num_threads | Number of threads to use. |
rng | Random number generator to use. |
Definition at line 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::get(), __gnu_parallel::_Settings::L2_cache_size, std::max(), 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().
void __gnu_parallel::parallel_random_shuffle_drs_pu | ( | DRSSorterPU< RandomAccessIterator, RandomNumberGenerator > * | pus | ) |
Random shuffle code executed by each thread.
pus | Array of thread-local data records. |
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, std::partial_sum(), 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().
|
inline |
Choose multiway mergesort, splitting variant at run-time, for parallel sorting.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
comp | Comparator. |
Definition at line 74 of file sort.h.
References _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), and __gnu_parallel::parallel_tag::get_num_threads().
|
inline |
Choose multiway mergesort with exact splitting, for parallel sorting.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
comp | Comparator. |
Definition at line 97 of file sort.h.
References _GLIBCXX_CALL, and __gnu_parallel::parallel_tag::get_num_threads().
|
inline |
Choose multiway mergesort with splitting by sampling, for parallel sorting.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
comp | Comparator. |
Definition at line 116 of file sort.h.
References _GLIBCXX_CALL, and __gnu_parallel::parallel_tag::get_num_threads().
|
inline |
Choose quicksort for parallel sorting.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
comp | Comparator. |
Definition at line 134 of file sort.h.
References _GLIBCXX_CALL, __gnu_parallel::parallel_tag::get_num_threads(), and parallel_sort_qs().
|
inline |
Choose balanced quicksort for parallel sorting.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
comp | Comparator. |
stable | Sort stable. |
Definition at line 154 of file sort.h.
References _GLIBCXX_CALL, __gnu_parallel::parallel_tag::get_num_threads(), and parallel_sort_qsb().
|
inline |
Choose multiway mergesort with exact splitting, for parallel sorting.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
comp | Comparator. |
Definition at line 175 of file sort.h.
References _GLIBCXX_CALL, and __gnu_parallel::parallel_tag::get_num_threads().
|
inline |
Choose a parallel sorting algorithm.
begin | Begin iterator of input sequence. |
end | End iterator of input sequence. |
comp | Comparator. |
stable | Sort stable. |
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().
void __gnu_parallel::parallel_sort_mwms | ( | RandomAccessIterator | begin, |
RandomAccessIterator | end, | ||
Comparator | comp, | ||
thread_index_t | num_threads | ||
) |
PMWMS main call.
begin | Begin iterator of sequence. |
end | End iterator of sequence. |
comp | Comparator. |
n | Length of sequence. |
num_threads | Number of threads to use. |
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, __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.
void __gnu_parallel::parallel_sort_mwms_pu | ( | PMWMSSortingData< RandomAccessIterator > * | sd, |
Comparator & | comp | ||
) |
PMWMS code executed by each thread.
sd | Pointer to algorithm data. |
comp | Comparator. |
Definition at line 315 of file multiway_mergesort.h.
References __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().
void __gnu_parallel::parallel_sort_qs | ( | RandomAccessIterator | begin, |
RandomAccessIterator | end, | ||
Comparator | comp, | ||
thread_index_t | num_threads | ||
) |
Unbalanced quicksort main call.
begin | Begin iterator of input sequence. |
end | End iterator input sequence, ignored. |
comp | Comparator. |
num_threads | Number of threads that are allowed to work on this part. |
Definition at line 157 of file quicksort.h.
References _GLIBCXX_CALL, and parallel_sort_qs_conquer().
Referenced by parallel_sort().
void __gnu_parallel::parallel_sort_qs_conquer | ( | RandomAccessIterator | begin, |
RandomAccessIterator | end, | ||
Comparator | comp, | ||
thread_index_t | num_threads | ||
) |
Unbalanced quicksort conquer step.
begin | Begin iterator of subsequence. |
end | End iterator of subsequence. |
comp | Comparator. |
num_threads | Number of threads that are allowed to work on this part. |
Definition at line 101 of file quicksort.h.
References __gnu_parallel::_Settings::get(), and parallel_sort_qs_divide().
Referenced by parallel_sort_qs().
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 | ||
) |
Unbalanced quicksort divide step.
begin | Begin iterator of subsequence. |
end | End iterator of subsequence. |
comp | Comparator. |
pivot_rank | Desired rank of the pivot. |
num_samples | Choose pivot from that many samples. |
num_threads | Number of threads that are allowed to work on this part. |
Definition at line 51 of file quicksort.h.
References std::min(), and parallel_partition().
Referenced by parallel_sort_qs_conquer().
void __gnu_parallel::parallel_sort_qsb | ( | RandomAccessIterator | begin, |
RandomAccessIterator | end, | ||
Comparator | comp, | ||
thread_index_t | num_threads | ||
) |
Top-level quicksort routine.
begin | Begin iterator of sequence. |
end | End iterator of sequence. |
comp | Comparator. |
num_threads | Number of threads that are allowed to work on this part. |
Definition at line 418 of file balanced_quicksort.h.
References _GLIBCXX_CALL, __gnu_parallel::QSBThreadLocal< RandomAccessIterator >::elements_leftover, and qsb_conquer().
Referenced by parallel_sort().
OutputIterator __gnu_parallel::parallel_unique_copy | ( | InputIterator | first, |
InputIterator | last, | ||
OutputIterator | result, | ||
BinaryPredicate | binary_pred | ||
) |
Parallel std::unique_copy(), w/o explicit equality predicate.
first | Begin iterator of input sequence. |
last | End iterator of input sequence. |
result | Begin iterator of result sequence. |
binary_pred | Equality predicate. |
Definition at line 51 of file unique_copy.h.
References _GLIBCXX_CALL, and equally_split().
Referenced by parallel_unique_copy().
|
inline |
Parallel std::unique_copy(), without explicit equality predicate.
first | Begin iterator of input sequence. |
last | End iterator of input sequence. |
result | Begin iterator of result sequence. |
Definition at line 181 of file unique_copy.h.
References parallel_unique_copy().
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 | ||
) |
Quicksort conquer step.
tls | Array of thread-local storages. |
begin | Begin iterator of subsequence. |
end | End iterator of subsequence. |
comp | Comparator. |
iam | Number of the thread processing this function. |
num_threads | Number of threads that are allowed to work on this part. |
Definition at line 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().
std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::qsb_divide | ( | RandomAccessIterator | begin, |
RandomAccessIterator | end, | ||
Comparator | comp, | ||
thread_index_t | num_threads | ||
) |
Balanced quicksort divide step.
begin | Begin iterator of subsequence. |
end | End iterator of subsequence. |
comp | Comparator. |
num_threads | Number of threads that are allowed to work on this part. |
(end-begin)>=1 Definition at line 100 of file balanced_quicksort.h.
References median_of_three_iterators(), parallel_partition(), and std::swap().
Referenced by qsb_conquer().
void __gnu_parallel::qsb_local_sort_with_helping | ( | QSBThreadLocal< RandomAccessIterator > ** | tls, |
Comparator & | comp, | ||
int | iam, | ||
bool | wait | ||
) |
Quicksort step doing load-balanced local sort.
tls | Array of thread-local storages. |
comp | Comparator. |
iam | Number of the thread processing this function. |
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::_Settings::sort_qsb_base_case_maximal_n, std::swap(), and yield().
Referenced by qsb_conquer().
|
inline |
Generate a random number in [0,2^logp).
logp | Logarithm (basis 2) of the upper range bound. |
rng | Random number generator to use. |
Definition at line 115 of file random_shuffle.h.
Referenced by parallel_random_shuffle_drs_pu(), and sequential_random_shuffle().
T __gnu_parallel::round_up_to_pow2 | ( | T | x | ) |
Round up to the next greater power of 2.
x | Integer to round up |
Definition at line 241 of file random_shuffle.h.
References __log2().
Referenced by parallel_random_shuffle_drs(), and sequential_random_shuffle().
_RandomAccessIterator1 __gnu_parallel::search_template | ( | _RandomAccessIterator1 | begin1, |
_RandomAccessIterator1 | end1, | ||
_RandomAccessIterator2 | begin2, | ||
_RandomAccessIterator2 | end2, | ||
Pred | pred | ||
) |
Parallel std::search.
begin1 | Begin iterator of first sequence. |
end1 | End iterator of first sequence. |
begin2 | Begin iterator of second sequence. |
end2 | End iterator of second sequence. |
pred | Find predicate. |
Definition at line 82 of file search.h.
References _GLIBCXX_CALL, calc_borders(), equally_split(), and std::min().
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 | ||
) |
Sequential multi-way merging switch.
The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings.
seqs_begin | Begin iterator of iterator pair input sequence. |
seqs_end | End iterator of iterator pair input sequence. |
target | Begin iterator out output sequence. |
comp | Comparator. |
length | Maximum length to merge, possibly larger than the number of elements available. |
stable | Stable merging incurs a performance penalty. |
sentinel | The sequences have a sentinel element. |
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().
void __gnu_parallel::sequential_random_shuffle | ( | RandomAccessIterator | begin, |
RandomAccessIterator | end, | ||
RandomNumberGenerator & | rng | ||
) |
Sequential cache-efficient random shuffle.
begin | Begin iterator of sequence. |
end | End iterator of sequence. |
rng | Random number generator to use. |
Definition at line 394 of file random_shuffle.h.
References __log2(), __gnu_parallel::_Settings::get(), __gnu_parallel::_Settings::L2_cache_size, std::min(), std::partial_sum(), random_number_pow2(), round_up_to_pow2(), and __gnu_parallel::_Settings::TLB_size.
Referenced by parallel_random_shuffle_drs().
void __gnu_parallel::shrink | ( | std::vector< InputIterator > & | os_starts, |
size_t & | count_to_two, | ||
size_t & | range_length | ||
) |
Combines two ranges into one and thus halves the number of ranges.
os_starts | Start positions worked on (oversampled). |
count_to_two | Counts up to 2. |
range_length | Current length of a chunk. |
Definition at line 70 of file list_partition.h.
References std::vector< _Tp, _Alloc >::size().
Referenced by shrink_and_double().
void __gnu_parallel::shrink_and_double | ( | std::vector< InputIterator > & | os_starts, |
size_t & | count_to_two, | ||
size_t & | range_length, | ||
const bool | make_twice | ||
) |
Shrinks and doubles the ranges.
os_starts | Start positions worked on (oversampled). |
count_to_two | Counts up to 2. |
range_length | Current length of a chunk. |
make_twice | Whether the os_starts is allowed to be grown or not |
Definition at line 50 of file list_partition.h.
References std::vector< _Tp, _Alloc >::resize(), shrink(), and std::vector< _Tp, _Alloc >::size().
Referenced by list_partition().
|
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().
|
static |