diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Makefile | 1 | ||||
| -rw-r--r-- | lib/qsort.c | 69 |
2 files changed, 70 insertions, 0 deletions
diff --git a/lib/Makefile b/lib/Makefile index c26536d0b31..2d969a3d77d 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -43,6 +43,7 @@ COBJS-$(CONFIG_LMB) += lmb.o COBJS-y += ldiv.o COBJS-$(CONFIG_MD5) += md5.o COBJS-y += net_utils.o +COBJS-y += qsort.o COBJS-$(CONFIG_SHA1) += sha1.o COBJS-$(CONFIG_SHA256) += sha256.o COBJS-y += string.o diff --git a/lib/qsort.c b/lib/qsort.c new file mode 100644 index 00000000000..bb47319f8ba --- /dev/null +++ b/lib/qsort.c @@ -0,0 +1,69 @@ +/* + * 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> +#if 0 +#include <assert.h> +#else +#define assert(arg) +#endif + +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 > 1) && (width > 0)) { + assert(nel <= ((size_t)(-1)) / width); /* check for overflow */ + 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 { + register char *a; + register 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); + } +} |