|
GNU g++
v5.2.1
GNU Standard C++
|
|
|
GNU g++
v5.2.1
GNU Standard C++
|
|
GNU parallel code for public use. More...
Classes | |
| struct | __accumulate_binop_reduct |
| General reduction, using a binary operator. More... | |
| struct | __accumulate_selector |
| std::accumulate() selector. More... | |
| struct | __adjacent_difference_selector |
| Selector that returns the difference between two adjacent __elements. More... | |
| struct | __adjacent_find_selector |
| Test predicate on two adjacent elements. More... | |
| class | __binder1st |
| Similar to std::binder1st, but giving the argument types explicitly. More... | |
| class | __binder2nd |
| Similar to std::binder2nd, but giving the argument types explicitly. More... | |
| struct | __count_if_selector |
| std::count_if () selector. More... | |
| struct | __count_selector |
| std::count() selector. More... | |
| struct | __difference_func |
| struct | __fill_selector |
| std::fill() selector. More... | |
| struct | __find_first_of_selector |
| Test predicate on several elements. More... | |
| struct | __find_if_selector |
| Test predicate on a single element, used for std::find() and std::find_if (). More... | |
| struct | __for_each_selector |
| std::for_each() selector. More... | |
| struct | __generate_selector |
| std::generate() selector. More... | |
| struct | __generic_find_selector |
| Base class of all __gnu_parallel::__find_template selectors. More... | |
| struct | __generic_for_each_selector |
| Generic __selector for embarrassingly parallel functions. More... | |
| struct | __identity_selector |
| Selector that just returns the passed iterator. More... | |
| struct | __inner_product_selector |
| std::inner_product() selector. More... | |
| struct | __intersection_func |
| struct | __max_element_reduct |
| Reduction for finding the maximum element, using a comparator. More... | |
| struct | __min_element_reduct |
| Reduction for finding the maximum element, using a comparator. More... | |
| struct | __mismatch_selector |
| Test inverted predicate on a single element. More... | |
| struct | __multiway_merge_3_variant_sentinel_switch |
| Switch for 3-way merging with __sentinels turned off. More... | |
| struct | __multiway_merge_3_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare > |
| Switch for 3-way merging with __sentinels turned on. More... | |
| struct | __multiway_merge_4_variant_sentinel_switch |
| Switch for 4-way merging with __sentinels turned off. More... | |
| struct | __multiway_merge_4_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare > |
| Switch for 4-way merging with __sentinels turned on. More... | |
| struct | __multiway_merge_k_variant_sentinel_switch |
| Switch for k-way merging with __sentinels turned on. More... | |
| struct | __multiway_merge_k_variant_sentinel_switch< false, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare > |
| Switch for k-way merging with __sentinels turned off. More... | |
| struct | __possibly_stable_multiway_merge |
| struct | __possibly_stable_multiway_merge< false, Seq_RAIter, _RAIter, _Compare, _DiffType > |
| struct | __possibly_stable_multiway_merge< true, Seq_RAIter, _RAIter, _Compare, _DiffType > |
| struct | __possibly_stable_sort |
| struct | __possibly_stable_sort< false, _RAIter, _Compare > |
| struct | __possibly_stable_sort< true, _RAIter, _Compare > |
| struct | __replace_if_selector |
| std::replace() selector. More... | |
| struct | __replace_selector |
| std::replace() selector. More... | |
| struct | __symmetric_difference_func |
| struct | __transform1_selector |
| std::transform() __selector, one input sequence variant. More... | |
| struct | __transform2_selector |
| std::transform() __selector, two input sequences variant. More... | |
| class | __unary_negate |
| Similar to std::unary_negate, but giving the argument types explicitly. More... | |
| struct | __union_func |
| struct | _DRandomShufflingGlobalData |
| Data known to every thread participating in __gnu_parallel::__parallel_random_shuffle(). More... | |
| struct | _DRSSorterPU |
| Local data for a thread participating in __gnu_parallel::__parallel_random_shuffle(). More... | |
| struct | _DummyReduct |
| Reduction function doing nothing. More... | |
| class | _EqualFromLess |
| Constructs predicate for equality from strict weak ordering predicate. More... | |
| struct | _EqualTo |
| Similar to std::equal_to, but allows two different types. More... | |
| class | _GuardedIterator |
| _Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. More... | |
| class | _IteratorPair |
| A pair of iterators. More... | |
| class | _IteratorTriple |
| A triple of iterators. More... | |
| struct | _Job |
| One __job for a certain thread. More... | |
| struct | _Less |
| Similar to std::less, but allows two different types. More... | |
| struct | _Less< _Tp, _Tp > |
| class | _Lexicographic |
| Compare __a pair of types lexicographically, ascending. More... | |
| class | _LexicographicReverse |
| Compare __a pair of types lexicographically, descending. More... | |
| class | _LoserTree |
| Stable _LoserTree variant. More... | |
| class | _LoserTree< false, _Tp, _Compare > |
| Unstable _LoserTree variant. More... | |
| class | _LoserTreeBase |
| Guarded loser/tournament tree. More... | |
| class | _LoserTreePointer |
| Stable _LoserTree implementation. More... | |
| class | _LoserTreePointer< false, _Tp, _Compare > |
| Unstable _LoserTree implementation. More... | |
| class | _LoserTreePointerBase |
| Base class of _Loser Tree implementation using pointers. More... | |
| class | _LoserTreePointerUnguarded |
| Stable unguarded _LoserTree variant storing pointers. More... | |
| class | _LoserTreePointerUnguarded< false, _Tp, _Compare > |
| Unstable unguarded _LoserTree variant storing pointers. More... | |
| class | _LoserTreePointerUnguardedBase |
| Unguarded loser tree, keeping only pointers to the elements in the tree structure. More... | |
| struct | _LoserTreeTraits |
| Traits for determining whether the loser tree should use pointers or copies. More... | |
| class | _LoserTreeUnguarded |
| Stable implementation of unguarded _LoserTree. More... | |
| class | _LoserTreeUnguarded< false, _Tp, _Compare > |
| Non-Stable implementation of unguarded _LoserTree. More... | |
| class | _LoserTreeUnguardedBase |
| Base class for unguarded _LoserTree implementation. More... | |
| struct | _Multiplies |
| Similar to std::multiplies, but allows two different types. More... | |
| struct | _Multiplies< _Tp, _Tp, _Tp > |
| struct | _Nothing |
| Functor doing nothing. More... | |
| struct | _Piece |
| Subsequence description. More... | |
| struct | _Plus |
| Similar to std::plus, but allows two different types. More... | |
| struct | _Plus< _Tp, _Tp, _Tp > |
| struct | _PMWMSSortingData |
| Data accessed by all threads. More... | |
| class | _PseudoSequence |
| Sequence that conceptually consists of multiple copies of the same element. More... | |
| class | _PseudoSequenceIterator |
| _Iterator associated with __gnu_parallel::_PseudoSequence. More... | |
| struct | _QSBThreadLocal |
| Information local to one thread in the parallel quicksort run. More... | |
| class | _RandomNumber |
| Random number generator, based on the Mersenne twister. More... | |
| class | _RestrictedBoundedConcurrentQueue |
| Double-ended queue of bounded size, allowing lock-free atomic access. More... | |
| struct | _SamplingSorter |
| Stable sorting functor. More... | |
| struct | _SamplingSorter< false, _RAIter, _StrictWeakOrdering > |
| Non-__stable sorting functor. More... | |
| struct | _Settings |
| class _Settings Run-time settings for the parallel mode including all tunable parameters. More... | |
| struct | _SplitConsistently |
| Split consistently. More... | |
| struct | _SplitConsistently< false, _RAIter, _Compare, _SortingPlacesIterator > |
| Split by sampling. More... | |
| struct | _SplitConsistently< true, _RAIter, _Compare, _SortingPlacesIterator > |
| Split by exact splitting. More... | |
| class | _UnguardedIterator |
| struct | balanced_quicksort_tag |
| Forces parallel sorting using balanced quicksort at compile time. More... | |
| struct | balanced_tag |
| Recommends parallel execution using dynamic load-balancing at compile time. More... | |
| struct | constant_size_blocks_tag |
| Selects the constant block size variant for std::find(). More... | |
| struct | default_parallel_tag |
| Recommends parallel execution using the default parallel algorithm. More... | |
| struct | equal_split_tag |
| Selects the equal splitting variant for std::find(). More... | |
| struct | exact_tag |
| Forces parallel merging with exact splitting, at compile time. More... | |
| struct | find_tag |
| Base class for for std::find() variants. More... | |
| struct | growing_blocks_tag |
| Selects the growing block size variant for std::find(). More... | |
| struct | multiway_mergesort_exact_tag |
| Forces parallel sorting using multiway mergesort with exact splitting at compile time. More... | |
| struct | multiway_mergesort_sampling_tag |
| Forces parallel sorting using multiway mergesort with splitting by sampling at compile time. More... | |
| struct | multiway_mergesort_tag |
| Forces parallel sorting using multiway mergesort at compile time. More... | |
| struct | omp_loop_static_tag |
| Recommends parallel execution using OpenMP static load-balancing at compile time. More... | |
| struct | omp_loop_tag |
| Recommends parallel execution using OpenMP dynamic load-balancing at compile time. More... | |
| struct | parallel_tag |
| Recommends parallel execution at compile time, optionally using a user-specified number of threads. More... | |
| struct | quicksort_tag |
| Forces parallel sorting using unbalanced quicksort at compile time. More... | |
| struct | sampling_tag |
| Forces parallel merging with exact splitting, at compile time. More... | |
| struct | sequential_tag |
| Forces sequential execution at compile time. More... | |
| struct | unbalanced_tag |
| Recommends parallel execution using static load-balancing at compile time. More... | |
Typedefs | |
| typedef unsigned short | _BinIndex |
| Type to hold the index of a bin. More... | |
| typedef int64_t | _CASable |
| Longest compare-and-swappable integer type on this platform. More... | |
| typedef uint64_t | _SequenceIndex |
| Unsigned integer to index __elements. More... | |
| typedef uint16_t | _ThreadIndex |
| Unsigned integer to index a thread number. More... | |
Enumerations | |
| enum | _AlgorithmStrategy { heuristic, force_sequential, force_parallel } |
| Strategies for run-time algorithm selection: More... | |
| enum | _FindAlgorithm { GROWING_BLOCKS, CONSTANT_SIZE_BLOCKS, EQUAL_SPLIT } |
| Find algorithms: More... | |
| enum | _MultiwayMergeAlgorithm { LOSER_TREE } |
| Merging algorithms: More... | |
| enum | _Parallelism { sequential, parallel_unbalanced, parallel_balanced, parallel_omp_loop, parallel_omp_loop_static, parallel_taskqueue } |
| Run-time equivalents for the compile-time tags. More... | |
| enum | _PartialSumAlgorithm { RECURSIVE, LINEAR } |
| Partial sum algorithms: recursive, linear. More... | |
| enum | _SortAlgorithm { MWMS, QS, QS_BALANCED } |
| Sorting algorithms: More... | |
| enum | _SplittingAlgorithm { SAMPLING, EXACT } |
| Sorting/merging algorithms: sampling, __exact. More... | |
Functions | |
| template<typename _Tp > | |
| _Tp | __add_omp (volatile _Tp *__ptr, _Tp __addend) |
| template<typename _RAIter , typename _DifferenceTp > | |
| void | __calc_borders (_RAIter __elements, _DifferenceTp __length, _DifferenceTp *__off) |
| Precalculate __advances for Knuth-Morris-Pratt algorithm. More... | |
| template<typename _Tp > | |
| bool | __cas_omp (volatile _Tp *__ptr, _Tp __comparand, _Tp __replacement) |
| template<typename _Tp > | |
| bool | __compare_and_swap (volatile _Tp *__ptr, _Tp __comparand, _Tp __replacement) |
| Compare-and-swap. More... | |
| template<typename _IIter , typename _OutputIterator > | |
| _OutputIterator | __copy_tail (std::pair< _IIter, _IIter > __b, std::pair< _IIter, _IIter > __e, _OutputIterator __r) |
| void | __decode2 (_CASable __x, int &__a, int &__b) |
| Decode two integers from one gnu_parallel::_CASable. More... | |
| template<typename _RAIter , typename _DifferenceTp > | |
| void | __determine_samples (_PMWMSSortingData< _RAIter > *__sd, _DifferenceTp __num_samples) |
| Select _M_samples from a sequence. More... | |
| _CASable | __encode2 (int __a, int __b) |
| Encode two integers into one gnu_parallel::_CASable. More... | |
| template<typename _DifferenceType , typename _OutputIterator > | |
| _OutputIterator | __equally_split (_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s) |
| function to split a sequence into parts of almost equal size. More... | |
| template<typename _DifferenceType > | |
| _DifferenceType | __equally_split_point (_DifferenceType __n, _ThreadIndex __num_threads, _ThreadIndex __thread_no) |
| function to split a sequence into parts of almost equal size. More... | |
| template<typename _Tp > | |
| _Tp | __fetch_and_add (volatile _Tp *__ptr, _Tp __addend) |
| Add a value to a variable, atomically. More... | |
| template<typename _RAIter1 , typename _RAIter2 , typename _Pred , typename _Selector > | |
| std::pair< _RAIter1, _RAIter2 > | __find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector) |
| Parallel std::find, switch for different algorithms. More... | |
| template<typename _IIter , typename _UserOp , typename _Functionality , typename _Red , typename _Result > | |
| _UserOp | __for_each_template_random_access (_IIter __begin, _IIter __end, _UserOp __user_op, _Functionality &__functionality, _Red __reduction, _Result __reduction_start, _Result &__output, typename std::iterator_traits< _IIter >::difference_type __bound, _Parallelism __parallelism_tag) |
Chose the desired algorithm by evaluating __parallelism_tag. More... | |
| template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > | |
| _Op | __for_each_template_random_access_ed (_RAIter __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound) |
| Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work. More... | |
| template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > | |
| _Op | __for_each_template_random_access_omp_loop (_RAIter __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound) |
| Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop. More... | |
| template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > | |
| _Op | __for_each_template_random_access_omp_loop_static (_RAIter __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound) |
| Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling. More... | |
| template<typename _RAIter , typename _Op , typename _Fu , typename _Red , typename _Result > | |
| _Op | __for_each_template_random_access_workstealing (_RAIter __begin, _RAIter __end, _Op __op, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound) |
| Work stealing algorithm for random access iterators. More... | |
| _ThreadIndex | __get_max_threads () |
| bool | __is_parallel (const _Parallelism __p) |
| template<typename _IIter , typename _Compare > | |
| bool | __is_sorted (_IIter __begin, _IIter __end, _Compare __comp) |
Check whether __end) is sorted according to __comp. More... | |
| template<typename _RAIter , typename _Compare > | |
| _RAIter | __median_of_three_iterators (_RAIter __a, _RAIter __b, _RAIter __c, _Compare __comp) |
Compute the median of three referenced elements, according to __comp. More... | |
| template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare > | |
| _OutputIterator | __merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp) |
Merge routine being able to merge only the __max_length smallest elements. More... | |
| template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare > | |
| _OutputIterator | __merge_advance_movc (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp) |
Merge routine being able to merge only the __max_length smallest elements. More... | |
| template<typename _RAIter1 , typename _RAIter2 , typename _OutputIterator , typename _DifferenceTp , typename _Compare > | |
| _OutputIterator | __merge_advance_usual (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp) |
Merge routine being able to merge only the __max_length smallest elements. More... | |
| template<typename _RAIter1 , typename _RAIter2 , typename _RAIter3 , typename _Compare > | |
| _RAIter3 | __parallel_merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp) |
| Merge routine fallback to sequential in case the iterators of the two input sequences are of different type. More... | |
| template<typename _RAIter1 , typename _RAIter3 , typename _Compare > | |
| _RAIter3 | __parallel_merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter1 &__begin2, _RAIter1 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp) |
Parallel merge routine being able to merge only the __max_length smallest elements. More... | |
| template<typename _RAIter , typename _Compare > | |
| void | __parallel_nth_element (_RAIter __begin, _RAIter __nth, _RAIter __end, _Compare __comp) |
| Parallel implementation of std::nth_element(). More... | |
| template<typename _RAIter , typename _Compare > | |
| void | __parallel_partial_sort (_RAIter __begin, _RAIter __middle, _RAIter __end, _Compare __comp) |
| Parallel implementation of std::partial_sort(). More... | |
| template<typename _IIter , typename _OutputIterator , typename _BinaryOperation > | |
| _OutputIterator | __parallel_partial_sum (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op) |
| Parallel partial sum front-__end. More... | |
| template<typename _IIter , typename _OutputIterator , typename _BinaryOperation > | |
| _OutputIterator | __parallel_partial_sum_basecase (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op, typename std::iterator_traits< _IIter >::value_type __value) |
| Base case prefix sum routine. More... | |
| template<typename _IIter , typename _OutputIterator , typename _BinaryOperation > | |
| _OutputIterator | __parallel_partial_sum_linear (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op, typename std::iterator_traits< _IIter >::difference_type __n) |
| Parallel partial sum implementation, two-phase approach, no recursion. More... | |
| template<typename _RAIter , typename _Predicate > | |
| std::iterator_traits< _RAIter >::difference_type | __parallel_partition (_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads) |
| Parallel implementation of std::partition. More... | |
| template<typename _RAIter , typename _RandomNumberGenerator > | |
| void | __parallel_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng=_RandomNumber()) |
| Parallel random public call. More... | |
| template<typename _RAIter , typename _RandomNumberGenerator > | |
| void | __parallel_random_shuffle_drs (_RAIter __begin, _RAIter __end, typename std::iterator_traits< _RAIter >::difference_type __n, _ThreadIndex __num_threads, _RandomNumberGenerator &__rng) |
| Main parallel random shuffle step. More... | |
| template<typename _RAIter , typename _RandomNumberGenerator > | |
| void | __parallel_random_shuffle_drs_pu (_DRSSorterPU< _RAIter, _RandomNumberGenerator > *__pus) |
| Random shuffle code executed by each thread. More... | |
| template<typename _IIter , typename _OutputIterator , typename _Compare > | |
| _OutputIterator | __parallel_set_difference (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp) |
| template<typename _IIter , typename _OutputIterator , typename _Compare > | |
| _OutputIterator | __parallel_set_intersection (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp) |
| template<typename _IIter , typename _OutputIterator , typename _Operation > | |
| _OutputIterator | __parallel_set_operation (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Operation __op) |
| template<typename _IIter , typename _OutputIterator , typename _Compare > | |
| _OutputIterator | __parallel_set_symmetric_difference (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp) |
| template<typename _IIter , typename _OutputIterator , typename _Compare > | |
| _OutputIterator | __parallel_set_union (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp) |
| template<bool __stable, typename _RAIter , typename _Compare , typename _Parallelism > | |
| void | __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, _Parallelism __parallelism) |
| template<bool __stable, typename _RAIter , typename _Compare > | |
| void | __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_tag __parallelism) |
| Choose multiway mergesort, splitting variant at run-time, for parallel sorting. More... | |
| template<bool __stable, typename _RAIter , typename _Compare > | |
| void | __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_exact_tag __parallelism) |
| Choose multiway mergesort with exact splitting, for parallel sorting. More... | |
| template<bool __stable, typename _RAIter , typename _Compare > | |
| void | __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_sampling_tag __parallelism) |
| Choose multiway mergesort with splitting by sampling, for parallel sorting. More... | |
| template<bool __stable, typename _RAIter , typename _Compare > | |
| void | __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, quicksort_tag __parallelism) |
| Choose quicksort for parallel sorting. More... | |
| template<bool __stable, typename _RAIter , typename _Compare > | |
| void | __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, balanced_quicksort_tag __parallelism) |
| Choose balanced quicksort for parallel sorting. More... | |
| template<bool __stable, typename _RAIter , typename _Compare > | |
| void | __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, default_parallel_tag __parallelism) |
| Choose multiway mergesort with exact splitting, for parallel sorting. More... | |
| template<bool __stable, typename _RAIter , typename _Compare > | |
| void | __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, parallel_tag __parallelism) |
| Choose a parallel sorting algorithm. More... | |
| template<typename _RAIter , typename _Compare > | |
| void | __parallel_sort_qs (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads) |
| Unbalanced quicksort main call. More... | |
| template<typename _RAIter , typename _Compare > | |
| void | __parallel_sort_qs_conquer (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads) |
| Unbalanced quicksort conquer step. More... | |
| template<typename _RAIter , typename _Compare > | |
| std::iterator_traits< _RAIter >::difference_type | __parallel_sort_qs_divide (_RAIter __begin, _RAIter __end, _Compare __comp, typename std::iterator_traits< _RAIter >::difference_type __pivot_rank, typename std::iterator_traits< _RAIter >::difference_type __num_samples, _ThreadIndex __num_threads) |
| Unbalanced quicksort divide step. More... | |
| template<typename _RAIter , typename _Compare > | |
| void | __parallel_sort_qsb (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads) |
| Top-level quicksort routine. More... | |
| template<typename _IIter , class _OutputIterator , class _BinaryPredicate > | |
| _OutputIterator | __parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result, _BinaryPredicate __binary_pred) |
| Parallel std::unique_copy(), w/__o explicit equality predicate. More... | |
| template<typename _IIter , class _OutputIterator > | |
| _OutputIterator | __parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result) |
| Parallel std::unique_copy(), without explicit equality predicate. More... | |
| template<typename _RAIter , typename _Compare > | |
| void | __qsb_conquer (_QSBThreadLocal< _RAIter > **__tls, _RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __iam, _ThreadIndex __num_threads, bool __parent_wait) |
| Quicksort conquer step. More... | |
| template<typename _RAIter , typename _Compare > | |
| std::iterator_traits< _RAIter >::difference_type | __qsb_divide (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads) |
| Balanced quicksort divide step. More... | |
| template<typename _RAIter , typename _Compare > | |
| void | __qsb_local_sort_with_helping (_QSBThreadLocal< _RAIter > **__tls, _Compare &__comp, _ThreadIndex __iam, bool __wait) |
| Quicksort step doing load-balanced local sort. More... | |
| template<typename _RandomNumberGenerator > | |
| int | __random_number_pow2 (int __logp, _RandomNumberGenerator &__rng) |
Generate a random number in | |
| template<typename _Size > | |
| _Size | __rd_log2 (_Size __n) |
Calculates the rounded-down logarithm of __n for base 2. More... | |
| template<typename _Tp > | |
| _Tp | __round_up_to_pow2 (_Tp __x) |
| Round up to the next greater power of 2. More... | |
| template<typename __RAIter1 , typename __RAIter2 , typename _Pred > | |
| __RAIter1 | __search_template (__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred) |
| Parallel std::search. More... | |
| template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > | |
| _RAIter3 | __sequential_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp) |
| Sequential multi-way merging switch. More... | |
| template<typename _RAIter , typename _RandomNumberGenerator > | |
| void | __sequential_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng) |
| Sequential cache-efficient random shuffle. More... | |
| template<typename _IIter > | |
| void | __shrink (std::vector< _IIter > &__os_starts, size_t &__count_to_two, size_t &__range_length) |
| Combines two ranges into one and thus halves the number of ranges. More... | |
| template<typename _IIter > | |
| void | __shrink_and_double (std::vector< _IIter > &__os_starts, size_t &__count_to_two, size_t &__range_length, const bool __make_twice) |
| Shrinks and doubles the ranges. More... | |
| void | __yield () |
| Yield control to another thread, without waiting for the end of the time slice. More... | |
| template<typename _IIter , typename _FunctorType > | |
| size_t | list_partition (const _IIter __begin, const _IIter __end, _IIter *__starts, size_t *__lengths, const int __num_parts, _FunctorType &__f, int __oversampling=0) |
| Splits a sequence given by input iterators into parts of almost equal size. More... | |
| template<typename _Tp > | |
| const _Tp & | max (const _Tp &__a, const _Tp &__b) |
| Equivalent to std::max. More... | |
| template<typename _Tp > | |
| const _Tp & | min (const _Tp &__a, const _Tp &__b) |
| Equivalent to std::min. More... | |
| template<typename _RanSeqs , typename _RankType , typename _RankIterator , typename _Compare > | |
| void | multiseq_partition (_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankIterator __begin_offsets, _Compare __comp=std::less< typename std::iterator_traits< typename std::iterator_traits< _RanSeqs >::value_type::first_type >::value_type >()) |
| Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each sequence. More... | |
| template<typename _Tp , typename _RanSeqs , typename _RankType , typename _Compare > | |
| _Tp | multiseq_selection (_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankType &__offset, _Compare __comp=std::less< _Tp >()) |
| Selects the element at a certain global __rank from several sorted sequences. More... | |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag) |
| Multiway Merge Frontend. More... | |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sampling_tag __tag) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0)) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag) |
| template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > | |
| _RAIter3 | multiway_merge_3_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp) |
| Highly efficient 3-way merging procedure. More... | |
| template<template< typename RAI, typename C > class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > | |
| _RAIter3 | multiway_merge_4_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp) |
| Highly efficient 4-way merging procedure. More... | |
| template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType > | |
| void | multiway_merge_exact_splitting (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces) |
| Exact splitting for parallel multiway-merge routine. More... | |
| template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > | |
| _RAIter3 | multiway_merge_loser_tree (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp) |
| Multi-way merging procedure for a high branching factor, guarded case. More... | |
| template<typename UnguardedLoserTree , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > | |
| _RAIter3 | multiway_merge_loser_tree_sentinel (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp) |
| Multi-way merging procedure for a high branching factor, requiring sentinels to exist. More... | |
| template<typename _LT , typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > | |
| _RAIter3 | multiway_merge_loser_tree_unguarded (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp) |
| Multi-way merging procedure for a high branching factor, unguarded case. More... | |
| template<bool __stable, typename _RAIterIterator , typename _Compare , typename _DifferenceType > | |
| void | multiway_merge_sampling_splitting (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces) |
| Sampling based splitting for parallel multiway-merge routine. More... | |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag) |
| Multiway Merge Frontend. More... | |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0)) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag) |
| template<bool __stable, bool __sentinels, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Splitter , typename _Compare > | |
| _RAIter3 | parallel_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _Splitter __splitter, _DifferenceTp __length, _Compare __comp, _ThreadIndex __num_threads) |
| Parallel multi-way merge routine. More... | |
| template<bool __stable, bool __exact, typename _RAIter , typename _Compare > | |
| void | parallel_sort_mwms (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads) |
| PMWMS main call. More... | |
| template<bool __stable, bool __exact, typename _RAIter , typename _Compare > | |
| void | parallel_sort_mwms_pu (_PMWMSSortingData< _RAIter > *__sd, _Compare &__comp) |
| PMWMS code executed by each thread. More... | |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0)) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0)) |
| template<typename _RAIterPairIterator , typename _RAIterOut , typename _DifferenceTp , typename _Compare > | |
| _RAIterOut | stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag) |
Variables | |
| static const int | _CASable_bits = std::numeric_limits<_CASable>::digits |
| Number of bits of _CASable. More... | |
| static const _CASable | _CASable_mask |
| _CASable with the right half of bits set to 1. More... | |
GNU parallel code for public use.
| typedef unsigned short __gnu_parallel::_BinIndex |
Type to hold the index of a bin.
Since many variables of this type are allocated, it should be chosen as small as possible.
| typedef int64_t __gnu_parallel::_CASable |
Longest compare-and-swappable integer type on this platform.
| typedef uint64_t __gnu_parallel::_SequenceIndex |
Unsigned integer to index __elements.
The total number of elements for each algorithm must fit into this type.
| typedef uint16_t __gnu_parallel::_ThreadIndex |
Unsigned integer to index a thread number.
The maximum thread number (for each processor) must fit into this type.
Run-time equivalents for the compile-time tags.
|
inline |
| void __gnu_parallel::__calc_borders | ( | _RAIter | __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. |
| __off | Returned __offsets. |
Referenced by __search_template().
|
inline |
|
inline |
Compare-and-swap.
Compare *__ptr and __comparand. If equal, let *__ptr=__replacement and return true, return false otherwise.
| __ptr | Pointer to signed integer. |
| __comparand | Compare value. |
| __replacement | Replacement value. |
References __cas_omp().
Referenced by __parallel_partition(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_back(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_front().
| _OutputIterator __gnu_parallel::__copy_tail | ( | std::pair< _IIter, _IIter > | __b, |
| std::pair< _IIter, _IIter > | __e, | ||
| _OutputIterator | __r | ||
| ) |
|
inline |
Decode two integers from one gnu_parallel::_CASable.
| __x | __gnu_parallel::_CASable to decode integers from. |
| __a | First integer, to be decoded from the most-significant _CASable_bits/2 bits of __x. |
| __b | Second integer, to be encoded in the least-significant _CASable_bits/2 bits of __x. |
References _CASable_bits, and _CASable_mask.
Referenced by __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_back(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_front(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::push_front().
| void __gnu_parallel::__determine_samples | ( | _PMWMSSortingData< _RAIter > * | __sd, |
| _DifferenceTp | __num_samples | ||
| ) |
Select _M_samples from a sequence.
| __sd | Pointer to algorithm data. _Result will be placed in __sd->_M_samples. |
| __num_samples | Number of _M_samples to select. |
References __equally_split(), __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_samples, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, and __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts.
Referenced by __gnu_parallel::_SplitConsistently< false, _RAIter, _Compare, _SortingPlacesIterator >::operator()().
|
inline |
Encode two integers into one gnu_parallel::_CASable.
| __a | First integer, to be encoded in the most-significant _CASable_bits/2 bits. |
| __b | Second integer, to be encoded in the least-significant _CASable_bits/2 bits. |
__a and __b. References _CASable_bits.
Referenced by __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::_RestrictedBoundedConcurrentQueue(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_back(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::pop_front(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::push_front().
| _OutputIterator __gnu_parallel::__equally_split | ( | _DifferenceType | __n, |
| _ThreadIndex | __num_threads, | ||
| _OutputIterator | __s | ||
| ) |
function to split a sequence into parts of almost equal size.
The resulting sequence __s of length __num_threads+1 contains the splitting positions when splitting the range [0,__n) into parts of almost equal size (plus minus 1). The first entry is 0, the last one n. There may result empty parts.
| __n | Number of elements |
| __num_threads | Number of parts |
| __s | Splitters |
__s+__num_threads+1 Referenced by __determine_samples(), __parallel_partial_sum_linear(), __parallel_set_operation(), __parallel_unique_copy(), __search_template(), and multiway_merge_exact_splitting().
| _DifferenceType __gnu_parallel::__equally_split_point | ( | _DifferenceType | __n, |
| _ThreadIndex | __num_threads, | ||
| _ThreadIndex | __thread_no | ||
| ) |
function to split a sequence into parts of almost equal size.
Returns the position of the splitting point between thread number __thread_no (included) and thread number __thread_no+1 (excluded).
| __n | Number of elements |
| __num_threads | Number of parts |
| __thread_no | Number of threads |
Referenced by __for_each_template_random_access_ed().
|
inline |
Add a value to a variable, atomically.
| __ptr | Pointer to a signed integer. |
| __addend | Value to add. |
References __add_omp().
Referenced by __parallel_partition(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Piece >::push_front().
|
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(),...) |
References _GLIBCXX_PARALLEL_ASSERT, CONSTANT_SIZE_BLOCKS, EQUAL_SPLIT, __gnu_parallel::_Settings::get(), and GROWING_BLOCKS.
Referenced by _GLIBCXX_VISIBILITY().
| _UserOp __gnu_parallel::__for_each_template_random_access | ( | _IIter | __begin, |
| _IIter | __end, | ||
| _UserOp | __user_op, | ||
| _Functionality & | __functionality, | ||
| _Red | __reduction, | ||
| _Result | __reduction_start, | ||
| _Result & | __output, | ||
| typename std::iterator_traits< _IIter >::difference_type | __bound, | ||
| _Parallelism | __parallelism_tag | ||
| ) |
Chose the desired algorithm by evaluating __parallelism_tag.
| __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 |
References __for_each_template_random_access_ed(), __for_each_template_random_access_omp_loop(), __for_each_template_random_access_workstealing(), parallel_omp_loop, parallel_omp_loop_static, and parallel_unbalanced.
Referenced by _GLIBCXX_VISIBILITY().
| _Op __gnu_parallel::__for_each_template_random_access_ed | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Op | __o, | ||
| _Fu & | __f, | ||
| _Red | __r, | ||
| _Result | __base, | ||
| _Result & | __output, | ||
| typename std::iterator_traits< _RAIter >::difference_type | __bound | ||
| ) |
Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work.
| __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()). |
References __equally_split_point(), and __get_max_threads().
Referenced by __for_each_template_random_access().
| _Op __gnu_parallel::__for_each_template_random_access_omp_loop | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Op | __o, | ||
| _Fu & | __f, | ||
| _Red | __r, | ||
| _Result | __base, | ||
| _Result & | __output, | ||
| typename std::iterator_traits< _RAIter >::difference_type | __bound | ||
| ) |
Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop.
| __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()). |
References __get_max_threads().
Referenced by __for_each_template_random_access().
| _Op __gnu_parallel::__for_each_template_random_access_omp_loop_static | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Op | __o, | ||
| _Fu & | __f, | ||
| _Red | __r, | ||
| _Result | __base, | ||
| _Result & | __output, | ||
| typename std::iterator_traits< _RAIter >::difference_type | __bound | ||
| ) |
Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling.
| __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()). |
References __get_max_threads().
| _Op __gnu_parallel::__for_each_template_random_access_workstealing | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Op | __op, | ||
| _Fu & | __f, | ||
| _Red | __r, | ||
| _Result | __base, | ||
| _Result & | __output, | ||
| typename std::iterator_traits< _RAIter >::difference_type | __bound | ||
| ) |
Work stealing algorithm for random access iterators.
Uses O(1) additional memory. Synchronization at job lists is done with atomic operations.
| __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()). |
References __gnu_debug::__base(), __get_max_threads(), __yield(), _GLIBCXX_CALL, __gnu_parallel::_Job< _DifferenceTp >::_M_first, __gnu_parallel::_Job< _DifferenceTp >::_M_last, __gnu_parallel::_Job< _DifferenceTp >::_M_load, __gnu_parallel::_Settings::cache_line_size, __gnu_parallel::_Settings::get(), min(), and __gnu_parallel::_Settings::workstealing_chunk_size.
Referenced by __for_each_template_random_access().
|
inline |
Referenced by __for_each_template_random_access_ed(), __for_each_template_random_access_omp_loop(), __for_each_template_random_access_omp_loop_static(), __for_each_template_random_access_workstealing(), __parallel_nth_element(), __parallel_partial_sum_linear(), __parallel_random_shuffle(), __parallel_set_operation(), __parallel_unique_copy(), __search_template(), and _GLIBCXX_VISIBILITY().
|
inline |
References sequential.
Referenced by _GLIBCXX_VISIBILITY().
| bool __gnu_parallel::__is_sorted | ( | _IIter | __begin, |
| _IIter | __end, | ||
| _Compare | __comp | ||
| ) |
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. Referenced by __sequential_multiway_merge(), multiway_merge_loser_tree_sentinel(), and parallel_multiway_merge().
| _RAIter __gnu_parallel::__median_of_three_iterators | ( | _RAIter | __a, |
| _RAIter | __b, | ||
| _RAIter | __c, | ||
| _Compare | __comp | ||
| ) |
Compute the median of three referenced elements, according to __comp.
| __a | First iterator. |
| __b | Second iterator. |
| __c | Third iterator. |
| __comp | Comparator. |
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. |
References __merge_advance_movc(), and _GLIBCXX_CALL.
Referenced by __parallel_merge_advance(), __sequential_multiway_merge(), and _GLIBCXX_VISIBILITY().
| _OutputIterator __gnu_parallel::__merge_advance_movc | ( | _RAIter1 & | __begin1, |
| _RAIter1 | __end1, | ||
| _RAIter2 & | __begin2, | ||
| _RAIter2 | __end2, | ||
| _OutputIterator | __target, | ||
| _DifferenceTp | __max_length, | ||
| _Compare | __comp | ||
| ) |
Merge routine being able to merge only the __max_length smallest elements.
The __begin iterators are advanced accordingly, they might not reach __end, in contrast to the usual variant. Specially designed code should allow the compiler to generate conditional moves instead of branches.
| __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. |
References _GLIBCXX_PARALLEL_ASSERT.
Referenced by __merge_advance().
| _OutputIterator __gnu_parallel::__merge_advance_usual | ( | _RAIter1 & | __begin1, |
| _RAIter1 | __end1, | ||
| _RAIter2 & | __begin2, | ||
| _RAIter2 | __end2, | ||
| _OutputIterator | __target, | ||
| _DifferenceTp | __max_length, | ||
| _Compare | __comp | ||
| ) |
Merge routine being able to merge only the __max_length smallest elements.
The __begin iterators are advanced accordingly, they might not reach __end, in contrast to the usual variant.
| __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. |
|
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. |
References __merge_advance().
Referenced by _GLIBCXX_VISIBILITY().
|
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. |
References multiway_merge_exact_splitting(), and parallel_multiway_merge().
| void __gnu_parallel::__parallel_nth_element | ( | _RAIter | __begin, |
| _RAIter | __nth, | ||
| _RAIter | __end, | ||
| _Compare | __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. |
References __get_max_threads(), __parallel_partition(), _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), max(), __gnu_parallel::_Settings::nth_element_minimal_n, and __gnu_parallel::_Settings::partition_minimal_n.
Referenced by __parallel_partial_sort(), and _GLIBCXX_VISIBILITY().
| void __gnu_parallel::__parallel_partial_sort | ( | _RAIter | __begin, |
| _RAIter | __middle, | ||
| _RAIter | __end, | ||
| _Compare | __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. |
References __parallel_nth_element().
Referenced by _GLIBCXX_VISIBILITY().
| _OutputIterator __gnu_parallel::__parallel_partial_sum | ( | _IIter | __begin, |
| _IIter | __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. |
References __parallel_partial_sum_linear(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_ASSERT, __gnu_parallel::_Settings::get(), and LINEAR.
| _OutputIterator __gnu_parallel::__parallel_partial_sum_basecase | ( | _IIter | __begin, |
| _IIter | __end, | ||
| _OutputIterator | __result, | ||
| _BinaryOperation | __bin_op, | ||
| typename std::iterator_traits< _IIter >::value_type | __value | ||
| ) |
Base case prefix sum routine.
| __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. |
Referenced by __parallel_partial_sum_linear().
| _OutputIterator __gnu_parallel::__parallel_partial_sum_linear | ( | _IIter | __begin, |
| _IIter | __end, | ||
| _OutputIterator | __result, | ||
| _BinaryOperation | __bin_op, | ||
| typename std::iterator_traits< _IIter >::difference_type | __n | ||
| ) |
Parallel partial sum implementation, two-phase approach, no recursion.
| __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. |
References __equally_split(), __get_max_threads(), __parallel_partial_sum_basecase(), __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::partial_sum_dilation.
Referenced by __parallel_partial_sum().
| std::iterator_traits<_RAIter>::difference_type __gnu_parallel::__parallel_partition | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Predicate | __pred, | ||
| _ThreadIndex | __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. |
References __compare_and_swap(), __fetch_and_add(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_ASSERT, _GLIBCXX_VOLATILE, __gnu_parallel::_Settings::get(), __gnu_parallel::_Settings::partition_chunk_share, and __gnu_parallel::_Settings::partition_chunk_size.
Referenced by __parallel_nth_element(), __parallel_sort_qs_divide(), __qsb_divide(), and _GLIBCXX_VISIBILITY().
|
inline |
Parallel random public call.
| __begin | Begin iterator of sequence. |
| __end | End iterator of sequence. |
| __rng | Random number generator to use. |
References __get_max_threads(), and __parallel_random_shuffle_drs().
Referenced by _GLIBCXX_VISIBILITY().
| void __gnu_parallel::__parallel_random_shuffle_drs | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| typename std::iterator_traits< _RAIter >::difference_type | __n, | ||
| _ThreadIndex | __num_threads, | ||
| _RandomNumberGenerator & | __rng | ||
| ) |
Main parallel random shuffle step.
| __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. |
References __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::__bins_end, __parallel_random_shuffle_drs_pu(), __rd_log2(), __round_up_to_pow2(), __sequential_random_shuffle(), _GLIBCXX_CALL, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_bin_proc, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_bins_begin, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_dist, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bins, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bits, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_num_threads, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_sd, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_seed, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_starts, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_temporaries, __gnu_parallel::_Settings::get(), __gnu_parallel::_Settings::L2_cache_size, max(), min(), and __gnu_parallel::_Settings::TLB_size.
Referenced by __parallel_random_shuffle().
| void __gnu_parallel::__parallel_random_shuffle_drs_pu | ( | _DRSSorterPU< _RAIter, _RandomNumberGenerator > * | __pus | ) |
Random shuffle code executed by each thread.
| __pus | Array of thread-local data records. |
References __random_number_pow2(), __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_dist, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bins, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bits, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_num_threads, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_sd, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_seed, and __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_starts.
Referenced by __parallel_random_shuffle_drs().
|
inline |
References __parallel_set_operation().
Referenced by _GLIBCXX_VISIBILITY().
|
inline |
References __parallel_set_operation().
Referenced by _GLIBCXX_VISIBILITY().
| _OutputIterator __gnu_parallel::__parallel_set_operation | ( | _IIter | __begin1, |
| _IIter | __end1, | ||
| _IIter | __begin2, | ||
| _IIter | __end2, | ||
| _OutputIterator | __result, | ||
| _Operation | __op | ||
| ) |
References __equally_split(), __get_max_threads(), __gnu_profile::__size(), _GLIBCXX_CALL, min(), and multiseq_partition().
Referenced by __parallel_set_difference(), __parallel_set_intersection(), __parallel_set_symmetric_difference(), and __parallel_set_union().
|
inline |
References __parallel_set_operation().
Referenced by _GLIBCXX_VISIBILITY().
|
inline |
References __parallel_set_operation().
Referenced by _GLIBCXX_VISIBILITY().
| void __gnu_parallel::__parallel_sort | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Compare | __comp, | ||
| _Parallelism | __parallelism | ||
| ) |
|
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. |
| __stable | Sort stable. |
References __gnu_parallel::parallel_tag::__get_num_threads(), _GLIBCXX_CALL, EXACT, and __gnu_parallel::_Settings::get().
|
inline |
Choose multiway mergesort with exact splitting, for parallel sorting.
| __begin | Begin iterator of input sequence. |
| __end | End iterator of input sequence. |
| __comp | Comparator. |
| __stable | Sort stable. |
References __gnu_parallel::parallel_tag::__get_num_threads(), and _GLIBCXX_CALL.
|
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. |
| __stable | Sort stable. |
References __gnu_parallel::parallel_tag::__get_num_threads(), and _GLIBCXX_CALL.
|
inline |
Choose quicksort for parallel sorting.
| __begin | Begin iterator of input sequence. |
| __end | End iterator of input sequence. |
| __comp | Comparator. |
| __stable | Sort stable. |
References __gnu_parallel::parallel_tag::__get_num_threads(), __parallel_sort_qs(), _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_ASSERT.
|
inline |
Choose balanced quicksort for parallel sorting.
| __begin | Begin iterator of input sequence. |
| __end | End iterator of input sequence. |
| __comp | Comparator. |
| __stable | Sort stable. |
References __gnu_parallel::parallel_tag::__get_num_threads(), __parallel_sort_qsb(), _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_ASSERT.
|
inline |
Choose multiway mergesort with exact splitting, for parallel sorting.
| __begin | Begin iterator of input sequence. |
| __end | End iterator of input sequence. |
| __comp | Comparator. |
| __stable | Sort stable. |
References __gnu_parallel::parallel_tag::__get_num_threads(), and _GLIBCXX_CALL.
|
inline |
Choose a parallel sorting algorithm.
| __begin | Begin iterator of input sequence. |
| __end | End iterator of input sequence. |
| __comp | Comparator. |
| __stable | Sort stable. |
References __gnu_parallel::parallel_tag::__get_num_threads(), __parallel_sort_qs(), __parallel_sort_qsb(), _GLIBCXX_CALL, EXACT, __gnu_parallel::_Settings::get(), MWMS, QS, QS_BALANCED, and __gnu_parallel::_Settings::sort_algorithm.
| void __gnu_parallel::__parallel_sort_qs | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Compare | __comp, | ||
| _ThreadIndex | __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. |
References __parallel_sort_qs_conquer(), and _GLIBCXX_CALL.
Referenced by __parallel_sort().
| void __gnu_parallel::__parallel_sort_qs_conquer | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Compare | __comp, | ||
| _ThreadIndex | __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. |
References __parallel_sort_qs_divide(), and __gnu_parallel::_Settings::get().
Referenced by __parallel_sort_qs().
| std::iterator_traits<_RAIter>::difference_type __gnu_parallel::__parallel_sort_qs_divide | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Compare | __comp, | ||
| typename std::iterator_traits< _RAIter >::difference_type | __pivot_rank, | ||
| typename std::iterator_traits< _RAIter >::difference_type | __num_samples, | ||
| _ThreadIndex | __num_threads | ||
| ) |
Unbalanced quicksort divide step.
| __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. |
References __parallel_partition(), and min().
Referenced by __parallel_sort_qs_conquer().
| void __gnu_parallel::__parallel_sort_qsb | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Compare | __comp, | ||
| _ThreadIndex | __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. |
References __qsb_conquer(), __rd_log2(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_ASSERT, and __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_elements_leftover.
Referenced by __parallel_sort().
| _OutputIterator __gnu_parallel::__parallel_unique_copy | ( | _IIter | __first, |
| _IIter | __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. |
References __equally_split(), __get_max_threads(), __gnu_profile::__size(), and _GLIBCXX_CALL.
Referenced by __parallel_unique_copy(), and _GLIBCXX_VISIBILITY().
|
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. |
References __parallel_unique_copy().
| void __gnu_parallel::__qsb_conquer | ( | _QSBThreadLocal< _RAIter > ** | __tls, |
| _RAIter | __begin, | ||
| _RAIter | __end, | ||
| _Compare | __comp, | ||
| _ThreadIndex | __iam, | ||
| _ThreadIndex | __num_threads, | ||
| bool | __parent_wait | ||
| ) |
Quicksort conquer step.
| __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. |
References __qsb_divide(), __qsb_local_sort_with_helping(), _GLIBCXX_PARALLEL_ASSERT, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_elements_leftover, and __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_initial.
Referenced by __parallel_sort_qsb().
| std::iterator_traits<_RAIter>::difference_type __gnu_parallel::__qsb_divide | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Compare | __comp, | ||
| _ThreadIndex | __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. |
References __median_of_three_iterators(), __parallel_partition(), and _GLIBCXX_PARALLEL_ASSERT.
Referenced by __qsb_conquer().
| void __gnu_parallel::__qsb_local_sort_with_helping | ( | _QSBThreadLocal< _RAIter > ** | __tls, |
| _Compare & | __comp, | ||
| _ThreadIndex | __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. |
References __yield(), _GLIBCXX_ASSERTIONS, _GLIBCXX_PARALLEL_ASSERT, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_elements_leftover, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_initial, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_leftover_parts, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_num_threads, __gnu_parallel::_Settings::get(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::pop_front(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::push_front(), and __gnu_parallel::_Settings::sort_qsb_base_case_maximal_n.
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. |
Referenced by __parallel_random_shuffle_drs_pu(), and __sequential_random_shuffle().
|
inline |
Calculates the rounded-down logarithm of __n for base 2.
| __n | Argument. |
Referenced by __parallel_random_shuffle_drs(), __parallel_sort_qsb(), __round_up_to_pow2(), __sequential_random_shuffle(), __gnu_parallel::_LoserTreeBase< _Tp, _Compare >::_LoserTreeBase(), __gnu_parallel::_LoserTreePointerBase< _Tp, _Compare >::_LoserTreePointerBase(), __gnu_parallel::_LoserTreePointerUnguardedBase< _Tp, _Compare >::_LoserTreePointerUnguardedBase(), __gnu_parallel::_LoserTreeUnguardedBase< _Tp, _Compare >::_LoserTreeUnguardedBase(), multiseq_partition(), and multiseq_selection().
| _Tp __gnu_parallel::__round_up_to_pow2 | ( | _Tp | __x | ) |
Round up to the next greater power of 2.
| __x | _Integer to round up |
References __rd_log2().
Referenced by __parallel_random_shuffle_drs(), __sequential_random_shuffle(), and multiseq_selection().
| __RAIter1 __gnu_parallel::__search_template | ( | __RAIter1 | __begin1, |
| __RAIter1 | __end1, | ||
| __RAIter2 | __begin2, | ||
| __RAIter2 | __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. |
References __calc_borders(), __equally_split(), __get_max_threads(), _GLIBCXX_CALL, and min().
Referenced by _GLIBCXX_VISIBILITY().
| _RAIter3 __gnu_parallel::__sequential_multiway_merge | ( | _RAIterIterator | __seqs_begin, |
| _RAIterIterator | __seqs_end, | ||
| _RAIter3 | __target, | ||
| const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type & | __sentinel, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp | ||
| ) |
Sequential multi-way merging switch.
The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings.
| __seqs_begin | Begin iterator of iterator pair input sequence. |
| __seqs_end | End iterator of iterator pair input sequence. |
| __target | Begin iterator of output sequence. |
| __comp | Comparator. |
| __length | Maximum length to merge, possibly larger than the number of elements available. |
| __sentinel | The sequences have __a __sentinel element. |
References __is_sorted(), __merge_advance(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_ASSERT, and _GLIBCXX_PARALLEL_LENGTH.
Referenced by multiway_merge(), multiway_merge_sentinels(), stable_multiway_merge(), and stable_multiway_merge_sentinels().
| void __gnu_parallel::__sequential_random_shuffle | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _RandomNumberGenerator & | __rng | ||
| ) |
Sequential cache-efficient random shuffle.
| __begin | Begin iterator of sequence. |
| __end | End iterator of sequence. |
| __rng | Random number generator to use. |
References __random_number_pow2(), __rd_log2(), __round_up_to_pow2(), __gnu_parallel::_Settings::get(), __gnu_parallel::_Settings::L2_cache_size, min(), and __gnu_parallel::_Settings::TLB_size.
Referenced by __parallel_random_shuffle_drs(), and _GLIBCXX_VISIBILITY().
| void __gnu_parallel::__shrink | ( | std::vector< _IIter > & | __os_starts, |
| size_t & | __count_to_two, | ||
| size_t & | __range_length | ||
| ) |
Combines two ranges into one and thus halves the number of ranges.
| __os_starts | Start positions worked on (oversampled). |
| __count_to_two | Counts up to 2. |
| __range_length | Current length of a chunk. |
Referenced by __shrink_and_double().
| void __gnu_parallel::__shrink_and_double | ( | std::vector< _IIter > & | __os_starts, |
| size_t & | __count_to_two, | ||
| size_t & | __range_length, | ||
| const bool | __make_twice | ||
| ) |
Shrinks and doubles the ranges.
| __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 |
References __shrink().
Referenced by list_partition().
|
inline |
Yield control to another thread, without waiting for the end of the time slice.
Referenced by __for_each_template_random_access_workstealing(), and __qsb_local_sort_with_helping().
| size_t __gnu_parallel::list_partition | ( | const _IIter | __begin, |
| const _IIter | __end, | ||
| _IIter * | __starts, | ||
| size_t * | __lengths, | ||
| const int | __num_parts, | ||
| _FunctorType & | __f, | ||
| int | __oversampling = 0 |
||
| ) |
Splits a sequence given by input iterators into parts of almost equal size.
The function needs only one pass over the sequence.
| __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 |
| __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  elements. Otherwise, the ratio between the longest and the shortest part is bounded by  |
References __shrink_and_double().
|
inline |
Equivalent to std::max.
Referenced by __gnu_profile::__hashfunc_info::__destruct(), __gnu_profile::__container_size_info::__destruct(), __gnu_profile::__hashfunc_info::__merge(), __gnu_profile::__list2vector_info::__merge(), __gnu_profile::__container_size_info::__merge(), __gnu_profile::__list2vector_info::__opr_insert(), __parallel_nth_element(), __parallel_random_shuffle_drs(), __gnu_profile::__container_size_info::__resize(), _GLIBCXX_VISIBILITY(), __gnu_pbds::detail::resize_policy< _Tp >::get_new_size_for_shrink(), multiseq_partition(), multiseq_selection(), __gnu_pbds::detail::resize_policy< _Tp >::notify_shrink_resize(), and __gnu_pbds::detail::rc< _Node, _Alloc >::swap().
|
inline |
Equivalent to std::min.
Referenced by __gnu_profile::__container_size_info::__destruct(), __for_each_template_random_access_workstealing(), __gnu_profile::__container_size_info::__merge(), __parallel_random_shuffle_drs(), __parallel_set_operation(), __parallel_sort_qs_divide(), __gnu_profile::__report(), __search_template(), __sequential_random_shuffle(), _GLIBCXX_VISIBILITY(), multiseq_partition(), and multiseq_selection().
| void __gnu_parallel::multiseq_partition | ( | _RanSeqs | __begin_seqs, |
| _RanSeqs | __end_seqs, | ||
| _RankType | __rank, | ||
| _RankIterator | __begin_offsets, | ||
| _Compare | __comp = std::less< typename std::iterator_traits<typename std::iterator_traits<_RanSeqs>::value_type:: first_type>::value_type>() |
||
| ) |
Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each sequence.
The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones on the __left side will be chosen from sequences with smaller number.
| __begin_seqs | Begin of the sequence of iterator pairs. |
| __end_seqs | End of the sequence of iterator pairs. |
| __rank | The global rank to partition at. |
| __begin_offsets | A random-access __sequence __begin where the __result will be stored in. Each element of the sequence is an iterator that points to the first element on the greater part of the respective __sequence. |
| __comp | The ordering functor, defaults to std::less<_Tp>. |
References __rd_log2(), __S, _GLIBCXX_CALL, _GLIBCXX_PARALLEL_ASSERT, max(), and min().
Referenced by __parallel_set_operation(), multiway_merge_exact_splitting(), and __gnu_parallel::_SplitConsistently< true, _RAIter, _Compare, _SortingPlacesIterator >::operator()().
| _Tp __gnu_parallel::multiseq_selection | ( | _RanSeqs | __begin_seqs, |
| _RanSeqs | __end_seqs, | ||
| _RankType | __rank, | ||
| _RankType & | __offset, | ||
| _Compare | __comp = std::less<_Tp>() |
||
| ) |
Selects the element at a certain global __rank from several sorted sequences.
The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty.
| __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. |
References __rd_log2(), __round_up_to_pow2(), __S, _GLIBCXX_CALL, max(), and min().
| _RAIterOut __gnu_parallel::multiway_merge | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| __gnu_parallel::sequential_tag | |||
| ) |
Multiway Merge Frontend.
Merge the sequences specified by seqs_begin and __seqs_end into __target. __seqs_begin and __seqs_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the _M_end of the same sequence in their second entry.
Ties are broken arbitrarily. See stable_multiway_merge for a variant that breaks ties by sequence number but is slower.
The first entries of the pairs (i.e. the begin iterators) will be moved forward.
The output sequence has to provide enough space for all elements that are written to it.
This function will merge the input sequences:
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);
| _RAIterPairIterator | iterator over sequence of pairs of iterators |
| _RAIterOut | iterator over target sequence |
| _DifferenceTp | difference type for the sequence |
| _Compare | strict weak ordering type to compare elements in sequences |
| __seqs_begin | __begin of sequence __sequence |
| __seqs_end | _M_end of sequence __sequence |
| __target | target sequence to merge to. |
| __comp | strict weak ordering to use for element comparison. |
| __length | Maximum length to merge, possibly larger than the number of elements available. |
References __sequential_multiway_merge(), and _GLIBCXX_CALL.
Referenced by multiway_merge(), and __gnu_parallel::__possibly_stable_multiway_merge< false, Seq_RAIter, _RAIter, _Compare, _DiffType >::operator()().
| _RAIterOut __gnu_parallel::multiway_merge | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| __gnu_parallel::exact_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), __sequential_multiway_merge(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_CONDITION, __gnu_parallel::_Settings::get(), multiway_merge_exact_splitting(), and parallel_multiway_merge().
| _RAIterOut __gnu_parallel::multiway_merge | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| __gnu_parallel::sampling_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), __sequential_multiway_merge(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_CONDITION, __gnu_parallel::_Settings::get(), multiway_merge_exact_splitting(), and parallel_multiway_merge().
| _RAIterOut __gnu_parallel::multiway_merge | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| parallel_tag | __tag = parallel_tag(0) |
||
| ) |
| _RAIterOut __gnu_parallel::multiway_merge | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| default_parallel_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), and multiway_merge().
| _RAIter3 __gnu_parallel::multiway_merge_3_variant | ( | _RAIterIterator | __seqs_begin, |
| _RAIterIterator | __seqs_end, | ||
| _RAIter3 | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp | ||
| ) |
Highly efficient 3-way merging procedure.
Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into labels in C++).
This works well for merging up to 4 sequences.
Note that making the merging stable does not come at a performance hit.
Whether the merging is done guarded or unguarded is selected by the used iterator class.
| __seqs_begin | Begin iterator of iterator pair input sequence. |
| __seqs_end | End iterator of iterator pair input sequence. |
| __target | Begin iterator of output sequence. |
| __comp | Comparator. |
| __length | Maximum length to merge, less equal than the total number of elements available. |
References _GLIBCXX_CALL, _GLIBCXX_PARALLEL_ASSERT, and _GLIBCXX_PARALLEL_MERGE_3_CASE.
| _RAIter3 __gnu_parallel::multiway_merge_4_variant | ( | _RAIterIterator | __seqs_begin, |
| _RAIterIterator | __seqs_end, | ||
| _RAIter3 | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp | ||
| ) |
Highly efficient 4-way merging procedure.
Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into goto labels in C++).
This works well for merging up to 4 sequences.
Note that making the merging stable does not come at a performance hit.
Whether the merging is done guarded or unguarded is selected by the used iterator class.
| __seqs_begin | Begin iterator of iterator pair input sequence. |
| __seqs_end | End iterator of iterator pair input sequence. |
| __target | Begin iterator of output sequence. |
| __comp | Comparator. |
| __length | Maximum length to merge, less equal than the total number of elements available. |
References _GLIBCXX_CALL, _GLIBCXX_PARALLEL_DECISION, and _GLIBCXX_PARALLEL_MERGE_4_CASE.
| void __gnu_parallel::multiway_merge_exact_splitting | ( | _RAIterIterator | __seqs_begin, |
| _RAIterIterator | __seqs_end, | ||
| _DifferenceType | __length, | ||
| _DifferenceType | __total_length, | ||
| _Compare | __comp, | ||
| std::vector< std::pair< _DifferenceType, _DifferenceType > > * | __pieces | ||
| ) |
Exact splitting for parallel multiway-merge routine.
None of the passed sequences may be empty.
References __equally_split(), _GLIBCXX_PARALLEL_LENGTH, and multiseq_partition().
Referenced by __parallel_merge_advance(), multiway_merge(), multiway_merge_sentinels(), stable_multiway_merge(), and stable_multiway_merge_sentinels().
| _RAIter3 __gnu_parallel::multiway_merge_loser_tree | ( | _RAIterIterator | __seqs_begin, |
| _RAIterIterator | __seqs_end, | ||
| _RAIter3 | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp | ||
| ) |
Multi-way merging procedure for a high branching factor, guarded case.
This merging variant uses a LoserTree class as selected by _LT.
Stability is selected through the used LoserTree class _LT.
At least one non-empty sequence is required.
| __seqs_begin | Begin iterator of iterator pair input sequence. |
| __seqs_end | End iterator of iterator pair input sequence. |
| __target | Begin iterator of output sequence. |
| __comp | Comparator. |
| __length | Maximum length to merge, less equal than the total number of elements available. |
References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_LENGTH.
| _RAIter3 __gnu_parallel::multiway_merge_loser_tree_sentinel | ( | _RAIterIterator | __seqs_begin, |
| _RAIterIterator | __seqs_end, | ||
| _RAIter3 | __target, | ||
| const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type & | __sentinel, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp | ||
| ) |
Multi-way merging procedure for a high branching factor, requiring sentinels to exist.
| UnguardedLoserTree | _Loser Tree variant to use for the unguarded merging. |
| __seqs_begin | Begin iterator of iterator pair input sequence. |
| __seqs_end | End iterator of iterator pair input sequence. |
| __target | Begin iterator of output sequence. |
| __comp | Comparator. |
| __length | Maximum length to merge, less equal than the total number of elements available. |
References __is_sorted(), _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_ASSERT.
| _RAIter3 __gnu_parallel::multiway_merge_loser_tree_unguarded | ( | _RAIterIterator | __seqs_begin, |
| _RAIterIterator | __seqs_end, | ||
| _RAIter3 | __target, | ||
| const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type & | __sentinel, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp | ||
| ) |
Multi-way merging procedure for a high branching factor, unguarded case.
Merging is done using the LoserTree class _LT.
Stability is selected by the used LoserTrees.
| __seqs_begin | Begin iterator of iterator pair input sequence. |
| __seqs_end | End iterator of iterator pair input sequence. |
| __target | Begin iterator of output sequence. |
| __comp | Comparator. |
| __length | Maximum length to merge, less equal than the total number of elements available. |
References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_ASSERT.
| void __gnu_parallel::multiway_merge_sampling_splitting | ( | _RAIterIterator | __seqs_begin, |
| _RAIterIterator | __seqs_end, | ||
| _DifferenceType | __length, | ||
| _DifferenceType | __total_length, | ||
| _Compare | __comp, | ||
| std::vector< std::pair< _DifferenceType, _DifferenceType > > * | __pieces | ||
| ) |
Sampling based splitting for parallel multiway-merge routine.
References _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::merge_oversampling.
Referenced by multiway_merge_sentinels(), stable_multiway_merge(), and stable_multiway_merge_sentinels().
| _RAIterOut __gnu_parallel::multiway_merge_sentinels | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| __gnu_parallel::sequential_tag | |||
| ) |
Multiway Merge Frontend.
Merge the sequences specified by seqs_begin and __seqs_end into __target. __seqs_begin and __seqs_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the _M_end of the same sequence in their second entry.
Ties are broken arbitrarily. See stable_multiway_merge for a variant that breaks ties by sequence number but is slower.
The first entries of the pairs (i.e. the begin iterators) will be moved forward accordingly.
The output sequence has to provide enough space for all elements that are written to it.
This function will merge the input sequences:
You have to take care that the element the _M_end iterator points to is readable and contains a value that is greater than any other non-sentinel value in all sequences.
Example:
int sequences[10][11];
for (int __i = 0; __i < 10; ++__i)
for (int __j = 0; __i < 11; ++__j)
sequences[__i][__j] = __j; // __last one is sentinel! int __out[33];
std::vector<std::pair<int*> > seqs;
for (int __i = 0; __i < 10; ++__i)
{ seqs.push(std::make_pair<int*>(sequences[__i],
sequences[__i] + 10)) }multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
__i, __seqs_begin[__i].second must be the end marker of the sequence, but also reference the one more __sentinel element.| _RAIterPairIterator | iterator over sequence of pairs of iterators |
| _RAIterOut | iterator over target sequence |
| _DifferenceTp | difference type for the sequence |
| _Compare | strict weak ordering type to compare elements in sequences |
| __seqs_begin | __begin of sequence __sequence |
| __seqs_end | _M_end of sequence __sequence |
| __target | target sequence to merge to. |
| __comp | strict weak ordering to use for element comparison. |
| __length | Maximum length to merge, possibly larger than the number of elements available. |
References __sequential_multiway_merge(), and _GLIBCXX_CALL.
Referenced by multiway_merge_sentinels().
| _RAIterOut __gnu_parallel::multiway_merge_sentinels | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| __gnu_parallel::exact_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), __sequential_multiway_merge(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_CONDITION, __gnu_parallel::_Settings::get(), multiway_merge_exact_splitting(), and parallel_multiway_merge().
| _RAIterOut __gnu_parallel::multiway_merge_sentinels | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| sampling_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), __sequential_multiway_merge(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_CONDITION, __gnu_parallel::_Settings::get(), multiway_merge_sampling_splitting(), and parallel_multiway_merge().
| _RAIterOut __gnu_parallel::multiway_merge_sentinels | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| parallel_tag | __tag = parallel_tag(0) |
||
| ) |
| _RAIterOut __gnu_parallel::multiway_merge_sentinels | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| default_parallel_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), and multiway_merge_sentinels().
| _RAIter3 __gnu_parallel::parallel_multiway_merge | ( | _RAIterIterator | __seqs_begin, |
| _RAIterIterator | __seqs_end, | ||
| _RAIter3 | __target, | ||
| _Splitter | __splitter, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| _ThreadIndex | __num_threads | ||
| ) |
Parallel multi-way merge routine.
The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings.
Must not be called if the number of sequences is 1.
| _Splitter | functor to split input (either __exact or sampling based) |
| __stable | Stable merging incurs a performance penalty. |
| __sentinel | Ignored. |
| __seqs_begin | Begin iterator of iterator pair input sequence. |
| __seqs_end | End iterator of iterator pair input sequence. |
| __target | Begin iterator of output sequence. |
| __comp | Comparator. |
| __length | Maximum length to merge, possibly larger than the number of elements available. |
References __is_sorted(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_ASSERT, _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::merge_oversampling.
Referenced by __parallel_merge_advance(), multiway_merge(), multiway_merge_sentinels(), stable_multiway_merge(), and stable_multiway_merge_sentinels().
| void __gnu_parallel::parallel_sort_mwms | ( | _RAIter | __begin, |
| _RAIter | __end, | ||
| _Compare | __comp, | ||
| _ThreadIndex | __num_threads | ||
| ) |
PMWMS main call.
| __begin | Begin iterator of sequence. |
| __end | End iterator of sequence. |
| __comp | Comparator. |
| __num_threads | Number of threads to use. |
References __gnu_profile::__size(), _GLIBCXX_CALL, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_num_threads, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_offsets, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_pieces, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_samples, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_temporary, __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::sort_mwms_oversampling.
| void __gnu_parallel::parallel_sort_mwms_pu | ( | _PMWMSSortingData< _RAIter > * | __sd, |
| _Compare & | __comp | ||
| ) |
PMWMS code executed by each thread.
| __sd | Pointer to algorithm data. |
| __comp | Comparator. |
References __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_num_threads, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_pieces, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_temporary, __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::sort_mwms_oversampling.
| _RAIterOut __gnu_parallel::stable_multiway_merge | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| __gnu_parallel::sequential_tag | |||
| ) |
References __sequential_multiway_merge(), and _GLIBCXX_CALL.
Referenced by __gnu_parallel::__possibly_stable_multiway_merge< true, Seq_RAIter, _RAIter, _Compare, _DiffType >::operator()(), and stable_multiway_merge().
| _RAIterOut __gnu_parallel::stable_multiway_merge | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| __gnu_parallel::exact_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), __sequential_multiway_merge(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_CONDITION, __gnu_parallel::_Settings::get(), multiway_merge_exact_splitting(), and parallel_multiway_merge().
| _RAIterOut __gnu_parallel::stable_multiway_merge | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| sampling_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), __sequential_multiway_merge(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_CONDITION, __gnu_parallel::_Settings::get(), multiway_merge_sampling_splitting(), and parallel_multiway_merge().
| _RAIterOut __gnu_parallel::stable_multiway_merge | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| parallel_tag | __tag = parallel_tag(0) |
||
| ) |
| _RAIterOut __gnu_parallel::stable_multiway_merge | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| default_parallel_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), and stable_multiway_merge().
| _RAIterOut __gnu_parallel::stable_multiway_merge_sentinels | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| __gnu_parallel::sequential_tag | |||
| ) |
References __sequential_multiway_merge(), and _GLIBCXX_CALL.
Referenced by stable_multiway_merge_sentinels().
| _RAIterOut __gnu_parallel::stable_multiway_merge_sentinels | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| __gnu_parallel::exact_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), __sequential_multiway_merge(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_CONDITION, __gnu_parallel::_Settings::get(), multiway_merge_exact_splitting(), and parallel_multiway_merge().
| _RAIterOut __gnu_parallel::stable_multiway_merge_sentinels | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| sampling_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), __sequential_multiway_merge(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_CONDITION, __gnu_parallel::_Settings::get(), multiway_merge_sampling_splitting(), and parallel_multiway_merge().
| _RAIterOut __gnu_parallel::stable_multiway_merge_sentinels | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| parallel_tag | __tag = parallel_tag(0) |
||
| ) |
| _RAIterOut __gnu_parallel::stable_multiway_merge_sentinels | ( | _RAIterPairIterator | __seqs_begin, |
| _RAIterPairIterator | __seqs_end, | ||
| _RAIterOut | __target, | ||
| _DifferenceTp | __length, | ||
| _Compare | __comp, | ||
| default_parallel_tag | __tag | ||
| ) |
References __gnu_parallel::parallel_tag::__get_num_threads(), and stable_multiway_merge_sentinels().
|
static |
Number of bits of _CASable.
Referenced by __decode2(), and __encode2().
|
static |
_CASable with the right half of bits set to 1.
Referenced by __decode2().
1.8.9.1 
