commit d4753e52dc50a892c6bcc1bf30e47d504e1f3166
parent da2c7d659930bdd5972109eec9d9d307876a3992
Author: Remy Noulin <loader2x@gmail.com>
Date: Sat, 19 Jan 2019 21:40:44 +0100
add radix sort
main.c | 714 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
package.yml | 6 +-
radixsort.h | 768 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
sort.h | 1 +
4 files changed, 1482 insertions(+), 7 deletions(-)
Diffstat:
| M | main.c | | | 714 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- |
| M | package.yml | | | 6 | ++++-- |
| A | radixsort.h | | | 768 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | sort.h | | | 1 | + |
4 files changed, 1482 insertions(+), 7 deletions(-)
diff --git a/main.c b/main.c
@@ -231,17 +231,677 @@ void flashSort_i32A(void *arr, size_t size, size_t elemSize, flashSortGetFt flas
+//radix bsort
+//#define RADIX_LEVEL 3
+#define RADIX_LEVEL 40
+internal inline void shellsort(u32 *arr, size_t size) {
+ u32 tmp; // tmp record
+
+ rangeFrom(i, 3, size) {
+ tmp = arr[i];
+ size_t j;
+ for(j = i ; j >= 3 && arr[j-3] > tmp; j-=3) {
+ arr[j] = arr[j-3];
+ }
+ arr[j] = tmp;
+ }
+
+ rangeFrom(i, 1, size) {
+ tmp = arr[i];
+ size_t j;
+ for(j = i ; j >= 1 && arr[j-1] > tmp; j--) {
+ arr[j] = arr[j-1];
+ }
+ arr[j] = tmp;
+ }
+}
+
+void radixyOrig(u32 *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff) {
+ #define stop 256
+ u8 *a = (u8*) arr;
+ size_t counts[stop];
+ size_t offsets[stop];
+ size_t starts[stop];
+ size_t ends[stop];
+ size_t digt = sizeof(u32) - digit - 1;
+
+ zeroBuf(counts, sizeof(counts));
+
+ // compute counts
+ range(x, size) {
+ u8 c = a[x * sizeof(u32) + digt];
+ counts[c]++;
+ }
+
+ // compute offsets
+ offsets[0] = 0;
+ starts[0] = 0;
+ rangeFrom(x, 1, stop) {
+ offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];
+ }
+ ends[stop-1] = size;
+
+
+ // loop on digit values
+ range(x, stop) {
+ // move records according to digit value
+ while(offsets[x] < ends[x]) {
+ u8 target = a[offsets[x] * sizeof(u32) + digt];
+ if (target == x) {
+ // this record already placed in the correct bucket
+ offsets[x]++;
+ }
+ else {
+ size_t stackIdx = 0;
+ size_t stack[stackSize];
+ stack[stackIdx++] = offsets[x];
+ while(target != x && stackIdx < stackSize) {
+ stack[stackIdx] = offsets[target]++;
+ target = a[stack[stackIdx] * sizeof(u32) + digt];
+ stackIdx++;
+ }
+ if (stackIdx != stackSize) {
+ // found an element to store a offsets[x]
+ offsets[x]++;
+ }
+ stackIdx--;
+ u32 tmp = arr[stack[stackIdx]];
+ while(stackIdx) {
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];
+ stackIdx--;
+ }
+ arr[stack[0]] = tmp;
+ }
+ }
+ }
+
+ // cutoff to shellsort
+ if (digit < cutoff) {
+ // loop on digit values to sort the buckets
+ range(x, stop) {
+ if (counts[x] > RADIX_LEVEL) {
+ radixyOrig(&arr[starts[x]], counts[x], digit+1, stackSize, cutoff);
+ }
+ else {
+ if (counts[x] < 2) continue;
+ shellsort(&arr[starts[x]], counts[x]);
+ }
+ }
+ }
+ else {
+ range(x, stop) {
+ if (counts[x] > 1) {
+ shellsort(&arr[starts[x]], counts[x]);
+ }
+ }
+ }
+ #undef stop
+}
+
+void radixy(u32 *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff);
+
+typ struct {u32 *arr; size_t size; size_t digit; size_t stackSize; size_t cutoff;} radixyArgst;
+
+typ struct {u32 *arr; size_t size;} shellsortArgst;
+
+void radixyThread(void *args) {
+ cast(radixyArgst*, p, args);
+ radixy(p->arr, p->size, p->digit, p->stackSize, p->cutoff);
+}
+
+void shellsortThread(void *args) {
+ cast(shellsortArgst *, p, args);
+ shellsort(p->arr, p->size);
+}
+
+// parallel radix sort for u32 array
+void radixy(u32 *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff) {
+ #define stop 256
+ u8 *a = (u8*) arr;
+ size_t counts[stop];
+ size_t offsets[stop];
+ size_t starts[stop];
+ size_t ends[stop];
+ size_t digt = sizeof(u32) - digit - 1;
+ radixyArgst rdxArgs[stop];
+ size_t rdxArgsIdx = 0;
+
+ zeroBuf(counts, sizeof(counts));
+
+ // compute counts
+ range(x, size) {
+ u8 c = a[x * sizeof(u32) + digt];
+ counts[c]++;
+ }
+
+ // compute offsets
+ offsets[0] = 0;
+ starts[0] = 0;
+ rangeFrom(x, 1, stop) {
+ offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];
+ }
+ ends[stop-1] = size;
+
+
+ // loop on digit values
+ range(x, stop) {
+ // move records according to digit value
+ while(offsets[x] < ends[x]) {
+ u8 target = a[offsets[x] * sizeof(u32) + digt];
+ if (target == x) {
+ // this record already placed in the correct bucket
+ offsets[x]++;
+ }
+ else {
+ size_t stackIdx = 0;
+ size_t stack[stackSize];
+ stack[stackIdx++] = offsets[x];
+ while(target != x && stackIdx < stackSize) {
+ stack[stackIdx] = offsets[target]++;
+ target = a[stack[stackIdx] * sizeof(u32) + digt];
+ stackIdx++;
+ }
+ if (stackIdx != stackSize) {
+ // found an element to store a offsets[x]
+ offsets[x]++;
+ }
+ stackIdx--;
+ u32 tmp = arr[stack[stackIdx]];
+ while(stackIdx) {
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];
+ stackIdx--;
+ }
+ arr[stack[0]] = tmp;
+ }
+ }
+ }
+
+ // cutoff to shellsort
+ if (digit < cutoff) {
+ // loop on digit values to sort the buckets
+ range(x, stop) {
+ if (counts[x] > RADIX_LEVEL) {
+ if (!digit) {
+ rdxArgs[rdxArgsIdx] = (radixyArgst){.arr=&arr[starts[x]], .size=counts[x], .digit=digit+1, .stackSize=stackSize, .cutoff=cutoff};
+ tpoolAdd(radixyThread, (void*)&rdxArgs[rdxArgsIdx]);
+ rdxArgsIdx++;
+ }
+ else
+ radixy(&arr[starts[x]], counts[x], digit+1, stackSize, cutoff);
+ }
+ else {
+ if (counts[x] < 2) continue;
+ /* ssArgs[ssArgsIdx] = (shellsortArgst){.arr=&arr[starts[x]], .size=counts[x]}; */
+ /* tpoolAdd(shellsortThread, (void*)&ssArgs[ssArgsIdx]); */
+ /* ssArgsIdx++; */
+ shellsort(&arr[starts[x]], counts[x]);
+ }
+ }
+ }
+ else {
+ range(x, stop) {
+ if (counts[x] > 1) {
+ shellsort(&arr[starts[x]], counts[x]);
+ }
+ }
+ }
+ #undef stop
+
+ if (!digit) {
+ tpoolWait;
+ }
+}
+
+void radixyMacro(u32 *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff) {
+ #define stop 256
+ u32 *ar[sizeof(u32)];
+ size_t sizes[sizeof(u32)];
+ u8 *a[sizeof(u32)];
+ size_t counts[sizeof(u32)][stop];
+ size_t offsets[sizeof(u32)][stop];
+ size_t starts[sizeof(u32)][stop];
+ size_t ends[sizeof(u32)][stop];
+ jmp_buf jumpBuffers[sizeof(u32)];
+
+ zeroBuf(counts, sizeof(counts));
+
+ ar[0] = arr;
+ sizes[0] = size;
+
+ radixStart:;
+ a[0] = (u8*) ar[0];
+ size_t digt = sizeof(u32) - digit - 1;
+ // compute counts
+ range(x, sizes[0]) {
+ u8 c = a[0][x * sizeof(u32) + digt];
+ counts[0][c]++;
+ }
+
+ // compute offsets
+ offsets[0][0] = 0;
+ starts[0][0] = 0;
+ rangeFrom(x, 1, stop) {
+ offsets[0][x] = starts[0][x] = ends[0][x-1] = offsets[0][x-1] + counts[0][x-1];
+ }
+ ends[0][stop-1] = sizes[0];
+
+
+ // loop on digit values
+ range(x, stop) {
+ // move records according to digit value
+ while(offsets[0][x] < ends[0][x]) {
+ u8 target = a[0][offsets[0][x] * sizeof(u32) + digt];
+ if (target == x) {
+ // this record already placed in the correct bucket
+ offsets[0][x]++;
+ }
+ else {
+ size_t stackIdx = 0;
+ size_t stack[stackSize];
+ stack[stackIdx++] = offsets[0][x];
+ while(target != x && stackIdx < stackSize) {
+ stack[stackIdx] = offsets[0][target]++;
+ target = a[0][stack[stackIdx] * sizeof(u32) + digt];
+ stackIdx++;
+ }
+ if (stackIdx != stackSize) {
+ // found an element to store a offsets[0][x]
+ offsets[0][x]++;
+ }
+ stackIdx--;
+ u32 tmp = ar[0][stack[stackIdx]];
+ while(stackIdx) {
+ ar[0][stack[stackIdx]] = ar[0][stack[stackIdx-1]];
+ stackIdx--;
+ }
+ ar[0][stack[0]] = tmp;
+ }
+ }
+ }
+
+ // cutoff to shellsort
+ if (digit < cutoff) {
+ // loop on digit values to sort the buckets
+ range(x, stop) {
+ if (counts[0][x] > RADIX_LEVEL) {
+ radixy(&ar[0][starts[0][x]], counts[0][x], digit+1, stackSize, cutoff);
+ }
+ else {
+ if (counts[0][x] < 2) continue;
+ shellsort(&ar[0][starts[0][x]], counts[0][x]);
+ }
+ }
+ }
+ else {
+ range(x, stop) {
+ if (counts[0][x] > 1) {
+ shellsort(&ar[0][starts[0][x]], counts[0][x]);
+ }
+ }
+ }
+ #undef stop
+}
+
+
+// radixy from strings
+internal inline void shellsortS(char **arr, size_t size) {
+ char *tmp; // tmp record
+
+ rangeFrom(i, 3, size) {
+ tmp = arr[i];
+ size_t j;
+ for(j = i ; j >= 3 && strcmp(arr[j-3],tmp) > 0; j-=3) {
+ arr[j] = arr[j-3];
+ }
+ arr[j] = tmp;
+ }
+
+ rangeFrom(i, 1, size) {
+ tmp = arr[i];
+ size_t j;
+ for(j = i ; j >= 1 && strcmp(arr[j-1],tmp) > 0; j--) {
+ arr[j] = arr[j-1];
+ }
+ arr[j] = tmp;
+ }
+}
+
+/**
+ * radixyS doesn't accept empty strings
+ * it segfaults when there is an empty string in the array
+ */
+void radixySOrig(char **arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff) {
+ size_t counts[charStop+1];
+ size_t offsets[charStop+1];
+ size_t starts[charStop+1];
+ size_t ends[charStop+1];
+ size_t digt = digit;
+
+ zeroBuf(counts, sizeof(counts));
+
+ // compute counts
+ range(x, size) {
+ u8 c = *(arr[x]+digt);
+ counts[c]++;
+ }
+
+ // compute offsets
+ offsets[0] = 0;
+ starts[0] = 0;
+ offsets[charStart] = starts[charStart] = ends[0] = offsets[0] + counts[0];
+ rangeFrom(x, charStart+1, charStop+1) {
+ offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];
+ }
+ ends[charStop] = size;
+
+ // sort 0 end of string
+ // move records according to digit value
+ while(offsets[0] < ends[0]) {
+ u8 target = *(arr[offsets[0]] + digt);
+ if (target == 0) {
+ // this record already placed in the correct bucket
+ offsets[0]++;
+ }
+ else {
+ size_t stackIdx = 0;
+ size_t stack[stackSize];
+ stack[stackIdx++] = offsets[0];
+ while(target != 0 && stackIdx < stackSize) {
+ stack[stackIdx] = offsets[target]++;
+ target = *(arr[stack[stackIdx]] + digt);
+ stackIdx++;
+ }
+ if (stackIdx != stackSize) {
+ // found an element to store a offsets[0]
+ offsets[0]++;
+ }
+ stackIdx--;
+ char *tmp = arr[stack[stackIdx]];
+ while(stackIdx) {
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];
+ stackIdx--;
+ }
+ arr[stack[0]] = tmp;
+ }
+ }
+ // loop on digit values
+ rangeFrom(x, charStart, charStop+1) {
+ // move records according to digit value
+ while(offsets[x] < ends[x]) {
+ u8 target = *(arr[offsets[x]] + digt);
+ if (target == x) {
+ // this record already placed in the correct bucket
+ offsets[x]++;
+ }
+ else {
+ size_t stackIdx = 0;
+ size_t stack[stackSize];
+ stack[stackIdx++] = offsets[x];
+ while(target != x && stackIdx < stackSize) {
+ stack[stackIdx] = offsets[target]++;
+ target = *(arr[stack[stackIdx]] + digt);
+ stackIdx++;
+ }
+ if (stackIdx != stackSize) {
+ // found an element to store a offsets[x]
+ offsets[x]++;
+ }
+ stackIdx--;
+ char *tmp = arr[stack[stackIdx]];
+ while(stackIdx) {
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];
+ stackIdx--;
+ }
+ arr[stack[0]] = tmp;
+ }
+ }
+ }
+
+ // cutoff to shellsort
+ if (digit < cutoff) {
+ // sort 0 end of string
+ if (counts[0] > RADIX_LEVEL) {
+ radixySOrig(&arr[starts[0]], counts[0], digit+1, charStart, charStop, stackSize, cutoff);
+ }
+ else {
+ if (counts[0] > 1) shellsortS(&arr[starts[0]], counts[0]);
+ }
+ // loop on digit values to sort the buckets
+ rangeFrom(x, charStart, charStop+1) {
+ if (counts[x] > RADIX_LEVEL) {
+ radixySOrig(&arr[starts[x]], counts[x], digit+1, charStart, charStop, stackSize, cutoff);
+ }
+ else {
+ if (counts[x] < 2) continue;
+ shellsortS(&arr[starts[x]], counts[x]);
+ }
+ }
+ }
+ else {
+ if (counts[0] > 1) {
+ shellsortS(&arr[starts[0]], counts[0]);
+ }
+ rangeFrom(x, charStart, charStop+1) {
+ if (counts[x] > 1) {
+ shellsortS(&arr[starts[x]], counts[x]);
+ }
+ }
+ }
+}
+
+void radixyS(char **arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff);
+
+typ struct {char **arr; size_t size; size_t digit; u8 charStart; u16 charStop; size_t stackSize; size_t cutoff;} radixySArgst;
+
+void radixySThread(void *args) {
+ cast(radixySArgst*, p, args);
+ radixyS(p->arr, p->size, p->digit, p->charStart, p->charStop, p->stackSize, p->cutoff);
+}
+
+// parallel radix sort for string (char*) arrays
+void radixyS(char **arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff) {
+ size_t counts[charStop+1];
+ size_t offsets[charStop+1];
+ size_t starts[charStop+1];
+ size_t ends[charStop+1];
+ size_t digt = digit;
+ radixySArgst rdxArgs[charStop+1];
+ size_t rdxArgsIdx = 0;
+
+ zeroBuf(counts, sizeof(counts));
+
+ // compute counts
+ range(x, size) {
+ u8 c = *(arr[x]+digt);
+ counts[c]++;
+ }
+
+ // compute offsets
+ offsets[0] = 0;
+ starts[0] = 0;
+ offsets[charStart] = starts[charStart] = ends[0] = offsets[0] + counts[0];
+ rangeFrom(x, charStart+1, charStop+1) {
+ offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];
+ }
+ ends[charStop] = size;
+
+ // sort 0 end of string
+ // move records according to digit value
+ while(offsets[0] < ends[0]) {
+ u8 target = *(arr[offsets[0]] + digt);
+ if (target == 0) {
+ // this record already placed in the correct bucket
+ offsets[0]++;
+ }
+ else {
+ size_t stackIdx = 0;
+ size_t stack[stackSize];
+ stack[stackIdx++] = offsets[0];
+ while(target != 0 && stackIdx < stackSize) {
+ stack[stackIdx] = offsets[target]++;
+ target = *(arr[stack[stackIdx]] + digt);
+ stackIdx++;
+ }
+ if (stackIdx != stackSize) {
+ // found an element to store a offsets[0]
+ offsets[0]++;
+ }
+ stackIdx--;
+ char *tmp = arr[stack[stackIdx]];
+ while(stackIdx) {
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];
+ stackIdx--;
+ }
+ arr[stack[0]] = tmp;
+ }
+ }
+ // loop on digit values
+ rangeFrom(x, charStart, charStop+1) {
+ // move records according to digit value
+ while(offsets[x] < ends[x]) {
+ u8 target = *(arr[offsets[x]] + digt);
+ if (target == x) {
+ // this record already placed in the correct bucket
+ offsets[x]++;
+ }
+ else {
+ size_t stackIdx = 0;
+ size_t stack[stackSize];
+ stack[stackIdx++] = offsets[x];
+ while(target != x && stackIdx < stackSize) {
+ stack[stackIdx] = offsets[target]++;
+ target = *(arr[stack[stackIdx]] + digt);
+ stackIdx++;
+ }
+ if (stackIdx != stackSize) {
+ // found an element to store a offsets[x]
+ offsets[x]++;
+ }
+ stackIdx--;
+ char *tmp = arr[stack[stackIdx]];
+ while(stackIdx) {
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];
+ stackIdx--;
+ }
+ arr[stack[0]] = tmp;
+ }
+ }
+ }
+
+ // cutoff to shellsort
+ if (digit < cutoff) {
+ // sort 0 end of string
+ if (counts[0] > RADIX_LEVEL) {
+ if (!digit) {
+ rdxArgs[rdxArgsIdx] = (radixySArgst){.arr=&arr[starts[0]], .size=counts[0], .digit=digit+1, .charStart=charStart, .charStop=charStop, .stackSize=stackSize, .cutoff=cutoff};
+ tpoolAdd(radixySThread, (void*)&rdxArgs[rdxArgsIdx]);
+ rdxArgsIdx++;
+ }
+ else
+ radixyS(&arr[starts[0]], counts[0], digit+1, charStart, charStop, stackSize, cutoff);
+ }
+ else {
+ if (counts[0] > 1) shellsortS(&arr[starts[0]], counts[0]);
+ }
+ // loop on digit values to sort the buckets
+ rangeFrom(x, charStart, charStop+1) {
+ if (counts[x] > RADIX_LEVEL) {
+ if (!digit) {
+ rdxArgs[rdxArgsIdx] = (radixySArgst){.arr=&arr[starts[x]], .size=counts[x], .digit=digit+1, .charStart=charStart, .charStop=charStop, .stackSize=stackSize, .cutoff=cutoff};
+ tpoolAdd(radixySThread, (void*)&rdxArgs[rdxArgsIdx]);
+ rdxArgsIdx++;
+ }
+ else
+ radixyS(&arr[starts[x]], counts[x], digit+1, charStart, charStop, stackSize, cutoff);
+ }
+ else {
+ if (counts[x] < 2) continue;
+ shellsortS(&arr[starts[x]], counts[x]);
+ }
+ }
+ }
+ else {
+ if (counts[0] > 1) {
+ shellsortS(&arr[starts[0]], counts[0]);
+ }
+ rangeFrom(x, charStart, charStop+1) {
+ if (counts[x] > 1) {
+ shellsortS(&arr[starts[x]], counts[x]);
+ }
+ }
+ }
+
+ if (!digit) {
+ tpoolWait;
+ }
+}
+
+
+// u32 array
+#define radixsortAt(ptr) *(ptr)
+radixyUintDef(/*scope*/,radi/*name*/,u32/*elemType*/,6/*stackSize*/,4/*cutoff*/,40/*RADIX_LEVEL*/);
+#undef radixsortAt
+//#define radi
+
+
+// u64 array
+typ struct {u64 a; int b;} rdxElemt;
+#define radixsortAt(ptr) (ptr)->a
+radixyUintThreadDef(/*scope*/,radi64/*name*/,rdxElemt/*elemType*/,6/*stackSize*/,4/*cutoff*/,40/*RADIX_LEVEL*/);
+#undef radixsortAt
+
+// array with string keys
+typ struct {char *a; int b;} skElemt;
+
+#define radixsortAt(ptr) (ptr)->a
+radixyStringThreadDef(/*scope*/,radiS/*name*/,skElemt/*elemType*/,6/*stackSize*/,4/*cutoff*/, 40/*RADIX_LEVEL*/);
+#undef radixsortAt
+
+
+// end radix sort
void trials(void) {
typ struct {i32 a; int b;} elemt;
//#define sz 600000
- #define sz 20
+ #define sz 60
//goto rnd;
+ // radix sort struct array
+ rdxElemt radA[sz];
+ skElemt radS[sz];
+
+
+
+ srandom(10);
+ range(i, ARRAY_SIZE(radA)) {
+ radA[i].a = (u64)random() << 27;
+ radA[i].b = i;
+ radS[i].a = randomS(random()%15+1);
+ radS[i].b = i;
+ /* printf("(%lu,%d) ", radA[i].a, radA[i].b); */
+ printf("(%s,%d) ", radS[i].a, radS[i].b);
+ }
+ put;put;
+
+ radi64(radA, sz);
+ //radiS(radS, sz);
+ if (!radiSSafe(radS, sz)) {
+ logE("Empty strings are not allowed");
+ }
+
+ //XSUCCESS;
+
+ range(i, ARRAY_SIZE(radA)) {
+ /* printf("(%lu,%d) ", radA[i].a, radA[i].b); */
+ printf("(%s,%d) ", radS[i].a, radS[i].b);
+ }
+ put;
+ XSUCCESS;
+
// --------------------------------
// float key array
//
@@ -374,6 +1034,9 @@ rnd:;
u32 urnd[sz];
i64 rnd64[sz];
u64 urnd64[sz];
+ char *list[sz+1];
+ list[sz] = NULL;
+ char **lst = list;
srandom(10);
range(i, ARRAY_SIZE(rnd)) {
@@ -381,14 +1044,22 @@ rnd:;
//rnd[i] = absV((int)randomWordFromHW()) % (ARRAY_SIZE(rnd) *2);
//rnd[i] = random() % (ARRAY_SIZE(rnd) *2);
rnd[i] = (random() - 0x4fffffff) * 2;
- urnd[i] = random() * 2;
+ //urnd[i] = (random() * 2);
+ urnd[i] = random();
+ // string representing a number
+ /* sprintf((char*)&urnd[i], "%d", ARRAY_SIZE(rnd)-i-1); */
+ /* sprintf((char*)&urnd[i], "%c", '0'+ARRAY_SIZE(rnd)-i-1); */
rnd64[i] = random() << 33 + random();
urnd64[i] = random() << 33 + random();
+ /* list[i] = intToS(random()); */
+ list[i] = randomS(random()%15+1);
//printf("%d ", rnd[i]);
//printf("%u ", urnd[i]);
+ //printf("%08x ", urnd[i]);
//printf("%ld ", rnd64[i]);
}
+ /* logVarG(lst); */
put;put
stopwatchStart;
@@ -403,11 +1074,19 @@ rnd:;
//flashsortM(rnd, ARRAY_SIZE(rnd), 0.2 * ARRAY_SIZE(rnd));
//flashsortM(urnd, ARRAY_SIZE(urnd), 0.2 * ARRAY_SIZE(urnd));
//flashsortM(rnd64, ARRAY_SIZE(rnd64), 0.2 * ARRAY_SIZE(rnd64));
- flashsortM(urnd64, ARRAY_SIZE(urnd64), 0.2 * ARRAY_SIZE(urnd64));
+ //flashsortM(urnd64, ARRAY_SIZE(urnd64), 0.2 * ARRAY_SIZE(urnd64));
//flashsort(rnd, ARRAY_SIZE(rnd));
//int *A = rnd;
//flashsort(A, ARRAY_SIZE(rnd));
+ //RadixSort(urnd, sz);
+ //radixSort(urnd, sz);
+ //radixy(urnd, sz, 0 /*digit*/, 6 /*stackSize*/, 4 /*cutoff*/);
+ radi(urnd, sz);
+ //radixyS(lst, sz, 0 /*digit*/, 44 /*start*/, 'z' /*stop*/, 5 /*stackSize*/, 4 /*cutoff*/);
+ //radixyStrTODO(urnd, sz, 0 /* digit */);
+ //sortG(&lst);
+
int cmp(const void *a, const void *b) {
ret CMP(*(int*)a, *(int*)b);
//ret ( *(int*)a - *(int*)b );
@@ -421,16 +1100,41 @@ rnd:;
stopwatchLogUs;
+ // check
+ range(i, sz-1) {
+ if (urnd[i+1] < urnd[i]) {
+ logVarG(i);
+ logVarG(urnd[i]);
+ logVarG(urnd[i+1]);
+ logE("wrong order");
+ /* XFAILURE; */
+ }
+ }
+
+ /* // check */
+ /* range(i, sz-1) { */
+ /* if (strcmp(lst[i+1], lst[i]) < 0) { */
+ /* logVarG(i); */
+ /* logVarG(lst[i]); */
+ /* logVarG(lst[i+1]); */
+ /* logE("wrong order"); */
+ /* } */
+ /* } */
//XSUCCESS;
range(i, ARRAY_SIZE(rnd)) {
/* printf("%d ", rnd[i]); */
- /* printf("%u ", urnd[i]); */
/* printf("%ld ", rnd64[i]); */
- printf("%lu ", urnd64[i]);
+ printf("%u ", urnd[i]);
+ /* printf("%08x ", urnd[i]); */
+ /* printf("%s ", &urnd[i]); */
+ /* printf("%lu ", urnd64[i]); */
}
put;
+ /* logVarG(lst); */
+ // TODO free lst strings
+
/* typeof(convertToUnsignedType(rnd[0])) a = 1; */
/* typeof(convertToUnsignedType(rnd[0])) b = -1; */
/* toUnsignedType((rnd[0])) a = 1; */
diff --git a/package.yml b/package.yml
@@ -1,7 +1,7 @@
---
name: sort
- version: 0.0.1
- description: "sorting algorithms for any type of array: flashsort"
+ version: 0.0.2
+ description: "sorting algorithms for any type of array: radixsort, flashsort"
bin: ./sort.h
cflags: -O3 -std=gnu11 -fPIC -pipe
#lflags: -lpcre
@@ -10,6 +10,8 @@
url: git+https://github.com/RemyNoulin/sort.git
keywords:
- sorting
+ - radixsort
+ - flashsort
- library
author: Remy
license: MIT
diff --git a/radixsort.h b/radixsort.h
@@ -0,0 +1,768 @@
+#pragma once
+
+/**
+ * type safe radix sort
+ *
+ * radix sort sorts keys that are either uint type or string type (char*) keys
+ * radix sort is faster than qsort from glibc and flashsort and takes less memory
+ *
+ * the radixyUintDef, radixyStringDef, radixyUintThreadDef, radixyStringThreadDef define the radix sort functions for arrays with the given element type:
+ *
+ * - shellsort##name or shellsortS##name - internal shell sort function
+ * - radixsort##name or radixsortS##name - function with all the parameters
+ * - name - function only with array and size parameters
+ * - nameSafe - like name and checks if there are empty strings
+ *
+ * the *ThreadDef macros defines threaded radix sort functions
+ *
+ *
+ * Example:
+ *
+ * // sorting array with string keys
+ *
+ * typ struct {char *a; int b;} skElemt;
+ *
+ * // define macro or function for access the key given an address to an element in the array
+ * #define radixsortAt(ptr) (ptr)->a
+ *
+ * // define a radixsort function with name 'radiS' and 'radiSSafe' sorting arrays with skElemt element type
+ * radixyStringDef(,radiS,skElemt,6,4, 40);
+ * #undef radixsortAt
+ *
+ * // the radiSSafe check if there are empty strings (NULL or "") in the keys
+ * // Empty strings are not allowed.
+ *
+ * // declare array
+ * skElemt radS[200];
+ *
+ * // sort the array
+ * radiS(radS, sz);
+ *
+ * // or call safe function:
+ * if (!radiSSafe(radS, sz)) {
+ * logE("Empty strings are not allowed");
+ * }
+ *
+ *
+ *
+ * // sorting a u32 array
+ *
+ * // define macro or function for access the key given an address to an element in the array
+ * #define radixsortAt(ptr) *(ptr)
+ *
+ * // define a radixsort function with name 'radi' sorting u32 arrays
+ * radixyUintDef(, radi , u32, 6, 4, 40);
+ * #undef radixsortAt
+ *
+ * // declare array
+ * u32 urnd[200];
+ *
+ * // sort the array
+ * radi(urnd, 200);
+ *
+ *
+ *
+ * // sorting an array with struct elements
+ *
+ * // declare element type
+ * typ struct {u64 a; int b;} rdxElemt;
+ *
+ * // define macro or function to access the key given an address to an element in the array
+ * #define radixsortAt(ptr) (ptr)->a
+ *
+ * // define a radixsort function with name 'radi64' sorting arrays with elements of type rdxElemt and u64 keys
+ * radixyUintDef(, radi64 , rdxElemt, 6, 4, 40);
+ * #undef radixsortAt
+ *
+ * // declare array
+ * rdxElemt radA[200];
+ *
+ * // sort the array
+ * radi64(radA, 200);
+ *
+ */
+
+// define for internal use in radixyUint
+#define radixyStop 256
+
+/**
+ * radixyUintDef defines functions for sorting arrays of elemType
+ * the keys have to be unsigned int (any size)
+ *
+ * Functions:
+ * - shellsort##name - internal shell sort function
+ * - radixsort##name - function with all the parameters
+ * - name - function only with array and size parameters
+ *
+ * \param
+ * scope is static, internal or empty
+ * \param
+ * name function name for the sort function
+ * \param
+ * stackSizeP is the depth of the look-forward stack
+ * \param
+ * cutoffP is the digit cutoff for switching to shellsort
+ * \param
+ * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort
+ */
+#define radixyUintDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\
+internal inline void shellsort##name(elemType *arr, size_t size) {\
+ typeof(radixsortAt(&arr[0])) tmp; /* tmp key */\
+ typeof(arr[0]) elem; /* tmp record */\
+ \
+ {rangeFrom(i, 3, size) {\
+ tmp = radixsortAt(&arr[i]);\
+ elem = arr[i];\
+ size_t j;\
+ for(j = i ; j >= 3 && radixsortAt(&arr[j-3]) > tmp; j-=3) {\
+ arr[j] = arr[j-3];\
+ }\
+ arr[j] = elem;\
+ }}\
+ \
+ {rangeFrom(i, 1, size) {\
+ tmp = radixsortAt(&arr[i]);\
+ elem = arr[i];\
+ size_t j;\
+ for(j = i ; j >= 1 && radixsortAt(&arr[j-1]) > tmp; j--) {\
+ arr[j] = arr[j-1];\
+ }\
+ arr[j] = elem;\
+ }}\
+}\
+\
+scope void radixsort##name(elemType *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff) {\
+ u8 *a;\
+ size_t counts[radixyStop];\
+ size_t offsets[radixyStop];\
+ size_t starts[radixyStop];\
+ size_t ends[radixyStop];\
+ size_t digt = sizeof(radixsortAt(&arr[0])) - digit - 1;\
+ \
+ zeroBuf(counts, sizeof(counts));\
+ \
+ /* compute counts */\
+ {range(x, size) {\
+ a = (u8*)&radixsortAt(&arr[x]);\
+ u8 c = a[digt];\
+ counts[c]++;\
+ }}\
+ \
+ /* compute offsets */\
+ offsets[0] = 0;\
+ starts[0] = 0;\
+ {rangeFrom(x, 1, radixyStop) {\
+ offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\
+ }}\
+ ends[radixyStop-1] = size;\
+ \
+ \
+ /* loop on digit values */\
+ {range(x, radixyStop) {\
+ /* move records according to digit value */\
+ while(offsets[x] < ends[x]) {\
+ a = (u8*)&radixsortAt(&arr[offsets[x]]);\
+ u8 target = a[digt];\
+ if (target == x) {\
+ /* this record already placed in the correct bucket */\
+ offsets[x]++;\
+ }\
+ else {\
+ size_t stackIdx = 0;\
+ size_t stack[stackSize];\
+ stack[stackIdx++] = offsets[x];\
+ while(target != x && stackIdx < stackSize) {\
+ stack[stackIdx] = offsets[target]++;\
+ a = (u8*)&radixsortAt(&arr[stack[stackIdx]]);\
+ target = a[digt];\
+ stackIdx++;\
+ }\
+ if (stackIdx != stackSize) {\
+ /* found an element to store a offsets[x] */\
+ offsets[x]++;\
+ }\
+ stackIdx--;\
+ var tmp = arr[stack[stackIdx]];\
+ while(stackIdx) {\
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
+ stackIdx--;\
+ }\
+ arr[stack[0]] = tmp;\
+ }\
+ }\
+ }}\
+ \
+ /* cutoff to shellsort */\
+ if (digit < cutoff) {\
+ /* loop on digit values to sort the buckets */\
+ {range(x, radixyStop) {\
+ if (counts[x] > radixLevel) {\
+ radixsort##name(&arr[starts[x]], counts[x], digit+1, stackSize, cutoff);\
+ }\
+ else {\
+ if (counts[x] < 2) continue;\
+ shellsort##name(&arr[starts[x]], counts[x]);\
+ }\
+ }}\
+ }\
+ else {\
+ {range(x, radixyStop) {\
+ if (counts[x] > 1) {\
+ shellsort##name(&arr[starts[x]], counts[x]);\
+ }\
+ }}\
+ }\
+}\
+scope void name(elemType *arr, size_t size) {\
+ radixsort##name(arr, size, 0, stackSizeP, cutoffP);\
+}
+
+
+/**
+ * radixyUintThreadDef (like radixyUintDef) defines functions for sorting arrays of elemType
+ * the keys have to be unsigned int (any size)
+ *
+ * the defined functions by this macro are multithreaded using the threadpool in libsheepy
+ *
+ * Functions:
+ * - shellsort##name - internal shell sort function
+ * - radixsort##name - function with all the parameters
+ * - name - function only with array and size parameters
+ *
+ * \param
+ * scope is static, internal or empty
+ * \param
+ * name function name for the sort function
+ * \param
+ * stackSizeP is the depth of the look-forward stack
+ * \param
+ * cutoffP is the digit cutoff for switching to shellsort
+ * \param
+ * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort
+ */
+#define radixyUintThreadDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\
+internal inline void shellsort##name(elemType *arr, size_t size) {\
+ typeof(radixsortAt(&arr[0])) tmp; /* tmp key */\
+ typeof(arr[0]) elem; /* tmp record */\
+ \
+ {rangeFrom(i, 3, size) {\
+ tmp = radixsortAt(&arr[i]);\
+ elem = arr[i];\
+ size_t j;\
+ for(j = i ; j >= 3 && radixsortAt(&arr[j-3]) > tmp; j-=3) {\
+ arr[j] = arr[j-3];\
+ }\
+ arr[j] = elem;\
+ }}\
+ \
+ {rangeFrom(i, 1, size) {\
+ tmp = radixsortAt(&arr[i]);\
+ elem = arr[i];\
+ size_t j;\
+ for(j = i ; j >= 1 && radixsortAt(&arr[j-1]) > tmp; j--) {\
+ arr[j] = arr[j-1];\
+ }\
+ arr[j] = elem;\
+ }}\
+}\
+\
+scope void radixsort##name(elemType *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff);\
+\
+typ struct {elemType *arr; size_t size; size_t digit; size_t stackSize; size_t cutoff;} radixy##name##Argst;\
+\
+void radixsort##name##Thread(void *args) {\
+ cast(radixy##name##Argst*, p, args);\
+ radixsort##name(p->arr, p->size, p->digit, p->stackSize, p->cutoff);\
+}\
+\
+scope void radixsort##name(elemType *arr, size_t size, size_t digit, size_t stackSize, size_t cutoff) {\
+ u8 *a;\
+ size_t counts[radixyStop];\
+ size_t offsets[radixyStop];\
+ size_t starts[radixyStop];\
+ size_t ends[radixyStop];\
+ size_t digt = sizeof(radixsortAt(&arr[0])) - digit - 1;\
+ radixy##name##Argst rdxArgs[radixyStop]; /* arguments for functions in the threadpool */\
+ size_t rdxArgsIdx = 0;\
+ \
+ zeroBuf(counts, sizeof(counts));\
+ \
+ /* compute counts */\
+ {range(x, size) {\
+ a = (u8*)&radixsortAt(&arr[x]);\
+ u8 c = a[digt];\
+ counts[c]++;\
+ }}\
+ \
+ /* compute offsets */\
+ offsets[0] = 0;\
+ starts[0] = 0;\
+ {rangeFrom(x, 1, radixyStop) {\
+ offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\
+ }}\
+ ends[radixyStop-1] = size;\
+ \
+ \
+ /* loop on digit values */\
+ {range(x, radixyStop) {\
+ /* move records according to digit value */\
+ while(offsets[x] < ends[x]) {\
+ a = (u8*)&radixsortAt(&arr[offsets[x]]);\
+ u8 target = a[digt];\
+ if (target == x) {\
+ /* this record already placed in the correct bucket */\
+ offsets[x]++;\
+ }\
+ else {\
+ size_t stackIdx = 0;\
+ size_t stack[stackSize];\
+ stack[stackIdx++] = offsets[x];\
+ while(target != x && stackIdx < stackSize) {\
+ stack[stackIdx] = offsets[target]++;\
+ a = (u8*)&radixsortAt(&arr[stack[stackIdx]]);\
+ target = a[digt];\
+ stackIdx++;\
+ }\
+ if (stackIdx != stackSize) {\
+ /* found an element to store a offsets[x] */\
+ offsets[x]++;\
+ }\
+ stackIdx--;\
+ var tmp = arr[stack[stackIdx]];\
+ while(stackIdx) {\
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
+ stackIdx--;\
+ }\
+ arr[stack[0]] = tmp;\
+ }\
+ }\
+ }}\
+ \
+ /* cutoff to shellsort */\
+ if (digit < cutoff) {\
+ /* loop on digit values to sort the buckets */\
+ {range(x, radixyStop) {\
+ if (counts[x] > radixLevel) {\
+ if (!digit) {\
+ rdxArgs[rdxArgsIdx] = (radixy##name##Argst){.arr=&arr[starts[x]], .size=counts[x], .digit=digit+1, .stackSize=stackSize, .cutoff=cutoff};\
+ tpoolAdd(radixsort##name##Thread, (void*)&rdxArgs[rdxArgsIdx]);\
+ rdxArgsIdx++;\
+ }\
+ else\
+ radixsort##name(&arr[starts[x]], counts[x], digit+1, stackSize, cutoff);\
+ }\
+ else {\
+ if (counts[x] < 2) continue;\
+ shellsort##name(&arr[starts[x]], counts[x]);\
+ }\
+ }}\
+ }\
+ else {\
+ {range(x, radixyStop) {\
+ if (counts[x] > 1) {\
+ shellsort##name(&arr[starts[x]], counts[x]);\
+ }\
+ }}\
+ }\
+ \
+ if (!digit) {\
+ tpoolWait;\
+ }\
+}\
+scope void name(elemType *arr, size_t size) {\
+ radixsort##name(arr, size, 0, stackSizeP, cutoffP);\
+}
+
+
+/**
+ * radixyStringDef defines functions for sorting arrays of elemType
+ * the keys have to be strings (of type char*) and empty keys (NULL or "") are not allowed (segfaults)
+ *
+ * Functions:
+ * - shellsortS##name - internal shell sort function
+ * - radixsortS##name - function with all the parameters
+ * - name - function only with array and size parameters
+ * - nameSafe - like name and checks if there are empty strings
+ *
+ * \param
+ * scope is static, internal or empty
+ * \param
+ * name function name for the sort function
+ * \param
+ * stackSizeP is the depth of the look-forward stack
+ * \param
+ * cutoffP is the digit cutoff for switching to shellsort
+ * \param
+ * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort
+ */
+#define radixyStringDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\
+internal inline void shellsortS##name(elemType *arr, size_t size) {\
+ char *tmp; /* tmp key */\
+ typeof(arr[0]) elem; /* tmp record */\
+ \
+ {rangeFrom(i, 3, size) {\
+ tmp = radixsortAt(&arr[i]);\
+ elem = arr[i];\
+ size_t j;\
+ for(j = i ; j >= 3 && strcmp(radixsortAt(&arr[j-3]),tmp) > 0; j-=3) {\
+ arr[j] = arr[j-3];\
+ }\
+ arr[j] = elem;\
+ }}\
+ \
+ {rangeFrom(i, 1, size) {\
+ tmp = radixsortAt(&arr[i]);\
+ elem = arr[i];\
+ size_t j;\
+ for(j = i ; j >= 1 && strcmp(radixsortAt(&arr[j-1]),tmp) > 0; j--) {\
+ arr[j] = arr[j-1];\
+ }\
+ arr[j] = elem;\
+ }}\
+}\
+\
+/**
+ * radixyS doesn't accept empty strings
+ * it segfaults when there is an empty string in the array
+ */\
+void radixsortS##name(elemType *arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff) {\
+ size_t counts[charStop+1];\
+ size_t offsets[charStop+1];\
+ size_t starts[charStop+1];\
+ size_t ends[charStop+1];\
+ size_t digt = digit;\
+ \
+ zeroBuf(counts, sizeof(counts));\
+ \
+ /* compute counts */\
+ {range(x, size) {\
+ u8 c = *(radixsortAt(&arr[x])+digt);\
+ counts[c]++;\
+ }}\
+ \
+ /* compute offsets */\
+ offsets[0] = 0;\
+ starts[0] = 0;\
+ offsets[charStart] = starts[charStart] = ends[0] = offsets[0] + counts[0];\
+ rangeFrom(x, charStart+1, charStop+1) {\
+ offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\
+ }\
+ ends[charStop] = size;\
+ \
+ /* sort 0 end of string */\
+ /* move records according to digit value */\
+ while(offsets[0] < ends[0]) {\
+ u8 target = *(radixsortAt(&arr[offsets[0]]) + digt);\
+ if (target == 0) {\
+ /* this record already placed in the correct bucket */\
+ offsets[0]++;\
+ }\
+ else {\
+ size_t stackIdx = 0;\
+ size_t stack[stackSize];\
+ stack[stackIdx++] = offsets[0];\
+ while(target != 0 && stackIdx < stackSize) {\
+ stack[stackIdx] = offsets[target]++;\
+ target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\
+ stackIdx++;\
+ }\
+ if (stackIdx != stackSize) {\
+ /* found an element to store a offsets[0] */\
+ offsets[0]++;\
+ }\
+ stackIdx--;\
+ var tmp = arr[stack[stackIdx]];\
+ while(stackIdx) {\
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
+ stackIdx--;\
+ }\
+ arr[stack[0]] = tmp;\
+ }\
+ }\
+ /* loop on digit values */\
+ {rangeFrom(x, charStart, charStop+1) {\
+ /* move records according to digit value */\
+ while(offsets[x] < ends[x]) {\
+ u8 target = *(radixsortAt(&arr[offsets[x]]) + digt);\
+ if (target == x) {\
+ /* this record already placed in the correct bucket */\
+ offsets[x]++;\
+ }\
+ else {\
+ size_t stackIdx = 0;\
+ size_t stack[stackSize];\
+ stack[stackIdx++] = offsets[x];\
+ while(target != x && stackIdx < stackSize) {\
+ stack[stackIdx] = offsets[target]++;\
+ target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\
+ stackIdx++;\
+ }\
+ if (stackIdx != stackSize) {\
+ /* found an element to store a offsets[x] */\
+ offsets[x]++;\
+ }\
+ stackIdx--;\
+ var tmp = arr[stack[stackIdx]];\
+ while(stackIdx) {\
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
+ stackIdx--;\
+ }\
+ arr[stack[0]] = tmp;\
+ }\
+ }\
+ }}\
+ \
+ /* cutoff to shellsort */\
+ if (digit < cutoff) {\
+ /* sort 0 end of string */\
+ if (counts[0] > radixLevel) {\
+ radixsortS##name(&arr[starts[0]], counts[0], digit+1, charStart, charStop, stackSize, cutoff);\
+ }\
+ else {\
+ if (counts[0] > 1) shellsortS##name(&arr[starts[0]], counts[0]);\
+ }\
+ /* loop on digit values to sort the buckets */\
+ {rangeFrom(x, charStart, charStop+1) {\
+ if (counts[x] > radixLevel) {\
+ radixsortS##name(&arr[starts[x]], counts[x], digit+1, charStart, charStop, stackSize, cutoff);\
+ }\
+ else {\
+ if (counts[x] < 2) continue;\
+ shellsortS##name(&arr[starts[x]], counts[x]);\
+ }\
+ }}\
+ }\
+ else {\
+ if (counts[0] > 1) {\
+ shellsortS##name(&arr[starts[0]], counts[0]);\
+ }\
+ rangeFrom(x, charStart, charStop+1) {\
+ if (counts[x] > 1) {\
+ shellsortS##name(&arr[starts[x]], counts[x]);\
+ }\
+ }\
+ }\
+}\
+scope void name(elemType *arr, size_t size) {\
+ radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\
+}\
+scope bool name##Safe(elemType *arr, size_t size) {\
+ {range(i, size) {\
+ if (isEmptyS(radixsortAt(&arr[i]))) ret false;\
+ }}\
+ radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\
+ ret true;\
+}
+
+
+
+/**
+ * radixyStringThreadDef (like radixyStringDef) defines functions for sorting arrays of elemType
+ * the keys have to be strings (of type char*) and empty keys (NULL or "") are not allowed (segfaults)
+ *
+ * the defined functions by this macro are multithreaded using the threadpool in libsheepy
+ *
+ * Functions:
+ * - shellsortS##name - internal shell sort function
+ * - radixsortS##name - function with all the parameters
+ * - name - function only with array and size parameters
+ * - nameSafe - like name and checks if there are empty strings
+ *
+ * \param
+ * scope is static, internal or empty
+ * \param
+ * name function name for the sort function
+ * \param
+ * stackSizeP is the depth of the look-forward stack
+ * \param
+ * cutoffP is the digit cutoff for switching to shellsort
+ * \param
+ * radixLevel is minimun element count in a bucket for running radix sort, otherwise run shellsort
+ */
+#define radixyStringThreadDef(scope, name, elemType, stackSizeP, cutoffP, radixLevel)\
+internal inline void shellsortS##name(elemType *arr, size_t size) {\
+ char *tmp; /* tmp key */\
+ typeof(arr[0]) elem; /* tmp record */\
+ \
+ {rangeFrom(i, 3, size) {\
+ tmp = radixsortAt(&arr[i]);\
+ elem = arr[i];\
+ size_t j;\
+ for(j = i ; j >= 3 && strcmp(radixsortAt(&arr[j-3]),tmp) > 0; j-=3) {\
+ arr[j] = arr[j-3];\
+ }\
+ arr[j] = elem;\
+ }}\
+ \
+ {rangeFrom(i, 1, size) {\
+ tmp = radixsortAt(&arr[i]);\
+ elem = arr[i];\
+ size_t j;\
+ for(j = i ; j >= 1 && strcmp(radixsortAt(&arr[j-1]),tmp) > 0; j--) {\
+ arr[j] = arr[j-1];\
+ }\
+ arr[j] = elem;\
+ }}\
+}\
+\
+void radixsortS##name(elemType *arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff);\
+\
+typ struct {elemType *arr; size_t size; size_t digit; u8 charStart; u16 charStop; size_t stackSize; size_t cutoff;} radixyS##name##Argst;\
+\
+void radixsortS##name##Thread(void *args) {\
+ cast(radixyS##name##Argst*, p, args);\
+ radixsortS##name(p->arr, p->size, p->digit, p->charStart, p->charStop, p->stackSize, p->cutoff);\
+}\
+\
+/**
+ * radixyS doesn't accept empty strings
+ * it segfaults when there is an empty string in the array
+ */\
+void radixsortS##name(elemType *arr, size_t size, size_t digit, u8 charStart, u16 charStop, size_t stackSize, size_t cutoff) {\
+ size_t counts[charStop+1];\
+ size_t offsets[charStop+1];\
+ size_t starts[charStop+1];\
+ size_t ends[charStop+1];\
+ size_t digt = digit;\
+ radixyS##name##Argst rdxArgs[charStop+1]; /* arguments for functions in the threadpool */\
+ size_t rdxArgsIdx = 0;\
+ \
+ zeroBuf(counts, sizeof(counts));\
+ \
+ /* compute counts */\
+ {range(x, size) {\
+ u8 c = *(radixsortAt(&arr[x])+digt);\
+ counts[c]++;\
+ }}\
+ \
+ /* compute offsets */\
+ offsets[0] = 0;\
+ starts[0] = 0;\
+ offsets[charStart] = starts[charStart] = ends[0] = offsets[0] + counts[0];\
+ rangeFrom(x, charStart+1, charStop+1) {\
+ offsets[x] = starts[x] = ends[x-1] = offsets[x-1] + counts[x-1];\
+ }\
+ ends[charStop] = size;\
+ \
+ /* sort 0 end of string */\
+ /* move records according to digit value */\
+ while(offsets[0] < ends[0]) {\
+ u8 target = *(radixsortAt(&arr[offsets[0]]) + digt);\
+ if (target == 0) {\
+ /* this record already placed in the correct bucket */\
+ offsets[0]++;\
+ }\
+ else {\
+ size_t stackIdx = 0;\
+ size_t stack[stackSize];\
+ stack[stackIdx++] = offsets[0];\
+ while(target != 0 && stackIdx < stackSize) {\
+ stack[stackIdx] = offsets[target]++;\
+ target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\
+ stackIdx++;\
+ }\
+ if (stackIdx != stackSize) {\
+ /* found an element to store a offsets[0] */\
+ offsets[0]++;\
+ }\
+ stackIdx--;\
+ var tmp = arr[stack[stackIdx]];\
+ while(stackIdx) {\
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
+ stackIdx--;\
+ }\
+ arr[stack[0]] = tmp;\
+ }\
+ }\
+ /* loop on digit values */\
+ {rangeFrom(x, charStart, charStop+1) {\
+ /* move records according to digit value */\
+ while(offsets[x] < ends[x]) {\
+ u8 target = *(radixsortAt(&arr[offsets[x]]) + digt);\
+ if (target == x) {\
+ /* this record already placed in the correct bucket */\
+ offsets[x]++;\
+ }\
+ else {\
+ size_t stackIdx = 0;\
+ size_t stack[stackSize];\
+ stack[stackIdx++] = offsets[x];\
+ while(target != x && stackIdx < stackSize) {\
+ stack[stackIdx] = offsets[target]++;\
+ target = *(radixsortAt(&arr[stack[stackIdx]]) + digt);\
+ stackIdx++;\
+ }\
+ if (stackIdx != stackSize) {\
+ /* found an element to store a offsets[x] */\
+ offsets[x]++;\
+ }\
+ stackIdx--;\
+ var tmp = arr[stack[stackIdx]];\
+ while(stackIdx) {\
+ arr[stack[stackIdx]] = arr[stack[stackIdx-1]];\
+ stackIdx--;\
+ }\
+ arr[stack[0]] = tmp;\
+ }\
+ }\
+ }}\
+ \
+ /* cutoff to shellsort */\
+ if (digit < cutoff) {\
+ /* sort 0 end of string */\
+ if (counts[0] > radixLevel) {\
+ if (!digit) {\
+ rdxArgs[rdxArgsIdx] = (radixyS##name##Argst){.arr=&arr[starts[0]], .size=counts[0], .digit=digit+1, .charStart=charStart, .charStop=charStop, .stackSize=stackSize, .cutoff=cutoff};\
+ tpoolAdd(radixsortS##name##Thread, (void*)&rdxArgs[rdxArgsIdx]);\
+ rdxArgsIdx++;\
+ }\
+ else\
+ radixsortS##name(&arr[starts[0]], counts[0], digit+1, charStart, charStop, stackSize, cutoff);\
+ }\
+ else {\
+ if (counts[0] > 1) shellsortS##name(&arr[starts[0]], counts[0]);\
+ }\
+ /* loop on digit values to sort the buckets */\
+ {rangeFrom(x, charStart, charStop+1) {\
+ if (counts[x] > radixLevel) {\
+ if (!digit) {\
+ rdxArgs[rdxArgsIdx] = (radixyS##name##Argst){.arr=&arr[starts[x]], .size=counts[x], .digit=digit+1, .charStart=charStart, .charStop=charStop, .stackSize=stackSize, .cutoff=cutoff};\
+ tpoolAdd(radixsortS##name##Thread, (void*)&rdxArgs[rdxArgsIdx]);\
+ rdxArgsIdx++;\
+ }\
+ else\
+ radixsortS##name(&arr[starts[x]], counts[x], digit+1, charStart, charStop, stackSize, cutoff);\
+ }\
+ else {\
+ if (counts[x] < 2) continue;\
+ shellsortS##name(&arr[starts[x]], counts[x]);\
+ }\
+ }}\
+ }\
+ else {\
+ if (counts[0] > 1) {\
+ shellsortS##name(&arr[starts[0]], counts[0]);\
+ }\
+ rangeFrom(x, charStart, charStop+1) {\
+ if (counts[x] > 1) {\
+ shellsortS##name(&arr[starts[x]], counts[x]);\
+ }\
+ }\
+ }\
+ \
+ if (!digit) {\
+ tpoolWait;\
+ }\
+}\
+scope void name(elemType *arr, size_t size) {\
+ radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\
+}\
+scope bool name##Safe(elemType *arr, size_t size) {\
+ {range(i, size) {\
+ if (isEmptyS(radixsortAt(&arr[i]))) ret false;\
+ }}\
+ radixsortS##name(arr, size, 0, 32, 255, stackSizeP, cutoffP);\
+ ret true;\
+}
+
+// vim: set expandtab ts=2 sw=2:
diff --git a/sort.h b/sort.h
@@ -1,3 +1,4 @@
#pragma once
#include "flashsort.h"
+#include "radixsort.h"
