* [PATCH 1/2] add qsort support
2012-05-14 18:20 [PATCH] Add glob sort support Sascha Hauer
@ 2012-05-14 18:20 ` Sascha Hauer
2012-05-14 18:21 ` [PATCH 2/2] glob: Add sorted output support Sascha Hauer
1 sibling, 0 replies; 3+ messages in thread
From: Sascha Hauer @ 2012-05-14 18:20 UTC (permalink / raw)
To: barebox
This is based on U-Boot code which in turn is based on uclibc
code.
Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de>
---
include/qsort.h | 7 +++++
lib/Kconfig | 3 +++
lib/Makefile | 1 +
lib/qsort.c | 79 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 90 insertions(+)
create mode 100644 include/qsort.h
create mode 100644 lib/qsort.c
diff --git a/include/qsort.h b/include/qsort.h
new file mode 100644
index 0000000..bbb2359
--- /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 f886e6e..3bcde5c 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 01a01b5..4e6b1ee 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/qsort.c b/lib/qsort.c
new file mode 100644
index 0000000..f648714
--- /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);
+}
--
1.7.10
_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox
^ permalink raw reply [flat|nested] 3+ messages in thread* [PATCH 2/2] glob: Add sorted output support
2012-05-14 18:20 [PATCH] Add glob sort support Sascha Hauer
2012-05-14 18:20 ` [PATCH 1/2] add qsort support Sascha Hauer
@ 2012-05-14 18:21 ` Sascha Hauer
1 sibling, 0 replies; 3+ messages in thread
From: Sascha Hauer @ 2012-05-14 18:21 UTC (permalink / raw)
To: barebox
This allows us for example to execute init scripts in the correct
order.
Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de>
---
common/Kconfig | 8 +++++++-
lib/glob.c | 11 +++++------
2 files changed, 12 insertions(+), 7 deletions(-)
diff --git a/common/Kconfig b/common/Kconfig
index 81e3acb..9f0e0f8 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/lib/glob.c b/lib/glob.c
index 74d2b12..c4c6067 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:
--
1.7.10
_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox
^ permalink raw reply [flat|nested] 3+ messages in thread