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
	Sample Sort Classification Tree Unrolled, Interleaved, and with Perfect Tree Index Calculations. More...

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

class	SSTreeBuilderLevelOrder
	Recursive TreeBuilder for full-descent and unrolled variants, constructs only a level-order binary tree of splitters. More...

class	SSTreeBuilderPreAndLevelOrder
	Recursive TreeBuilder for full-descent and unrolled variants, constructs a both a pre-order and level-order array of splitters and the corresponding LCPs. More...

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
	Objectified string array pointer and shadow pointer array for out-of-place swapping of pointers. More...

class	StringShadowPtr
	Objectified string array pointer and shadow pointer array for out-of-place swapping of pointers. More...

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< char >	CharStringSet

typedef GenericCharStringSet< unsigned char >	UCharStringSet

typedef GenericCharStringSet< const char >	CCharStringSet

typedef GenericCharStringSet< const unsigned char >	CUCharStringSet

Functions
template<typename StringPtr >
static enable_if<!StringPtr::with_lcp, void >::type	insertion_sort (const StringPtr &strptr, size_t depth, size_t)
	Generic insertion sort for abstract string sets. More...

template<typename StringPtr >
static enable_if< StringPtr::with_lcp, void >::type	insertion_sort (const StringPtr &strptr, size_t depth, size_t)
	LCP insertion sort for abstract string sets. More...

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

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

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

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 StringPtr >
static void	radixsort_CI3 (const StringPtr &strptr, uint16_t *charcache, 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_CE2 (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_CE3 (const StringPtr &strptr, 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, 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...

static void	perfect_tree_calculations_self_verify ()

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)

Variables
static const size_t	g_inssort_threshold

Typedef Documentation

typedef GenericCharStringSet<const char> CCharStringSet

Definition at line 364 of file string_set.hpp.

typedef GenericCharStringSet<char> CharStringSet

Definition at line 361 of file string_set.hpp.

typedef GenericCharStringSet<const unsigned char> CUCharStringSet

Definition at line 365 of file string_set.hpp.

typedef GenericCharStringSet<unsigned char> UCharStringSet

Definition at line 362 of file string_set.hpp.

Function Documentation

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.

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.

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.

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.

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.

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.

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

inlinestatic

Definition at line 156 of file parallel_sample_sort.hpp.

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.

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.

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.

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.

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.

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.

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.

static void tlx::sort_strings_detail::perfect_tree_calculations_self_verify ( )

inlinestatic

Definition at line 103 of file sample_sort_tools.hpp.

void tlx::sort_strings_detail::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.

Definition at line 206 of file parallel_sample_sort.hpp.

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

inlinestatic

Adapter method to allocate shadow array if needed.

Definition at line 166 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CE0_loop	(	const StringShadowPtr &	strptr,
		size_t	depth,
		size_t	memory
	)

inlinestatic

Definition at line 112 of file radix_sort.hpp.

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

inlinestatic

Definition at line 319 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CE2_loop	(	const StringShadowPtr &	strptr,
		uint8_t *	charcache,
		size_t	depth,
		size_t	memory
	)

inlinestatic

Definition at line 267 of file radix_sort.hpp.

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

inlinestatic

Definition at line 502 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CE3_loop	(	const StringShadowPtr &	strptr,
		uint16_t *	charcache,
		size_t	depth,
		size_t	memory
	)

inlinestatic

Definition at line 430 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CI2	(	const StringPtr &	strptr,
		uint8_t *	charcache,
		size_t	depth,
		size_t	memory
	)

inlinestatic

Definition at line 616 of file radix_sort.hpp.

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

inlinestatic

Definition at line 673 of file radix_sort.hpp.

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

inlinestatic

Definition at line 788 of file radix_sort.hpp.

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

inlinestatic

Definition at line 861 of file radix_sort.hpp.

static std::string tlx::sort_strings_detail::to_binary	(	Type	v,
		const size_t	width = `(8 * sizeof(Type))`
	)

inlinestatic

represent binary digits of large integer datatypes

Definition at line 40 of file sample_sort_tools.hpp.

static void tlx::sort_strings_detail::vec_swap	(	typename StringSet::Iterator	a,
		typename StringSet::Iterator	b,
		size_t	n
	)

inlinestatic

Definition at line 40 of file multikey_quicksort.hpp.

Variable Documentation

const size_t g_inssort_threshold

static

Definition at line 42 of file radix_sort.hpp.

Classes

Typedefs

Functions

Variables

Typedef Documentation

Function Documentation

Variable Documentation