scc

 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
11struct qsort {
12	size_t es;
13	int (*cmp)(const void *, const void *);
14};
15
16static void
17swap(unsigned char *i, unsigned 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 */
31static void
32xqsort(unsigned char *a, size_t n, struct qsort *qs)
33{
34	size_t nj, ni, es = qs->es;
35	unsigned 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-ni-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
73void
74qsort(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}