20060303a

1 files changed, 122 insertions, 0 deletions

diff --git a/libkern/qsort.c b/libkern/qsort.c
new file mode 100644
index 00000000..3388891c
--- /dev/null
+++ b/libkern/qsort.c
@@ -0,0 +1,122 @@
+/*
+ * qsort -- simple quicksort
+ */
+
+typedef
+struct
+{
+	int	(*cmp)(void*, void*);
+	void	(*swap)(char*, char*, long);
+	long	es;
+} Sort;
+
+static	void
+swapb(char *i, char *j, long es)
+{
+	char c;
+
+	do {
+		c = *i;
+		*i++ = *j;
+		*j++ = c;
+		es--;
+	} while(es != 0);
+
+}
+
+static	void
+swapi(char *ii, char *ij, long es)
+{
+	long *i, *j, c;
+
+	i = (long*)ii;
+	j = (long*)ij;
+	do {
+		c = *i;
+		*i++ = *j;
+		*j++ = c;
+		es -= sizeof(long);
+	} while(es != 0);
+}
+
+static	char*
+pivot(char *a, long n, Sort *p)
+{
+	long j;
+	char *pi, *pj, *pk;
+
+	j = n/6 * p->es;
+	pi = a + j;	/* 1/6 */
+	j += j;
+	pj = pi + j;	/* 1/2 */
+	pk = pj + j;	/* 5/6 */
+	if(p->cmp(pi, pj) < 0) {
+		if(p->cmp(pi, pk) < 0) {
+			if(p->cmp(pj, pk) < 0)
+				return pj;
+			return pk;
+		}
+		return pi;
+	}
+	if(p->cmp(pj, pk) < 0) {
+		if(p->cmp(pi, pk) < 0)
+			return pi;
+		return pk;
+	}
+	return pj;
+}
+
+static	void
+qsorts(char *a, long n, Sort *p)
+{
+	long j, es;
+	char *pi, *pj, *pn;
+
+	es = p->es;
+	while(n > 1) {
+		if(n > 10) {
+			pi = pivot(a, n, p);
+		} else
+			pi = a + (n>>1)*es;
+
+		p->swap(a, pi, es);
+		pi = a;
+		pn = a + n*es;
+		pj = pn;
+		for(;;) {
+			do
+				pi += es;
+			while(pi < pn && p->cmp(pi, a) < 0);
+			do
+				pj -= es;
+			while(pj > a && p->cmp(pj, a) > 0);
+			if(pj < pi)
+				break;
+			p->swap(pi, pj, es);
+		}
+		p->swap(a, pj, es);
+		j = (pj - a) / es;
+
+		n = n-j-1;
+		if(j >= n) {
+			qsorts(a, j, p);
+			a += (j+1)*es;
+		} else {
+			qsorts(a + (j+1)*es, n, p);
+			n = j;
+		}
+	}
+}
+
+void
+qsort(void *va, long n, long es, int (*cmp)(void*, void*))
+{
+	Sort s;
+
+	s.cmp = cmp;
+	s.es = es;
+	s.swap = swapi;
+	if(((long)va | es) % sizeof(long))
+		s.swap = swapb;
+	qsorts((char*)va, n, &s);
+}