Detailed Description

template<typename Context, typename StringPtr, typename BktSizeType>
class tlx::sort_strings_detail::PS5SmallsortJob< Context, StringPtr, BktSizeType >

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

Definition at line 291 of file parallel_sample_sort.hpp.

Inheritance diagram for PS5SmallsortJob< Context, StringPtr, BktSizeType >:

Collaboration diagram for PS5SmallsortJob< Context, StringPtr, BktSizeType >:

#include <parallel_sample_sort.hpp>

Classes
class	MKQSStep

class	SeqSampleSortStep
	Stack of Recursive Sample Sort Steps. More...

Public Types
typedef BktSizeType	bktsize_type

typedef Context::key_type	key_type

typedef StringPtr::StringSet	StringSet

Public Member Functions
	PS5SmallsortJob (Context &ctx, PS5SortStep *pstep, const StringPtr &strptr, size_t depth)

	~PS5SmallsortJob ()

void	mkqs_free_work ()

void	run ()

void	sample_sort_free_work ()

void	sort_mkqs_cache (const StringPtr &strptr, size_t depth)

void	sort_sample_sort (const StringPtr &strptr, size_t depth)

void	substep_all_done () final
	Pure virtual function called by substep when all substeps are done. More...

Public Member Functions inherited from PS5SortStep
void	substep_notify_done ()
	Notify superstep that the currently substep is done. More...

Static Public Member Functions
static int	cmp (const key_type &a, const key_type &b)
	Stack of Recursive MKQS Steps. More...

template<bool CacheDirty>
static void	insertion_sort_cache (const StringPtr &_strptr, key_type *cache, size_t depth)
	Insertion sort, but use cached characters if possible. More...

static void	insertion_sort_cache_block (const StringPtr &strptr, key_type *cache)
	Insertion sort the strings only based on the cached characters. More...

template<typename Type >
static size_t	med3 (Type *A, size_t i, size_t j, size_t k)

Public Attributes
simple_vector< uint8_t >	bktcache_

size_t	bktcache_size_ = 0

Context &	ctx_

size_t	depth_

size_t	ms_front_ = 0

std::vector< MKQSStep >	ms_stack_

MultiTimer	mtimer_

PS5SortStep *	pstep_
	parent sort step More...

size_t	ss_front_ = 0

std::vector< SeqSampleSortStep >	ss_stack_

StringPtr	strptr_

Additional Inherited Members
Protected Member Functions inherited from PS5SortStep
	PS5SortStep ()

virtual	~PS5SortStep ()

void	substep_add ()
	Register new substep. More...

Member Typedef Documentation

◆ bktsize_type

typedef BktSizeType bktsize_type

Definition at line 305 of file parallel_sample_sort.hpp.

◆ key_type

typedef Context::key_type key_type

Definition at line 303 of file parallel_sample_sort.hpp.

◆ StringSet

typedef StringPtr::StringSet StringSet

Definition at line 304 of file parallel_sample_sort.hpp.

Constructor & Destructor Documentation

◆ PS5SmallsortJob()

PS5SmallsortJob	(	Context &	ctx,
		PS5SortStep *	pstep,
		const StringPtr &	strptr,
		size_t	depth
	)

inline

Definition at line 307 of file parallel_sample_sort.hpp.

References StringPtr< StringSet_ >::size(), and TLX_LOGC.

◆ ~PS5SmallsortJob()

~PS5SmallsortJob ( )

inline

Definition at line 315 of file parallel_sample_sort.hpp.

References MultiTimer::stop().

Member Function Documentation

◆ cmp()

static int cmp	(	const key_type &	a,
		const key_type &	b
	)

inlinestatic

Stack of Recursive MKQS Steps.

Definition at line 647 of file parallel_sample_sort.hpp.

◆ insertion_sort_cache()

static void insertion_sort_cache	(	const StringPtr &	_strptr,
		key_type *	cache,
		size_t	depth
	)

inlinestatic

Insertion sort, but use cached characters if possible.

Definition at line 691 of file parallel_sample_sort.hpp.

References StringPtr< StringSet_ >::fill_lcp(), tlx::sort_strings_detail::insertion_sort(), tlx::sort_strings_detail::lcpKeyDepth(), tlx::sort_strings_detail::lcpKeyType(), StringPtr< StringSet_ >::set_lcp(), StringPtr< StringSet_ >::size(), StringPtr< StringSet_ >::sub(), and StringPtr< StringSet_ >::with_lcp.

◆ insertion_sort_cache_block()

static void insertion_sort_cache_block	(	const StringPtr &	strptr,
		key_type *	cache
	)

inlinestatic

Insertion sort the strings only based on the cached characters.

Definition at line 670 of file parallel_sample_sort.hpp.

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

◆ med3()

static size_t med3	(	Type *	A,
		size_t	i,
		size_t	j,
		size_t	k
	)

inlinestatic

Definition at line 653 of file parallel_sample_sort.hpp.

◆ mkqs_free_work()

void mkqs_free_work ( )

inline

Definition at line 1016 of file parallel_sample_sort.hpp.

◆ run()

void run ( )

inline

Definition at line 323 of file parallel_sample_sort.hpp.

References SimpleVector< ValueType, Mode >::resize(), StringPtr< StringSet_ >::size(), MultiTimer::start(), and TLX_LOGC.

◆ sample_sort_free_work()

void sample_sort_free_work ( )

inline

Definition at line 563 of file parallel_sample_sort.hpp.

References StringPtr< StringSet_ >::fill_lcp(), tlx::sort_strings_detail::lcpKeyDepth(), TLX_LOGC, and StringPtr< StringSet_ >::with_lcp.

◆ sort_mkqs_cache()

void sort_mkqs_cache	(	const StringPtr &	strptr,
		size_t	depth
	)

inline

Definition at line 898 of file parallel_sample_sort.hpp.

◆ sort_sample_sort()

void sort_sample_sort	(	const StringPtr &	strptr,
		size_t	depth
	)

inline

Definition at line 444 of file parallel_sample_sort.hpp.

References SimpleVector< ValueType, Mode >::data(), StringPtr< StringSet_ >::fill_lcp(), tlx::sort_strings_detail::lcpKeyDepth(), TLX_LOGC, and StringPtr< StringSet_ >::with_lcp.

◆ substep_all_done()

void substep_all_done ( )

inlinefinalvirtual

Pure virtual function called by substep when all substeps are done.

Implements PS5SortStep.

Definition at line 1070 of file parallel_sample_sort.hpp.

References PS5SortStep::substep_notify_done(), and TLX_LOGC.

Member Data Documentation

◆ bktcache_

simple_vector<uint8_t> bktcache_

Definition at line 320 of file parallel_sample_sort.hpp.

◆ bktcache_size_

size_t bktcache_size_ = 0

Definition at line 321 of file parallel_sample_sort.hpp.

◆ ctx_

Context& ctx_

Definition at line 294 of file parallel_sample_sort.hpp.

◆ depth_

size_t depth_

Definition at line 300 of file parallel_sample_sort.hpp.

◆ ms_front_

size_t ms_front_ = 0

Definition at line 895 of file parallel_sample_sort.hpp.

◆ ms_stack_

std::vector<MKQSStep> ms_stack_

Definition at line 896 of file parallel_sample_sort.hpp.

◆ mtimer_

MultiTimer mtimer_

Definition at line 301 of file parallel_sample_sort.hpp.

◆ pstep_

PS5SortStep* pstep_

parent sort step

Definition at line 297 of file parallel_sample_sort.hpp.

◆ ss_front_

size_t ss_front_ = 0

Definition at line 441 of file parallel_sample_sort.hpp.

◆ ss_stack_

std::vector<SeqSampleSortStep> ss_stack_

Definition at line 442 of file parallel_sample_sort.hpp.

◆ strptr_

StringPtr strptr_

Definition at line 299 of file parallel_sample_sort.hpp.

The documentation for this class was generated from the following file:

extlib/tlx/tlx/sort/strings/parallel_sample_sort.hpp

Detailed Description

template<typename Context, typename StringPtr, typename BktSizeType> class tlx::sort_strings_detail::PS5SmallsortJob< Context, StringPtr, BktSizeType >

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Additional Inherited Members

Member Typedef Documentation

◆ bktsize_type

◆ key_type

◆ StringSet

Constructor & Destructor Documentation

◆ PS5SmallsortJob()

◆ ~PS5SmallsortJob()

Member Function Documentation

◆ cmp()

◆ insertion_sort_cache()

◆ insertion_sort_cache_block()

◆ med3()

◆ mkqs_free_work()

◆ run()

◆ sample_sort_free_work()

◆ sort_mkqs_cache()

◆ sort_sample_sort()

◆ substep_all_done()

Member Data Documentation

◆ bktcache_

◆ bktcache_size_

◆ ctx_

◆ depth_

◆ ms_front_

◆ ms_stack_

◆ mtimer_

◆ pstep_

◆ ss_front_

◆ ss_stack_

◆ strptr_

template<typename Context, typename StringPtr, typename BktSizeType>
class tlx::sort_strings_detail::PS5SmallsortJob< Context, StringPtr, BktSizeType >