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>

2 files changed, 70 insertions, 0 deletions

diff --git a/lib_generic/Makefile b/lib_generic/Makefile
index bfaf3468e..2bf73e8da 100644
--- a/lib_generic/Makefile
+++ b/lib_generic/Makefile
@@ -41,6 +41,7 @@ COBJS-y += gunzip.o
 COBJS-y += lmb.o
 COBJS-y += ldiv.o
 COBJS-$(CONFIG_MD5) += md5.o
+COBJS-y += qsort.o
 COBJS-y += sha1.o
 COBJS-$(CONFIG_SHA256) += sha256.o
 COBJS-y += string.o
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);
+	}
+}