Home
qsort.c - scc - simple c99 compiler
HTML 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 }