scc

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

qsort.c (1321B)


      1 #include <stdlib.h>
      2 #include <string.h>
      3 #undef qsort
      4 
      5 /*
      6  * This implementation of qsort is based in the paper
      7  * "Engineering a Sort Function", by Jon L.Bentley and M. Douglas McIlroy.
      8  * A lot of different optimizations were removed to make the code simpler.
      9  */
     10 
     11 struct qsort {
     12 	size_t es;
     13 	int (*cmp)(const void *, const void *);
     14 };
     15 
     16 static void
     17 swap(char *i, char *j, size_t n)
     18 {
     19 	do {
     20 		char c = *i;
     21 		*i++ = *j;
     22 		*j++ = c;
     23 	} while (--n > 0);
     24 }
     25 
     26 /*
     27  * This function recurses as much as log2(n) because
     28  * it always recurses in the smaller part of the
     29  * array.
     30  */
     31 static void
     32 xqsort(char *a, size_t n, struct qsort *qs)
     33 {
     34 	size_t nj, ni, es = qs->es;
     35 	char *pi, *pj, *pn;
     36 
     37 	if (n <= 1)
     38 		return;
     39 
     40 	pi = a;
     41 	pn = pj = a + n*es;
     42 
     43 	swap(a, a + n/2 * es,  es);
     44 	for (;;) {
     45 		do {
     46 			pi += es;
     47 		} while  (pi < pn && qs->cmp(pi, a) < 0);
     48 
     49 		do {
     50 			pj -= es;
     51 		} while (pj > a && qs->cmp(pj, a) > 0);
     52 
     53 		if (pj < pi)
     54 			break;
     55 		swap(pi, pj, es);
     56 	}
     57 	swap(a, pj, es);
     58 
     59 	pi = a;
     60 	ni = (pj - a) / es;
     61 	pj += es;
     62 	nj = n-nj-1;
     63 
     64 	if (ni < nj) {
     65 		xqsort(pi, ni, qs);
     66 		xqsort(pj, nj, qs);
     67 	} else {
     68 		xqsort(pj, nj, qs);
     69 		xqsort(pi, ni, qs);
     70 	}
     71 }
     72 
     73 void
     74 qsort(void *base, size_t nmemb, size_t size,
     75       int (*f)(const void *, const void *))
     76 {
     77 	struct qsort qs;
     78 
     79 	qs.cmp = f;
     80 	qs.es = size;
     81 	xqsort(base, nmemb, &qs);
     82 }