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
19 #include <linux/types.h>
24 void qsort(void *base,
27 int (*comp)(const void *, const void *))
32 if ((nel > 1) && (width > 0)) {
33 assert(nel <= ((size_t)(-1)) / width); /* check for overflow */
37 } while (wgap < (nel-1)/3);
38 /* From the above, we know that either wgap == 1 < nel or */
39 /* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap < nel. */
40 wgap *= width; /* So this can not overflow if wnel doesn't. */
41 nel *= width; /* Convert nel to 'wnel' */
51 a = j + ((char *)base);
53 if ((*comp)(a, b) <= 0) {
65 wgap = (wgap - width)/3;
70 int strcmp_compar(const void *p1, const void *p2)
72 return strcmp(*(const char **)p1, *(const char **)p2);