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