New asort routine; unf. breaks under -Wmissing-prototypes etc :(
authorRusty Russell <rusty@rustcorp.com.au>
Sat, 21 Nov 2009 02:59:45 +0000 (13:29 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Sat, 21 Nov 2009 02:59:45 +0000 (13:29 +1030)
Makefile-ccan
ccan/asort/_info [new file with mode: 0644]
ccan/asort/asort.c [new file with mode: 0644]
ccan/asort/asort.h [new file with mode: 0644]
ccan/asort/test/compile_fail-context-type.c [new file with mode: 0644]
ccan/asort/test/run-strings.c [new file with mode: 0644]
ccan/asort/test/run.c [new file with mode: 0644]
config.h
tools/tools.h

index bac2dd17c7bcc6f9004d9e0574544c1e6e615a0e..de669a0e7f0e482f7974ff266fc35498ab7ef170 100644 (file)
@@ -2,7 +2,8 @@
 # For simple projects you could just do:
 #      SRCFILES += $(wildcard ccan/*/*.c)
 
-CFLAGS=-g -O3 -Wall -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -Werror -I. $(DEPGEN)
+#CFLAGS=-g -O3 -Wall -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -Werror -I. $(DEPGEN)
+CFLAGS=-g -Wall -Wstrict-prototypes -Wold-style-definition -Werror -I. $(DEPGEN)
 
 # Automatic dependency generation: makes ccan/*.d files.
 DEPGEN=-MD
diff --git a/ccan/asort/_info b/ccan/asort/_info
new file mode 100644 (file)
index 0000000..3b71998
--- /dev/null
@@ -0,0 +1,65 @@
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * asort - typesafe array sort (qsort)
+ *
+ * qsort() is the standard routine for sorting an array of objects.
+ * Unfortunately, it has two problems:
+ *     1) It isn't typesafe,
+ *     2) The comparison function doesn't take a context pointer.
+ *
+ * asort does both.
+ *
+ * Licence: LGPL
+ *
+ * Example:
+ *     #include <ccan/asort/asort.h>
+ *     #include <stdio.h>
+ *     #include <string.h>
+ *     
+ *     static int cmp(const char **a, const char **n, bool *casefold)
+ *     {
+ *             if (*casefold)
+ *                     return strcasecmp(*a, *b);
+ *             else
+ *                     return strcmp(*a, *b);
+ *     }
+ *     
+ *     int main(int argc, char *argv[])
+ *     {
+ *             bool casefold = false;
+ *             unsigned int i;
+ *     
+ *             if (argc < 2) {
+ *                     fprintf(stderr, "Usage: %s [-i] <list>...\n"
+ *                             "Sort arguments (-i = ignore case)\n",
+ *                             argv[0]);
+ *                     exit(1);
+ *             }
+ *     
+ *             if (strcmp(argv[1], "-i") == 0) {
+ *                     casefold = true;
+ *                     argc--;
+ *                     argv++;
+ *             }
+ *             asort(&argv[1], argc-1, cmp, &casefold);
+ *             for (i = 1; i < argc; i++)
+ *                     printf("%s ", argv[i]);
+ *             printf("\n");
+ *             return 0;
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/typesafe_cb\n");
+               printf("ccan/array_size\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/asort/asort.c b/ccan/asort/asort.c
new file mode 100644 (file)
index 0000000..cf8d8d9
--- /dev/null
@@ -0,0 +1,21 @@
+#include <ccan/asort/asort.h>
+#include <stdlib.h>
+
+void _asort(void *base, size_t nmemb, size_t size,
+           int(*compar)(const void *, const void *, const void *ctx),
+           const void *ctx)
+{
+#if HAVE_NESTED_FUNCTIONS
+       /* This gives bogus "warning: no previous prototype for ‘cmp’"
+        * with gcc 4 with -Wmissing-prototypes.  But there's no way
+        * to predeclare it, so we lose. */
+       int cmp(const void *a, const void *b)
+       {
+               return compar(a, b, ctx);
+       }
+       qsort(base, nmemb, size, cmp);
+#else
+       #error "Need to open-code quicksort?"
+       /* qsort is a classic "needed more real-life testing" API. */
+#endif
+}
diff --git a/ccan/asort/asort.h b/ccan/asort/asort.h
new file mode 100644 (file)
index 0000000..1139238
--- /dev/null
@@ -0,0 +1,37 @@
+#ifndef CCAN_ASORT_H
+#define CCAN_ASORT_H
+#include <ccan/typesafe_cb/typesafe_cb.h>
+#include <stdlib.h>
+
+/**
+ * asort - sort an array of elements
+ * @base: pointer to data to sort
+ * @num: number of elements
+ * @cmp: pointer to comparison function
+ * @ctx: a context pointer for the cmp function
+ *
+ * This function does a sort on the given array.  The resulting array
+ * will be in ascending sorted order by the provided comparison function.
+ *
+ * The @cmp function should exactly match the type of the @base and
+ * @ctx arguments.  Otherwise it can take three const void *.
+ */
+#if HAVE_TYPEOF
+#define asort(base, num, cmp, ctx)                                     \
+_asort((base), (num), sizeof(*(base)),                                 \
+       cast_if_type((cmp),                                             \
+                   int (*)(const __typeof__(*(base)) *,                \
+                           const __typeof__(*(base)) *,                \
+                           __typeof__(ctx)),                           \
+                   int (*)(const void *, const void *, const void *)), (ctx))
+#else
+#define asort(base, num, cmp, ctx)                             \
+       _asort((base), (num), sizeof(*(base)),                  \
+              (int (*)(const void *, const void *, const void *))(cmp), ctx)
+#endif
+
+void _asort(void *base, size_t nmemb, size_t size,
+           int(*compar)(const void *, const void *, const void *),
+           const void *ctx);
+
+#endif /* CCAN_ASORT_H */
diff --git a/ccan/asort/test/compile_fail-context-type.c b/ccan/asort/test/compile_fail-context-type.c
new file mode 100644 (file)
index 0000000..62d16c5
--- /dev/null
@@ -0,0 +1,21 @@
+#include <ccan/asort/asort.h>
+#include <ccan/asort/asort.c>
+
+static int cmp(char *const *a, char *const *b, int *flag)
+{
+       return 0;
+}
+
+int main(int argc, char **argv)
+{
+#ifdef FAIL
+       char flag;
+#if !HAVE_TYPEOF
+#error "Unfortunately we don't fail if no typeof."
+#endif
+#else
+       int flag;
+#endif
+       asort(argv+1, argc-1, cmp, &flag);
+       return 0;
+}
diff --git a/ccan/asort/test/run-strings.c b/ccan/asort/test/run-strings.c
new file mode 100644 (file)
index 0000000..3ec4538
--- /dev/null
@@ -0,0 +1,22 @@
+#include <ccan/asearch/asearch.h>
+#include <ccan/array_size/array_size.h>
+#include <ccan/tap/tap.h>
+#include <stdlib.h>
+
+static int cmp(const int *key, const char *const *elem)
+{
+       return *key - atoi(*elem);
+}
+
+int main(void)
+{
+       const char *args[] = { "1", "4", "7", "9" };
+       int key = 7;
+       const char **p;
+
+       plan_tests(1);
+       p = asearch(&key, args, ARRAY_SIZE(args), cmp);
+       ok1(p == &args[2]);
+
+       return exit_status();
+}
diff --git a/ccan/asort/test/run.c b/ccan/asort/test/run.c
new file mode 100644 (file)
index 0000000..69bab97
--- /dev/null
@@ -0,0 +1,68 @@
+#include <ccan/asort/asort.h>
+#include <ccan/asort/asort.c>
+#include <ccan/array_size/array_size.h>
+#include <ccan/tap/tap.h>
+#include <limits.h>
+#include <stdbool.h>
+
+static int test_cmp(const int *key, const int *elt, int *flag)
+{
+       if (*key < *elt)
+               return -1 * *flag;
+       else if (*key > *elt)
+               return 1 * *flag;
+
+       return 0;
+}
+
+static bool is_sorted(const int arr[], unsigned int size)
+{
+       unsigned int i;
+
+       for (i = 1; i < size; i++)
+               if (arr[i] < arr[i-1])
+                       return false;
+       return true;
+}
+
+static bool is_reverse_sorted(const int arr[], unsigned int size)
+{
+       unsigned int i;
+
+       for (i = 1; i < size; i++)
+               if (arr[i] > arr[i-1])
+                       return false;
+       return true;
+}
+
+static void psuedo_random_array(int arr[], unsigned int size)
+{
+       unsigned int i;
+
+       for (i = 0; i < size; i++)
+               arr[i] = i * (INT_MAX / 4 - 7);
+}
+
+#define TEST_SIZE 100
+
+int main(void)
+{
+       int tmparr[TEST_SIZE];
+       int multiplier = 1;
+
+       plan_tests(4);
+
+       psuedo_random_array(tmparr, TEST_SIZE);
+       ok1(!is_sorted(tmparr, TEST_SIZE));
+       ok1(!is_reverse_sorted(tmparr, TEST_SIZE));
+
+       asort(tmparr, TEST_SIZE, test_cmp, &multiplier);
+       ok1(is_sorted(tmparr, TEST_SIZE));
+
+       psuedo_random_array(tmparr, TEST_SIZE);
+       multiplier = -1;
+       asort(tmparr, TEST_SIZE, test_cmp, &multiplier);
+       ok1(is_reverse_sorted(tmparr, TEST_SIZE));
+
+       return exit_status();
+}
index 54291b4b9565c30986d5a75938f13e9ea6dd146d..d8504ce6530a7eeeb8301017f14c6d8292ef391c 100644 (file)
--- a/config.h
+++ b/config.h
@@ -1,13 +1,14 @@
 /* Simple config.h for gcc. */
-#define HAVE_TYPEOF 1
 #define HAVE_ALIGNOF 1
-#define HAVE_STATEMENT_EXPR 1
-#define HAVE_BUILTIN_EXPECT 1
 #define HAVE_ATTRIBUTE_PRINTF 1
-#define HAVE_BUILTIN_TYPES_COMPATIBLE_P 1
+#define HAVE_BIG_ENDIAN 0
 #define HAVE_BUILTIN_CHOOSE_EXPR 1
+#define HAVE_BUILTIN_EXPECT 1
+#define HAVE_BUILTIN_TYPES_COMPATIBLE_P 1
+#define HAVE_GETPAGESIZE 1
 #define HAVE_LITTLE_ENDIAN 1
-#define HAVE_BIG_ENDIAN 0
 #define HAVE_MMAP 1
-#define HAVE_GETPAGESIZE 1
+#define HAVE_NESTED_FUNCTIONS 1
+#define HAVE_STATEMENT_EXPR 1
+#define HAVE_TYPEOF 1
 #define HAVE_UTIME 1
index b7fe9155802df816af4feefaf37f037dac38fcae..ed2f6bfb6e77442e9682f450d34db6b2cce6e93e 100644 (file)
@@ -9,7 +9,8 @@
 #define SPACE_CHARS    " \f\n\r\t\v"
 
 /* FIXME: Remove some -I */
-#define CFLAGS "-g -Wall -Wundef -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -Werror -Iccan/ -I. -I.. -I../.."
+/* FIXME: Nested functions break with -Wmissing-prototypes -Wmissing-declarations */
+#define CFLAGS "-g -Wall -Wundef -Wstrict-prototypes -Wold-style-definition -Werror -Iccan/ -I. -I.. -I../.."
 
 /* This actually compiles and runs the info file to get dependencies. */
 char **get_deps(const void *ctx, const char *dir, const char *name,