mcstl Namespace Reference

Contains all entities related to the parallel implementation of the STL. It is called the Multi-Core Standard Template Library. More...


Classes

struct  QSBThreadLocal
 Information local to one thread in the parallel quicksort run. More...
class  binary_negate
 Alternative to std::not2, typedefs first_argument_type and second_argument_type not needed. More...
class  equal_from_less
 Constructs predicate for equality from strict weak ordering predicate. More...
class  pseudo_sequence_iterator
 Iterator associated with mcstl::pseudo_sequence. If features the usual random-access iterator functionality. More...
class  pseudo_sequence
 Sequence that conceptually consists of multiple copies of the same element. The copies are not stored explicitly, of course. More...
class  void_functor
 Functor that does nothing. More...
struct  equal_to
 Similar to std::equal_to, but allows two different types. More...
struct  less
 Similar to std::less, but allows two different types. More...
struct  generic_find_selector
 Base class of all mcstl::find_template selectors. More...
struct  find_if_selector
 Test predicate on a single element, used for std::find() and std::find_if(). More...
struct  adjacent_find_selector
 Test predicate on two adjacent elements. More...
struct  mismatch_selector
 Test inverted predicate on a single element. More...
struct  find_first_of_selector
 Test predicate on several elements. More...
struct  generic_for_each_selector
 Generic selector for embarrassingly parallel functions. More...
struct  for_each_selector
 std::for_each() selector. More...
struct  generate_selector
 std::generate() selector. More...
struct  fill_selector
 std::fill() selector. More...
struct  transform1_selector
 std::transform() selector, one input sequence variant. More...
struct  transform2_selector
 std::transform() selector, two input sequences variant. More...
struct  replace_selector
 std::replace() selector. More...
struct  replace_if_selector
 std::replace() selector. More...
struct  count_selector
 std::count() selector. More...
struct  count_if_selector
 std::count_if() selector. More...
struct  accumulate_selector
 std::accumulate() selector. More...
struct  inner_product_selector
 std::inner_product() selector. More...
struct  identity_selector
 Selector that just returns the passed iterator. More...
struct  adjacent_difference_selector
 Selector that returns the difference between two adjacent elements. More...
struct  nothing
 Functor doing nothing. More...
struct  dummy_reduct
 Reduction function doing nothing. More...
struct  min_element_reduct
 Reduction for finding the maximum element, using a comparator. More...
struct  max_element_reduct
 Reduction for finding the maximum element, using a comparator. More...
struct  accumulate_binop_reduct
 General reduction, using a binary operator. More...
class  iterator_pair
 A pair of iterators. The usual iterator operations are applied to both child iterators. More...
class  iterator_triple
 A triple of iterators. The usual iterator operations are applied to all three child iterators. More...
class  lexicographic
 Compare a pair of types lexcigraphically, ascending. More...
class  lexicographic_rev
 Compare a pair of types lexcigraphically, descending. More...
class  guarded_iterator
 Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. Deriving from RandomAccessIterator is not possible since RandomAccessIterator need not be a class. More...
class  unguarded_iterator
struct  loser_tree_traits
class  loser_tree_traits_unguarded
struct  Piece
 Subsequence description. More...
struct  PMWMSSortingData
 Data accessed by all threads. More...
struct  PMWMSSorterPU
 Thread local data for PMWMS. More...
class  RestrictedBoundedConcurrentQueue
 Double-ended queue of bounded size, allowing lock-free atomic access. push_front() and pop_front() must not be called concurrently to each other, while pop_back() can be called concurrently at all times. empty(), size(), and top() are intentionally not provided. Calling them would not make sense in a concurrent setting. More...
class  mersenne_twister
class  random_number
 Random number generator, based on the Mersenne twister. More...
struct  DRandomShufflingGlobalData
 Data known to every thread participating in mcstl::parallel_random_shuffle(). More...
struct  DRSSorterPU
 Local data for a thread participating in mcstl::parallel_random_shuffle(). More...
struct  symmetric_difference_func
struct  difference_func
struct  intersection_func
struct  union_func
struct  parallelism
 Type to be passed to algorithm calls in order to guide their level of parallelism. More...
class  NumberOfThreads
 Pseudo-integer that gets its initial value from omp_get_max_threads(). More...
struct  Settings
 Run-time settings for the MCSTL. More...
class  active_tag
 Makes the parametrized class actually do work, i. e. actives it. More...
class  inactive_tag
 Makes the parametrized class do nothing, i. e. deactives it. More...
struct  sequential_tag
 Forces sequential execution at compile time. More...
struct  parallel_tag
 Recommends parallel execution at compile time. More...
struct  balanced_tag
 Recommends parallel execution using dynamic load-balancing, at compile time. More...
struct  unbalanced_tag
 Recommends parallel execution using static load-balancing, at compile time. More...
struct  omp_loop_tag
 Recommends parallel execution using OpenMP dynamic load-balancing, at compile time. More...
struct  omp_loop_static_tag
 Recommends parallel execution using OpenMP static load-balancing, at compile time. More...
struct  growing_blocks_tag
 Selects the growing block size variant for std::find(). More...
struct  constant_size_blocks_tag
 Selects the constant block size variant for std::find(). More...
struct  equal_split_tag
 Selects the equal splitting variant for std::find(). More...
struct  unconst_first_component
 Helper class: remove the const modifier from the first component, if present. Set kind component. More...
struct  StrictlyLess
 Helper class: set the appropriate comparator to deal with repetitions. Comparator for unique dictionaries. More...
struct  LessEqual
 Helper class: set the appropriate comparator to deal with repetitions. Comparator for non-unique dictionaries. More...
class  _Rb_tree
 Parallel red-black tree. More...
struct  Job
 One job for a certain thread. More...
class  Timing< active_tag, must_be_int >
 A class that provides simple run time measurements, also for parallel code. More...
class  Timing< inactive_tag, must_be_int >
 A class that provides simple run time measurements, also for parallel code. More...
struct  unconst_first_component< std::pair< const Key, Load > >
 Helper class: remove the const modifier from the first component, if present. Map kind component. More...

Typedefs

typedef mersenne_twister<
uint32, 32, 351, 175, 19, 0xccab8ee7, 11, 7, 0x31b6ab00, 15, 0xffe50000, 17, 0xa37d3c92 > 
mt11213b
typedef mersenne_twister<
uint32, 32, 624, 397, 31, 0x9908b0df, 11, 7, 0x9d2c5680, 15, 0xefc60000, 18, 3346425566U > 
mt19937
typedef unsigned short bin_index
 Type to hold the index of a bin.
typedef parallelism PARALLELISM
typedef Settings SETTINGS
 Convenience typedef to avoid to have write Settings<>.
typedef Settings HEURISTIC
 Convenience typedef to avoid to have write Settings<>.
typedef char int8
 8-bit signed integer.
typedef unsigned char uint8
 8-bit unsigned integer.
typedef short int16
 16-bit signed integer.
typedef unsigned short uint16
 16-bit unsigned integer.
typedef int int32
 32-bit signed integer.
typedef unsigned int uint32
 32-bit unsigned integer.
typedef long long int64
 64-bit signed integer.
typedef unsigned long long uint64
 64-bit unsigned integer.
typedef uint64 sequence_index_t
 Unsigned integer to index elements. The total number of elements for each algorithm must fit into this type.
typedef uint16 thread_index_t
 Unsigned integer to index a thread number. The maximum thread number must fit into this type.
typedef int64 lcas_t
 Longest compare-and-swappable integer type on this platform.
typedef double point_in_time
 Type of of point in time, used for the Timing classes.

Functions

template<typename RandomAccessIterator>
void qsb_initialize (QSBThreadLocal< RandomAccessIterator > **tls, int queue_size)
 Initialize the thread local storage.
template<typename RandomAccessIterator, typename Comparator>
std::iterator_traits< RandomAccessIterator
>::difference_type 
qsb_divide (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, int num_threads)
 Balanced quicksort divide step.
template<typename RandomAccessIterator, typename Comparator>
void qsb_conquer (QSBThreadLocal< RandomAccessIterator > **tls, RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, thread_index_t iam, thread_index_t num_threads)
 Quicksort conquer step.
template<typename RandomAccessIterator, typename Comparator>
void qsb_local_sort_with_helping (QSBThreadLocal< RandomAccessIterator > **tls, Comparator &comp, int iam)
 Quicksort step doing load-balanced local sort.
template<typename RandomAccessIterator, typename Comparator>
void parallel_sort_qsb (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, typename std::iterator_traits< RandomAccessIterator >::difference_type n, int num_threads)
 Top-level quicksort routine.
template<typename Size>
Size log2 (Size n)
 Calculates the rounded-down logrithm of n for base 2.
template<typename InputIterator, typename OutputIterator>
OutputIterator partial_sum (InputIterator begin, InputIterator end, OutputIterator result)
 Same functionality as std::partial_sum().
template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
OutputIterator partial_sum (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation binary_op)
 Same functionality as std::partial_sum().
lcas_t encode2 (int a, int b)
 Encode two integers into one mcstl::lcas_t.
void decode2 (lcas_t x, int &a, int &b)
 Decode two integers from one mcstl::lcas_t.
template<typename RandomAccessIterator, typename Comparator>
RandomAccessIterator median_of_three_iterators (RandomAccessIterator a, RandomAccessIterator b, RandomAccessIterator c, Comparator &comp)
 Compute the median of three referenced elements, according to comp.
int32 fetch_and_add_32 (volatile int32 *ptr, int32 addend)
 Add a value to a variable, atomically.
int64 fetch_and_add_64 (volatile int64 *ptr, int64 addend)
 Add a value to a variable, atomically.
template<typename T>
fetch_and_add (volatile T *ptr, T addend)
 Add a value to a variable, atomically.
bool compare_and_swap_32 (volatile int32 *ptr, int32 comparand, int32 replacement)
 Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise.
bool compare_and_swap_64 (volatile int64 *ptr, int64 comparand, int64 replacement)
 Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise.
template<typename T>
bool compare_and_swap (volatile T *ptr, T comparand, T replacement)
 Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise.
void yield ()
 Yield the control to another thread, without waiting for the end to the time slice.
template<typename DiffType, typename DiffTypeOutputIterator>
DiffTypeOutputIterator equally_split (DiffType n, thread_index_t p, DiffTypeOutputIterator s)
 Split a sequence into parts of almost equal size.
template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector>
std::pair< RandomAccessIterator1,
RandomAccessIterator2 > 
find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector)
 Parallel std::find, switch for different algorithms.
template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector>
std::pair< RandomAccessIterator1,
RandomAccessIterator2 > 
find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector, equal_split_tag)
 Parallel std::find, equal splitting variant.
template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector>
std::pair< RandomAccessIterator1,
RandomAccessIterator2 > 
find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector, growing_blocks_tag)
 Parallel std::find, growing block size variant.
template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector>
std::pair< RandomAccessIterator1,
RandomAccessIterator2 > 
find_template (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector, constant_size_blocks_tag)
 Parallel std::find, constant block size variant.
template<typename InputIterator, typename UserOp, typename Functionality, typename Red, typename Result>
UserOp for_each_template_random_access (InputIterator begin, InputIterator end, UserOp user_op, Functionality &functionality, Red reduction, Result reduction_start, Result &output, typename std::iterator_traits< InputIterator >::difference_type bound, PARALLELISM parallelism_tag)
 Chose the desired algorithm by evaluating parallelism_tag.
template<typename InputIterator>
void shrink_and_double (std::vector< InputIterator > &os_starts, size_t &count_to_two, size_t &range_length, const bool make_twice)
 Shrinks and doubles the ranges.
template<typename InputIterator>
void shrink (std::vector< InputIterator > &os_starts, size_t &count_to_two, size_t &range_length)
 Combines two ranges into one and thus halves the number of ranges.
template<typename InputIterator, typename FunctorType>
size_t list_partition (const InputIterator begin, const InputIterator end, InputIterator *starts, size_t *lengths, const int num_parts, FunctorType &f, int oversampling=0)
 Splits a sequence given by input iterators into parts of almost equal size.
template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename DiffType, typename Comparator>
OutputIterator merge_advance_usual (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_length, Comparator comp)
 Merge routine being able to merge only the max_length smallest elements.
template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename DiffType, typename Comparator>
OutputIterator merge_advance_movc (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_length, Comparator comp)
 Merge routine being able to merge only the max_length smallest elements.
template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename DiffType, typename Comparator>
OutputIterator merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_length, Comparator comp)
 Merge routine being able to merge only the max_length smallest elements.
template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename RandomAccessIterator3, typename Comparator>
RandomAccessIterator3 parallel_merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp)
 Merge routine fallback to sequential in case the iterators of the two input sequences are of different type.
template<typename RandomAccessIterator1, typename RandomAccessIterator3, typename Comparator>
RandomAccessIterator3 parallel_merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator1 &begin2, RandomAccessIterator1 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp)
 Parallel merge routine being able to merge only the max_length smallest elements.
template<typename RanSeqs, typename RankType, typename RankIterator, typename Comparator>
void multiseq_partition (RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, RankIterator begin_offsets, Comparator comp=std::less< typename std::iterator_traits< typename std::iterator_traits< RanSeqs >::value_type::first_type >::value_type >())
 Splits several sorted sequences at a certain global rank, resulting in a splitting point for each sequence. The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones on the left side will be chosen from sequences with smaller number.
template<typename T, typename RanSeqs, typename RankType, typename Comparator>
multiseq_selection (RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, RankType &offset, Comparator comp=std::less< T >())
 Selects the element at a certain global rank from several sorted sequences.
template<typename RandomAccessIterator, typename Comparator>
bool operator< (guarded_iterator< RandomAccessIterator, Comparator > &bi1, guarded_iterator< RandomAccessIterator, Comparator > &bi2)
 Compare two elements referenced by guarded iterators.
template<typename RandomAccessIterator, typename Comparator>
bool operator<= (guarded_iterator< RandomAccessIterator, Comparator > &bi1, guarded_iterator< RandomAccessIterator, Comparator > &bi2)
 Compare two elements referenced by guarded iterators.
template<typename RandomAccessIterator, typename Comparator>
bool operator< (unguarded_iterator< RandomAccessIterator, Comparator > &bi1, unguarded_iterator< RandomAccessIterator, Comparator > &bi2)
 Compare two elements referenced by unguarded iterators.
template<typename RandomAccessIterator, typename Comparator>
bool operator<= (unguarded_iterator< RandomAccessIterator, Comparator > &bi1, unguarded_iterator< RandomAccessIterator, Comparator > &bi2)
 Compare two elements referenced by unguarded iterators.
template<typename RandomAccessIteratorIterator, typename Comparator>
std::iterator_traits< typename
std::iterator_traits< RandomAccessIteratorIterator
>::value_type::first_type
>::difference_type 
prepare_unguarded (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp, int &min_sequence, bool stable)
template<typename RandomAccessIteratorIterator, typename Comparator>
std::iterator_traits< typename
std::iterator_traits< RandomAccessIteratorIterator
>::value_type::first_type
>::difference_type 
prepare_unguarded_sentinel (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp)
template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge_3_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable)
 Highly efficient 3-way merging procedure.
template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge_3_combined (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable)
template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge_4_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable)
 Highly efficient 4-way merging procedure.
template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge_4_combined (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable)
template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge_bubble (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable)
 Basic multi-way merging procedure.
template<typename LT, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge_loser_tree (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable)
 Multi-way merging procedure for a high branching factor, guarded case.
template<typename LT, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge_loser_tree_unguarded (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable)
 Multi-way merging procedure for a high branching factor, unguarded case.
template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge_loser_tree_combined (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable)
template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge_loser_tree_sentinel (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable)
template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable, bool sentinel, sequential_tag)
 Sequential multi-way merging switch.
template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 parallel_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable, bool sentinel)
 Parallel multi-way merge routine.
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable)
 Multi-way merging front-end.
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 multiway_merge_sentinel (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIterator3 target, Comparator comp, DiffType length, bool stable)
 Multi-way merging front-end.
template<typename RandomAccessIterator, typename DiffType>
void determine_samples (PMWMSSorterPU< RandomAccessIterator > *d, DiffType &num_samples)
 Select samples from a sequence.
template<typename RandomAccessIterator, typename Comparator>
void parallel_sort_mwms_pu (PMWMSSorterPU< RandomAccessIterator > *d, Comparator &comp)
 PMWMS code executed by each thread.
template<typename RandomAccessIterator, typename Comparator>
void parallel_sort_mwms (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, typename std::iterator_traits< RandomAccessIterator >::difference_type n, int num_threads, bool stable)
 PMWMS main call.
template<typename RandomAccessIterator, typename Op, typename Fu, typename Red, typename Result>
Op for_each_template_random_access_omp_loop (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu &f, Red r, Result base, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound)
 Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop.
template<typename RandomAccessIterator, typename Op, typename Fu, typename Red, typename Result>
Op for_each_template_random_access_omp_loop_static (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu &f, Red r, Result base, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound)
 Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling.
template<typename RandomAccessIterator, typename Op, typename Fu, typename Red, typename Result>
Op for_each_template_random_access_ed (RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu &f, Red r, Result base, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound)
 Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work.
template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
OutputIterator parallel_partial_sum_basecase (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename::std::iterator_traits< InputIterator >::value_type value)
 Base case prefix sum routine.
template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
OutputIterator parallel_partial_sum_linear (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename::std::iterator_traits< InputIterator >::difference_type n, int num_threads)
 Parallel partial sum implmenetation, two-phase approach, no recursion.
template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
OutputIterator parallel_partial_sum (InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op)
 Parallel partial sum front-end.
template<typename RandomAccessIterator, typename Predicate>
std::iterator_traits< RandomAccessIterator
>::difference_type 
parallel_partition (RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, thread_index_t max_num_threads)
 Parallel implementation of std::partition.
template<typename RandomAccessIterator, typename Comparator>
void parallel_nth_element (RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, Comparator comp)
 Parallel implementation of std::nth_element().
template<typename RandomAccessIterator, typename Comparator>
void parallel_partial_sort (RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, Comparator comp)
 Parallel implementation of std::partial_sort().
template<typename RandomAccessIterator, typename Comparator>
std::iterator_traits< RandomAccessIterator
>::difference_type 
parallel_sort_qs_divide (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, typename std::iterator_traits< RandomAccessIterator >::difference_type pivot_rank, typename std::iterator_traits< RandomAccessIterator >::difference_type num_samples, thread_index_t num_threads)
 Unbalanced quicksort divide step.
template<typename RandomAccessIterator, typename Comparator>
void parallel_sort_qs_conquer (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, int num_threads)
 Unbalanced quicksort conquer step.
template<typename RandomAccessIterator, typename Comparator>
void parallel_sort_qs (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, typename std::iterator_traits< RandomAccessIterator >::difference_type n, int num_threads)
 Unbalanced quicksort main call.
template<typename RandomNumberGenerator>
int random_number_pow2 (int logp, RandomNumberGenerator &rng)
 Generate a random number in [0,2^logp).
template<typename RandomAccessIterator, typename RandomNumberGenerator>
void parallel_random_shuffle_drs_pu (DRSSorterPU< RandomAccessIterator, RandomNumberGenerator > *pus)
 Random shuffle code executed by each thread.
template<typename T>
round_up_to_pow2 (T x)
 Round up to the next greater power of 2.
template<typename RandomAccessIterator, typename RandomNumberGenerator>
void parallel_random_shuffle_drs (RandomAccessIterator begin, RandomAccessIterator end, typename std::iterator_traits< RandomAccessIterator >::difference_type n, int num_threads, RandomNumberGenerator &rng)
 Main parallel random shuffle step.
template<typename RandomAccessIterator, typename RandomNumberGenerator>
void sequential_random_shuffle (RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator &rng)
 Sequential cache-efficient random shuffle.
template<typename RandomAccessIterator, typename RandomNumberGenerator>
void parallel_random_shuffle (RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator rng=random_number())
 Parallel random public call.
template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename Pred>
_RandomAccessIterator1 search_template (_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1, _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2, Pred pred)
 Parallel std::search.
template<typename InputIterator, typename OutputIterator>
OutputIterator copy_tail (std::pair< InputIterator, InputIterator > b, std::pair< InputIterator, InputIterator > e, OutputIterator r)
template<typename InputIterator, typename OutputIterator, typename Operation>
OutputIterator parallel_set_operation (InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result, Operation op)
template<typename InputIterator, typename OutputIterator, typename Comparator>
OutputIterator parallel_set_union (InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result, Comparator comp)
template<typename InputIterator, typename OutputIterator, typename Comparator>
OutputIterator parallel_set_intersection (InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result, Comparator comp)
template<typename InputIterator, typename OutputIterator>
OutputIterator set_intersection (InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result)
template<typename InputIterator, typename OutputIterator, typename Comparator>
OutputIterator parallel_set_difference (InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result, Comparator comp)
template<typename InputIterator, typename OutputIterator, typename Comparator>
OutputIterator parallel_set_symmetric_difference (InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result, Comparator comp)
template<typename RandomAccessIterator, typename Comparator>
void parallel_sort (RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, bool stable)
 Choose a parallel sorting algorithm.
template<class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator parallel_unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred)
 Parallel std::unique_copy(), without explicit equality predicate.
template<class InputIterator, class OutputIterator>
OutputIterator parallel_unique_copy (InputIterator first, InputIterator last, OutputIterator result)
 Parallel std::unique_copy(), without explicit equality predicate.
template<typename RandomAccessIterator, typename Op, typename Fu, typename Red, typename Result>
Op for_each_template_random_access_workstealing (RandomAccessIterator begin, RandomAccessIterator end, Op op, Fu &f, Red r, Result base, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound)
 Work stealing algorithm for random access iterators.
template<typename InputIterator, typename Comparator>
bool is_sorted (InputIterator begin, InputIterator end, Comparator comp=std::less< typename std::iterator_traits< InputIterator >::value_type >())
 Check whether [begin, end) is sorted according to comp.
template<typename InputIterator, typename Comparator>
bool is_sorted_failure (InputIterator begin, InputIterator end, InputIterator &first_failure, Comparator comp=std::less< typename std::iterator_traits< InputIterator >::value_type >())
 Check whether [begin, end) is sorted according to comp. Prints the position in case an misordered pair is found.
template<typename InputIterator, typename Comparator>
bool is_sorted_print_failures (InputIterator begin, InputIterator end, Comparator comp=std::less< typename std::iterator_traits< InputIterator >::value_type >())
 Check whether [begin, end) is sorted according to comp. Prints all misordered pair, including the surrounding two elements.

Variables

static const int lcas_t_bits = sizeof(lcas_t) * 8
 Number of bits of lcas_t.
static const lcas_t lcas_t_mask = (((lcas_t)1 << (lcas_t_bits / 2)) - 1)
 lcas_t with the right half of bits set to 1.


Detailed Description

Contains all entities related to the parallel implementation of the STL. It is called the Multi-Core Standard Template Library.

Typedef Documentation

typedef unsigned short mcstl::bin_index

Type to hold the index of a bin.

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

Definition at line 32 of file mcstl_random_shuffle.h.

typedef Settings mcstl::HEURISTIC

Convenience typedef to avoid to have write Settings<>.

Deprecated:
For backward compatibility only.

Definition at line 259 of file mcstl_settings.h.

typedef short mcstl::int16

16-bit signed integer.

Definition at line 27 of file mcstl_types.h.

typedef int mcstl::int32

32-bit signed integer.

Definition at line 31 of file mcstl_types.h.

typedef long long mcstl::int64

64-bit signed integer.

Definition at line 35 of file mcstl_types.h.

typedef char mcstl::int8

8-bit signed integer.

Definition at line 23 of file mcstl_types.h.

typedef int64 mcstl::lcas_t

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

Definition at line 52 of file mcstl_types.h.

typedef mersenne_twister<uint32,32,351,175,19,0xccab8ee7,11, 7,0x31b6ab00,15,0xffe50000,17, 0xa37d3c92> mcstl::mt11213b

Definition at line 249 of file mcstl_random_number.h.

typedef mersenne_twister<uint32,32,624,397,31,0x9908b0df,11, 7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mcstl::mt19937

Definition at line 253 of file mcstl_random_number.h.

typedef parallelism mcstl::PARALLELISM

Definition at line 49 of file mcstl_settings.h.

typedef double mcstl::point_in_time

Type of of point in time, used for the Timing classes.

Definition at line 27 of file mcstl_timing.h.

typedef uint64 mcstl::sequence_index_t

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

Definition at line 43 of file mcstl_types.h.

typedef Settings mcstl::SETTINGS

Convenience typedef to avoid to have write Settings<>.

Definition at line 254 of file mcstl_settings.h.

typedef uint16 mcstl::thread_index_t

Unsigned integer to index a thread number. The maximum thread number must fit into this type.

Definition at line 48 of file mcstl_types.h.

typedef unsigned short mcstl::uint16

16-bit unsigned integer.

Definition at line 29 of file mcstl_types.h.

typedef unsigned int mcstl::uint32

32-bit unsigned integer.

Definition at line 33 of file mcstl_types.h.

typedef unsigned long long mcstl::uint64

64-bit unsigned integer.

Definition at line 37 of file mcstl_types.h.

typedef unsigned char mcstl::uint8

8-bit unsigned integer.

Definition at line 25 of file mcstl_types.h.


Function Documentation

template<typename T>
bool mcstl::compare_and_swap ( volatile T *  ptr,
comparand,
replacement 
) [inline]

Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise.

Implementation is heavily platform-dependent.

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

Definition at line 288 of file mcstl_compatibility.h.

References compare_and_swap_32(), and compare_and_swap_64().

Referenced by mcstl::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::_M_bulk_insertion_merge_concatenate(), mcstl::RestrictedBoundedConcurrentQueue< mcstl::Piece< DiffType > >::pop_back(), and mcstl::RestrictedBoundedConcurrentQueue< mcstl::Piece< DiffType > >::pop_front().

Here is the call graph for this function:

bool mcstl::compare_and_swap_32 ( volatile int32 *  ptr,
int32  comparand,
int32  replacement 
) [inline]

Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise.

Implementation is heavily platform-dependent.

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

Definition at line 205 of file mcstl_compatibility.h.

Referenced by compare_and_swap().

bool mcstl::compare_and_swap_64 ( volatile int64 *  ptr,
int64  comparand,
int64  replacement 
) [inline]

Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise.

Implementation is heavily platform-dependent.

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

Definition at line 241 of file mcstl_compatibility.h.

Referenced by compare_and_swap().

template<typename InputIterator, typename OutputIterator>
OutputIterator mcstl::copy_tail ( std::pair< InputIterator, InputIterator >  b,
std::pair< InputIterator, InputIterator >  e,
OutputIterator  r 
) [inline]

Definition at line 27 of file mcstl_set_operations.h.

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

Decode two integers from one mcstl::lcas_t.

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

Definition at line 102 of file mcstl_base.h.

References lcas_t_bits, and lcas_t_mask.

Referenced by mcstl::RestrictedBoundedConcurrentQueue< mcstl::Piece< DiffType > >::pop_back(), mcstl::RestrictedBoundedConcurrentQueue< mcstl::Piece< DiffType > >::pop_front(), and mcstl::RestrictedBoundedConcurrentQueue< mcstl::Piece< DiffType > >::push_front().

template<typename RandomAccessIterator, typename DiffType>
void mcstl::determine_samples ( PMWMSSorterPU< RandomAccessIterator > *  d,
DiffType &  num_samples 
) [inline]

Select samples from a sequence.

Parameters:
d Pointer to thread-local data. Result will be placed in d->ds->samples.
num_samples Number of samples to select.

Definition at line 94 of file mcstl_multiway_mergesort.h.

References equally_split(), mcstl::PMWMSSorterPU< RandomAccessIterator >::iam, mcstl::PMWMSSorterPU< RandomAccessIterator >::num_threads, mcstl::PMWMSSortingData< RandomAccessIterator >::samples, mcstl::PMWMSSorterPU< RandomAccessIterator >::sd, mcstl::Settings< must_be_int >::sort_mwms_oversampling, mcstl::PMWMSSortingData< RandomAccessIterator >::source, and mcstl::PMWMSSortingData< RandomAccessIterator >::starts.

Referenced by parallel_sort_mwms_pu().

Here is the call graph for this function:

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

Encode two integers into one mcstl::lcas_t.

Parameters:
a First integer, to be encoded in the most-significant lcas_t_bits/2 bits.
b Second integer, to be encoded in the least-significant lcas_t_bits/2 bits.
Returns:
mcstl::lcas_t value encoding a and b.
See also:
decode2

Definition at line 92 of file mcstl_base.h.

References lcas_t_bits.

Referenced by mcstl::RestrictedBoundedConcurrentQueue< mcstl::Piece< DiffType > >::pop_back(), mcstl::RestrictedBoundedConcurrentQueue< mcstl::Piece< DiffType > >::pop_front(), mcstl::RestrictedBoundedConcurrentQueue< mcstl::Piece< DiffType > >::push_front(), and mcstl::RestrictedBoundedConcurrentQueue< mcstl::Piece< DiffType > >::RestrictedBoundedConcurrentQueue().

template<typename DiffType, typename DiffTypeOutputIterator>
DiffTypeOutputIterator mcstl::equally_split ( DiffType  n,
thread_index_t  p,
DiffTypeOutputIterator  s 
)

Split a sequence into parts of almost equal size.

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

Parameters:
n Number of elements
p Number of parts
s Splitters
Returns:
End of splitter sequence, i. e. s+p+1

Definition at line 29 of file mcstl_equally_split.h.

Referenced by determine_samples(), find_template(), parallel_multiway_merge(), parallel_partial_sum_linear(), parallel_set_operation(), parallel_unique_copy(), and search_template().

template<typename T>
T mcstl::fetch_and_add ( volatile T *  ptr,
addend 
) [inline]

Add a value to a variable, atomically.

Implementation is heavily platform-dependent.

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

Definition at line 160 of file mcstl_compatibility.h.

References fetch_and_add_32(), and fetch_and_add_64().

Referenced by mcstl::RestrictedBoundedConcurrentQueue< mcstl::Piece< DiffType > >::push_front().

Here is the call graph for this function:

int32 mcstl::fetch_and_add_32 ( volatile int32 *  ptr,
int32  addend 
) [inline]

Add a value to a variable, atomically.

Implementation is heavily platform-dependent.

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

Definition at line 73 of file mcstl_compatibility.h.

Referenced by fetch_and_add().

int64 mcstl::fetch_and_add_64 ( volatile int64 *  ptr,
int64  addend 
) [inline]

Add a value to a variable, atomically.

Implementation is heavily platform-dependent.

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

Definition at line 111 of file mcstl_compatibility.h.

Referenced by fetch_and_add().

template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector>
std::pair<RandomAccessIterator1, RandomAccessIterator2> mcstl::find_template ( RandomAccessIterator1  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2  begin2,
Pred  pred,
Selector  selector,
constant_size_blocks_tag   
)

Parallel std::find, constant block size variant.

Parameters:
begin1 Begin iterator of first sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence. Second sequence must have same length as first sequence.
pred Find predicate.
selector Functionality (e. g. std::find_if(), std::equal(),...)
Returns:
Place of finding in both sequences.
See also:
mcstl::Settings::find_sequential_search_size

mcstl::Settings::find_block_size There are two main differences between the growing blocks and the constant-size blocks variants. 1. For GB, the block size grows; for CSB, the block size is fixed. 2. For GB, the blocks are allocated dynamically; for CSB, the blocks are allocated in a predetermined manner, namely spacial round-robin.

Definition at line 220 of file mcstl_find.h.

References mcstl::Settings< must_be_int >::find_initial_block_size, mcstl::Settings< must_be_int >::find_sequential_search_size, MCSTL_CALL, and mcstl::Settings< must_be_int >::num_threads.

template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector>
std::pair<RandomAccessIterator1, RandomAccessIterator2> mcstl::find_template ( RandomAccessIterator1  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2  begin2,
Pred  pred,
Selector  selector,
growing_blocks_tag   
)

Parallel std::find, growing block size variant.

Parameters:
begin1 Begin iterator of first sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence. Second sequence must have same length as first sequence.
pred Find predicate.
selector Functionality (e. g. std::find_if(), std::equal(),...)
Returns:
Place of finding in both sequences.
See also:
mcstl::Settings::find_sequential_search_size

mcstl::Settings::find_initial_block_size

mcstl::Settings::find_maximum_block_size

mcstl::Settings::find_increasing_factor

There are two main differences between the growing blocks and the constant-size blocks variants. 1. For GB, the block size grows; for CSB, the block size is fixed. 2. For GB, the blocks are allocated dynamically; for CSB, the blocks are allocated in a predetermined manner, namely spacial round-robin.

Definition at line 138 of file mcstl_find.h.

References mcstl::Settings< must_be_int >::find_increasing_factor, mcstl::Settings< must_be_int >::find_initial_block_size, mcstl::Settings< must_be_int >::find_maximum_block_size, mcstl::Settings< must_be_int >::find_sequential_search_size, MCSTL_CALL, and mcstl::Settings< must_be_int >::num_threads.

template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector>
std::pair<RandomAccessIterator1, RandomAccessIterator2> mcstl::find_template ( RandomAccessIterator1  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2  begin2,
Pred  pred,
Selector  selector,
equal_split_tag   
)

Parallel std::find, equal splitting variant.

Parameters:
begin1 Begin iterator of first sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence. Second sequence must have same length as first sequence.
pred Find predicate.
selector Functionality (e. g. std::find_if(), std::equal(),...)
Returns:
Place of finding in both sequences.

Definition at line 66 of file mcstl_find.h.

References equally_split(), MCSTL_CALL, and mcstl::Settings< must_be_int >::num_threads.

Here is the call graph for this function:

template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred, typename Selector>
std::pair<RandomAccessIterator1, RandomAccessIterator2> mcstl::find_template ( RandomAccessIterator1  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2  begin2,
Pred  pred,
Selector  selector 
)

Parallel std::find, switch for different algorithms.

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

Definition at line 34 of file mcstl_find.h.

References mcstl::Settings< must_be_int >::find_distribution.

Referenced by std::adjacent_find_switch(), std::find_first_of_switch(), std::find_if_switch(), std::find_switch(), and std::mismatch_switch().

template<typename InputIterator, typename UserOp, typename Functionality, typename Red, typename Result>
UserOp mcstl::for_each_template_random_access ( InputIterator  begin,
InputIterator  end,
UserOp  user_op,
Functionality &  functionality,
Red  reduction,
Result  reduction_start,
Result &  output,
typename std::iterator_traits< InputIterator >::difference_type  bound,
PARALLELISM  parallelism_tag 
)

Chose the desired algorithm by evaluating parallelism_tag.

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

Definition at line 38 of file mcstl_for_each.h.

References for_each_template_random_access_ed(), for_each_template_random_access_omp_loop(), for_each_template_random_access_workstealing(), mcstl::parallelism::par, mcstl::parallelism::PARALLEL_OMP_LOOP, mcstl::parallelism::PARALLEL_OMP_LOOP_STATIC, and mcstl::parallelism::PARALLEL_UNBALANCED.

Referenced by std::accumulate_switch(), std::adjacent_difference_switch(), std::count_if_switch(), std::count_switch(), std::fill_switch(), std::for_each_switch(), std::generate_switch(), std::inner_product_switch(), std::max_element_switch(), std::min_element_switch(), std::replace_if_switch(), std::transform1_switch(), and std::transform2_switch().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Op, typename Fu, typename Red, typename Result>
Op mcstl::for_each_template_random_access_ed ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Op  o,
Fu &  f,
Red  r,
Result  base,
Result &  output,
typename std::iterator_traits< RandomAccessIterator >::difference_type  bound 
)

Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work.

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

Definition at line 38 of file mcstl_par_loop.h.

References mcstl::Settings< must_be_int >::num_threads.

Referenced by for_each_template_random_access().

template<typename RandomAccessIterator, typename Op, typename Fu, typename Red, typename Result>
Op mcstl::for_each_template_random_access_omp_loop ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Op  o,
Fu &  f,
Red  r,
Result  base,
Result &  output,
typename std::iterator_traits< RandomAccessIterator >::difference_type  bound 
)

Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop.

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

Definition at line 37 of file mcstl_omp_loop.h.

References mcstl::Settings< must_be_int >::num_threads.

Referenced by for_each_template_random_access().

template<typename RandomAccessIterator, typename Op, typename Fu, typename Red, typename Result>
Op mcstl::for_each_template_random_access_omp_loop_static ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Op  o,
Fu &  f,
Red  r,
Result  base,
Result &  output,
typename std::iterator_traits< RandomAccessIterator >::difference_type  bound 
)

Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling.

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

Definition at line 37 of file mcstl_omp_loop_static.h.

References mcstl::Settings< must_be_int >::num_threads.

template<typename RandomAccessIterator, typename Op, typename Fu, typename Red, typename Result>
Op mcstl::for_each_template_random_access_workstealing ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Op  op,
Fu &  f,
Red  r,
Result  base,
Result &  output,
typename std::iterator_traits< RandomAccessIterator >::difference_type  bound 
)

Work stealing algorithm for random access iterators.

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

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

Definition at line 59 of file mcstl_workstealing.h.

References mcstl::Settings< must_be_int >::cache_line_size, mcstl::Job< DiffType >::first, mcstl::Job< DiffType >::last, mcstl::Job< DiffType >::load, MCSTL_CALL, mcstl::Settings< must_be_int >::num_threads, mcstl::Settings< must_be_int >::workstealing_chunk_size, and yield().

Referenced by for_each_template_random_access().

Here is the call graph for this function:

template<typename InputIterator, typename Comparator>
bool mcstl::is_sorted ( InputIterator  begin,
InputIterator  end,
Comparator  comp = std::less<typename std::iterator_traits<InputIterator>::value_type>() 
)

Check whether [begin, end) is sorted according to comp.

Parameters:
begin Begin iterator of sequence.
end End iterator of sequence.
comp Comparator.
Returns:
true if sorted, false otherwise.

Definition at line 34 of file mcstl_checkers.h.

Referenced by mcstl::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::_M_bulk_insertion_construction(), mcstl::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::is_sorted_distance(), mcstl::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::is_sorted_distance_accessors(), multiway_merge(), multiway_merge_3_combined(), multiway_merge_4_combined(), multiway_merge_loser_tree_combined(), multiway_merge_loser_tree_sentinel(), parallel_multiway_merge(), and parallel_sort_mwms_pu().

template<typename InputIterator, typename Comparator>
bool mcstl::is_sorted_failure ( InputIterator  begin,
InputIterator  end,
InputIterator &  first_failure,
Comparator  comp = std::less<typename std::iterator_traits<InputIterator>::value_type>() 
)

Check whether [begin, end) is sorted according to comp. Prints the position in case an misordered pair is found.

Parameters:
begin Begin iterator of sequence.
end End iterator of sequence.
first_failure The first failure is returned in this variable.
comp Comparator.
Returns:
true if sorted, false otherwise.

Definition at line 67 of file mcstl_checkers.h.

template<typename InputIterator, typename Comparator>
bool mcstl::is_sorted_print_failures ( InputIterator  begin,
InputIterator  end,
Comparator  comp = std::less<typename std::iterator_traits<InputIterator>::value_type>() 
)

Check whether [begin, end) is sorted according to comp. Prints all misordered pair, including the surrounding two elements.

Parameters:
begin Begin iterator of sequence.
end End iterator of sequence.
comp Comparator.
Returns:
true if sorted, false otherwise.

Definition at line 100 of file mcstl_checkers.h.

template<typename InputIterator, typename FunctorType>
size_t mcstl::list_partition ( const InputIterator  begin,
const InputIterator  end,
InputIterator *  starts,
size_t *  lengths,
const int  num_parts,
FunctorType &  f,
int  oversampling = 0 
)

Splits a sequence given by input iterators into parts of almost equal size.

The function needs only one pass over the sequence.

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

Definition at line 69 of file mcstl_list_partition.h.

References shrink_and_double().

Referenced by mcstl::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::is_sorted_distance_accessors().

Here is the call graph for this function:

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

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

Parameters:
n Argument.
Returns:
Returns 0 for argument 0.

Definition at line 27 of file mcstl_base.h.

Referenced by mcstl::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::_M_sorted_bulk_insertion(), multiseq_partition(), multiseq_selection(), mcstl::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::nodes_initializer< ranker >::nodes_initializer(), parallel_sort_qsb(), round_up_to_pow2(), and sequential_random_shuffle().

template<typename RandomAccessIterator, typename Comparator>
RandomAccessIterator mcstl::median_of_three_iterators ( RandomAccessIterator  a,
RandomAccessIterator  b,
RandomAccessIterator  c,
Comparator &  comp 
)

Compute the median of three referenced elements, according to comp.

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

Definition at line 236 of file mcstl_base.h.

Referenced by qsb_divide().

template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename DiffType, typename Comparator>
OutputIterator mcstl::merge_advance ( RandomAccessIterator1 &  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2 &  begin2,
RandomAccessIterator2  end2,
OutputIterator  target,
DiffType  max_length,
Comparator  comp 
) [inline]

Merge routine being able to merge only the max_length smallest elements.

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

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

Definition at line 133 of file mcstl_merge.h.

References MCSTL_CALL, and merge_advance_movc().

Referenced by std::merge_switch(), multiway_merge(), multiway_merge_3_combined(), parallel_merge_advance(), and parallel_multiway_merge().

Here is the call graph for this function:

template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename DiffType, typename Comparator>
OutputIterator mcstl::merge_advance_movc ( RandomAccessIterator1 &  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2 &  begin2,
RandomAccessIterator2  end2,
OutputIterator  target,
DiffType  max_length,
Comparator  comp 
)

Merge routine being able to merge only the max_length smallest elements.

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

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

Definition at line 71 of file mcstl_merge.h.

Referenced by merge_advance().

template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename DiffType, typename Comparator>
OutputIterator mcstl::merge_advance_usual ( RandomAccessIterator1 &  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2 &  begin2,
RandomAccessIterator2  end2,
OutputIterator  target,
DiffType  max_length,
Comparator  comp 
)

Merge routine being able to merge only the max_length smallest elements.

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

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

Definition at line 34 of file mcstl_merge.h.

template<typename RanSeqs, typename RankType, typename RankIterator, typename Comparator>
void mcstl::multiseq_partition ( RanSeqs  begin_seqs,
RanSeqs  end_seqs,
RankType  rank,
RankIterator  begin_offsets,
Comparator  comp = std::less< typename std::iterator_traits<typename std::iterator_traits<RanSeqs>::value_type::first_type>::value_type >() 
)

Splits several sorted sequences at a certain global rank, resulting in a splitting point for each sequence. The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones on the left side will be chosen from sequences with smaller number.

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

Definition at line 84 of file mcstl_multiseq_selection.h.

References log2(), MCSTL_CALL, and S.

Referenced by parallel_multiway_merge(), parallel_set_operation(), and parallel_sort_mwms_pu().

Here is the call graph for this function:

template<typename T, typename RanSeqs, typename RankType, typename Comparator>
T mcstl::multiseq_selection ( RanSeqs  begin_seqs,
RanSeqs  end_seqs,
RankType  rank,
RankType &  offset,
Comparator  comp = std::less<T>() 
)

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

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

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

Definition at line 313 of file mcstl_multiseq_selection.h.

References log2(), MCSTL_CALL, and S.

Here is the call graph for this function:

template<typename RandomAccessIteratorPairIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge ( RandomAccessIteratorPairIterator  seqs_begin,
RandomAccessIteratorPairIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable 
)

Multi-way merging front-end.

Parameters:
seqs_begin Begin iterator of iterator pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge.
stable Stable merging incurs a performance penalty.
Returns:
End iterator of output sequence.

Definition at line 1500 of file mcstl_multiway_merge.h.

References MCSTL_CALL, MCSTL_PARALLEL_CONDITION, and parallel_multiway_merge().

Referenced by multiway_merge_sentinel(), and parallel_multiway_merge().

Here is the call graph for this function:

template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable,
bool  sentinel,
sequential_tag   
)

Sequential multi-way merging switch.

The decision if based on the branching factor and runtime settings.

Parameters:
seqs_begin Begin iterator of iterator pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge.
stable Stable merging incurs a performance penalty.
sentinel The sequences have a sentinel element.
Returns:
End iterator of output sequence.

Definition at line 1187 of file mcstl_multiway_merge.h.

References is_sorted(), MCSTL_CALL, merge_advance(), multiway_merge_3_combined(), multiway_merge_4_combined(), multiway_merge_bubble(), multiway_merge_loser_tree_combined(), and multiway_merge_loser_tree_sentinel().

Referenced by parallel_sort_mwms_pu().

Here is the call graph for this function:

template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge_3_combined ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable 
)

Definition at line 421 of file mcstl_multiway_merge.h.

References is_sorted(), LENGTH, MCSTL_CALL, merge_advance(), and prepare_unguarded().

Referenced by multiway_merge().

Here is the call graph for this function:

template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge_3_variant ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable 
)

Highly efficient 3-way merging procedure.

Parameters:
seqs_begin Begin iterator of iterator pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge.
stable Unused, stable anyway.
Returns:
End iterator of output sequence.

Definition at line 349 of file mcstl_multiway_merge.h.

References MCSTL_CALL, and Merge3Case.

template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge_4_combined ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable 
)

Definition at line 595 of file mcstl_multiway_merge.h.

References is_sorted(), LENGTH, MCSTL_CALL, and prepare_unguarded().

Referenced by multiway_merge().

Here is the call graph for this function:

template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge_4_variant ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable 
)

Highly efficient 4-way merging procedure.

Parameters:
seqs_begin Begin iterator of iterator pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge.
stable Unused, stable anyway.
Returns:
End iterator of output sequence.

Definition at line 498 of file mcstl_multiway_merge.h.

References Decision, MCSTL_CALL, and Merge4Case.

template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge_bubble ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable 
)

Basic multi-way merging procedure.

The head elements are kept in a sorted array, new heads are inserted linearly.

Parameters:
seqs_begin Begin iterator of iterator pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge.
stable Stable merging incurs a performance penalty.
Returns:
End iterator of output sequence.

Definition at line 658 of file mcstl_multiway_merge.h.

References LENGTH, MCSTL_CALL, POS, and STOPS.

Referenced by multiway_merge().

template<typename LT, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge_loser_tree ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable 
)

Multi-way merging procedure for a high branching factor, guarded case.

The head elements are kept in a loser tree.

Parameters:
seqs_begin Begin iterator of iterator pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge.
stable Stable merging incurs a performance penalty.
Returns:
End iterator of output sequence.

Definition at line 828 of file mcstl_multiway_merge.h.

References LENGTH, and MCSTL_CALL.

Referenced by multiway_merge_loser_tree_combined().

template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge_loser_tree_combined ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable 
)

Definition at line 1073 of file mcstl_multiway_merge.h.

References is_sorted(), LENGTH, MCSTL_CALL, multiway_merge_loser_tree(), multiway_merge_loser_tree_unguarded(), and prepare_unguarded().

Referenced by multiway_merge().

Here is the call graph for this function:

template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge_loser_tree_sentinel ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable 
)

Definition at line 1123 of file mcstl_multiway_merge.h.

References is_sorted(), LENGTH, MCSTL_CALL, multiway_merge_loser_tree_unguarded(), and prepare_unguarded_sentinel().

Referenced by multiway_merge().

Here is the call graph for this function:

template<typename LT, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge_loser_tree_unguarded ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable 
)

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

The head elements are kept in a loser tree.

Parameters:
seqs_begin Begin iterator of iterator pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge.
stable Stable merging incurs a performance penalty.
Returns:
End iterator of output sequence.
Precondition:
No input will run out of elements during the merge.

Definition at line 922 of file mcstl_multiway_merge.h.

References LENGTH, MCSTL_ASSERTIONS, and MCSTL_CALL.

Referenced by multiway_merge_loser_tree_combined(), and multiway_merge_loser_tree_sentinel().

template<typename RandomAccessIteratorPairIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::multiway_merge_sentinel ( RandomAccessIteratorPairIterator  seqs_begin,
RandomAccessIteratorPairIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable 
)

Multi-way merging front-end.

Parameters:
seqs_begin Begin iterator of iterator pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge.
stable Stable merging incurs a performance penalty.
Returns:
End iterator of output sequence.
Precondition:
For each i, seqs_begin[i].second must be the end marker of the sequence, but also reference the one more sentinel element.

Definition at line 1532 of file mcstl_multiway_merge.h.

References MCSTL_CALL, MCSTL_PARALLEL_CONDITION, multiway_merge(), and parallel_multiway_merge().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Comparator>
bool mcstl::operator< ( unguarded_iterator< RandomAccessIterator, Comparator > &  bi1,
unguarded_iterator< RandomAccessIterator, Comparator > &  bi2 
) [inline]

Compare two elements referenced by unguarded iterators.

Parameters:
bi1 First iterator.
bi2 Second iterator.
Returns:
True if less.

Definition at line 205 of file mcstl_multiway_merge.h.

References mcstl::unguarded_iterator< RandomAccessIterator, Comparator >::comp.

template<typename RandomAccessIterator, typename Comparator>
bool mcstl::operator< ( guarded_iterator< RandomAccessIterator, Comparator > &  bi1,
guarded_iterator< RandomAccessIterator, Comparator > &  bi2 
) [inline]

Compare two elements referenced by guarded iterators.

Parameters:
bi1 First iterator.
bi2 Second iterator.
Returns:
True if less.

Definition at line 108 of file mcstl_multiway_merge.h.

References mcstl::guarded_iterator< RandomAccessIterator, Comparator >::comp, mcstl::guarded_iterator< RandomAccessIterator, Comparator >::current, and mcstl::guarded_iterator< RandomAccessIterator, Comparator >::end.

template<typename RandomAccessIterator, typename Comparator>
bool mcstl::operator<= ( unguarded_iterator< RandomAccessIterator, Comparator > &  bi1,
unguarded_iterator< RandomAccessIterator, Comparator > &  bi2 
) [inline]

Compare two elements referenced by unguarded iterators.

Parameters:
bi1 First iterator.
bi2 Second iterator.
Returns:
True if less equal.

Definition at line 217 of file mcstl_multiway_merge.h.

References mcstl::unguarded_iterator< RandomAccessIterator, Comparator >::comp.

template<typename RandomAccessIterator, typename Comparator>
bool mcstl::operator<= ( guarded_iterator< RandomAccessIterator, Comparator > &  bi1,
guarded_iterator< RandomAccessIterator, Comparator > &  bi2 
) [inline]

Compare two elements referenced by guarded iterators.

Parameters:
bi1 First iterator.
bi2 Second iterator.
Returns:
True if less equal.

Definition at line 124 of file mcstl_multiway_merge.h.

References mcstl::guarded_iterator< RandomAccessIterator, Comparator >::comp, mcstl::guarded_iterator< RandomAccessIterator, Comparator >::current, and mcstl::guarded_iterator< RandomAccessIterator, Comparator >::end.

template<typename RandomAccessIterator1, typename RandomAccessIterator3, typename Comparator>
RandomAccessIterator3 mcstl::parallel_merge_advance ( RandomAccessIterator1 &  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator1 &  begin2,
RandomAccessIterator1  end2,
RandomAccessIterator3  target,
typename std::iterator_traits< RandomAccessIterator1 >::difference_type  max_length,
Comparator  comp 
) [inline]

Parallel merge routine being able to merge only the max_length smallest elements.

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

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

Definition at line 174 of file mcstl_merge.h.

References parallel_multiway_merge().

Here is the call graph for this function:

template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename RandomAccessIterator3, typename Comparator>
RandomAccessIterator3 mcstl::parallel_merge_advance ( RandomAccessIterator1 &  begin1,
RandomAccessIterator1  end1,
RandomAccessIterator2 &  begin2,
RandomAccessIterator2  end2,
RandomAccessIterator3  target,
typename std::iterator_traits< RandomAccessIterator1 >::difference_type  max_length,
Comparator  comp 
) [inline]

Merge routine fallback to sequential in case the iterators of the two input sequences are of different type.

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

Definition at line 151 of file mcstl_merge.h.

References merge_advance().

Referenced by std::merge_switch().

Here is the call graph for this function:

template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3 mcstl::parallel_multiway_merge ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
RandomAccessIterator3  target,
Comparator  comp,
DiffType  length,
bool  stable,
bool  sentinel 
)

Parallel multi-way merge routine.

The decision if based on the branching factor and runtime settings.

Parameters:
seqs_begin Begin iterator of iterator pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge.
stable Stable merging incurs a performance penalty.
sentinel Ignored.
Returns:
End iterator of output sequence.

Definition at line 1301 of file mcstl_multiway_merge.h.

References equally_split(), is_sorted(), LENGTH, MCSTL_CALL, merge_advance(), multiseq_partition(), and multiway_merge().

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

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Comparator>
void mcstl::parallel_nth_element ( RandomAccessIterator  begin,
RandomAccessIterator  nth,
RandomAccessIterator  end,
Comparator  comp 
)

Parallel implementation of std::nth_element().

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

Definition at line 266 of file mcstl_partition.h.

References MCSTL_CALL, mcstl::Settings< must_be_int >::num_threads, parallel_partition(), and mcstl::Settings< must_be_int >::partition_minimal_n.

Referenced by std::nth_element(), and parallel_partial_sort().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Comparator>
void mcstl::parallel_partial_sort ( RandomAccessIterator  begin,
RandomAccessIterator  middle,
RandomAccessIterator  end,
Comparator  comp 
)

Parallel implementation of std::partial_sort().

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

Definition at line 328 of file mcstl_partition.h.

References parallel_nth_element(), and std::sort().

Referenced by std::partial_sort().

Here is the call graph for this function:

template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
OutputIterator mcstl::parallel_partial_sum ( InputIterator  begin,
InputIterator  end,
OutputIterator  result,
BinaryOperation  bin_op 
)

Parallel partial sum front-end.

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

Definition at line 140 of file mcstl_partial_sum.h.

References mcstl::Settings< must_be_int >::LINEAR, MCSTL_CALL, mcstl::Settings< must_be_int >::num_threads, parallel_partial_sum_linear(), and mcstl::Settings< must_be_int >::partial_sum_algorithm.

Referenced by std::partial_sum_switch().

Here is the call graph for this function:

template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
OutputIterator mcstl::parallel_partial_sum_basecase ( InputIterator  begin,
InputIterator  end,
OutputIterator  result,
BinaryOperation  bin_op,
typename::std::iterator_traits< InputIterator >::value_type  value 
) [inline]

Base case prefix sum routine.

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

Definition at line 37 of file mcstl_partial_sum.h.

Referenced by parallel_partial_sum_linear().

template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
OutputIterator mcstl::parallel_partial_sum_linear ( InputIterator  begin,
InputIterator  end,
OutputIterator  result,
BinaryOperation  bin_op,
typename::std::iterator_traits< InputIterator >::difference_type  n,
int  num_threads 
)

Parallel partial sum implmenetation, two-phase approach, no recursion.

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

Definition at line 65 of file mcstl_partial_sum.h.

References std::accumulate(), equally_split(), parallel_partial_sum_basecase(), and mcstl::Settings< must_be_int >::partial_sum_dilatation.

Referenced by parallel_partial_sum().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Predicate>
std::iterator_traits<RandomAccessIterator>::difference_type mcstl::parallel_partition ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Predicate  pred,
thread_index_t  max_num_threads 
) [inline]

Parallel implementation of std::partition.

Parameters:
begin Begin iterator of input sequence to split.
end End iterator of input sequence to split.
pred Partition predicate, possibly including some kind of pivot.
max_num_threads Maximum number of threads to use for this task.
Returns:
Number of elements not fulfilling the predicate.

Definition at line 43 of file mcstl_partition.h.

References MCSTL_CALL, MCSTL_VOLATILE, mcstl::Settings< must_be_int >::partition_chunk_share, and mcstl::Settings< must_be_int >::partition_chunk_size.

Referenced by parallel_nth_element(), parallel_sort_qs_divide(), std::partition_switch(), and qsb_divide().

template<typename RandomAccessIterator, typename RandomNumberGenerator>
void mcstl::parallel_random_shuffle ( RandomAccessIterator  begin,
RandomAccessIterator  end,
RandomNumberGenerator  rng = random_number() 
) [inline]

Parallel random public call.

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

Definition at line 459 of file mcstl_random_shuffle.h.

References parallel_random_shuffle_drs().

Referenced by std::random_shuffle().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename RandomNumberGenerator>
void mcstl::parallel_random_shuffle_drs ( RandomAccessIterator  begin,
RandomAccessIterator  end,
typename std::iterator_traits< RandomAccessIterator >::difference_type  n,
int  num_threads,
RandomNumberGenerator &  rng 
) [inline]

Main parallel random shuffle step.

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

Definition at line 238 of file mcstl_random_shuffle.h.

References mcstl::DRandomShufflingGlobalData< RandomAccessIterator >::bin_proc, mcstl::DRandomShufflingGlobalData< RandomAccessIterator >::dist, MCSTL_CALL, round_up_to_pow2(), sequential_random_shuffle(), and mcstl::DRandomShufflingGlobalData< RandomAccessIterator >::temporaries.

Referenced by parallel_random_shuffle().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename RandomNumberGenerator>
void mcstl::parallel_random_shuffle_drs_pu ( DRSSorterPU< RandomAccessIterator, RandomNumberGenerator > *  pus  )  [inline]

Random shuffle code executed by each thread.

Parameters:
pus Arary of thread-local data records.

Definition at line 94 of file mcstl_random_shuffle.h.

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

Here is the call graph for this function:

template<typename InputIterator, typename OutputIterator, typename Comparator>
OutputIterator mcstl::parallel_set_difference ( InputIterator  begin1,
InputIterator  end1,
InputIterator  begin2,
InputIterator  end2,
OutputIterator  result,
Comparator  comp 
)

Definition at line 438 of file mcstl_set_operations.h.

References parallel_set_operation().

Referenced by std::set_difference_switch().

Here is the call graph for this function:

template<typename InputIterator, typename OutputIterator, typename Comparator>
OutputIterator mcstl::parallel_set_intersection ( InputIterator  begin1,
InputIterator  end1,
InputIterator  begin2,
InputIterator  end2,
OutputIterator  result,
Comparator  comp 
)

Definition at line 418 of file mcstl_set_operations.h.

References parallel_set_operation().

Referenced by std::set_intersection_switch().

Here is the call graph for this function:

template<typename InputIterator, typename OutputIterator, typename Operation>
OutputIterator mcstl::parallel_set_operation ( InputIterator  begin1,
InputIterator  end1,
InputIterator  begin2,
InputIterator  end2,
OutputIterator  result,
Operation  op 
)

Definition at line 291 of file mcstl_set_operations.h.

References equally_split(), MCSTL_CALL, multiseq_partition(), and mcstl::Settings< must_be_int >::num_threads.

Referenced by parallel_set_difference(), parallel_set_intersection(), parallel_set_symmetric_difference(), and parallel_set_union().

Here is the call graph for this function:

template<typename InputIterator, typename OutputIterator, typename Comparator>
OutputIterator mcstl::parallel_set_symmetric_difference ( InputIterator  begin1,
InputIterator  end1,
InputIterator  begin2,
InputIterator  end2,
OutputIterator  result,
Comparator  comp 
)

Definition at line 447 of file mcstl_set_operations.h.

References parallel_set_operation().

Referenced by std::set_symmetric_difference_switch().

Here is the call graph for this function:

template<typename InputIterator, typename OutputIterator, typename Comparator>
OutputIterator mcstl::parallel_set_union ( InputIterator  begin1,
InputIterator  end1,
InputIterator  begin2,
InputIterator  end2,
OutputIterator  result,
Comparator  comp 
)

Definition at line 409 of file mcstl_set_operations.h.

References parallel_set_operation().

Referenced by std::set_union_switch().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Comparator>
void mcstl::parallel_sort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
bool  stable 
) [inline]

Choose a parallel sorting algorithm.

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

Definition at line 48 of file mcstl_sort.h.

References MCSTL_CALL, mcstl::Settings< must_be_int >::MWMS, mcstl::Settings< must_be_int >::num_threads, parallel_sort_mwms(), parallel_sort_qs(), parallel_sort_qsb(), mcstl::Settings< must_be_int >::QS, mcstl::Settings< must_be_int >::QS_BALANCED, and mcstl::Settings< must_be_int >::sort_algorithm.

Referenced by std::sort(), and std::stable_sort().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Comparator>
void mcstl::parallel_sort_mwms ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
typename std::iterator_traits< RandomAccessIterator >::difference_type  n,
int  num_threads,
bool  stable 
) [inline]

PMWMS main call.

Parameters:
begin Begin iterator of sequence.
end End iterator of sequence.
comp Comparator.
n Length of sequence.
num_threads Number of threads to use.
stable Stable sorting.

Definition at line 279 of file mcstl_multiway_mergesort.h.

References mcstl::PMWMSSorterPU< RandomAccessIterator >::iam, MCSTL_CALL, mcstl::PMWMSSorterPU< RandomAccessIterator >::num_threads, parallel_sort_mwms_pu(), mcstl::Settings< must_be_int >::SAMPLING, mcstl::PMWMSSorterPU< RandomAccessIterator >::sd, mcstl::Settings< must_be_int >::sort_mwms_oversampling, mcstl::Settings< must_be_int >::sort_splitting, and mcstl::PMWMSSorterPU< RandomAccessIterator >::stable.

Referenced by parallel_sort().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Comparator>
void mcstl::parallel_sort_mwms_pu ( PMWMSSorterPU< RandomAccessIterator > *  d,
Comparator &  comp 
) [inline]

PMWMS code executed by each thread.

Parameters:
d Pointer to thread-local data.
comp Comparator.

Definition at line 111 of file mcstl_multiway_mergesort.h.

References determine_samples(), mcstl::Settings< must_be_int >::EXACT, mcstl::PMWMSSorterPU< RandomAccessIterator >::iam, is_sorted(), MCSTL_ASSERTIONS, mcstl::PMWMSSortingData< RandomAccessIterator >::merging_places, multiseq_partition(), multiway_merge(), mcstl::PMWMSSorterPU< RandomAccessIterator >::num_threads, mcstl::PMWMSSortingData< RandomAccessIterator >::pieces, mcstl::PMWMSSortingData< RandomAccessIterator >::samples, mcstl::Settings< must_be_int >::SAMPLING, mcstl::PMWMSSorterPU< RandomAccessIterator >::sd, mcstl::Settings< must_be_int >::sort_splitting, mcstl::PMWMSSortingData< RandomAccessIterator >::sorting_places, mcstl::PMWMSSortingData< RandomAccessIterator >::source, mcstl::PMWMSSorterPU< RandomAccessIterator >::stable, mcstl::PMWMSSortingData< RandomAccessIterator >::starts, and mcstl::PMWMSSortingData< RandomAccessIterator >::temporaries.

Referenced by parallel_sort_mwms().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Comparator>
void mcstl::parallel_sort_qs ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
typename std::iterator_traits< RandomAccessIterator >::difference_type  n,
int  num_threads 
) [inline]

Unbalanced quicksort main call.

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

Definition at line 122 of file mcstl_quicksort.h.

References MCSTL_CALL, parallel_sort_qs_conquer(), and mcstl::Settings< must_be_int >::sort_qs_num_samples_preset.

Referenced by parallel_sort().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Comparator>
void mcstl::parallel_sort_qs_conquer ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
int  num_threads 
) [inline]

Unbalanced quicksort conquer step.

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

Definition at line 70 of file mcstl_quicksort.h.

References parallel_sort_qs_divide(), and mcstl::Settings< must_be_int >::sort_qs_num_samples_preset.

Referenced by parallel_sort_qs().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Comparator>
std::iterator_traits<RandomAccessIterator>::difference_type mcstl::parallel_sort_qs_divide ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
typename std::iterator_traits< RandomAccessIterator >::difference_type  pivot_rank,
typename std::iterator_traits< RandomAccessIterator >::difference_type  num_samples,
thread_index_t  num_threads 
) [inline]

Unbalanced quicksort divide step.

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

Definition at line 33 of file mcstl_quicksort.h.

References parallel_partition().

Referenced by parallel_sort_qs_conquer().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Comparator>
void mcstl::parallel_sort_qsb ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
typename std::iterator_traits< RandomAccessIterator >::difference_type  n,
int  num_threads 
) [inline]

Top-level quicksort routine.

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

Definition at line 344 of file mcstl_balanced_quicksort.h.

References log2(), MCSTL_CALL, qsb_conquer(), and qsb_initialize().

Referenced by parallel_sort().

Here is the call graph for this function:

template<class InputIterator, class OutputIterator>
OutputIterator mcstl::parallel_unique_copy ( InputIterator  first,
InputIterator  last,
OutputIterator  result 
) [inline]

Parallel std::unique_copy(), without explicit equality predicate.

Parameters:
first Begin iterator of input sequence.
last End iterator of input sequence.
result Begin iterator of result sequence.
Returns:
End iterator of result sequence.

Definition at line 160 of file mcstl_unique_copy.h.

References parallel_unique_copy().

Here is the call graph for this function:

template<class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator mcstl::parallel_unique_copy ( InputIterator  first,
InputIterator  last,
OutputIterator  result,
BinaryPredicate  binary_pred 
) [inline]

Parallel std::unique_copy(), without explicit equality predicate.

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

Definition at line 29 of file mcstl_unique_copy.h.

References equally_split(), MCSTL_CALL, and mcstl::Settings< must_be_int >::num_threads.

Referenced by parallel_unique_copy(), and std::unique_copy_switch().

Here is the call graph for this function:

template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
OutputIterator mcstl::partial_sum ( InputIterator  begin,
InputIterator  end,
OutputIterator  result,
BinaryOperation  binary_op 
)

Same functionality as std::partial_sum().

Definition at line 55 of file mcstl_base.h.

template<typename InputIterator, typename OutputIterator>
OutputIterator mcstl::partial_sum ( InputIterator  begin,
InputIterator  end,
OutputIterator  result 
)

Same functionality as std::partial_sum().

Definition at line 37 of file mcstl_base.h.

Referenced by mcstl::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::_M_sorted_no_gapped_bulk_allocation_and_initialization(), and parallel_random_shuffle_drs_pu().

template<typename RandomAccessIteratorIterator, typename Comparator>
std::iterator_traits<typename std::iterator_traits<RandomAccessIteratorIterator>::value_type::first_type>::difference_type mcstl::prepare_unguarded ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
Comparator  comp,
int &  min_sequence,
bool  stable 
)

Prepare a set of sequences to be merged without a (end) guard

Parameters:
seqs_begin 
seqs_end 
comp 
min_sequence 
stable 
Precondition:
(seqs_end - seqs_begin > 0)

Definition at line 233 of file mcstl_multiway_merge.h.

References MCSTL_CALL.

Referenced by multiway_merge_3_combined(), multiway_merge_4_combined(), and multiway_merge_loser_tree_combined().

template<typename RandomAccessIteratorIterator, typename Comparator>
std::iterator_traits<typename std::iterator_traits<RandomAccessIteratorIterator>::value_type::first_type>::difference_type mcstl::prepare_unguarded_sentinel ( RandomAccessIteratorIterator  seqs_begin,
RandomAccessIteratorIterator  seqs_end,
Comparator  comp 
)

Prepare a set of sequences to be merged with a (end) guard (sentinel)

Parameters:
seqs_begin 
seqs_end 
comp 

Definition at line 301 of file mcstl_multiway_merge.h.

References MCSTL_CALL.

Referenced by multiway_merge_loser_tree_sentinel().

template<typename RandomAccessIterator, typename Comparator>
void mcstl::qsb_conquer ( QSBThreadLocal< RandomAccessIterator > **  tls,
RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
thread_index_t  iam,
thread_index_t  num_threads 
) [inline]

Quicksort conquer step.

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

Definition at line 137 of file mcstl_balanced_quicksort.h.

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

Referenced by parallel_sort_qsb().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename Comparator>
std::iterator_traits<RandomAccessIterator>::difference_type mcstl::qsb_divide ( RandomAccessIterator  begin,
RandomAccessIterator  end,
Comparator  comp,
int  num_threads 
) [inline]

Balanced quicksort divide step.

Parameters:
begin Begin iterator of subsequence.
end End iterator of subsequence.
comp Comparator.
num_threads Number of threads that are allowed to work on this part.
Precondition:
(end-begin)>=1

Definition at line 79 of file mcstl_balanced_quicksort.h.

References median_of_three_iterators(), and parallel_partition().

Referenced by qsb_conquer().

Here is the call graph for this function:

template<typename RandomAccessIterator>
void mcstl::qsb_initialize ( QSBThreadLocal< RandomAccessIterator > **  tls,
int  queue_size 
) [inline]

Initialize the thread local storage.

Parameters:
tls Array of thread-local storages.
queue_size Size of the work-stealing queue.

Definition at line 61 of file mcstl_balanced_quicksort.h.

Referenced by parallel_sort_qsb().

template<typename RandomAccessIterator, typename Comparator>
void mcstl::qsb_local_sort_with_helping ( QSBThreadLocal< RandomAccessIterator > **  tls,
Comparator &  comp,
int  iam 
) [inline]

Quicksort step doing load-balanced local sort.

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

Definition at line 190 of file mcstl_balanced_quicksort.h.

References mcstl::QSBThreadLocal< RandomAccessIterator >::elements_leftover, mcstl::QSBThreadLocal< RandomAccessIterator >::initial, mcstl::QSBThreadLocal< RandomAccessIterator >::leftover_parts, MCSTL_ASSERTIONS, mcstl::QSBThreadLocal< RandomAccessIterator >::num_threads, mcstl::Settings< must_be_int >::sort_qsb_base_case_maximal_n, and yield().

Referenced by qsb_conquer().

Here is the call graph for this function:

template<typename RandomNumberGenerator>
int mcstl::random_number_pow2 ( int  logp,
RandomNumberGenerator &  rng 
) [inline]

Generate a random number in [0,2^logp).

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

Definition at line 86 of file mcstl_random_shuffle.h.

Referenced by parallel_random_shuffle_drs_pu(), and sequential_random_shuffle().

template<typename T>
T mcstl::round_up_to_pow2 ( x  ) 

Round up to the next greater power of 2.

Parameters:
x Integer to round up

Definition at line 221 of file mcstl_random_shuffle.h.

References log2().

Referenced by parallel_random_shuffle_drs(), and sequential_random_shuffle().

Here is the call graph for this function:

template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename Pred>
_RandomAccessIterator1 mcstl::search_template ( _RandomAccessIterator1  begin1,
_RandomAccessIterator1  end1,
_RandomAccessIterator2  begin2,
_RandomAccessIterator2  end2,
Pred  pred 
)

Parallel std::search.

Parameters:
begin1 Begin iterator of first sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
pred Find predicate.
Returns:
Place of finding in first sequences.

Definition at line 51 of file mcstl_search.h.

References calc_borders(), equally_split(), MCSTL_CALL, and mcstl::Settings< must_be_int >::num_threads.

Referenced by std::search_n_switch(), and std::search_switch().

Here is the call graph for this function:

template<typename RandomAccessIterator, typename RandomNumberGenerator>
void mcstl::sequential_random_shuffle ( RandomAccessIterator  begin,
RandomAccessIterator  end,
RandomNumberGenerator &  rng 
) [inline]

Sequential cache-efficient random shuffle.

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

Definition at line 351 of file mcstl_random_shuffle.h.

References log2(), partial_sum, random_number_pow2(), and round_up_to_pow2().

Referenced by parallel_random_shuffle_drs(), and std::random_shuffle().

Here is the call graph for this function:

template<typename InputIterator, typename OutputIterator>
OutputIterator mcstl::set_intersection ( InputIterator  begin1,
InputIterator  end1,
InputIterator  begin2,
InputIterator  end2,
OutputIterator  result 
)

Definition at line 428 of file mcstl_set_operations.h.

template<typename InputIterator>
void mcstl::shrink ( std::vector< InputIterator > &  os_starts,
size_t &  count_to_two,
size_t &  range_length 
)

Combines two ranges into one and thus halves the number of ranges.

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

Definition at line 47 of file mcstl_list_partition.h.

Referenced by shrink_and_double().

template<typename InputIterator>
void mcstl::shrink_and_double ( std::vector< InputIterator > &  os_starts,
size_t &  count_to_two,
size_t &  range_length,
const bool  make_twice 
)

Shrinks and doubles the ranges.

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

Definition at line 28 of file mcstl_list_partition.h.

References shrink().

Referenced by list_partition().

Here is the call graph for this function:

void mcstl::yield (  )  [inline]

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

Definition at line 299 of file mcstl_compatibility.h.

Referenced by mcstl::_Rb_tree< _Key, _Val, _KeyOfValue, _Compare, _Alloc >::_M_sorted_bulk_insertion(), for_each_template_random_access_workstealing(), and qsb_local_sort_with_helping().


Variable Documentation

const int mcstl::lcas_t_bits = sizeof(lcas_t) * 8 [static]

Number of bits of lcas_t.

Definition at line 56 of file mcstl_types.h.

Referenced by decode2(), and encode2().

const lcas_t mcstl::lcas_t_mask = (((lcas_t)1 << (lcas_t_bits / 2)) - 1) [static]

lcas_t with the right half of bits set to 1.

Definition at line 60 of file mcstl_types.h.

Referenced by decode2().


Generated on Fri Aug 24 22:05:43 2007 by  doxygen 1.5.0