qsort.c - scc - simple c99 compiler
 (HTM) git clone git://git.simple-cc.org/scc
 (DIR) Log
 (DIR) Files
 (DIR) Refs
 (DIR) Submodules
 (DIR) README
 (DIR) 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 }