From 009f261242b7e1f5482e097315c82a4185a708bf Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Sat, 21 Nov 2009 13:29:45 +1030 Subject: [PATCH] New asort routine; unf. breaks under -Wmissing-prototypes etc :( --- Makefile-ccan | 3 +- ccan/asort/_info | 65 ++++++++++++++++++++ ccan/asort/asort.c | 21 +++++++ ccan/asort/asort.h | 37 +++++++++++ ccan/asort/test/compile_fail-context-type.c | 21 +++++++ ccan/asort/test/run-strings.c | 22 +++++++ ccan/asort/test/run.c | 68 +++++++++++++++++++++ config.h | 13 ++-- tools/tools.h | 3 +- 9 files changed, 245 insertions(+), 8 deletions(-) create mode 100644 ccan/asort/_info create mode 100644 ccan/asort/asort.c create mode 100644 ccan/asort/asort.h create mode 100644 ccan/asort/test/compile_fail-context-type.c create mode 100644 ccan/asort/test/run-strings.c create mode 100644 ccan/asort/test/run.c diff --git a/Makefile-ccan b/Makefile-ccan index bac2dd17..de669a0e 100644 --- a/Makefile-ccan +++ b/Makefile-ccan @@ -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 index 00000000..3b71998a --- /dev/null +++ b/ccan/asort/_info @@ -0,0 +1,65 @@ +#include +#include + +/** + * 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 + * #include + * #include + * + * 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] ...\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 index 00000000..cf8d8d9d --- /dev/null +++ b/ccan/asort/asort.c @@ -0,0 +1,21 @@ +#include +#include + +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 index 00000000..1139238e --- /dev/null +++ b/ccan/asort/asort.h @@ -0,0 +1,37 @@ +#ifndef CCAN_ASORT_H +#define CCAN_ASORT_H +#include +#include + +/** + * 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 index 00000000..62d16c5e --- /dev/null +++ b/ccan/asort/test/compile_fail-context-type.c @@ -0,0 +1,21 @@ +#include +#include + +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 index 00000000..3ec45384 --- /dev/null +++ b/ccan/asort/test/run-strings.c @@ -0,0 +1,22 @@ +#include +#include +#include +#include + +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 index 00000000..69bab975 --- /dev/null +++ b/ccan/asort/test/run.c @@ -0,0 +1,68 @@ +#include +#include +#include +#include +#include +#include + +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(); +} diff --git a/config.h b/config.h index 54291b4b..d8504ce6 100644 --- 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 diff --git a/tools/tools.h b/tools/tools.h index b7fe9155..ed2f6bfb 100644 --- a/tools/tools.h +++ b/tools/tools.h @@ -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, -- 2.39.2