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