tlx
Loading...
Searching...
No Matches
PS5SmallsortJob< Context, StringPtr, BktSizeType > Class Template Reference

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

#include <parallel_sample_sort.hpp>

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

Classes

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

Public Types

typedef Context::key_type key_type
 
typedef StringPtr::StringSet StringSet
 
typedef BktSizeType bktsize_type
 

Public Member Functions

 PS5SmallsortJob (Context &ctx, PS5SortStep *pstep, const StringPtr &strptr, size_t depth)
 
 ~PS5SmallsortJob ()
 
void run ()
 
void sort_sample_sort (const StringPtr &strptr, size_t depth)
 
void sample_sort_free_work ()
 
void sort_mkqs_cache (const StringPtr &strptr, size_t depth)
 
void mkqs_free_work ()
 
void substep_all_done () final
 Pure virtual function called by substep when all substeps are done.
 
- Public Member Functions inherited from PS5SortStep
void substep_notify_done ()
 Notify superstep that the currently substep is done.
 

Static Public Member Functions

static int cmp (const key_type &a, const key_type &b)
 Stack of Recursive MKQS Steps.
 
template<typename Type >
static size_t med3 (Type *A, size_t i, size_t j, size_t k)
 
static void insertion_sort_cache_block (const StringPtr &strptr, key_type *cache)
 Insertion sort the strings only based on the cached characters.
 
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.
 

Public Attributes

Context & ctx_
 
PS5SortSteppstep_
 parent sort step
 
StringPtr strptr_
 
size_t depth_
 
MultiTimer mtimer_
 
simple_vector< std::uint8_t > bktcache_
 
size_t bktcache_size_
 
size_t ss_front_
 
std::vector< SeqSampleSortStepss_stack_
 
size_t ms_front_
 
std::vector< MKQSStepms_stack_
 

Additional Inherited Members

- Protected Member Functions inherited from PS5SortStep
 PS5SortStep ()
 
virtual ~PS5SortStep ()
 
void substep_add ()
 Register new substep.
 

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 292 of file parallel_sample_sort.hpp.

Member Typedef Documentation

◆ bktsize_type

template<typename Context , typename StringPtr , typename BktSizeType >
typedef BktSizeType bktsize_type

Definition at line 306 of file parallel_sample_sort.hpp.

◆ key_type

template<typename Context , typename StringPtr , typename BktSizeType >
typedef Context::key_type key_type

Definition at line 304 of file parallel_sample_sort.hpp.

◆ StringSet

template<typename Context , typename StringPtr , typename BktSizeType >
typedef StringPtr::StringSet StringSet

Definition at line 305 of file parallel_sample_sort.hpp.

Constructor & Destructor Documentation

◆ PS5SmallsortJob()

template<typename Context , typename StringPtr , typename BktSizeType >
PS5SmallsortJob ( Context &  ctx,
PS5SortStep pstep,
const StringPtr strptr,
size_t  depth 
)
inline

Definition at line 308 of file parallel_sample_sort.hpp.

◆ ~PS5SmallsortJob()

template<typename Context , typename StringPtr , typename BktSizeType >
~PS5SmallsortJob ( )
inline

Definition at line 316 of file parallel_sample_sort.hpp.

Member Function Documentation

◆ cmp()

template<typename Context , typename StringPtr , typename BktSizeType >
static int cmp ( const key_type a,
const key_type b 
)
inlinestatic

Stack of Recursive MKQS Steps.

Definition at line 648 of file parallel_sample_sort.hpp.

◆ insertion_sort_cache()

template<typename Context , typename StringPtr , typename BktSizeType >
template<bool CacheDirty>
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 692 of file parallel_sample_sort.hpp.

◆ insertion_sort_cache_block()

template<typename Context , typename StringPtr , typename BktSizeType >
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 671 of file parallel_sample_sort.hpp.

◆ med3()

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

Definition at line 654 of file parallel_sample_sort.hpp.

◆ mkqs_free_work()

template<typename Context , typename StringPtr , typename BktSizeType >
void mkqs_free_work ( )
inline

Definition at line 1017 of file parallel_sample_sort.hpp.

◆ run()

template<typename Context , typename StringPtr , typename BktSizeType >
void run ( )
inline

Definition at line 324 of file parallel_sample_sort.hpp.

◆ sample_sort_free_work()

template<typename Context , typename StringPtr , typename BktSizeType >
void sample_sort_free_work ( )
inline

Definition at line 564 of file parallel_sample_sort.hpp.

◆ sort_mkqs_cache()

template<typename Context , typename StringPtr , typename BktSizeType >
void sort_mkqs_cache ( const StringPtr strptr,
size_t  depth 
)
inline

Definition at line 899 of file parallel_sample_sort.hpp.

◆ sort_sample_sort()

template<typename Context , typename StringPtr , typename BktSizeType >
void sort_sample_sort ( const StringPtr strptr,
size_t  depth 
)
inline

Definition at line 445 of file parallel_sample_sort.hpp.

◆ substep_all_done()

template<typename Context , typename StringPtr , typename BktSizeType >
void substep_all_done ( )
inlinefinalvirtual

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

Implements PS5SortStep.

Definition at line 1071 of file parallel_sample_sort.hpp.

Member Data Documentation

◆ bktcache_

template<typename Context , typename StringPtr , typename BktSizeType >
simple_vector<std::uint8_t> bktcache_

Definition at line 321 of file parallel_sample_sort.hpp.

◆ bktcache_size_

template<typename Context , typename StringPtr , typename BktSizeType >
size_t bktcache_size_

Definition at line 322 of file parallel_sample_sort.hpp.

◆ ctx_

template<typename Context , typename StringPtr , typename BktSizeType >
Context& ctx_

Definition at line 295 of file parallel_sample_sort.hpp.

◆ depth_

template<typename Context , typename StringPtr , typename BktSizeType >
size_t depth_

Definition at line 301 of file parallel_sample_sort.hpp.

◆ ms_front_

template<typename Context , typename StringPtr , typename BktSizeType >
size_t ms_front_

Definition at line 896 of file parallel_sample_sort.hpp.

◆ ms_stack_

template<typename Context , typename StringPtr , typename BktSizeType >
std::vector<MKQSStep> ms_stack_

Definition at line 897 of file parallel_sample_sort.hpp.

◆ mtimer_

template<typename Context , typename StringPtr , typename BktSizeType >
MultiTimer mtimer_

Definition at line 302 of file parallel_sample_sort.hpp.

◆ pstep_

template<typename Context , typename StringPtr , typename BktSizeType >
PS5SortStep* pstep_

parent sort step

Definition at line 298 of file parallel_sample_sort.hpp.

◆ ss_front_

template<typename Context , typename StringPtr , typename BktSizeType >
size_t ss_front_

Definition at line 442 of file parallel_sample_sort.hpp.

◆ ss_stack_

template<typename Context , typename StringPtr , typename BktSizeType >
std::vector<SeqSampleSortStep> ss_stack_

Definition at line 443 of file parallel_sample_sort.hpp.

◆ strptr_

template<typename Context , typename StringPtr , typename BktSizeType >
StringPtr strptr_

Definition at line 300 of file parallel_sample_sort.hpp.


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