__gnu_parallel(3)

📦

version 16.2.1+r23+gd564253eb6c8 · 8 versions

16.2.1+r23+gd564253eb6c8 · arch rolling, centos-stream 10, fedora 43, fedora 44 (latest)
11.5.0 · centos-stream 9
15.2.1 · centos-stream 9
16.2.1 · centos-stream 9
14.2.1 · centos-stream 9
13.3.1 · centos-stream 9
12.2.1 · centos-stream 9
4.4.0 · nixpkgs unstable

, in arch rolling, centos-stream 10, fedora 43, fedora 44

💅 `__gnu_parallel` — GNU parallel code for public use 💅

okay bestie, sit down, hydrate, and let me tell you about __gnu_parallel 💖 this is the page from section 3 of the Library Functions Manual, and it's literally the GNU parallel code for public use — all the shared machinery that makes GNU's parallel algorithms go brrr ⚡

it's giving "one header, a hundred little helper types, and every single one of them matters" 🫶 so let's do this properly, no skimming, no skipping. iykyk 🌸

💖 NAME 💖

__gnu_parallel — GNU parallel code for public use.

✨ SYNOPSIS ✨

this is the cast list, bestie — every class, typedef and enum that lives in here. buckle up, it's a big friend group 🌈

🎀 Classes 🎀

struct __accumulate_binop_reduct — general reduction, powered by a binary operator 🧮
struct __accumulate_selector — the selector for std::accumulate() ✨
struct __adjacent_difference_selector — hands you back the difference between two adjacent __elements 💫
struct __adjacent_find_selector — runs a predicate over two elements that are sitting right next to each other 👯
class __binder1st — basically std::binder1st, except it spells the argument types out loud, no guessing 🎀
class __binder2nd — std::binder2nd's cousin, argument types stated explicitly 💅
struct __count_if_selector — the selector for std::count_if () 🔢
struct __count_selector — the selector for std::count() 🔢
struct __fill_selector — the selector for std::fill() 🪣
struct __find_first_of_selector — tests a predicate on several elements at once 🔍
struct __find_if_selector — tests a predicate on one single element; this is the one std::find() and std::find_if () roll with 🔍
struct __for_each_selector — the selector for std::for_each() 🔁
struct __generate_selector — the selector for std::generate() 🌱
struct __generic_find_selector — the base class of all __gnu_parallel::__find_template selectors, the founding mother 👑
struct __generic_for_each_selector — the generic __selector for embarrassingly parallel functions 😌
struct __identity_selector — a selector that just returns the iterator you handed it, that's it, that's the whole job 🪞
struct __inner_product_selector — the selector for std::inner_product() ✖️
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 — tests an inverted predicate on a single element 🔄
struct __multiway_merge_3_variant_sentinel_switch — the switch for 3-way merging with __sentinels turned off 🔀
struct __multiway_merge_3_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare > — the switch for 3-way merging with __sentinels turned on 🔀
struct __multiway_merge_4_variant_sentinel_switch — the switch for 4-way merging with __sentinels turned off 🔀
struct __multiway_merge_4_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare > — the switch for 4-way merging with __sentinels turned on 🔀
struct __multiway_merge_k_variant_sentinel_switch — the switch for k-way merging with __sentinels turned on 🔀
struct __multiway_merge_k_variant_sentinel_switch< false, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare > — the switch for k-way merging with __sentinels turned off 🔀
struct __replace_if_selector — the selector for std::replace() ♻️
struct __replace_selector — the selector for std::replace() ♻️
struct __transform1_selector — the std::transform() __selector, one-input-sequence flavour ✨
struct __transform2_selector — the std::transform() __selector, two-input-sequences flavour ✨
class __unary_negate — like std::unary_negate, but the argument types are given explicitly 💫
struct _DRandomShufflingGlobalData — data that every thread taking part in __gnu_parallel::__parallel_random_shuffle() knows about 🃏
struct _DRSSorterPU — local data for one thread participating in __gnu_parallel::__parallel_random_shuffle() 🃏
struct _DummyReduct — a reduction function that does absolutely nothing 💀
class _EqualFromLess — constructs a predicate for equality out of a strict weak ordering predicate 🔁
struct _EqualTo — like std::equal_to, except it's chill with two different types 💞
class _GuardedIterator — an _Iterator wrapper that carries an implicit supremum at the end of the sequence, and that supremum dominates every single comparison 👑
class _IteratorPair — a pair of iterators; the usual iterator operations get applied to both child iterators 👯
class _IteratorTriple — a triple of iterators; the usual iterator operations get applied to all three child iterators 👯👯
struct _Job — one __job for a certain thread 🧾
struct _Less — like std::less, except it allows two different types 🤝
class _Lexicographic — compares __a pair of types lexicographically, ascending 🔤
class _LexicographicReverse — compares __a pair of types lexicographically, descending 🔤
class _LoserTree — the stable _LoserTree variant 🌳
class _LoserTree< false, _Tp, _Compare > — the 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 the _Loser Tree implementation that uses pointers 👉
class _LoserTreePointerUnguarded — stable unguarded _LoserTree variant that stores pointers 🎯
class _LoserTreePointerUnguarded< false, _Tp, _Compare > — unstable unguarded _LoserTree variant that stores pointers 🎯
class _LoserTreePointerUnguardedBase — unguarded loser tree that keeps only pointers to the elements in the tree structure 🎯
struct _LoserTreeTraits — traits that figure out whether the loser tree should be using pointers or copies 🤔
class _LoserTreeUnguarded — stable implementation of the unguarded _LoserTree 🌳
class _LoserTreeUnguarded< false, _Tp, _Compare > — non-stable implementation of the unguarded _LoserTree 🌳
class _LoserTreeUnguardedBase — base class for the unguarded _LoserTree implementation 🌳
struct _Multiplies — like std::multiplies, except it allows two different types ✖️
struct _Nothing — a functor doing nothing 🫥
struct _Piece — subsequence description 🧩
struct _Plus — like std::plus, except it allows two different types ➕
struct _PMWMSSortingData — data accessed by all threads 🗂️
class _PseudoSequence — a sequence that conceptually consists of multiple copies of the same element; the copies are not stored explicitly, of course 😌
class _PseudoSequenceIterator — the _Iterator associated with __gnu_parallel::_PseudoSequence; it 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 — a double-ended queue of bounded size that allows lock-free atomic access. push_front() and pop_front() must not be called concurrently with 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 the 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 the 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 — a type to hold the index of a bin 🗃️
typedef int64_t _CASable — the longest compare-and-swappable integer type on this platform 🔁
typedef uint64_t _SequenceIndex — unsigned integer for indexing __elements; the total number of elements for each algorithm has to fit into this type 📏
typedef uint16_t _ThreadIndex — unsigned integer for indexing a thread number; the maximum thread number (for each processor) has to 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 } — the 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 ✂️

bestie this is literally part one of ten, so don't you dare think we're done 💖 there is so much more of this page coming ✨

✨ Functions ✨

the function lineup, exact signatures only, no skips. every option and detail stays, only the vibe is upgraded. 💅

__add_omp — no description in the source, just this exact signature:

template<typename _Tp> _Tp __add_omp (volatile _Tp *__ptr, _Tp __addend)

__calc_borders — precalculates __advances for the Knuth-Morris-Pratt algorithm. string-matching prep fr fr.

template<typename _RAIter, typename _DifferenceTp> void __calc_borders
    (_RAIter __elements, _DifferenceTp __length, _DifferenceTp *__off)

__cas_omp — no description, exact signature:

template<typename _Tp> bool __cas_omp (volatile _Tp *__ptr, _Tp
    __comparand, _Tp __replacement)

__compare_and_swap — compare-and-swap. that's the whole vibe.

template<typename _Tp> bool __compare_and_swap (volatile _Tp *__ptr, _Tp
    __comparand, _Tp __replacement)

__copy_tail — no description, exact signature:

template<typename _IIter, typename _OutputIterator> _OutputIterator
    __copy_tail (std::pair< _IIter, _IIter > __b, std::pair< _IIter,
    _IIter > __e, _OutputIterator __r)

__decode2 — decodes two integers from one gnu_parallel::_CASable. cute.

void __decode2 (_CASable __x, int &__a, int &__b)

__determine_samples — selects _M_samples from a sequence. periodt.

template<typename _RAIter, typename _DifferenceTp> void
    __determine_samples (_PMWMSSortingData< _RAIter > *__sd,
    _DifferenceTp __num_samples)

__encode2 — encodes two integers into one gnu_parallel::_CASable. the reverse of decode, slay.

_CASable __encode2 (int __a, int __b)

__equally_split — function to split a sequence into parts of almost equal size. lowkey the group project splitter.

template<typename _DifferenceType, typename _OutputIterator>
    _OutputIterator __equally_split (_DifferenceType __n, _ThreadIndex
    __num_threads, _OutputIterator __s)

__equally_split_point — function to split a sequence into parts of almost equal size. same energy, different return.

template<typename _DifferenceType> _DifferenceType __equally_split_point
    (_DifferenceType __n, _ThreadIndex __num_threads, _ThreadIndex
    __thread_no)

__fetch_and_add — add a value to a variable, atomically. no cap, atomicity is the moment.

template<typename _Tp> _Tp __fetch_and_add (volatile _Tp *__ptr, _Tp
    __addend)

__find_template — parallel std::find, switch for different algorithms. the main character of find.

template<typename _RAIter1, typename _RAIter2, typename _Pred, typename
    _Selector> std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1
    __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred,
    _Selector __selector)

__find_template (constant_size_blocks_tag) — parallel std::find, constant block size variant. blocks stay same size, consistency queen.

template<typename _RAIter1, typename _RAIter2, typename _Pred, typename
    _Selector> std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1
    __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred,
    _Selector __selector, constant_size_blocks_tag)

__find_template (equal_split_tag) — parallel std::find, equal splitting variant. everyone gets a fair slice.

template<typename _RAIter1, typename _RAIter2, typename _Pred, typename
    _Selector> std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1
    __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred,
    _Selector __selector, equal_split_tag)

__find_template (growing_blocks_tag) — parallel std::find, growing block size variant. blocks start small and grow, it's giving adaptive.

template<typename _RAIter1, typename _RAIter2, typename _Pred, typename
    _Selector> std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1
    __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred,
    _Selector __selector, growing_blocks_tag)

__for_each_template_random_access — chose the desired algorithm by evaluating __parallelism_tag. it's the picker.

template<typename _IIter, typename _UserOp, typename _Functionality,
    typename _Red, typename _Result> _UserOp
    __for_each_template_random_access (_IIter __begin, _IIter __end,
    _UserOp __user_op, _Functionality &__functionality, _Red
    __reduction, _Result __reduction_start, _Result &__output, typename
    std::iterator_traits< _IIter >::difference_type __bound,
    _Parallelism __parallelism_tag)

__for_each_template_random_access_ed — embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work. hand-crafted? we love a bespoke moment.

template<typename _RAIter, typename _Op, typename _Fu, typename _Red,
    typename _Result> _Op __for_each_template_random_access_ed (_RAIter
    __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base,
    _Result &__output, typename std::iterator_traits< _RAIter
    >::difference_type __bound)

__for_each_template_random_access_omp_loop — embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop. OpenMP said let me handle this.

template<typename _RAIter, typename _Op, typename _Fu, typename _Red,
    typename _Result> _Op __for_each_template_random_access_omp_loop
    (_RAIter __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r,
    _Result __base, _Result &__output, typename std::iterator_traits<
    _RAIter >::difference_type __bound)

__for_each_template_random_access_omp_loop_static — embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling. static scheduling, she's stable.

template<typename _RAIter, typename _Op, typename _Fu, typename _Red,
    typename _Result> _Op
    __for_each_template_random_access_omp_loop_static (_RAIter __begin,
    _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base, _Result
    &__output, typename std::iterator_traits< _RAIter >::difference_type
    __bound)

__for_each_template_random_access_workstealing — work stealing algorithm for random access iterators. stealing work but make it collaborative. 💅

template<typename _RAIter, typename _Op, typename _Fu, typename _Red,
    typename _Result> _Op __for_each_template_random_access_workstealing
    (_RAIter __begin, _RAIter __end, _Op __op, _Fu &__f, _Red __r,
    _Result __base, _Result &__output, typename std::iterator_traits<
    _RAIter >::difference_type __bound)

__get_max_threads — no description, exact signature:

_ThreadIndex __get_max_threads ()

__is_parallel — no description, exact signature:

bool __is_parallel (const _Parallelism __p)

__is_sorted — check whether [__begin, __end) is sorted according to __comp. the vibe check for order.

template<typename _IIter, typename _Compare> bool __is_sorted (_IIter
    __begin, _IIter __end, _Compare __comp)

__median_of_three_iterators — compute the median of three referenced elements, according to __comp. middle child energy.

template<typename _RAIter, typename _Compare> _RAIter
    __median_of_three_iterators (_RAIter __a, _RAIter __b, _RAIter __c,
    _Compare __comp)

__merge_advance — merge routine being able to merge only the __max_length smallest elements. only the smallest, we're selective.

template<typename _RAIter1, typename _RAIter2, typename _OutputIterator,
    typename _DifferenceTp, typename _Compare> _OutputIterator
    __merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2
    &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp
    __max_length, _Compare __comp)

__merge_advance_movc — merge routine being able to merge only the __max_length smallest elements. same brief, different implementation.

template<typename _RAIter1, typename _RAIter2, typename _OutputIterator,
    typename _DifferenceTp, typename _Compare> _OutputIterator
    __merge_advance_movc (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2
    &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp
    __max_length, _Compare __comp)

__merge_advance_usual — merge routine being able to merge only the __max_length smallest elements. the usual, as the name says.

template<typename _RAIter1, typename _RAIter2, typename _OutputIterator,
    typename _DifferenceTp, typename _Compare> _OutputIterator
    __merge_advance_usual (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2
    &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp
    __max_length, _Compare __comp)

__parallel_merge_advance — parallel merge routine being able to merge only the __max_length smallest elements. parallel merge, slay.

template<typename _RAIter1, typename _RAIter3, typename _Compare>
    _RAIter3 __parallel_merge_advance (_RAIter1 &__begin1, _RAIter1
    __end1, _RAIter1 &__begin2, _RAIter1 __end2, _RAIter3 __target,
    typename std::iterator_traits< _RAIter1 >::difference_type
    __max_length, _Compare __comp)

__parallel_merge_advance — merge routine fallback to sequential in case the iterators of the two input sequences are of different type. when types don't match, it falls back, no drama.

template<typename _RAIter1, typename _RAIter2, typename _RAIter3,
    typename _Compare> _RAIter3 __parallel_merge_advance (_RAIter1
    &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2,
    _RAIter3 __target, typename std::iterator_traits< _RAIter1
    >::difference_type __max_length, _Compare __comp)

__parallel_nth_element — parallel implementation of std::nth_element(). nth element but make it parallel.

template<typename _RAIter, typename _Compare> void
    __parallel_nth_element (_RAIter __begin, _RAIter __nth, _RAIter
    __end, _Compare __comp)

__parallel_partial_sort — parallel implementation of std::partial_sort(). partial sort, full parallel energy.

template<typename _RAIter, typename _Compare> void
    __parallel_partial_sort (_RAIter __begin, _RAIter __middle, _RAIter
    __end, _Compare __comp)

__parallel_partial_sum — parallel partial sum front-__end. front to end, parallel.

template<typename _IIter, typename _OutputIterator, typename
    _BinaryOperation> _OutputIterator __parallel_partial_sum (_IIter
    __begin, _IIter __end, _OutputIterator __result, _BinaryOperation
    __bin_op)

__parallel_partial_sum_basecase — base case prefix sum routine. the base case, holding it down.

template<typename _IIter, typename _OutputIterator, typename
    _BinaryOperation> _OutputIterator __parallel_partial_sum_basecase
    (_IIter __begin, _IIter __end, _OutputIterator __result,
    _BinaryOperation __bin_op, typename std::iterator_traits< _IIter
    >::value_type __value)

__parallel_partial_sum_linear — parallel partial sum implementation, two-phase approach, no recursion. two-phase, no recursion, clean.

template<typename _IIter, typename _OutputIterator, typename
    _BinaryOperation> _OutputIterator __parallel_partial_sum_linear
    (_IIter __begin, _IIter __end, _OutputIterator __result,
    _BinaryOperation __bin_op, typename std::iterator_traits< _IIter
    >::difference_type __n)

__parallel_partition — parallel implementation of std::partition. partition but parallel.

template<typename _RAIter, typename _Predicate> std::iterator_traits<
    _RAIter >::difference_type __parallel_partition (_RAIter __begin,
    _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads)

__parallel_random_shuffle — parallel random public call. public call, random shuffle.

template<typename _RAIter, typename _RandomNumberGenerator> void
    __parallel_random_shuffle (_RAIter __begin, _RAIter __end,
    _RandomNumberGenerator __rng=_RandomNumber())

__parallel_random_shuffle_drs — main parallel random shuffle step. the main step, main character.

template<typename _RAIter, typename _RandomNumberGenerator> void
    __parallel_random_shuffle_drs (_RAIter __begin, _RAIter __end,
    typename std::iterator_traits< _RAIter >::difference_type __n,
    _ThreadIndex __num_threads, _RandomNumberGenerator &__rng)

__parallel_random_shuffle_drs_pu — random shuffle code executed by each thread. each thread gets a turn.

template<typename _RAIter, typename _RandomNumberGenerator> void
    __parallel_random_shuffle_drs_pu (_DRSSorterPU< _RAIter,
    _RandomNumberGenerator > *__pus)

__parallel_set_difference — no description, exact signature:

template<typename _IIter, typename _OutputIterator, typename _Compare>
    _OutputIterator __parallel_set_difference (_IIter __begin1, _IIter
    __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result,
    _Compare __comp)

__parallel_set_intersection — no description, exact signature:

template<typename _IIter, typename _OutputIterator, typename _Compare>
    _OutputIterator __parallel_set_intersection (_IIter __begin1, _IIter
    __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result,
    _Compare __comp)

__parallel_set_operation — no description, exact signature:

template<typename _IIter, typename _OutputIterator, typename _Operation>
    _OutputIterator __parallel_set_operation (_IIter __begin1, _IIter
    __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result,
    _Operation __op)

and the source cuts off mid-signature here:

template<typename _IIter, typename _OutputIterator, typename _Compare>

template<typename _IIter, typename _OutputIterator, typename _Compare>
    _OutputIterator __parallel_set_symmetric_difference (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp)

no little blurb in the docs for this one bestie, she's just here, existing, looking gorgeous 💜

template<typename _IIter, typename _OutputIterator, typename _Compare>
    _OutputIterator __parallel_set_union (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp)

same energy — signature only, no commentary, and honestly? iconic for that 🌈

template<bool __stable, typename _RAIter, typename _Compare, typename _Parallelism>
    void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, _Parallelism __parallelism)

the generic sort-y one, no blurb attached, take the signature and go 💖

✨ okay but now we get to the __parallel_sort overloads and they ALL have opinions ✨

template<bool __stable, typename _RAIter, typename _Compare>
    void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp,
    balanced_quicksort_tag __parallelism)

Choose balanced quicksort for parallel sorting. like, when you want your parallel sort to be balanced quicksort specifically 🎀

template<bool __stable, typename _RAIter, typename _Compare>
    void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp,
    default_parallel_tag __parallelism)

Choose multiway mergesort with exact splitting, for parallel sorting. yep, exact splitting, that's the whole vibe ✨

template<bool __stable, typename _RAIter, typename _Compare>
    void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp,
    multiway_mergesort_exact_tag __parallelism)

Choose multiway mergesort with exact splitting, for parallel sorting. twins with the one above fr fr 👯

template<bool __stable, typename _RAIter, typename _Compare>
    void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp,
    multiway_mergesort_sampling_tag __parallelism)

Choose multiway mergesort with splitting by sampling, for parallel sorting. different splitting, still mergesort, still parallel, still slaying 🌸

template<bool __stable, typename _RAIter, typename _Compare>
    void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp,
    multiway_mergesort_tag __parallelism)

Choose multiway mergesort, splitting variant at run-time, for parallel sorting. she picks her splitting variant at run-time, she's flexible like that 💅

template<bool __stable, typename _RAIter, typename _Compare>
    void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp,
    parallel_tag __parallelism)

Choose a parallel sorting algorithm. just. a parallel sorting algorithm. dealer's choice, bestie 👑

template<bool __stable, typename _RAIter, typename _Compare>
    void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp,
    quicksort_tag __parallelism)

Choose quicksort for parallel sorting. quicksort, parallel, periodt 🔥

🎀 the unbalanced quicksort girlies 🎀

template<typename _RAIter, typename _Compare>
    void __parallel_sort_qs (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)

Unbalanced quicksort main call. the main character of the unbalanced quicksort situation 💫

template<typename _RAIter, typename _Compare>
    void __parallel_sort_qs_conquer (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)

Unbalanced quicksort conquer step. she conquers. literally. 🗡️

template<typename _RAIter, typename _Compare>
    std::iterator_traits<_RAIter>::difference_type __parallel_sort_qs_divide (_RAIter __begin, _RAIter __end, _Compare __comp, typename std::iterator_traits<_RAIter>::difference_type __pivot_rank, typename std::iterator_traits<_RAIter>::difference_type __num_samples, _ThreadIndex __num_threads)

Unbalanced quicksort divide step. divide, then conquer, that's the order, don't @ me ✨

template<typename _RAIter, typename _Compare>
    void __parallel_sort_qsb (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)

Top-level quicksort routine. top level, top tier, top everything 🌟

🦋 unique_copy but make it parallel 🦋

template<typename _IIter, class _OutputIterator>
    _OutputIterator __parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result)

Parallel std::unique_copy(), without explicit equality predicate. no predicate, she just knows 🫶

template<typename _IIter, class _OutputIterator, class _BinaryPredicate>
    _OutputIterator __parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result, _BinaryPredicate __binary_pred)

Parallel std::unique_copy(), w/__o explicit equality predicate. yes, the docs literally say w/__o, we are NOT fixing it, it's part of her charm 😭

💜 balanced quicksort internals, the backstage pass 💜

template<typename _RAIter, typename _Compare>
    void __qsb_conquer (_QSBThreadLocal<_RAIter> **__tls, _RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __iam, _ThreadIndex __num_threads, bool __parent_wait)

Quicksort conquer step. (the b stands for balanced, iykyk) 💜

template<typename _RAIter, typename _Compare>
    std::iterator_traits<_RAIter>::difference_type __qsb_divide (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)

Balanced quicksort divide step. balanced this time, not like her chaotic cousin up there ⚖️

template<typename _RAIter, typename _Compare>
    void __qsb_local_sort_with_helping (_QSBThreadLocal<_RAIter> **__tls, _Compare &__comp, _ThreadIndex __iam, bool __wait)

Quicksort step doing load-balanced local sort. she does a local sort AND balances the load AND helps?? she's literally the whole team 🫶

⭐ lil math besties, they're so cute ⭐

template<typename _RandomNumberGenerator>
    int __random_number_pow2 (int __logp, _RandomNumberGenerator &__rng)

Generate a random number in [0,2^__logp). note the half-open interval bestie, it does NOT include 2^__logp 🌸

template<typename _Size>
    _Size __rd_log2 (_Size __n)

Calculates the rounded-down logarithm of __n for base 2. rounded DOWN. not up. down. 🍓

template<typename _Tp>
    _Tp __round_up_to_pow2 (_Tp __x)

Round up to the next greater power of 2. and this one rounds UP, see, they're a matched set 🎀

🔍 search, but parallel 🔍

template<typename __RAIter1, typename __RAIter2, typename _Pred>
    __RAIter1 __search_template (__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred)

Parallel std::search. parallel search, parallel vibes, parallel everything 🌊

🧚 sequential things that are quietly doing the most 🧚

template<bool __stable, bool __sentinels, typename _RAIterIterator, typename _RAIter3, typename _DifferenceTp, typename _Compare>
    _RAIter3 __sequential_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits<typename std::iterator_traits<_RAIterIterator>::value_type::first_type>::value_type &__sentinel, _DifferenceTp __length, _Compare __comp)

Sequential multi-way merging switch. she's a switch, and she's sequential, and she merges multiple ways, that's three whole things 🔀

template<typename _RAIter, typename _RandomNumberGenerator>
    void __sequential_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng)

Sequential cache-efficient random shuffle. sequential AND cache-efficient AND random, she contains multitudes ✨

🎀 the range-shrinking situation (this is such a serve) 🎀

template<typename _IIter>
    void __shrink (std::vector<_IIter> &__os_starts, size_t &__count_to_two, size_t &__range_length)

Combines two ranges into one and thus halves the number of ranges. two become one, math is beautiful actually 💖

template<typename _IIter>
    void __shrink_and_double (std::vector<_IIter> &__os_starts, size_t &__count_to_two, size_t &__range_length, const bool __make_twice)

Shrinks and doubles the ranges. shrink AND double, she's doing both, she's unhinged, we love her 😭

void __yield ()

Yield control to another thread, without waiting for the end of the time slice. no arguments, no waiting, she just yields and dips immediately 💅

template<typename _IIter, typename _FunctorType>
    size_t list_partition (const _IIter __begin, const _IIter __end, _IIter *__starts, size_t *__lengths, const int __num_parts, _FunctorType &__f, int __oversampling=0)

Splits a sequence given by input iterators into parts of almost equal size. almost equal bestie, not exactly equal, don't come for her. also hi __oversampling=0, the default 💙

template<typename _Tp>
    const _Tp & max (const _Tp &__a, const _Tp &__b)

Equivalent to std::max. just std::max. that's it. that's the description 🌿

template<typename _Tp>
    const _Tp & min (const _Tp &__a, const _Tp &__b)

Equivalent to std::min. and here's std::min's twin, standing right next to her 💚

🌈 multiseq time, and these descriptions EAT 🌈

template<typename _RanSeqs, typename _RankType, typename _RankIterator, typename _Compare>
    void multiseq_partition (_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankIterator __begin_offsets, _Compare __comp=std::less<typename std::iterator_traits<typename std::iterator_traits<_RanSeqs>::value_type::first_type>::value_type>())

Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each sequence. 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.

okay that was a lot, let me translate: sequences come in as pairs of random-access iterators, none of them may be empty (rule is a rule), and if there's a tie across the split, the left side wins and it's picked from the sequence with the smaller number. also yes, the __comp default is that whole std::less<...> monster, we're keeping every character of it 💖

template<typename _Tp, typename _RanSeqs, typename _RankType, typename _Compare>
    _Tp multiseq_selection (_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankType &__offset, _Compare __comp=std::less<_Tp>())

Selects the element at a certain global __rank from several sorted sequences.

and she's got a __comp defaulted to std::less<_Tp>(), plus a __offset she fills in for you 🫶

💫 multiway_merge overload family portrait 💫

template<typename _RAIterPairIterator, typename _RAIterOut, typename _DifferenceTp, typename _Compare>
    _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag)

no blurb for the exact_tag one, bestie — she's just out here taking an __gnu_parallel::exact_tag and being mysterious 🔵

template<typename _RAIterPairIterator, typename _RAIterOut, typename _DifferenceTp, typename _Compare>
    _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sampling_tag __tag)

same deal for sampling_tag — no description in the docs, just the signature, and she's serving anyway 🌊

template<typename _RAIterPairIterator, typename _RAIterOut, typename _DifferenceTp, typename _Compare>
    _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)

Multiway Merge Frontend. the frontend!! she's the face of the operation 💅

template<typename _RAIterPairIterator, typename _RAIterOut, typename _DifferenceTp, typename _Compare>
    _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag)

no blurb for the default_parallel_tag overload either — signature only, she's lowkey about it 🙈

template<typename _RAIterPairIterator, typename _RAIterOut, typename _DifferenceTp, typename _Compare>
    _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))

and the parallel_tag one has no description either, but she DOES have a default: __tag=parallel_tag(0). keep that, it matters ⭐

🔥 the 3-way and 4-way girlies 🔥

template<template<typename _RAI, typename _Cp> 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. highly efficient. the docs said highly. they meant it 🔥

template<template<typename _RAI, typename _Cp> 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. four ways this time, equally highly efficient, equally iconic 👑

template<bool __stable, typename _RAIterIterator, typename _Compare, typename _DifferenceType>
    void multiway_merge_exact_splitting (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)

Exact splitting for parallel multiway-merge routine. exact, not approximate, she does not do approximate ✨

template<typename _LT, typename _RAIterIterator, typename _RAIter3,

bestie this one got cut off mid-signature in the source 😭 — she's literally still being written, we'll pick her back up in the next part, don't panic 🫶

typename _DifferenceTp, typename _Compare> _RAIter3
multiway_merge_loser_tree (_RAIterIterator __seqs_begin,
_RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp
__length, _Compare __comp)

Multi-way merging procedure for a high branching factor, guarded case. 💅 It's giving guarded merging realness, no cap.

multiway_merge_loser_tree_sentinel — Multi-way merging procedure for a high branching factor, requiring sentinels to exist. 🛡️

template<typename _UnguardedLoserTree, typename _RAIterIterator,
    typename _RAIter3, typename _DifferenceTp, typename _Compare>
    _RAIter3 multiway_merge_loser_tree_sentinel (_RAIterIterator
    __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const
    typename std::iterator_traits< typename std::iterator_traits<
    _RAIterIterator >::value_type::first_type >::value_type &__sentinel,
    _DifferenceTp __length, _Compare __comp)

multiway_merge_loser_tree_unguarded — Multi-way merging procedure for a high branching factor, unguarded case. 😈

template<typename _LT, typename _RAIterIterator, typename _RAIter3,
    typename _DifferenceTp, typename _Compare> _RAIter3
    multiway_merge_loser_tree_unguarded (_RAIterIterator __seqs_begin,
    _RAIterIterator __seqs_end, _RAIter3 __target, const typename
    std::iterator_traits< typename std::iterator_traits< _RAIterIterator
    >::value_type::first_type >::value_type &__sentinel, _DifferenceTp
    __length, _Compare __comp)

multiway_merge_sampling_splitting — Sampling based splitting for parallel multiway-merge routine. 🎲

template<bool __stable, typename _RAIterIterator, typename _Compare,
    typename _DifferenceType> void multiway_merge_sampling_splitting
    (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end,
    _DifferenceType __length, _DifferenceType __total_length, _Compare
    __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > >
    *__pieces)

multiway_merge_sentinels (with __gnu_parallel::exact_tag __tag)

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut
    multiway_merge_sentinels (_RAIterPairIterator __seqs_begin,
    _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp
    __length, _Compare __comp, __gnu_parallel::exact_tag __tag)

multiway_merge_sentinels (with __gnu_parallel::sequential_tag) — Multiway Merge Frontend. 🚀

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut
    multiway_merge_sentinels (_RAIterPairIterator __seqs_begin,
    _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp
    __length, _Compare __comp, __gnu_parallel::sequential_tag)

multiway_merge_sentinels (with default_parallel_tag __tag)

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut
    multiway_merge_sentinels (_RAIterPairIterator __seqs_begin,
    _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp
    __length, _Compare __comp, default_parallel_tag __tag)

multiway_merge_sentinels (with parallel_tag __tag=parallel_tag(0))

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut
    multiway_merge_sentinels (_RAIterPairIterator __seqs_begin,
    _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp
    __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))

multiway_merge_sentinels (with sampling_tag __tag)

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut
    multiway_merge_sentinels (_RAIterPairIterator __seqs_begin,
    _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp
    __length, _Compare __comp, sampling_tag __tag)

parallel_multiway_merge — Parallel multi-way merge routine. 🔥

template<bool __stable, bool __sentinels, typename _RAIterIterator,
    typename _RAIter3, typename _DifferenceTp, typename _Splitter,
    typename _Compare> _RAIter3 parallel_multiway_merge (_RAIterIterator
    __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target,
    _Splitter __splitter, _DifferenceTp __length, _Compare __comp,
    _ThreadIndex __num_threads)

parallel_sort_mwms — PMWMS main call. 👑

template<bool __stable, bool __exact, typename _RAIter, typename
    _Compare> void parallel_sort_mwms (_RAIter __begin, _RAIter __end,
    _Compare __comp, _ThreadIndex __num_threads)

parallel_sort_mwms_pu — PMWMS code executed by each thread. 🧵

template<bool __stable, bool __exact, typename _RAIter, typename
    _Compare> void parallel_sort_mwms_pu (_PMWMSSortingData< _RAIter >
    *__sd, _Compare &__comp)

stable_multiway_merge (with __gnu_parallel::exact_tag __tag)

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut stable_multiway_merge
    (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end,
    _RAIterOut __target, _DifferenceTp __length, _Compare __comp,
    __gnu_parallel::exact_tag __tag)

stable_multiway_merge (with __gnu_parallel::sequential_tag)

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut stable_multiway_merge
    (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end,
    _RAIterOut __target, _DifferenceTp __length, _Compare __comp,
    __gnu_parallel::sequential_tag)

stable_multiway_merge (with default_parallel_tag __tag)

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut stable_multiway_merge
    (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end,
    _RAIterOut __target, _DifferenceTp __length, _Compare __comp,
    default_parallel_tag __tag)

stable_multiway_merge (with parallel_tag __tag=parallel_tag(0))

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut stable_multiway_merge
    (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end,
    _RAIterOut __target, _DifferenceTp __length, _Compare __comp,
    parallel_tag __tag=parallel_tag(0))

stable_multiway_merge (with sampling_tag __tag)

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut stable_multiway_merge
    (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end,
    _RAIterOut __target, _DifferenceTp __length, _Compare __comp,
    sampling_tag __tag)

stable_multiway_merge_sentinels (with __gnu_parallel::exact_tag __tag)

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut
    stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin,
    _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp
    __length, _Compare __comp, __gnu_parallel::exact_tag __tag)

stable_multiway_merge_sentinels (with __gnu_parallel::sequential_tag)

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut
    stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin,
    _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp
    __length, _Compare __comp, __gnu_parallel::sequential_tag)

stable_multiway_merge_sentinels (with default_parallel_tag __tag)

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut
    stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin,
    _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp
    __length, _Compare __comp, default_parallel_tag __tag)

stable_multiway_merge_sentinels (with parallel_tag __tag=parallel_tag(0))

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut
    stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin,
    _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp
    __length, _Compare __comp, parallel_tag __tag=parallel_tag(0))

stable_multiway_merge_sentinels (with sampling_tag __tag)

template<typename _RAIterPairIterator, typename _RAIterOut, typename
    _DifferenceTp, typename _Compare> _RAIterOut
    stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin,
    _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp
    __length, _Compare __comp, 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. 💖 It's giving open-source, bestie. No cap.

🎀 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. 🏷️
- 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 🔥

__calc_borders

template<typename _RAIter, typename _DifferenceTp> 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().

__compare_and_swap

template<typename _Tp> 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().

__decode2

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().

🌸 `__determine_samples`

template<typename _RAIter, typename _DifferenceTp>
void __gnu_parallel::__determine_samples(_PMWMSSortingData< _RAIter > * __sd, _DifferenceTp __num_samples)

okay so this one's whole job is picking out _M_samples from a sequence 💅 like it goes shopping and comes back with the samples, no cap.

Parameters

__sd — pointer to the algorithm data, bestie. The _Result gets parked right into __sd->_M_samples.
__num_samples — how many _M_samples we're selecting. the count, the whole vibe.

References — __equally_split(), __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_samples, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, and __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts.

🎀 `__encode2`

_CASable __gnu_parallel::__encode2(int __a, int __b) [inline]

packing two integers into ONE gnu_parallel::_CASable. two little guys, one container. iconic honestly ✨

Parameters

__a — first integer, and it gets encoded into the most-significant _CASable_bits/2 bits. front of the line, main character.
__b — second integer, encoded into the least-significant _CASable_bits/2 bits. back of the bus but still slaying.

Returns — a value that encodes __a and __b together. periodt.

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().

🦋 `__equally_split`

template<typename _DifferenceType, typename _OutputIterator>
_OutputIterator __gnu_parallel::__equally_split(_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s)

the function that splits a sequence into parts of almost equal size 🫶 and yes, the word is almost, don't come for me. the resulting sequence __s of length __num_threads+1 holds all the splitting positions you get when you split the range [0,__n) into parts of almost equal size (plus minus 1, okay, it's giving approximate). the first entry is 0, the last one is n. and heads up — you may end up with empty parts. it happens. no one's judging 🙈

Parameters

__n — number of elements.
__num_threads — number of parts.
__s — the splitters themselves.

Returns — the end of the __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().

🌸 `__equally_split_point`

template<typename _DifferenceType>
_DifferenceType __gnu_parallel::__equally_split_point(_DifferenceType __n, _ThreadIndex __num_threads, _ThreadIndex __thread_no)

another splitter function, bestie, but this one's a little different — it hands you the position of the splitting point between thread number __thread_no (included) and thread number __thread_no+1 (excluded). so it's literally telling you where the line is drawn between those two threads 💅

Parameters

__n — number of elements.
__num_threads — number of parts.
__thread_no — number of threads.

Returns — the splitting point. that's it, that's the whole thing.

Referenced by — __for_each_template_random_access_ed().

✨ `__fetch_and_add`

template<typename _Tp>
_Tp __gnu_parallel::__fetch_and_add(volatile _Tp * __ptr, _Tp __addend) [inline]

adds a value to a variable, and it does it atomically 🔥 no race conditions, no drama, no two threads fighting over the same number like it's the last croissant.

Parameters

__ptr — pointer to a signed integer.
__addend — the value to add.

Referenced by — __find_template(), __for_each_template_random_access_workstealing(), __parallel_partition(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::push_front().

💜 `__find_template` (the dispatcher)

template<typename _RAIter1, typename _RAIter2, typename _Pred, typename _Selector>
std::pair< _RAIter1, _RAIter2 >
__gnu_parallel::__find_template(_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector) [inline]

this is the parallel std::find, and it's basically the switchboard operator that picks between the different algorithms 🎀 one call, many vibes.

Parameters

__begin1 — begin iterator of the first sequence.
__end1 — end iterator of the first sequence.
__begin2 — begin iterator of the second sequence. must have same length as the first sequence, no exceptions.
__pred — the find predicate.
__selector — the _Functionality (e. g. std::find_if(), std::equal(),...).

Returns — the place of finding in both sequences.

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

Referenced by — __find_template().

🌈 `__find_template` (constant block size variant)

template<typename _RAIter1, typename _RAIter2, typename _Pred, typename _Selector>
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, but the constant block size flavour. the blocks stay the same size the entire time. consistency queen 👑

Parameters

__begin1 — begin iterator of the first sequence.
__end1 — end iterator of the first sequence.
__begin2 — begin iterator of the second sequence. the second __sequence must have same length as the first sequence.
__pred — the find predicate.
__selector — the _Functionality (e. g. std::find_if(), std::equal(),...).

Returns — the 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, and I'm listing them because they matter:

For GB, the block size grows; for CSB, the block size is fixed.
For GB, the blocks are allocated dynamically; for CSB, the blocks are allocated in a predetermined manner, namely spacial round-robin.

References — _GLIBCXX_CALL, __gnu_parallel::_Settings::find_initial_block_size, __gnu_parallel::_Settings::find_sequential_search_size, std::pair< _T1, _T2 >::first, __gnu_parallel::_Settings::get(), and std::min().

⭐ `__find_template` (equal splitting variant)

template<typename _RAIter1, typename _RAIter2, typename _Pred, typename _Selector>
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. everyone gets their fair share, we love an even split 🫶

Parameters

__begin1 — begin iterator of the first sequence.
__end1 — end iterator of the first sequence.
__begin2 — begin iterator of the second sequence. the second __sequence must have same length as the first sequence.
__pred — the find predicate.
__selector — the _Functionality (e. g. std::find_if(), std::equal(),...).

Returns — the place of finding in both sequences.

References — __equally_split(), and _GLIBCXX_CALL.

🔥 `__find_template` (growing blocks variant)

template<typename _RAIter1, typename _RAIter2, typename _Pred, typename _Selector>
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. the blocks literally start small and grow up. glow-up arc 🌱➡️🌳

Parameters

__begin1 — begin iterator of the first sequence.
__end1 — end iterator of the first sequence.
__begin2 — begin iterator of the second sequence. the second __sequence must have same length as the first sequence.
__pred — the find predicate.
__selector — the _Functionality (e. g. std::find_if(), std::equal(),...).

Returns — the 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 — same list, because it's the same comparison:

For GB, the block size grows; for CSB, the block size is fixed.
For GB, the blocks are allocated dynamically; for CSB, the blocks are allocated in a predetermined manner, namely spacial round-robin.

References — __fetch_and_add(), _GLIBCXX_CALL, __gnu_parallel::_Settings::find_scale_factor, __gnu_parallel::_Settings::find_sequential_search_size, std::pair< _T1, _T2 >::first, __gnu_parallel::_Settings::get(), std::max(), and std::min().

💖 `__for_each_template_random_access`

template<typename _IIter, typename _UserOp, typename _Functionality, typename _Red, typename _Result>
_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)

this one chooses the desired algorithm by evaluating __parallelism_tag. it's the group-chat admin deciding which plan we're going with based on the 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 — the 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.

🎀 `__for_each_template_random_access_ed`

template<typename _RAIter, typename _Op, typename _Fu, typename _Red, typename _Result>
_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)

the embarrassingly parallel algorithm for random access iterators, doing hand-crafted parallelization by equal splitting the work ✨ hand-crafted!! artisanal!! no cap.

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 — the user-supplied functor (that may contain a part of the result). yeah, it hands the functor back to you, and it might be carrying some of the result inside. sneaky but iconic.

References — __equally_split_point(), and min().

Referenced by — __for_each_template_random_access().

🧚 `__for_each_template_random_access_omp_loop`

template<typename _RAIter, typename _Op, typename _Fu, typename _Red, typename _Result>
_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, but this time it's using an OpenMP for loop 🌸 same energy, different engine.

✨ Parameters ✨

__begin — begin iterator of the element sequence, bestie. where it all starts 🫶
__end — end iterator of the element sequence. the finish line, we don't touch it.
__o — the user-supplied functor (comparator, predicate, adding functor, whatever flavour of the above you're on today).
__f — the functor that processes an element together with __op. what exactly it does depends on what you're trying to do, e.g. for std::for_each(), ...
__r — the functor that adds a single __result onto the elements that have already been processed (again, depends on the functionality).
__base — the base value for the reduction. the lil seed everything grows from 🌱
__output — pointer to the position where the final result gets written. the final destination, no cap.
__bound — the maximum number of elements processed (e.g. for std::count_n()).

💖 Returns

The user-supplied functor (which may contain a part of the result). yes it hands you back your own functor, possibly holding onto some of the work it did.

References min().

Referenced by __for_each_template_random_access().

template<typename _RAIter, typename _Op, typename _Fu, typename _Red,
    typename _Result> _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, and it does it with an OpenMP for loop on static scheduling. set it and forget it energy 💅

🌸 Parameters

__begin — begin iterator of element sequence.
__end — end iterator of element sequence.
__o — user-supplied functor (comparator, predicate, adding functor, ...).
__f — functor to process an element with __op (depends on desired functionality, e. g. for std::for_each(), ...).
__r — functor to add a single __result to the already processed __elements (depends on functionality).
__base — base value for reduction.
__output — pointer to position where final result is written to
__bound — maximum number of elements processed (e. g. for std::count_n()).

🦋 Returns

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

References std::min().

template<typename _RAIter, typename _Op, typename _Fu, typename _Red,
    typename _Result> _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. this one is so iconic — it uses O(1) additional memory, and the synchronization at the job lists is done with atomic operations. no locks, just vibes and atomics ✨

💜 Parameters

__begin — begin iterator of element sequence.
__end — end iterator of element sequence.
__op — user-supplied functor (comparator, predicate, adding functor, ...).
__f — functor to process an element with __op (depends on desired functionality, e. g. for std::for_each(), ...).
__r — functor to add a single __result to the already processed elements (depends on functionality).
__base — base value for reduction.
__output — pointer to position where final result is written to
__bound — maximum number of elements processed (e. g. for std::count_n()).

⭐ Returns

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

References __fetch_and_add(), __yield(), _GLIBCXX_CALL, __gnu_parallel::_Job< _DifferenceTp >::_M_first, __gnu_parallel::_Job< _DifferenceTp >::_M_last, __gnu_parallel::_Job< _DifferenceTp >::_M_load, __gnu_parallel::_Settings::cache_line_size, __gnu_parallel::_Settings::get(), max(), and min().

Referenced by __for_each_template_random_access().

template<typename _IIter, typename _Compare> bool
    __gnu_parallel::__is_sorted (_IIter __begin, _IIter __end, _Compare
    __comp)

Check whether [__begin, __end) is sorted according to __comp. vibe check but for ordering, honestly 🎀

🍓 Parameters

__begin — begin iterator of sequence.
__end — end iterator of sequence.
__comp — comparator.

💫 Returns

true if sorted, false otherwise. that's it, that's the answer.

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

template<typename _RAIter, typename _Compare> _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. three little iterators walk into a bar and one of them is the median 💅

🌈 Parameters

__a — first iterator.
__b — second iterator.
__c — third iterator.
__comp — comparator.

Referenced by __qsb_divide().

template<typename _RAIter1, typename _RAIter2, typename _OutputIterator,
    typename _DifferenceTp, typename _Compare> _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, and heads up — they might not reach __end, in contrast to the usual variant. Also there's a static switch on whether to use the conditional-move variant. fancy 😌

🌸 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<typename _RAIter1, typename _RAIter2, typename _OutputIterator,
    typename _DifferenceTp, typename _Compare> _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, and they might not reach __end, in contrast to the usual variant. This one has specially designed code so the compiler can generate conditional moves instead of branches. branchless bestie behaviour fr fr 🧚

💖 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<typename _RAIter1, typename _RAIter2, typename _OutputIterator,
    typename _DifferenceTp, typename _Compare> _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. no conditional-move tricks here, just the plain version doing its thing 🫶

🌸 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<typename _RAIter1, typename _RAIter3, typename _Compare> _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. glow up 💅

💜 Parameters

__begin1 — begin iterator of first sequence.
__end1 — end iterator of first sequence.
__begin2 — begin iterator of second sequence.
__end2 — end iterator of second sequence.
__target — target begin iterator.
__max_length — maximum number of elements to merge.
__comp — comparator.

🌈 Returns

Output end iterator.

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

template<typename _RAIter1, typename _RAIter2, typename _RAIter3, typename
    _Compare> _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. sometimes you just gotta walk it yourself, and that's okay 😭

🌸 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<typename _RAIter, typename _Compare> void
    __gnu_parallel::__parallel_nth_element (_RAIter __begin, _RAIter __nth,
    _RAIter __end, _Compare __comp)

Parallel implementation of std::nth_element(). same energy, more threads 🔥

🎀 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<typename _RAIter, typename _Compare> void
    __gnu_parallel::__parallel_partial_sort (_RAIter __begin, _RAIter
    __middle, _RAIter __end, _Compare __comp)

Parallel implementation of std::partial_sort(). partially sorted, fully slaying 💅

🦋 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<typename _IIter, typename _OutputIterator, typename
    _BinaryOperation> _OutputIterator __gnu_parallel::__parallel_partial_sum
    (_IIter __begin, _IIter __end, _OutputIterator __result,
    _BinaryOperation __bin_op)

Parallel partial sum front-__end. running total but make it multithreaded ✨

💖 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 for the previous entry: __parallel_partial_sum_linear(), _GLIBCXX_CALL, and __gnu_parallel::_Settings::get(). 💖

`__gnu_parallel::__parallel_partial_sum_basecase` 🌸

template<typename _IIter, typename _OutputIterator, typename
    _BinaryOperation> _OutputIterator
    __gnu_parallel::__parallel_partial_sum_basecase (_IIter __begin, _IIter
    __end, _OutputIterator __result, _BinaryOperation __bin_op, typename
    std::iterator_traits< _IIter >::value_type __value)

Okay bestie, this one is the 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. (no cap, it’s required!) 😭

Returns

End iterator of output sequence. 🫶

Referenced by

__parallel_partial_sum_linear() 💜

`__gnu_parallel::__parallel_partial_sum_linear` 🌈

template<typename _IIter, typename _OutputIterator, typename
    _BinaryOperation> _OutputIterator
    __gnu_parallel::__parallel_partial_sum_linear (_IIter __begin, _IIter
    __end, _OutputIterator __result, _BinaryOperation __bin_op, typename
    std::iterator_traits< _IIter >::difference_type __n)

This is the parallel partial sum implementation, two-phase approach, no recursion. It’s giving efficient. 🔥

Parameters

__begin — begin iterator of input sequence.
__end — end iterator of input sequence.
__result — begin iterator of output sequence.
__bin_op — associative binary function.
__n — length of sequence.

Returns

End iterator of output sequence. 💖

References

__equally_split()
__parallel_partial_sum_basecase()
__gnu_parallel::_Settings::get()
std::max()
std::min()
__gnu_parallel::_Settings::partial_sum_dilation

Referenced by

__parallel_partial_sum()

`__gnu_parallel::__parallel_partition` 💅

template<typename _RAIter, typename _Predicate> std::iterator_traits<
    _RAIter >::difference_type __gnu_parallel::__parallel_partition (_RAIter
    __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads)

Parallel implementation of std::partition. Periodt. 🎀

Parameters

__begin — begin iterator of input sequence to split.
__end — end iterator of input sequence to split.
__pred — partition predicate, possibly including some kind of pivot.
__num_threads — maximum number of threads to use for this task.

Returns

Number of elements not fulfilling the predicate. 😭

References

__compare_and_swap()
__fetch_and_add()
_GLIBCXX_CALL
_GLIBCXX_VOLATILE
__gnu_parallel::_Settings::get()
std::max()
__gnu_parallel::_Settings::partition_chunk_share
__gnu_parallel::_Settings::partition_chunk_size

Referenced by

__parallel_nth_element()
__parallel_sort_qs_divide()
__qsb_divide()

`__gnu_parallel::__parallel_random_shuffle` 🦋

template<typename _RAIter, typename _RandomNumberGenerator> void
    __gnu_parallel::__parallel_random_shuffle (_RAIter __begin, _RAIter
    __end, _RandomNumberGenerator __rng = _RandomNumber()) [inline]

Parallel random public call. It’s the public vibe. ✨

Parameters

__begin — begin iterator of sequence.
__end — end iterator of sequence.
__rng — random number generator to use.

References

__parallel_random_shuffle_drs()

`__gnu_parallel::__parallel_random_shuffle_drs` 🌸

template<typename _RAIter, typename _RandomNumberGenerator> 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. The main character of shuffling. 👑

Parameters

__begin — begin iterator of sequence.
__end — end iterator of sequence.
__n — length of sequence.
__num_threads — number of threads to use.
__rng — random number generator to use.

References

__gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::__bins_end
__parallel_random_shuffle_drs_pu()
__rd_log2()
__round_up_to_pow2()
__sequential_random_shuffle()
_GLIBCXX_CALL
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_bin_proc
__gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_bins_begin
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_dist
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bins
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bits
__gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_num_threads
__gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_sd
__gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_seed
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_starts
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_temporaries
__gnu_parallel::_Settings::get()
__gnu_parallel::_Settings::L2_cache_size
std::max()
std::numeric_limits< _Tp >::max()
std::min()
__gnu_parallel::_Settings::TLB_size

Referenced by

__parallel_random_shuffle()

`__gnu_parallel::__parallel_random_shuffle_drs_pu` 🧚

template<typename _RAIter, typename _RandomNumberGenerator> void
    __gnu_parallel::__parallel_random_shuffle_drs_pu (_DRSSorterPU< _RAIter,
    _RandomNumberGenerator > * __pus)

Random shuffle code executed by each thread. It’s giving teamwork. 🫶

Parameters

__pus — array of thread-local data records.

References

__random_number_pow2()
__sequential_random_shuffle()
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_bin_proc
__gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_bins_begin
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_dist
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bins
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bits
__gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_num_threads
__gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_sd
__gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_seed
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_source
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_starts
__gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_temporaries
std::partial_sum()

Referenced by

__parallel_random_shuffle_drs()

`__gnu_parallel::__parallel_sort` — `balanced_quicksort_tag` 🎀

template<bool __stable, typename _RAIter, typename _Compare> void
    __gnu_parallel::__parallel_sort (_RAIter __begin, _RAIter __end,
    _Compare __comp, balanced_quicksort_tag __parallelism) [inline]

Choose balanced quicksort for parallel sorting. Slay. 💅

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()
_GLIBCXX_CALL

`__gnu_parallel::__parallel_sort` — `default_parallel_tag` ✨

template<bool __stable, typename _RAIter, typename _Compare> 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. It’s giving exact. 💖

Parameters

__begin — begin iterator of input sequence.
__end — end iterator of input sequence.
__comp — comparator.

Template Parameters

__stable — sort stable.

References

__gnu_parallel::parallel_tag::__get_num_threads()
_GLIBCXX_CALL

`__gnu_parallel::__parallel_sort` — `multiway_mergesort_exact_tag` 🌈

template<bool __stable, typename _RAIter, typename _Compare> 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. Same vibe, different tag. 🔥

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
parallel_sort_mwms()

`__gnu_parallel::__parallel_sort` — `multiway_mergesort_sampling_tag` 🦋

template<bool __stable, typename _RAIter, typename _Compare> 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. Sampling? We love a good sample. 🍓

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
parallel_sort_mwms()

`__gnu_parallel::__parallel_sort` — `multiway_mergesort_tag` 👑

template<bool __stable, typename _RAIter, typename _Compare> 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. Run-time decisions? Main character energy. 💅

Parameters

__begin — begin iterator of input sequence.
__end — end iterator of input sequence.
__comp — comparator.

Template Parameters

__stable — sort stable.

References

__gnu_parallel::parallel_tag::__get_num_threads()
_GLIBCXX_CALL
__gnu_parallel::_Settings::get()
parallel_sort_mwms()

`__gnu_parallel::__parallel_sort` — `parallel_tag` 🌟

template<bool __stable, typename _RAIter, typename _Compare> void
    __gnu_parallel::__parallel_sort (_RAIter __begin, _RAIter __end,
    _Compare __comp, parallel_tag __parallelism) [inline]

Choose a parallel sorting algorithm. The generic baddie. ✨

Parameters

__begin — begin iterator of input sequence.
__end — end iterator of input sequence.
__comp — comparator.

Template Parameters

__stable — sort stable.

References

__gnu_parallel::parallel_tag::__get_num_threads()
__parallel_sort_qs()
__parallel_sort_qsb()
_GLIBCXX_CALL
__gnu_parallel::_Settings::get()
parallel_sort_mwms()

`__gnu_parallel::__parallel_sort` — `quicksort_tag` 💖

template<bool __stable, typename _RAIter, typename _Compare> void
    __gnu_parallel::__parallel_sort (_RAIter __begin, _RAIter __end,
    _Compare __comp, quicksort_tag __parallelism) [inline]

Choose quicksort for parallel sorting. Quick like a bunny. 🦋

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()
_GLIBCXX_CALL

`__gnu_parallel::__parallel_sort_qs` 🔥

template<typename _RAIter, typename _Compare> void
    __gnu_parallel::__parallel_sort_qs (_RAIter __begin, _RAIter __end,
    _Compare __comp, _ThreadIndex __num_threads)

Unbalanced quicksort main call. It’s unbalanced but that’s the vibe. 💅

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()
_GLIBCXX_CALL

Referenced by

__parallel_sort()
__parallel_sort()

`__gnu_parallel::__parallel_sort_qs_conquer` 🌸

template<typename _RAIter, typename _Compare> void
    __gnu_parallel::__parallel_sort_qs_conquer (_RAIter __begin, _RAIter
    __end, _Compare __comp, _ThreadIndex __num_threads)

Unbalanced quicksort conquer step.

okay so the parameters for that last one are:

__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(). 💖

`__gnu_parallel::__parallel_sort_qs_divide` — unbalanced quicksort divide step 💅

template<typename _RAIter, typename _Compare>
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)

Bestie, this is the unbalanced quicksort divide step. It's giving divide and conquer, but make it unbalanced. 😌

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(). 💖

`__gnu_parallel::__parallel_sort_qsb` — top-level quicksort routine 👑

template<typename _RAIter, typename _Compare>
void
__gnu_parallel::__parallel_sort_qsb (_RAIter __begin, _RAIter __end,
    _Compare __comp, _ThreadIndex __num_threads)

This is the top-level quicksort routine. Main character energy fr fr. 💅

Parameters:

__begin — Begin iterator of sequence. 🌈
__end — End iterator of sequence. 🌈
__comp — Comparator. 💅
__num_threads — Number of threads that are allowed to work on this part. 👑

References: __qsb_conquer(), __rd_log2(), _GLIBCXX_CALL, and std::make_pair(). ✨

Referenced by: __parallel_sort(), and __parallel_sort(). 💖

`__gnu_parallel::__parallel_unique_copy` — parallel `std::unique_copy()` without explicit equality predicate 🦋

template<typename _IIter, class _OutputIterator>
_OutputIterator
__gnu_parallel::__parallel_unique_copy (_IIter __first, _IIter __last,
    _OutputIterator __result) [inline]

It's std::unique_copy() but parallel, and no explicit equality predicate. Iconic. ✨

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(). 🔥

`__gnu_parallel::__parallel_unique_copy` — parallel `std::unique_copy()` with explicit equality predicate 💅

template<typename _IIter, class _OutputIterator, class _BinaryPredicate>
_OutputIterator
__gnu_parallel::__parallel_unique_copy (_IIter __first, _IIter __last,
    _OutputIterator __result, _BinaryPredicate __binary_pred)

Parallel std::unique_copy(), w/__o explicit equality predicate. (Yes, the original says w/__o — we keep it exactly, no cap.) 😭

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(). 💖

`__gnu_parallel::__qsb_conquer` — quicksort conquer step 👑

template<typename _RAIter, typename _Compare>
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. It's giving conquer, not divide. 😌

Parameters:

__tls — Array of thread-local storages. 🧚
__begin — Begin iterator of subsequence. 🌸
__end — End iterator of subsequence. 🌸
__comp — Comparator. 💅
__iam — Number of the thread processing this function. 👑
__num_threads — Number of threads that are allowed to work on this part. 👑

References: __qsb_conquer(), __qsb_divide(), __qsb_local_sort_with_helping(), __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_elements_leftover, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_initial, std::max(), and std::min(). ✨

Referenced by: __parallel_sort_qsb(), and __qsb_conquer(). 💖

`__gnu_parallel::__qsb_divide` — balanced quicksort divide step ⚖️

template<typename _RAIter, typename _Compare>
std::iterator_traits< _RAIter >::difference_type
__gnu_parallel::__qsb_divide (_RAIter __begin, _RAIter __end,
    _Compare __comp, _ThreadIndex __num_threads)

Balanced quicksort divide step. Balance is key, bestie. 💅

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 🚨

You better have at least one element in there, fr fr.

References: __median_of_three_iterators(), and __parallel_partition(). ✨

Referenced by: __qsb_conquer(). 💖

`__gnu_parallel::__qsb_local_sort_with_helping` — quicksort step doing load-balanced local sort 🧚

template<typename _RAIter, typename _Compare>
void
__gnu_parallel::__qsb_local_sort_with_helping (_QSBThreadLocal< _RAIter > ** __tls,
    _Compare & __comp, _ThreadIndex __iam, bool __wait)

Quicksort step doing load-balanced local sort. It's helping, it's local, it's balanced. We love. ✨

Parameters:

__tls — Array of thread-local storages. 🧚
__comp — Comparator. 💅
__iam — Number of the thread processing this function. 👑

References: __yield(), _GLIBCXX_PARALLEL_ASSERTIONS, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_elements_leftover, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_initial, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_leftover_parts, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_num_threads, __gnu_parallel::_Settings::get(), std::make_pair(), and __gnu_parallel::_Settings::sort_qsb_base_case_maximal_n. ✨

Referenced by: __qsb_conquer(). 💖

`__gnu_parallel::__random_number_pow2` — generate a random number in `[0,2^__logp)` 🎲

template<typename _RandomNumberGenerator>
int
__gnu_parallel::__random_number_pow2 (int __logp, _RandomNumberGenerator & __rng) [inline]

Generate a random number in [0,2^__logp). Random but make it powers of two. 💅

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(). 💖

`__gnu_parallel::__rd_log2` — rounded-down logarithm of `__n` for base 2 📐

template<typename _Size>
_Size
__gnu_parallel::__rd_log2 (_Size __n) [inline]

Calculates the rounded-down logarithm of __n for base 2. Math queen. 👑

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(). 💖

`__gnu_parallel::__round_up_to_pow2` — round up to the next greater power of 2 🔼

template<typename _Tp>
_Tp
__gnu_parallel::__round_up_to_pow2 (_Tp __x)

Round up to the next greater power of 2. It's giving upward mobility. ✨

Parameters:

__x — _Integer to round up. 🔢

References: __rd_log2(). ✨

Referenced by: __parallel_random_shuffle_drs(), __sequential_random_shuffle(), and multiseq_selection(). 💖

`__gnu_parallel::__search_template` — parallel `std::search` 🔍

template<typename __RAIter1, typename __RAIter2, typename _Pred>
__RAIter1
__gnu_parallel::__search_template (__RAIter1 __begin1, __RAIter1 __end1,
    __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred)

Parallel std::search. It's searching, but make it parallel. 🔍✨

Parameters:

__begin1 — Begin iterator of first sequence. 🌸
__end1 — End iterator of first sequence. 🌸
__begin2 — Begin iterator of second sequence. 🌺
__end2 — End iterator of second sequence. 🌺
__pred — Find predicate. 💅

Returns: Place of finding in first sequences. 🫶

References: __calc_borders(), __equally_split(), _GLIBCXX_CALL, std::max(), and std::min(). ✨

`__gnu_parallel::__sequential_multiway_merge` — sequential multi-way merging switch 🔀

template<bool __stable, bool __sentinels, typename _RAIterIterator, typename _RAIter3, typename _DifferenceTp, typename _Compare>
_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. It's giving decision energy. 💅

Parameters:

__seqs_begin — Begin iterator of iterator pair input sequence. 🌈
__seqs_end — End iterator of iterator pair input sequence. 🌈
__target — Begin iterator of output sequence. 🎯
__comp — Comparator. 💅
__length — Maximum length to merge, possibly larger than the number of elements available. 📏
__sentinel — The sequences have __a __sentinel element. 🛡️

Returns: End iterator of output sequence. 🫶

References: __is_sorted(), __merge_advance(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_LENGTH, and std::min(). ✨

Referenced by: multiway_merge(), multiway_merge_sentinels(), and parallel_multiway_merge(). 💖

`__gnu_parallel::__sequential_random_shuffle` — sequential cache-efficient random shuffle 🎲

template<typename _RAIter, typename _RandomNumberGenerator>
void
__gnu_parallel::__sequential_random_shuffle (_RAIter __begin, _RAIter __end,
    _RandomNumberGenerator & __rng)

Sequential cache-efficient random shuffle. Cache-friendly and random? We love a multi-talented icon. ✨

Parameters:

__begin — Begin iterator of sequence. 🌸
__end — End iterator of sequence. 🌸
__rng — Random number generator to use. 🎲

References: __random_number_pow2(), __rd_log2(), __round_up_to_pow2(), __sequential_random_shuffle(), __gnu_parallel::_Settings::get(), __gnu_parallel::_Settings::L2_cache_size, std::max(), std::min(), std::partial_sum(), and __gnu_parallel::_Settings::TLB_size. ✨

Referenced by: __parallel_random_shuffle_drs(), __parallel_random_shuffle_drs_pu(), and __sequential_random_shuffle(). 💖

`__gnu_parallel::__shrink` — combines two ranges into one and halves the number of ranges 🗜️

template<typename _IIter>
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. Shrink it down, bestie. 💅

Parameters:

__os_starts — Start positions worked on (oversampled). 📍
__count_to_two — Counts up to 2. 🔢
__range_length — Current length of a chunk. 📏

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

Referenced by: __shrink_and_double(). 💖

`__gnu_parallel::__shrink_and_double` — shrinks and doubles the ranges 🔄

template<typename _IIter>
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. Shrink, then double. It's giving reversible jacket. 😭

Parameters:

__os_starts — Start positions worked on (oversampled). 📍
__count_to_two — Counts up to 2. 🔢
__range_length — Current length of a chunk. 📏
__make_twice — Whether the __os_starts is allowed to be grown or not. 🌱

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

Referenced by: list_partition(). 💖

`__gnu_parallel::__yield` — yield control to another thread 💅

void
__gnu_parallel::__yield () [inline]

Yield control to another thread, without waiting for the end of the time slice. It's giving generous. 🫶

Referenced by: __for_each_template_random_access_workstealing(), and __qsb_local_sort_with_helping(). 💖

`__gnu_parallel::list_partition` — splits a sequence into parts of almost equal size ✂️

template<typename _IIter, typename _FunctorType>
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. One pass? Efficient queen. 👑

### 💫 Parameters 💫

__begin — begin iterator of the input sequence, the og starting point bestie 🫶
__end — end iterator of the input sequence, where the vibes stop
__starts — start iterators for the resulting parts, dimension __num_parts+1. and for convenience?? __starts [__num_parts] contains the end iterator of the sequence. it's giving thoughtful ✨
__lengths — length of the resulting parts
__num_parts — number of parts to split the sequence into, the way it just divides everything up 💅
__f — functor to be applied to each element by traversing __it
__oversampling — oversampling factor. if 0, then the partitions will differ in at most $t{thrm{end} - thrm{begin}}$ elements. otherwise, the ratio between the longest and the shortest part is bounded by $1/(thrm{oversampling}

### 🔙 Returns 🔙

Length of the whole sequence. that's the whole return, no notes 💖

### 🔗 References 🔗

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

### 🦋 max 🦋

template<typename _Tp> const _Tp & __gnu_parallel::max (const _Tp & __a, const _Tp & __b) [inline]

Equivalent to std::max. literally that's it, no cap 🔥

Referenced by __for_each_template_random_access_workstealing().

### 🦋 min 🦋

template<typename _Tp> const _Tp & __gnu_parallel::min (const _Tp & __a, const _Tp & __b) [inline]

Equivalent to std::min. twin of the one above, obsessed 💜

Referenced by __for_each_template_random_access_ed(), __for_each_template_random_access_omp_loop(), and __for_each_template_random_access_workstealing().

### 🌈 multiseq_partition 🌈

template<typename _RanSeqs, typename _RankType, typename _RankIterator, typename _Compare>
void __gnu_parallel::multiseq_partition (_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankIterator __begin_offsets, _Compare __comp = std::less< typename std::iterator_traits<typename std::iterator_traits<_RanSeqs>::value_type:: first_type>::value_type>())

Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each sequence. The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones on the __left side will be chosen from sequences with smaller number. okay so it's got opinions and we respect them 💅

#### Parameters

__begin_seqs — begin of the sequence of iterator pairs
__end_seqs — end of the sequence of iterator pairs
__rank — the global rank to partition at
__begin_offsets — a random-access __sequence __begin where the __result will be stored in. Each element of the sequence is an iterator that points to the first element on the greater part of the respective __sequence.
__comp — the ordering functor, defaults to std::less<_Tp>

#### References

__rd_log2(), _GLIBCXX_CALL, std::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::make_pair(), std::max(), std::min(), std::priority_queue< _Tp, _Sequence, _Compare >::pop(), std::priority_queue< _Tp, _Sequence, _Compare >::push(), and std::priority_queue< _Tp, _Sequence, _Compare >::top().

Referenced by multiway_merge_exact_splitting().

### 🌸 multiseq_selection 🌸

template<typename _Tp, typename _RanSeqs, typename _RankType, typename _Compare>
_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. same rule as above, don't test it 🫶

#### 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. it's giving the chosen one ✨
__comp — the ordering functor, defaults to std::less

#### References

__rd_log2(), __round_up_to_pow2(), _GLIBCXX_CALL, std::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::make_pair(), std::max(), std::min(), std::priority_queue< _Tp, _Sequence, _Compare >::pop(), std::priority_queue< _Tp, _Sequence, _Compare >::push(), and std::priority_queue< _Tp, _Sequence, _Compare >::top().

### 👑 multiway_merge 👑

template<typename _RAIterPairIterator, typename _RAIterOut, typename _DifferenceTp, typename _Compare>
_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. so it's pairs of (start, end) and honestly? iconic structure 💅

Ties are broken arbitrarily. See stable_multiway_merge for a variant that breaks ties by sequence number but is slower. speed or fairness, bestie, you literally cannot have both 😭

The first entries of the pairs (i.e. the begin iterators) will be moved forward. yes it mutates them, don't be surprised

The output sequence has to provide enough space for all elements that are written to it. do not skip this part, it will not be cute 💀

This function will merge the input sequences:

not stable
parallel, depending on the input size and Settings
using sampling for splitting
not using sentinels

Example:

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

int __out[33];
std::vector<std::pair<int*> > seqs;
for (int __i = 0; __i < 10; ++__i)
  { seqs.push(std::make_pair<int*>(sequences[__i],
                                   sequences[__i] + 10)) }

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

#### See also

stable_multiway_merge

#### Precondition

All input sequences must be sorted.

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

#### Postcondition

[__target, return __value) contains merged __elements from the input sequences.

return __value - __target = min(__length, number of elements in all sequences).

#### 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.

### 🚀 multiway_merge_3_variant 🚀

template<template< typename _RAI, typename _Cp > 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++). ngl that is unhinged in the best way 🔥

This works well for merging up to 4 sequences.

Note that making the merging stable does not come at a performance hit. free stability?? we love to see it ✨

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.

### 🚀 multiway_merge_4_variant 🚀

template<template< typename _RAI, typename _Cp > 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++). four-way edition, same chaotic genius energy 💅

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.

### ✂️ multiway_merge_exact_splitting ✂️

template<bool __stable, typename _RAIterIterator, typename _Compare, typename _DifferenceType>
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. for real for real 🫶

#### References

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

Referenced by __parallel_merge_advance().

### 🌳 multiway_merge_loser_tree 🌳

template<typename _LT, typename _RAIterIterator, typename _RAIter3, typename _DifferenceTp, typename _Compare>
_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. it's called a loser tree and it is honestly the main character here 👑

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. no cap.

okay bestie, next function coming at you:

template<typename _UnguardedLoserTree, typename _RAIterIterator, typename _RAIter3, typename _DifferenceTp, typename _Compare> _RAIter3 __gnu_parallel::multiway_merge_loser_tree_sentinel (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type & __sentinel, _DifferenceTp __length, _Compare __comp)

Multi-way merging procedure for a high branching factor, requiring sentinels to exist. 🛡️

Template Parameters

_UnguardedLoserTree — Loser Tree variant to use for the unguarded merging.

Parameters

__seqs_begin — Begin iterator of iterator pair input sequence.
__seqs_end — End iterator of iterator pair input sequence.
__target — Begin iterator of output sequence.
__comp — Comparator.
__length — Maximum length to merge, less equal than the total number of elements available.

Returns

End iterator of output sequence.

References

__is_sorted(), _GLIBCXX_CALL, and multiway_merge_loser_tree_unguarded().

template<typename _LT, typename _RAIterIterator, typename _RAIter3, typename _DifferenceTp, typename _Compare> _RAIter3 __gnu_parallel::multiway_merge_loser_tree_unguarded (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type & __sentinel, _DifferenceTp __length, _Compare __comp)

Multi-way merging procedure for a high branching factor, unguarded case. Merging is done using the LoserTree class _LT. 🌳

Stability is selected by the used LoserTrees. 💅

Precondition

No input will run out of elements during the merge. ⚠️

Parameters

__seqs_begin — Begin iterator of iterator pair input sequence.
__seqs_end — End iterator of iterator pair input sequence.
__target — Begin iterator of output sequence.
__comp — Comparator.
__length — Maximum length to merge, less equal than the total number of elements available.

Returns

End iterator of output sequence.

References

_GLIBCXX_CALL.

Referenced by

multiway_merge_loser_tree_sentinel().

template<bool __stable, typename _RAIterIterator, typename _Compare, typename _DifferenceType> 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<typename _RAIterPairIterator, typename _RAIterOut, typename _DifferenceTp, typename _Compare> _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<std::pair<int*> > seqs;
for (int __i = 0; __i < 10; ++__i)
  { seqs.push(std::make_pair<int*>(sequences[__i],
                                   sequences[__i] + 10)) }

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

Precondition

All input sequences must be sorted. 📈

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

For each __i, __seqs_begin[__i].second must be the end marker of the sequence, but also reference the one more __sentinel element. 🛡️

Postcondition

[__target, return __value) contains merged __elements from the input sequences. 🎯

return __value - __target = min(__length, number of elements in all sequences). 🧮

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<bool __stable, bool __sentinels, typename _RAIterIterator, typename _RAIter3, typename _DifferenceTp, typename _Splitter, typename _Compare> _RAIter3 __gnu_parallel::parallel_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _Splitter __splitter, _DifferenceTp __length, _Compare __comp, _ThreadIndex __num_threads)

Parallel multi-way merge routine. The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings. ⚙️

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

Template Parameters

_Splitter — functor to split input (either __exact or sampling based)
__stable — Stable merging incurs a performance penalty.
__sentinel — Ignored.

Parameters

__seqs_begin — Begin iterator of iterator pair input sequence.
__seqs_end — End iterator of iterator pair input sequence.
__target — Begin iterator of output sequence.
__comp — Comparator.
__length — Maximum length to merge, possibly larger than the number of elements available.

Returns

End iterator of output sequence.

References

__is_sorted(), __sequential_multiway_merge(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), std::make_pair(), __gnu_parallel::_Settings::merge_oversampling, and std::min().

Referenced by

__parallel_merge_advance().

template<bool __stable, bool __exact, typename _RAIter, typename _Compare> void __gnu_parallel::parallel_sort_mwms (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)

PMWMS main call. 🏁

Parameters

__begin — Begin iterator of sequence.
__end — End iterator of sequence.
__comp — Comparator.
__num_threads — Number of threads to use.

References

_GLIBCXX_CALL, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_num_threads, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_offsets, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_pieces, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_samples, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_temporary, __gnu_parallel::_Settings::get(), parallel_sort_mwms_pu(), and __gnu_parallel::_Settings::sort_mwms_oversampling.

Referenced by

__parallel_sort(), __parallel_sort(), __parallel_sort(), and __parallel_sort().

template<bool __stable, bool __exact, typename _RAIter, typename _Compare> void __gnu_parallel::parallel_sort_mwms_pu (_PMWMSSortingData< _RAIter > * __sd, _Compare & __comp)

PMWMS code executed by each thread. 🧵

Parameters

__sd — Pointer to algorithm data.
__comp — Comparator.

References

__gnu_parallel::_PMWMSSortingData< _RAIter >::_M_num_threads, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_pieces, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_temporary, __gnu_parallel::_Settings::get(), std::make_pair(), __gnu_parallel::_Settings::sort_mwms_oversampling, and std::uninitialized_copy().

Referenced by

parallel_sort_mwms().

Variable Documentation 💖

`const int __gnu_parallel::_CASable_bits [static]`

Number of bits of _CASable. 🔢

Referenced by __decode2(), and __encode2().

`const _CASable __gnu_parallel::_CASable_mask [static]`

_CASable with the right half of bits set to 1. 🎭

Referenced by __decode2().

Author ✍️

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

💖 and that's the whole __gnu_parallel(3) page, bestie! source/version: libstdc++ · __gnu_parallel(3) · date: (the footer didn't show one, but it's giving timeless ✨). stay iconic, stay parallel. 👑🦋

📦 where this page comes from

arch rolling: gcc 16.2.1+r23+gd564253eb6c8-1 · GPL-3.0-or-later WITH GCC-exception-3.1 AND GFDL-1.3-or-later
centos-stream 10: gcc-toolset-15-libstdc++-docs 15.2.1-8.1.el10 · GPL-3.0-or-later AND LGPL-3.0-or-later AND (GPL-3.0-or-later WITH GCC-exception-3.1) AND (GPL-3.0-or-later WITH Texinfo-exception) AND (LGPL-2.1-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GNU-compiler-exception) AND BSL-1.0 AND GFDL-1.3-or-later AND Linux-man-pages-copyleft-2-para AND SunPro AND BSD-1-Clause AND BSD-2-Clause AND BSD-2-Clause-Views AND BSD-3-Clause AND BSD-4-Clause AND BSD-Source-Code AND Zlib AND MIT AND Apache-2.0 AND (Apache-2.0 WITH LLVM-Exception) AND ZPL-2.1 AND ISC AND LicenseRef-Fedora-Public-Domain AND HP-1986 AND curl AND Martin-Birgmeier AND HPND-Markus-Kuhn AND dtoa AND SMLNJ AND AMD-newlib AND OAR AND HPND-merchantability-variant AND HPND-Intel
centos-stream 10: gcc-toolset-16-libstdc++-docs 16.2.1-1.3.el10 · GPL-3.0-or-later AND LGPL-3.0-or-later AND (GPL-3.0-or-later WITH GCC-exception-3.1) AND (GPL-3.0-or-later WITH Texinfo-exception) AND (LGPL-2.1-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GNU-compiler-exception) AND BSL-1.0 AND GFDL-1.3-or-later AND Linux-man-pages-copyleft-2-para AND SunPro AND BSD-1-Clause AND BSD-2-Clause AND BSD-2-Clause-Views AND BSD-3-Clause AND BSD-4-Clause AND BSD-Source-Code AND Zlib AND MIT AND Apache-2.0 AND (Apache-2.0 WITH LLVM-Exception) AND ZPL-2.1 AND ISC AND LicenseRef-Fedora-Public-Domain AND HP-1986 AND curl AND Martin-Birgmeier AND HPND-Markus-Kuhn AND dtoa AND SMLNJ AND AMD-newlib AND OAR AND HPND-merchantability-variant AND HPND-Intel
centos-stream 10: libstdc++-docs 14.4.1-4.el10 · GPL-3.0-or-later AND LGPL-3.0-or-later AND (GPL-3.0-or-later WITH GCC-exception-3.1) AND (GPL-3.0-or-later WITH Texinfo-exception) AND (LGPL-2.1-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GNU-compiler-exception) AND BSL-1.0 AND GFDL-1.3-or-later AND Linux-man-pages-copyleft-2-para AND SunPro AND BSD-1-Clause AND BSD-2-Clause AND BSD-2-Clause-Views AND BSD-3-Clause AND BSD-4-Clause AND BSD-Source-Code AND Zlib AND MIT AND Apache-2.0 AND (Apache-2.0 WITH LLVM-Exception) AND ZPL-2.1 AND ISC AND LicenseRef-Fedora-Public-Domain AND HP-1986 AND curl AND Martin-Birgmeier AND HPND-Markus-Kuhn AND dtoa AND SMLNJ AND AMD-newlib AND OAR AND HPND-merchantability-variant AND HPND-Intel
fedora 43: libstdc++-docs 15.2.1-2.fc43 · GPL-3.0-or-later AND LGPL-3.0-or-later AND (GPL-3.0-or-later WITH GCC-exception-3.1) AND (GPL-3.0-or-later WITH Texinfo-exception) AND (LGPL-2.1-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GNU-compiler-exception) AND BSL-1.0 AND GFDL-1.3-or-later AND Linux-man-pages-copyleft-2-para AND SunPro AND BSD-1-Clause AND BSD-2-Clause AND BSD-2-Clause-Views AND BSD-3-Clause AND BSD-4-Clause AND BSD-Source-Code AND Zlib AND MIT AND Apache-2.0 AND (Apache-2.0 WITH LLVM-Exception) AND ZPL-2.1 AND ISC AND LicenseRef-Fedora-Public-Domain AND HP-1986 AND curl AND Martin-Birgmeier AND HPND-Markus-Kuhn AND dtoa AND SMLNJ AND AMD-newlib AND OAR AND HPND-merchantability-variant AND HPND-Intel
fedora 43: libstdc++-docs 15.3.1-1.fc43 · GPL-3.0-or-later AND LGPL-3.0-or-later AND (GPL-3.0-or-later WITH GCC-exception-3.1) AND (GPL-3.0-or-later WITH Texinfo-exception) AND (LGPL-2.1-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GNU-compiler-exception) AND BSL-1.0 AND GFDL-1.3-or-later AND Linux-man-pages-copyleft-2-para AND SunPro AND BSD-1-Clause AND BSD-2-Clause AND BSD-2-Clause-Views AND BSD-3-Clause AND BSD-4-Clause AND BSD-Source-Code AND Zlib AND MIT AND Apache-2.0 AND (Apache-2.0 WITH LLVM-Exception) AND ZPL-2.1 AND ISC AND LicenseRef-Fedora-Public-Domain AND HP-1986 AND curl AND Martin-Birgmeier AND HPND-Markus-Kuhn AND dtoa AND SMLNJ AND AMD-newlib AND OAR AND HPND-merchantability-variant AND HPND-Intel
fedora 44: libstdc++-docs 16.0.1-0.10.fc44 · GPL-3.0-or-later AND LGPL-3.0-or-later AND (GPL-3.0-or-later WITH GCC-exception-3.1) AND (GPL-3.0-or-later WITH Texinfo-exception) AND (LGPL-2.1-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GNU-compiler-exception) AND BSL-1.0 AND GFDL-1.3-or-later AND Linux-man-pages-copyleft-2-para AND SunPro AND BSD-1-Clause AND BSD-2-Clause AND BSD-2-Clause-Views AND BSD-3-Clause AND BSD-4-Clause AND BSD-Source-Code AND Zlib AND MIT AND Apache-2.0 AND (Apache-2.0 WITH LLVM-Exception) AND ZPL-2.1 AND ISC AND LicenseRef-Fedora-Public-Domain AND HP-1986 AND curl AND Martin-Birgmeier AND HPND-Markus-Kuhn AND dtoa AND SMLNJ AND AMD-newlib AND OAR AND HPND-merchantability-variant AND HPND-Intel
fedora 44: libstdc++-docs 16.2.1-2.fc44
fedora 44: libstdc++-docs 16.2.1-3.fc44 · GPL-3.0-or-later AND LGPL-3.0-or-later AND (GPL-3.0-or-later WITH GCC-exception-3.1) AND (GPL-3.0-or-later WITH Texinfo-exception) AND (LGPL-2.1-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GCC-exception-2.0) AND (GPL-2.0-or-later WITH GNU-compiler-exception) AND BSL-1.0 AND GFDL-1.3-or-later AND Linux-man-pages-copyleft-2-para AND SunPro AND BSD-1-Clause AND BSD-2-Clause AND BSD-2-Clause-Views AND BSD-3-Clause AND BSD-4-Clause AND BSD-Source-Code AND Zlib AND MIT AND Apache-2.0 AND (Apache-2.0 WITH LLVM-Exception) AND ZPL-2.1 AND ISC AND LicenseRef-Fedora-Public-Domain AND HP-1986 AND curl AND Martin-Birgmeier AND HPND-Markus-Kuhn AND dtoa AND SMLNJ AND AMD-newlib AND OAR AND HPND-merchantability-variant AND HPND-Intel
💖 girlified by deepseek-ai/DeepSeek-V4.1-Flash on 2026-10-14: a language model's rewrite of the original, under its terms

__gnu_parallel(3)

💅 __gnu_parallel — GNU parallel code for public use 💅

💖 NAME 💖

✨ SYNOPSIS ✨

🎀 Classes 🎀

🎀 Typedefs 🎀

🎀 Enumerations 🎀

✨ Functions ✨

✨ Variables ✨

💅 Detailed Description 💅

🎀 Typedef Documentation 🎀

🌈 Enumeration Type Documentation 🌈

🔥 Function Documentation 🔥

🌸 __determine_samples

🎀 __encode2

🦋 __equally_split

🌸 __equally_split_point

✨ __fetch_and_add

💜 __find_template (the dispatcher)

🌈 __find_template (constant block size variant)

⭐ __find_template (equal splitting variant)

🔥 __find_template (growing blocks variant)

💖 __for_each_template_random_access

🎀 __for_each_template_random_access_ed

🧚 __for_each_template_random_access_omp_loop

✨ Parameters ✨

💖 Returns

🌸 Parameters

🦋 Returns

💜 Parameters

⭐ Returns

🍓 Parameters

💫 Returns

🌈 Parameters

🌸 Parameters

👑 Returns

💖 Parameters

✨ Returns

🌸 Parameters

🦋 Returns

💜 Parameters

🌈 Returns

🌸 Parameters

⭐ Returns

🎀 Parameters

🦋 Parameters

💖 Parameters

👑 Returns

__gnu_parallel::__parallel_partial_sum_basecase 🌸

__gnu_parallel::__parallel_partial_sum_linear 🌈

__gnu_parallel::__parallel_partition 💅

__gnu_parallel::__parallel_random_shuffle 🦋

__gnu_parallel::__parallel_random_shuffle_drs 🌸

__gnu_parallel::__parallel_random_shuffle_drs_pu 🧚

__gnu_parallel::__parallel_sort — balanced_quicksort_tag 🎀

__gnu_parallel::__parallel_sort — default_parallel_tag ✨

__gnu_parallel::__parallel_sort — multiway_mergesort_exact_tag 🌈

__gnu_parallel::__parallel_sort — multiway_mergesort_sampling_tag 🦋

__gnu_parallel::__parallel_sort — multiway_mergesort_tag 👑

__gnu_parallel::__parallel_sort — parallel_tag 🌟

__gnu_parallel::__parallel_sort — quicksort_tag 💖

__gnu_parallel::__parallel_sort_qs 🔥

__gnu_parallel::__parallel_sort_qs_conquer 🌸

__gnu_parallel::__parallel_sort_qs_divide — unbalanced quicksort divide step 💅

__gnu_parallel::__parallel_sort_qsb — top-level quicksort routine 👑

__gnu_parallel::__parallel_unique_copy — parallel std::unique_copy() without explicit equality predicate 🦋

__gnu_parallel::__parallel_unique_copy — parallel std::unique_copy() with explicit equality predicate 💅

__gnu_parallel::__qsb_conquer — quicksort conquer step 👑

__gnu_parallel::__qsb_divide — balanced quicksort divide step ⚖️

__gnu_parallel::__qsb_local_sort_with_helping — quicksort step doing load-balanced local sort 🧚

__gnu_parallel::__random_number_pow2 — generate a random number in [0,2^__logp) 🎲

__gnu_parallel::__rd_log2 — rounded-down logarithm of __n for base 2 📐

__gnu_parallel::__round_up_to_pow2 — round up to the next greater power of 2 🔼

__gnu_parallel::__search_template — parallel std::search 🔍

__gnu_parallel::__sequential_multiway_merge — sequential multi-way merging switch 🔀

__gnu_parallel::__sequential_random_shuffle — sequential cache-efficient random shuffle 🎲

__gnu_parallel::__shrink — combines two ranges into one and halves the number of ranges 🗜️

__gnu_parallel::__shrink_and_double — shrinks and doubles the ranges 🔄

__gnu_parallel::__yield — yield control to another thread 💅

__gnu_parallel::list_partition — splits a sequence into parts of almost equal size ✂️

💅 `__gnu_parallel` — GNU parallel code for public use 💅

🌸 `__determine_samples`

🎀 `__encode2`

🦋 `__equally_split`

🌸 `__equally_split_point`

✨ `__fetch_and_add`

💜 `__find_template` (the dispatcher)

🌈 `__find_template` (constant block size variant)

⭐ `__find_template` (equal splitting variant)

🔥 `__find_template` (growing blocks variant)

💖 `__for_each_template_random_access`

🎀 `__for_each_template_random_access_ed`

🧚 `__for_each_template_random_access_omp_loop`

`__gnu_parallel::__parallel_partial_sum_basecase` 🌸

`__gnu_parallel::__parallel_partial_sum_linear` 🌈

`__gnu_parallel::__parallel_partition` 💅

`__gnu_parallel::__parallel_random_shuffle` 🦋

`__gnu_parallel::__parallel_random_shuffle_drs` 🌸

`__gnu_parallel::__parallel_random_shuffle_drs_pu` 🧚

`__gnu_parallel::__parallel_sort` — `balanced_quicksort_tag` 🎀

`__gnu_parallel::__parallel_sort` — `default_parallel_tag` ✨

`__gnu_parallel::__parallel_sort` — `multiway_mergesort_exact_tag` 🌈

`__gnu_parallel::__parallel_sort` — `multiway_mergesort_sampling_tag` 🦋

`__gnu_parallel::__parallel_sort` — `multiway_mergesort_tag` 👑

`__gnu_parallel::__parallel_sort` — `parallel_tag` 🌟

`__gnu_parallel::__parallel_sort` — `quicksort_tag` 💖

`__gnu_parallel::__parallel_sort_qs` 🔥

`__gnu_parallel::__parallel_sort_qs_conquer` 🌸

`__gnu_parallel::__parallel_sort_qs_divide` — unbalanced quicksort divide step 💅

`__gnu_parallel::__parallel_sort_qsb` — top-level quicksort routine 👑

`__gnu_parallel::__parallel_unique_copy` — parallel `std::unique_copy()` without explicit equality predicate 🦋

`__gnu_parallel::__parallel_unique_copy` — parallel `std::unique_copy()` with explicit equality predicate 💅

`__gnu_parallel::__qsb_conquer` — quicksort conquer step 👑

`__gnu_parallel::__qsb_divide` — balanced quicksort divide step ⚖️

`__gnu_parallel::__qsb_local_sort_with_helping` — quicksort step doing load-balanced local sort 🧚

`__gnu_parallel::__random_number_pow2` — generate a random number in `[0,2^__logp)` 🎲

`__gnu_parallel::__rd_log2` — rounded-down logarithm of `__n` for base 2 📐

`__gnu_parallel::__round_up_to_pow2` — round up to the next greater power of 2 🔼

`__gnu_parallel::__search_template` — parallel `std::search` 🔍

`__gnu_parallel::__sequential_multiway_merge` — sequential multi-way merging switch 🔀

`__gnu_parallel::__sequential_random_shuffle` — sequential cache-efficient random shuffle 🎲

`__gnu_parallel::__shrink` — combines two ranges into one and halves the number of ranges 🗜️

`__gnu_parallel::__shrink_and_double` — shrinks and doubles the ranges 🔄

`__gnu_parallel::__yield` — yield control to another thread 💅

`__gnu_parallel::list_partition` — splits a sequence into parts of almost equal size ✂️

`const int __gnu_parallel::_CASable_bits [static]`

`const _CASable __gnu_parallel::_CASable_mask [static]`