tlx
parallel_sample_sort.hpp File Reference
#include <algorithm>
#include <atomic>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <random>
#include <vector>
#include <tlx/sort/strings/insertion_sort.hpp>
#include <tlx/sort/strings/sample_sort_tools.hpp>
#include <tlx/sort/strings/string_ptr.hpp>
#include <tlx/logger/core.hpp>
#include <tlx/math/clz.hpp>
#include <tlx/math/ctz.hpp>
#include <tlx/meta/enable_if.hpp>
#include <tlx/multi_timer.hpp>
#include <tlx/simple_vector.hpp>
#include <tlx/thread_pool.hpp>
#include <tlx/unused.hpp>

Go to the source code of this file.

Classes

class  PS5ParametersDefault
 Parallel Super Scalar String Sample Sort Parameter Struct. More...
 
class  PS5Context< Parameters >
 Parallel Super Scalar String Sample Sort Context. More...
 
class  PS5SortStep
 PS5SortStep Top-Level Class to Keep Track of Substeps. More...
 
class  PS5SmallsortJob< Context, StringPtr, BktSizeType >
 SampleSort: Non-Recursive In-Place Sequential Sample Sort for Small Sorts. More...
 
class  PS5SmallsortJob< Context, StringPtr, BktSizeType >::SeqSampleSortStep
 Stack of Recursive Sample Sort Steps. More...
 
class  PS5SmallsortJob< Context, StringPtr, BktSizeType >::MKQSStep
 
class  PS5BigSortStep< Context, StringPtr >
 PS5BigSortStep Out-of-Place Parallel Sample Sort with Separate Jobs. More...
 

Namespaces

 tlx
 
 tlx::sort_strings_detail
 

Functions

template<typename KeyType >
static unsigned char lcpKeyType (const KeyType &a, const KeyType &b)
 LCP calculation of Splitter Strings. More...
 
template<typename KeyType >
static unsigned char lcpKeyDepth (const KeyType &a)
 
template<typename KeyType >
static unsigned char getCharAtDepth (const KeyType &a, unsigned char d)
 return the d-th character in the (swapped) key More...
 
template<size_t bktnum, typename Context , typename Classify , typename StringPtr , typename BktSizeType >
void ps5_sample_sort_lcp (const Context &ctx, const Classify &classifier, const StringPtr &strptr, size_t depth, const BktSizeType *bkt)
 LCP Calculation for Finished Sample Sort Steps. More...
 
template<typename PS5Parameters , typename StringPtr >
void parallel_sample_sort_base (const StringPtr &strptr, size_t depth)
 Main Parallel Sample Sort Function. See below for more convenient wrappers. More...
 
template<typename PS5Parameters , typename StringPtr >
enable_if<!StringPtr::with_lcp, void >::type parallel_sample_sort_params (const StringPtr &strptr, size_t depth, size_t memory=0)
 Parallel Sample Sort Function for a generic StringSet, this allocates the shadow array for flipping. More...
 
template<typename PS5Parameters , typename StringPtr >
enable_if< StringPtr::with_lcp, void >::type parallel_sample_sort_params (const StringPtr &strptr, size_t depth, size_t memory=0)
 Parallel Sample Sort Function for a generic StringSet with LCPs, this allocates the shadow array for flipping. More...
 
template<typename StringPtr >
void parallel_sample_sort (const StringPtr &strptr, size_t depth, size_t memory)
 Parallel Sample Sort Function with default parameter size for a generic StringSet. More...