Thrill  0.1
Public Member Functions | Static Public Attributes | Private Attributes | List of all members
SSClassifyTreeCalcUnrollInterleave< key_type, TreeBits, Rollout > Class Template Reference

Detailed Description

template<typename key_type, size_t TreeBits, unsigned Rollout = 4>
class tlx::sort_strings_detail::SSClassifyTreeCalcUnrollInterleave< key_type, TreeBits, Rollout >

Sample Sort Classification Tree Unrolled, Interleaved, and with Perfect Tree Index Calculations

Definition at line 576 of file sample_sort_tools.hpp.

#include <sample_sort_tools.hpp>

Public Member Functions

void build (key_type *samples, size_t samplesize, unsigned char *splitter_lcp)
 build tree and splitter array from sample More...
 
template<typename StringSet >
void classify (const StringSet &strset, typename StringSet::Iterator begin, typename StringSet::Iterator end, uint16_t *bktout, size_t depth) const
 classify all strings in area by walking tree and saving bucket id More...
 
unsigned int find_bkt (const key_type &key) const
 binary search on splitter array for bucket number More...
 
void find_bkt_unroll (const key_type key[Rollout], uint16_t obkt[Rollout]) const
 
key_type get_splitter (unsigned int i) const
 return a splitter More...
 

Static Public Attributes

static const size_t num_splitters = (1 << treebits) - 1
 
static const size_t treebits = TreeBits
 

Private Attributes

key_type splitter_tree_ [num_splitters+1]
 

Member Function Documentation

◆ build()

void build ( key_type *  samples,
size_t  samplesize,
unsigned char *  splitter_lcp 
)
inline

build tree and splitter array from sample

Definition at line 583 of file sample_sort_tools.hpp.

◆ classify()

void classify ( const StringSet &  strset,
typename StringSet::Iterator  begin,
typename StringSet::Iterator  end,
uint16_t *  bktout,
size_t  depth 
) const
inline

classify all strings in area by walking tree and saving bucket id

Definition at line 687 of file sample_sort_tools.hpp.

◆ find_bkt()

unsigned int find_bkt ( const key_type &  key) const
inline

binary search on splitter array for bucket number

Definition at line 590 of file sample_sort_tools.hpp.

◆ find_bkt_unroll()

void find_bkt_unroll ( const key_type  key[Rollout],
uint16_t  obkt[Rollout] 
) const
inline

search in splitter tree for bucket number, unrolled for Rollout keys at once.

Definition at line 621 of file sample_sort_tools.hpp.

References TLX_CLASSIFY_TREE_STEP.

◆ get_splitter()

key_type get_splitter ( unsigned int  i) const
inline

return a splitter

Definition at line 712 of file sample_sort_tools.hpp.

References PerfectTreeCalculations< TreeBits >::pre_to_levelorder().

Member Data Documentation

◆ num_splitters

const size_t num_splitters = (1 << treebits) - 1
static

Definition at line 580 of file sample_sort_tools.hpp.

◆ splitter_tree_

key_type splitter_tree_[num_splitters+1]
private

Definition at line 718 of file sample_sort_tools.hpp.

◆ treebits

const size_t treebits = TreeBits
static

Definition at line 579 of file sample_sort_tools.hpp.

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