summaryrefslogtreecommitdiff
path: root/lib/qsort.c
diff options
context:
space:
mode:
authorWolfgang Denk <wd@denx.de>2010-06-13 01:45:10 +0200
committerWolfgang Denk <wd@denx.de>2010-09-19 19:29:47 +0200
commit54c6977e9ca41fb38b45f1746d90f2806be3b5cb (patch)
tree66b23eabbb3a2569a69d7247590b53894c055e8c /lib/qsort.c
parent65cd3fa81ff48cd44bcb3d9baf646dade15b9131 (diff)
Add qsort - add support for sorting data arrays
Code adapted from uClibc-0.9.30.3 Signed-off-by: Wolfgang Denk <wd@denx.de>
Diffstat (limited to 'lib/qsort.c')
-rw-r--r--lib/qsort.c69
1 files changed, 69 insertions, 0 deletions
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);
+ }
+}