21 #ifndef TLX_SORT_STRINGS_RADIX_SORT_HEADER
22 #define TLX_SORT_STRINGS_RADIX_SORT_HEADER
38 namespace sort_strings_detail {
47 template <
typename StringShadowPtr>
48 struct RadixStep_CE0 {
53 typedef typename StringSet::Iterator
Iterator;
62 for (
Iterator i = ss.begin(); i != ss.end(); ++i)
63 ++
bkt_size[ss.get_uint8(ss[i], depth)];
68 for (
size_t i = 1; i < 256; ++i)
69 bkt_index[i] = bkt_index[i - 1] +
bkt_size[i - 1];
72 for (
Iterator i = ss.begin(); i != ss.end(); ++i)
73 *(bkt_index[ss.get_uint8(ss[i], depth)]++) = std::move(ss[i]);
84 size_t size = ss.
size();
87 for (
size_t i = 1; i <
pos; ++i)
92 if (bkt > 0 && bkt < size)
110 template <
typename StringShadowPtr>
114 typedef RadixStep_CE0<StringShadowPtr> RadixStep;
116 std::stack<RadixStep, std::vector<RadixStep> > radixstack;
117 radixstack.emplace(strptr, depth);
119 while (radixstack.size())
121 while (radixstack.top().idx < 255)
123 RadixStep& rs = radixstack.top();
126 size_t bkt_size = rs.bkt_size[++rs.idx];
133 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
134 depth + radixstack.size(),
135 memory -
sizeof(RadixStep) * radixstack.size());
141 memory <
sizeof(RadixStep) * (radixstack.size() + 1)))
144 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
145 depth + radixstack.size(),
146 memory -
sizeof(RadixStep) * radixstack.size());
152 radixstack.emplace(rs.strptr.flip(rs.pos - bkt_size, bkt_size),
153 depth + radixstack.size());
164 template <
typename StringPtr>
166 radixsort_CE0(
const StringPtr& strptr,
size_t depth,
size_t memory) {
169 const StringSet& ss = strptr.active();
173 typedef RadixStep_CE0<typename StringPtr::WithShadow> RadixStep;
177 2 *
sizeof(size_t) +
sizeof(StringSet)
178 + ss.size() *
sizeof(
typename StringSet::String);
179 size_t memory_slack = 3 *
sizeof(RadixStep);
181 if (memory != 0 && memory < memory_use + memory_slack + 1)
184 typename StringSet::Container shadow = ss.allocate(ss.size());
186 strptr.add_shadow(StringSet(shadow)), depth, memory - memory_use);
187 StringSet::deallocate(shadow);
193 template <
typename StringShadowPtr>
194 struct RadixStep_CE2 {
199 typedef typename StringSet::Iterator
Iterator;
201 RadixStep_CE2(
const StringShadowPtr& in_strptr,
size_t depth,
202 uint8_t* charcache) :
strptr(in_strptr) {
205 const size_t n = ss.size();
209 uint8_t* cc = charcache;
210 for (
Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
211 *cc = ss.get_uint8(ss[i], depth);
212 for (cc = charcache; cc != charcache + n; ++cc)
218 for (
size_t i = 1; i < 256; ++i)
223 for (
Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
224 *(bkt_index[
static_cast<uint8_t
>(*cc)]++) = std::move(ss[i]);
234 size_t size = ss.
size();
237 for (
size_t i = 1; i <
pos; ++i)
242 if (bkt > 0 && bkt < size)
257 template <
typename StringPtr>
260 size_t depth,
size_t memory);
265 template <
typename StringShadowPtr>
268 uint8_t* charcache,
size_t depth,
size_t memory) {
270 typedef RadixStep_CE2<StringShadowPtr> RadixStep;
272 std::stack<RadixStep, std::vector<RadixStep> > radixstack;
273 radixstack.emplace(strptr, depth, charcache);
277 while (
TLX_LIKELY(radixstack.top().idx < 255))
279 RadixStep& rs = radixstack.top();
282 size_t bkt_size = rs.bkt_size[++rs.idx];
289 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
290 depth + radixstack.size(),
291 memory -
sizeof(RadixStep) * radixstack.size());
297 memory <
sizeof(RadixStep) * (radixstack.size() + 1)))
300 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
301 depth + radixstack.size(),
302 memory -
sizeof(RadixStep) * radixstack.size());
309 radixstack.emplace(rs.strptr.flip(rs.pos - bkt_size, bkt_size),
310 depth + radixstack.size(), charcache);
317 template <
typename StringPtr>
319 radixsort_CE2(
const StringPtr& strptr,
size_t depth,
size_t memory) {
322 const StringSet& ss = strptr.active();
326 typedef RadixStep_CE2<typename StringPtr::WithShadow> RadixStep;
330 2 *
sizeof(size_t) +
sizeof(StringSet)
331 + ss.size() *
sizeof(uint8_t)
332 + ss.size() *
sizeof(
typename StringSet::String);
333 size_t memory_slack = 3 *
sizeof(RadixStep);
335 if (memory != 0 && memory < memory_use + memory_slack + 1)
338 typename StringSet::Container shadow = ss.allocate(ss.size());
339 uint8_t* charcache =
new uint8_t[ss.size()];
342 charcache, depth, memory - memory_use);
345 StringSet::deallocate(shadow);
351 template <
typename StringShadowPtr>
352 struct RadixStep_CE3 {
353 enum {
RADIX = 0x10000 };
359 typedef typename StringSet::Iterator
Iterator;
361 RadixStep_CE3(
const StringShadowPtr& in_strptr,
size_t depth,
362 uint16_t* charcache) :
strptr(in_strptr) {
365 const size_t n = ss.size();
369 uint16_t* cc = charcache;
370 for (
Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
371 *cc = ss.get_uint16(ss[i], depth);
372 for (cc = charcache; cc != charcache + n; ++cc)
378 for (
size_t i = 1; i <
RADIX; ++i)
384 for (
size_t i = 1; i <
bkt_size[0]; ++i)
389 size_t bkt = bkt_index[first] +
bkt_size[first] - bkt_index[0];
392 while (second <
RADIX)
394 size_t partial_equal = (first >> 8) == (second >> 8);
404 for (
Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
405 *(bkt_index[
static_cast<uint16_t
>(*cc)]++) = std::move(ss[i]);
428 template <
typename StringShadowPtr>
431 uint16_t* charcache,
size_t depth,
size_t memory) {
433 enum { RADIX = 0x10000 };
437 std::stack<RadixStep, std::vector<RadixStep> > radixstack;
438 radixstack.emplace(strptr, depth, charcache);
442 while (
TLX_LIKELY(radixstack.top().idx < RADIX - 1))
444 RadixStep& rs = radixstack.top();
447 size_t bkt_size = rs.bkt_size[++rs.idx];
454 rs.strptr.flip(rs.pos, bkt_size).copy_back();
455 for (
size_t i = rs.pos + 1; i < rs.pos + bkt_size; ++i)
456 rs.strptr.set_lcp(i, depth + 2 * radixstack.size() - 1);
462 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
463 depth + 2 * radixstack.size(),
464 memory -
sizeof(RadixStep) * radixstack.size());
467 else if (bkt_size < RADIX)
470 rs.strptr.flip(rs.pos, bkt_size),
471 reinterpret_cast<uint8_t*
>(charcache),
472 depth + 2 * radixstack.size(),
473 memory -
sizeof(RadixStep) * radixstack.size());
479 memory <
sizeof(RadixStep) * (radixstack.size() + 1)))
482 rs.strptr.flip(rs.pos, bkt_size).copy_back(),
483 depth + 2 * radixstack.size(),
484 memory -
sizeof(RadixStep) * radixstack.size());
492 rs.strptr.flip(rs.pos - bkt_size, bkt_size),
493 depth + 2 * radixstack.size(), charcache);
500 template <
typename StringPtr>
502 radixsort_CE3(
const StringPtr& strptr,
size_t depth,
size_t memory) {
503 enum { RADIX = 0x10000 };
506 const StringSet& ss = strptr.active();
510 if (ss.size() < RADIX)
513 typedef RadixStep_CE3<typename StringPtr::WithShadow> RadixStep;
517 2 *
sizeof(size_t) +
sizeof(StringSet)
518 + ss.size() *
sizeof(uint16_t)
519 + ss.size() *
sizeof(
typename StringSet::String);
520 size_t memory_slack = 3 *
sizeof(RadixStep);
522 if (memory != 0 && memory < memory_use + memory_slack + 1)
525 typename StringSet::Container shadow = ss.allocate(ss.size());
526 uint16_t* charcache =
new uint16_t[ss.size()];
529 charcache, depth, memory - memory_use);
532 StringSet::deallocate(shadow);
538 template <
typename StringPtr>
539 struct RadixStep_CI2 {
541 typedef typename StringSet::Iterator
Iterator;
542 typedef typename StringSet::String
String;
548 size_t base,
size_t depth, uint8_t* charcache) {
551 size_t size = ss.size();
555 uint8_t* cc = charcache;
556 for (
Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
557 *cc = ss.get_uint8(ss[i], depth);
558 for (cc = charcache; cc != charcache + size; ++cc)
565 for (
size_t i = 1; i < 256; ++i) {
571 for (
size_t i = 0, j; i < size - last_bkt_size; )
573 String perm = std::move(ss[ss.begin() + i]);
574 uint8_t permch = charcache[i];
575 while ((j = --bkt[permch]) > i)
580 ss[ss.begin() + i] = std::move(perm);
589 if (strptr.with_lcp) {
591 for (
size_t i = 1; i <
bkt_size[0]; ++i)
592 strptr.set_lcp(i, depth);
596 if (lbkt > 0 && lbkt < size)
597 strptr.set_lcp(lbkt, depth);
604 strptr.set_lcp(lbkt, depth);
614 template <
typename StringPtr>
617 size_t depth,
size_t memory) {
619 typedef RadixStep_CI2<StringPtr> RadixStep;
621 std::stack<RadixStep, std::vector<RadixStep> > radixstack;
622 radixstack.emplace(strptr, 0, depth, charcache);
626 while (
TLX_LIKELY(radixstack.top().idx < 255))
628 RadixStep& rs = radixstack.top();
631 size_t bkt_size = rs.bkt_size[++rs.idx];
639 strptr.sub(rs.pos, bkt_size),
640 depth + radixstack.size(),
641 memory -
sizeof(RadixStep) * radixstack.size());
647 memory <
sizeof(RadixStep) * (radixstack.size() + 1)))
650 strptr.sub(rs.pos, bkt_size),
651 depth + radixstack.size(),
652 memory -
sizeof(RadixStep) * radixstack.size());
660 strptr.sub(rs.pos - bkt_size, bkt_size),
661 rs.pos - bkt_size, depth + radixstack.size(), charcache);
671 template <
typename StringPtr>
673 radixsort_CI2(
const StringPtr& strptr,
size_t depth,
size_t memory) {
679 typedef RadixStep_CI2<StringPtr> RadixStep;
683 2 *
sizeof(size_t) +
sizeof(StringSet)
684 + strptr.size() *
sizeof(uint8_t);
685 size_t memory_slack = 3 *
sizeof(RadixStep);
687 if (memory != 0 && memory < memory_use + memory_slack + 1)
690 uint8_t* charcache =
new uint8_t[strptr.size()];
692 radixsort_CI2(strptr, charcache, depth, memory - memory_use);
700 template <
typename StringPtr>
701 struct RadixStep_CI3 {
702 enum {
RADIX = 0x10000 };
705 typedef typename StringSet::Iterator
Iterator;
706 typedef typename StringSet::String
String;
711 RadixStep_CI3(
const StringPtr& strptr,
size_t base,
size_t depth,
712 uint16_t* charcache) {
715 const size_t n = ss.size();
718 uint16_t* cc = charcache;
719 for (
Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
720 *cc = ss.get_uint16(ss[i], depth);
721 for (cc = charcache; cc != charcache + n; ++cc)
728 for (
size_t i = 1; i <
RADIX; ++i) {
734 if (strptr.with_lcp) {
736 for (
size_t i = 1; i <
bkt_size[0]; ++i)
737 strptr.set_lcp(i, depth);
741 size_t bkt = bkt_index[first];
744 while (second <
RADIX)
746 size_t partial_equal = (first >> 8) == (second >> 8);
747 strptr.set_lcp(bkt, depth + partial_equal);
755 for (
size_t i = 0, j; i < n - last_bkt_size; )
757 String perm = std::move(ss[ss.begin() + i]);
758 uint16_t permch = charcache[i];
759 while ((j = --bkt_index[permch]) > i)
764 ss[ss.begin() + i] = std::move(perm);
786 template <
typename StringPtr>
789 size_t depth,
size_t memory) {
790 enum { RADIX = 0x10000 };
794 std::stack<RadixStep, std::vector<RadixStep> > radixstack;
795 radixstack.emplace(strptr, 0, depth, charcache);
799 while (
TLX_LIKELY(radixstack.top().idx < RADIX - 1))
801 RadixStep& rs = radixstack.top();
804 size_t bkt_size = rs.bkt_size[++rs.idx];
812 for (
size_t i = rs.pos + 1; i < rs.pos + bkt_size; ++i)
813 strptr.set_lcp(i, depth + 2 * radixstack.size() - 1);
820 strptr.sub(rs.pos, bkt_size),
821 depth + 2 * radixstack.size(),
822 memory -
sizeof(RadixStep) * radixstack.size());
825 else if (bkt_size < RADIX)
828 strptr.sub(rs.pos, bkt_size),
829 reinterpret_cast<uint8_t*
>(charcache),
830 depth + 2 * radixstack.size(),
831 memory -
sizeof(RadixStep) * radixstack.size());
837 memory <
sizeof(RadixStep) * (radixstack.size() + 1)))
840 strptr.sub(rs.pos, bkt_size),
841 depth + 2 * radixstack.size(),
842 memory -
sizeof(RadixStep) * radixstack.size());
850 strptr.sub(rs.pos - bkt_size, bkt_size),
852 depth + 2 * radixstack.size(), charcache);
859 template <
typename StringPtr>
861 radixsort_CI3(
const StringPtr& strptr,
size_t depth,
size_t memory) {
862 enum { RADIX = 0x10000 };
868 if (strptr.size() < RADIX)
871 typedef RadixStep_CI3<StringPtr> RadixStep;
875 2 *
sizeof(size_t) +
sizeof(StringSet)
876 + strptr.size() *
sizeof(uint16_t);
877 size_t memory_slack = 3 *
sizeof(RadixStep);
879 if (memory != 0 && memory < memory_use + memory_slack + 1)
882 uint16_t* charcache =
new uint16_t[strptr.size()];
883 radixsort_CI3(strptr, charcache, depth, memory - memory_use);
895 #endif // !TLX_SORT_STRINGS_RADIX_SORT_HEADER