shithub: scc

Info  •  Files  •  Log  •  Branches

[lib/c] Simplify qsort()

Scc libc is not designed to be a fast library but a simple and
small library. For this reason, and after doing some testing
there is no reason to  make the code more complex.

--- a/lib/c/src/qsort.c

+++ b/lib/c/src/qsort.c

@@ -5,17 +5,17 @@

 /*

  * This implementation of qsort is based in the paper

- * "Engineering a Sort Function", by Jon L.Bentley and M. Douglas McIlroy

+ * "Engineering a Sort Function", by Jon L.Bentley and M. Douglas McIlroy.

+ * A lot of different optimizations were removed to make the code simpler.

  */

 struct qsort {

 	size_t es;

 	int (*cmp)(const void *, const void *);

-	void (*swap)(char *i, char *j, size_t n);

 };

 static void

-swapb(char *i, char *j, size_t n)

+swap(char *i, char *j, size_t n)

 {

 	do {

 		char c = *i;

@@ -25,77 +25,11 @@

 }

 static void

-swapw(char *i, char *j, size_t n)

-{

-	int w, *wi = (int *) i, *wj = (int *) j;

-

-	n /= sizeof(w);

-

-	do {

-		w = *wi;

-		*wi++ = *wj;

-		*wj++ = w;

-	} while (--n > 0);

-}

-

-static void

-swapl(char *i, char *j, size_t n)

-{

-	char *tmp[n];

-

-	memcpy(tmp, i, n);

-	memcpy(i, j, n);

-	memcpy(j, tmp, n);

-}

-

-static char *

-med3(char *a, char *b, char *c, int (*cmp)(const void *, const void *))

-{

-	if (cmp(a, b) < 0) {

-		if (cmp(b, c) < 0)

-			return b;

-		return (cmp(a, c) < 0) ? c : a;

-	} else {

-		if (cmp(b, c) > 0)

-			return b;

-		return (cmp(a, c) > 0) ? c : a;

-	}

-}

-

-static char *

-pivot(char *v, size_t n, struct qsort *qs)

-{

-	char *p1, *pm, *pn; /* 1st, middle, nth */

-	int (*cmp)(const void *, const void *);

-	size_t s, es = qs->es;

-	

-

-	pm = v + n/2 * es;

-	if (n < 10)

-		return pm;

-

-	cmp = qs->cmp;

-	s = n/6 * es;

-	p1 = v + s;

-	pn = pm + 2*s;

-

-	if (n > 50) {

-		s = n/8 * es;

-		p1 = med3(p1, p1+s, p1 + 2*s, cmp);

-		pm = med3(pm-s, pm, pm+s, cmp);

-		pn = med3(pn-2*s, pn-s, pn, cmp);

-	}

-

-	return med3(p1, pm, pn, qs->cmp);

-}

-

-static void

 xqsort(char *a, size_t n, struct qsort *qs)

 {

 	size_t j, es = qs->es;

 	char *pi, *pj, *pn;

-tail_recursion:

 	if (n <= 1)

 		return;

@@ -102,11 +36,11 @@

 	pi = a;

 	pn = pj = a + n*es;

-	qs->swap(a, pivot(a, n, qs), es);

+	swap(a, a + n/2 * es,  es);

 	for (;;) {

 		do {

 			pi += es;

-		} while  (pi < pn && qs->cmp(pi, pn) < 0);

+		} while  (pi < pn && qs->cmp(pi, a) < 0);

 		do {

 			pj -= es;

@@ -114,25 +48,13 @@

 		if (pj < pi)

 			break;

-		qs->swap(pi, pj, es);

+		swap(pi, pj, es);

 	}

-	qs->swap(a, pj, es);

+	swap(a, pj, es);

-	/*

-	 * We have to recurse over two subarrays. One of them can be

-	 * optimized with tail recursion. We select to recurse over

-	 * the bigger subarray, because it will allow us to apply a

-	 * better divide and conquer strategy.

-	 */

 	j = (pj - a) / es;

-	if (j >= n) {

-		xqsort(a, j, qs);

-		a += (j+1) * es;

-	} else {

-		xqsort(a + (j+1) * es, n-j-1, qs);

-		n = j;

-	}

-	goto tail_recursion;

+	xqsort(a, j, qs);

+	xqsort(a + (j+1)*es, n-j-1, qs);

 }

 void

@@ -143,13 +65,5 @@

 	qs.cmp = f;

 	qs.es = size;

-

-	if (size > 7 * sizeof(int))

-		qs.swap = swapl;

-	else if (size % sizeof(int) == 0)

-		qs.swap = swapw;

-	else

-		qs.swap = swapb;

-

 	xqsort(base, nmemb, &qs);

 }