Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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-2018 Timo Bingmann <[email protected]>
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 <stack>
30 #include <utility>
31 #include <vector>
32 
33 namespace tlx {
34 namespace sort_strings_detail {
35 
36 /******************************************************************************/
37 
38 static const size_t g_inssort_threshold = 32;
39 
40 /******************************************************************************/
41 // Out-of-place 8-bit radix-sort WITHOUT character caching.
42 
43 template <typename StringSet>
44 struct RadixStep_CE0 {
46  size_t idx, pos, bkt_size[256];
47 
48  typedef typename StringSet::Iterator Iterator;
49 
50  RadixStep_CE0(const StringShadowPtr<StringSet>& in_strptr, size_t depth)
51  : strptr(in_strptr) {
52 
53  const StringSet& ss = strptr.active();
54 
55  // count character occurrences
56  std::fill(bkt_size, bkt_size + 256, 0);
57  for (Iterator i = ss.begin(); i != ss.end(); ++i)
58  ++bkt_size[ss.get_uint8(ss[i], depth)];
59 
60  // prefix sum
61  Iterator bkt_index[256];
62  bkt_index[0] = strptr.shadow().begin();
63  for (size_t i = 1; i < 256; ++i)
64  bkt_index[i] = bkt_index[i - 1] + bkt_size[i - 1];
65 
66  // distribute
67  for (Iterator i = ss.begin(); i != ss.end(); ++i)
68  *(bkt_index[ss.get_uint8(ss[i], depth)]++) = std::move(ss[i]);
69 
70  idx = 0; // will increment to 1 on first process
71  pos = bkt_size[0];
72 
73  // copy back finished strings in zeroth bucket
74  strptr.flip(0, pos).copy_back();
75  }
76 };
77 
78 /*
79  * Out-of-place 8-bit radix-sort WITHOUT character caching.
80  */
81 template <typename StringSet>
82 static inline void
83 radixsort_CE0(const StringSet& ss, size_t depth, size_t memory) {
84 
85  if (ss.size() < g_inssort_threshold)
86  return insertion_sort(ss, depth, memory);
87 
88  typedef RadixStep_CE0<StringSet> RadixStep;
89 
90  // try to estimate the amount of memory used
91  size_t memory_use =
92  2 * sizeof(size_t) + sizeof(StringSet)
93  + ss.size() * sizeof(typename StringSet::String);
94  size_t memory_slack = 3 * sizeof(RadixStep);
95 
96  if (memory != 0 && memory < memory_use + memory_slack + 1)
97  return multikey_quicksort(ss, depth, memory);
98 
99  typename StringSet::Container shadow = ss.allocate(ss.size());
100  StringShadowPtr<StringSet> strptr(ss, StringSet(shadow));
101 
102  std::stack<RadixStep, std::vector<RadixStep> > radixstack;
103  radixstack.emplace(strptr, depth);
104 
105  while (radixstack.size())
106  {
107  while (radixstack.top().idx < 255)
108  {
109  RadixStep& rs = radixstack.top();
110 
111  // process the bucket rs.idx
112  size_t bkt_size = rs.bkt_size[++rs.idx];
113 
114  if (bkt_size == 0) {
115  // done
116  }
117  else if (bkt_size < g_inssort_threshold) {
119  rs.strptr.flip(rs.pos, rs.pos + bkt_size).copy_back(),
120  depth + radixstack.size(),
121  memory - sizeof(RadixStep) * radixstack.size());
122  rs.pos += bkt_size;
123  }
124  else if (TLX_UNLIKELY(memory != 0 &&
125  memory < sizeof(RadixStep) * radixstack.size() + 1))
126  {
128  rs.strptr.flip(rs.pos, rs.pos + bkt_size).copy_back(),
129  depth + radixstack.size(),
130  memory - sizeof(RadixStep) * radixstack.size());
131  rs.pos += bkt_size;
132  }
133  else
134  {
135  rs.pos += bkt_size;
136  radixstack.emplace(rs.strptr.flip(rs.pos - bkt_size, rs.pos),
137  depth + radixstack.size());
138  // cannot add here, because rs may have invalidated
139  }
140  }
141  radixstack.pop();
142  }
143 
144  StringSet::deallocate(shadow);
145 }
146 
147 /******************************************************************************/
148 // Out-of-place 8-bit radix-sort with character caching.
149 
150 template <typename StringSet>
153  size_t idx, pos, bkt_size[256];
154 
155  typedef typename StringSet::Iterator Iterator;
156 
157  RadixStep_CE2(const StringShadowPtr<StringSet>& in_strptr, size_t depth,
158  uint8_t* charcache) : strptr(in_strptr) {
159 
160  const StringSet& ss = strptr.active();
161  const size_t n = ss.size();
162 
163  // read characters and count character occurrences
164  std::fill(bkt_size, bkt_size + 256, 0);
165  uint8_t* cc = charcache;
166  for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
167  *cc = ss.get_uint8(ss[i], depth);
168  for (cc = charcache; cc != charcache + n; ++cc)
169  ++bkt_size[static_cast<uint8_t>(*cc)];
170 
171  // prefix sum
172  Iterator bkt_index[256];
173  bkt_index[0] = strptr.shadow().begin();
174  for (size_t i = 1; i < 256; ++i)
175  bkt_index[i] = bkt_index[i - 1] + bkt_size[i - 1];
176 
177  // distribute
178  cc = charcache;
179  for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
180  *(bkt_index[static_cast<uint8_t>(*cc)]++) = std::move(ss[i]);
181 
182  idx = 0; // will increment to 1 on first process
183  pos = bkt_size[0];
184 
185  // copy back finished strings in zeroth bucket
186  strptr.flip(0, pos).copy_back();
187  }
188 };
189 
190 /*
191  * Out-of-place 8-bit radix-sort with character caching.
192  */
193 template <typename StringSet>
194 static inline void
196  uint8_t* charcache, size_t depth, size_t memory) {
197 
198  typedef RadixStep_CE2<StringSet> RadixStep;
199 
200  std::stack<RadixStep, std::vector<RadixStep> > radixstack;
201  radixstack.emplace(strptr, depth, charcache);
202 
203  while (TLX_LIKELY(!radixstack.empty()))
204  {
205  while (TLX_LIKELY(radixstack.top().idx < 255))
206  {
207  RadixStep& rs = radixstack.top();
208 
209  // process the bucket rs.idx
210  size_t bkt_size = rs.bkt_size[++rs.idx];
211 
212  if (TLX_UNLIKELY(bkt_size == 0)) {
213  // done
214  }
215  else if (bkt_size < g_inssort_threshold) {
217  rs.strptr.flip(rs.pos, rs.pos + bkt_size).copy_back(),
218  depth + radixstack.size(),
219  memory - sizeof(RadixStep) * radixstack.size());
220  rs.pos += bkt_size;
221  }
222  else if (TLX_UNLIKELY(memory != 0 &&
223  memory < sizeof(RadixStep) * radixstack.size() + 1))
224  {
226  rs.strptr.flip(rs.pos, rs.pos + bkt_size).copy_back(),
227  depth + radixstack.size(),
228  memory - sizeof(RadixStep) * radixstack.size());
229  rs.pos += bkt_size;
230  }
231  else
232  {
233  // have to increment first, as rs may be invalidated
234  rs.pos += bkt_size;
235  radixstack.emplace(rs.strptr.flip(rs.pos - bkt_size, rs.pos),
236  depth + radixstack.size(), charcache);
237  }
238  }
239  radixstack.pop();
240  }
241 }
242 
243 template <typename StringSet>
244 static inline void
245 radixsort_CI3(const StringSet& ss, size_t depth, size_t memory);
246 
247 /*
248  * Out-of-place 8-bit radix-sort with character caching.
249  */
250 template <typename StringSet>
251 static inline void
252 radixsort_CE2(const StringSet& ss, size_t depth, size_t memory) {
253 
254  if (ss.size() < g_inssort_threshold)
255  return insertion_sort(ss, depth, memory);
256 
257  typedef RadixStep_CE2<StringSet> RadixStep;
258 
259  // try to estimate the amount of memory used
260  size_t memory_use =
261  2 * sizeof(size_t) + sizeof(StringSet) + ss.size() * sizeof(uint8_t)
262  + ss.size() * sizeof(typename StringSet::String);
263  size_t memory_slack = 3 * sizeof(RadixStep);
264 
265  if (memory != 0 && memory < memory_use + memory_slack + 1)
266  return radixsort_CI3(ss, depth, memory);
267 
268  typename StringSet::Container shadow = ss.allocate(ss.size());
269  StringShadowPtr<StringSet> strptr(ss, StringSet(shadow));
270 
271  uint8_t* charcache = new uint8_t[ss.size()];
272 
273  radixsort_CE2<StringSet>(
274  strptr, charcache, depth, memory - memory_use);
275 
276  delete[] charcache;
277  StringSet::deallocate(shadow);
278 }
279 
280 /******************************************************************************/
281 // Out-of-place adaptive radix-sort with character caching
282 
283 template <typename StringSet>
285  enum { RADIX = 0x10000 };
286 
288  size_t idx, pos, bkt_size[RADIX];
289 
290  typedef typename StringSet::Iterator Iterator;
291 
292  RadixStep_CE3(const StringShadowPtr<StringSet>& in_strptr, size_t depth,
293  uint16_t* charcache) : strptr(in_strptr) {
294 
295  const StringSet& ss = strptr.active();
296  const size_t n = ss.size();
297 
298  // read characters and count character occurrences
299  std::fill(bkt_size, bkt_size + RADIX, 0);
300  uint16_t* cc = charcache;
301  for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
302  *cc = ss.get_uint16(ss[i], depth);
303  for (cc = charcache; cc != charcache + n; ++cc)
304  ++bkt_size[static_cast<uint16_t>(*cc)];
305 
306  // prefix sum
307  simple_vector<Iterator> bkt_index(RADIX);
308  bkt_index[0] = strptr.shadow().begin();
309  for (size_t i = 1; i < RADIX; ++i)
310  bkt_index[i] = bkt_index[i - 1] + bkt_size[i - 1];
311 
312  // distribute
313  cc = charcache;
314  for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
315  *(bkt_index[static_cast<uint16_t>(*cc)]++) = std::move(ss[i]);
316 
317  idx = 0; // will increment to 1 on first process
318  pos = bkt_size[0];
319 
320  // copy back finished strings in zeroth bucket
321  strptr.flip(0, pos).copy_back();
322  }
323 };
324 
325 /*
326  * Out-of-place adaptive radix-sort with character caching which starts with
327  * 16-bit radix sort and then switching to 8-bit for smaller string sets.
328  */
329 template <typename StringSet>
330 static inline void
331 radixsort_CE3(const StringSet& ss, size_t depth, size_t memory) {
332  enum { RADIX = 0x10000 };
333 
334  if (ss.size() < g_inssort_threshold)
335  return insertion_sort(ss, depth, memory);
336 
337  if (ss.size() < RADIX)
338  return radixsort_CE2(ss, depth, memory);
339 
340  typedef RadixStep_CE3<StringSet> RadixStep;
341 
342  // try to estimate the amount of memory used
343  size_t memory_use =
344  2 * sizeof(size_t) + sizeof(StringSet) + ss.size() * sizeof(uint16_t)
345  + ss.size() * sizeof(typename StringSet::String);
346  size_t memory_slack = 3 * sizeof(RadixStep);
347 
348  if (memory != 0 && memory < memory_use + memory_slack + 1)
349  return radixsort_CE2(ss, depth, memory);
350 
351  typename StringSet::Container shadow = ss.allocate(ss.size());
352  StringShadowPtr<StringSet> strptr(ss, StringSet(shadow));
353 
354  uint16_t* charcache = new uint16_t[ss.size()];
355 
356  typedef std::stack<RadixStep, std::vector<RadixStep> > radixstack_type;
357  radixstack_type radixstack;
358  radixstack.emplace(strptr, depth, charcache);
359 
360  while (TLX_LIKELY(!radixstack.empty()))
361  {
362  while (TLX_LIKELY(radixstack.top().idx < RADIX - 1))
363  {
364  RadixStep& rs = radixstack.top();
365 
366  // process the bucket rs.idx
367  size_t bkt_size = rs.bkt_size[++rs.idx];
368 
369  if (TLX_UNLIKELY(bkt_size == 0)) {
370  // done
371  }
372  else if (TLX_UNLIKELY((rs.idx & 0xFF) == 0)) { // zero-termination
373  rs.strptr.flip(rs.pos, rs.pos + bkt_size).copy_back();
374  rs.pos += bkt_size;
375  }
376  else if (TLX_UNLIKELY(bkt_size < g_inssort_threshold))
377  {
379  rs.strptr.flip(rs.pos, rs.pos + bkt_size).copy_back(),
380  depth + 2 * radixstack.size(),
381  memory - memory_use - sizeof(RadixStep) * radixstack.size());
382  rs.pos += bkt_size;
383  }
384  else if (bkt_size < RADIX)
385  {
387  rs.strptr.flip(rs.pos, rs.pos + bkt_size),
388  reinterpret_cast<uint8_t*>(charcache),
389  depth + 2 * radixstack.size(),
390  memory - memory_use - sizeof(RadixStep) * radixstack.size());
391  rs.pos += bkt_size;
392  }
393  else if (TLX_UNLIKELY(memory != 0 &&
394  memory < memory_use + sizeof(RadixStep) * radixstack.size() + 1))
395  {
397  rs.strptr.flip(rs.pos, rs.pos + bkt_size).copy_back(),
398  depth + 2 * radixstack.size(),
399  memory - memory_use - sizeof(RadixStep) * radixstack.size());
400  rs.pos += bkt_size;
401  }
402  else
403  {
404  // have to increment first, as rs may be invalidated
405  rs.pos += bkt_size;
406  radixstack.emplace(
407  rs.strptr.flip(rs.pos - bkt_size, rs.pos),
408  depth + 2 * radixstack.size(), charcache);
409  }
410  }
411  radixstack.pop();
412  }
413 
414  delete[] charcache;
415  StringSet::deallocate(shadow);
416 }
417 
418 /******************************************************************************/
419 // In-place 8-bit radix-sort with character caching.
420 
421 template <typename StringSet>
423 
424  typedef typename StringSet::Iterator Iterator;
425  typedef typename StringSet::String String;
426 
427  size_t idx;
429  size_t bkt_size[256];
430 
431  RadixStep_CI2(const StringSet& ss, size_t depth, uint8_t* charcache) {
432  const size_t n = ss.size();
433 
434  // read characters and count character occurrences
435  std::fill(bkt_size, bkt_size + 256, 0);
436  uint8_t* cc = charcache;
437  for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
438  *cc = ss.get_uint8(ss[i], depth);
439  for (cc = charcache; cc != charcache + n; ++cc)
440  ++bkt_size[static_cast<uint8_t>(*cc)];
441 
442  // inclusive prefix sum
443  size_t bkt[256];
444  bkt[0] = bkt_size[0];
445  size_t last_bkt_size = bkt_size[0];
446  for (size_t i = 1; i < 256; ++i) {
447  bkt[i] = bkt[i - 1] + bkt_size[i];
448  if (bkt_size[i]) last_bkt_size = bkt_size[i];
449  }
450 
451  // premute in-place
452  for (size_t i = 0, j; i < n - last_bkt_size; )
453  {
454  String perm = std::move(ss[ss.begin() + i]);
455  uint8_t permch = charcache[i];
456  while ((j = --bkt[permch]) > i)
457  {
458  std::swap(perm, ss[ss.begin() + j]);
459  std::swap(permch, charcache[j]);
460  }
461  ss[ss.begin() + i] = std::move(perm);
462  i += bkt_size[permch];
463  }
464 
465  pos = ss.begin() + bkt_size[0];
466  idx = 0; // will increment to 1 on first process, bkt 0 is not sorted further
467  }
468 };
469 
470 /*
471  * In-place 8-bit radix-sort with character caching.
472  */
473 template <typename StringSet>
474 static inline void
475 radixsort_CI2(const StringSet& ss, uint8_t* charcache,
476  size_t depth, size_t memory) {
477 
478  typedef RadixStep_CI2<StringSet> RadixStep;
479 
480  std::stack<RadixStep, std::vector<RadixStep> > radixstack;
481  radixstack.emplace(ss, depth, charcache);
482 
483  while (TLX_LIKELY(!radixstack.empty()))
484  {
485  while (TLX_LIKELY(radixstack.top().idx < 255))
486  {
487  RadixStep& rs = radixstack.top();
488 
489  // process the bucket rs.idx
490  size_t bkt_size = rs.bkt_size[++rs.idx];
491 
492  if (TLX_UNLIKELY(bkt_size <= 1)) {
493  // done
494  rs.pos += bkt_size;
495  }
496  else if (bkt_size < g_inssort_threshold) {
498  ss.sub(rs.pos, rs.pos + bkt_size),
499  depth + radixstack.size(),
500  memory - sizeof(RadixStep) * radixstack.size());
501  rs.pos += bkt_size;
502  }
503  else if (TLX_UNLIKELY(memory != 0 &&
504  memory < sizeof(RadixStep) * radixstack.size() + 1))
505  {
507  ss.sub(rs.pos, rs.pos + bkt_size),
508  depth + radixstack.size(),
509  memory - sizeof(RadixStep) * radixstack.size());
510  rs.pos += bkt_size;
511  }
512  else
513  {
514  // have to increment first, as rs may be invalidated
515  rs.pos += bkt_size;
516  radixstack.emplace(ss.sub(rs.pos - bkt_size, rs.pos),
517  depth + radixstack.size(), charcache);
518  }
519  }
520  radixstack.pop();
521  }
522 }
523 
524 /*
525  * In-place 8-bit radix-sort with character caching.
526  */
527 template <typename StringSet>
528 static inline void
529 radixsort_CI2(const StringSet& ss, size_t depth, size_t memory) {
530 
531  if (ss.size() < g_inssort_threshold)
532  return insertion_sort(ss, depth, memory);
533 
534  typedef RadixStep_CI2<StringSet> RadixStep;
535 
536  // try to estimate the amount of memory used
537  size_t memory_use =
538  2 * sizeof(size_t) + sizeof(StringSet) + ss.size() * sizeof(uint8_t);
539  size_t memory_slack = 3 * sizeof(RadixStep);
540 
541  if (memory != 0 && memory < memory_use + memory_slack + 1)
542  return multikey_quicksort(ss, depth, memory);
543 
544  uint8_t* charcache = new uint8_t[ss.size()];
545 
546  radixsort_CI2<StringSet>(ss, charcache, depth, memory - memory_use);
547 
548  delete[] charcache;
549 }
550 
551 /******************************************************************************/
552 // In-place adaptive radix-sort with character caching
553 
554 template <typename StringSet>
556  enum { RADIX = 0x10000 };
557 
558  typedef typename StringSet::Iterator Iterator;
559  typedef typename StringSet::String String;
560 
561  size_t idx;
563  size_t bkt_size[RADIX];
564 
565  RadixStep_CI3(const StringSet& ss, size_t depth, uint16_t* charcache) {
566  const size_t n = ss.size();
567 
568  // read characters and count character occurrences
569  std::fill(bkt_size, bkt_size + RADIX, 0);
570  uint16_t* cc = charcache;
571  for (Iterator i = ss.begin(); i != ss.end(); ++i, ++cc)
572  *cc = ss.get_uint16(ss[i], depth);
573  for (cc = charcache; cc != charcache + n; ++cc)
574  ++bkt_size[static_cast<uint16_t>(*cc)];
575 
576  // inclusive prefix sum
578  bkt[0] = bkt_size[0];
579  size_t last_bkt_size = bkt_size[0];
580  for (size_t i = 1; i < RADIX; ++i) {
581  bkt[i] = bkt[i - 1] + bkt_size[i];
582  if (bkt_size[i]) last_bkt_size = bkt_size[i];
583  }
584 
585  // premute in-place
586  for (size_t i = 0, j; i < n - last_bkt_size; )
587  {
588  String perm = std::move(ss[ss.begin() + i]);
589  uint16_t permch = charcache[i];
590  while ((j = --bkt[permch]) > i)
591  {
592  std::swap(perm, ss[ss.begin() + j]);
593  std::swap(permch, charcache[j]);
594  }
595  ss[ss.begin() + i] = std::move(perm);
596  i += bkt_size[permch];
597  }
598 
599  // will increment to 1 on first process, bkt 0 is not sorted further
600  idx = 0;
601  pos = ss.begin() + bkt_size[0];
602  }
603 };
604 
605 /*
606  * In-place adaptive radix-sort with character caching which starts with 16-bit
607  * radix sort and then switching to 8-bit for smaller string sets.
608  */
609 template <typename StringSet>
610 static inline void
611 radixsort_CI3(const StringSet& ss, size_t depth, size_t memory) {
612  enum { RADIX = 0x10000 };
613 
614  if (ss.size() < g_inssort_threshold)
615  return insertion_sort(ss, depth, memory);
616 
617  if (ss.size() < RADIX)
618  return radixsort_CI2(ss, depth, memory);
619 
620  typedef RadixStep_CI3<StringSet> RadixStep;
621 
622  // try to estimate the amount of memory used
623  size_t memory_use =
624  2 * sizeof(size_t) + sizeof(StringSet) + ss.size() * sizeof(uint16_t);
625  size_t memory_slack = 3 * sizeof(RadixStep);
626 
627  if (memory != 0 && memory < memory_use + memory_slack + 1)
628  return radixsort_CI2(ss, depth, memory);
629 
630  uint16_t* charcache = new uint16_t[ss.size()];
631 
632  std::stack<RadixStep, std::vector<RadixStep> > radixstack;
633  radixstack.emplace(ss, depth, charcache);
634 
635  while (TLX_LIKELY(!radixstack.empty()))
636  {
637  while (TLX_LIKELY(radixstack.top().idx < RADIX - 1))
638  {
639  RadixStep& rs = radixstack.top();
640 
641  // process the bucket rs.idx
642  size_t bkt_size = rs.bkt_size[++rs.idx];
643 
644  if (TLX_UNLIKELY(bkt_size <= 1)) {
645  // done
646  rs.pos += bkt_size;
647  }
648  else if (TLX_UNLIKELY((rs.idx & 0xFF) == 0)) { // zero-termination
649  rs.pos += bkt_size;
650  }
651  else if (TLX_UNLIKELY(bkt_size < g_inssort_threshold))
652  {
654  ss.sub(rs.pos, rs.pos + bkt_size),
655  depth + 2 * radixstack.size(),
656  memory - memory_use - sizeof(RadixStep) * radixstack.size());
657  rs.pos += bkt_size;
658  }
659  else if (bkt_size < RADIX)
660  {
661  radixsort_CI2(ss.sub(rs.pos, rs.pos + bkt_size),
662  reinterpret_cast<uint8_t*>(charcache),
663  depth + 2 * radixstack.size(),
664  memory - memory_use - sizeof(RadixStep) * radixstack.size());
665  rs.pos += bkt_size;
666  }
667  else if (TLX_UNLIKELY(memory != 0 &&
668  memory < memory_use + sizeof(RadixStep) * radixstack.size() + 1))
669  {
671  ss.sub(rs.pos, rs.pos + bkt_size),
672  depth + 2 * radixstack.size(),
673  memory - memory_use - sizeof(RadixStep) * radixstack.size());
674  rs.pos += bkt_size;
675  }
676  else
677  {
678  // have to increment first, as rs may be invalidated
679  rs.pos += bkt_size;
680  radixstack.emplace(
681  ss.sub(rs.pos - bkt_size, rs.pos),
682  depth + 2 * radixstack.size(), charcache);
683  }
684  }
685  radixstack.pop();
686  }
687 
688  delete[] charcache;
689 }
690 
691 /******************************************************************************/
692 
693 } // namespace sort_strings_detail
694 } // namespace tlx
695 
696 #endif // !TLX_SORT_STRINGS_RADIX_SORT_HEADER
697 
698 /******************************************************************************/
StringShadowPtr flip(size_t begin, size_t end) const
Definition: string_set.hpp:578
static void radixsort_CI2(const StringSet &ss, uint8_t *charcache, size_t depth, size_t memory)
Definition: radix_sort.hpp:475
RadixStep_CI2(const StringSet &ss, size_t depth, uint8_t *charcache)
Definition: radix_sort.hpp:431
RadixStep_CI3(const StringSet &ss, size_t depth, uint16_t *charcache)
Definition: radix_sort.hpp:565
StringShadowPtr< StringSet > strptr
Definition: radix_sort.hpp:45
Simpler non-growing vector without initialization.
const StringSet & active() const
return currently active array
Definition: string_set.hpp:565
#define TLX_UNLIKELY(c)
Definition: likely.hpp:24
StringShadowPtr< StringSet > strptr
Definition: radix_sort.hpp:287
static void insertion_sort(const StringSet &ss, size_t depth, size_t)
RadixStep_CE0(const StringShadowPtr< StringSet > &in_strptr, size_t depth)
Definition: radix_sort.hpp:50
StringShadowPtr< StringSet > strptr
Definition: radix_sort.hpp:152
#define TLX_LIKELY(c)
Definition: likely.hpp:23
RadixStep_CE2(const StringShadowPtr< StringSet > &in_strptr, size_t depth, uint8_t *charcache)
Definition: radix_sort.hpp:157
static const size_t g_inssort_threshold
Definition: radix_sort.hpp:38
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
RadixStep_CE3(const StringShadowPtr< StringSet > &in_strptr, size_t depth, uint16_t *charcache)
Definition: radix_sort.hpp:292
static void radixsort_CE3(const StringSet &ss, size_t depth, size_t memory)
Definition: radix_sort.hpp:331
static void radixsort_CE2(const StringShadowPtr< StringSet > &strptr, uint8_t *charcache, size_t depth, size_t memory)
Definition: radix_sort.hpp:195
const StringSet & copy_back() const
Definition: string_set.hpp:592
static void radixsort_CI3(const StringSet &ss, size_t depth, size_t memory)
Definition: radix_sort.hpp:611
static void multikey_quicksort(const StringSet &ss, size_t depth, size_t memory)
Generic multikey quicksort for strings.
const StringSet & shadow() const
return current shadow array
Definition: string_set.hpp:568
static void radixsort_CE0(const StringSet &ss, size_t depth, size_t memory)
Definition: radix_sort.hpp:83