ref: 5c448c618a89ab8933838da1b5b97ed7c4a42e08
dir: /sys/src/ape/lib/ap/gen/qsort.c/
/* qsort -- qsort interface implemented by faster quicksort */ #include <stdlib.h> #define SWAPINIT(a, es) swaptype = \ (a - (char*) 0) % sizeof(long) || es % sizeof(long) ? 2 : \ es == sizeof(long) ? 0 : 1; #define swapcode(TYPE, parmi, parmj, n) { \ long i = (n) / (int) sizeof(TYPE); \ register TYPE *pi = (TYPE *) (parmi); \ register TYPE *pj = (TYPE *) (parmj); \ do { \ register TYPE t = *pi; \ *pi++ = *pj; \ *pj++ = t; \ } while (--i > 0); \ } static void swapfunc(char *a, char *b, int n, int swaptype) { if (swaptype <= 1) swapcode(long, a, b, n) else swapcode(char, a, b, n) } #define swap(a, b) { \ if (swaptype == 0) { \ long t = * (long *) (a); \ * (long *) (a) = * (long *) (b); \ * (long *) (b) = t; \ } else \ swapfunc(a, b, es, swaptype); \ } #define vecswap(a, b, n) { if (n > 0) swapfunc(a, b, n*es, swaptype); } static char *med3func(char *a, char *b, char *c, int (*cmp)(const void *, const void *)) { return cmp(a, b) < 0 ? (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ) ) : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ) ); } #define med3(a, b, c) med3func(a, b, c, cmp) void qsort(void *va, size_t n, size_t es, int (*cmp)(const void *, const void *)) { char *a, *pa, *pb, *pc, *pd, *pl, *pm, *pn; int r, swaptype, na, nb, nc, nd, d; a = va; SWAPINIT(a, es); if (n < 7) { /* Insertion sort on small arrays */ for (pm = a + es; pm < a + n*es; pm += es) for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es) swap(pl, pl-es); return; } pm = a + (n/2) * es; if (n > 7) { pl = a; pn = a + (n-1) * es; if (n > 40) { /* On big arrays, pseudomedian of 9 */ d = (n/8) * es; pl = med3(pl, pl+d, pl+2*d); pm = med3(pm-d, pm, pm+d); pn = med3(pn-2*d, pn-d, pn); } pm = med3(pl, pm, pn); /* On medium arrays, median of 3 */ } swap(a, pm); /* On tiny arrays, partition around middle */ pa = pb = a + es; pc = pd = pn = a + (n-1)*es; for (;;) { while (pb <= pc && (r = cmp(pb, a)) <= 0) { if (r == 0) { swap(pa, pb); pa += es; } pb += es; } while (pb <= pc && (r = cmp(pc, a)) >= 0) { if (r == 0) { swap(pc, pd); pd -= es; } pc -= es; } if (pb > pc) break; swap(pb, pc); pb += es; pc -= es; } na = (pa - a) / es; nb = (pb - pa) / es; nc = (pd - pc) / es; nd = (pn - pd) / es; if (na < nb) { vecswap(a, a + nb*es, na); } else { vecswap(a, a + na*es, nb); } if (nc < nd) { vecswap(pb, pb + nd*es, nc); } else { vecswap(pb, pb + nc*es, nd); } if (nb > 1) qsort(a, nb, es, cmp); if (nc > 1) qsort(a + (n-nc) * es, nc, es, cmp); }