💾 Archived View for gmi.noulin.net › gitRepositories › sort › file › radixsort.h.gmi captured on 2024-07-09 at 02:46:08. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
radixsort.h (23557B)
1 #pragma once
2
3 /**
4 * type safe radix sort
5 *
6 * radix sort sorts keys that are either uint type or string type (char*) keys
7 * radix sort is faster than qsort from glibc and flashsort and takes less memory
8 *
9 * the radixyUintDef, radixyStringDef, radixyUintThreadDef, radixyStringThreadDef define the radix sort functions for arrays with the given element type:
10 *
11 * - shellsort##name or shellsortS##name - internal shell sort function
12 * - radixsort##name or radixsortS##name - function with all the parameters
13 * - name - function only with array and size parameters
14 * - nameSafe - like name and checks if there are empty strings
15 *
16 * the *ThreadDef macros defines threaded radix sort functions
17 *
18 *
19 * Example:
20 *
21 * // sorting array with string keys
22 *
23 * typ struct {char *a; int b;} skElemt;
24 *
25 * // define macro or function for access the key given an address to an element in the array
26 * #define radixsortAt(ptr) (ptr)->a
27 *
28 * // define a radixsort function with name 'radiS' and 'radiSSafe' sorting arrays with skElemt element type
29 * radixyStringDef(,radiS,skElemt,6,4, 40);
30 * #undef radixsortAt
31 *
32 * // the radiSSafe check if there are empty strings (NULL or "") in the keys
33 * // Empty strings are not allowed.
34 *
35 * // declare array
36 * skElemt radS[200];
37 *
38 * // sort the array
39 * radiS(radS, sz);
40 *
41 * // or call safe function:
42 * if (!radiSSafe(radS, sz)) {
43 * logE("Empty strings are not allowed");
44 * }
45 *
46 *
47 *
48 * // sorting a u32 array
49 *
50 * // define macro or function for access the key given an address to an element in the array
51 * #define radixsortAt(ptr) *(ptr)
52 *
53 * // define a radixsort function with name 'radi' sorting u32 arrays
54 * radixyUintDef(, radi , u32, 6, 4, 40);
55 * #undef radixsortAt
56 *
57 * // declare array
58 * u32 urnd[200];
59 *
60 * // sort the array
61 * radi(urnd, 200);
62 *
63 *
64 *
65 * // sorting an array with struct elements
66 *
67 * // declare element type
68 * typ struct {u64 a; int b;} rdxElemt;
69 *
70 * // define macro or function to access the key given an address to an element in the array
71 * #define radixsortAt(ptr) (ptr)->a
72 *
73 * // define a radixsort function with name 'radi64' sorting arrays with elements of type rdxElemt and u64 keys
74 * radixyUintDef(, radi64 , rdxElemt, 6, 4, 40);
75 * #undef radixsortAt
76 *
77 * // declare array
78 * rdxElemt radA[200];
79 *
80 * // sort the array
81 * radi64(radA, 200);
82 *
83 */
84
85 // define for internal use in radixyUint
86 #define radixyStop 256
87
88 /**
89 * radixyUintDef defines functions for sorting arrays of elemType
90 * the keys have to be unsigned int (any size)
91 *
92 * Functions:
93 * - shellsort##name - internal shell sort function
94 * - radixsort##name - function with all the parameters
95 * - name - function only with array and size parameters
96 *
97 * \param
98 * scope is static, internal or empty
99 * \param
100 * name function name for the sort function
101 * \param
102 * stackSizeP is the depth of the look-forward stack
103 * \param
104 * cutoffP is the digit cutoff for switching to shellsort
105 * \param
106 * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort
107 */
108 #define radixyUintDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\
109 internal inline void shellsort##name(elemType *arr, size_t size) {\
110 typeof(radixsortAt(&arr[0])) tmp; /* tmp key */\
111 typeof(arr[0]) elem; /* tmp record */\
112 \
113 {rangeFrom(i, 3, size) {\
114 tmp = radixsortAt(&arr[i]);\
115 elem = arr[i];\
116 size_t j;\
117 for(j = i ; j >= 3 && radixsortAt(&arr[j-3]) > tmp; j-=3) {\
118 arr[j] = arr[j-3];\
119 }\
120 arr[j] = elem;\
121 }}\
122 \
123 {rangeFrom(i, 1, size) {\
124 tmp = radixsortAt(&arr[i]);\
125 elem = arr[i];\
126 size_t j;\
127 for(j = i ; j >= 1 && radixsortAt(&arr[j-1]) > tmp; j--) {\
128 arr[j] = arr[j-1];\
129 }\
130 arr[j] = elem;\
131 }}\
132 }\
133 \
134 scope void radixsort##name(elemType *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff) {\
135 u8 *a;\
136 size_t counts[radixyStop];\
137 size_t offsets[radixyStop];\
138 size_t starts[radixyStop];\
139 size_t ends[radixyStop];\
140 size_t digt = sizeof(radixsortAt(&arr[0])) - digit - 1;\
141 \
142 pError0(zeroBuf(counts, sizeof(counts)));\
143 \
144 /* compute counts */\
145 {range(x, size) {\
146 a = (u8*)&radixsortAt(&arr[x]);\
147 u8 c = a[digt];\
148 counts[c]++;\
149 }}\
150 \
151 /* compute offsets */\
152 offsets[0] = 0;\
153 starts[0] = 0;\
154 {rangeFrom(x, 1, radixyStop) {\
155 offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\
156 }}\
157 ends[radixyStop-1] = size;\
158 \
159 \
160 /* loop on digit values */\
161 {range(x, radixyStop) {\
162 /* move records according to digit value */\
163 while(offsets[x] < ends[x]) {\
164 a = (u8*)&radixsortAt(&arr[offsets[x]]);\
165 u8 target = a[digt];\
166 if (target == x) {\
167 /* this record already placed in the correct bucket */\
168 offsets[x]++;\
169 }\
170 else {\
171 size_t stackIdx = 0;\
172 size_t stack[stackSize];\
173 stack[stackIdx++] = offsets[x];\
174 while(target != x && stackIdx < stackSize) {\
175 stack[stackIdx] = offsets[target]++;\
176 a = (u8*)&radixsortAt(&arr[stack[stackIdx]]);\
177 target = a[digt];\
178 stackIdx++;\
179 }\
180 if (stackIdx != stackSize) {\
181 /* found an element to store a offsets[x] */\
182 offsets[x]++;\
183 }\
184 stackIdx--;\
185 var tmp = arr[stack[stackIdx]];\
186 while(stackIdx) {\
187 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
188 stackIdx--;\
189 }\
190 arr[stack[0]] = tmp;\
191 }\
192 }\
193 }}\
194 \
195 /* cutoff to shellsort */\
196 if (digit < cutoff) {\
197 /* loop on digit values to sort the buckets */\
198 {range(x, radixyStop) {\
199 if (counts[x] > radixLevel) {\
200 radixsort##name(&arr[starts[x]], counts[x], digit+1, stackSize, cutoff);\
201 }\
202 else {\
203 if (counts[x] < 2) continue;\
204 shellsort##name(&arr[starts[x]], counts[x]);\
205 }\
206 }}\
207 }\
208 else {\
209 {range(x, radixyStop) {\
210 if (counts[x] > 1) {\
211 shellsort##name(&arr[starts[x]], counts[x]);\
212 }\
213 }}\
214 }\
215 }\
216 scope void name(elemType *arr, size_t size) {\
217 radixsort##name(arr, size, 0, stackSizeP, cutoffP);\
218 }
219
220
221 /**
222 * radixyUintThreadDef (like radixyUintDef) defines functions for sorting arrays of elemType
223 * the keys have to be unsigned int (any size)
224 *
225 * the defined functions by this macro are multithreaded using the threadpool in libsheepy
226 *
227 * Functions:
228 * - shellsort##name - internal shell sort function
229 * - radixsort##name - function with all the parameters
230 * - name - function only with array and size parameters
231 *
232 * \param
233 * scope is static, internal or empty
234 * \param
235 * name function name for the sort function
236 * \param
237 * stackSizeP is the depth of the look-forward stack
238 * \param
239 * cutoffP is the digit cutoff for switching to shellsort
240 * \param
241 * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort
242 */
243 #define radixyUintThreadDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\
244 internal inline void shellsort##name(elemType *arr, size_t size) {\
245 typeof(radixsortAt(&arr[0])) tmp; /* tmp key */\
246 typeof(arr[0]) elem; /* tmp record */\
247 \
248 {rangeFrom(i, 3, size) {\
249 tmp = radixsortAt(&arr[i]);\
250 elem = arr[i];\
251 size_t j;\
252 for(j = i ; j >= 3 && radixsortAt(&arr[j-3]) > tmp; j-=3) {\
253 arr[j] = arr[j-3];\
254 }\
255 arr[j] = elem;\
256 }}\
257 \
258 {rangeFrom(i, 1, size) {\
259 tmp = radixsortAt(&arr[i]);\
260 elem = arr[i];\
261 size_t j;\
262 for(j = i ; j >= 1 && radixsortAt(&arr[j-1]) > tmp; j--) {\
263 arr[j] = arr[j-1];\
264 }\
265 arr[j] = elem;\
266 }}\
267 }\
268 \
269 scope void radixsort##name(elemType *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff);\
270 \
271 typ struct {elemType *arr; size_t size; size_t digit; size_t stackSize; size_t cutoff;} radixy##name##Argst;\
272 \
273 void radixsort##name##Thread(void *args) {\
274 cast(radixy##name##Argst*, p, args);\
275 radixsort##name(p->arr, p->size, p->digit, p->stackSize, p->cutoff);\
276 }\
277 \
278 scope void radixsort##name(elemType *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff) {\
279 u8 *a;\
280 size_t counts[radixyStop];\
281 size_t offsets[radixyStop];\
282 size_t starts[radixyStop];\
283 size_t ends[radixyStop];\
284 size_t digt = sizeof(radixsortAt(&arr[0])) - digit - 1;\
285 radixy##name##Argst rdxArgs[radixyStop]; /* arguments for functions in the threadpool */\
286 size_t rdxArgsIdx = 0;\
287 \
288 pError0(zeroBuf(counts, sizeof(counts)));\
289 \
290 /* compute counts */\
291 {range(x, size) {\
292 a = (u8*)&radixsortAt(&arr[x]);\
293 u8 c = a[digt];\
294 counts[c]++;\
295 }}\
296 \
297 /* compute offsets */\
298 offsets[0] = 0;\
299 starts[0] = 0;\
300 {rangeFrom(x, 1, radixyStop) {\
301 offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\
302 }}\
303 ends[radixyStop-1] = size;\
304 \
305 \
306 /* loop on digit values */\
307 {range(x, radixyStop) {\
308 /* move records according to digit value */\
309 while(offsets[x] < ends[x]) {\
310 a = (u8*)&radixsortAt(&arr[offsets[x]]);\
311 u8 target = a[digt];\
312 if (target == x) {\
313 /* this record already placed in the correct bucket */\
314 offsets[x]++;\
315 }\
316 else {\
317 size_t stackIdx = 0;\
318 size_t stack[stackSize];\
319 stack[stackIdx++] = offsets[x];\
320 while(target != x && stackIdx < stackSize) {\
321 stack[stackIdx] = offsets[target]++;\
322 a = (u8*)&radixsortAt(&arr[stack[stackIdx]]);\
323 target = a[digt];\
324 stackIdx++;\
325 }\
326 if (stackIdx != stackSize) {\
327 /* found an element to store a offsets[x] */\
328 offsets[x]++;\
329 }\
330 stackIdx--;\
331 var tmp = arr[stack[stackIdx]];\
332 while(stackIdx) {\
333 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
334 stackIdx--;\
335 }\
336 arr[stack[0]] = tmp;\
337 }\
338 }\
339 }}\
340 \
341 /* cutoff to shellsort */\
342 if (digit < cutoff) {\
343 /* loop on digit values to sort the buckets */\
344 {range(x, radixyStop) {\
345 if (counts[x] > radixLevel) {\
346 if (!digit) {\
347 rdxArgs[rdxArgsIdx] = (radixy##name##Argst){.arr=&arr[starts[x]], .size=counts[x], .digit=digit+1, .stackSize=stackSize, .cutoff=cutoff};\
348 tpoolAdd(radixsort##name##Thread, (void*)&rdxArgs[rdxArgsIdx]);\
349 rdxArgsIdx++;\
350 }\
351 else\
352 radixsort##name(&arr[starts[x]], counts[x], digit+1, stackSize, cutoff);\
353 }\
354 else {\
355 if (counts[x] < 2) continue;\
356 shellsort##name(&arr[starts[x]], counts[x]);\
357 }\
358 }}\
359 }\
360 else {\
361 {range(x, radixyStop) {\
362 if (counts[x] > 1) {\
363 shellsort##name(&arr[starts[x]], counts[x]);\
364 }\
365 }}\
366 }\
367 \
368 if (!digit) {\
369 tpoolWait;\
370 }\
371 }\
372 scope void name(elemType *arr, size_t size) {\
373 radixsort##name(arr, size, 0, stackSizeP, cutoffP);\
374 }
375
376
377 /**
378 * radixyStringDef defines functions for sorting arrays of elemType
379 * the keys have to be strings (of type char*) and empty keys (NULL or "") are not allowed (segfaults)
380 *
381 * Functions:
382 * - shellsortS##name - internal shell sort function
383 * - radixsortS##name - function with all the parameters
384 * - name - function only with array and size parameters
385 * - nameSafe - like name and checks if there are empty strings
386 *
387 * \param
388 * scope is static, internal or empty
389 * \param
390 * name function name for the sort function
391 * \param
392 * stackSizeP is the depth of the look-forward stack
393 * \param
394 * cutoffP is the digit cutoff for switching to shellsort
395 * \param
396 * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort
397 */
398 #define radixyStringDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\
399 internal inline void shellsortS##name(elemType *arr, size_t size) {\
400 char *tmp; /* tmp key */\
401 typeof(arr[0]) elem; /* tmp record */\
402 \
403 {rangeFrom(i, 3, size) {\
404 tmp = radixsortAt(&arr[i]);\
405 elem = arr[i];\
406 size_t j;\
407 for(j = i ; j >= 3 && strcmp(radixsortAt(&arr[j-3]),tmp) > 0; j-=3) {\
408 arr[j] = arr[j-3];\
409 }\
410 arr[j] = elem;\
411 }}\
412 \
413 {rangeFrom(i, 1, size) {\
414 tmp = radixsortAt(&arr[i]);\
415 elem = arr[i];\
416 size_t j;\
417 for(j = i ; j >= 1 && strcmp(radixsortAt(&arr[j-1]),tmp) > 0; j--) {\
418 arr[j] = arr[j-1];\
419 }\
420 arr[j] = elem;\
421 }}\
422 }\
423 \
424 /**
425 * radixyS doesn't accept empty strings
426 * it segfaults when there is an empty string in the array
427 */\
428 void radixsortS##name(elemType *arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff) {\
429 size_t counts[charStop+1];\
430 size_t offsets[charStop+1];\
431 size_t starts[charStop+1];\
432 size_t ends[charStop+1];\
433 size_t digt = digit;\
434 \
435 pError0(zeroBuf(counts, sizeof(counts)));\
436 \
437 /* compute counts */\
438 {range(x, size) {\
439 u8 c = *(radixsortAt(&arr[x])+digt);\
440 counts[c]++;\
441 }}\
442 \
443 /* compute offsets */\
444 offsets[0] = 0;\
445 starts[0] = 0;\
446 offsets[charStart] = starts[charStart] = ends[0] = offsets[0] + counts[0];\
447 rangeFrom(x, charStart+1, charStop+1) {\
448 offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\
449 }\
450 ends[charStop] = size;\
451 \
452 /* sort 0 end of string */\
453 /* move records according to digit value */\
454 while(offsets[0] < ends[0]) {\
455 u8 target = *(radixsortAt(&arr[offsets[0]]) + digt);\
456 if (target == 0) {\
457 /* this record already placed in the correct bucket */\
458 offsets[0]++;\
459 }\
460 else {\
461 size_t stackIdx = 0;\
462 size_t stack[stackSize];\
463 stack[stackIdx++] = offsets[0];\
464 while(target != 0 && stackIdx < stackSize) {\
465 stack[stackIdx] = offsets[target]++;\
466 target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\
467 stackIdx++;\
468 }\
469 if (stackIdx != stackSize) {\
470 /* found an element to store a offsets[0] */\
471 offsets[0]++;\
472 }\
473 stackIdx--;\
474 var tmp = arr[stack[stackIdx]];\
475 while(stackIdx) {\
476 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
477 stackIdx--;\
478 }\
479 arr[stack[0]] = tmp;\
480 }\
481 }\
482 /* loop on digit values */\
483 {rangeFrom(x, charStart, charStop+1) {\
484 /* move records according to digit value */\
485 while(offsets[x] < ends[x]) {\
486 u8 target = *(radixsortAt(&arr[offsets[x]]) + digt);\
487 if (target == x) {\
488 /* this record already placed in the correct bucket */\
489 offsets[x]++;\
490 }\
491 else {\
492 size_t stackIdx = 0;\
493 size_t stack[stackSize];\
494 stack[stackIdx++] = offsets[x];\
495 while(target != x && stackIdx < stackSize) {\
496 stack[stackIdx] = offsets[target]++;\
497 target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\
498 stackIdx++;\
499 }\
500 if (stackIdx != stackSize) {\
501 /* found an element to store a offsets[x] */\
502 offsets[x]++;\
503 }\
504 stackIdx--;\
505 var tmp = arr[stack[stackIdx]];\
506 while(stackIdx) {\
507 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
508 stackIdx--;\
509 }\
510 arr[stack[0]] = tmp;\
511 }\
512 }\
513 }}\
514 \
515 /* cutoff to shellsort */\
516 if (digit < cutoff) {\
517 /* sort 0 end of string */\
518 if (counts[0] > radixLevel) {\
519 radixsortS##name(&arr[starts[0]], counts[0], digit+1, charStart, charStop, stackSize, cutoff);\
520 }\
521 else {\
522 if (counts[0] > 1) shellsortS##name(&arr[starts[0]], counts[0]);\
523 }\
524 /* loop on digit values to sort the buckets */\
525 {rangeFrom(x, charStart, charStop+1) {\
526 if (counts[x] > radixLevel) {\
527 radixsortS##name(&arr[starts[x]], counts[x], digit+1, charStart, charStop, stackSize, cutoff);\
528 }\
529 else {\
530 if (counts[x] < 2) continue;\
531 shellsortS##name(&arr[starts[x]], counts[x]);\
532 }\
533 }}\
534 }\
535 else {\
536 if (counts[0] > 1) {\
537 shellsortS##name(&arr[starts[0]], counts[0]);\
538 }\
539 rangeFrom(x, charStart, charStop+1) {\
540 if (counts[x] > 1) {\
541 shellsortS##name(&arr[starts[x]], counts[x]);\
542 }\
543 }\
544 }\
545 }\
546 scope void name(elemType *arr, size_t size) {\
547 radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\
548 }\
549 scope bool name##Safe(elemType *arr, size_t size) {\
550 {range(i, size) {\
551 if (isEmptyS(radixsortAt(&arr[i]))) ret false;\
552 }}\
553 radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\
554 ret true;\
555 }
556
557
558
559 /**
560 * radixyStringThreadDef (like radixyStringDef) defines functions for sorting arrays of elemType
561 * the keys have to be strings (of type char*) and empty keys (NULL or "") are not allowed (segfaults)
562 *
563 * the defined functions by this macro are multithreaded using the threadpool in libsheepy
564 *
565 * Functions:
566 * - shellsortS##name - internal shell sort function
567 * - radixsortS##name - function with all the parameters
568 * - name - function only with array and size parameters
569 * - nameSafe - like name and checks if there are empty strings
570 *
571 * \param
572 * scope is static, internal or empty
573 * \param
574 * name function name for the sort function
575 * \param
576 * stackSizeP is the depth of the look-forward stack
577 * \param
578 * cutoffP is the digit cutoff for switching to shellsort
579 * \param
580 * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort
581 */
582 #define radixyStringThreadDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\
583 internal inline void shellsortS##name(elemType *arr, size_t size) {\
584 char *tmp; /* tmp key */\
585 typeof(arr[0]) elem; /* tmp record */\
586 \
587 {rangeFrom(i, 3, size) {\
588 tmp = radixsortAt(&arr[i]);\
589 elem = arr[i];\
590 size_t j;\
591 for(j = i ; j >= 3 && strcmp(radixsortAt(&arr[j-3]),tmp) > 0; j-=3) {\
592 arr[j] = arr[j-3];\
593 }\
594 arr[j] = elem;\
595 }}\
596 \
597 {rangeFrom(i, 1, size) {\
598 tmp = radixsortAt(&arr[i]);\
599 elem = arr[i];\
600 size_t j;\
601 for(j = i ; j >= 1 && strcmp(radixsortAt(&arr[j-1]),tmp) > 0; j--) {\
602 arr[j] = arr[j-1];\
603 }\
604 arr[j] = elem;\
605 }}\
606 }\
607 \
608 void radixsortS##name(elemType *arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff);\
609 \
610 typ struct {elemType *arr; size_t size; size_t digit; u8 charStart; u16 charStop; size_t stackSize; size_t cutoff;} radixyS##name##Argst;\
611 \
612 void radixsortS##name##Thread(void *args) {\
613 cast(radixyS##name##Argst*, p, args);\
614 radixsortS##name(p->arr, p->size, p->digit, p->charStart, p->charStop, p->stackSize, p->cutoff);\
615 }\
616 \
617 /**
618 * radixyS doesn't accept empty strings
619 * it segfaults when there is an empty string in the array
620 */\
621 void radixsortS##name(elemType *arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff) {\
622 size_t counts[charStop+1];\
623 size_t offsets[charStop+1];\
624 size_t starts[charStop+1];\
625 size_t ends[charStop+1];\
626 size_t digt = digit;\
627 radixyS##name##Argst rdxArgs[charStop+1]; /* arguments for functions in the threadpool */\
628 size_t rdxArgsIdx = 0;\
629 \
630 pError0(zeroBuf(counts, sizeof(counts)));\
631 \
632 /* compute counts */\
633 {range(x, size) {\
634 u8 c = *(radixsortAt(&arr[x])+digt);\
635 counts[c]++;\
636 }}\
637 \
638 /* compute offsets */\
639 offsets[0] = 0;\
640 starts[0] = 0;\
641 offsets[charStart] = starts[charStart] = ends[0] = offsets[0] + counts[0];\
642 rangeFrom(x, charStart+1, charStop+1) {\
643 offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\
644 }\
645 ends[charStop] = size;\
646 \
647 /* sort 0 end of string */\
648 /* move records according to digit value */\
649 while(offsets[0] < ends[0]) {\
650 u8 target = *(radixsortAt(&arr[offsets[0]]) + digt);\
651 if (target == 0) {\
652 /* this record already placed in the correct bucket */\
653 offsets[0]++;\
654 }\
655 else {\
656 size_t stackIdx = 0;\
657 size_t stack[stackSize];\
658 stack[stackIdx++] = offsets[0];\
659 while(target != 0 && stackIdx < stackSize) {\
660 stack[stackIdx] = offsets[target]++;\
661 target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\
662 stackIdx++;\
663 }\
664 if (stackIdx != stackSize) {\
665 /* found an element to store a offsets[0] */\
666 offsets[0]++;\
667 }\
668 stackIdx--;\
669 var tmp = arr[stack[stackIdx]];\
670 while(stackIdx) {\
671 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
672 stackIdx--;\
673 }\
674 arr[stack[0]] = tmp;\
675 }\
676 }\
677 /* loop on digit values */\
678 {rangeFrom(x, charStart, charStop+1) {\
679 /* move records according to digit value */\
680 while(offsets[x] < ends[x]) {\
681 u8 target = *(radixsortAt(&arr[offsets[x]]) + digt);\
682 if (target == x) {\
683 /* this record already placed in the correct bucket */\
684 offsets[x]++;\
685 }\
686 else {\
687 size_t stackIdx = 0;\
688 size_t stack[stackSize];\
689 stack[stackIdx++] = offsets[x];\
690 while(target != x && stackIdx < stackSize) {\
691 stack[stackIdx] = offsets[target]++;\
692 target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\
693 stackIdx++;\
694 }\
695 if (stackIdx != stackSize) {\
696 /* found an element to store a offsets[x] */\
697 offsets[x]++;\
698 }\
699 stackIdx--;\
700 var tmp = arr[stack[stackIdx]];\
701 while(stackIdx) {\
702 arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
703 stackIdx--;\
704 }\
705 arr[stack[0]] = tmp;\
706 }\
707 }\
708 }}\
709 \
710 /* cutoff to shellsort */\
711 if (digit < cutoff) {\
712 /* sort 0 end of string */\
713 if (counts[0] > radixLevel) {\
714 if (!digit) {\
715 rdxArgs[rdxArgsIdx] = (radixyS##name##Argst){.arr=&arr[starts[0]], .size=counts[0], .digit=digit+1, .charStart=charStart, .charStop=charStop, .stackSize=stackSize, .cutoff=cutoff};\
716 tpoolAdd(radixsortS##name##Thread, (void*)&rdxArgs[rdxArgsIdx]);\
717 rdxArgsIdx++;\
718 }\
719 else\
720 radixsortS##name(&arr[starts[0]], counts[0], digit+1, charStart, charStop, stackSize, cutoff);\
721 }\
722 else {\
723 if (counts[0] > 1) shellsortS##name(&arr[starts[0]], counts[0]);\
724 }\
725 /* loop on digit values to sort the buckets */\
726 {rangeFrom(x, charStart, charStop+1) {\
727 if (counts[x] > radixLevel) {\
728 if (!digit) {\
729 rdxArgs[rdxArgsIdx] = (radixyS##name##Argst){.arr=&arr[starts[x]], .size=counts[x], .digit=digit+1, .charStart=charStart, .charStop=charStop, .stackSize=stackSize, .cutoff=cutoff};\
730 tpoolAdd(radixsortS##name##Thread, (void*)&rdxArgs[rdxArgsIdx]);\
731 rdxArgsIdx++;\
732 }\
733 else\
734 radixsortS##name(&arr[starts[x]], counts[x], digit+1, charStart, charStop, stackSize, cutoff);\
735 }\
736 else {\
737 if (counts[x] < 2) continue;\
738 shellsortS##name(&arr[starts[x]], counts[x]);\
739 }\
740 }}\
741 }\
742 else {\
743 if (counts[0] > 1) {\
744 shellsortS##name(&arr[starts[0]], counts[0]);\
745 }\
746 rangeFrom(x, charStart, charStop+1) {\
747 if (counts[x] > 1) {\
748 shellsortS##name(&arr[starts[x]], counts[x]);\
749 }\
750 }\
751 }\
752 \
753 if (!digit) {\
754 tpoolWait;\
755 }\
756 }\
757 scope void name(elemType *arr, size_t size) {\
758 radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\
759 }\
760 scope bool name##Safe(elemType *arr, size_t size) {\
761 {range(i, size) {\
762 if (isEmptyS(radixsortAt(&arr[i]))) ret false;\
763 }}\
764 radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\
765 ret true;\
766 }
767
768 // vim: set expandtab ts=2 sw=2: