Merge branch 'pu/globsort' into next

6 files changed, 102 insertions, 7 deletions

diff --git a/common/Kconfig b/common/Kconfig
index 81e3acb54a..9f0e0f86f9 100644
--- a/common/Kconfig
+++ b/common/Kconfig
@@ -310,7 +310,13 @@ config GLOB
 	depends on SHELL_HUSH
 	help
 	  If you want to use wildcards like * or ? say y here.
-	
+
+config GLOB_SORT
+	select QSORT
+	bool
+	prompt "glob sort support"
+	depends on GLOB
+
 config PROMPT_HUSH_PS2
 	string
 	depends on SHELL_HUSH
diff --git a/include/qsort.h b/include/qsort.h
new file mode 100644
index 0000000000..bbb23595b2
--- /dev/null
+++ b/include/qsort.h
@@ -0,0 +1,7 @@
+#ifndef __QSORT_H
+#define __QSORT_H
+
+void qsort(void  *base, size_t nel, size_t width,
+	   int (*comp)(const void *, const void *));
+
+#endif /* __QSORT_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index f886e6e2a5..3bcde5c1ff 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -35,4 +35,7 @@ config BCH
 config BITREV
        bool
 
+config QSORT
+	bool
+
 endmenu
diff --git a/lib/Makefile b/lib/Makefile
index 01a01b5966..4e6b1ee90d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -33,3 +33,4 @@ obj-$(CONFIG_FDT)	+= fdt/
 obj-$(CONFIG_UNCOMPRESS)	+= uncompress.o
 obj-$(CONFIG_BCH)	+= bch.o
 obj-$(CONFIG_BITREV)	+= bitrev.o
+obj-$(CONFIG_QSORT)	+= qsort.o
diff --git a/lib/glob.c b/lib/glob.c
index 74d2b123e3..c4c60674b6 100644
--- a/lib/glob.c
+++ b/lib/glob.c
@@ -22,6 +22,7 @@ Cambridge, MA 02139, USA.  */
 #include <malloc.h>
 #include <xfuncs.h>
 #include <fnmatch.h>
+#include <qsort.h>
 #define _GNU_SOURCE
 #include <glob.h>
 
@@ -75,12 +76,10 @@ int glob_pattern_p(const char *pattern, int quote)
 
 #ifdef CONFIG_GLOB_SORT
 /* Do a collated comparison of A and B.  */
-static int collated_compare(a, b)
-const __ptr_t a;
-const __ptr_t b;
+static int collated_compare(const void *a, const void *b)
 {
-	const char *const s1 = *(const char *const *)a;
-	const char *const s2 = *(const char *const *)b;
+	const char *s1 = a;
+	const char *s2 = b;
 
 	if (s1 == s2)
 		return 0;
@@ -266,7 +265,7 @@ int glob(const char *pattern, int flags,
 		/* Sort the vector.  */
 		qsort((__ptr_t) & pglob->gl_pathv[oldcount],
 		      pglob->gl_pathc - oldcount,
-		      sizeof(char *), (__compar_fn_t) collated_compare);
+		      sizeof(char *), collated_compare);
 #endif
 	status = 0;
 out:
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);
+}