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
swapfunc(a,b,n,swaptype)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 *
med3(a,b,c,cmp)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
qsort(a,n,es,cmp)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