__gnu_parallel(3)

NAME

__gnu_parallel

Detailed Description

GNU parallel code for public use.

SYNOPSIS

Classes
    struct _Settings
        class _Settings Run-time settings for the parallel mode, including
        all tunable parameters.
    struct accumulate_binop_reduct
        General reduction, using a binary operator.
    struct accumulate_selector
        std::accumulate() selector.
    struct adjacent_difference_selector
        Selector that returns the difference between two adjacent elements.
    struct adjacent_find_selector
        Test predicate on two adjacent elements.
    struct balanced_tag
        Recommends parallel execution using dynamic load-balancing at
        compile time.
    class binder1st
        Similar to std::binder1st, but giving the argument types
        explicitly.
    class binder2nd
        Similar to std::binder2nd, but giving the argument types
        explicitly.
    struct constant_size_blocks_tag
        Selects the constant block size variant for std::find().
    struct count_if_selector
        std::count_if () selector.
    struct count_selector
        std::count() selector.
    struct DRandomShufflingGlobalData
        Data known to every thread participating in
        __gnu_parallel::parallel_random_shuffle().
    struct DRSSorterPU
        Local data for a thread participating in
        __gnu_parallel::parallel_random_shuffle().
    struct dummy_reduct
        Reduction function doing nothing.
    class equal_from_less
        Constructs predicate for equality from strict weak ordering
        predicate.
    struct equal_split_tag
        Selects the equal splitting variant for std::find().
    struct equal_to
        Similar to std::equal_to, but allows two different types.
    struct exact_tag
        Forces exact splitting in multiway merge at compile time.
    struct fill_selector
        std::fill() selector.
    struct find_first_of_selector
        Test predicate on several elements.
    struct find_if_selector
        Test predicate on a single element, used for std::find() and
        std::find_if ().
    struct for_each_selector
        std::for_each() selector.
    struct generate_selector
        std::generate() selector.
    struct generic_find_selector
        Base class of all __gnu_parallel::find_template selectors.
    struct generic_for_each_selector
        Generic selector for embarrassingly parallel functions.
    struct growing_blocks_tag
        Selects the growing block size variant for std::find().
    class guarded_iterator
        Iterator wrapper supporting an implicit supremum at the end of the
        sequence, dominating all comparisons.
    struct identity_selector
        Selector that just returns the passed iterator.
    struct inner_product_selector
        std::inner_product() selector.
    class iterator_pair
        A pair of iterators. The usual iterator operations are applied to
        both child iterators.
    class iterator_triple
        A triple of iterators. The usual iterator operations are applied to
        all three child iterators.
    struct Job
        One job for a certain thread.
    struct less
        Similar to std::less, but allows two different types.
    class lexicographic
        Compare a pair of types lexicographically, ascending.
    class lexicographic_reverse
        Compare a pair of types lexicographically, descending.
    struct loser_tree_traits
        Traits for determining whether the loser tree should use pointers
        or copies.
    class LoserTree
        Stable LoserTree variant.
    class LoserTree< false, T, Comparator >
        Unstable LoserTree variant.
    class LoserTreeBase
        Guarded loser/tournament tree.
    class LoserTreePointer
        Stable LoserTree implementation.
    class LoserTreePointer< false, T, Comparator >
        Unstable LoserTree implementation.
    class LoserTreePointerBase
        Base class of Loser Tree implementation using pointers.
    class LoserTreePointerUnguarded
        Stable unguarded LoserTree variant storing pointers.
    class LoserTreePointerUnguarded< false, T, Comparator >
        Unstable unguarded LoserTree variant storing pointers.
    class LoserTreePointerUnguardedBase
        Unguarded loser tree, keeping only pointers to the elements in the
        tree structure.
    class LoserTreeUnguarded
        Stable implementation of unguarded LoserTree.
    class LoserTreeUnguarded< false, T, Comparator >
        Non-Stable implementation of unguarded LoserTree.
    class LoserTreeUnguardedBase
        Base class for unguarded LoserTree implementation.
    struct max_element_reduct
        Reduction for finding the maximum element, using a comparator.
    struct min_element_reduct
        Reduction for finding the maximum element, using a comparator.
    struct mismatch_selector
        Test inverted predicate on a single element.
    struct multiplies
        Similar to std::multiplies, but allows two different types.
    struct multiway_merge_3_variant_sentinel_switch
        Switch for 3-way merging with sentinels turned off.
    struct multiway_merge_3_variant_sentinel_switch< true,
        RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp,
        Comparator >
        Switch for 3-way merging with sentinels turned on.
    struct multiway_merge_4_variant_sentinel_switch
        Switch for 4-way merging with sentinels turned off.
    struct multiway_merge_4_variant_sentinel_switch< true,
        RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp,
        Comparator >
        Switch for 4-way merging with sentinels turned on.
    struct multiway_merge_k_variant_sentinel_switch
        Switch for k-way merging with sentinels turned on.
    struct multiway_merge_k_variant_sentinel_switch< false, stable,
        RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp,
        Comparator >
        Switch for k-way merging with sentinels turned off.
    struct nothing
        Functor doing nothing.
    struct omp_loop_static_tag
        Recommends parallel execution using OpenMP static load-balancing at
        compile time.
    struct omp_loop_tag
        Recommends parallel execution using OpenMP dynamic load-balancing
        at compile time.
    struct parallel_tag
        Recommends parallel execution at compile time.
    struct Piece
        Subsequence description.
    struct plus
        Similar to std::plus, but allows two different types.
    struct PMWMSSortingData
        Data accessed by all threads.
    class pseudo_sequence
        Sequence that conceptually consists of multiple copies of the same
        element. The copies are not stored explicitly, of course.
    class pseudo_sequence_iterator
        Iterator associated with __gnu_parallel::pseudo_sequence. If
        features the usual random-access iterator functionality.
    struct QSBThreadLocal
        Information local to one thread in the parallel quicksort run.
    class random_number
        Random number generator, based on the Mersenne twister.
    struct replace_if_selector
        std::replace() selector.
    struct replace_selector
        std::replace() selector.
    class RestrictedBoundedConcurrentQueue
        Double-ended queue of bounded size, allowing lock-free atomic
        access. push_front() and pop_front() must not be called
        concurrently to each other, while pop_back() can be called
        concurrently at all times. empty(), size(), and top() are
        intentionally not provided. Calling them would not make sense in a
        concurrent setting.
    struct sampling_sorter
        Stable sorting functor.
    struct sampling_sorter< false, RandomAccessIterator, StrictWeakOrdering
        >
        Non-stable sorting functor.
    struct sequential_tag
        Forces sequential execution at compile time.
    struct split_consistently
        Split consistently.
    struct split_consistently< false, RandomAccessIterator, Comparator,
        SortingPlacesIterator >
        Split by sampling.
    struct split_consistently< true, RandomAccessIterator, Comparator,
        SortingPlacesIterator >
        Split by exact splitting.
    struct transform1_selector
        std::transform() selector, one input sequence variant.
    struct transform2_selector
        std::transform() selector, two input sequences variant.
    class unary_negate
        Similar to std::binder1st, but giving the argument types
        explicitly.
    struct unbalanced_tag
        Recommends parallel execution using static load-balancing at
        compile time.
    class void_functor
        Functor that does nothing.
Typedefs
    typedef unsigned short bin_index
    typedef short int16
    typedef int int32
    typedef long long int64
    typedef int64 lcas_t
    typedef uint64 sequence_index_t
    typedef uint16 thread_index_t
    typedef unsigned short uint16
    typedef unsigned int uint32
    typedef unsigned long long uint64
Enumerations
    enum _AlgorithmStrategy { heuristic, force_sequential, force_parallel }
    enum _FindAlgorithm { GROWING_BLOCKS, CONSTANT_SIZE_BLOCKS, EQUAL_SPLIT
        }
    enum _MultiwayMergeAlgorithm { LOSER_TREE }
    enum _Parallelism { sequential, parallel_unbalanced, parallel_balanced,
        parallel_omp_loop, parallel_omp_loop_static, parallel_taskqueue }
    enum _PartialSumAlgorithm { RECURSIVE, LINEAR }
    enum _SortAlgorithm { MWMS, QS, QS_BALANCED }
    enum _SplittingAlgorithm { SAMPLING, EXACT }
Functions
    void __replacement_assert (const char *__file, int __line, const char
        *__function, const char *__condition)
    template<typename RandomAccessIterator, typename _DifferenceTp> void
        calc_borders (RandomAccessIterator elements, _DifferenceTp length,
        _DifferenceTp *off)
    template<typename T> bool compare_and_swap (volatile T *ptr, T
        comparand, T replacement)
    bool compare_and_swap_32 (volatile int32 *ptr, int32 comparand, int32
        replacement)
    bool compare_and_swap_64 (volatile int64 *ptr, int64 comparand, int64
        replacement)
    template<typename InputIterator, typename OutputIterator>
        OutputIterator copy_tail (std::pair< InputIterator, InputIterator >
        b, std::pair< InputIterator, InputIterator > e, OutputIterator r)
    void decode2 (lcas_t x, int &a, int &b)
    template<typename RandomAccessIterator, typename _DifferenceTp> void
        determine_samples (PMWMSSortingData< RandomAccessIterator > *sd,
        _DifferenceTp num_samples)
    lcas_t encode2 (int a, int b)
    template<typename difference_type, typename OutputIterator>
        OutputIterator equally_split (difference_type n, thread_index_t
        num_threads, OutputIterator s)
    template<typename difference_type> difference_type equally_split_point
        (difference_type n, thread_index_t num_threads, thread_index_t
        thread_no)
    template<typename T> T fetch_and_add (volatile T *ptr, T addend)
    int32 fetch_and_add_32 (volatile int32 *ptr, int32 addend)
    int64 fetch_and_add_64 (volatile int64 *ptr, int64 addend)
    template<typename RandomAccessIterator1, typename
        RandomAccessIterator2, typename Pred, typename Selector> std::pair<
        RandomAccessIterator1, RandomAccessIterator2 > find_template
        (RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
        RandomAccessIterator2 begin2, Pred pred, Selector selector)
    template<typename InputIterator, typename UserOp, typename
        Functionality, typename Red, typename Result> UserOp
        for_each_template_random_access (InputIterator begin, InputIterator
        end, UserOp user_op, Functionality &functionality, Red reduction,
        Result reduction_start, Result &output, typename
        std::iterator_traits< InputIterator >::difference_type bound,
        _Parallelism parallelism_tag)
    template<typename RandomAccessIterator, typename Op, typename Fu,
        typename Red, typename Result> Op
        for_each_template_random_access_ed (RandomAccessIterator begin,
        RandomAccessIterator end, Op o, Fu &f, Red r, Result base, Result
        &output, typename std::iterator_traits< RandomAccessIterator
        >::difference_type bound)
    template<typename RandomAccessIterator, typename Op, typename Fu,
        typename Red, typename Result> Op
        for_each_template_random_access_omp_loop (RandomAccessIterator
        begin, RandomAccessIterator end, Op o, Fu &f, Red r, Result base,
        Result &output, typename std::iterator_traits< RandomAccessIterator
        >::difference_type bound)
    template<typename RandomAccessIterator, typename Op, typename Fu,
        typename Red, typename Result> Op
        for_each_template_random_access_omp_loop_static
        (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu &f,
        Red r, Result base, Result &output, typename std::iterator_traits<
        RandomAccessIterator >::difference_type bound)
    template<typename RandomAccessIterator, typename Op, typename Fu,
        typename Red, typename Result> Op
        for_each_template_random_access_workstealing (RandomAccessIterator
        begin, RandomAccessIterator end, Op op, Fu &f, Red r, Result base,
        Result &output, typename std::iterator_traits< RandomAccessIterator
        >::difference_type bound)
    int get_max_threads ()
    bool is_parallel (const _Parallelism __p)
    template<typename InputIterator, typename Comparator> bool is_sorted
        (InputIterator begin, InputIterator end, Comparator comp=std::less<
        typename std::iterator_traits< InputIterator >::value_type >())
    template<typename InputIterator, typename Comparator> bool
        is_sorted_failure (InputIterator begin, InputIterator end,
        InputIterator &first_failure, Comparator comp=std::less< typename
        std::iterator_traits< InputIterator >::value_type >())
    template<typename InputIterator, typename Comparator> bool
        is_sorted_print_failures (InputIterator begin, InputIterator end,
        Comparator comp=std::less< typename std::iterator_traits<
        InputIterator >::value_type >())
    template<typename InputIterator, typename FunctorType> size_t
        list_partition (const InputIterator begin, const InputIterator end,
        InputIterator *starts, size_t *lengths, const int num_parts,
        FunctorType &f, int oversampling=0)
    template<typename Size> Size log2 (Size n)
    template<typename T> const T & max (const T &a, const T &b)
    template<typename RandomAccessIterator, typename Comparator>
        RandomAccessIterator median_of_three_iterators
        (RandomAccessIterator a, RandomAccessIterator b,
        RandomAccessIterator c, Comparator &comp)
    template<typename RandomAccessIterator1, typename
        RandomAccessIterator2, typename OutputIterator, typename
        _DifferenceTp, typename Comparator> OutputIterator merge_advance
        (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1,
        RandomAccessIterator2 &begin2, RandomAccessIterator2 end2,
        OutputIterator target, _DifferenceTp max_length, Comparator comp)
    template<typename RandomAccessIterator1, typename
        RandomAccessIterator2, typename OutputIterator, typename
        _DifferenceTp, typename Comparator> OutputIterator
        merge_advance_movc (RandomAccessIterator1 &begin1,
        RandomAccessIterator1 end1, RandomAccessIterator2 &begin2,
        RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp
        max_length, Comparator comp)
    template<typename RandomAccessIterator1, typename
        RandomAccessIterator2, typename OutputIterator, typename
        _DifferenceTp, typename Comparator> OutputIterator
        merge_advance_usual (RandomAccessIterator1 &begin1,
        RandomAccessIterator1 end1, RandomAccessIterator2 &begin2,
        RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp
        max_length, Comparator comp)
    template<typename T> const T & min (const T &a, const T &b)
    template<typename RanSeqs, typename RankType, typename RankIterator,
        typename Comparator> void multiseq_partition (RanSeqs begin_seqs,
        RanSeqs end_seqs, RankType rank, RankIterator begin_offsets,
        Comparator comp=std::less< typename std::iterator_traits< typename
        std::iterator_traits< RanSeqs >::value_type::first_type
        >::value_type >())
    template<typename T, typename RanSeqs, typename RankType, typename
        Comparator> T multiseq_selection (RanSeqs begin_seqs, RanSeqs
        end_seqs, RankType rank, RankType &offset, Comparator
        comp=std::less< T >())
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut multiway_merge
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length,
        __gnu_parallel::exact_tag)
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut multiway_merge
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length,
        __gnu_parallel::sequential_tag)
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut multiway_merge
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length)
    template<template< typename RAI, typename C > class iterator, typename
        RandomAccessIteratorIterator, typename RandomAccessIterator3,
        typename _DifferenceTp, typename Comparator> RandomAccessIterator3
        multiway_merge_3_variant (RandomAccessIteratorIterator seqs_begin,
        RandomAccessIteratorIterator seqs_end, RandomAccessIterator3
        target, Comparator comp, _DifferenceTp length)
    template<template< typename RAI, typename C > class iterator, typename
        RandomAccessIteratorIterator, typename RandomAccessIterator3,
        typename _DifferenceTp, typename Comparator> RandomAccessIterator3
        multiway_merge_4_variant (RandomAccessIteratorIterator seqs_begin,
        RandomAccessIteratorIterator seqs_end, RandomAccessIterator3
        target, Comparator comp, _DifferenceTp length)
    template<bool stable, typename RandomAccessIteratorIterator, typename
        Comparator, typename difference_type> void
        multiway_merge_exact_splitting (RandomAccessIteratorIterator
        seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp,
        difference_type length, difference_type total_length, std::vector<
        std::pair< difference_type, difference_type > > *pieces)
    template<typename LT, typename RandomAccessIteratorIterator, typename
        RandomAccessIterator3, typename _DifferenceTp, typename Comparator>
        RandomAccessIterator3 multiway_merge_loser_tree
        (RandomAccessIteratorIterator seqs_begin,
        RandomAccessIteratorIterator seqs_end, RandomAccessIterator3
        target, Comparator comp, _DifferenceTp length)
    template<typename UnguardedLoserTree, typename
        RandomAccessIteratorIterator, typename RandomAccessIterator3,
        typename _DifferenceTp, typename Comparator> RandomAccessIterator3
        multiway_merge_loser_tree_sentinel (RandomAccessIteratorIterator
        seqs_begin, RandomAccessIteratorIterator seqs_end,
        RandomAccessIterator3 target, const typename std::iterator_traits<
        typename std::iterator_traits< RandomAccessIteratorIterator
        >::value_type::first_type >::value_type &sentinel, Comparator comp,
        _DifferenceTp length)
    template<typename LT, typename RandomAccessIteratorIterator, typename
        RandomAccessIterator3, typename _DifferenceTp, typename Comparator>
        RandomAccessIterator3 multiway_merge_loser_tree_unguarded
        (RandomAccessIteratorIterator seqs_begin,
        RandomAccessIteratorIterator seqs_end, RandomAccessIterator3
        target, const typename std::iterator_traits< typename
        std::iterator_traits< RandomAccessIteratorIterator
        >::value_type::first_type >::value_type &sentinel, Comparator comp,
        _DifferenceTp length)
    template<bool stable, typename RandomAccessIteratorIterator, typename
        Comparator, typename difference_type> void
        multiway_merge_sampling_splitting (RandomAccessIteratorIterator
        seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp,
        difference_type length, difference_type total_length, std::vector<
        std::pair< difference_type, difference_type > > *pieces)
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut multiway_merge_sentinels
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length,
        __gnu_parallel::exact_tag)
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut multiway_merge_sentinels
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length,
        __gnu_parallel::sequential_tag)
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut multiway_merge_sentinels
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length)
    template<typename RandomAccessIterator, typename Comparator> bool
        operator< (unguarded_iterator< RandomAccessIterator, Comparator >
        &bi1, unguarded_iterator< RandomAccessIterator, Comparator > &bi2)
    template<typename RandomAccessIterator, typename Comparator> bool
        operator< (guarded_iterator< RandomAccessIterator, Comparator >
        &bi1, guarded_iterator< RandomAccessIterator, Comparator > &bi2)
    template<typename RandomAccessIterator, typename Comparator> bool
        operator<= (unguarded_iterator< RandomAccessIterator, Comparator >
        &bi1, unguarded_iterator< RandomAccessIterator, Comparator > &bi2)
    template<typename RandomAccessIterator, typename Comparator> bool
        operator<= (guarded_iterator< RandomAccessIterator, Comparator >
        &bi1, guarded_iterator< RandomAccessIterator, Comparator > &bi2)
    template<typename RandomAccessIterator1, typename
        RandomAccessIterator3, typename Comparator> RandomAccessIterator3
        parallel_merge_advance (RandomAccessIterator1 &begin1,
        RandomAccessIterator1 end1, RandomAccessIterator1 &begin2,
        RandomAccessIterator1 end2, RandomAccessIterator3 target, typename
        std::iterator_traits< RandomAccessIterator1 >::difference_type
        max_length, Comparator comp)
    template<typename RandomAccessIterator1, typename
        RandomAccessIterator2, typename RandomAccessIterator3, typename
        Comparator> RandomAccessIterator3 parallel_merge_advance
        (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1,
        RandomAccessIterator2 &begin2, RandomAccessIterator2 end2,
        RandomAccessIterator3 target, typename std::iterator_traits<
        RandomAccessIterator1 >::difference_type max_length, Comparator
        comp)
    template<bool stable, bool sentinels, typename
        RandomAccessIteratorIterator, typename RandomAccessIterator3,
        typename _DifferenceTp, typename Splitter, typename Comparator>
        RandomAccessIterator3 parallel_multiway_merge
        (RandomAccessIteratorIterator seqs_begin,
        RandomAccessIteratorIterator seqs_end, RandomAccessIterator3
        target, Comparator comp, Splitter splitter, _DifferenceTp length)
    template<typename RandomAccessIterator, typename Comparator> void
        parallel_nth_element (RandomAccessIterator begin,
        RandomAccessIterator nth, RandomAccessIterator end, Comparator
        comp)
    template<typename RandomAccessIterator, typename Comparator> void
        parallel_partial_sort (RandomAccessIterator begin,
        RandomAccessIterator middle, RandomAccessIterator end, Comparator
        comp)
    template<typename InputIterator, typename OutputIterator, typename
        BinaryOperation> OutputIterator parallel_partial_sum (InputIterator
        begin, InputIterator end, OutputIterator result, BinaryOperation
        bin_op)
    template<typename InputIterator, typename OutputIterator, typename
        BinaryOperation> OutputIterator parallel_partial_sum_basecase
        (InputIterator begin, InputIterator end, OutputIterator result,
        BinaryOperation bin_op, typename std::iterator_traits<
        InputIterator >::value_type value)
    template<typename InputIterator, typename OutputIterator, typename
        BinaryOperation> OutputIterator parallel_partial_sum_linear
        (InputIterator begin, InputIterator end, OutputIterator result,
        BinaryOperation bin_op, typename std::iterator_traits<
        InputIterator >::difference_type n)
    template<typename RandomAccessIterator, typename Predicate>
        std::iterator_traits< RandomAccessIterator >::difference_type
        parallel_partition (RandomAccessIterator begin,
        RandomAccessIterator end, Predicate pred, thread_index_t
        num_threads)
    template<typename RandomAccessIterator, typename RandomNumberGenerator>
        void parallel_random_shuffle (RandomAccessIterator begin,
        RandomAccessIterator end, RandomNumberGenerator
        rng=random_number())
    template<typename RandomAccessIterator, typename RandomNumberGenerator>
        void parallel_random_shuffle_drs (RandomAccessIterator begin,
        RandomAccessIterator end, typename std::iterator_traits<
        RandomAccessIterator >::difference_type n, thread_index_t
        num_threads, RandomNumberGenerator &rng)
    template<typename RandomAccessIterator, typename RandomNumberGenerator>
        void parallel_random_shuffle_drs_pu (DRSSorterPU<
        RandomAccessIterator, RandomNumberGenerator > *pus)
    template<typename InputIterator, typename OutputIterator, typename
        Comparator> OutputIterator parallel_set_difference (InputIterator
        begin1, InputIterator end1, InputIterator begin2, InputIterator
        end2, OutputIterator result, Comparator comp)
    template<typename InputIterator, typename OutputIterator, typename
        Comparator> OutputIterator parallel_set_intersection (InputIterator
        begin1, InputIterator end1, InputIterator begin2, InputIterator
        end2, OutputIterator result, Comparator comp)
    template<typename InputIterator, typename OutputIterator, typename
        Operation> OutputIterator parallel_set_operation (InputIterator
        begin1, InputIterator end1, InputIterator begin2, InputIterator
        end2, OutputIterator result, Operation op)
    template<typename InputIterator, typename OutputIterator, typename
        Comparator> OutputIterator parallel_set_symmetric_difference
        (InputIterator begin1, InputIterator end1, InputIterator begin2,
        InputIterator end2, OutputIterator result, Comparator comp)
    template<typename InputIterator, typename OutputIterator, typename
        Comparator> OutputIterator parallel_set_union (InputIterator
        begin1, InputIterator end1, InputIterator begin2, InputIterator
        end2, OutputIterator result, Comparator comp)
    template<typename RandomAccessIterator, typename Comparator> void
        parallel_sort (RandomAccessIterator begin, RandomAccessIterator
        end, Comparator comp, bool stable)
    template<bool stable, bool exact, typename RandomAccessIterator,
        typename Comparator> void parallel_sort_mwms (RandomAccessIterator
        begin, RandomAccessIterator end, Comparator comp, thread_index_t
        num_threads)
    template<bool stable, bool exact, typename RandomAccessIterator,
        typename Comparator> void parallel_sort_mwms_pu (PMWMSSortingData<
        RandomAccessIterator > *sd, Comparator &comp)
    template<typename RandomAccessIterator, typename Comparator> void
        parallel_sort_qs (RandomAccessIterator begin, RandomAccessIterator
        end, Comparator comp, typename std::iterator_traits<
        RandomAccessIterator >::difference_type n, int num_threads)
    template<typename RandomAccessIterator, typename Comparator> void
        parallel_sort_qs_conquer (RandomAccessIterator begin,
        RandomAccessIterator end, Comparator comp, thread_index_t
        num_threads)
    template<typename RandomAccessIterator, typename Comparator>
        std::iterator_traits< RandomAccessIterator >::difference_type
        parallel_sort_qs_divide (RandomAccessIterator begin,
        RandomAccessIterator end, Comparator comp, typename
        std::iterator_traits< RandomAccessIterator >::difference_type
        pivot_rank, typename std::iterator_traits< RandomAccessIterator
        >::difference_type num_samples, thread_index_t num_threads)
    template<typename RandomAccessIterator, typename Comparator> void
        parallel_sort_qsb (RandomAccessIterator begin, RandomAccessIterator
        end, Comparator comp, typename std::iterator_traits<
        RandomAccessIterator >::difference_type n, thread_index_t
        num_threads)
    template<typename InputIterator, class OutputIterator> OutputIterator
        parallel_unique_copy (InputIterator first, InputIterator last,
        OutputIterator result)
    template<typename InputIterator, class OutputIterator, class
        BinaryPredicate> OutputIterator parallel_unique_copy (InputIterator
        first, InputIterator last, OutputIterator result, BinaryPredicate
        binary_pred)
    template<typename RandomAccessIterator, typename Comparator> void
        qsb_conquer (QSBThreadLocal< RandomAccessIterator > **tls,
        RandomAccessIterator begin, RandomAccessIterator end, Comparator
        comp, thread_index_t iam, thread_index_t num_threads, bool
        parent_wait)
    template<typename RandomAccessIterator, typename Comparator>
        std::iterator_traits< RandomAccessIterator >::difference_type
        qsb_divide (RandomAccessIterator begin, RandomAccessIterator end,
        Comparator comp, thread_index_t num_threads)
    template<typename RandomAccessIterator, typename Comparator> void
        qsb_local_sort_with_helping (QSBThreadLocal< RandomAccessIterator >
        **tls, Comparator &comp, int iam, bool wait)
    template<typename RandomNumberGenerator> int random_number_pow2 (int
        logp, RandomNumberGenerator &rng)
    template<typename T> T round_up_to_pow2 (T x)
    template<typename _RandomAccessIterator1, typename
        _RandomAccessIterator2, typename Pred> _RandomAccessIterator1
        search_template (_RandomAccessIterator1 begin1,
        _RandomAccessIterator1 end1, _RandomAccessIterator2 begin2,
        _RandomAccessIterator2 end2, Pred pred)
    template<bool stable, bool sentinels, typename
        RandomAccessIteratorIterator, typename RandomAccessIterator3,
        typename _DifferenceTp, typename Comparator> RandomAccessIterator3
        sequential_multiway_merge (RandomAccessIteratorIterator seqs_begin,
        RandomAccessIteratorIterator seqs_end, RandomAccessIterator3
        target, const typename std::iterator_traits< typename
        std::iterator_traits< RandomAccessIteratorIterator
        >::value_type::first_type >::value_type &sentinel, Comparator comp,
        _DifferenceTp length)
    template<typename RandomAccessIterator, typename RandomNumberGenerator>
        void sequential_random_shuffle (RandomAccessIterator begin,
        RandomAccessIterator end, RandomNumberGenerator &rng)
    template<typename InputIterator, typename OutputIterator>
        OutputIterator set_intersection (InputIterator begin1,
        InputIterator end1, InputIterator begin2, InputIterator end2,
        OutputIterator result)
    template<typename InputIterator> void shrink (std::vector<
        InputIterator > &os_starts, size_t &count_to_two, size_t
        &range_length)
    template<typename InputIterator> void shrink_and_double (std::vector<
        InputIterator > &os_starts, size_t &count_to_two, size_t
        &range_length, const bool make_twice)
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut stable_multiway_merge
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length,
        __gnu_parallel::exact_tag)
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut stable_multiway_merge
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length,
        __gnu_parallel::sequential_tag)
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut stable_multiway_merge
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length)
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut stable_multiway_merge_sentinels
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length,
        __gnu_parallel::exact_tag)
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut stable_multiway_merge_sentinels
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length,
        __gnu_parallel::sequential_tag)
    template<typename RandomAccessIteratorPairIterator, typename
        RandomAccessIteratorOut, typename _DifferenceTp, typename
        Comparator> RandomAccessIteratorOut stable_multiway_merge_sentinels
        (RandomAccessIteratorPairIterator seqs_begin,
        RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut
        target, Comparator comp, _DifferenceTp length)
    void yield ()
Variables
    static const int lcas_t_bits
    static const lcas_t lcas_t_mask

Typedef Documentation

typedef unsigned short __gnu_parallel::bin_index

Type to hold the index of a bin.

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

Definition at line 53 of file random_shuffle.h.

typedef short __gnu_parallel::int16

Integer Types.

16-bit signed integer.

Definition at line 120 of file types.h.

typedef int __gnu_parallel::int32

32-bit signed integer.

Definition at line 126 of file types.h.

typedef long long __gnu_parallel::int64

64-bit signed integer.

Definition at line 132 of file types.h.

typedef int64 __gnu_parallel::lcas_t

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

Definition at line 151 of file types.h.

typedef uint64 __gnu_parallel::sequence_index_t

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

Definition at line 141 of file types.h.

typedef uint16 __gnu_parallel::thread_index_t

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

Definition at line 147 of file types.h.

typedef unsigned short __gnu_parallel::uint16

16-bit unsigned integer.

Definition at line 123 of file types.h.

typedef unsigned int __gnu_parallel::uint32

32-bit unsigned integer.

Definition at line 129 of file types.h.

typedef unsigned long long __gnu_parallel::uint64

64-bit unsigned integer.

Definition at line 135 of file types.h.

Enumeration Type Documentation

enum __gnu_parallel::_AlgorithmStrategy

Strategies for run-time algorithm selection:.

Definition at line 71 of file types.h.

enum __gnu_parallel::_FindAlgorithm

Find algorithms:.

Definition at line 110 of file types.h.

enum __gnu_parallel::_MultiwayMergeAlgorithm

Merging algorithms:.

Definition at line 89 of file types.h.

enum __gnu_parallel::_Parallelism

Run-time equivalents for the compile-time tags.

Enumerator:

sequential

Not parallel.

parallel_unbalanced

Parallel unbalanced (equal-sized chunks).

parallel_balanced

Parallel balanced (work-stealing).

parallel_omp_loop

Parallel with OpenMP dynamic load-balancing.

parallel_omp_loop_static

Parallel with OpenMP static load-balancing.

parallel_taskqueue

Parallel with OpenMP taskqueue construct.

Definition at line 48 of file types.h.

enum __gnu_parallel::_PartialSumAlgorithm

Partial sum algorithms: recursive, linear.

Definition at line 95 of file types.h.

enum __gnu_parallel::_SortAlgorithm

Sorting algorithms:.

Definition at line 80 of file types.h.

enum __gnu_parallel::_SplittingAlgorithm

Sorting/merging algorithms: sampling, exact.

Definition at line 102 of file types.h.

Function Documentation

template<typename RandomAccessIterator, typename _DifferenceTp> void

__gnu_parallel::calc_borders (RandomAccessIterator elements, _DifferenceTp length, _DifferenceTp * off) [inline] Precalculate advances for Knuth-Morris-Pratt algorithm.

Parameters:

elements Begin iterator of sequence to search for. length Length of sequence to search for.
advances Returned offsets.

Definition at line 58 of file search.h.

Referenced by search_template().

template<typename T> bool __gnu_parallel::compare_and_swap (volatile T *

ptr, T comparand, T replacement) [inline] Compare *ptr and comparand. If equal, let *ptr=replacement and return
true, return false otherwise.

Implementation is heavily platform-dependent.

Parameters:

ptr Pointer to signed integer.
comparand Compare value.
replacement Replacement value.

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

References compare_and_swap_32(), and compare_and_swap_64().

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue<
std::pair< RandomAccessIterator, RandomAccessIterator > >::pop_back(), and __gnu_parallel::RestrictedBoundedConcurrentQueue< std::pair<
RandomAccessIterator, RandomAccessIterator > >::pop_front().

bool __gnu_parallel::compare_and_swap_32 (volatile int32 * ptr, int32

comparand, int32 replacement) [inline] Compare *ptr and comparand. If equal, let *ptr=replacement and return
true, return false otherwise.

Implementation is heavily platform-dependent.

Parameters:

ptr Pointer to 32-bit signed integer.
comparand Compare value.
replacement Replacement value.

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

Referenced by compare_and_swap().

bool __gnu_parallel::compare_and_swap_64 (volatile int64 * ptr, int64

comparand, int64 replacement) [inline] Compare *ptr and comparand. If equal, let *ptr=replacement and return
true, return false otherwise.

Implementation is heavily platform-dependent.

Parameters:

ptr Pointer to 64-bit signed integer.
comparand Compare value.
replacement Replacement value.

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

Referenced by compare_and_swap().

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

Decode two integers from one __gnu_parallel::lcas_t.

Parameters:

x __gnu_parallel::lcas_t to decode integers from. a First integer, to be decoded from the most-significant
lcas_t_bits/2 bits of x.
b Second integer, to be encoded in the least-significant
lcas_t_bits/2 bits of x.

See also:

encode2

Definition at line 143 of file base.h.

References lcas_t_bits, and lcas_t_mask.

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue<
std::pair< RandomAccessIterator, RandomAccessIterator > >::pop_back(), __gnu_parallel::RestrictedBoundedConcurrentQueue< std::pair<
RandomAccessIterator, RandomAccessIterator > >::pop_front(), and
__gnu_parallel::RestrictedBoundedConcurrentQueue< std::pair<
RandomAccessIterator, RandomAccessIterator > >::push_front().

template<typename RandomAccessIterator, typename _DifferenceTp> void

__gnu_parallel::determine_samples (PMWMSSortingData< RandomAccessIterator > * sd, _DifferenceTp num_samples) [inline] Select samples from a sequence.

Parameters:

sd Pointer to algorithm data. Result will be placed in sd->samples. num_samples Number of samples to select.

Definition at line 104 of file multiway_mergesort.h.

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

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

Encode two integers into one __gnu_parallel::lcas_t.

Parameters:

a First integer, to be encoded in the most-significant
lcas_t_bits/2 bits.
b Second integer, to be encoded in the least-significant
lcas_t_bits/2 bits.

Returns:

__gnu_parallel::lcas_t value encoding a and b.

See also:

decode2

Definition at line 129 of file base.h.

References lcas_t_bits.

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue<
std::pair< RandomAccessIterator, RandomAccessIterator > >::pop_back(), __gnu_parallel::RestrictedBoundedConcurrentQueue< std::pair<
RandomAccessIterator, RandomAccessIterator > >::pop_front(),
__gnu_parallel::RestrictedBoundedConcurrentQueue< std::pair<
RandomAccessIterator, RandomAccessIterator > >::push_front(), and
__gnu_parallel::RestrictedBoundedConcurrentQueue< std::pair<
RandomAccessIterator, RandomAccessIterator >
>::RestrictedBoundedConcurrentQueue().

template<typename difference_type, typename OutputIterator> OutputIterator

__gnu_parallel::equally_split (difference_type n, thread_index_t num_threads, OutputIterator s) [inline] Function to split a sequence into parts of almost equal size.

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

Parameters:

n Number of elements
num_threads Number of parts
s Splitters

Returns:

End of splitter sequence, i. e. s+num_threads+1

Definition at line 54 of file equally_split.h.

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

template<typename difference_type> difference_type

__gnu_parallel::equally_split_point (difference_type n, thread_index_t num_threads, thread_index_t thread_no) [inline] Function to split a sequence into parts of almost equal size.

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

Parameters:

n Number of elements
num_threads Number of parts

Returns:

_SplittingAlgorithm point

Definition at line 79 of file equally_split.h.

Referenced by for_each_template_random_access_ed().

template<typename T> T __gnu_parallel::fetch_and_add (volatile T * ptr, T

addend) [inline]
Add a value to a variable, atomically.

Implementation is heavily platform-dependent.

Parameters:

ptr Pointer to a signed integer.
addend Value to add.

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

References fetch_and_add_32(), and fetch_and_add_64().

Referenced by __gnu_parallel::RestrictedBoundedConcurrentQueue<
std::pair< RandomAccessIterator, RandomAccessIterator >
>::push_front().

int32 __gnu_parallel::fetch_and_add_32 (volatile int32 * ptr, int32 addend)

[inline]
Add a value to a variable, atomically.

Implementation is heavily platform-dependent.

Parameters:

ptr Pointer to a 32-bit signed integer.
addend Value to add.

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

Referenced by fetch_and_add().

int64 __gnu_parallel::fetch_and_add_64 (volatile int64 * ptr, int64 addend)

[inline]
Add a value to a variable, atomically.

Implementation is heavily platform-dependent.

Parameters:

ptr Pointer to a 64-bit signed integer.
addend Value to add.

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

Referenced by fetch_and_add().

template<typename RandomAccessIterator1, typename RandomAccessIterator2,

typename Pred, typename Selector> std::pair<RandomAccessIterator1, RandomAccessIterator2> __gnu_parallel::find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector) [inline] Parallel std::find, switch for different algorithms.

Parameters:

begin1 Begin iterator of first sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence. Must have same length as first sequence.
pred Find predicate.
selector Functionality (e. g. std::find_if (), std::equal(),...)

Returns:

Place of finding in both sequences.

Definition at line 66 of file find.h.

References __gnu_parallel::_Settings::get(), and std::make_pair().

template<typename InputIterator, typename UserOp, typename Functionality,

typename Red, typename Result> UserOp __gnu_parallel::for_each_template_random_access (InputIterator begin, InputIterator end, UserOp user_op, Functionality & functionality, Red reduction, Result reduction_start, Result & output, typename std::iterator_traits< InputIterator >::difference_type bound, _Parallelism parallelism_tag) [inline] Chose the desired algorithm by evaluating parallelism_tag.

Parameters:

begin Begin iterator of input sequence.
end End iterator of input sequence.
user_op A user-specified functor (comparator, predicate, associative operator,...)
functionality functor to 'process' an element with user_op (depends on desired functionality, e. g. accumulate, for_each,...
reduction Reduction functor.
reduction_start Initial value for reduction. output Output iterator.
bound Maximum number of elements processed.
parallelism_tag Parallelization method

Definition at line 67 of file for_each.h.

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

template<typename RandomAccessIterator, typename Op, typename Fu, typename

Red, typename Result> Op
__gnu_parallel::for_each_template_random_access_ed (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu & f, Red r, Result base, Result & output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound) [inline] Embarrassingly parallel algorithm for random access iterators, using
hand-crafted parallelization by equal splitting the work.

Parameters:

begin Begin iterator of element sequence.
end End iterator of element sequence.
o User-supplied functor (comparator, predicate, adding functor,
...)
f Functor to 'process' an element with op (depends on desired
functionality, e. g. for std::for_each(), ...).
r Functor to 'add' a single result to the already processed
elements (depends on functionality).
base Base value for reduction.
output Pointer to position where final result is written to bound Maximum number of elements processed (e. g. for
std::count_n()).

Returns:

User-supplied functor (that may contain a part of the result).

Definition at line 73 of file par_loop.h.

References equally_split_point().

Referenced by for_each_template_random_access().

template<typename RandomAccessIterator, typename Op, typename Fu, typename

Red, typename Result> Op
__gnu_parallel::for_each_template_random_access_omp_loop (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu & f, Red r, Result base, Result & output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound) [inline] Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop.

Parameters:

begin Begin iterator of element sequence.
end End iterator of element sequence.
o User-supplied functor (comparator, predicate, adding functor,
etc.).
f Functor to 'process' an element with op (depends on desired
functionality, e. g. for std::for_each(), ...).
r Functor to 'add' a single result to the already processed
elements (depends on functionality).
base Base value for reduction.
output Pointer to position where final result is written to bound Maximum number of elements processed (e. g. for
std::count_n()).

Returns:

User-supplied functor (that may contain a part of the result).

Definition at line 73 of file omp_loop.h.

Referenced by for_each_template_random_access().

template<typename RandomAccessIterator, typename Op, typename Fu, typename

Red, typename Result> Op
__gnu_parallel::for_each_template_random_access_omp_loop_static (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu & f, Red r, Result base, Result & output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound) [inline] Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling.

Parameters:

begin Begin iterator of element sequence.
end End iterator of element sequence.
o User-supplied functor (comparator, predicate, adding functor,
...).
f Functor to 'process' an element with op (depends on desired
functionality, e. g. for std::for_each(), ...).
r Functor to 'add' a single result to the already processed
elements (depends on functionality).
base Base value for reduction.
output Pointer to position where final result is written to bound Maximum number of elements processed (e. g. for
std::count_n()).

Returns:

User-supplied functor (that may contain a part of the result).

Definition at line 73 of file omp_loop_static.h.

template<typename RandomAccessIterator, typename Op, typename Fu, typename

Red, typename Result> Op
__gnu_parallel::for_each_template_random_access_workstealing (RandomAccessIterator begin, RandomAccessIterator end, Op op, Fu & f, Red r, Result base, Result & output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound) [inline] Work stealing algorithm for random access iterators.

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

Parameters:

begin Begin iterator of element sequence.
end End iterator of element sequence.
op User-supplied functor (comparator, predicate, adding functor, ...).
f Functor to 'process' an element with op (depends on desired
functionality, e. g. for std::for_each(), ...).
r Functor to 'add' a single result to the already processed
elements (depends on functionality).
base Base value for reduction.
output Pointer to position where final result is written to bound Maximum number of elements processed (e. g. for
std::count_n()).

Returns:

User-supplied functor (that may contain a part of the result).

Definition at line 105 of file workstealing.h.

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

Referenced by for_each_template_random_access().

template<typename InputIterator, typename Comparator> bool

__gnu_parallel::is_sorted (InputIterator begin, InputIterator end, Comparator comp = std::less<typename std::iterator_traits<InputIterator>:: value_type>()) [inline] Check whether [begin, end) is sorted according to comp.

Parameters:

begin Begin iterator of sequence.
end End iterator of sequence.
comp Comparator.

Returns:

true if sorted, false otherwise.

Definition at line 57 of file checkers.h.

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

template<typename InputIterator, typename Comparator> bool

__gnu_parallel::is_sorted_failure (InputIterator begin, InputIterator end, InputIterator & first_failure, Comparator comp = std::less<typename std::iterator_traits<InputIterator>:: value_type>()) [inline]
Check whether [begin, end) is sorted according to comp. Prints the
position in case an unordered pair is found.

Parameters:

begin Begin iterator of sequence.
end End iterator of sequence.
first_failure The first failure is returned in this variable. comp Comparator.

Returns:

true if sorted, false otherwise.

Definition at line 95 of file checkers.h.

template<typename InputIterator, typename Comparator> bool

__gnu_parallel::is_sorted_print_failures (InputIterator begin, InputIterator end, Comparator comp = std::less<typename std::iterator_traits <InputIterator>::value_type>()) [inline] Check whether [begin, end) is sorted according to comp. Prints all
unordered pair, including the surrounding two elements.

Parameters:

begin Begin iterator of sequence.
end End iterator of sequence.
comp Comparator.

Returns:

true if sorted, false otherwise.

Definition at line 135 of file checkers.h.

template<typename InputIterator, typename FunctorType> size_t

__gnu_parallel::list_partition (const InputIterator begin, const InputIterator end, InputIterator * starts, size_t * lengths, const int num_parts, FunctorType & f, int oversampling = 0) [inline] Splits a sequence given by input iterators into parts of almost equal
size.

The function needs only one pass over the sequence.

Parameters:

begin Begin iterator of input sequence.
end End iterator of input sequence.
starts Start iterators for the resulting parts, dimension num_parts+1. For convenience, starts [num_parts] contains the end
iterator of the sequence.
lengths Length of the resulting parts.
num_parts Number of parts to split the sequence into. f Functor to be applied to each element by traversing it
oversampling Oversampling factor. If 0, then the partitions will differ in at most $ t{thrm{end} - thrm{begin}} $ elements.
Otherwise, the ratio between the longest and the shortest part is
bounded by $ 1/(thrm{oversampling}

Returns:

Length of the whole sequence.

Definition at line 106 of file list_partition.h.

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

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

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

Parameters:

n Argument.

Returns:

Returns 0 for argument 0.

Definition at line 112 of file base.h.

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

template<typename T> const T& __gnu_parallel::max (const T & a, const T &

b) [inline]
Equivalent to std::max.

Definition at line 158 of file base.h.

template<typename RandomAccessIterator, typename Comparator>

RandomAccessIterator __gnu_parallel::median_of_three_iterators (RandomAccessIterator a, RandomAccessIterator b, RandomAccessIterator c, Comparator & comp) [inline] Compute the median of three referenced elements, according to comp.

Parameters:

a First iterator.
b Second iterator.
c Third iterator.
comp Comparator.

Definition at line 450 of file base.h.

Referenced by qsb_divide().

template<typename RandomAccessIterator1, typename RandomAccessIterator2,

typename OutputIterator, typename _DifferenceTp, typename Comparator> OutputIterator __gnu_parallel::merge_advance (RandomAccessIterator1 & begin1, RandomAccessIterator1 end1, RandomAccessIterator2 & begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp) [inline] Merge routine being able to merge only the max_length smallest
elements.

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

Parameters:

begin1 Begin iterator of first sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
target Target begin iterator.
max_length Maximum number of elements to merge. comp Comparator.

Returns:

Output end iterator.

Definition at line 180 of file merge.h.

References _GLIBCXX_CALL, and merge_advance_movc().

Referenced by parallel_merge_advance(), and
sequential_multiway_merge().

template<typename RandomAccessIterator1, typename RandomAccessIterator2,

typename OutputIterator, typename _DifferenceTp, typename Comparator> OutputIterator __gnu_parallel::merge_advance_movc (RandomAccessIterator1 & begin1, RandomAccessIterator1 end1, RandomAccessIterator2 & begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp) [inline]
Merge routine being able to merge only the max_length smallest
elements.

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

Parameters:

begin1 Begin iterator of first sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
target Target begin iterator.
max_length Maximum number of elements to merge. comp Comparator.

Returns:

Output end iterator.

Definition at line 112 of file merge.h.

Referenced by merge_advance().

template<typename RandomAccessIterator1, typename RandomAccessIterator2,

typename OutputIterator, typename _DifferenceTp, typename Comparator> OutputIterator __gnu_parallel::merge_advance_usual (RandomAccessIterator1 & begin1, RandomAccessIterator1 end1, RandomAccessIterator2 & begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp) [inline]
Merge routine being able to merge only the max_length smallest
elements.

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

Parameters:

begin1 Begin iterator of first sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
target Target begin iterator.
max_length Maximum number of elements to merge. comp Comparator.

Returns:

Output end iterator.

Definition at line 63 of file merge.h.

template<typename T> const T& __gnu_parallel::min (const T & a, const T &

b) [inline]
Equivalent to std::min.

Definition at line 152 of file base.h.

Referenced by for_each_template_random_access_workstealing(), and
__gnu_cxx::random_sample_n().

template<typename RanSeqs, typename RankType, typename RankIterator,

typename Comparator> void __gnu_parallel::multiseq_partition (RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, RankIterator begin_offsets, Comparator comp = std::less< typename std::iterator_traits<typename std::iterator_traits<RanSeqs>::value_type:: first_type>::value_type>()) [inline]
Splits several sorted sequences at a certain global rank, resulting in a splitting point for each sequence. The sequences are passed via a
sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones
on the left side will be chosen from sequences with smaller number.

Parameters:

begin_seqs Begin of the sequence of iterator pairs. end_seqs End of the sequence of iterator pairs.
rank The global rank to partition at.
begin_offsets A random-access sequence begin where the result will be stored in. Each element of the sequence is an iterator that
points to the first element on the greater part of the respective
sequence.
comp The ordering functor, defaults to std::less<T>.

Definition at line 129 of file multiseq_selection.h.

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

Referenced by multiway_merge_exact_splitting().

template<typename T, typename RanSeqs, typename RankType, typename

Comparator> T __gnu_parallel::multiseq_selection (RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, RankType & offset, Comparator comp = std::less<T>()) [inline] Selects the element at a certain global rank from several sorted
sequences.

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

Parameters:

begin_seqs Begin of the sequence of iterator pairs. end_seqs End of the sequence of iterator pairs.
rank The global rank to partition at.
offset The rank of the selected element in the global subsequence of elements equal to the selected element. If the selected element is unique, this number is 0.
comp The ordering functor, defaults to std::less.

Definition at line 390 of file multiseq_selection.h.

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

template<typename RandomAccessIteratorPairIterator, typename

RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length) [inline] Multiway Merge Frontend.

Merge the sequences specified by seqs_begin and seqs_end into target.
seqs_begin and seqs_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the end of the same sequence in their second
entry.

Ties are broken arbitrarily. See stable_multiway_merge for a variant
that breaks ties by sequence number but is slower.

The first entries of the pairs (i.e. the begin iterators) will be moved forward.

The output sequence has to provide enough space for all elements that
are written to it.

This function will merge the input sequences:

· not stable

· parallel, depending on the input size and Settings

· using sampling for splitting

· not using sentinels

Example:

int sequences[10][10];
for (int i = 0; i < 10; ++i)

for (int j = 0; i < 10; ++j)

sequences[i][j] = j;

int out[33];
std::vector<std::pair<int*> > seqs;
for (int i = 0; i < 10; ++i)

{ seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }

multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);

See also:

stable_multiway_merge

Precondition:

All input sequences must be sorted.

Target must provide enough space to merge out length elements or
the number of elements in all sequences, whichever is smaller.

Postcondition:

[target, return value) contains merged elements from the input
sequences.

return value - target = min(length, number of elements in all
sequences).

Parameters:

RandomAccessIteratorPairIterator iterator over sequence of pairs of iterators
RandomAccessIteratorOut iterator over target sequence _DifferenceTp difference type for the sequence Comparator strict weak ordering type to compare elements in sequences
seqs_begin begin of sequence sequence
seqs_end end of sequence sequence
target target sequence to merge to.
comp strict weak ordering to use for element comparison.
length Maximum length to merge, possibly larger than the number of elements available.

Returns:

end iterator of output sequence

Definition at line 1491 of file multiway_merge.h.

References _GLIBCXX_CALL, _GLIBCXX_PARALLEL_CONDITION,
__gnu_parallel::_Settings::get(), multiway_merge_sampling_splitting(), parallel_multiway_merge(), and sequential_multiway_merge().

template<template< typename RAI, typename C > class iterator, typename

RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_3_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length) [inline]
Highly efficient 3-way merging procedure.

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

This works well for merging up to 4 sequences.

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

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

Parameters:

seqs_begin Begin iterator of iterator pair input sequence. seqs_end End iterator of iterator pair input sequence. target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, less equal than the total number of elements available.

Returns:

End iterator of output sequence.

Definition at line 296 of file multiway_merge.h.

References _GLIBCXX_CALL.

template<template< typename RAI, typename C > class iterator, typename

RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_4_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length) [inline]
Highly efficient 4-way merging procedure.

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

This works well for merging up to 4 sequences.

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

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

Parameters:

seqs_begin Begin iterator of iterator pair input sequence. seqs_end End iterator of iterator pair input sequence. target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, less equal than the total number of elements available.

Returns:

End iterator of output sequence.

Definition at line 416 of file multiway_merge.h.

References _GLIBCXX_CALL.

template<bool stable, typename RandomAccessIteratorIterator, typename

Comparator, typename difference_type> void __gnu_parallel::multiway_merge_exact_splitting (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp, difference_type length, difference_type total_length, std::vector< std::pair< difference_type, difference_type > > * pieces) [inline]
Exact splitting for parallel multiway-merge routine.

None of the passed sequences may be empty.

Definition at line 1190 of file multiway_merge.h.

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

Referenced by parallel_merge_advance().

template<typename LT, typename RandomAccessIteratorIterator, typename

RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length) [inline]
Multi-way merging procedure for a high branching factor, guarded case.

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

Stability is selected through the used LoserTree class LT.

At least one non-empty sequence is required.

Parameters:

seqs_begin Begin iterator of iterator pair input sequence. seqs_end End iterator of iterator pair input sequence. target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, less equal than the total number of elements available.

Returns:

End iterator of output sequence.

Definition at line 540 of file multiway_merge.h.

References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_LENGTH.

template<typename UnguardedLoserTree, typename

RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree_sentinel (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type & sentinel, Comparator comp, _DifferenceTp length) [inline] Multi-way merging procedure for a high branching factor, requiring
sentinels to exist.

Parameters:

stable The value must the same as for the used LoserTrees. UnguardedLoserTree Loser Tree variant to use for the unguarded merging.
GuardedLoserTree Loser Tree variant to use for the guarded merging. seqs_begin Begin iterator of iterator pair input sequence. seqs_end End iterator of iterator pair input sequence. target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, less equal than the total number of elements available.

Returns:

End iterator of output sequence.

Definition at line 712 of file multiway_merge.h.

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

template<typename LT, typename RandomAccessIteratorIterator, typename

RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3
__gnu_parallel::multiway_merge_loser_tree_unguarded (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type & sentinel, Comparator comp, _DifferenceTp length) [inline] Multi-way merging procedure for a high branching factor, unguarded
case.

Merging is done using the LoserTree class LT.

Stability is selected by the used LoserTrees.

Precondition:

No input will run out of elements during the merge.

Parameters:

seqs_begin Begin iterator of iterator pair input sequence. seqs_end End iterator of iterator pair input sequence. target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, less equal than the total number of elements available.

Returns:

End iterator of output sequence.

Definition at line 622 of file multiway_merge.h.

References _GLIBCXX_CALL.

Referenced by multiway_merge_loser_tree_sentinel().

template<bool stable, typename RandomAccessIteratorIterator, typename

Comparator, typename difference_type> void __gnu_parallel::multiway_merge_sampling_splitting (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp, difference_type length, difference_type total_length, std::vector< std::pair< difference_type, difference_type > > * pieces) [inline]
Sampling based splitting for parallel multiway-merge routine.

Definition at line 1108 of file multiway_merge.h.

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

Referenced by multiway_merge(), and multiway_merge_sentinels().

template<typename RandomAccessIteratorPairIterator, typename

RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length) [inline] Multiway Merge Frontend.

Merge the sequences specified by seqs_begin and seqs_end into target.
seqs_begin and seqs_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the end of the same sequence in their second
entry.

Ties are broken arbitrarily. See stable_multiway_merge for a variant
that breaks ties by sequence number but is slower.

The first entries of the pairs (i.e. the begin iterators) will be moved forward accordingly.

The output sequence has to provide enough space for all elements that
are written to it.

This function will merge the input sequences:

· not stable

· parallel, depending on the input size and Settings

· using sampling for splitting

· using sentinels

You have to take care that the element the end iterator points to is
readable and contains a value that is greater than any other nonsentinel value in all sequences.

Example:

int sequences[10][11];
for (int i = 0; i < 10; ++i)

for (int j = 0; i < 11; ++j)

sequences[i][j] = j; // last one is sentinel!

int out[33];
std::vector<std::pair<int*> > seqs;
for (int i = 0; i < 10; ++i)

{ seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }

multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);

Precondition:

All input sequences must be sorted.

Target must provide enough space to merge out length elements or
the number of elements in all sequences, whichever is smaller.

For each i, seqs_begin[i].second must be the end marker of the
sequence, but also reference the one more sentinel element.

Postcondition:

[target, return value) contains merged elements from the input
sequences.

return value - target = min(length, number of elements in all
sequences).

See also:

stable_multiway_merge_sentinels

Parameters:

RandomAccessIteratorPairIterator iterator over sequence of pairs of iterators
RandomAccessIteratorOut iterator over target sequence _DifferenceTp difference type for the sequence Comparator strict weak ordering type to compare elements in sequences
seqs_begin begin of sequence sequence
seqs_end end of sequence sequence
target target sequence to merge to.
comp strict weak ordering to use for element comparison.
length Maximum length to merge, possibly larger than the number of elements available.

Returns:

end iterator of output sequence

Definition at line 1792 of file multiway_merge.h.

References _GLIBCXX_CALL, _GLIBCXX_PARALLEL_CONDITION,
__gnu_parallel::_Settings::get(), multiway_merge_sampling_splitting(), parallel_multiway_merge(), and sequential_multiway_merge().

template<typename RandomAccessIterator, typename Comparator> bool

__gnu_parallel::operator< (unguarded_iterator< RandomAccessIterator, Comparator > & bi1, unguarded_iterator< RandomAccessIterator, Comparator > & bi2) [inline] Compare two elements referenced by unguarded iterators.

Parameters:

bi1 First iterator.
bi2 Second iterator.

Returns:

True if less.

Definition at line 245 of file multiway_merge.h.

template<typename RandomAccessIterator, typename Comparator> bool

__gnu_parallel::operator< (guarded_iterator< RandomAccessIterator, Comparator > & bi1, guarded_iterator< RandomAccessIterator, Comparator > & bi2) [inline]
Compare two elements referenced by guarded iterators.

Parameters:

bi1 First iterator.
bi2 Second iterator.

Returns:

True if less.

Definition at line 150 of file multiway_merge.h.

template<typename RandomAccessIterator, typename Comparator> bool

__gnu_parallel::operator<= (unguarded_iterator< RandomAccessIterator, Comparator > & bi1, unguarded_iterator< RandomAccessIterator, Comparator > & bi2) [inline] Compare two elements referenced by unguarded iterators.

Parameters:

bi1 First iterator.
bi2 Second iterator.

Returns:

True if less equal.

Definition at line 258 of file multiway_merge.h.

template<typename RandomAccessIterator, typename Comparator> bool

__gnu_parallel::operator<= (guarded_iterator< RandomAccessIterator, Comparator > & bi1, guarded_iterator< RandomAccessIterator, Comparator > & bi2) [inline]
Compare two elements referenced by guarded iterators.

Parameters:

bi1 First iterator.
bi2 Second iterator.

Returns:

True if less equal.

Definition at line 166 of file multiway_merge.h.

template<typename RandomAccessIterator1, typename RandomAccessIterator3,

typename Comparator> RandomAccessIterator3 __gnu_parallel::parallel_merge_advance (RandomAccessIterator1 & begin1, RandomAccessIterator1 end1, RandomAccessIterator1 & begin2, RandomAccessIterator1 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp) [inline] Parallel merge routine being able to merge only the max_length smallest elements.

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

Parameters:

begin1 Begin iterator of first sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
target Target begin iterator.
max_length Maximum number of elements to merge. comp Comparator.

Returns:

Output end iterator.

Definition at line 234 of file merge.h.

References std::make_pair(), multiway_merge_exact_splitting(), and
parallel_multiway_merge().

template<typename RandomAccessIterator1, typename RandomAccessIterator2,

typename RandomAccessIterator3, typename Comparator> RandomAccessIterator3 __gnu_parallel::parallel_merge_advance (RandomAccessIterator1 & begin1, RandomAccessIterator1 end1, RandomAccessIterator2 & begin2, RandomAccessIterator2 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp) [inline]
Merge routine fallback to sequential in case the iterators of the two
input sequences are of different type.

Parameters:

begin1 Begin iterator of first sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
target Target begin iterator.
max_length Maximum number of elements to merge. comp Comparator.

Returns:

Output end iterator.

Definition at line 204 of file merge.h.

References merge_advance().

template<bool stable, bool sentinels, typename

RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Splitter, typename Comparator> RandomAccessIterator3 __gnu_parallel::parallel_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, Splitter splitter, _DifferenceTp length) [inline] Parallel multi-way merge routine.

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

Must not be called if the number of sequences is 1.

Parameters:

Splitter functor to split input (either exact or sampling based) seqs_begin Begin iterator of iterator pair input sequence. seqs_end End iterator of iterator pair input sequence. target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, possibly larger than the number of elements available.
stable Stable merging incurs a performance penalty.
sentinel Ignored.

Returns:

End iterator of output sequence.

Definition at line 1297 of file multiway_merge.h.

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

Referenced by multiway_merge(), multiway_merge_sentinels(), and
parallel_merge_advance().

template<typename RandomAccessIterator, typename Comparator> void

__gnu_parallel::parallel_nth_element (RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, Comparator comp) [inline]
Parallel implementation of std::nth_element().

Parameters:

begin Begin iterator of input sequence.
nth Iterator of element that must be in position afterwards. end End iterator of input sequence.
comp Comparator.

Definition at line 336 of file partition.h.

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

Referenced by parallel_partial_sort().

template<typename RandomAccessIterator, typename Comparator> void

__gnu_parallel::parallel_partial_sort (RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, Comparator comp) [inline]
Parallel implementation of std::partial_sort().

Parameters:

begin Begin iterator of input sequence.
middle Sort until this position.
end End iterator of input sequence.
comp Comparator.

Definition at line 423 of file partition.h.

References parallel_nth_element().

template<typename InputIterator, typename OutputIterator, typename

BinaryOperation> OutputIterator __gnu_parallel::parallel_partial_sum (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op) [inline] Parallel partial sum front-end.

Parameters:

begin Begin iterator of input sequence.
end End iterator of input sequence.
result Begin iterator of output sequence.
bin_op Associative binary function.

Returns:

End iterator of output sequence.

Definition at line 202 of file partial_sum.h.

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

template<typename InputIterator, typename OutputIterator, typename

BinaryOperation> OutputIterator __gnu_parallel::parallel_partial_sum_basecase (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename std::iterator_traits< InputIterator >::value_type value) [inline]
Base case prefix sum routine.

Parameters:

begin Begin iterator of input sequence.
end End iterator of input sequence.
result Begin iterator of output sequence.
bin_op Associative binary function.
value Start value. Must be passed since the neutral element is unknown in general.

Returns:

End iterator of output sequence.

Definition at line 64 of file partial_sum.h.

Referenced by parallel_partial_sum_linear().

template<typename InputIterator, typename OutputIterator, typename

BinaryOperation> OutputIterator __gnu_parallel::parallel_partial_sum_linear (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename std::iterator_traits< InputIterator >::difference_type n) [inline]
Parallel partial sum implementation, two-phase approach, no recursion.

Parameters:

begin Begin iterator of input sequence.
end End iterator of input sequence.
result Begin iterator of output sequence.
bin_op Associative binary function.
n Length of sequence.
num_threads Number of threads to use.

Returns:

End iterator of output sequence.

Definition at line 96 of file partial_sum.h.

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

Referenced by parallel_partial_sum().

template<typename RandomAccessIterator, typename Predicate>

std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::parallel_partition (RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, thread_index_t num_threads) [inline]
Parallel implementation of std::partition.

Parameters:

begin Begin iterator of input sequence to split.
end End iterator of input sequence to split.
pred Partition predicate, possibly including some kind of pivot. num_threads Maximum number of threads to use for this task.

Returns:

Number of elements not fulfilling the predicate.

Definition at line 61 of file partition.h.

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

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

template<typename RandomAccessIterator, typename RandomNumberGenerator>

void __gnu_parallel::parallel_random_shuffle (RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator rng = random_number()) [inline] Parallel random public call.

Parameters:

begin Begin iterator of sequence.
end End iterator of sequence.
rng Random number generator to use.

Definition at line 513 of file random_shuffle.h.

References parallel_random_shuffle_drs().

template<typename RandomAccessIterator, typename RandomNumberGenerator>

void __gnu_parallel::parallel_random_shuffle_drs (RandomAccessIterator begin, RandomAccessIterator end, typename std::iterator_traits< RandomAccessIterator >::difference_type n, thread_index_t num_threads, RandomNumberGenerator & rng) [inline] Main parallel random shuffle step.

Parameters:

begin Begin iterator of sequence.
end End iterator of sequence.
n Length of sequence.
num_threads Number of threads to use.
rng Random number generator to use.

Definition at line 264 of file random_shuffle.h.

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

Referenced by parallel_random_shuffle().

template<typename RandomAccessIterator, typename RandomNumberGenerator>

void __gnu_parallel::parallel_random_shuffle_drs_pu (DRSSorterPU< RandomAccessIterator, RandomNumberGenerator > * pus) [inline] Random shuffle code executed by each thread.

Parameters:

pus Array of thread-local data records.

Definition at line 128 of file random_shuffle.h.

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

Referenced by parallel_random_shuffle_drs().

template<typename RandomAccessIterator, typename Comparator> void

__gnu_parallel::parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, bool stable) [inline] Choose a parallel sorting algorithm.

Parameters:

begin Begin iterator of input sequence.
end End iterator of input sequence.
comp Comparator.
stable Sort stable.

Definition at line 73 of file sort.h.

References _GLIBCXX_CALL, __gnu_parallel::_Settings::get(),
parallel_sort_qs(), parallel_sort_qsb(),
__gnu_parallel::_Settings::sort_algorithm, and
__gnu_parallel::_Settings::sort_splitting.

template<bool stable, bool exact, typename RandomAccessIterator, typename

Comparator> void __gnu_parallel::parallel_sort_mwms (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads) [inline] PMWMS main call.

Parameters:

begin Begin iterator of sequence.
end End iterator of sequence.
comp Comparator.
n Length of sequence.
num_threads Number of threads to use.

Definition at line 404 of file multiway_mergesort.h.

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

template<bool stable, bool exact, typename RandomAccessIterator, typename

Comparator> void __gnu_parallel::parallel_sort_mwms_pu (PMWMSSortingData< RandomAccessIterator > * sd, Comparator & comp) [inline]
PMWMS code executed by each thread.

Parameters:

sd Pointer to algorithm data.
comp Comparator.

Definition at line 321 of file multiway_mergesort.h.

References __gnu_parallel::_Settings::get(), std::make_pair(),
__gnu_parallel::PMWMSSortingData< RandomAccessIterator >::num_threads, __gnu_parallel::PMWMSSortingData< RandomAccessIterator >::pieces,
__gnu_parallel::_Settings::sort_mwms_oversampling,
__gnu_parallel::PMWMSSortingData< RandomAccessIterator >::source,
__gnu_parallel::PMWMSSortingData< RandomAccessIterator >::starts,
__gnu_parallel::PMWMSSortingData< RandomAccessIterator >::temporary,
and std::uninitialized_copy().

template<typename RandomAccessIterator, typename Comparator> void

__gnu_parallel::parallel_sort_qs (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, typename std::iterator_traits< RandomAccessIterator >::difference_type n, int num_threads) [inline]
Unbalanced quicksort main call.

Parameters:

begin Begin iterator of input sequence.
end End iterator input sequence, ignored.
comp Comparator.
n Length of input sequence.
num_threads Number of threads that are allowed to work on this part.

Definition at line 163 of file quicksort.h.

References _GLIBCXX_CALL, and parallel_sort_qs_conquer().

Referenced by parallel_sort().

template<typename RandomAccessIterator, typename Comparator> void

__gnu_parallel::parallel_sort_qs_conquer (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads) [inline]
Unbalanced quicksort conquer step.

Parameters:

begin Begin iterator of subsequence.
end End iterator of subsequence.
comp Comparator.
num_threads Number of threads that are allowed to work on this part.

Definition at line 106 of file quicksort.h.

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

Referenced by parallel_sort_qs().

template<typename RandomAccessIterator, typename Comparator>

std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::parallel_sort_qs_divide (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, typename std::iterator_traits< RandomAccessIterator >::difference_type pivot_rank, typename std::iterator_traits< RandomAccessIterator >::difference_type num_samples, thread_index_t num_threads) [inline] Unbalanced quicksort divide step.

Parameters:

begin Begin iterator of subsequence.
end End iterator of subsequence.
comp Comparator.
pivot_rank Desired rank of the pivot.
num_samples Choose pivot from that many samples. num_threads Number of threads that are allowed to work on this part.

Definition at line 57 of file quicksort.h.

References std::min(), and parallel_partition().

Referenced by parallel_sort_qs_conquer().

template<typename RandomAccessIterator, typename Comparator> void

__gnu_parallel::parallel_sort_qsb (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, typename std::iterator_traits< RandomAccessIterator >::difference_type n, thread_index_t num_threads) [inline] Top-level quicksort routine.

Parameters:

begin Begin iterator of sequence.
end End iterator of sequence.
comp Comparator.
n Length of the sequence to sort.
num_threads Number of threads that are allowed to work on this part.

Definition at line 424 of file balanced_quicksort.h.

References _GLIBCXX_CALL, log2(), std::make_pair(), and qsb_conquer().

Referenced by parallel_sort().

template<typename InputIterator, class OutputIterator> OutputIterator

__gnu_parallel::parallel_unique_copy (InputIterator first, InputIterator last, OutputIterator result) [inline] Parallel std::unique_copy(), without explicit equality predicate.

Parameters:

first Begin iterator of input sequence.
last End iterator of input sequence.
result Begin iterator of result sequence.

Returns:

End iterator of result sequence.

Definition at line 187 of file unique_copy.h.

References parallel_unique_copy().

template<typename InputIterator, class OutputIterator, class

BinaryPredicate> OutputIterator __gnu_parallel::parallel_unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred) [inline] Parallel std::unique_copy(), w/o explicit equality predicate.

Parameters:

first Begin iterator of input sequence.
last End iterator of input sequence.
result Begin iterator of result sequence.
binary_pred Equality predicate.

Returns:

End iterator of result sequence.

Definition at line 57 of file unique_copy.h.

References _GLIBCXX_CALL, and equally_split().

Referenced by parallel_unique_copy().

template<typename RandomAccessIterator, typename Comparator> void

__gnu_parallel::qsb_conquer (QSBThreadLocal< RandomAccessIterator > ** tls, RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t iam, thread_index_t num_threads, bool parent_wait) [inline]
Quicksort conquer step.

Parameters:

tls Array of thread-local storages.
begin Begin iterator of subsequence.
end End iterator of subsequence.
comp Comparator.
iam Number of the thread processing this function.
num_threads Number of threads that are allowed to work on this part.

Definition at line 169 of file balanced_quicksort.h.

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

Referenced by parallel_sort_qsb().

template<typename RandomAccessIterator, typename Comparator>

std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::qsb_divide (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t num_threads) [inline]
Balanced quicksort divide step.

Parameters:

begin Begin iterator of subsequence.
end End iterator of subsequence.
comp Comparator.
num_threads Number of threads that are allowed to work on this part.

Precondition:

(end-begin)>=1

Definition at line 106 of file balanced_quicksort.h.

References median_of_three_iterators(), and parallel_partition().

Referenced by qsb_conquer().

template<typename RandomAccessIterator, typename Comparator> void

__gnu_parallel::qsb_local_sort_with_helping (QSBThreadLocal< RandomAccessIterator > ** tls, Comparator & comp, int iam, bool wait) [inline]
Quicksort step doing load-balanced local sort.

Parameters:

tls Array of thread-local storages.
comp Comparator.
iam Number of the thread processing this function.

Definition at line 245 of file balanced_quicksort.h.

References _GLIBCXX_ASSERTIONS, __gnu_parallel::QSBThreadLocal<
RandomAccessIterator >::elements_leftover,
__gnu_parallel::_Settings::get(), __gnu_parallel::QSBThreadLocal<
RandomAccessIterator >::initial, __gnu_parallel::QSBThreadLocal<
RandomAccessIterator >::leftover_parts, std::make_pair(),
__gnu_parallel::QSBThreadLocal< RandomAccessIterator >::num_threads,
__gnu_parallel::_Settings::sort_qsb_base_case_maximal_n, and yield().

Referenced by qsb_conquer().

template<typename RandomNumberGenerator> int

__gnu_parallel::random_number_pow2 (int logp, RandomNumberGenerator & rng) [inline]
Generate a random number in [0,2^logp).

Parameters:

logp Logarithm (basis 2) of the upper range bound.
rng Random number generator to use.

Definition at line 121 of file random_shuffle.h.

Referenced by parallel_random_shuffle_drs_pu(), and
sequential_random_shuffle().

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

Round up to the next greater power of 2.

Parameters:

x Integer to round up

Definition at line 247 of file random_shuffle.h.

References log2().

Referenced by parallel_random_shuffle_drs(), and
sequential_random_shuffle().

template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,

typename Pred> _RandomAccessIterator1 __gnu_parallel::search_template (_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1, _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2, Pred pred) [inline]
Parallel std::search.

Parameters:

begin1 Begin iterator of first sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
pred Find predicate.

Returns:

Place of finding in first sequences.

Definition at line 88 of file search.h.

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

template<bool stable, bool sentinels, typename

RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::sequential_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type & sentinel, Comparator comp, _DifferenceTp length) [inline] Sequential multi-way merging switch.

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

Parameters:

seqs_begin Begin iterator of iterator pair input sequence. seqs_end End iterator of iterator pair input sequence. target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, possibly larger than the number of elements available.
stable Stable merging incurs a performance penalty.
sentinel The sequences have a sentinel element.

Returns:

End iterator of output sequence.

Definition at line 986 of file multiway_merge.h.

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

Referenced by multiway_merge(), and multiway_merge_sentinels().

template<typename RandomAccessIterator, typename RandomNumberGenerator>

void __gnu_parallel::sequential_random_shuffle (RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator & rng) [inline] Sequential cache-efficient random shuffle.

Parameters:

begin Begin iterator of sequence.
end End iterator of sequence.
rng Random number generator to use.

Definition at line 400 of file random_shuffle.h.

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

Referenced by parallel_random_shuffle_drs().

template<typename InputIterator> void __gnu_parallel::shrink (std::vector<

InputIterator > & os_starts, size_t & count_to_two, size_t & range_length) [inline]
Combines two ranges into one and thus halves the number of ranges.

Parameters:

os_starts Start positions worked on (oversampled). count_to_two Counts up to 2.
range_length Current length of a chunk.

Definition at line 76 of file list_partition.h.

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

Referenced by shrink_and_double().

template<typename InputIterator> void __gnu_parallel::shrink_and_double

(std::vector< InputIterator > & os_starts, size_t & count_to_two, size_t & range_length, const bool make_twice) [inline] Shrinks and doubles the ranges.

Parameters:

os_starts Start positions worked on (oversampled). count_to_two Counts up to 2.
range_length Current length of a chunk.
make_twice Whether the os_starts is allowed to be grown or not

Definition at line 56 of file list_partition.h.

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

Referenced by list_partition().

void __gnu_parallel::yield () [inline]

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

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

Referenced by for_each_template_random_access_workstealing(), and
qsb_local_sort_with_helping().

Variable Documentation

const int __gnu_parallel::lcas_t_bits [static]

Number of bits of lcas_t.

Definition at line 155 of file types.h.

Referenced by decode2(), and encode2().

const lcas_t __gnu_parallel::lcas_t_mask [static]

lcas_t with the right half of bits set to 1.

Definition at line 158 of file types.h.

Referenced by decode2().

Author

Generated automatically by Doxygen for libstdc++ from the source code.

libstdc++ 31 Dec 2008 __gnu_parallel(3)