]>
git.ipfire.org Git - thirdparty/u-boot.git/blob - lib/qsort.c
2 * Code adapted from uClibc-0.9.30.3
4 * It is therefore covered by the GNU LESSER GENERAL PUBLIC LICENSE
5 * Version 2.1, February 1999
7 * Wolfgang Denk <wd@denx.de>
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.
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
18 #include <linux/types.h>
25 void qsort(void *base
,
28 int (*comp
)(const void *, const void *))
33 if ((nel
> 1) && (width
> 0)) {
34 assert(nel
<= ((size_t)(-1)) / width
); /* check for overflow */
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' */
52 a
= j
+ ((char *)base
);
54 if ((*comp
)(a
, b
) <= 0) {
66 wgap
= (wgap
- width
)/3;