1*3e12c5d1SDavid du Colombier /* qsort -- qsort interface implemented by faster quicksort */
2*3e12c5d1SDavid du Colombier #include <stdlib.h>
3*3e12c5d1SDavid du Colombier
4*3e12c5d1SDavid du Colombier #define SWAPINIT(a, es) swaptype = \
5*3e12c5d1SDavid du Colombier (a - (char*) 0) % sizeof(long) || es % sizeof(long) ? 2 : \
6*3e12c5d1SDavid du Colombier es == sizeof(long) ? 0 : 1;
7*3e12c5d1SDavid du Colombier #define swapcode(TYPE, parmi, parmj, n) { \
8*3e12c5d1SDavid du Colombier long i = (n) / (int) sizeof(TYPE); \
9*3e12c5d1SDavid du Colombier register TYPE *pi = (TYPE *) (parmi); \
10*3e12c5d1SDavid du Colombier register TYPE *pj = (TYPE *) (parmj); \
11*3e12c5d1SDavid du Colombier do { \
12*3e12c5d1SDavid du Colombier register TYPE t = *pi; \
13*3e12c5d1SDavid du Colombier *pi++ = *pj; \
14*3e12c5d1SDavid du Colombier *pj++ = t; \
15*3e12c5d1SDavid du Colombier } while (--i > 0); \
16*3e12c5d1SDavid du Colombier }
swapfunc(char * a,char * b,int n,int swaptype)17*3e12c5d1SDavid du Colombier static void swapfunc(char *a, char *b, int n, int swaptype)
18*3e12c5d1SDavid du Colombier { if (swaptype <= 1) swapcode(long, a, b, n)
19*3e12c5d1SDavid du Colombier else swapcode(char, a, b, n)
20*3e12c5d1SDavid du Colombier }
21*3e12c5d1SDavid du Colombier #define swap(a, b) { \
22*3e12c5d1SDavid du Colombier if (swaptype == 0) { \
23*3e12c5d1SDavid du Colombier long t = * (long *) (a); \
24*3e12c5d1SDavid du Colombier * (long *) (a) = * (long *) (b); \
25*3e12c5d1SDavid du Colombier * (long *) (b) = t; \
26*3e12c5d1SDavid du Colombier } else \
27*3e12c5d1SDavid du Colombier swapfunc(a, b, es, swaptype); \
28*3e12c5d1SDavid du Colombier }
29*3e12c5d1SDavid du Colombier #define vecswap(a, b, n) { if (n > 0) swapfunc(a, b, n*es, swaptype); }
30*3e12c5d1SDavid du Colombier
med3func(char * a,char * b,char * c,int (* cmp)(const void *,const void *))31*3e12c5d1SDavid du Colombier static char *med3func(char *a, char *b, char *c, int (*cmp)(const void *, const void *))
32*3e12c5d1SDavid du Colombier { return cmp(a, b) < 0 ?
33*3e12c5d1SDavid du Colombier (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ) )
34*3e12c5d1SDavid du Colombier : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ) );
35*3e12c5d1SDavid du Colombier }
36*3e12c5d1SDavid du Colombier #define med3(a, b, c) med3func(a, b, c, cmp)
37*3e12c5d1SDavid du Colombier
qsort(void * va,size_t n,size_t es,int (* cmp)(const void *,const void *))38*3e12c5d1SDavid du Colombier void qsort(void *va, size_t n, size_t es, int (*cmp)(const void *, const void *))
39*3e12c5d1SDavid du Colombier {
40*3e12c5d1SDavid du Colombier char *a, *pa, *pb, *pc, *pd, *pl, *pm, *pn;
41*3e12c5d1SDavid du Colombier int r, swaptype, na, nb, nc, nd, d;
42*3e12c5d1SDavid du Colombier
43*3e12c5d1SDavid du Colombier a = va;
44*3e12c5d1SDavid du Colombier SWAPINIT(a, es);
45*3e12c5d1SDavid du Colombier if (n < 7) { /* Insertion sort on small arrays */
46*3e12c5d1SDavid du Colombier for (pm = a + es; pm < a + n*es; pm += es)
47*3e12c5d1SDavid du Colombier for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
48*3e12c5d1SDavid du Colombier swap(pl, pl-es);
49*3e12c5d1SDavid du Colombier return;
50*3e12c5d1SDavid du Colombier }
51*3e12c5d1SDavid du Colombier pm = a + (n/2) * es;
52*3e12c5d1SDavid du Colombier if (n > 7) {
53*3e12c5d1SDavid du Colombier pl = a;
54*3e12c5d1SDavid du Colombier pn = a + (n-1) * es;
55*3e12c5d1SDavid du Colombier if (n > 40) { /* On big arrays, pseudomedian of 9 */
56*3e12c5d1SDavid du Colombier d = (n/8) * es;
57*3e12c5d1SDavid du Colombier pl = med3(pl, pl+d, pl+2*d);
58*3e12c5d1SDavid du Colombier pm = med3(pm-d, pm, pm+d);
59*3e12c5d1SDavid du Colombier pn = med3(pn-2*d, pn-d, pn);
60*3e12c5d1SDavid du Colombier }
61*3e12c5d1SDavid du Colombier pm = med3(pl, pm, pn); /* On medium arrays, median of 3 */
62*3e12c5d1SDavid du Colombier }
63*3e12c5d1SDavid du Colombier swap(a, pm); /* On tiny arrays, partition around middle */
64*3e12c5d1SDavid du Colombier pa = pb = a + es;
65*3e12c5d1SDavid du Colombier pc = pd = pn = a + (n-1)*es;
66*3e12c5d1SDavid du Colombier for (;;) {
67*3e12c5d1SDavid du Colombier while (pb <= pc && (r = cmp(pb, a)) <= 0) {
68*3e12c5d1SDavid du Colombier if (r == 0) { swap(pa, pb); pa += es; }
69*3e12c5d1SDavid du Colombier pb += es;
70*3e12c5d1SDavid du Colombier }
71*3e12c5d1SDavid du Colombier while (pb <= pc && (r = cmp(pc, a)) >= 0) {
72*3e12c5d1SDavid du Colombier if (r == 0) { swap(pc, pd); pd -= es; }
73*3e12c5d1SDavid du Colombier pc -= es;
74*3e12c5d1SDavid du Colombier }
75*3e12c5d1SDavid du Colombier if (pb > pc) break;
76*3e12c5d1SDavid du Colombier swap(pb, pc);
77*3e12c5d1SDavid du Colombier pb += es;
78*3e12c5d1SDavid du Colombier pc -= es;
79*3e12c5d1SDavid du Colombier }
80*3e12c5d1SDavid du Colombier na = (pa - a) / es;
81*3e12c5d1SDavid du Colombier nb = (pb - pa) / es;
82*3e12c5d1SDavid du Colombier nc = (pd - pc) / es;
83*3e12c5d1SDavid du Colombier nd = (pn - pd) / es;
84*3e12c5d1SDavid du Colombier if (na < nb) { vecswap(a, a + nb*es, na); }
85*3e12c5d1SDavid du Colombier else { vecswap(a, a + na*es, nb); }
86*3e12c5d1SDavid du Colombier if (nc < nd) { vecswap(pb, pb + nd*es, nc); }
87*3e12c5d1SDavid du Colombier else { vecswap(pb, pb + nc*es, nd); }
88*3e12c5d1SDavid du Colombier if (nb > 1) qsort(a, nb, es, cmp);
89*3e12c5d1SDavid du Colombier if (nc > 1) qsort(a + (n-nc) * es, nc, es, cmp);
90*3e12c5d1SDavid du Colombier }
91