1 /* 2 * Copyright (c) 1992 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * 6 * %sccs.include.redist.c% 7 */ 8 9 10 #ifndef lint 11 static char copyright[] = 12 "@(#) Copyright (c) 1992 The Regents of the University of California.\n\ 13 All rights reserved.\n"; 14 #endif /* not lint */ 15 16 #ifndef lint 17 static char sccsid[] = "@(#)qsort.c 5.11 (Berkeley) 12/10/92"; 18 #endif /* not lint */ 19 20 #include <sys/types.h> 21 22 static char *med3 __P((char *, char *, char *, int (*)())); 23 static void swapfunc __P((char *, char *, int, int)); 24 25 #define min(a, b) (a) < (b) ? a : b 26 27 /* 28 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". 29 */ 30 #define swapcode(TYPE, parmi, parmj, n) { \ 31 long i = (n) / sizeof (TYPE); \ 32 register TYPE *pi = (TYPE *) (parmi); \ 33 register TYPE *pj = (TYPE *) (parmj); \ 34 do { \ 35 register TYPE t = *pi; \ 36 *pi++ = *pj; \ 37 *pj++ = t; \ 38 } while (--i > 0); \ 39 } 40 41 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ 42 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; 43 44 static void 45 swapfunc(a, b, n, swaptype) 46 char *a, *b; 47 int n, swaptype; 48 { 49 if(swaptype <= 1) 50 swapcode(long, a, b, n) 51 else 52 swapcode(char, a, b, n) 53 } 54 55 #define swap(a, b) \ 56 if (swaptype == 0) { \ 57 long t = *(long *)(a); \ 58 *(long *)(a) = *(long *)(b); \ 59 *(long *)(b) = t; \ 60 } else \ 61 swapfunc(a, b, es, swaptype) 62 63 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) 64 65 static char * 66 med3(a, b, c, cmp) 67 char *a, *b, *c; 68 int (*cmp)(); 69 { 70 return cmp(a, b) < 0 ? 71 (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) 72 :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); 73 } 74 75 void 76 qsort(a, n, es, cmp) 77 void *a; 78 size_t n, es; 79 int (*cmp)(); 80 { 81 char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 82 int d, r, swaptype, swap_cnt; 83 84 loop: SWAPINIT(a, es); 85 swap_cnt = 0; 86 if (n < 7) { 87 for (pm = a + es; pm < (char *) a + n * es; pm += es) 88 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 89 pl -= es) 90 swap(pl, pl - es); 91 return; 92 } 93 pm = a + (n / 2) * es; 94 if (n > 7) { 95 pl = a; 96 pn = a + (n - 1) * es; 97 if (n > 40) { 98 d = (n / 8) * es; 99 pl = med3(pl, pl + d, pl + 2 * d, cmp); 100 pm = med3(pm - d, pm, pm + d, cmp); 101 pn = med3(pn - 2 * d, pn - d, pn, cmp); 102 } 103 pm = med3(pl, pm, pn, cmp); 104 } 105 swap(a, pm); 106 pa = pb = a + es; 107 108 pc = pd = a + (n - 1) * es; 109 for (;;) { 110 while (pb <= pc && (r = cmp(pb, a)) <= 0) { 111 if (r == 0) { 112 swap_cnt = 1; 113 swap(pa, pb); 114 pa += es; 115 } 116 pb += es; 117 } 118 while (pb <= pc && (r = cmp(pc, a)) >= 0) { 119 if (r == 0) { 120 swap_cnt = 1; 121 swap(pc, pd); 122 pd -= es; 123 } 124 pc -= es; 125 } 126 if (pb > pc) 127 break; 128 swap(pb, pc); 129 swap_cnt = 1; 130 pb += es; 131 pc -= es; 132 } 133 if (swap_cnt == 0) { /* Switch to insertion sort */ 134 for (pm = a + es; pm < (char *) a + n * es; pm += es) 135 for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 136 pl -= es) 137 swap(pl, pl - es); 138 return; 139 } 140 141 pn = a + n * es; 142 r = min(pa - (char *)a, pb - pa); 143 vecswap(a, pb - r, r); 144 r = min(pd - pc, pn - pd - es); 145 vecswap(pb, pn - r, r); 146 if ((r = pb - pa) > es) { 147 /* 148 * To decrease the stack space we iterate here rather than 149 * recurse. 150 */ 151 n = r / es; 152 goto loop; 153 } 154 if ((r = pd - pc) > es) 155 nqsort(pn - r, r / es, es, cmp); 156 } 157 158