diff options
author | Sascha Hauer <s.hauer@pengutronix.de> | 2012-05-13 15:02:24 +0200 |
---|---|---|
committer | Sascha Hauer <s.hauer@pengutronix.de> | 2012-05-14 20:16:26 +0200 |
commit | cbdf1e6dfaa895b12c40cfb2aa15dee65f0b85d6 (patch) | |
tree | 3b0aba1b3109d5412049d5742e946727f3dfcc2b /lib/qsort.c | |
parent | 7b5817e58d77d44d1e85fb25e384785d2682ed7d (diff) | |
download | barebox-cbdf1e6dfaa895b12c40cfb2aa15dee65f0b85d6.tar.gz barebox-cbdf1e6dfaa895b12c40cfb2aa15dee65f0b85d6.tar.xz |
add qsort support
This is based on U-Boot code which in turn is based on uclibc
code.
Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de>
Diffstat (limited to 'lib/qsort.c')
-rw-r--r-- | lib/qsort.c | 79 |
1 files changed, 79 insertions, 0 deletions
diff --git a/lib/qsort.c b/lib/qsort.c new file mode 100644 index 0000000000..f64871489d --- /dev/null +++ b/lib/qsort.c @@ -0,0 +1,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); +} |