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