1 /*
2 * qsort -- simple quicksort
3 */
4
5 #include <u.h>
6
7 typedef
8 struct
9 {
10 int (*cmp)(void*, void*);
11 void (*swap)(char*, char*, long);
12 long es;
13 } Sort;
14
15 static void
swapb(char * i,char * j,long es)16 swapb(char *i, char *j, long es)
17 {
18 char c;
19
20 do {
21 c = *i;
22 *i++ = *j;
23 *j++ = c;
24 es--;
25 } while(es != 0);
26
27 }
28
29 static void
swapi(char * ii,char * ij,long es)30 swapi(char *ii, char *ij, long es)
31 {
32 long *i, *j, c;
33
34 i = (long*)ii;
35 j = (long*)ij;
36 do {
37 c = *i;
38 *i++ = *j;
39 *j++ = c;
40 es -= sizeof(long);
41 } while(es != 0);
42 }
43
44 static char*
pivot(char * a,long n,Sort * p)45 pivot(char *a, long n, Sort *p)
46 {
47 long j;
48 char *pi, *pj, *pk;
49
50 j = n/6 * p->es;
51 pi = a + j; /* 1/6 */
52 j += j;
53 pj = pi + j; /* 1/2 */
54 pk = pj + j; /* 5/6 */
55 if(p->cmp(pi, pj) < 0) {
56 if(p->cmp(pi, pk) < 0) {
57 if(p->cmp(pj, pk) < 0)
58 return pj;
59 return pk;
60 }
61 return pi;
62 }
63 if(p->cmp(pj, pk) < 0) {
64 if(p->cmp(pi, pk) < 0)
65 return pi;
66 return pk;
67 }
68 return pj;
69 }
70
71 static void
qsorts(char * a,long n,Sort * p)72 qsorts(char *a, long n, Sort *p)
73 {
74 long j, es;
75 char *pi, *pj, *pn;
76
77 es = p->es;
78 while(n > 1) {
79 if(n > 10) {
80 pi = pivot(a, n, p);
81 } else
82 pi = a + (n>>1)*es;
83
84 p->swap(a, pi, es);
85 pi = a;
86 pn = a + n*es;
87 pj = pn;
88 for(;;) {
89 do
90 pi += es;
91 while(pi < pn && p->cmp(pi, a) < 0);
92 do
93 pj -= es;
94 while(pj > a && p->cmp(pj, a) > 0);
95 if(pj < pi)
96 break;
97 p->swap(pi, pj, es);
98 }
99 p->swap(a, pj, es);
100 j = (pj - a) / es;
101
102 n = n-j-1;
103 if(j >= n) {
104 qsorts(a, j, p);
105 a += (j+1)*es;
106 } else {
107 qsorts(a + (j+1)*es, n, p);
108 n = j;
109 }
110 }
111 }
112
113 void
qsort(void * va,long n,long es,int (* cmp)(void *,void *))114 qsort(void *va, long n, long es, int (*cmp)(void*, void*))
115 {
116 Sort s;
117
118 s.cmp = cmp;
119 s.es = es;
120 s.swap = swapi;
121 if(((uintptr)va | es) % sizeof(long))
122 s.swap = swapb;
123 qsorts((char*)va, n, &s);
124 }
125