Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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
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
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*
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
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
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 
}