scc

commit 15d9bea9a00f9bc013e0a7954eb9a59fb3039549
parent 7531f49b441cafa6fc1c20659abb29bfc5f3a989
Author: Roberto E. Vargas Caballero <k0ga@shike2.com>
Date:   Fri,  8 Dec 2017 11:04:22 +0000

[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.

Diffstat:
M
lib/c/src/qsort.c
 | 
104
+++++++------------------------------------------------------------------------

1 file changed, 9 insertions(+), 95 deletions(-)
diff --git 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,88 +25,22 @@ swapb(char *i, char *j, size_t n)
 }
 
 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;
 
 	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 @@ tail_recursion:
 
 		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 @@ qsort(void *base, size_t nmemb, size_t size,
 
 	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);
 }