1 /*
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 #include <common.h>
20 #include <exports.h>
21 #include <sort.h>
22
qsort(void * base,size_t nel,size_t width,int (* comp)(const void *,const void *))23 void qsort(void *base,
24 size_t nel,
25 size_t width,
26 int (*comp)(const void *, const void *))
27 {
28 size_t wgap, i, j, k;
29 char tmp;
30
31 if ((nel > 1) && (width > 0)) {
32 assert(nel <= ((size_t)(-1)) / width); /* check for overflow */
33 wgap = 0;
34 do {
35 wgap = 3 * wgap + 1;
36 } while (wgap < (nel-1)/3);
37 /* From the above, we know that either wgap == 1 < nel or */
38 /* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap < nel. */
39 wgap *= width; /* So this can not overflow if wnel doesn't. */
40 nel *= width; /* Convert nel to 'wnel' */
41 do {
42 i = wgap;
43 do {
44 j = i;
45 do {
46 register char *a;
47 register char *b;
48
49 j -= wgap;
50 a = j + ((char *)base);
51 b = a + wgap;
52 if ((*comp)(a, b) <= 0) {
53 break;
54 }
55 k = width;
56 do {
57 tmp = *a;
58 *a++ = *b;
59 *b++ = tmp;
60 } while (--k);
61 } while (j >= wgap);
62 i += width;
63 } while (i < nel);
64 wgap = (wgap - width)/3;
65 } while (wgap);
66 }
67 }
68
strcmp_compar(const void * p1,const void * p2)69 int strcmp_compar(const void *p1, const void *p2)
70 {
71 return strcmp(*(const char **)p1, *(const char **)p2);
72 }
73