scc

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

qsort.c (1097B)


      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 static void
     27 xqsort(char *a, size_t n, struct qsort *qs)
     28 {
     29 	size_t j, es = qs->es;
     30 	char *pi, *pj, *pn;
     31 
     32 	if (n <= 1)
     33 		return;
     34 
     35 	pi = a;
     36 	pn = pj = a + n*es;
     37 
     38 	swap(a, a + n/2 * es,  es);
     39 	for (;;) {
     40 		do {
     41 			pi += es;
     42 		} while  (pi < pn && qs->cmp(pi, a) < 0);
     43 
     44 		do {
     45 			pj -= es;
     46 		} while (pj > a && qs->cmp(pj, a) > 0);
     47 
     48 		if (pj < pi)
     49 			break;
     50 		swap(pi, pj, es);
     51 	}
     52 	swap(a, pj, es);
     53 
     54 	j = (pj - a) / es;
     55 	xqsort(a, j, qs);
     56 	xqsort(a + (j+1)*es, n-j-1, qs);
     57 }
     58 
     59 void
     60 qsort(void *base, size_t nmemb, size_t size,
     61       int (*f)(const void *, const void *))
     62 {
     63 	struct qsort qs;
     64 
     65 	qs.cmp = f;
     66 	qs.es = size;
     67 	xqsort(base, nmemb, &qs);
     68 }