blob: e771dcfcf2756504bc53916cd0366643ff70a81d [file] [log] [blame]
Wolfgang Denk54c69772010-06-13 01:45:10 +02001/*
2 * Code adapted from uClibc-0.9.30.3
3 *
4 * It is therefore covered by the GNU LESSER GENERAL PUBLIC LICENSE
5 * Version 2.1, February 1999
6 *
7 * Wolfgang Denk <wd@denx.de>
8 */
9
10/* This code is derived from a public domain shell sort routine by
11 * Ray Gardner and found in Bob Stout's snippets collection. The
12 * original code is included below in an #if 0/#endif block.
13 *
14 * I modified it to avoid the possibility of overflow in the wgap
15 * calculation, as well as to reduce the generated code size with
16 * bcc and gcc. */
17
18#include <linux/types.h>
19#if 0
20#include <assert.h>
21#else
22#define assert(arg)
23#endif
24
25void qsort(void *base,
Wolfgang Denk071bc922010-10-27 22:48:30 +020026 size_t nel,
27 size_t width,
28 int (*comp)(const void *, const void *))
Wolfgang Denk54c69772010-06-13 01:45:10 +020029{
30 size_t wgap, i, j, k;
31 char tmp;
32
33 if ((nel > 1) && (width > 0)) {
34 assert(nel <= ((size_t)(-1)) / width); /* check for overflow */
35 wgap = 0;
36 do {
37 wgap = 3 * wgap + 1;
38 } while (wgap < (nel-1)/3);
39 /* From the above, we know that either wgap == 1 < nel or */
40 /* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap < nel. */
41 wgap *= width; /* So this can not overflow if wnel doesn't. */
42 nel *= width; /* Convert nel to 'wnel' */
43 do {
44 i = wgap;
45 do {
46 j = i;
47 do {
48 register char *a;
49 register char *b;
50
51 j -= wgap;
52 a = j + ((char *)base);
53 b = a + wgap;
54 if ((*comp)(a, b) <= 0) {
55 break;
56 }
57 k = width;
58 do {
59 tmp = *a;
60 *a++ = *b;
61 *b++ = tmp;
62 } while (--k);
63 } while (j >= wgap);
64 i += width;
65 } while (i < nel);
66 wgap = (wgap - width)/3;
67 } while (wgap);
68 }
69}