tlx
Loading...
Searching...
No Matches
radix_sort.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/sort/strings/radix_sort.hpp
3 *
4 * Out-of-place and in-place radix sort for strings. This is an internal
5 * implementation header, see tlx/sort/strings.hpp for public front-end
6 * functions.
7 *
8 * These are explicit stack-based most-significant-digit radix sort
9 * implementations. All implementations were written by Timo Bingmann and are
10 * based on work by Juha Kärkkäinen and Tommi Rantala. "Engineering Radix Sort
11 * for Strings." International Symposium on String Processing and Information
12 * Retrieval (SPIRE). Springer, 2008.
13 *
14 * Part of tlx - http://panthema.net/tlx
15 *
16 * Copyright (C) 2015-2019 Timo Bingmann <tb@panthema.net>
17 *
18 * All rights reserved. Published under the Boost Software License, Version 1.0
19 ******************************************************************************/
20
21#ifndef TLX_SORT_STRINGS_RADIX_SORT_HEADER
22#define TLX_SORT_STRINGS_RADIX_SORT_HEADER
23
25#include <tlx/define/likely.hpp>
28
29#include <cstdint>
30#include <stack>
31#include <utility>
32#include <vector>
33
34namespace tlx {
35
36//! \addtogroup tlx_sort
37//! \{
38
39namespace sort_strings_detail {
40
41/******************************************************************************/
42
43static const size_t g_inssort_threshold = 32;
44
45/******************************************************************************/
46// Out-of-place 8-bit radix-sort WITHOUT character caching.
47
48template <typename StringShadowPtr>
51 size_t idx, pos, bkt_size[256];
52
54 typedef typename StringSet::Iterator Iterator;
55
56 RadixStep_CE0(const StringShadowPtr& in_strptr, size_t depth)
57 : strptr(in_strptr) {
58
59 const StringSet& ss = strptr.active();
60
61 // count character occurrences
62 std::fill(bkt_size, bkt_size + 256, 0);
63 for (Iterator i = ss.begin(); i != ss.end(); ++i)
64 ++bkt_size[ss.get_uint8(ss[i], depth)];
65
66 // prefix sum
67 Iterator bkt_index[256];
68 bkt_index[0] = strptr.shadow().begin();
69 for (size_t i = 1; i < 256; ++i)
70 bkt_index[i] = bkt_index[i - 1] + bkt_size[i - 1];
71
72 // distribute
73 for (Iterator i = ss.begin(); i != ss.end(); ++i)
74 *(bkt_index[ss.get_uint8(ss[i], depth)]++) = std::move(ss[i]);
75
76 // will increment to 1 on first process
77 idx = 0;
78 pos = bkt_size[0];
79
80 // copy back finished strings in zeroth bucket
82
83 // store lcps
84 if (strptr.with_lcp) {
85 size_t size = ss.size();
86
87 // set lcps of zero-terminated strings
88 for (size_t i = 1; i < pos; ++i)
89 strptr.set_lcp(i, depth);
90
91 // set lcps between non-empty bucket boundaries
92 size_t bkt = bkt_size[0], i = 1;
93 if (bkt > 0 && bkt < size)
94 strptr.set_lcp(bkt, depth);
95 while (i < 256) {
96 while (i < 256 && bkt_size[i] == 0)
97 ++i;
98 bkt += bkt_size[i];
99 if (bkt >= size)
100 break;
101 strptr.set_lcp(bkt, depth);
102 ++i;
103 }
104 }
105 }
106};
107
108/*
109 * Out-of-place 8-bit radix-sort WITHOUT character caching.
110 */
111template <typename StringShadowPtr>
112static inline void
113radixsort_CE0_loop(const StringShadowPtr& strptr, size_t depth, size_t memory) {
114
115 typedef RadixStep_CE0<StringShadowPtr> RadixStep;
116
117 std::stack<RadixStep, std::vector<RadixStep> > radixstack;
118 radixstack.emplace(strptr, depth);
119
120 while (radixstack.size())
121 {
122 while (radixstack.top().idx < 255)
123 {
124 RadixStep& rs = radixstack.top();
125
126 // process the bucket rs.idx
127 size_t bkt_size = rs.bkt_size[++rs.idx];
128
129 if (bkt_size == 0) {
130 // done
131 }
132 else if (bkt_size < g_inssort_threshold) {
134 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
135 depth + radixstack.size(),
136 memory - sizeof(RadixStep) * radixstack.size());
137 rs.pos += bkt_size;
138 }
139 else if (
141 memory != 0 &&
142 memory < sizeof(RadixStep) * (radixstack.size() + 1)))
143 {
145 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
146 depth + radixstack.size(),
147 memory - sizeof(RadixStep) * radixstack.size());
148 rs.pos += bkt_size;
149 }
150 else
151 {
152 rs.pos += bkt_size;
153 radixstack.emplace(rs.strptr.flip(rs.pos - bkt_size, bkt_size),
154 depth + radixstack.size());
155 // cannot add here, because rs may have invalidated
156 }
157 }
158 radixstack.pop();
159 }
160}
161
162/*!
163 * Adapter method to allocate shadow array if needed.
164 */
165template <typename StringPtr>
166static inline void
167radixsort_CE0(const StringPtr& strptr, size_t depth, size_t memory) {
168
169 typedef typename StringPtr::StringSet StringSet;
170 const StringSet& ss = strptr.active();
171 if (ss.size() < g_inssort_threshold)
172 return insertion_sort(strptr, depth, memory);
173
175
176 // try to estimate the amount of memory used
177 size_t memory_use =
178 2 * sizeof(size_t) + sizeof(StringSet)
179 + ss.size() * sizeof(typename StringSet::String);
180 size_t memory_slack = 3 * sizeof(RadixStep);
181
182 if (memory != 0 && memory < memory_use + memory_slack + 1)
183 return multikey_quicksort(strptr, depth, memory);
184
185 typename StringSet::Container shadow = ss.allocate(ss.size());
187 strptr.add_shadow(StringSet(shadow)), depth, memory - memory_use);
188 StringSet::deallocate(shadow);
189}
190
191/******************************************************************************/
192// Out-of-place 8-bit radix-sort with character caching.
193
194template <typename StringShadowPtr>
197 size_t idx, pos, bkt_size[256];
198
200 typedef typename StringSet::Iterator Iterator;
201
202 RadixStep_CE2(const StringShadowPtr& in_strptr, size_t depth,
203 std::uint8_t* charcache) : strptr(in_strptr) {
204
205 const StringSet& ss = strptr.active();
206 const size_t n = ss.size();
207
208 // read characters and count character occurrences
209 std::fill(bkt_size, bkt_size + 256, 0);
210 std::uint8_t* cc = charcache;
211 for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
212 *cc = ss.get_uint8(ss[i], depth);
213 for (cc = charcache; cc != charcache + n; ++cc)
214 ++bkt_size[static_cast<std::uint8_t>(*cc)];
215
216 // prefix sum
217 Iterator bkt_index[256];
218 bkt_index[0] = strptr.shadow().begin();
219 for (size_t i = 1; i < 256; ++i)
220 bkt_index[i] = bkt_index[i - 1] + bkt_size[i - 1];
221
222 // distribute
223 cc = charcache;
224 for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
225 *(bkt_index[static_cast<std::uint8_t>(*cc)]++) = std::move(ss[i]);
226
227 idx = 0; // will increment to 1 on first process
228 pos = bkt_size[0];
229
230 // copy back finished strings in zeroth bucket
231 strptr.flip(0, pos).copy_back();
232
233 // store lcps
234 if (strptr.with_lcp) {
235 size_t size = ss.size();
236
237 // set lcps of zero-terminated strings
238 for (size_t i = 1; i < pos; ++i)
239 strptr.set_lcp(i, depth);
240
241 // set lcps between non-empty bucket boundaries
242 size_t bkt = bkt_size[0], i = 1;
243 if (bkt > 0 && bkt < size)
244 strptr.set_lcp(bkt, depth);
245 while (i < 256) {
246 while (i < 256 && bkt_size[i] == 0)
247 ++i;
248 bkt += bkt_size[i];
249 if (bkt >= size)
250 break;
251 strptr.set_lcp(bkt, depth);
252 ++i;
253 }
254 }
255 }
256};
257
258template <typename StringPtr>
259static inline void
260radixsort_CI3(const StringPtr& strptr, std::uint16_t* charcache,
261 size_t depth, size_t memory);
262
263/*
264 * Out-of-place 8-bit radix-sort with character caching.
265 */
266template <typename StringShadowPtr>
267static inline void
269 std::uint8_t* charcache, size_t depth, size_t memory) {
270
271 typedef RadixStep_CE2<StringShadowPtr> RadixStep;
272
273 std::stack<RadixStep, std::vector<RadixStep> > radixstack;
274 radixstack.emplace(strptr, depth, charcache);
275
276 while (TLX_LIKELY(!radixstack.empty()))
277 {
278 while (TLX_LIKELY(radixstack.top().idx < 255))
279 {
280 RadixStep& rs = radixstack.top();
281
282 // process the bucket rs.idx
283 size_t bkt_size = rs.bkt_size[++rs.idx];
284
285 if (TLX_UNLIKELY(bkt_size == 0)) {
286 // done
287 }
288 else if (bkt_size < g_inssort_threshold) {
290 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
291 depth + radixstack.size(),
292 memory - sizeof(RadixStep) * radixstack.size());
293 rs.pos += bkt_size;
294 }
295 else if (
297 memory != 0 &&
298 memory < sizeof(RadixStep) * (radixstack.size() + 1)))
299 {
301 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
302 depth + radixstack.size(),
303 memory - sizeof(RadixStep) * radixstack.size());
304 rs.pos += bkt_size;
305 }
306 else
307 {
308 // have to increment first, as rs may be invalidated
309 rs.pos += bkt_size;
310 radixstack.emplace(rs.strptr.flip(rs.pos - bkt_size, bkt_size),
311 depth + radixstack.size(), charcache);
312 }
313 }
314 radixstack.pop();
315 }
316}
317
318template <typename StringPtr>
319static inline void
320radixsort_CE2(const StringPtr& strptr, size_t depth, size_t memory) {
321
322 typedef typename StringPtr::StringSet StringSet;
323 const StringSet& ss = strptr.active();
324 if (ss.size() < g_inssort_threshold)
325 return insertion_sort(strptr, depth, memory);
326
328
329 // try to estimate the amount of memory used
330 size_t memory_use =
331 2 * sizeof(size_t) + sizeof(StringSet)
332 + ss.size() * sizeof(std::uint8_t)
333 + ss.size() * sizeof(typename StringSet::String);
334 size_t memory_slack = 3 * sizeof(RadixStep);
335
336 if (memory != 0 && memory < memory_use + memory_slack + 1)
337 return radixsort_CI3(strptr, depth, memory);
338
339 typename StringSet::Container shadow = ss.allocate(ss.size());
340 std::uint8_t* charcache = new std::uint8_t[ss.size()];
341
342 radixsort_CE2_loop(strptr.add_shadow(StringSet(shadow)),
343 charcache, depth, memory - memory_use);
344
345 delete[] charcache;
346 StringSet::deallocate(shadow);
347}
348
349/******************************************************************************/
350// Out-of-place adaptive radix-sort with character caching
351
352template <typename StringShadowPtr>
354 enum { RADIX = 0x10000 };
355
358
360 typedef typename StringSet::Iterator Iterator;
361
362 RadixStep_CE3(const StringShadowPtr& in_strptr, size_t depth,
363 std::uint16_t* charcache) : strptr(in_strptr) {
364
365 const StringSet& ss = strptr.active();
366 const size_t n = ss.size();
367
368 // read characters and count character occurrences
369 std::fill(bkt_size, bkt_size + RADIX, 0);
370 std::uint16_t* cc = charcache;
371 for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
372 *cc = ss.get_uint16(ss[i], depth);
373 for (cc = charcache; cc != charcache + n; ++cc)
374 ++bkt_size[static_cast<std::uint16_t>(*cc)];
375
376 // prefix sum
378 bkt_index[0] = strptr.shadow().begin();
379 for (size_t i = 1; i < RADIX; ++i)
380 bkt_index[i] = bkt_index[i - 1] + bkt_size[i - 1];
381
382 // store lcps
383 if (strptr.with_lcp) {
384 // set lcps of zero-terminated strings
385 for (size_t i = 1; i < bkt_size[0]; ++i)
386 strptr.set_lcp(i, depth);
387
388 // set lcps between non-empty bucket boundaries
389 size_t first = get_next_non_empty_bkt_index(0);
390 size_t bkt = bkt_index[first] + bkt_size[first] - bkt_index[0];
391
392 size_t second = get_next_non_empty_bkt_index(first + 1);
393 while (second < RADIX)
394 {
395 size_t partial_equal = (first >> 8) == (second >> 8);
396 strptr.set_lcp(bkt, depth + partial_equal);
397 bkt += bkt_size[second];
398 first = second;
399 second = get_next_non_empty_bkt_index(second + 1);
400 }
401 }
402
403 // distribute
404 cc = charcache;
405 for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
406 *(bkt_index[static_cast<std::uint16_t>(*cc)]++) = std::move(ss[i]);
407
408 // will increment to 1 on first process
409 idx = 0;
410 pos = bkt_size[0];
411
412 // copy back finished strings in zeroth bucket
413 strptr.flip(0, pos).copy_back();
414 }
415
416 size_t get_next_non_empty_bkt_index(size_t start) {
417 if (start >= RADIX)
418 return RADIX;
419 while (start < RADIX && bkt_size[start] == 0)
420 ++start;
421 return start;
422 }
423};
424
425/*
426 * Out-of-place adaptive radix-sort with character caching which starts with
427 * 16-bit radix sort and then switching to 8-bit for smaller string sets.
428 */
429template <typename StringShadowPtr>
430static inline void
432 std::uint16_t* charcache, size_t depth, size_t memory) {
433
434 enum { RADIX = 0x10000 };
435
436 typedef RadixStep_CE3<StringShadowPtr> RadixStep;
437
438 std::stack<RadixStep, std::vector<RadixStep> > radixstack;
439 radixstack.emplace(strptr, depth, charcache);
440
441 while (TLX_LIKELY(!radixstack.empty()))
442 {
443 while (TLX_LIKELY(radixstack.top().idx < RADIX - 1))
444 {
445 RadixStep& rs = radixstack.top();
446
447 // process the bucket rs.idx
448 size_t bkt_size = rs.bkt_size[++rs.idx];
449
450 if (TLX_UNLIKELY(bkt_size == 0)) {
451 // done
452 }
453 else if (TLX_UNLIKELY((rs.idx & 0xFF) == 0)) {
454 // zero-termination
455 rs.strptr.flip(rs.pos, bkt_size).copy_back();
456 for (size_t i = rs.pos + 1; i < rs.pos + bkt_size; ++i)
457 rs.strptr.set_lcp(i, depth + 2 * radixstack.size() - 1);
458 rs.pos += bkt_size;
459 }
460 else if (TLX_UNLIKELY(bkt_size < g_inssort_threshold))
461 {
463 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
464 depth + 2 * radixstack.size(),
465 memory - sizeof(RadixStep) * radixstack.size());
466 rs.pos += bkt_size;
467 }
468 else if (bkt_size < RADIX)
469 {
471 rs.strptr.flip(rs.pos, bkt_size),
472 reinterpret_cast<std::uint8_t*>(charcache),
473 depth + 2 * radixstack.size(),
474 memory - sizeof(RadixStep) * radixstack.size());
475 rs.pos += bkt_size;
476 }
477 else if (
479 memory != 0 &&
480 memory < sizeof(RadixStep) * (radixstack.size() + 1)))
481 {
483 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
484 depth + 2 * radixstack.size(),
485 memory - sizeof(RadixStep) * radixstack.size());
486 rs.pos += bkt_size;
487 }
488 else
489 {
490 // have to increment first, as rs may be invalidated
491 rs.pos += bkt_size;
492 radixstack.emplace(
493 rs.strptr.flip(rs.pos - bkt_size, bkt_size),
494 depth + 2 * radixstack.size(), charcache);
495 }
496 }
497 radixstack.pop();
498 }
499}
500
501template <typename StringPtr>
502static inline void
503radixsort_CE3(const StringPtr& strptr, size_t depth, size_t memory) {
504 enum { RADIX = 0x10000 };
505 typedef typename StringPtr::StringSet StringSet;
506
507 const StringSet& ss = strptr.active();
508 if (ss.size() < g_inssort_threshold)
509 return insertion_sort(strptr, depth, memory);
510
511 if (ss.size() < RADIX)
512 return radixsort_CE2(strptr, depth, memory);
513
515
516 // try to estimate the amount of memory used
517 size_t memory_use =
518 2 * sizeof(size_t) + sizeof(StringSet)
519 + ss.size() * sizeof(std::uint16_t)
520 + ss.size() * sizeof(typename StringSet::String);
521 size_t memory_slack = 3 * sizeof(RadixStep);
522
523 if (memory != 0 && memory < memory_use + memory_slack + 1)
524 return radixsort_CE2(strptr, depth, memory);
525
526 typename StringSet::Container shadow = ss.allocate(ss.size());
527 std::uint16_t* charcache = new std::uint16_t[ss.size()];
528
529 radixsort_CE3_loop(strptr.add_shadow(StringSet(shadow)),
530 charcache, depth, memory - memory_use);
531
532 delete[] charcache;
533 StringSet::deallocate(shadow);
534}
535
536/******************************************************************************/
537// In-place 8-bit radix-sort with character caching.
538
539template <typename StringPtr>
542 typedef typename StringSet::Iterator Iterator;
543 typedef typename StringSet::String String;
544
545 size_t idx, pos;
546 size_t bkt_size[256];
547
549 size_t base, size_t depth, std::uint8_t* charcache) {
550
551 const StringSet& ss = strptr.active();
552 size_t size = ss.size();
553
554 // read characters and count character occurrences
555 std::fill(bkt_size, bkt_size + 256, 0);
556 std::uint8_t* cc = charcache;
557 for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
558 *cc = ss.get_uint8(ss[i], depth);
559 for (cc = charcache; cc != charcache + size; ++cc)
560 ++bkt_size[static_cast<std::uint8_t>(*cc)];
561
562 // inclusive prefix sum
563 size_t bkt[256];
564 bkt[0] = bkt_size[0];
565 size_t last_bkt_size = bkt_size[0];
566 for (size_t i = 1; i < 256; ++i) {
567 bkt[i] = bkt[i - 1] + bkt_size[i];
568 if (bkt_size[i] != 0) last_bkt_size = bkt_size[i];
569 }
570
571 // premute in-place
572 for (size_t i = 0, j; i < size - last_bkt_size; )
573 {
574 String perm = std::move(ss[ss.begin() + i]);
575 std::uint8_t permch = charcache[i];
576 while ((j = --bkt[permch]) > i)
577 {
578 std::swap(perm, ss[ss.begin() + j]);
579 std::swap(permch, charcache[j]);
580 }
581 ss[ss.begin() + i] = std::move(perm);
582 i += bkt_size[permch];
583 }
584
585 // will increment idx to 1 in first step, bkt 0 is not sorted further
586 idx = 0;
587 pos = base + bkt_size[0];
588
589 // store lcps
590 if (strptr.with_lcp) {
591 // set lcps of zero-terminated strings
592 for (size_t i = 1; i < bkt_size[0]; ++i)
593 strptr.set_lcp(i, depth);
594
595 // set lcps between non-empty bucket boundaries
596 size_t lbkt = bkt_size[0], i = 1;
597 if (lbkt > 0 && lbkt < size)
598 strptr.set_lcp(lbkt, depth);
599 while (i < 256) {
600 while (i < 256 && bkt_size[i] == 0)
601 ++i;
602 lbkt += bkt_size[i];
603 if (lbkt >= size)
604 break;
605 strptr.set_lcp(lbkt, depth);
606 ++i;
607 }
608 }
609 }
610};
611
612/*
613 * In-place 8-bit radix-sort with character caching.
614 */
615template <typename StringPtr>
616static inline void
617radixsort_CI2(const StringPtr& strptr, std::uint8_t* charcache,
618 size_t depth, size_t memory) {
619
620 typedef RadixStep_CI2<StringPtr> RadixStep;
621
622 std::stack<RadixStep, std::vector<RadixStep> > radixstack;
623 radixstack.emplace(strptr, /* base */ 0, depth, charcache);
624
625 while (TLX_LIKELY(!radixstack.empty()))
626 {
627 while (TLX_LIKELY(radixstack.top().idx < 255))
628 {
629 RadixStep& rs = radixstack.top();
630
631 // process the bucket rs.idx
632 size_t bkt_size = rs.bkt_size[++rs.idx];
633
634 if (TLX_UNLIKELY(bkt_size <= 1)) {
635 // done
636 rs.pos += bkt_size;
637 }
638 else if (bkt_size < g_inssort_threshold) {
640 strptr.sub(rs.pos, bkt_size),
641 depth + radixstack.size(),
642 memory - sizeof(RadixStep) * radixstack.size());
643 rs.pos += bkt_size;
644 }
645 else if (
647 memory != 0 &&
648 memory < sizeof(RadixStep) * (radixstack.size() + 1)))
649 {
651 strptr.sub(rs.pos, bkt_size),
652 depth + radixstack.size(),
653 memory - sizeof(RadixStep) * radixstack.size());
654 rs.pos += bkt_size;
655 }
656 else
657 {
658 // have to increment first, as rs may be invalidated
659 rs.pos += bkt_size;
660 radixstack.emplace(
661 strptr.sub(rs.pos - bkt_size, bkt_size),
662 rs.pos - bkt_size, depth + radixstack.size(), charcache);
663 }
664 }
665 radixstack.pop();
666 }
667}
668
669/*
670 * In-place 8-bit radix-sort with character caching.
671 */
672template <typename StringPtr>
673static inline void
674radixsort_CI2(const StringPtr& strptr, size_t depth, size_t memory) {
675 typedef typename StringPtr::StringSet StringSet;
676
677 if (strptr.size() < g_inssort_threshold)
678 return insertion_sort(strptr, depth, memory);
679
680 typedef RadixStep_CI2<StringPtr> RadixStep;
681
682 // try to estimate the amount of memory used
683 size_t memory_use =
684 2 * sizeof(size_t) + sizeof(StringSet)
685 + strptr.size() * sizeof(std::uint8_t);
686 size_t memory_slack = 3 * sizeof(RadixStep);
687
688 if (memory != 0 && memory < memory_use + memory_slack + 1)
689 return multikey_quicksort(strptr, depth, memory);
690
691 std::uint8_t* charcache = new std::uint8_t[strptr.size()];
692
693 radixsort_CI2(strptr, charcache, depth, memory - memory_use);
694
695 delete[] charcache;
696}
697
698/******************************************************************************/
699// In-place adaptive radix-sort with character caching
700
701template <typename StringPtr>
703 enum { RADIX = 0x10000 };
704
706 typedef typename StringSet::Iterator Iterator;
707 typedef typename StringSet::String String;
708
709 size_t idx, pos;
711
712 RadixStep_CI3(const StringPtr& strptr, size_t base, size_t depth,
713 std::uint16_t* charcache) {
714
715 const StringSet& ss = strptr.active();
716 const size_t n = ss.size();
717 // read characters and count character occurrences
718 std::fill(bkt_size, bkt_size + RADIX, 0);
719 std::uint16_t* cc = charcache;
720 for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
721 *cc = ss.get_uint16(ss[i], depth);
722 for (cc = charcache; cc != charcache + n; ++cc)
723 ++bkt_size[static_cast<std::uint16_t>(*cc)];
724
725 // inclusive prefix sum
726 simple_vector<size_t> bkt_index(RADIX);
727 bkt_index[0] = bkt_size[0];
728 size_t last_bkt_size = bkt_size[0];
729 for (size_t i = 1; i < RADIX; ++i) {
730 bkt_index[i] = bkt_index[i - 1] + bkt_size[i];
731 if (bkt_size[i]) last_bkt_size = bkt_size[i];
732 }
733
734 // store lcps
735 if (strptr.with_lcp) {
736 // set lcps of zero-terminated strings
737 for (size_t i = 1; i < bkt_size[0]; ++i)
738 strptr.set_lcp(i, depth);
739
740 // set lcps between non-empty bucket boundaries
741 size_t first = get_next_non_empty_bkt_index(0);
742 size_t bkt = bkt_index[first];
743
744 size_t second = get_next_non_empty_bkt_index(first + 1);
745 while (second < RADIX)
746 {
747 size_t partial_equal = (first >> 8) == (second >> 8);
748 strptr.set_lcp(bkt, depth + partial_equal);
749 bkt += bkt_size[second];
750 first = second;
751 second = get_next_non_empty_bkt_index(second + 1);
752 }
753 }
754
755 // premute in-place
756 for (size_t i = 0, j; i < n - last_bkt_size; )
757 {
758 String perm = std::move(ss[ss.begin() + i]);
759 std::uint16_t permch = charcache[i];
760 while ((j = --bkt_index[permch]) > i)
761 {
762 std::swap(perm, ss[ss.begin() + j]);
763 std::swap(permch, charcache[j]);
764 }
765 ss[ss.begin() + i] = std::move(perm);
766 i += bkt_size[permch];
767 }
768
769 // will increment to 1 on first process, bkt 0 is not sorted further
770 idx = 0;
771 pos = base + bkt_size[0];
772 }
773
774 size_t get_next_non_empty_bkt_index(size_t start) {
775 if (start >= RADIX)
776 return RADIX;
777 while (start < RADIX && bkt_size[start] == 0)
778 ++start;
779 return start;
780 }
781};
782
783/*
784 * In-place adaptive radix-sort with character caching which starts with 16-bit
785 * radix sort and then switching to 8-bit for smaller string sets.
786 */
787template <typename StringPtr>
788static inline void
789radixsort_CI3(const StringPtr& strptr, std::uint16_t* charcache,
790 size_t depth, size_t memory) {
791 enum { RADIX = 0x10000 };
792
793 typedef RadixStep_CI3<StringPtr> RadixStep;
794
795 std::stack<RadixStep, std::vector<RadixStep> > radixstack;
796 radixstack.emplace(strptr, /* base */ 0, depth, charcache);
797
798 while (TLX_LIKELY(!radixstack.empty()))
799 {
800 while (TLX_LIKELY(radixstack.top().idx < RADIX - 1))
801 {
802 RadixStep& rs = radixstack.top();
803
804 // process the bucket rs.idx
805 size_t bkt_size = rs.bkt_size[++rs.idx];
806
807 if (TLX_UNLIKELY(bkt_size <= 1)) {
808 // done
809 rs.pos += bkt_size;
810 }
811 else if (TLX_UNLIKELY((rs.idx & 0xFF) == 0)) {
812 // zero-termination
813 for (size_t i = rs.pos + 1; i < rs.pos + bkt_size; ++i)
814 strptr.set_lcp(i, depth + 2 * radixstack.size() - 1);
815
816 rs.pos += bkt_size;
817 }
818 else if (TLX_UNLIKELY(bkt_size < g_inssort_threshold))
819 {
821 strptr.sub(rs.pos, bkt_size),
822 depth + 2 * radixstack.size(),
823 memory - sizeof(RadixStep) * radixstack.size());
824 rs.pos += bkt_size;
825 }
826 else if (bkt_size < RADIX)
827 {
829 strptr.sub(rs.pos, bkt_size),
830 reinterpret_cast<std::uint8_t*>(charcache),
831 depth + 2 * radixstack.size(),
832 memory - sizeof(RadixStep) * radixstack.size());
833 rs.pos += bkt_size;
834 }
835 else if (
837 memory != 0 &&
838 memory < sizeof(RadixStep) * (radixstack.size() + 1)))
839 {
841 strptr.sub(rs.pos, bkt_size),
842 depth + 2 * radixstack.size(),
843 memory - sizeof(RadixStep) * radixstack.size());
844 rs.pos += bkt_size;
845 }
846 else
847 {
848 // have to increment first, as rs may be invalidated
849 rs.pos += bkt_size;
850 radixstack.emplace(
851 strptr.sub(rs.pos - bkt_size, bkt_size),
852 /* base */ rs.pos - bkt_size,
853 depth + 2 * radixstack.size(), charcache);
854 }
855 }
856 radixstack.pop();
857 }
858}
859
860template <typename StringPtr>
861static inline void
862radixsort_CI3(const StringPtr& strptr, size_t depth, size_t memory) {
863 enum { RADIX = 0x10000 };
864 typedef typename StringPtr::StringSet StringSet;
865
866 if (strptr.size() < g_inssort_threshold)
867 return insertion_sort(strptr, depth, memory);
868
869 if (strptr.size() < RADIX)
870 return radixsort_CI2(strptr, depth, memory);
871
872 typedef RadixStep_CI3<StringPtr> RadixStep;
873
874 // try to estimate the amount of memory used
875 size_t memory_use =
876 2 * sizeof(size_t) + sizeof(StringSet)
877 + strptr.size() * sizeof(std::uint16_t);
878 size_t memory_slack = 3 * sizeof(RadixStep);
879
880 if (memory != 0 && memory < memory_use + memory_slack + 1)
881 return radixsort_CI2(strptr, depth, memory);
882
883 std::uint16_t* charcache = new std::uint16_t[strptr.size()];
884 radixsort_CI3(strptr, charcache, depth, memory - memory_use);
885 delete[] charcache;
886}
887
888/******************************************************************************/
889
890} // namespace sort_strings_detail
891
892//! \}
893
894} // namespace tlx
895
896#endif // !TLX_SORT_STRINGS_RADIX_SORT_HEADER
897
898/******************************************************************************/
Simpler non-growing vector without initialization.
Objectified string array pointer array.
Definition: string_ptr.hpp:48
size_t size() const
return valid length
Definition: string_ptr.hpp:66
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:63
StringPtr sub(size_t offset, size_t sub_size) const
Advance (both) pointers by given offset, return sub-array.
Definition: string_ptr.hpp:69
static const bool with_lcp
if we want to save the LCPs
Definition: string_ptr.hpp:75
void set_lcp(size_t, const LcpType &) const
set the i-th lcp to v and check its value
Definition: string_ptr.hpp:79
WithShadow add_shadow(const StringSet &shadow) const
construct objectified string and shadow pointer class
Definition: string_ptr.hpp:343
Objectified string array pointer and shadow pointer array for out-of-place swapping of pointers.
Definition: string_ptr.hpp:169
size_t size() const
return valid length
Definition: string_ptr.hpp:198
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:189
const StringSet & shadow() const
return current shadow array
Definition: string_ptr.hpp:192
StringShadowPtr flip(size_t offset, size_t sub_size) const
construct a StringShadowPtr object specifying a sub-array with flipping to other array.
Definition: string_ptr.hpp:210
StringShadowPtr copy_back() const
return subarray pointer to n strings in original array, might copy from shadow before returning.
Definition: string_ptr.hpp:219
static const bool with_lcp
if we want to save the LCPs
Definition: string_ptr.hpp:230
void set_lcp(size_t, const LcpType &) const
set the i-th lcp to v and check its value
Definition: string_ptr.hpp:234
#define TLX_UNLIKELY(c)
Definition: likely.hpp:24
#define TLX_LIKELY(c)
Definition: likely.hpp:23
static void multikey_quicksort(const StringPtr &strptr, size_t depth, size_t memory)
Generic multikey quicksort for strings.
static const size_t g_inssort_threshold
Definition: radix_sort.hpp:43
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.
static void radixsort_CE2_loop(const StringShadowPtr &strptr, std::uint8_t *charcache, size_t depth, size_t memory)
Definition: radix_sort.hpp:268
static void radixsort_CE2(const StringPtr &strptr, size_t depth, size_t memory)
Definition: radix_sort.hpp:320
static void radixsort_CE3(const StringPtr &strptr, size_t depth, size_t memory)
Definition: radix_sort.hpp:503
static void radixsort_CE0_loop(const StringShadowPtr &strptr, size_t depth, size_t memory)
Definition: radix_sort.hpp:113
static void radixsort_CE3_loop(const StringShadowPtr &strptr, std::uint16_t *charcache, size_t depth, size_t memory)
Definition: radix_sort.hpp:431
static void radixsort_CE0(const StringPtr &strptr, size_t depth, size_t memory)
Adapter method to allocate shadow array if needed.
Definition: radix_sort.hpp:167
static void radixsort_CI2(const StringPtr &strptr, std::uint8_t *charcache, size_t depth, size_t memory)
Definition: radix_sort.hpp:617
static void radixsort_CI3(const StringPtr &strptr, std::uint16_t *charcache, size_t depth, size_t memory)
Definition: radix_sort.hpp:789
StringShadowPtr::StringSet StringSet
Definition: radix_sort.hpp:53
RadixStep_CE0(const StringShadowPtr &in_strptr, size_t depth)
Definition: radix_sort.hpp:56
StringShadowPtr::StringSet StringSet
Definition: radix_sort.hpp:199
RadixStep_CE2(const StringShadowPtr &in_strptr, size_t depth, std::uint8_t *charcache)
Definition: radix_sort.hpp:202
StringShadowPtr::StringSet StringSet
Definition: radix_sort.hpp:359
RadixStep_CE3(const StringShadowPtr &in_strptr, size_t depth, std::uint16_t *charcache)
Definition: radix_sort.hpp:362
size_t get_next_non_empty_bkt_index(size_t start)
Definition: radix_sort.hpp:416
RadixStep_CI2(const StringPtr &strptr, size_t base, size_t depth, std::uint8_t *charcache)
Definition: radix_sort.hpp:548
RadixStep_CI3(const StringPtr &strptr, size_t base, size_t depth, std::uint16_t *charcache)
Definition: radix_sort.hpp:712
size_t get_next_non_empty_bkt_index(size_t start)
Definition: radix_sort.hpp:774