--- a/include/stdlib.h +++ b/include/stdlib.h @@ -52,10 +52,13 @@ char *getenv (const char *); int system (const char *); +typedef int (*__compar_fn_t)(const void *, const void *); +typedef int (*comparison_fn_t)(const void *, const void *); void *bsearch (const void *, const void *, size_t, size_t, int (*)(const void *, const void *)); void qsort (void *, size_t, size_t, int (*)(const void *, const void *)); +void qsort_r (void *, size_t, size_t, int (*)(const void *, const void *, void *), void *); int abs (int); long labs (long); long long llabs (long long); --- a/src/stdlib/qsort.c 2017-01-01 04:27:17.000000000 +0100 +++ b/src/stdlib/qsort.c 2017-01-29 00:21:27.194887091 +0100 @@ -28,7 +28,7 @@ #include "atomic.h" #define ntz(x) a_ctz_l((x)) -typedef int (*cmpfun)(const void *, const void *); +typedef int (*cmpfun)(const void *, const void *, void *); static inline int pntz(size_t p[2]) { int r = ntz(p[0] - 1); @@ -85,7 +85,7 @@ p[1] >>= n; } -static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshift, size_t lp[]) +static void sift(unsigned char *head, size_t width, cmpfun cmp, void* arg, int pshift, size_t lp[]) { unsigned char *rt, *lf; unsigned char *ar[14 * sizeof(size_t) + 1]; @@ -96,10 +96,10 @@ rt = head - width; lf = head - width - lp[pshift - 2]; - if((*cmp)(ar[0], lf) >= 0 && (*cmp)(ar[0], rt) >= 0) { + if((*cmp)(ar[0], lf, arg) >= 0 && (*cmp)(ar[0], rt, arg) >= 0) { break; } - if((*cmp)(lf, rt) >= 0) { + if((*cmp)(lf, rt, arg) >= 0) { ar[i++] = lf; head = lf; pshift -= 1; @@ -112,7 +112,7 @@ cycle(width, ar, i); } -static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2], int pshift, int trusty, size_t lp[]) +static void trinkle(unsigned char *head, size_t width, cmpfun cmp, void* arg, size_t pp[2], int pshift, int trusty, size_t lp[]) { unsigned char *stepson, *rt, *lf; @@ -127,13 +127,13 @@ ar[0] = head; while(p[0] != 1 || p[1] != 0) { stepson = head - lp[pshift]; - if((*cmp)(stepson, ar[0]) <= 0) { + if((*cmp)(stepson, ar[0], arg) <= 0) { break; } if(!trusty && pshift > 1) { rt = head - width; lf = head - width - lp[pshift - 2]; - if((*cmp)(rt, stepson) >= 0 || (*cmp)(lf, stepson) >= 0) { + if((*cmp)(rt, stepson, arg) >= 0 || (*cmp)(lf, stepson, arg) >= 0) { break; } } @@ -147,11 +147,11 @@ } if(!trusty) { cycle(width, ar, i); - sift(head, width, cmp, pshift, lp); + sift(head, width, cmp, arg, pshift, lp); } } -void qsort(void *base, size_t nel, size_t width, cmpfun cmp) +void qsort_r(void *base, size_t nel, size_t width, cmpfun cmp, void* arg) { size_t lp[12*sizeof(size_t)]; size_t i, size = width * nel; @@ -170,14 +170,14 @@ while(head < high) { if((p[0] & 3) == 3) { - sift(head, width, cmp, pshift, lp); + sift(head, width, cmp, arg, pshift, lp); shr(p, 2); pshift += 2; } else { if(lp[pshift - 1] >= high - head) { - trinkle(head, width, cmp, p, pshift, 0, lp); + trinkle(head, width, cmp, arg, p, pshift, 0, lp); } else { - sift(head, width, cmp, pshift, lp); + sift(head, width, cmp, arg, pshift, lp); } if(pshift == 1) { @@ -193,7 +193,7 @@ head += width; } - trinkle(head, width, cmp, p, pshift, 0, lp); + trinkle(head, width, cmp, arg, p, pshift, 0, lp); while(pshift != 1 || p[0] != 1 || p[1] != 0) { if(pshift <= 1) { @@ -205,11 +205,16 @@ pshift -= 2; p[0] ^= 7; shr(p, 1); - trinkle(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, lp); + trinkle(head - lp[pshift] - width, width, cmp, arg, p, pshift + 1, 1, lp); shl(p, 1); p[0] |= 1; - trinkle(head - width, width, cmp, p, pshift, 1, lp); + trinkle(head - width, width, cmp, arg, p, pshift, 1, lp); } head -= width; } } + +void qsort(void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *)) +{ + return qsort_r (base, nel, width, (cmpfun)cmp, NULL); +}