shithub: scc

Download patch

ref: 428e86f306625a3192e03260a921a19c3109f57d
parent: bb99c8599bac91bd98e0f9bbe0c994e97f0956a1
author: Roberto E. Vargas Caballero <k0ga@shike2.com>
date: Thu Dec 7 20:14:36 EST 2017 

[lib/c] Add qsort()


--- a/lib/c/src/Makefile
+++ b/lib/c/src/Makefile
@@ -2,7 +2,7 @@
 
 include ../../../config.mk
 
-OBJ = bsearch.o \
+OBJ = bsearch.o qsort.o \
       abs.o __abs.o labs.o __labs.o llabs.o __labs.o \
       perror.o strerror.o \
       printf.o fprintf.o vfprintf.o \
--- /dev/null
+++ b/lib/c/src/qsort.c
@@ -1,0 +1,155 @@
+
+#include <stdlib.h>
+#include <string.h>
+#undef qsort
+
+/*
+ * This implementation of qsort is based in the paper
+ * "Engineering a Sort Function", by Jon L.Bentley and M. Douglas McIlroy
+ */
+
+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)
+{
+	do {
+		char c = *i;
+		*i++ = *j;
+		*j++ = c;
+	} while (--n > 0);
+}
+
+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);
+	for (;;) {
+		do {
+			pi += es;
+		} while  (pi < pn && qs->cmp(pi, pn) < 0);
+
+		do {
+			pj -= es;
+		} while (pj > a && qs->cmp(pj, a) > 0);
+
+		if (pj < pi)
+			break;
+		qs->swap(pi, pj, es);
+	}
+	qs->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;
+}
+
+void
+qsort(void *base, size_t nmemb, size_t size,
+      int (*f)(const void *, const void *))
+{
+	struct qsort qs;
+
+	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);
+}