Classes
class	GenericCharStringSet
	Class implementing StringSet concept for char* and unsigned char* strings. More...

class	GenericCharStringSetTraits
	Traits class implementing StringSet concept for char* and unsigned char* strings. More...

struct	PerfectTreeCalculations
	Class to transform in-order to level-order indexes in a perfect binary tree. More...

class	PS5BigSortStep
	PS5BigSortStep Out-of-Place Parallel Sample Sort with Separate Jobs. More...

class	PS5Context
	Parallel Super Scalar String Sample Sort Context. More...

class	PS5ParametersDefault
	Parallel Super Scalar String Sample Sort Parameter Struct. More...

class	PS5SmallsortJob
	SampleSort: Non-Recursive In-Place Sequential Sample Sort for Small Sorts. More...

class	PS5SortStep
	PS5SortStep Top-Level Class to Keep Track of Substeps. More...

struct	RadixStep_CE0

struct	RadixStep_CE2

struct	RadixStep_CE3

struct	RadixStep_CI2

struct	RadixStep_CI3

class	SSClassifyEqualUnroll
	Sample Sort Classification Tree Unrolled with Equal Comparisons. More...

class	SSClassifyTreeCalcUnrollInterleave

class	SSClassifyTreeUnrollInterleave
	Sample Sort Classification Tree Unrolled and Interleaved. More...

class	SSTreeBuilderLevelOrder

class	SSTreeBuilderPreAndLevelOrder

class	StdStringSet
	Class implementing StringSet concept for arrays of std::string objects. More...

class	StdStringSetTraits
	Class implementing StringSet concept for a std::string objects. More...

class	StringLcpPtr
	Objectified string and LCP array pointer arrays. More...

class	StringPtr
	Objectified string array pointer array. More...

class	StringSetBase
	Base class for common string set functions, included via CRTP. More...

class	StringShadowLcpPtr

class	StringShadowPtr

class	StringSuffixSet
	Class implementing StringSet concept for suffix sorting indexes of a std::string text object. More...

class	StringSuffixSetTraits
	Class implementing StringSet concept for suffix sorting indexes of a std::string text object. More...

class	UPtrStdStringSet
	Class implementing StringSet concept for a std::vector containing std::string objects. More...

class	UPtrStdStringSetTraits
	Class implementing StringSet concept for a std::unique_ptr<std::string objects, which are non-copyable. More...

Typedefs
typedef GenericCharStringSet< const char >	CCharStringSet

typedef GenericCharStringSet< char >	CharStringSet

typedef GenericCharStringSet< const unsigned char >	CUCharStringSet

typedef GenericCharStringSet< unsigned char >	UCharStringSet

Functions
template<typename Type , typename StringSet >
enable_if< sizeof(Type)==4, uint32_t >::type	get_key (const StringSet &strset, const typename StringSet::String &s, size_t depth)

template<typename Type , typename StringSet >
enable_if< sizeof(Type)==8, uint64_t >::type	get_key (const StringSet &strset, const typename StringSet::String &s, size_t depth)

template<typename Type , typename StringSet >
Type	get_key_at (const StringSet &strset, size_t idx, size_t depth)

template<typename KeyType >
static unsigned char	getCharAtDepth (const KeyType &a, unsigned char d)
	return the d-th character in the (swapped) key More...

template<typename StringPtr >
static enable_if<!StringPtr::with_lcp, void >::type	insertion_sort (const StringPtr &strptr, size_t depth, size_t)

template<typename StringPtr >
static enable_if< StringPtr::with_lcp, void >::type	insertion_sort (const StringPtr &strptr, size_t depth, size_t)

template<typename KeyType >
static unsigned char	lcpKeyDepth (const KeyType &a)

template<typename KeyType >
static unsigned char	lcpKeyType (const KeyType &a, const KeyType &b)
	LCP calculation of Splitter Strings. More...

template<typename StringSet >
static StringSet::Iterator	med3func (const StringSet &ss, typename StringSet::Iterator a, typename StringSet::Iterator b, typename StringSet::Iterator c, size_t depth)

template<typename StringPtr >
static void	multikey_quicksort (const StringPtr &strptr, size_t depth, size_t memory)
	Generic multikey quicksort for strings. More...

template<typename StringPtr >
void	parallel_sample_sort (const StringPtr &strptr, size_t depth, size_t memory)

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)

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)

static void	perfect_tree_calculations_self_verify ()

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 StringPtr >
static void	radixsort_CE0 (const StringPtr &strptr, size_t depth, size_t memory)
	Adapter method to allocate shadow array if needed. More...

template<typename StringShadowPtr >
static void	radixsort_CE0_loop (const StringShadowPtr &strptr, size_t depth, size_t memory)

template<typename StringPtr >
static void	radixsort_CE2 (const StringPtr &strptr, size_t depth, size_t memory)

template<typename StringShadowPtr >
static void	radixsort_CE2_loop (const StringShadowPtr &strptr, uint8_t *charcache, size_t depth, size_t memory)

template<typename StringPtr >
static void	radixsort_CE3 (const StringPtr &strptr, size_t depth, size_t memory)

template<typename StringShadowPtr >
static void	radixsort_CE3_loop (const StringShadowPtr &strptr, uint16_t *charcache, size_t depth, size_t memory)

template<typename StringPtr >
static void	radixsort_CI2 (const StringPtr &strptr, uint8_t *charcache, size_t depth, size_t memory)

template<typename StringPtr >
static void	radixsort_CI2 (const StringPtr &strptr, size_t depth, size_t memory)

template<typename StringPtr >
static void	radixsort_CI3 (const StringPtr &strptr, uint16_t *charcache, size_t depth, size_t memory)

template<typename StringPtr >
static void	radixsort_CI3 (const StringPtr &strptr, size_t depth, size_t memory)

template<typename Type >
static std::string	to_binary (Type v, const size_t width=(8 *sizeof(Type)))
	represent binary digits of large integer datatypes More...

template<typename StringSet >
static void	vec_swap (typename StringSet::Iterator a, typename StringSet::Iterator b, size_t n)

Variables
static const size_t	g_inssort_threshold = 32

Typedef Documentation

◆ CCharStringSet

typedef GenericCharStringSet<const char> CCharStringSet

Definition at line 364 of file string_set.hpp.

◆ CharStringSet

typedef GenericCharStringSet<char> CharStringSet

Definition at line 361 of file string_set.hpp.

◆ CUCharStringSet

typedef GenericCharStringSet<const unsigned char> CUCharStringSet

Definition at line 365 of file string_set.hpp.

◆ UCharStringSet

typedef GenericCharStringSet<unsigned char> UCharStringSet

Definition at line 362 of file string_set.hpp.

Function Documentation

◆ get_key() [1/2]

enable_if<sizeof(Type) == 4, uint32_t>::type tlx::sort_strings_detail::get_key	(	const StringSet &	strset,
		const typename StringSet::String &	s,
		size_t	depth
	)

inline

Definition at line 248 of file string_set.hpp.

◆ get_key() [2/2]

enable_if<sizeof(Type) == 8, uint64_t>::type tlx::sort_strings_detail::get_key	(	const StringSet &	strset,
		const typename StringSet::String &	s,
		size_t	depth
	)

inline

Definition at line 256 of file string_set.hpp.

◆ get_key_at()

Type tlx::sort_strings_detail::get_key_at	(	const StringSet &	strset,
		size_t	idx,
		size_t	depth
	)

inline

Definition at line 263 of file string_set.hpp.

◆ getCharAtDepth()

static unsigned char tlx::sort_strings_detail::getCharAtDepth	(	const KeyType &	a,
		unsigned char	d
	)

inlinestatic

return the d-th character in the (swapped) key

Definition at line 164 of file parallel_sample_sort.hpp.

◆ insertion_sort() [1/2]

static enable_if<!StringPtr::with_lcp, void>::type tlx::sort_strings_detail::insertion_sort	(	const StringPtr &	strptr,
		size_t	depth,
		size_t
	)

inlinestatic

Generic insertion sort for abstract string sets. This method only requires O(1) additional memory for sorting n strings, but runs in time O(nD).

Definition at line 35 of file insertion_sort.hpp.

References StringPtr< StringSet_ >::active(), TLX_LIKELY, and TLX_UNLIKELY.

Referenced by PS5SmallsortJob< Context, StringPtr, BktSizeType >::insertion_sort_cache(), multikey_quicksort(), radixsort_CE0(), radixsort_CE0_loop(), radixsort_CE2(), radixsort_CE2_loop(), radixsort_CE3(), radixsort_CE3_loop(), radixsort_CI2(), radixsort_CI3(), and PS5SmallsortJob< Context, StringPtr, BktSizeType >::sort_mkqs_cache().

◆ insertion_sort() [2/2]

static enable_if<StringPtr::with_lcp, void>::type tlx::sort_strings_detail::insertion_sort	(	const StringPtr &	strptr,
		size_t	depth,
		size_t
	)

inlinestatic

LCP insertion sort for abstract string sets. Enabled via SFINAE if StringPtr::with_lcp is true. This method only requires O(1) additional memory for sorting n strings, and runs in time O(n^2 + D).

Definition at line 82 of file insertion_sort.hpp.

References StringPtr< StringSet_ >::active(), and StringPtr< StringSet_ >::set_lcp().

◆ lcpKeyDepth()

static unsigned char tlx::sort_strings_detail::lcpKeyDepth ( const KeyType & a )

inlinestatic

Definition at line 156 of file parallel_sample_sort.hpp.

References tlx::ctz().

Referenced by PS5BigSortStep< Context, StringPtr >::distribute_finished(), PS5SmallsortJob< Context, StringPtr, BktSizeType >::insertion_sort_cache(), PS5SmallsortJob< Context, StringPtr, BktSizeType >::MKQSStep::MKQSStep(), PS5SmallsortJob< Context, StringPtr, BktSizeType >::sample_sort_free_work(), and PS5SmallsortJob< Context, StringPtr, BktSizeType >::sort_sample_sort().

◆ lcpKeyType()

static unsigned char tlx::sort_strings_detail::lcpKeyType	(	const KeyType &	a,
		const KeyType &	b
	)

inlinestatic

LCP calculation of Splitter Strings.

Definition at line 149 of file parallel_sample_sort.hpp.

References tlx::clz().

Referenced by PS5SmallsortJob< Context, StringPtr, BktSizeType >::insertion_sort_cache(), PS5SmallsortJob< Context, StringPtr, BktSizeType >::MKQSStep::MKQSStep(), and ps5_sample_sort_lcp().

◆ med3func()

static StringSet::Iterator tlx::sort_strings_detail::med3func	(	const StringSet &	ss,
		typename StringSet::Iterator	a,
		typename StringSet::Iterator	b,
		typename StringSet::Iterator	c,
		size_t	depth
	)

inlinestatic

Definition at line 47 of file multikey_quicksort.hpp.

Referenced by multikey_quicksort().

◆ multikey_quicksort()

static void tlx::sort_strings_detail::multikey_quicksort	(	const StringPtr &	strptr,
		size_t	depth,
		size_t	memory
	)

inlinestatic

Generic multikey quicksort for strings.

Based on multikey quicksort, a quick sort algorithm for arrays of character strings by Bentley and Sedgewick. This method requires up to O(maxlcp) memory due to the recursion stack and it runs in expected time O(D + n log n) and worst-case time O(D + n^2).

J. Bentley and R. Sedgewick. Fast algorithms for sorting and searching strings. In Proceedings of 8th Annual ACM-SIAM Symposium on Discrete Algorithms, 1997.

Definition at line 74 of file multikey_quicksort.hpp.

References StringPtr< StringSet_ >::active(), insertion_sort(), med3func(), min(), StringPtr< StringSet_ >::set_lcp(), StringPtr< StringSet_ >::sub(), and tlx::swap().

Referenced by radixsort_CE0(), radixsort_CE0_loop(), radixsort_CE2_loop(), radixsort_CE3_loop(), radixsort_CI2(), and radixsort_CI3().

◆ parallel_sample_sort()

void tlx::sort_strings_detail::parallel_sample_sort	(	const StringPtr &	strptr,
		size_t	depth,
		size_t	memory
	)

Parallel Sample Sort Function with default parameter size for a generic StringSet.

Definition at line 1510 of file parallel_sample_sort.hpp.

Referenced by tlx::sort_strings_parallel(), and tlx::sort_strings_parallel_lcp().

◆ parallel_sample_sort_base()

void tlx::sort_strings_detail::parallel_sample_sort_base	(	const StringPtr &	strptr,
		size_t	depth
	)

Main Parallel Sample Sort Function. See below for more convenient wrappers.

Definition at line 1420 of file parallel_sample_sort.hpp.

References StringPtr< StringSet_ >::size(), MultiTimer::start(), MultiTimer::stop(), TLX_LOGC, and MultiTimer::total().

◆ parallel_sample_sort_params() [1/2]

enable_if<!StringPtr::with_lcp, void>::type tlx::sort_strings_detail::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.

Definition at line 1464 of file parallel_sample_sort.hpp.

References StringPtr< StringSet_ >::active(), and tlx::unused().

◆ parallel_sample_sort_params() [2/2]

enable_if<StringPtr::with_lcp, void>::type tlx::sort_strings_detail::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.

Definition at line 1487 of file parallel_sample_sort.hpp.

References StringPtr< StringSet_ >::active(), and tlx::unused().

◆ perfect_tree_calculations_self_verify()

static void tlx::sort_strings_detail::perfect_tree_calculations_self_verify ( )

inlinestatic

Definition at line 103 of file sample_sort_tools.hpp.

References PerfectTreeCalculations< TreeBits >::self_verify().

◆ ps5_sample_sort_lcp()

void tlx::sort_strings_detail::ps5_sample_sort_lcp	(	const Context &	ctx,
		const Classify &	classifier,
		const StringPtr &	strptr,
		size_t	depth,
		const BktSizeType *	bkt
	)