16#ifndef TLX_SORT_STRINGS_PARALLEL_SAMPLE_SORT_HEADER
17#define TLX_SORT_STRINGS_PARALLEL_SAMPLE_SORT_HEADER
42namespace sort_strings_detail {
94template <
typename Parameters>
124 template <
typename StringPtr>
129 size_t threshold = this->smallsort_threshold;
130 if (this->enable_rest_size) {
140 if (this->enable_rest_size)
148template <
typename KeyType>
149static inline unsigned char
152 return clz(a ^ b) / 8;
155template <
typename KeyType>
156static inline unsigned char
159 return sizeof(KeyType) - (
ctz(a) / 8);
163template <
typename KeyType>
164static inline unsigned char
166 return static_cast<unsigned char>(a >> (8 * (
sizeof(KeyType) - 1 - d)));
205template <
size_t bktnum,
typename Context,
typename Classify,
206 typename StringPtr,
typename BktSizeType>
209 const BktSizeType* bkt) {
210 assert(!strptr.flipped());
213 typedef typename Context::key_type key_type;
216 key_type prevkey = 0;
227 if (bkt[b] != bkt[b + 1]) {
228 prevkey = classifier.get_splitter(b / 2);
235 if (bkt[b] != bkt[b + 1]) {
245 if (b < bktnum && b % 2 == 0)
goto even_bucket;
251 if (bkt[b] != bkt[b + 1]) {
252 key_type thiskey = classifier.get_splitter(b / 2);
256 strptr.
set_lcp(bkt[b], depth + rlcp);
260 <<
"LCP at odd-bucket " << b
261 <<
" [" << bkt[b] <<
"," << bkt[b + 1] <<
")"
262 <<
" is " << depth + rlcp;
270 if (bkt[b] != bkt[b + 1]) {
274 strptr.
set_lcp(bkt[b], depth + rlcp);
278 <<
"LCP at even-bucket " << b
279 <<
" [" << bkt[b] <<
"," << bkt[b + 1] <<
")"
280 <<
" is " << depth + rlcp;
291template <
typename Context,
typename StringPtr,
typename BktSizeType>
312 <<
"enqueue depth=" <<
depth_
330 <<
"Process PS5SmallsortJob " <<
this <<
" of size " << n;
335 if (ctx_.enable_sequential_sample_sort && n >=
ctx_.smallsort_threshold)
337 bktcache_.resize(n *
sizeof(std::uint16_t));
372 std::uint16_t* bktcache)
378 const size_t oversample_factor = 2;
379 const size_t sample_size = oversample_factor *
num_splitters;
385 std::minstd_rand rng(
reinterpret_cast<uintptr_t
>(samples.
data()));
387 for (
size_t i = 0; i < sample_size; ++i)
390 std::sort(samples.
begin(), samples.
end());
397 strset, strset.begin(), strset.end(), bktcache,
depth_);
404 for (
size_t si = 0; si < n; ++si)
405 ++bktsize[bktcache[si]];
410 for (
unsigned int i = 1; i <
bktnum; ++i) {
411 bkt[i] =
bkt[i - 1] + bktsize[i];
421 typename StringSet::Iterator sbegin = sorted.begin();
423 for (
typename StringSet::Iterator str = strB.begin();
424 str != strB.end(); ++str, ++bktcache)
425 *(sbegin + --
bkt[*bktcache]) = std::move(*str);
435 TLX_LOGC(ctx.debug_lcp) <<
"Calculate LCP after sample sort step";
451 std::uint16_t* bktcache =
reinterpret_cast<std::uint16_t*
>(
bktcache_.data());
463 if (i < Step::bktnum)
465 size_t bktsize = s.bkt[i + 1] - s.bkt[i];
467 StringPtr sp = s.strptr_.flip(s.bkt[i], bktsize);
475 else if (bktsize <
ctx_.smallsort_threshold)
477 assert(i / 2 <= Step::num_splitters);
478 if (i == Step::bktnum - 1)
480 <<
"Recurse[" << s.depth_ <<
"]: > bkt "
481 << i <<
" size " << bktsize <<
" no lcp";
484 <<
"Recurse[" << s.depth_ <<
"]: < bkt "
485 << i <<
" size " << bktsize <<
" lcp "
486 << int(s.splitter_lcp[i / 2] & 0x7F);
490 sp, s.depth_ + (s.splitter_lcp[i / 2] & 0x7F));
494 if (i == Step::bktnum - 1)
496 <<
"Recurse[" << s.depth_ <<
"]: > bkt "
497 << i <<
" size " << bktsize <<
" no lcp";
500 <<
"Recurse[" << s.depth_ <<
"]: < bkt "
501 << i <<
" size " << bktsize <<
" lcp "
502 << int(s.splitter_lcp[i / 2] & 0x7F);
505 ctx_, sp, s.depth_ + (s.splitter_lcp[i / 2] & 0x7F), bktcache);
514 else if (s.splitter_lcp[i / 2] & 0x80) {
517 <<
"Recurse[" << s.depth_ <<
"]: = bkt "
518 << i <<
" size " << bktsize <<
" is done!";
523 s.depth_ +
lcpKeyDepth(s.classifier.get_splitter(i / 2)));
525 ctx_.donesize(bktsize);
527 else if (bktsize <
ctx_.smallsort_threshold)
530 <<
"Recurse[" << s.depth_ <<
"]: = bkt "
531 << i <<
" size " << bktsize <<
" lcp keydepth!";
539 <<
"Recurse[" << s.depth_ <<
"]: = bkt "
540 << i <<
" size " << bktsize <<
" lcp keydepth!";
558 if (
ctx_.enable_work_sharing &&
ctx_.threads_.has_idle()) {
574 <<
"Freeing top level of PS5SmallsortJob's sample_sort stack";
579 while (s.idx_ < Step::bktnum)
583 size_t bktsize = s.bkt[i + 1] - s.bkt[i];
585 StringPtr sp = s.strptr_.flip(s.bkt[i], bktsize);
595 if (i == Step::bktnum - 1)
597 <<
"Recurse[" << s.depth_ <<
"]: > bkt "
598 << i <<
" size " << bktsize <<
" no lcp";
601 <<
"Recurse[" << s.depth_ <<
"]: < bkt "
602 << i <<
" size " << bktsize <<
" lcp "
603 << int(s.splitter_lcp[i / 2] & 0x7F);
606 ctx_.enqueue(
this, sp,
607 s.depth_ + (s.splitter_lcp[i / 2] & 0x7F));
616 else if (s.splitter_lcp[i / 2] & 0x80) {
619 <<
"Recurse[" << s.depth_ <<
"]: = bkt "
620 << i <<
" size " << bktsize <<
" is done!";
625 s.classifier.get_splitter(i / 2)));
627 ctx_.donesize(bktsize);
632 <<
"Recurse[" << s.depth_ <<
"]: = bkt "
633 << i <<
" size " << bktsize <<
" lcp keydepth!";
636 ctx_.enqueue(
this, sp, s.depth_ +
sizeof(
key_type));
649 return (a > b) ? 1 : (a < b) ? -1 : 0;
652 template <
typename Type>
654 med3(Type* A,
size_t i,
size_t j,
size_t k) {
655 if (A[i] == A[j])
return i;
656 if (A[k] == A[i] || A[k] == A[j])
return k;
658 if (A[j] < A[k])
return j;
659 if (A[i] < A[k])
return k;
663 if (A[j] > A[k])
return j;
664 if (A[i] < A[k])
return i;
673 size_t n = strptr.
size();
675 for (pi = 1; --n > 0; ++pi) {
676 typename StringSet::String tmps = std::move(strings.at(pi));
678 for (pj = pi; pj > 0; --pj) {
679 if (cache[pj - 1] <= tmpc)
681 strings.at(pj) = std::move(strings.at(pj - 1));
682 cache[pj] = cache[pj - 1];
684 strings.at(pj) = std::move(tmps);
690 template <
bool CacheDirty>
695 if (strptr.
size() <= 1)
return;
701 size_t start = 0, bktsize = 1;
702 for (
size_t i = 0; i < strptr.
size() - 1; ++i) {
704 if (cache[i] == cache[i + 1]) {
709 if (start != 0 && strptr.
with_lcp) {
710 int rlcp =
lcpKeyType(cache[start - 1], cache[start]);
711 strptr.
set_lcp(start, depth + rlcp);
716 if (cache[start] & 0xFF) {
719 strptr.
sub(start, bktsize), depth +
sizeof(
key_type),
731 if (start != 0 && strptr.
with_lcp) {
732 int rlcp =
lcpKeyType(cache[start - 1], cache[start]);
733 strptr.
set_lcp(start, depth + rlcp);
737 if (cache[start] & 0xFF) {
740 strptr.
sub(start, bktsize), depth +
sizeof(
key_type),
762 key_type* cache,
size_t depth,
bool CacheDirty)
769 typename StringSet::Iterator it = strset.begin();
770 for (
size_t i = 0; i < n; ++i, ++it) {
778 med3(
cache_, n / 2 - n / 8, n / 2, n / 2 + n / 8),
779 med3(
cache_, n - 1 - n / 4, n - 1 - n / 8, n - 3));
781 std::swap(strset.at(0), strset.at(p));
786 key_type max_lt = 0, min_gt = std::numeric_limits<key_type>::max();
790 size_t leq = 1, llt = 1, rgt = n - 1, req = n - 1;
795 int r =
cmp(cache[llt], pivot);
797 min_gt = std::min(min_gt, cache[llt]);
801 std::swap(strset.at(leq), strset.at(llt));
802 std::swap(cache[leq], cache[llt]);
806 max_lt = std::max(max_lt, cache[llt]);
812 int r =
cmp(cache[rgt], pivot);
814 max_lt = std::max(max_lt, cache[rgt]);
818 std::swap(strset.at(req), strset.at(rgt));
819 std::swap(cache[req], cache[rgt]);
823 min_gt = std::min(min_gt, cache[rgt]);
829 std::swap(strset.at(llt), strset.at(rgt));
830 std::swap(cache[llt], cache[rgt]);
835 size_t num_leq = leq, num_req = n - 1 - req;
843 const size_t size1 = std::min(num_leq,
num_lt_);
844 std::swap_ranges(strset.begin(), strset.begin() + size1,
845 strset.begin() + llt - size1);
846 std::swap_ranges(cache, cache + size1, cache + llt - size1);
849 const size_t size2 = std::min(num_req,
num_gt_);
850 std::swap_ranges(strset.begin() + llt, strset.begin() + llt + size2,
851 strset.begin() + n - size2);
852 std::swap_ranges(cache + llt, cache + llt + size2,
860 assert(max_lt == *std::max_element(
872 assert(min_gt == *std::min_element(
880 ++ctx.base_sort_steps;
902 if (!
ctx_.enable_sequential_mkqs ||
903 strptr.
size() <
ctx_.inssort_threshold) {
905 <<
"insertion_sort() size "
906 << strptr.
size() <<
" depth " << depth;
915 <<
"sort_mkqs_cache() size " << strptr.
size() <<
" depth " << depth;
956 else if (ms.
idx_ == 2) {
980 else if (ms.
idx_ == 3) {
1011 if (
ctx_.enable_work_sharing &&
ctx_.threads_.has_idle()) {
1020 for (
unsigned int fl = 0; fl < 8; ++fl)
1027 <<
"Freeing top level of PS5SmallsortJob's mkqs stack - size "
1073 <<
"SmallSort[" <<
depth_ <<
"] "
1074 <<
"all substeps done -> LCP calculation";
1096template <
typename Context,
typename StringPtr>
1123 static const size_t treebits_ = Context::Classify::treebits;
1151 <<
"enqueue depth=" <<
depth_
1155 <<
" flip=" <<
strptr_.flipped();
1157 ctx.threads_.enqueue([
this]() {
sample(); });
1158 ++ctx.para_ss_steps;
1168 TLX_LOGC(
ctx_.debug_jobs) <<
"Process SampleJob @ " <<
this;
1170 const size_t oversample_factor = 2;
1174 size_t n = strset.size();
1178 std::minstd_rand rng(
reinterpret_cast<uintptr_t
>(samples.
data()));
1180 for (
size_t i = 0; i < sample_size; ++i)
1183 std::sort(samples.
begin(), samples.
end());
1189 for (
unsigned int p = 0; p <
parts_; ++p) {
1190 ctx_.threads_.enqueue([
this, p]() {
count(p); });
1199 TLX_LOGC(
ctx_.debug_jobs) <<
"Process CountJob " << p <<
" @ " <<
this;
1205 if (strE < strB) strE = strB;
1208 std::uint16_t* bktcache =
bktcache_[p].data();
1212 size_t* bkt =
bkt_[p].data();
1213 memset(bkt, 0,
bktnum_ *
sizeof(
size_t));
1215 for (std::uint16_t* bc = bktcache; bc != bktcache + (strE - strB); ++bc)
1224 TLX_LOGC(
ctx_.debug_jobs) <<
"Finishing CountJob " <<
this <<
" with prefixsum";
1227 if (
ctx_.use_only_first_sortstep)
1232 for (
unsigned int i = 0; i <
bktnum_; ++i) {
1233 for (
unsigned int p = 0; p <
parts_; ++p) {
1241 for (
unsigned int p = 0; p <
parts_; ++p) {
1251 TLX_LOGC(
ctx_.debug_jobs) <<
"Process DistributeJob " << p <<
" @ " <<
this;
1257 if (strE < strB) strE = strB;
1261 typename StringSet::Iterator sbegin = sorted.begin();
1263 std::uint16_t* bktcache =
bktcache_[p].data();
1264 size_t* bkt =
bkt_[p].data();
1266 for (
StrIterator str = strB; str != strE; ++str, ++bktcache)
1267 *(sbegin + --bkt[*bktcache]) = std::move(*str);
1280 <<
"Finishing DistributeJob " <<
this <<
" with enqueuing subjobs";
1282 size_t* bkt =
bkt_[0].data();
1286 assert(bkt[0] == 0);
1296 size_t bktsize = bkt[i + 1] - bkt[i];
1300 else if (bktsize == 1) {
1301 strptr_.flip(bkt[i], 1).copy_back();
1307 <<
"Recurse[" <<
depth_ <<
"]: < bkt " << bkt[i]
1308 <<
" size " << bktsize <<
" lcp "
1311 ctx_.enqueue(
this,
strptr_.flip(bkt[i], bktsize),
1316 bktsize = bkt[i + 1] - bkt[i];
1320 else if (bktsize == 1) {
1321 strptr_.flip(bkt[i], 1).copy_back();
1329 <<
"Recurse[" <<
depth_ <<
"]: = bkt " << bkt[i]
1330 <<
" size " << bktsize <<
" is done!";
1334 ctx_.donesize(bktsize);
1338 <<
"Recurse[" <<
depth_ <<
"]: = bkt " << bkt[i]
1339 <<
" size " << bktsize <<
" lcp keydepth!";
1341 ctx_.enqueue(
this,
strptr_.flip(bkt[i], bktsize),
1348 size_t bktsize = bkt[i + 1] - bkt[i];
1353 else if (bktsize == 1) {
1354 strptr_.flip(bkt[i], 1).copy_back();
1359 <<
"Recurse[" <<
depth_ <<
"]: > bkt " << bkt[i]
1360 <<
" size " << bktsize <<
" no lcp";
1378 <<
"pSampleSortStep[" <<
depth_ <<
"]: all substeps done.";
1393template <
typename Parameters>
1394template <
typename StringPtr>
1397 if (this->enable_parallel_sample_sort &&
1398 (strptr.
size() > sequential_threshold() ||
1399 this->use_only_first_sortstep)) {
1403 if (strptr.
size() < (1LLU << 32)) {
1405 *
this, pstep, strptr, depth);
1406 threads_.enqueue([j]() { j->run(); });
1410 *
this, pstep, strptr, depth);
1411 threads_.enqueue([j]() { j->run(); });
1420template <
typename PS5Parameters,
typename StringPtr>
1424 Context ctx(std::thread::hardware_concurrency());
1425 ctx.total_size = strptr.
size();
1426 ctx.rest_size = strptr.
size();
1427 ctx.num_threads = ctx.threads_.size();
1430 timer.
start(
"sort");
1432 ctx.enqueue(
nullptr, strptr, depth);
1433 ctx.threads_.loop_until_empty();
1437 assert(!ctx.enable_rest_size || ctx.rest_size == 0);
1443 <<
" sizeof(key_type)=" <<
sizeof(
typename PS5Parameters::key_type)
1444 <<
" splitter_treebits=" <<
size_t(BigSortStep::treebits_)
1445 <<
" num_splitters=" << size_t(BigSortStep::num_splitters_)
1446 <<
" num_threads=" << ctx.num_threads
1447 <<
" enable_work_sharing=" << size_t(ctx.enable_work_sharing)
1448 <<
" use_restsize=" << size_t(ctx.enable_rest_size)
1449 <<
" tm_para_ss=" << ctx.mtimer.get(
"para_ss")
1450 <<
" tm_seq_ss=" << ctx.mtimer.get(
"sequ_ss")
1451 <<
" tm_mkqs=" << ctx.mtimer.get(
"mkqs")
1452 <<
" tm_inssort=" << ctx.mtimer.get(
"inssort")
1453 <<
" tm_total=" << ctx.mtimer.total()
1455 << (ctx.num_threads * timer.
total()) - ctx.mtimer.total()
1456 <<
" steps_para_sample_sort=" << ctx.para_ss_steps
1457 <<
" steps_seq_sample_sort=" << ctx.sequ_ss_steps
1458 <<
" steps_base_sort=" << ctx.base_sort_steps;
1463template <
typename PS5Parameters,
typename StringPtr>
1466 const StringPtr& strptr,
size_t depth,
size_t memory = 0) {
1470 const StringSet& strset = strptr.
active();
1473 typedef typename StringSet::Container Container;
1476 Container shadow = strset.allocate(strset.size());
1481 StringSet::deallocate(shadow);
1486template <
typename PS5Parameters,
typename StringPtr>
1489 const StringPtr& strptr,
size_t depth,
size_t memory = 0) {
1493 typedef typename StringPtr::LcpType LcpType;
1494 const StringSet& strset = strptr.
active();
1497 typedef typename StringSet::Container Container;
1500 Container shadow = strset.allocate(strset.size());
1505 StringSet::deallocate(shadow);
1510template <
typename StringPtr>
1512 const StringPtr& strptr,
size_t depth,
size_t memory) {
1514 strptr, depth, memory);
MultiTimer can be used to measure time usage of different phases in a program or algorithm.
void start(const char *timer)
start new timer phase, stop the currently running one.
void stop()
stop the currently running timer.
const char * running() const
return name of currently running timer.
double total() const
return total duration of all timers.
RAII Scoped MultiTimer switcher: switches the timer of a MultiTimer on construction and back to old o...
Independent RAII Scoped MultiTimer: contains a MultiTimer which is started with the given timer,...
Simpler non-growing vector without initialization.
iterator data() noexcept
return iterator to beginning of vector
iterator begin() noexcept
return mutable iterator to first element
iterator end() noexcept
return mutable iterator beyond last element
ThreadPool starts a fixed number p of std::threads which process Jobs that are enqueued into a concur...
PS5BigSortStep Out-of-Place Parallel Sample Sort with Separate Jobs.
void count(unsigned int p)
simple_vector< simple_vector< size_t > > bkt_
individual bucket array of threads, keep bkt[0] for DistributeJob
simple_vector< simple_vector< std::uint16_t > > bktcache_
bucket ids cache, created by classifier and later counted
PS5SortStep * pstep_
parent sort step for notification
std::atomic< size_t > pwork_
number of threads still working
size_t psize_
size of all parts except the last
StringPtr strptr_
string pointers, size, and current sorting depth
Context::Classify classifier_
classifier instance and variables (contains splitter tree
void substep_all_done() final
Pure virtual function called by substep when all substeps are done.
void distribute(unsigned int p)
StringSet::Iterator StrIterator
static const size_t bktnum_
static const size_t num_splitters_
PS5BigSortStep(Context &ctx, PS5SortStep *pstep, const StringPtr &strptr, size_t depth)
unsigned char splitter_lcp_[num_splitters_+1]
LCPs of splitters, needed for recursive calls.
static const size_t treebits_
Context::key_type key_type
void distribute_finished()
size_t parts_
number of parts into which the strings were split
StringPtr::StringSet StringSet
virtual ~PS5BigSortStep()
Parallel Super Scalar String Sample Sort Context.
void enqueue(PS5SortStep *sstep, const StringPtr &strptr, size_t depth)
enqueue a new job in the thread pool
void donesize(size_t n)
decrement number of unordered strings
std::atomic< size_t > rest_size
number of remaining strings to sort
PS5Context(size_t _thread_num)
context constructor
std::atomic< size_t > base_sort_steps
size_t sequential_threshold()
return sequential sorting threshold
ThreadPool threads_
thread pool
size_t num_threads
number of threads overall
std::atomic< size_t > sequ_ss_steps
std::atomic< size_t > para_ss_steps
counters
MultiTimer mtimer
timers for individual sorting steps
size_t total_size
total size of input
Parallel Super Scalar String Sample Sort Parameter Struct.
static const size_t smallsort_threshold
threshold to run sequential small sorts
static const bool debug_steps
static const bool enable_parallel_sample_sort
enable/disable various sorting levels
static const unsigned TreeBits
depth of classification tree used in sample sorts
static const bool debug_lcp
static const bool debug_recursion
static const bool enable_sequential_mkqs
static const bool debug_result
static const size_t inssort_threshold
threshold to switch to insertion sort
static const bool debug_bucket_size
static const bool debug_jobs
static const bool enable_rest_size
whether the base sequential_threshold() on the remaining unsorted string set or on the whole string s...
size_t key_type
key type for sample sort: 32-bit or 64-bit
static const bool enable_sequential_sample_sort
static const bool enable_work_sharing
enable work freeing
static const bool use_only_first_sortstep
terminate sort after first parallel sample sort step
unsigned char eq_recurse_
MKQSStep(Context &ctx, const StringPtr &strptr, key_type *cache, size_t depth, bool CacheDirty)
Stack of Recursive Sample Sort Steps.
bktsize_type bkt[bktnum+1]
unsigned char splitter_lcp[num_splitters+1]
static const size_t bktnum
Context::Classify classifier
void calculate_lcp(Context &ctx)
static const size_t num_splitters
typename StringPtr::StringSet StringSet
SeqSampleSortStep(Context &ctx, const StringPtr &strptr, size_t depth, std::uint16_t *bktcache)
SampleSort: Non-Recursive In-Place Sequential Sample Sort for Small Sorts.
void sort_mkqs_cache(const StringPtr &strptr, size_t depth)
static void insertion_sort_cache(const StringPtr &_strptr, key_type *cache, size_t depth)
Insertion sort, but use cached characters if possible.
std::vector< MKQSStep > ms_stack_
static size_t med3(Type *A, size_t i, size_t j, size_t k)
PS5SortStep * pstep_
parent sort step
static void insertion_sort_cache_block(const StringPtr &strptr, key_type *cache)
Insertion sort the strings only based on the cached characters.
PS5SmallsortJob(Context &ctx, PS5SortStep *pstep, const StringPtr &strptr, size_t depth)
void substep_all_done() final
Pure virtual function called by substep when all substeps are done.
std::vector< SeqSampleSortStep > ss_stack_
simple_vector< std::uint8_t > bktcache_
void sort_sample_sort(const StringPtr &strptr, size_t depth)
static int cmp(const key_type &a, const key_type &b)
Stack of Recursive MKQS Steps.
Context::key_type key_type
StringPtr::StringSet StringSet
void sample_sort_free_work()
PS5SortStep Top-Level Class to Keep Track of Substeps.
virtual void substep_all_done()=0
Pure virtual function called by substep when all substeps are done.
void substep_notify_done()
Notify superstep that the currently substep is done.
void substep_add()
Register new substep.
std::atomic< size_t > substep_working_
Number of substeps still running.
Sample Sort Classification Tree Unrolled, Interleaved, and with Perfect Tree Index Calculations.
Objectified string array pointer array.
size_t size() const
return valid length
const StringSet & active() const
return currently active array
StringPtr sub(size_t offset, size_t sub_size) const
Advance (both) pointers by given offset, return sub-array.
void fill_lcp(const LcpType &) const
fill entire LCP array with v, excluding the first lcp[0] position!
static const bool with_lcp
if we want to save the LCPs
void set_lcp(size_t, const LcpType &) const
set the i-th lcp to v and check its value
Objectified string array pointer and shadow pointer array for out-of-place swapping of pointers.
Objectified string array pointer and shadow pointer array for out-of-place swapping of pointers.
#define TLX_LOGC(cond)
Explicitly specify the condition for logging.
static unsigned char lcpKeyType(const KeyType &a, const KeyType &b)
LCP calculation of Splitter Strings.
static unsigned char lcpKeyDepth(const KeyType &a)
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.
Type get_key_at(const StringSet &strset, size_t idx, size_t depth)
void parallel_sample_sort_base(const StringPtr &strptr, size_t depth)
Main Parallel Sample Sort Function. See below for more convenient wrappers.
enable_if< sizeof(Type)==4, std::uint32_t >::type get_key(const StringSet &strset, const typename StringSet::String &s, size_t depth)
static unsigned char getCharAtDepth(const KeyType &a, unsigned char d)
return the d-th character in the (swapped) key
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.
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.
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.
SFINAE enable_if – copy of std::enable_if<> with less extra cruft.