--- name: "__gnu_parallel" section: "3" platform: "linux" package: "gcc" version: "16.2.1+r23+gd564253eb6c8-1" release: "Arch Linux 2026-11-01" platforms: ["linux"] url: "https://new.carta.tech/__gnu_parallel" --- # \_\_gnu\_parallel(3) GNU parallel code for public use. ## NAME \_\_gnu\_parallel - GNU parallel code for public use. ## SYNOPSIS ### Classes 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. 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 **\_\_count\_if\_selector**\ std::count\_if () selector. struct **\_\_count\_selector**\ std::count() selector. 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 **\_\_identity\_selector**\ Selector that just returns the passed iterator. struct **\_\_inner\_product\_selector**\ std::inner\_product() selector. 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 **\_\_multiway\_merge\_3\_variant\_sentinel\_switch**\ Switch for 3-way merging with \_\_sentinels turned off. struct **\_\_multiway\_merge\_3\_variant\_sentinel\_switch\< true, \_RAIterIterator, \_RAIter3, \_DifferenceTp, \_Compare \>**\ 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, \_RAIterIterator, \_RAIter3, \_DifferenceTp, \_Compare \>**\ 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, \_RAIterIterator, \_RAIter3, \_DifferenceTp, \_Compare \>**\ Switch for k-way merging with \_\_sentinels turned off. struct **\_\_replace\_if\_selector**\ std::replace() selector. struct **\_\_replace\_selector**\ std::replace() selector. 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::unary\_negate, but giving the argument types explicitly. 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 **\_DummyReduct**\ Reduction function doing nothing. class **\_EqualFromLess**\ Constructs predicate for equality from strict weak ordering predicate. struct **\_EqualTo**\ Similar to std::equal\_to, but allows two different types. class **\_GuardedIterator**\ \_Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. class **\_IteratorPair**\ A pair of iterators. The usual iterator operations are applied to both child iterators. class **\_IteratorTriple**\ 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 **\_LexicographicReverse**\ Compare \_\_a pair of types lexicographically, descending. class **\_LoserTree**\ Stable \_LoserTree variant. class **\_LoserTree\< false, \_Tp, \_Compare \>**\ Unstable \_LoserTree variant. class **\_LoserTreeBase**\ Guarded loser/tournament tree. class **\_LoserTreePointer**\ Stable \_LoserTree implementation. class **\_LoserTreePointer\< false, \_Tp, \_Compare \>**\ Unstable \_LoserTree implementation. class **\_LoserTreePointerBase**\ Base class of \_Loser Tree implementation using pointers. class **\_LoserTreePointerUnguarded**\ Stable unguarded \_LoserTree variant storing pointers. class **\_LoserTreePointerUnguarded\< false, \_Tp, \_Compare \>**\ Unstable unguarded \_LoserTree variant storing pointers. class **\_LoserTreePointerUnguardedBase**\ Unguarded loser tree, keeping only pointers to the elements in the tree structure. struct **\_LoserTreeTraits**\ Traits for determining whether the loser tree should use pointers or copies. class **\_LoserTreeUnguarded**\ Stable implementation of unguarded \_LoserTree. class **\_LoserTreeUnguarded\< false, \_Tp, \_Compare \>**\ Non-Stable implementation of unguarded \_LoserTree. class **\_LoserTreeUnguardedBase**\ Base class for unguarded \_LoserTree implementation. struct **\_Multiplies**\ Similar to std::multiplies, but allows two different types. struct **\_Nothing**\ Functor doing nothing. struct **\_Piece**\ Subsequence description. struct **\_Plus**\ Similar to std::plus, but allows two different types. struct **\_PMWMSSortingData**\ Data accessed by all threads. class **\_PseudoSequence**\ Sequence that conceptually consists of multiple copies of the same element. The copies are not stored explicitly, of course. class **\_PseudoSequenceIterator**\ \_Iterator associated with \_\_gnu\_parallel::\_PseudoSequence. If features the usual random-access iterator functionality. struct **\_QSBThreadLocal**\ Information local to one thread in the parallel quicksort run. class **\_RandomNumber**\ Random number generator, based on the Mersenne twister. 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 **\_SamplingSorter**\ Stable sorting functor. struct **\_SamplingSorter\< false, \_RAIter, \_StrictWeakOrdering \>**\ Non-\_\_stable sorting functor. struct **\_Settings**\ class \_Settings Run-time settings for the parallel mode including all tunable parameters. struct **\_SplitConsistently**\ Split consistently. struct **\_SplitConsistently\< false, \_RAIter, \_Compare, \_SortingPlacesIterator \>**\ Split by sampling. struct **\_SplitConsistently\< true, \_RAIter, \_Compare, \_SortingPlacesIterator \>**\ Split by exact splitting. struct **balanced\_quicksort\_tag**\ Forces parallel sorting using balanced quicksort at compile time. struct **balanced\_tag**\ Recommends parallel execution using dynamic load-balancing at compile time. struct **constant\_size\_blocks\_tag**\ Selects the constant block size variant for std::find(). struct **default\_parallel\_tag**\ Recommends parallel execution using the default parallel algorithm. struct **equal\_split\_tag**\ Selects the equal splitting variant for std::find(). struct **exact\_tag**\ Forces parallel merging with exact splitting, at compile time. struct **find\_tag**\ Base class for for std::find() variants. struct **growing\_blocks\_tag**\ Selects the growing block size variant for std::find(). struct **multiway\_mergesort\_exact\_tag**\ Forces parallel sorting using multiway mergesort with exact splitting at compile time. struct **multiway\_mergesort\_sampling\_tag**\ Forces parallel sorting using multiway mergesort with splitting by sampling at compile time. struct **multiway\_mergesort\_tag**\ Forces parallel sorting using multiway mergesort at compile time. struct **omp\_loop\_static\_tag**\ Recommends parallel execution using OpenMP static load-balancing at compile time. struct **omp\_loop\_tag**\ Recommends parallel execution using OpenMP dynamic load-balancing at compile time. struct **parallel\_tag**\ Recommends parallel execution at compile time, optionally using a user-specified number of threads. struct **quicksort\_tag**\ Forces parallel sorting using unbalanced quicksort at compile time. struct **sampling\_tag**\ Forces parallel merging with exact splitting, at compile time. struct **sequential\_tag**\ Forces sequential execution at compile time. struct **unbalanced\_tag**\ Recommends parallel execution using static load-balancing at compile time. ### Typedefs typedef unsigned short **\_BinIndex**\ Type to hold the index of a bin. typedef int64\_t **\_CASable**\ Longest compare-and-swappable integer type on this platform. typedef uint64\_t **\_SequenceIndex**\ Unsigned integer to index \_\_elements. The total number of elements for each algorithm must fit into this type. typedef uint16\_t **\_ThreadIndex**\ Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit into this type. ### Enumerations enum **\_AlgorithmStrategy** { **heuristic**, **force\_sequential**, **force\_parallel** }\ Strategies for run-time algorithm selection: enum **\_FindAlgorithm** { **GROWING\_BLOCKS**, **CONSTANT\_SIZE\_BLOCKS**, **EQUAL\_SPLIT** }\ Find algorithms: enum **\_MultiwayMergeAlgorithm** { **LOSER\_TREE** }\ Merging algorithms: enum **\_Parallelism** { **sequential**, **parallel\_unbalanced**, **parallel\_balanced**, **parallel\_omp\_loop**, **parallel\_omp\_loop\_static**, **parallel\_taskqueue** }\ Run-time equivalents for the compile-time tags. enum **\_PartialSumAlgorithm** { **RECURSIVE**, **LINEAR** }\ Partial sum algorithms: recursive, linear. enum **\_SortAlgorithm** { **MWMS**, **QS**, **QS\_BALANCED** }\ Sorting algorithms: enum **\_SplittingAlgorithm** { **SAMPLING**, **EXACT** }\ Sorting/merging algorithms: sampling, \_\_exact. ### Functions template\ \_Tp **\_\_add\_omp** (volatile \_Tp \*\_\_ptr, \_Tp \_\_addend)\ template\ void **\_\_calc\_borders** (\_RAIter \_\_elements, \_DifferenceTp \_\_length, \_DifferenceTp \*\_\_off)\ Precalculate \_\_advances for Knuth-Morris-Pratt algorithm. template\ bool **\_\_cas\_omp** (volatile \_Tp \*\_\_ptr, \_Tp \_\_comparand, \_Tp \_\_replacement)\ template\ bool **\_\_compare\_and\_swap** (volatile \_Tp \*\_\_ptr, \_Tp \_\_comparand, \_Tp \_\_replacement)\ Compare-and-swap. template\ \_OutputIterator **\_\_copy\_tail** (**std::pair**\< \_IIter, \_IIter \> \_\_b, **std::pair**\< \_IIter, \_IIter \> \_\_e, \_OutputIterator \_\_r)\ void **\_\_decode2** (**\_CASable** \_\_x, int &\_\_a, int &\_\_b)\ Decode two integers from one gnu\_parallel::\_CASable. template\ void **\_\_determine\_samples** (**\_PMWMSSortingData**\< \_RAIter \> \*\_\_sd, \_DifferenceTp \_\_num\_samples)\ Select \_M\_samples from a sequence. **\_CASable** **\_\_encode2** (int \_\_a, int \_\_b)\ Encode two integers into one gnu\_parallel::\_CASable. template\ \_OutputIterator **\_\_equally\_split** (\_DifferenceType \_\_n, **\_ThreadIndex** \_\_num\_threads, \_OutputIterator \_\_s)\ function to split a sequence into parts of almost equal size. template\ \_DifferenceType **\_\_equally\_split\_point** (\_DifferenceType \_\_n, **\_ThreadIndex** \_\_num\_threads, **\_ThreadIndex** \_\_thread\_no)\ function to split a sequence into parts of almost equal size. template\ \_Tp **\_\_fetch\_and\_add** (volatile \_Tp \*\_\_ptr, \_Tp \_\_addend)\ Add a value to a variable, atomically. template\ **std::pair**\< \_RAIter1, \_RAIter2 \> **\_\_find\_template** (\_RAIter1 \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 \_\_begin2, \_Pred \_\_pred, \_Selector \_\_selector)\ Parallel std::find, switch for different algorithms. template\ **std::pair**\< \_RAIter1, \_RAIter2 \> **\_\_find\_template** (\_RAIter1 \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 \_\_begin2, \_Pred \_\_pred, \_Selector \_\_selector, **constant\_size\_blocks\_tag**)\ Parallel std::find, constant block size variant. template\ **std::pair**\< \_RAIter1, \_RAIter2 \> **\_\_find\_template** (\_RAIter1 \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 \_\_begin2, \_Pred \_\_pred, \_Selector \_\_selector, **equal\_split\_tag**)\ Parallel std::find, equal splitting variant. template\ **std::pair**\< \_RAIter1, \_RAIter2 \> **\_\_find\_template** (\_RAIter1 \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 \_\_begin2, \_Pred \_\_pred, \_Selector \_\_selector, **growing\_blocks\_tag**)\ Parallel std::find, growing block size variant. template\ \_UserOp **\_\_for\_each\_template\_random\_access** (\_IIter \_\_begin, \_IIter \_\_end, \_UserOp \_\_user\_op, \_Functionality &\_\_functionality, \_Red \_\_reduction, \_Result \_\_reduction\_start, \_Result &\_\_output, typename **std::iterator\_traits**\< \_IIter \>::difference\_type \_\_bound, **\_Parallelism** \_\_parallelism\_tag)\ Chose the desired algorithm by evaluating \_\_parallelism\_tag. template\ \_Op **\_\_for\_each\_template\_random\_access\_ed** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Op \_\_o, \_Fu &\_\_f, \_Red \_\_r, \_Result \_\_base, \_Result &\_\_output, typename **std::iterator\_traits**\< \_RAIter \>::difference\_type \_\_bound)\ Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work. template\ \_Op **\_\_for\_each\_template\_random\_access\_omp\_loop** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Op \_\_o, \_Fu &\_\_f, \_Red \_\_r, \_Result \_\_base, \_Result &\_\_output, typename **std::iterator\_traits**\< \_RAIter \>::difference\_type \_\_bound)\ Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop. template\ \_Op **\_\_for\_each\_template\_random\_access\_omp\_loop\_static** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Op \_\_o, \_Fu &\_\_f, \_Red \_\_r, \_Result \_\_base, \_Result &\_\_output, typename **std::iterator\_traits**\< \_RAIter \>::difference\_type \_\_bound)\ Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling. template\ \_Op **\_\_for\_each\_template\_random\_access\_workstealing** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Op \_\_op, \_Fu &\_\_f, \_Red \_\_r, \_Result \_\_base, \_Result &\_\_output, typename **std::iterator\_traits**\< \_RAIter \>::difference\_type \_\_bound)\ Work stealing algorithm for random access iterators. **\_ThreadIndex** **\_\_get\_max\_threads** ()\ bool **\_\_is\_parallel** (const **\_Parallelism** \_\_p)\ template\ bool **\_\_is\_sorted** (\_IIter \_\_begin, \_IIter \_\_end, \_Compare \_\_comp)\ Check whether \[\_\_begin, \_\_end) is sorted according to \_\_comp. template\ \_RAIter **\_\_median\_of\_three\_iterators** (\_RAIter \_\_a, \_RAIter \_\_b, \_RAIter \_\_c, \_Compare \_\_comp)\ Compute the median of three referenced elements, according to \_\_comp. template\ \_OutputIterator **\_\_merge\_advance** (\_RAIter1 &\_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 &\_\_begin2, \_RAIter2 \_\_end2, \_OutputIterator \_\_target, \_DifferenceTp \_\_max\_length, \_Compare \_\_comp)\ Merge routine being able to merge only the \_\_max\_length smallest elements. template\ \_OutputIterator **\_\_merge\_advance\_movc** (\_RAIter1 &\_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 &\_\_begin2, \_RAIter2 \_\_end2, \_OutputIterator \_\_target, \_DifferenceTp \_\_max\_length, \_Compare \_\_comp)\ Merge routine being able to merge only the \_\_max\_length smallest elements. template\ \_OutputIterator **\_\_merge\_advance\_usual** (\_RAIter1 &\_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 &\_\_begin2, \_RAIter2 \_\_end2, \_OutputIterator \_\_target, \_DifferenceTp \_\_max\_length, \_Compare \_\_comp)\ Merge routine being able to merge only the \_\_max\_length smallest elements. template\ \_RAIter3 **\_\_parallel\_merge\_advance** (\_RAIter1 &\_\_begin1, \_RAIter1 \_\_end1, \_RAIter1 &\_\_begin2, \_RAIter1 \_\_end2, \_RAIter3 \_\_target, typename **std::iterator\_traits**\< \_RAIter1 \>::difference\_type \_\_max\_length, \_Compare \_\_comp)\ Parallel merge routine being able to merge only the \_\_max\_length smallest elements. template\ \_RAIter3 **\_\_parallel\_merge\_advance** (\_RAIter1 &\_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 &\_\_begin2, \_RAIter2 \_\_end2, \_RAIter3 \_\_target, typename **std::iterator\_traits**\< \_RAIter1 \>::difference\_type \_\_max\_length, \_Compare \_\_comp)\ Merge routine fallback to sequential in case the iterators of the two input sequences are of different type. template\ void **\_\_parallel\_nth\_element** (\_RAIter \_\_begin, \_RAIter \_\_nth, \_RAIter \_\_end, \_Compare \_\_comp)\ Parallel implementation of std::nth\_element(). template\ void **\_\_parallel\_partial\_sort** (\_RAIter \_\_begin, \_RAIter \_\_middle, \_RAIter \_\_end, \_Compare \_\_comp)\ Parallel implementation of std::partial\_sort(). template\ \_OutputIterator **\_\_parallel\_partial\_sum** (\_IIter \_\_begin, \_IIter \_\_end, \_OutputIterator \_\_result, \_BinaryOperation \_\_bin\_op)\ Parallel partial sum front-\_\_end. template\ \_OutputIterator **\_\_parallel\_partial\_sum\_basecase** (\_IIter \_\_begin, \_IIter \_\_end, \_OutputIterator \_\_result, \_BinaryOperation \_\_bin\_op, typename **std::iterator\_traits**\< \_IIter \>::value\_type \_\_value)\ Base case prefix sum routine. template\ \_OutputIterator **\_\_parallel\_partial\_sum\_linear** (\_IIter \_\_begin, \_IIter \_\_end, \_OutputIterator \_\_result, \_BinaryOperation \_\_bin\_op, typename **std::iterator\_traits**\< \_IIter \>::difference\_type \_\_n)\ Parallel partial sum implementation, two-phase approach, no recursion. template\ **std::iterator\_traits**\< \_RAIter \>::difference\_type **\_\_parallel\_partition** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Predicate \_\_pred, **\_ThreadIndex** \_\_num\_threads)\ Parallel implementation of std::partition. template\ void **\_\_parallel\_random\_shuffle** (\_RAIter \_\_begin, \_RAIter \_\_end, \_RandomNumberGenerator \_\_rng=**\_RandomNumber**())\ Parallel random public call. template\ void **\_\_parallel\_random\_shuffle\_drs** (\_RAIter \_\_begin, \_RAIter \_\_end, typename **std::iterator\_traits**\< \_RAIter \>::difference\_type \_\_n, **\_ThreadIndex** \_\_num\_threads, \_RandomNumberGenerator &\_\_rng)\ Main parallel random shuffle step. template\ void **\_\_parallel\_random\_shuffle\_drs\_pu** (**\_DRSSorterPU**\< \_RAIter, \_RandomNumberGenerator \> \*\_\_pus)\ Random shuffle code executed by each thread. template\ \_OutputIterator **\_\_parallel\_set\_difference** (\_IIter \_\_begin1, \_IIter \_\_end1, \_IIter \_\_begin2, \_IIter \_\_end2, \_OutputIterator \_\_result, \_Compare \_\_comp)\ template\ \_OutputIterator **\_\_parallel\_set\_intersection** (\_IIter \_\_begin1, \_IIter \_\_end1, \_IIter \_\_begin2, \_IIter \_\_end2, \_OutputIterator \_\_result, \_Compare \_\_comp)\ template\ \_OutputIterator **\_\_parallel\_set\_operation** (\_IIter \_\_begin1, \_IIter \_\_end1, \_IIter \_\_begin2, \_IIter \_\_end2, \_OutputIterator \_\_result, \_Operation \_\_op)\ template\ \_OutputIterator **\_\_parallel\_set\_symmetric\_difference** (\_IIter \_\_begin1, \_IIter \_\_end1, \_IIter \_\_begin2, \_IIter \_\_end2, \_OutputIterator \_\_result, \_Compare \_\_comp)\ template\ \_OutputIterator **\_\_parallel\_set\_union** (\_IIter \_\_begin1, \_IIter \_\_end1, \_IIter \_\_begin2, \_IIter \_\_end2, \_OutputIterator \_\_result, \_Compare \_\_comp)\ template\ void **\_\_parallel\_sort** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **\_Parallelism** \_\_parallelism)\ template\ void **\_\_parallel\_sort** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **balanced\_quicksort\_tag** \_\_parallelism)\ Choose balanced quicksort for parallel sorting. template\ void **\_\_parallel\_sort** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **default\_parallel\_tag** \_\_parallelism)\ Choose multiway mergesort with exact splitting, for parallel sorting. template\ void **\_\_parallel\_sort** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **multiway\_mergesort\_exact\_tag** \_\_parallelism)\ Choose multiway mergesort with exact splitting, for parallel sorting. template\ void **\_\_parallel\_sort** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **multiway\_mergesort\_sampling\_tag** \_\_parallelism)\ Choose multiway mergesort with splitting by sampling, for parallel sorting. template\ void **\_\_parallel\_sort** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **multiway\_mergesort\_tag** \_\_parallelism)\ Choose multiway mergesort, splitting variant at run-time, for parallel sorting. template\ void **\_\_parallel\_sort** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **parallel\_tag** \_\_parallelism)\ Choose a parallel sorting algorithm. template\ void **\_\_parallel\_sort** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **quicksort\_tag** \_\_parallelism)\ Choose quicksort for parallel sorting. template\ void **\_\_parallel\_sort\_qs** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **\_ThreadIndex** \_\_num\_threads)\ Unbalanced quicksort main call. template\ void **\_\_parallel\_sort\_qs\_conquer** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **\_ThreadIndex** \_\_num\_threads)\ Unbalanced quicksort conquer step. template\ **std::iterator\_traits**\< \_RAIter \>::difference\_type **\_\_parallel\_sort\_qs\_divide** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, typename **std::iterator\_traits**\< \_RAIter \>::difference\_type \_\_pivot\_rank, typename **std::iterator\_traits**\< \_RAIter \>::difference\_type \_\_num\_samples, **\_ThreadIndex** \_\_num\_threads)\ Unbalanced quicksort divide step. template\ void **\_\_parallel\_sort\_qsb** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **\_ThreadIndex** \_\_num\_threads)\ Top-level quicksort routine. template\ \_OutputIterator **\_\_parallel\_unique\_copy** (\_IIter \_\_first, \_IIter \_\_last, \_OutputIterator \_\_result)\ Parallel std::unique\_copy(), without explicit equality predicate. template\ \_OutputIterator **\_\_parallel\_unique\_copy** (\_IIter \_\_first, \_IIter \_\_last, \_OutputIterator \_\_result, \_BinaryPredicate \_\_binary\_pred)\ Parallel std::unique\_copy(), w/\_\_o explicit equality predicate. template\ void **\_\_qsb\_conquer** (**\_QSBThreadLocal**\< \_RAIter \> \*\*\_\_tls, \_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **\_ThreadIndex** \_\_iam, **\_ThreadIndex** \_\_num\_threads, bool \_\_parent\_wait)\ Quicksort conquer step. template\ **std::iterator\_traits**\< \_RAIter \>::difference\_type **\_\_qsb\_divide** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **\_ThreadIndex** \_\_num\_threads)\ Balanced quicksort divide step. template\ void **\_\_qsb\_local\_sort\_with\_helping** (**\_QSBThreadLocal**\< \_RAIter \> \*\*\_\_tls, \_Compare &\_\_comp, **\_ThreadIndex** \_\_iam, bool \_\_wait)\ Quicksort step doing load-balanced local sort. template\ int **\_\_random\_number\_pow2** (int \_\_logp, \_RandomNumberGenerator &\_\_rng)\ Generate a random number in \[0,2^\_\_logp). template\ \_Size **\_\_rd\_log2** (\_Size \_\_n)\ Calculates the rounded-down logarithm of \_\_n for base 2. template\ \_Tp **\_\_round\_up\_to\_pow2** (\_Tp \_\_x)\ Round up to the next greater power of 2. template\ \_\_RAIter1 **\_\_search\_template** (\_\_RAIter1 \_\_begin1, \_\_RAIter1 \_\_end1, \_\_RAIter2 \_\_begin2, \_\_RAIter2 \_\_end2, \_Pred \_\_pred)\ Parallel std::search. template\ \_RAIter3 **\_\_sequential\_multiway\_merge** (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, const typename **std::iterator\_traits**\< typename **std::iterator\_traits**\< \_RAIterIterator \>::value\_type::first\_type \>::value\_type &\_\_sentinel, \_DifferenceTp \_\_length, \_Compare \_\_comp)\ Sequential multi-way merging switch. template\ void **\_\_sequential\_random\_shuffle** (\_RAIter \_\_begin, \_RAIter \_\_end, \_RandomNumberGenerator &\_\_rng)\ Sequential cache-efficient random shuffle. template\ void **\_\_shrink** (**std::vector**\< \_IIter \> &\_\_os\_starts, size\_t &\_\_count\_to\_two, size\_t &\_\_range\_length)\ Combines two ranges into one and thus halves the number of ranges. template\ void **\_\_shrink\_and\_double** (**std::vector**\< \_IIter \> &\_\_os\_starts, size\_t &\_\_count\_to\_two, size\_t &\_\_range\_length, const bool \_\_make\_twice)\ Shrinks and doubles the ranges. void **\_\_yield** ()\ Yield control to another thread, without waiting for the end of the time slice. template\ size\_t **list\_partition** (const \_IIter \_\_begin, const \_IIter \_\_end, \_IIter \*\_\_starts, size\_t \*\_\_lengths, const int \_\_num\_parts, \_FunctorType &\_\_f, int \_\_oversampling=0)\ Splits a sequence given by input iterators into parts of almost equal size. template\ const \_Tp & **max** (const \_Tp &\_\_a, const \_Tp &\_\_b)\ Equivalent to std::max. template\ const \_Tp & **min** (const \_Tp &\_\_a, const \_Tp &\_\_b)\ Equivalent to std::min. template\ void **multiseq\_partition** (\_RanSeqs \_\_begin\_seqs, \_RanSeqs \_\_end\_seqs, \_RankType \_\_rank, \_RankIterator \_\_begin\_offsets, \_Compare \_\_comp=**std::less**\< typename **std::iterator\_traits**\< typename **std::iterator\_traits**\< \_RanSeqs \>::value\_type::first\_type \>::value\_type \>())\ Splits several sorted sequences at a certain global \_\_rank, resulting in a splitting point for each sequence. 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. template\ \_Tp **multiseq\_selection** (\_RanSeqs \_\_begin\_seqs, \_RanSeqs \_\_end\_seqs, \_RankType \_\_rank, \_RankType &\_\_offset, \_Compare \_\_comp=**std::less**\< \_Tp \>())\ Selects the element at a certain global \_\_rank from several sorted sequences. template\ \_RAIterOut **multiway\_merge** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **\_\_gnu\_parallel::exact\_tag** \_\_tag)\ template\ \_RAIterOut **multiway\_merge** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **\_\_gnu\_parallel::sampling\_tag** \_\_tag)\ template\ \_RAIterOut **multiway\_merge** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **\_\_gnu\_parallel::sequential\_tag**)\ Multiway Merge Frontend. template\ \_RAIterOut **multiway\_merge** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **default\_parallel\_tag** \_\_tag)\ template\ \_RAIterOut **multiway\_merge** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **parallel\_tag** \_\_tag=**parallel\_tag**(0))\ template\ class iterator, typename \_RAIterIterator, typename \_RAIter3, typename \_DifferenceTp, typename \_Compare\> \_RAIter3 **multiway\_merge\_3\_variant** (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp)\ Highly efficient 3-way merging procedure. template\ class iterator, typename \_RAIterIterator, typename \_RAIter3, typename \_DifferenceTp, typename \_Compare\> \_RAIter3 **multiway\_merge\_4\_variant** (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp)\ Highly efficient 4-way merging procedure. template\ void **multiway\_merge\_exact\_splitting** (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_DifferenceType \_\_length, \_DifferenceType \_\_total\_length, \_Compare \_\_comp, **std::vector**\< **std::pair**\< \_DifferenceType, \_DifferenceType \> \> \*\_\_pieces)\ Exact splitting for parallel multiway-merge routine. template\ \_RAIter3 **multiway\_merge\_loser\_tree** (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp)\ Multi-way merging procedure for a high branching factor, guarded case. template\ \_RAIter3 **multiway\_merge\_loser\_tree\_sentinel** (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, const typename **std::iterator\_traits**\< typename **std::iterator\_traits**\< \_RAIterIterator \>::value\_type::first\_type \>::value\_type &\_\_sentinel, \_DifferenceTp \_\_length, \_Compare \_\_comp)\ Multi-way merging procedure for a high branching factor, requiring sentinels to exist. template\ \_RAIter3 **multiway\_merge\_loser\_tree\_unguarded** (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, const typename **std::iterator\_traits**\< typename **std::iterator\_traits**\< \_RAIterIterator \>::value\_type::first\_type \>::value\_type &\_\_sentinel, \_DifferenceTp \_\_length, \_Compare \_\_comp)\ Multi-way merging procedure for a high branching factor, unguarded case. template\ void **multiway\_merge\_sampling\_splitting** (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_DifferenceType \_\_length, \_DifferenceType \_\_total\_length, \_Compare \_\_comp, **std::vector**\< **std::pair**\< \_DifferenceType, \_DifferenceType \> \> \*\_\_pieces)\ Sampling based splitting for parallel multiway-merge routine. template\ \_RAIterOut **multiway\_merge\_sentinels** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **\_\_gnu\_parallel::exact\_tag** \_\_tag)\ template\ \_RAIterOut **multiway\_merge\_sentinels** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **\_\_gnu\_parallel::sequential\_tag**)\ Multiway Merge Frontend. template\ \_RAIterOut **multiway\_merge\_sentinels** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **default\_parallel\_tag** \_\_tag)\ template\ \_RAIterOut **multiway\_merge\_sentinels** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **parallel\_tag** \_\_tag=**parallel\_tag**(0))\ template\ \_RAIterOut **multiway\_merge\_sentinels** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **sampling\_tag** \_\_tag)\ template\ \_RAIter3 **parallel\_multiway\_merge** (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, \_Splitter \_\_splitter, \_DifferenceTp \_\_length, \_Compare \_\_comp, **\_ThreadIndex** \_\_num\_threads)\ Parallel multi-way merge routine. template\ void **parallel\_sort\_mwms** (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, **\_ThreadIndex** \_\_num\_threads)\ PMWMS main call. template\ void **parallel\_sort\_mwms\_pu** (**\_PMWMSSortingData**\< \_RAIter \> \*\_\_sd, \_Compare &\_\_comp)\ PMWMS code executed by each thread. template\ \_RAIterOut **stable\_multiway\_merge** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **\_\_gnu\_parallel::exact\_tag** \_\_tag)\ template\ \_RAIterOut **stable\_multiway\_merge** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **\_\_gnu\_parallel::sequential\_tag**)\ template\ \_RAIterOut **stable\_multiway\_merge** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **default\_parallel\_tag** \_\_tag)\ template\ \_RAIterOut **stable\_multiway\_merge** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **parallel\_tag** \_\_tag=**parallel\_tag**(0))\ template\ \_RAIterOut **stable\_multiway\_merge** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **sampling\_tag** \_\_tag)\ template\ \_RAIterOut **stable\_multiway\_merge\_sentinels** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **\_\_gnu\_parallel::exact\_tag** \_\_tag)\ template\ \_RAIterOut **stable\_multiway\_merge\_sentinels** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **\_\_gnu\_parallel::sequential\_tag**)\ template\ \_RAIterOut **stable\_multiway\_merge\_sentinels** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **default\_parallel\_tag** \_\_tag)\ template\ \_RAIterOut **stable\_multiway\_merge\_sentinels** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **parallel\_tag** \_\_tag=**parallel\_tag**(0))\ template\ \_RAIterOut **stable\_multiway\_merge\_sentinels** (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, **sampling\_tag** \_\_tag)\ ### Variables static const int **\_CASable\_bits**\ Number of bits of \_CASable. static const **\_CASable** **\_CASable\_mask**\ \_CASable with the right half of bits set to 1. ## Detailed Description GNU parallel code for public use. ## Typedef Documentation ### typedef unsigned short \_\_gnu\_parallel::\_BinIndex Type to hold the index of a bin. Since many variables of this type are allocated, it should be chosen as small as possible. ### typedef int64\_t \_\_gnu\_parallel::\_CASable Longest compare-and-swappable integer type on this platform. ### typedef uint64\_t \_\_gnu\_parallel::\_SequenceIndex Unsigned integer to index \_\_elements. The total number of elements for each algorithm must fit into this type. ### typedef uint16\_t \_\_gnu\_parallel::\_ThreadIndex Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit into this type. ## Enumeration Type Documentation ### enum \_\_gnu\_parallel::\_AlgorithmStrategy Strategies for run-time algorithm selection: ### enum \_\_gnu\_parallel::\_FindAlgorithm Find algorithms: ### enum \_\_gnu\_parallel::\_MultiwayMergeAlgorithm Merging algorithms: ### 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. ### enum \_\_gnu\_parallel::\_PartialSumAlgorithm Partial sum algorithms: recursive, linear. ### enum \_\_gnu\_parallel::\_SortAlgorithm Sorting algorithms: ### enum \_\_gnu\_parallel::\_SplittingAlgorithm Sorting/merging algorithms: sampling, \_\_exact. ## Function Documentation ### template\ void \_\_gnu\_parallel::\_\_calc\_borders (\_RAIter \_\_elements, \_DifferenceTp \_\_length, \_DifferenceTp \* \_\_off) Precalculate \_\_advances for Knuth-Morris-Pratt algorithm. **Parameters** *\_\_elements* Begin iterator of sequence to search for. \ *\_\_length* Length of sequence to search for. \ *\_\_off* Returned \_\_offsets. Referenced by **\_\_search\_template()**. ### template\ bool \_\_gnu\_parallel::\_\_compare\_and\_swap (volatile \_Tp \* \_\_ptr, \_Tp \_\_comparand, \_Tp \_\_replacement) \[inline\] Compare-and-swap. Compare \*\_\_ptr and \_\_comparand. If equal, let \*\_\_ptr=\_\_replacement and return true, return false otherwise. **Parameters** *\_\_ptr* Pointer to signed integer. \ *\_\_comparand* Compare value. \ *\_\_replacement* Replacement value. Referenced by **\_\_parallel\_partition()**, **\_\_gnu\_parallel::\_RestrictedBoundedConcurrentQueue\< \_Tp \>::pop\_back()**, and **\_\_gnu\_parallel::\_RestrictedBoundedConcurrentQueue\< \_Tp \>::pop\_front()**. ### void \_\_gnu\_parallel::\_\_decode2 (\_CASable \_\_x, int & \_\_a, int & \_\_b) \[inline\] Decode two integers from one gnu\_parallel::\_CASable. **Parameters** *\_\_x* \_\_gnu\_parallel::\_CASable to decode integers from. \ *\_\_a* First integer, to be decoded from the most-significant \_CASable\_bits/2 bits of \_\_x. \ *\_\_b* Second integer, to be encoded in the least-significant \_CASable\_bits/2 bits of \_\_x. **See also** \_\_encode2 References **\_CASable\_bits**, and **\_CASable\_mask**. Referenced by **\_\_gnu\_parallel::\_RestrictedBoundedConcurrentQueue\< \_Tp \>::pop\_back()**, **\_\_gnu\_parallel::\_RestrictedBoundedConcurrentQueue\< \_Tp \>::pop\_front()**, and **\_\_gnu\_parallel::\_RestrictedBoundedConcurrentQueue\< \_Tp \>::push\_front()**. ### template\ void \_\_gnu\_parallel::\_\_determine\_samples (\_PMWMSSortingData\< \_RAIter \> \* \_\_sd, \_DifferenceTp \_\_num\_samples) Select \_M\_samples from a sequence. **Parameters** *\_\_sd* Pointer to algorithm data. \_Result will be placed in \_\_sd-\>\_M\_samples. \ *\_\_num\_samples* Number of \_M\_samples to select. References **\_\_equally\_split()**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_samples**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_source**, and **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_starts**. ### \_CASable \_\_gnu\_parallel::\_\_encode2 (int \_\_a, int \_\_b) \[inline\] Encode two integers into one gnu\_parallel::\_CASable. **Parameters** *\_\_a* First integer, to be encoded in the most-significant \_CASable\_bits/2 bits. \ *\_\_b* Second integer, to be encoded in the least-significant \_CASable\_bits/2 bits. **Returns** value encoding \_\_a and \_\_b. **See also** \_\_decode2 References **\_CASable\_bits**. Referenced by **\_\_gnu\_parallel::\_RestrictedBoundedConcurrentQueue\< \_Tp \>::\_RestrictedBoundedConcurrentQueue()**, **\_\_gnu\_parallel::\_RestrictedBoundedConcurrentQueue\< \_Tp \>::pop\_back()**, **\_\_gnu\_parallel::\_RestrictedBoundedConcurrentQueue\< \_Tp \>::pop\_front()**, and **\_\_gnu\_parallel::\_RestrictedBoundedConcurrentQueue\< \_Tp \>::push\_front()**. ### template\ \_OutputIterator \_\_gnu\_parallel::\_\_equally\_split (\_DifferenceType \_\_n, \_ThreadIndex \_\_num\_threads, \_OutputIterator \_\_s) function to split a sequence into parts of almost equal size. The resulting sequence \_\_s of length \_\_num\_threads+1 contains the splitting positions when splitting the range \[0,\_\_n) into parts of almost equal size (plus minus 1). The first entry is 0, the last one n. There may result empty parts. **Parameters** *\_\_n* Number of elements \ *\_\_num\_threads* Number of parts \ *\_\_s* Splitters **Returns** End of \_\_splitter sequence, i.e. \_\_s+\_\_num\_threads+1 Referenced by **\_\_determine\_samples()**, **\_\_find\_template()**, **\_\_parallel\_partial\_sum\_linear()**, **\_\_parallel\_unique\_copy()**, **\_\_search\_template()**, and **multiway\_merge\_exact\_splitting()**. ### template\ \_DifferenceType \_\_gnu\_parallel::\_\_equally\_split\_point (\_DifferenceType \_\_n, \_ThreadIndex \_\_num\_threads, \_ThreadIndex \_\_thread\_no) function to split a sequence into parts of almost equal size. Returns the position of the splitting point between thread number \_\_thread\_no (included) and thread number \_\_thread\_no+1 (excluded). **Parameters** *\_\_n* Number of elements \ *\_\_num\_threads* Number of parts \ *\_\_thread\_no* Number of threads **Returns** splitting point Referenced by **\_\_for\_each\_template\_random\_access\_ed()**. ### template\ \_Tp \_\_gnu\_parallel::\_\_fetch\_and\_add (volatile \_Tp \* \_\_ptr, \_Tp \_\_addend) \[inline\] Add a value to a variable, atomically. **Parameters** *\_\_ptr* Pointer to a signed integer. \ *\_\_addend* Value to add. Referenced by **\_\_find\_template()**, **\_\_for\_each\_template\_random\_access\_workstealing()**, **\_\_parallel\_partition()**, and **\_\_gnu\_parallel::\_RestrictedBoundedConcurrentQueue\< \_Tp \>::push\_front()**. ### template\ std::pair\< \_RAIter1, \_RAIter2 \> \_\_gnu\_parallel::\_\_find\_template (\_RAIter1 \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 \_\_begin2, \_Pred \_\_pred, \_Selector \_\_selector) \[inline\] Parallel std::find, switch for different algorithms. **Parameters** *\_\_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. References **\_\_find\_template()**, **\_\_gnu\_parallel::\_Settings::get()**, and **std::make\_pair()**. Referenced by **\_\_find\_template()**. ### template\ std::pair\< \_RAIter1, \_RAIter2 \> \_\_gnu\_parallel::\_\_find\_template (\_RAIter1 \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 \_\_begin2, \_Pred \_\_pred, \_Selector \_\_selector, constant\_size\_blocks\_tag ) Parallel std::find, constant block size variant. **Parameters** *\_\_begin1* Begin iterator of first sequence. \ *\_\_end1* End iterator of first sequence. \ *\_\_begin2* Begin iterator of second sequence. 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. **See also** \_\_gnu\_parallel::\_Settings::find\_sequential\_search\_size \_\_gnu\_parallel::\_Settings::find\_block\_size There are two main differences between the growing blocks and the constant-size blocks variants. - 1\. For GB, the block size grows; for CSB, the block size is fixed. - 2\. For GB, the blocks are allocated dynamically; for CSB, the blocks are allocated in a predetermined manner, namely spacial round-robin. References **\_GLIBCXX\_CALL**, **\_\_gnu\_parallel::\_Settings::find\_initial\_block\_size**, **\_\_gnu\_parallel::\_Settings::find\_sequential\_search\_size**, **std::pair\< \_T1, \_T2 \>::first**, **\_\_gnu\_parallel::\_Settings::get()**, and **std::min()**. ### template\ std::pair\< \_RAIter1, \_RAIter2 \> \_\_gnu\_parallel::\_\_find\_template (\_RAIter1 \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 \_\_begin2, \_Pred \_\_pred, \_Selector \_\_selector, equal\_split\_tag ) Parallel std::find, equal splitting variant. **Parameters** *\_\_begin1* Begin iterator of first sequence. \ *\_\_end1* End iterator of first sequence. \ *\_\_begin2* Begin iterator of second sequence. 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. References **\_\_equally\_split()**, and **\_GLIBCXX\_CALL**. ### template\ std::pair\< \_RAIter1, \_RAIter2 \> \_\_gnu\_parallel::\_\_find\_template (\_RAIter1 \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 \_\_begin2, \_Pred \_\_pred, \_Selector \_\_selector, growing\_blocks\_tag ) Parallel std::find, growing block size variant. **Parameters** *\_\_begin1* Begin iterator of first sequence. \ *\_\_end1* End iterator of first sequence. \ *\_\_begin2* Begin iterator of second sequence. 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. **See also** \_\_gnu\_parallel::\_Settings::find\_sequential\_search\_size \_\_gnu\_parallel::\_Settings::find\_scale\_factor There are two main differences between the growing blocks and the constant-size blocks variants. - 1\. For GB, the block size grows; for CSB, the block size is fixed. - 2\. For GB, the blocks are allocated dynamically; for CSB, the blocks are allocated in a predetermined manner, namely spacial round-robin. References **\_\_fetch\_and\_add()**, **\_GLIBCXX\_CALL**, **\_\_gnu\_parallel::\_Settings::find\_scale\_factor**, **\_\_gnu\_parallel::\_Settings::find\_sequential\_search\_size**, **std::pair\< \_T1, \_T2 \>::first**, **\_\_gnu\_parallel::\_Settings::get()**, **std::max()**, and **std::min()**. ### template\ \_UserOp \_\_gnu\_parallel::\_\_for\_each\_template\_random\_access (\_IIter \_\_begin, \_IIter \_\_end, \_UserOp \_\_user\_op, \_Functionality & \_\_functionality, \_Red \_\_reduction, \_Result \_\_reduction\_start, \_Result & \_\_output, typename std::iterator\_traits\< \_IIter \>::difference\_type \_\_bound, \_Parallelism \_\_parallelism\_tag) Chose the desired algorithm by evaluating \_\_parallelism\_tag. **Parameters** *\_\_begin* Begin iterator of input sequence. \ *\_\_end* End iterator of input sequence. \ *\_\_user\_op* A user-specified functor (comparator, predicate, associative operator,...) \ *\_\_functionality* functor to *process* an element with \_\_user\_op (depends on desired functionality, e. g. accumulate, for\_each,... \ *\_\_reduction* Reduction functor. \ *\_\_reduction\_start* Initial value for reduction. \ *\_\_output* Output iterator. \ *\_\_bound* Maximum number of elements processed. \ *\_\_parallelism\_tag* Parallelization method References **\_\_for\_each\_template\_random\_access\_ed()**, **\_\_for\_each\_template\_random\_access\_omp\_loop()**, **\_\_for\_each\_template\_random\_access\_workstealing()**, **parallel\_omp\_loop**, **parallel\_omp\_loop\_static**, and **parallel\_unbalanced**. ### template\ \_Op \_\_gnu\_parallel::\_\_for\_each\_template\_random\_access\_ed (\_RAIter \_\_begin, \_RAIter \_\_end, \_Op \_\_o, \_Fu & \_\_f, \_Red \_\_r, \_Result \_\_base, \_Result & \_\_output, typename std::iterator\_traits\< \_RAIter \>::difference\_type \_\_bound) Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work. **Parameters** *\_\_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). References **\_\_equally\_split\_point()**, and **min()**. Referenced by **\_\_for\_each\_template\_random\_access()**. ### template\ \_Op \_\_gnu\_parallel::\_\_for\_each\_template\_random\_access\_omp\_loop (\_RAIter \_\_begin, \_RAIter \_\_end, \_Op \_\_o, \_Fu & \_\_f, \_Red \_\_r, \_Result \_\_base, \_Result & \_\_output, typename std::iterator\_traits\< \_RAIter \>::difference\_type \_\_bound) Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop. **Parameters** *\_\_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). References **min()**. Referenced by **\_\_for\_each\_template\_random\_access()**. ### template\ \_Op \_\_gnu\_parallel::\_\_for\_each\_template\_random\_access\_omp\_loop\_static (\_RAIter \_\_begin, \_RAIter \_\_end, \_Op \_\_o, \_Fu & \_\_f, \_Red \_\_r, \_Result \_\_base, \_Result & \_\_output, typename std::iterator\_traits\< \_RAIter \>::difference\_type \_\_bound) Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling. **Parameters** *\_\_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). References **std::min()**. ### template\ \_Op \_\_gnu\_parallel::\_\_for\_each\_template\_random\_access\_workstealing (\_RAIter \_\_begin, \_RAIter \_\_end, \_Op \_\_op, \_Fu & \_\_f, \_Red \_\_r, \_Result \_\_base, \_Result & \_\_output, typename std::iterator\_traits\< \_RAIter \>::difference\_type \_\_bound) Work stealing algorithm for random access iterators. Uses O(1) additional memory. Synchronization at job lists is done with atomic operations. **Parameters** *\_\_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). References **\_\_fetch\_and\_add()**, **\_\_yield()**, **\_GLIBCXX\_CALL**, **\_\_gnu\_parallel::\_Job\< \_DifferenceTp \>::\_M\_first**, **\_\_gnu\_parallel::\_Job\< \_DifferenceTp \>::\_M\_last**, **\_\_gnu\_parallel::\_Job\< \_DifferenceTp \>::\_M\_load**, **\_\_gnu\_parallel::\_Settings::cache\_line\_size**, **\_\_gnu\_parallel::\_Settings::get()**, **max()**, and **min()**. Referenced by **\_\_for\_each\_template\_random\_access()**. ### template\ bool \_\_gnu\_parallel::\_\_is\_sorted (\_IIter \_\_begin, \_IIter \_\_end, \_Compare \_\_comp) 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. Referenced by **\_\_sequential\_multiway\_merge()**, **multiway\_merge\_loser\_tree\_sentinel()**, and **parallel\_multiway\_merge()**. ### template\ \_RAIter \_\_gnu\_parallel::\_\_median\_of\_three\_iterators (\_RAIter \_\_a, \_RAIter \_\_b, \_RAIter \_\_c, \_Compare \_\_comp) Compute the median of three referenced elements, according to \_\_comp. **Parameters** *\_\_a* First iterator. \ *\_\_b* Second iterator. \ *\_\_c* Third iterator. \ *\_\_comp* Comparator. Referenced by **\_\_qsb\_divide()**. ### template\ \_OutputIterator \_\_gnu\_parallel::\_\_merge\_advance (\_RAIter1 & \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 & \_\_begin2, \_RAIter2 \_\_end2, \_OutputIterator \_\_target, \_DifferenceTp \_\_max\_length, \_Compare \_\_comp) \[inline\] Merge routine being able to merge only the \_\_max\_length smallest elements. The \_\_begin iterators are advanced accordingly, they might not reach \_\_end, in contrast to the usual variant. Static switch on whether to use the conditional-move variant. **Parameters** *\_\_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. References **\_\_merge\_advance\_movc()**, and **\_GLIBCXX\_CALL**. Referenced by **\_\_parallel\_merge\_advance()**, and **\_\_sequential\_multiway\_merge()**. ### template\ \_OutputIterator \_\_gnu\_parallel::\_\_merge\_advance\_movc (\_RAIter1 & \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 & \_\_begin2, \_RAIter2 \_\_end2, \_OutputIterator \_\_target, \_DifferenceTp \_\_max\_length, \_Compare \_\_comp) Merge routine being able to merge only the \_\_max\_length smallest elements. The \_\_begin iterators are advanced accordingly, they might not reach \_\_end, in contrast to the usual variant. Specially designed code should allow the compiler to generate conditional moves instead of branches. **Parameters** *\_\_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. Referenced by **\_\_merge\_advance()**. ### template\ \_OutputIterator \_\_gnu\_parallel::\_\_merge\_advance\_usual (\_RAIter1 & \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 & \_\_begin2, \_RAIter2 \_\_end2, \_OutputIterator \_\_target, \_DifferenceTp \_\_max\_length, \_Compare \_\_comp) Merge routine being able to merge only the \_\_max\_length smallest elements. The \_\_begin iterators are advanced accordingly, they might not reach \_\_end, in contrast to the usual variant. **Parameters** *\_\_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. ### template\ \_RAIter3 \_\_gnu\_parallel::\_\_parallel\_merge\_advance (\_RAIter1 & \_\_begin1, \_RAIter1 \_\_end1, \_RAIter1 & \_\_begin2, \_RAIter1 \_\_end2, \_RAIter3 \_\_target, typename std::iterator\_traits\< \_RAIter1 \>::difference\_type \_\_max\_length, \_Compare \_\_comp) \[inline\] Parallel merge routine being able to merge only the \_\_max\_length smallest elements. The \_\_begin iterators are advanced accordingly, they might not reach \_\_end, in contrast to the usual variant. The functionality is projected onto parallel\_multiway\_merge. **Parameters** *\_\_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. References **std::make\_pair()**, **multiway\_merge\_exact\_splitting()**, and **parallel\_multiway\_merge()**. ### template\ \_RAIter3 \_\_gnu\_parallel::\_\_parallel\_merge\_advance (\_RAIter1 & \_\_begin1, \_RAIter1 \_\_end1, \_RAIter2 & \_\_begin2, \_RAIter2 \_\_end2, \_RAIter3 \_\_target, typename std::iterator\_traits\< \_RAIter1 \>::difference\_type \_\_max\_length, \_Compare \_\_comp) \[inline\] Merge routine fallback to sequential in case the iterators of the two input sequences are of different type. **Parameters** *\_\_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. References **\_\_merge\_advance()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_nth\_element (\_RAIter \_\_begin, \_RAIter \_\_nth, \_RAIter \_\_end, \_Compare \_\_comp) 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. References **\_\_parallel\_partition()**, **\_GLIBCXX\_CALL**, **\_\_gnu\_parallel::\_Settings::get()**, **std::max()**, **\_\_gnu\_parallel::\_Settings::nth\_element\_minimal\_n**, and **\_\_gnu\_parallel::\_Settings::partition\_minimal\_n**. Referenced by **\_\_parallel\_partial\_sort()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_partial\_sort (\_RAIter \_\_begin, \_RAIter \_\_middle, \_RAIter \_\_end, \_Compare \_\_comp) 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. References **\_\_parallel\_nth\_element()**. ### template\ \_OutputIterator \_\_gnu\_parallel::\_\_parallel\_partial\_sum (\_IIter \_\_begin, \_IIter \_\_end, \_OutputIterator \_\_result, \_BinaryOperation \_\_bin\_op) 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. References **\_\_parallel\_partial\_sum\_linear()**, **\_GLIBCXX\_CALL**, and **\_\_gnu\_parallel::\_Settings::get()**. ### template\ \_OutputIterator \_\_gnu\_parallel::\_\_parallel\_partial\_sum\_basecase (\_IIter \_\_begin, \_IIter \_\_end, \_OutputIterator \_\_result, \_BinaryOperation \_\_bin\_op, typename std::iterator\_traits\< \_IIter \>::value\_type \_\_value) Base case prefix sum routine. **Parameters** *\_\_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. Referenced by **\_\_parallel\_partial\_sum\_linear()**. ### template\ \_OutputIterator \_\_gnu\_parallel::\_\_parallel\_partial\_sum\_linear (\_IIter \_\_begin, \_IIter \_\_end, \_OutputIterator \_\_result, \_BinaryOperation \_\_bin\_op, typename std::iterator\_traits\< \_IIter \>::difference\_type \_\_n) Parallel partial sum implementation, two-phase approach, no recursion. **Parameters** *\_\_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. **Returns** End iterator of output sequence. References **\_\_equally\_split()**, **\_\_parallel\_partial\_sum\_basecase()**, **\_\_gnu\_parallel::\_Settings::get()**, **std::max()**, **std::min()**, and **\_\_gnu\_parallel::\_Settings::partial\_sum\_dilation**. Referenced by **\_\_parallel\_partial\_sum()**. ### template\ std::iterator\_traits\< \_RAIter \>::difference\_type \_\_gnu\_parallel::\_\_parallel\_partition (\_RAIter \_\_begin, \_RAIter \_\_end, \_Predicate \_\_pred, \_ThreadIndex \_\_num\_threads) Parallel implementation of std::partition. **Parameters** *\_\_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. References **\_\_compare\_and\_swap()**, **\_\_fetch\_and\_add()**, **\_GLIBCXX\_CALL**, **\_GLIBCXX\_VOLATILE**, **\_\_gnu\_parallel::\_Settings::get()**, **std::max()**, **\_\_gnu\_parallel::\_Settings::partition\_chunk\_share**, and **\_\_gnu\_parallel::\_Settings::partition\_chunk\_size**. Referenced by **\_\_parallel\_nth\_element()**, **\_\_parallel\_sort\_qs\_divide()**, and **\_\_qsb\_divide()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_random\_shuffle (\_RAIter \_\_begin, \_RAIter \_\_end, \_RandomNumberGenerator \_\_rng = \_RandomNumber()) \[inline\] Parallel random public call. **Parameters** *\_\_begin* Begin iterator of sequence. \ *\_\_end* End iterator of sequence. \ *\_\_rng* Random number generator to use. References **\_\_parallel\_random\_shuffle\_drs()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_random\_shuffle\_drs (\_RAIter \_\_begin, \_RAIter \_\_end, typename std::iterator\_traits\< \_RAIter \>::difference\_type \_\_n, \_ThreadIndex \_\_num\_threads, \_RandomNumberGenerator & \_\_rng) Main parallel random shuffle step. **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. References **\_\_gnu\_parallel::\_DRSSorterPU\< \_RAIter, \_RandomNumberGenerator \>::\_\_bins\_end**, **\_\_parallel\_random\_shuffle\_drs\_pu()**, **\_\_rd\_log2()**, **\_\_round\_up\_to\_pow2()**, **\_\_sequential\_random\_shuffle()**, **\_GLIBCXX\_CALL**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_bin\_proc**, **\_\_gnu\_parallel::\_DRSSorterPU\< \_RAIter, \_RandomNumberGenerator \>::\_M\_bins\_begin**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_dist**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_num\_bins**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_num\_bits**, **\_\_gnu\_parallel::\_DRSSorterPU\< \_RAIter, \_RandomNumberGenerator \>::\_M\_num\_threads**, **\_\_gnu\_parallel::\_DRSSorterPU\< \_RAIter, \_RandomNumberGenerator \>::\_M\_sd**, **\_\_gnu\_parallel::\_DRSSorterPU\< \_RAIter, \_RandomNumberGenerator \>::\_M\_seed**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_starts**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_temporaries**, **\_\_gnu\_parallel::\_Settings::get()**, **\_\_gnu\_parallel::\_Settings::L2\_cache\_size**, **std::max()**, **std::numeric\_limits\< \_Tp \>::max()**, **std::min()**, and **\_\_gnu\_parallel::\_Settings::TLB\_size**. Referenced by **\_\_parallel\_random\_shuffle()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_random\_shuffle\_drs\_pu (\_DRSSorterPU\< \_RAIter, \_RandomNumberGenerator \> \* \_\_pus) Random shuffle code executed by each thread. **Parameters** *\_\_pus* Array of thread-local data records. References **\_\_random\_number\_pow2()**, **\_\_sequential\_random\_shuffle()**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_bin\_proc**, **\_\_gnu\_parallel::\_DRSSorterPU\< \_RAIter, \_RandomNumberGenerator \>::\_M\_bins\_begin**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_dist**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_num\_bins**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_num\_bits**, **\_\_gnu\_parallel::\_DRSSorterPU\< \_RAIter, \_RandomNumberGenerator \>::\_M\_num\_threads**, **\_\_gnu\_parallel::\_DRSSorterPU\< \_RAIter, \_RandomNumberGenerator \>::\_M\_sd**, **\_\_gnu\_parallel::\_DRSSorterPU\< \_RAIter, \_RandomNumberGenerator \>::\_M\_seed**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_source**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_starts**, **\_\_gnu\_parallel::\_DRandomShufflingGlobalData\< \_RAIter \>::\_M\_temporaries**, and **std::partial\_sum()**. Referenced by **\_\_parallel\_random\_shuffle\_drs()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_sort (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, balanced\_quicksort\_tag \_\_parallelism) \[inline\] Choose balanced quicksort for parallel sorting. **Parameters** *\_\_begin* Begin iterator of input sequence. \ *\_\_end* End iterator of input sequence. \ *\_\_comp* Comparator. **Template Parameters** *\_\_stable* Sort stable. References **\_\_gnu\_parallel::parallel\_tag::\_\_get\_num\_threads()**, **\_\_parallel\_sort\_qsb()**, and **\_GLIBCXX\_CALL**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_sort (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, default\_parallel\_tag \_\_parallelism) \[inline\] Choose multiway mergesort with exact splitting, for parallel sorting. **Parameters** *\_\_begin* Begin iterator of input sequence. \ *\_\_end* End iterator of input sequence. \ *\_\_comp* Comparator. **Template Parameters** *\_\_stable* Sort stable. References **\_\_gnu\_parallel::parallel\_tag::\_\_get\_num\_threads()**, and **\_GLIBCXX\_CALL**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_sort (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, multiway\_mergesort\_exact\_tag \_\_parallelism) \[inline\] Choose multiway mergesort with exact splitting, for parallel sorting. **Parameters** *\_\_begin* Begin iterator of input sequence. \ *\_\_end* End iterator of input sequence. \ *\_\_comp* Comparator. **Template Parameters** *\_\_stable* Sort stable. References **\_\_gnu\_parallel::parallel\_tag::\_\_get\_num\_threads()**, **\_GLIBCXX\_CALL**, and **parallel\_sort\_mwms()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_sort (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, multiway\_mergesort\_sampling\_tag \_\_parallelism) \[inline\] Choose multiway mergesort with splitting by sampling, for parallel sorting. **Parameters** *\_\_begin* Begin iterator of input sequence. \ *\_\_end* End iterator of input sequence. \ *\_\_comp* Comparator. **Template Parameters** *\_\_stable* Sort stable. References **\_\_gnu\_parallel::parallel\_tag::\_\_get\_num\_threads()**, **\_GLIBCXX\_CALL**, and **parallel\_sort\_mwms()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_sort (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, multiway\_mergesort\_tag \_\_parallelism) \[inline\] Choose multiway mergesort, splitting variant at run-time, for parallel sorting. **Parameters** *\_\_begin* Begin iterator of input sequence. \ *\_\_end* End iterator of input sequence. \ *\_\_comp* Comparator. **Template Parameters** *\_\_stable* Sort stable. References **\_\_gnu\_parallel::parallel\_tag::\_\_get\_num\_threads()**, **\_GLIBCXX\_CALL**, **\_\_gnu\_parallel::\_Settings::get()**, and **parallel\_sort\_mwms()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_sort (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, parallel\_tag \_\_parallelism) \[inline\] Choose a parallel sorting algorithm. **Parameters** *\_\_begin* Begin iterator of input sequence. \ *\_\_end* End iterator of input sequence. \ *\_\_comp* Comparator. **Template Parameters** *\_\_stable* Sort stable. References **\_\_gnu\_parallel::parallel\_tag::\_\_get\_num\_threads()**, **\_\_parallel\_sort\_qs()**, **\_\_parallel\_sort\_qsb()**, **\_GLIBCXX\_CALL**, **\_\_gnu\_parallel::\_Settings::get()**, and **parallel\_sort\_mwms()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_sort (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, quicksort\_tag \_\_parallelism) \[inline\] Choose quicksort for parallel sorting. **Parameters** *\_\_begin* Begin iterator of input sequence. \ *\_\_end* End iterator of input sequence. \ *\_\_comp* Comparator. **Template Parameters** *\_\_stable* Sort stable. References **\_\_gnu\_parallel::parallel\_tag::\_\_get\_num\_threads()**, **\_\_parallel\_sort\_qs()**, and **\_GLIBCXX\_CALL**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_sort\_qs (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, \_ThreadIndex \_\_num\_threads) Unbalanced quicksort main call. **Parameters** *\_\_begin* Begin iterator of input sequence. \ *\_\_end* End iterator input sequence, ignored. \ *\_\_comp* Comparator. \ *\_\_num\_threads* Number of threads that are allowed to work on this part. References **\_\_parallel\_sort\_qs\_conquer()**, and **\_GLIBCXX\_CALL**. Referenced by **\_\_parallel\_sort()**, and **\_\_parallel\_sort()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_sort\_qs\_conquer (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, \_ThreadIndex \_\_num\_threads) 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. References **\_\_parallel\_sort\_qs\_conquer()**, **\_\_parallel\_sort\_qs\_divide()**, and **\_\_gnu\_parallel::\_Settings::get()**. Referenced by **\_\_parallel\_sort\_qs()**, and **\_\_parallel\_sort\_qs\_conquer()**. ### template\ std::iterator\_traits\< \_RAIter \>::difference\_type \_\_gnu\_parallel::\_\_parallel\_sort\_qs\_divide (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, typename std::iterator\_traits\< \_RAIter \>::difference\_type \_\_pivot\_rank, typename std::iterator\_traits\< \_RAIter \>::difference\_type \_\_num\_samples, \_ThreadIndex \_\_num\_threads) Unbalanced quicksort divide step. **Parameters** *\_\_begin* Begin iterator of subsequence. \ *\_\_end* End iterator of subsequence. \ *\_\_comp* Comparator. \ *\_\_pivot\_rank* Desired \_\_rank of the pivot. \ *\_\_num\_samples* Choose pivot from that many samples. \ *\_\_num\_threads* Number of threads that are allowed to work on this part. References **\_\_parallel\_partition()**, and **std::min()**. Referenced by **\_\_parallel\_sort\_qs\_conquer()**. ### template\ void \_\_gnu\_parallel::\_\_parallel\_sort\_qsb (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, \_ThreadIndex \_\_num\_threads) Top-level quicksort routine. **Parameters** *\_\_begin* Begin iterator of sequence. \ *\_\_end* End iterator of sequence. \ *\_\_comp* Comparator. \ *\_\_num\_threads* Number of threads that are allowed to work on this part. References **\_\_qsb\_conquer()**, **\_\_rd\_log2()**, **\_GLIBCXX\_CALL**, and **std::make\_pair()**. Referenced by **\_\_parallel\_sort()**, and **\_\_parallel\_sort()**. ### template\ \_OutputIterator \_\_gnu\_parallel::\_\_parallel\_unique\_copy (\_IIter \_\_first, \_IIter \_\_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. References **\_\_parallel\_unique\_copy()**. ### template\ \_OutputIterator \_\_gnu\_parallel::\_\_parallel\_unique\_copy (\_IIter \_\_first, \_IIter \_\_last, \_OutputIterator \_\_result, \_BinaryPredicate \_\_binary\_pred) Parallel std::unique\_copy(), w/\_\_o explicit equality predicate. **Parameters** *\_\_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. References **\_\_equally\_split()**, and **\_GLIBCXX\_CALL**. Referenced by **\_\_parallel\_unique\_copy()**. ### template\ void \_\_gnu\_parallel::\_\_qsb\_conquer (\_QSBThreadLocal\< \_RAIter \> \*\* \_\_tls, \_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, \_ThreadIndex \_\_iam, \_ThreadIndex \_\_num\_threads, bool \_\_parent\_wait) Quicksort conquer step. **Parameters** *\_\_tls* Array of thread-local storages. \ *\_\_begin* Begin iterator of subsequence. \ *\_\_end* End iterator of subsequence. \ *\_\_comp* Comparator. \ *\_\_iam* Number of the thread processing this function. \ *\_\_num\_threads* Number of threads that are allowed to work on this part. References **\_\_qsb\_conquer()**, **\_\_qsb\_divide()**, **\_\_qsb\_local\_sort\_with\_helping()**, **\_\_gnu\_parallel::\_QSBThreadLocal\< \_RAIter \>::\_M\_elements\_leftover**, **\_\_gnu\_parallel::\_QSBThreadLocal\< \_RAIter \>::\_M\_initial**, **std::max()**, and **std::min()**. Referenced by **\_\_parallel\_sort\_qsb()**, and **\_\_qsb\_conquer()**. ### template\ std::iterator\_traits\< \_RAIter \>::difference\_type \_\_gnu\_parallel::\_\_qsb\_divide (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, \_ThreadIndex \_\_num\_threads) 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 References **\_\_median\_of\_three\_iterators()**, and **\_\_parallel\_partition()**. Referenced by **\_\_qsb\_conquer()**. ### template\ void \_\_gnu\_parallel::\_\_qsb\_local\_sort\_with\_helping (\_QSBThreadLocal\< \_RAIter \> \*\* \_\_tls, \_Compare & \_\_comp, \_ThreadIndex \_\_iam, bool \_\_wait) Quicksort step doing load-balanced local sort. **Parameters** *\_\_tls* Array of thread-local storages. \ *\_\_comp* Comparator. \ *\_\_iam* Number of the thread processing this function. References **\_\_yield()**, **\_GLIBCXX\_PARALLEL\_ASSERTIONS**, **\_\_gnu\_parallel::\_QSBThreadLocal\< \_RAIter \>::\_M\_elements\_leftover**, **\_\_gnu\_parallel::\_QSBThreadLocal\< \_RAIter \>::\_M\_initial**, **\_\_gnu\_parallel::\_QSBThreadLocal\< \_RAIter \>::\_M\_leftover\_parts**, **\_\_gnu\_parallel::\_QSBThreadLocal\< \_RAIter \>::\_M\_num\_threads**, **\_\_gnu\_parallel::\_Settings::get()**, **std::make\_pair()**, and **\_\_gnu\_parallel::\_Settings::sort\_qsb\_base\_case\_maximal\_n**. Referenced by **\_\_qsb\_conquer()**. ### template\ 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. Referenced by **\_\_parallel\_random\_shuffle\_drs\_pu()**, and **\_\_sequential\_random\_shuffle()**. ### template\ \_Size \_\_gnu\_parallel::\_\_rd\_log2 (\_Size \_\_n) \[inline\] Calculates the rounded-down logarithm of \_\_n for base 2. **Parameters** *\_\_n* Argument. **Returns** Returns 0 for any argument \<1. Referenced by **\_\_gnu\_parallel::\_LoserTreeBase\< \_Tp, \_Compare \>::\_LoserTreeBase()**, **\_\_parallel\_random\_shuffle\_drs()**, **\_\_parallel\_sort\_qsb()**, **\_\_round\_up\_to\_pow2()**, **\_\_sequential\_random\_shuffle()**, **multiseq\_partition()**, and **multiseq\_selection()**. ### template\ \_Tp \_\_gnu\_parallel::\_\_round\_up\_to\_pow2 (\_Tp \_\_x) Round up to the next greater power of 2. **Parameters** *\_\_x* \_Integer to round up References **\_\_rd\_log2()**. Referenced by **\_\_parallel\_random\_shuffle\_drs()**, **\_\_sequential\_random\_shuffle()**, and **multiseq\_selection()**. ### template\ \_\_RAIter1 \_\_gnu\_parallel::\_\_search\_template (\_\_RAIter1 \_\_begin1, \_\_RAIter1 \_\_end1, \_\_RAIter2 \_\_begin2, \_\_RAIter2 \_\_end2, \_Pred \_\_pred) 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. References **\_\_calc\_borders()**, **\_\_equally\_split()**, **\_GLIBCXX\_CALL**, **std::max()**, and **std::min()**. ### template\ \_RAIter3 \_\_gnu\_parallel::\_\_sequential\_multiway\_merge (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, const typename std::iterator\_traits\< typename std::iterator\_traits\< \_RAIterIterator \>::value\_type::first\_type \>::value\_type & \_\_sentinel, \_DifferenceTp \_\_length, \_Compare \_\_comp) Sequential multi-way merging switch. The \_GLIBCXX\_PARALLEL\_DECISION is based on the branching factor and runtime settings. **Parameters** *\_\_seqs\_begin* Begin iterator of iterator pair input sequence. \ *\_\_seqs\_end* End iterator of iterator pair input sequence. \ *\_\_target* Begin iterator of output sequence. \ *\_\_comp* Comparator. \ *\_\_length* Maximum length to merge, possibly larger than the number of elements available. \ *\_\_sentinel* The sequences have \_\_a \_\_sentinel element. **Returns** End iterator of output sequence. References **\_\_is\_sorted()**, **\_\_merge\_advance()**, **\_GLIBCXX\_CALL**, **\_GLIBCXX\_PARALLEL\_LENGTH**, and **std::min()**. Referenced by **multiway\_merge()**, **multiway\_merge\_sentinels()**, and **parallel\_multiway\_merge()**. ### template\ void \_\_gnu\_parallel::\_\_sequential\_random\_shuffle (\_RAIter \_\_begin, \_RAIter \_\_end, \_RandomNumberGenerator & \_\_rng) Sequential cache-efficient random shuffle. **Parameters** *\_\_begin* Begin iterator of sequence. \ *\_\_end* End iterator of sequence. \ *\_\_rng* Random number generator to use. References **\_\_random\_number\_pow2()**, **\_\_rd\_log2()**, **\_\_round\_up\_to\_pow2()**, **\_\_sequential\_random\_shuffle()**, **\_\_gnu\_parallel::\_Settings::get()**, **\_\_gnu\_parallel::\_Settings::L2\_cache\_size**, **std::max()**, **std::min()**, **std::partial\_sum()**, and **\_\_gnu\_parallel::\_Settings::TLB\_size**. Referenced by **\_\_parallel\_random\_shuffle\_drs()**, **\_\_parallel\_random\_shuffle\_drs\_pu()**, and **\_\_sequential\_random\_shuffle()**. ### template\ void \_\_gnu\_parallel::\_\_shrink (std::vector\< \_IIter \> & \_\_os\_starts, size\_t & \_\_count\_to\_two, size\_t & \_\_range\_length) Combines two ranges into one and thus halves the number of ranges. **Parameters** *\_\_os\_starts* Start positions worked on (oversampled). \ *\_\_count\_to\_two* Counts up to 2. \ *\_\_range\_length* Current length of a chunk. References **std::vector\< \_Tp, \_Alloc \>::size()**. Referenced by **\_\_shrink\_and\_double()**. ### template\ void \_\_gnu\_parallel::\_\_shrink\_and\_double (std::vector\< \_IIter \> & \_\_os\_starts, size\_t & \_\_count\_to\_two, size\_t & \_\_range\_length, const bool \_\_make\_twice) Shrinks and doubles the ranges. **Parameters** *\_\_os\_starts* Start positions worked on (oversampled). \ *\_\_count\_to\_two* Counts up to 2. \ *\_\_range\_length* Current length of a chunk. \ *\_\_make\_twice* Whether the \_\_os\_starts is allowed to be grown or not References **\_\_shrink()**, **std::vector\< \_Tp, \_Alloc \>::resize()**, and **std::vector\< \_Tp, \_Alloc \>::size()**. Referenced by **list\_partition()**. ### void \_\_gnu\_parallel::\_\_yield () \[inline\] Yield control to another thread, without waiting for the end of the time slice. Referenced by **\_\_for\_each\_template\_random\_access\_workstealing()**, and **\_\_qsb\_local\_sort\_with\_helping()**. ### template\ size\_t \_\_gnu\_parallel::list\_partition (const \_IIter \_\_begin, const \_IIter \_\_end, \_IIter \* \_\_starts, size\_t \* \_\_lengths, const int \_\_num\_parts, \_FunctorType & \_\_f, int \_\_oversampling = 0) Splits a sequence given by input iterators into parts of almost equal size. The function needs only one pass over the sequence. **Parameters** *\_\_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 $qrt{thrm{end} - thrm{begin}}$ elements. Otherwise, the ratio between the longest and the shortest part is bounded by $1/(thrm{oversampling} dot thrm{num\_parts})$ **Returns** Length of the whole sequence. References **\_\_shrink\_and\_double()**, and **std::vector\< \_Tp, \_Alloc \>::size()**. ### template\ const \_Tp & \_\_gnu\_parallel::max (const \_Tp & \_\_a, const \_Tp & \_\_b) \[inline\] Equivalent to std::max. Referenced by **\_\_for\_each\_template\_random\_access\_workstealing()**. ### template\ const \_Tp & \_\_gnu\_parallel::min (const \_Tp & \_\_a, const \_Tp & \_\_b) \[inline\] Equivalent to std::min. Referenced by **\_\_for\_each\_template\_random\_access\_ed()**, **\_\_for\_each\_template\_random\_access\_omp\_loop()**, and **\_\_for\_each\_template\_random\_access\_workstealing()**. ### template\ void \_\_gnu\_parallel::multiseq\_partition (\_RanSeqs \_\_begin\_seqs, \_RanSeqs \_\_end\_seqs, \_RankType \_\_rank, \_RankIterator \_\_begin\_offsets, \_Compare \_\_comp = std::less\< typename std::iterator\_traits\::value\_type:: first\_type\>::value\_type\>()) Splits several sorted sequences at a certain global \_\_rank, resulting in a splitting point for each sequence. The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones on the \_\_left side will be chosen from sequences with smaller number. **Parameters** *\_\_begin\_seqs* Begin of the sequence of iterator pairs. \ *\_\_end\_seqs* End of the sequence of iterator pairs. \ *\_\_rank* The global rank to partition at. \ *\_\_begin\_offsets* A random-access \_\_sequence \_\_begin where the \_\_result will be stored in. Each element of the sequence is an iterator that points to the first element on the greater part of the respective \_\_sequence. \ *\_\_comp* The ordering functor, defaults to std::less\<\_Tp\>. References **\_\_rd\_log2()**, **\_GLIBCXX\_CALL**, **std::distance()**, **std::priority\_queue\< \_Tp, \_Sequence, \_Compare \>::empty()**, **std::make\_pair()**, **std::max()**, **std::min()**, **std::priority\_queue\< \_Tp, \_Sequence, \_Compare \>::pop()**, **std::priority\_queue\< \_Tp, \_Sequence, \_Compare \>::push()**, and **std::priority\_queue\< \_Tp, \_Sequence, \_Compare \>::top()**. Referenced by **multiway\_merge\_exact\_splitting()**. ### template\ \_Tp \_\_gnu\_parallel::multiseq\_selection (\_RanSeqs \_\_begin\_seqs, \_RanSeqs \_\_end\_seqs, \_RankType \_\_rank, \_RankType & \_\_offset, \_Compare \_\_comp = std::less\<\_Tp\>()) Selects the element at a certain global \_\_rank from several sorted sequences. The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. **Parameters** *\_\_begin\_seqs* Begin of the sequence of iterator pairs. \ *\_\_end\_seqs* End of the sequence of iterator pairs. \ *\_\_rank* The global rank to partition at. \ *\_\_offset* The rank of the selected element in the global subsequence of elements equal to the selected element. If the selected element is unique, this number is 0. \ *\_\_comp* The ordering functor, defaults to std::less. References **\_\_rd\_log2()**, **\_\_round\_up\_to\_pow2()**, **\_GLIBCXX\_CALL**, **std::distance()**, **std::priority\_queue\< \_Tp, \_Sequence, \_Compare \>::empty()**, **std::make\_pair()**, **std::max()**, **std::min()**, **std::priority\_queue\< \_Tp, \_Sequence, \_Compare \>::pop()**, **std::priority\_queue\< \_Tp, \_Sequence, \_Compare \>::push()**, and **std::priority\_queue\< \_Tp, \_Sequence, \_Compare \>::top()**. ### template\ \_RAIterOut \_\_gnu\_parallel::multiway\_merge (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, \_\_gnu\_parallel::sequential\_tag ) Multiway Merge Frontend. Merge the sequences specified by seqs\_begin and \_\_seqs\_end into \_\_target. \_\_seqs\_begin and \_\_seqs\_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the \_M\_end of the same sequence in their second entry. Ties are broken arbitrarily. See stable\_multiway\_merge for a variant that breaks ties by sequence number but is slower. The first entries of the pairs (i.e. the begin iterators) will be moved forward. The output sequence has to provide enough space for all elements that are written to it. This function will merge the input sequences: - • not stable - • parallel, depending on the input size and Settings - • using sampling for splitting - • not using sentinels Example: ``` int sequences[10][10]; for (int __i = 0; __i < 10; ++__i) for (int __j = 0; __i < 10; ++__j) sequences[__i][__j] = __j; int __out[33]; std::vector > seqs; for (int __i = 0; __i < 10; ++__i) { seqs.push(std::make_pair(sequences[__i], sequences[__i] + 10)) } multiway_merge(seqs.begin(), seqs.end(), __target, std::less(), 33); ``` **See also** stable\_multiway\_merge **Precondition** All input sequences must be sorted. Target must provide enough space to merge out length elements or the number of elements in all sequences, whichever is smaller. **Postcondition** \[\_\_target, return \_\_value) contains merged \_\_elements from the input sequences. return \_\_value - \_\_target = min(\_\_length, number of elements in all\ sequences). **Template Parameters** *\_RAIterPairIterator* iterator over sequence of pairs of iterators \ *\_RAIterOut* iterator over target sequence \ *\_DifferenceTp* difference type for the sequence \ *\_Compare* strict weak ordering type to compare elements in sequences **Parameters** *\_\_seqs\_begin* \_\_begin of sequence \_\_sequence \ *\_\_seqs\_end* \_M\_end of sequence \_\_sequence \ *\_\_target* target sequence to merge to. \ *\_\_comp* strict weak ordering to use for element comparison. \ *\_\_length* Maximum length to merge, possibly larger than the number of elements available. **Returns** \_M\_end iterator of output sequence References **\_\_sequential\_multiway\_merge()**, and **\_GLIBCXX\_CALL**. ### template\ class iterator, typename \_RAIterIterator, typename \_RAIter3, typename \_DifferenceTp, typename \_Compare\> \_RAIter3 \_\_gnu\_parallel::multiway\_merge\_3\_variant (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp) Highly efficient 3-way merging procedure. Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into labels in C++). This works well for merging up to 4 sequences. Note that making the merging stable does *not* come at a performance hit. Whether the merging is done guarded or unguarded is selected by the used iterator class. **Parameters** *\_\_seqs\_begin* Begin iterator of iterator pair input sequence. \ *\_\_seqs\_end* End iterator of iterator pair input sequence. \ *\_\_target* Begin iterator of output sequence. \ *\_\_comp* Comparator. \ *\_\_length* Maximum length to merge, less equal than the total number of elements available. **Returns** End iterator of output sequence. References **\_GLIBCXX\_CALL**. ### template\ class iterator, typename \_RAIterIterator, typename \_RAIter3, typename \_DifferenceTp, typename \_Compare\> \_RAIter3 \_\_gnu\_parallel::multiway\_merge\_4\_variant (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp) Highly efficient 4-way merging procedure. Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into goto labels in C++). This works well for merging up to 4 sequences. Note that making the merging stable does *not* come at a performance hit. Whether the merging is done guarded or unguarded is selected by the used iterator class. **Parameters** *\_\_seqs\_begin* Begin iterator of iterator pair input sequence. \ *\_\_seqs\_end* End iterator of iterator pair input sequence. \ *\_\_target* Begin iterator of output sequence. \ *\_\_comp* Comparator. \ *\_\_length* Maximum length to merge, less equal than the total number of elements available. **Returns** End iterator of output sequence. References **\_GLIBCXX\_CALL**. ### template\ void \_\_gnu\_parallel::multiway\_merge\_exact\_splitting (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_DifferenceType \_\_length, \_DifferenceType \_\_total\_length, \_Compare \_\_comp, std::vector\< std::pair\< \_DifferenceType, \_DifferenceType \> \> \* \_\_pieces) Exact splitting for parallel multiway-merge routine. None of the passed sequences may be empty. References **\_\_equally\_split()**, **\_GLIBCXX\_PARALLEL\_LENGTH**, **std::vector\< \_Tp, \_Alloc \>::begin()**, **std::vector\< \_Tp, \_Alloc \>::end()**, **multiseq\_partition()**, and **std::vector\< \_Tp, \_Alloc \>::resize()**. Referenced by **\_\_parallel\_merge\_advance()**. ### template\ \_RAIter3 \_\_gnu\_parallel::multiway\_merge\_loser\_tree (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp) Multi-way merging procedure for a high branching factor, guarded case. This merging variant uses a LoserTree class as selected by \_LT. Stability is selected through the used LoserTree class \_LT. At least one non-empty sequence is required. **Parameters** *\_\_seqs\_begin* Begin iterator of iterator pair input sequence. \ *\_\_seqs\_end* End iterator of iterator pair input sequence. \ *\_\_target* Begin iterator of output sequence. \ *\_\_comp* Comparator. \ *\_\_length* Maximum length to merge, less equal than the total number of elements available. **Returns** End iterator of output sequence. References **\_GLIBCXX\_CALL**, and **\_GLIBCXX\_PARALLEL\_LENGTH**. ### template\ \_RAIter3 \_\_gnu\_parallel::multiway\_merge\_loser\_tree\_sentinel (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, const typename std::iterator\_traits\< typename std::iterator\_traits\< \_RAIterIterator \>::value\_type::first\_type \>::value\_type & \_\_sentinel, \_DifferenceTp \_\_length, \_Compare \_\_comp) Multi-way merging procedure for a high branching factor, requiring sentinels to exist. **Template Parameters** *\_UnguardedLoserTree* Loser Tree variant to use for the unguarded merging. **Parameters** *\_\_seqs\_begin* Begin iterator of iterator pair input sequence. \ *\_\_seqs\_end* End iterator of iterator pair input sequence. \ *\_\_target* Begin iterator of output sequence. \ *\_\_comp* Comparator. \ *\_\_length* Maximum length to merge, less equal than the total number of elements available. **Returns** End iterator of output sequence. References **\_\_is\_sorted()**, **\_GLIBCXX\_CALL**, and **multiway\_merge\_loser\_tree\_unguarded()**. ### template\ \_RAIter3 \_\_gnu\_parallel::multiway\_merge\_loser\_tree\_unguarded (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, const typename std::iterator\_traits\< typename std::iterator\_traits\< \_RAIterIterator \>::value\_type::first\_type \>::value\_type & \_\_sentinel, \_DifferenceTp \_\_length, \_Compare \_\_comp) Multi-way merging procedure for a high branching factor, unguarded case. Merging is done using the LoserTree class \_LT. Stability is selected by the used LoserTrees. **Precondition** No input will run out of elements during the merge. **Parameters** *\_\_seqs\_begin* Begin iterator of iterator pair input sequence. \ *\_\_seqs\_end* End iterator of iterator pair input sequence. \ *\_\_target* Begin iterator of output sequence. \ *\_\_comp* Comparator. \ *\_\_length* Maximum length to merge, less equal than the total number of elements available. **Returns** End iterator of output sequence. References **\_GLIBCXX\_CALL**. Referenced by **multiway\_merge\_loser\_tree\_sentinel()**. ### template\ void \_\_gnu\_parallel::multiway\_merge\_sampling\_splitting (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_DifferenceType \_\_length, \_DifferenceType \_\_total\_length, \_Compare \_\_comp, std::vector\< std::pair\< \_DifferenceType, \_DifferenceType \> \> \* \_\_pieces) Sampling based splitting for parallel multiway-merge routine. References **\_GLIBCXX\_PARALLEL\_LENGTH**, **\_\_gnu\_parallel::\_Settings::get()**, and **\_\_gnu\_parallel::\_Settings::merge\_oversampling**. ### template\ \_RAIterOut \_\_gnu\_parallel::multiway\_merge\_sentinels (\_RAIterPairIterator \_\_seqs\_begin, \_RAIterPairIterator \_\_seqs\_end, \_RAIterOut \_\_target, \_DifferenceTp \_\_length, \_Compare \_\_comp, \_\_gnu\_parallel::sequential\_tag ) Multiway Merge Frontend. Merge the sequences specified by seqs\_begin and \_\_seqs\_end into \_\_target. \_\_seqs\_begin and \_\_seqs\_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the \_M\_end of the same sequence in their second entry. Ties are broken arbitrarily. See stable\_multiway\_merge for a variant that breaks ties by sequence number but is slower. The first entries of the pairs (i.e. the begin iterators) will be moved forward accordingly. The output sequence has to provide enough space for all elements that are written to it. This function will merge the input sequences: - • not stable - • parallel, depending on the input size and Settings - • using sampling for splitting - • using sentinels You have to take care that the element the \_M\_end iterator points to is readable and contains a value that is greater than any other non-sentinel value in all sequences. Example: ``` int sequences[10][11]; for (int __i = 0; __i < 10; ++__i) for (int __j = 0; __i < 11; ++__j) sequences[__i][__j] = __j; // __last one is sentinel! int __out[33]; std::vector > seqs; for (int __i = 0; __i < 10; ++__i) { seqs.push(std::make_pair(sequences[__i], sequences[__i] + 10)) } multiway_merge(seqs.begin(), seqs.end(), __target, std::less(), 33); ``` **Precondition** All input sequences must be sorted. Target must provide enough space to merge out length elements or the number of elements in all sequences, whichever is smaller. For each \_\_i, \_\_seqs\_begin\[\_\_i\].second must be the end marker of the sequence, but also reference the one more \_\_sentinel element. **Postcondition** \[\_\_target, return \_\_value) contains merged \_\_elements from the input sequences. return \_\_value - \_\_target = min(\_\_length, number of elements in all\ sequences). **See also** stable\_multiway\_merge\_sentinels **Template Parameters** *\_RAIterPairIterator* iterator over sequence of pairs of iterators \ *\_RAIterOut* iterator over target sequence \ *\_DifferenceTp* difference type for the sequence \ *\_Compare* strict weak ordering type to compare elements in sequences **Parameters** *\_\_seqs\_begin* \_\_begin of sequence \_\_sequence \ *\_\_seqs\_end* \_M\_end of sequence \_\_sequence \ *\_\_target* target sequence to merge to. \ *\_\_comp* strict weak ordering to use for element comparison. \ *\_\_length* Maximum length to merge, possibly larger than the number of elements available. **Returns** \_M\_end iterator of output sequence References **\_\_sequential\_multiway\_merge()**, and **\_GLIBCXX\_CALL**. ### template\ \_RAIter3 \_\_gnu\_parallel::parallel\_multiway\_merge (\_RAIterIterator \_\_seqs\_begin, \_RAIterIterator \_\_seqs\_end, \_RAIter3 \_\_target, \_Splitter \_\_splitter, \_DifferenceTp \_\_length, \_Compare \_\_comp, \_ThreadIndex \_\_num\_threads) Parallel multi-way merge routine. The \_GLIBCXX\_PARALLEL\_DECISION is based on the branching factor and runtime settings. Must not be called if the number of sequences is 1. **Template Parameters** *\_Splitter* functor to split input (either \_\_exact or sampling based) \ *\_\_stable* Stable merging incurs a performance penalty. \ *\_\_sentinel* Ignored. **Parameters** *\_\_seqs\_begin* Begin iterator of iterator pair input sequence. \ *\_\_seqs\_end* End iterator of iterator pair input sequence. \ *\_\_target* Begin iterator of output sequence. \ *\_\_comp* Comparator. \ *\_\_length* Maximum length to merge, possibly larger than the number of elements available. **Returns** End iterator of output sequence. References **\_\_is\_sorted()**, **\_\_sequential\_multiway\_merge()**, **\_GLIBCXX\_CALL**, **\_GLIBCXX\_PARALLEL\_LENGTH**, **\_\_gnu\_parallel::\_Settings::get()**, **std::make\_pair()**, **\_\_gnu\_parallel::\_Settings::merge\_oversampling**, and **std::min()**. Referenced by **\_\_parallel\_merge\_advance()**. ### template\ void \_\_gnu\_parallel::parallel\_sort\_mwms (\_RAIter \_\_begin, \_RAIter \_\_end, \_Compare \_\_comp, \_ThreadIndex \_\_num\_threads) PMWMS main call. **Parameters** *\_\_begin* Begin iterator of sequence. \ *\_\_end* End iterator of sequence. \ *\_\_comp* Comparator. \ *\_\_num\_threads* Number of threads to use. References **\_GLIBCXX\_CALL**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_num\_threads**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_offsets**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_pieces**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_samples**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_source**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_starts**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_temporary**, **\_\_gnu\_parallel::\_Settings::get()**, **parallel\_sort\_mwms\_pu()**, and **\_\_gnu\_parallel::\_Settings::sort\_mwms\_oversampling**. Referenced by **\_\_parallel\_sort()**, **\_\_parallel\_sort()**, **\_\_parallel\_sort()**, and **\_\_parallel\_sort()**. ### template\ void \_\_gnu\_parallel::parallel\_sort\_mwms\_pu (\_PMWMSSortingData\< \_RAIter \> \* \_\_sd, \_Compare & \_\_comp) PMWMS code executed by each thread. **Parameters** *\_\_sd* Pointer to algorithm data. \ *\_\_comp* Comparator. References **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_num\_threads**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_pieces**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_source**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_starts**, **\_\_gnu\_parallel::\_PMWMSSortingData\< \_RAIter \>::\_M\_temporary**, **\_\_gnu\_parallel::\_Settings::get()**, **std::make\_pair()**, **\_\_gnu\_parallel::\_Settings::sort\_mwms\_oversampling**, and **std::uninitialized\_copy()**. Referenced by **parallel\_sort\_mwms()**. ## Variable Documentation ### const int \_\_gnu\_parallel::\_CASable\_bits \[static\] Number of bits of \_CASable. Referenced by **\_\_decode2()**, and **\_\_encode2()**. ### const \_CASable \_\_gnu\_parallel::\_CASable\_mask \[static\] \_CASable with the right half of bits set to 1. Referenced by **\_\_decode2()**. ## Author Generated automatically by Doxygen for libstdc++ from the source code.