scc

simple c99 compiler
git clone git://git.simple-cc.org/scc
Log | Files | Refs | Submodules | README | LICENSE

commit 7531f49b441cafa6fc1c20659abb29bfc5f3a989
parent 1dcc4bd503a9705419f3405e8db92019a7e02c26
Author: Roberto E. Vargas Caballero <k0ga@shike2.com>
Date:   Fri,  8 Dec 2017 01:14:36 +0100

[lib/c] Add qsort()

Diffstat:
Mlib/c/src/Makefile | 2+-
Alib/c/src/qsort.c | 155+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 156 insertions(+), 1 deletion(-)

diff --git 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 \ diff --git a/lib/c/src/qsort.c b/lib/c/src/qsort.c @@ -0,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); +}