--- name: "__gnu_parallel" section: "3cxx" platform: "linux" package: "libstdc++-12-doc" version: "12.4.0-5" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/__gnu_parallel/3cxx" --- # \_\_gnu\_parallel(3cxx) 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* **\_\_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()***, and* **\_\_gnu\_parallel::\_Settings::get()***.* *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***, and* **\_\_gnu\_parallel::\_Settings::get()***.* ### 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* **\_GLIBCXX\_CALL***,* **\_\_gnu\_parallel::\_Settings::find\_scale\_factor***,* **\_\_gnu\_parallel::\_Settings::find\_sequential\_search\_size***, and* **\_\_gnu\_parallel::\_Settings::get()***.* ### 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()***.* *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).* *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).* ### 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* **\_\_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()***, 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* **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()***, 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()***,* **\_\_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::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* **\_\_gnu\_parallel::\_DRSSorterPU\< \_RAIter, \_RandomNumberGenerator \>::\_\_bins\_end***,* **\_\_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()***, and* **\_GLIBCXX\_CALL***.* ### 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()***, and* **\_GLIBCXX\_CALL***.* ### 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***, and* **\_\_gnu\_parallel::\_Settings::get()***.* ### 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***, and* **\_\_gnu\_parallel::\_Settings::get()***.* ### 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* **\_\_gnu\_parallel::\_QSBThreadLocal\< \_RAIter \>::\_M\_elements\_leftover***.* *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***, and* **\_\_gnu\_parallel::\_QSBThreadLocal\< \_RAIter \>::\_M\_initial***.* *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()***, 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***, 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***, and* **\_GLIBCXX\_PARALLEL\_LENGTH***.* *Referenced by* **multiway\_merge()***, and* **multiway\_merge\_sentinels()***.* ### 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::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.* *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()***.* *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()***.* ### template\ const \_Tp & \_\_gnu\_parallel::max (const \_Tp & \_\_a, const \_Tp & \_\_b)` [inline]` *Equivalent to std::max.* ### template\ const \_Tp & \_\_gnu\_parallel::min (const \_Tp & \_\_a, const \_Tp & \_\_b)` [inline]` *Equivalent to std::min.* *Referenced by* **\_\_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::max()***, and* **std::min()***.* *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::max()***, and* **std::min()***.* ### 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***, and* **multiseq\_partition()***.* *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()***, and* **\_GLIBCXX\_CALL***.* ### 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***.* ### 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()***,* **\_GLIBCXX\_CALL***,* **\_GLIBCXX\_PARALLEL\_LENGTH***,* **\_\_gnu\_parallel::\_Settings::get()***, and* **\_\_gnu\_parallel::\_Settings::merge\_oversampling***.* *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()***, and* **\_\_gnu\_parallel::\_Settings::sort\_mwms\_oversampling***.* ### 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()***,* **\_\_gnu\_parallel::\_Settings::sort\_mwms\_oversampling***, and* **std::uninitialized\_copy()***.* ## 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.*