diff options
author | Michael Brandt <michael.brandt@stericsson.com> | 2010-11-12 11:11:53 +0100 |
---|---|---|
committer | Michael BRANDT <michael.brandt@stericsson.com> | 2010-11-17 10:32:03 +0100 |
commit | fcbb9f2f34873b6e344cd4377fc768c185888718 (patch) | |
tree | d8d226e5474335ee5a9409b8db8eb15cccb0e213 /lib_generic/qsort.c | |
parent | c15700c56ad0f46f09ce094d4e1c89196e5dd9fc (diff) |
Add qsort - add support for sorting data arrays
Code adapted from uClibc-0.9.30.3
Originated from U-Boot mainline git://git.denx.de/u-boot.git
commit 54c6977e9ca41fb38b45f1746d90f2806be3b5cb
Original committer Wolfgang Denk <wd@denx.de>
Change-Id: I85a11005af9eaed50d94674fdac74a32f7bc4f35
Signed-off-by: Michael Brandt <michael.brandt@stericsson.com>
Reviewed-on: http://gerrit.lud.stericsson.com/gerrit/8439
Reviewed-by: Mikael LARSSON1 <mikael.xt.larsson@stericsson.com>
Tested-by: Mikael LARSSON1 <mikael.xt.larsson@stericsson.com>
Diffstat (limited to 'lib_generic/qsort.c')
-rw-r--r-- | lib_generic/qsort.c | 69 |
1 files changed, 69 insertions, 0 deletions
diff --git a/lib_generic/qsort.c b/lib_generic/qsort.c new file mode 100644 index 000000000..e771dcfcf --- /dev/null +++ b/lib_generic/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); + } +} |