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