Code adapted from uClibc-0.9.30.3
Signed-off-by: Wolfgang Denk wd@denx.de --- include/common.h | 4 +++ lib/Makefile | 1 + lib/qsort.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 74 insertions(+), 0 deletions(-) create mode 100644 lib/qsort.c
diff --git a/include/common.h b/include/common.h index eddec22..e4b4ec0 100644 --- a/include/common.h +++ b/include/common.h @@ -631,6 +631,10 @@ static inline IPaddr_t getenv_IPaddr (char *var) return (string_to_ip(getenv(var))); }
+/* lib/qsort.c */ +void qsort(void *base, size_t nmemb, size_t size, + int(*compar)(const void *, const void *)); + /* lib/time.c */ void udelay (unsigned long);
diff --git a/lib/Makefile b/lib/Makefile index c26536d..2d969a3 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 0000000..bb47319 --- /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); + } +}