From daddafe53685b0b6f90a7746cbbd1a2e7df59216 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Tue, 2 Nov 2010 11:55:33 +1030 Subject: [PATCH] foreach: new module --- ccan/foreach/_info | 70 +++++++++++++++ ccan/foreach/foreach.c | 158 +++++++++++++++++++++++++++++++++ ccan/foreach/foreach.h | 107 ++++++++++++++++++++++ ccan/foreach/test/run-break.c | 38 ++++++++ ccan/foreach/test/run-nested.c | 102 +++++++++++++++++++++ ccan/foreach/test/run.c | 29 ++++++ config.h | 2 + 7 files changed, 506 insertions(+) create mode 100644 ccan/foreach/_info create mode 100644 ccan/foreach/foreach.c create mode 100644 ccan/foreach/foreach.h create mode 100644 ccan/foreach/test/run-break.c create mode 100644 ccan/foreach/test/run-nested.c create mode 100644 ccan/foreach/test/run.c diff --git a/ccan/foreach/_info b/ccan/foreach/_info new file mode 100644 index 00000000..a00ee8b3 --- /dev/null +++ b/ccan/foreach/_info @@ -0,0 +1,70 @@ +#include +#include +#include "config.h" + +/** + * foreach - macro for simple iteration of arrays + * + * The foreach_int and foreach_ptr macros allow simple iteration of + * static arrays. This is very efficient with good compiler support + * (ie. gcc), and not too bad (ie. a few compares and mallocs) for + * other compilers. + * + * License: LGPL (3 or any later version) + * Author: Rusty Russell + * + * Example: + * // Figure out how to get usage: message out of a program. + * #include + * #include + * #include + * #include + * #include + * + * // Returns true if program outputs "usage:" + * static bool try_usage(const char *prog, const char *arg) + * { + * char *command; + * FILE *in; + * int status; + * + * command = malloc(strlen(prog) + 1 + strlen(arg) + 1 + + * sizeof("&1 | grep -qiw usage:")); + * sprintf(command, "%s %s &1 | grep -qiw usage:", + * prog, arg); + * in = popen(command, "r"); + * if (!in) + * err(2, "running '%s'", command); + * status = pclose(in); + * free(command); + * return (WIFEXITED(status) && WEXITSTATUS(status) == 0); + * } + * + * int main(int argc, char *argv[]) + * { + * const char *arg; + * + * if (argc != 2) + * errx(1, "Usage: %s \n" + * "Figures out how to get usage message", argv[0]); + * foreach_ptr(arg, "--help", "-h", "--usage", "-?", "") { + * if (try_usage(argv[1], arg)) { + * printf("%s %s\n", argv[1], arg); + * exit(0); + * } + * } + * printf("%s is unhelpful\n", argv[1]); + * exit(1); + * } + */ +int main(int argc, char *argv[]) +{ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + return 0; + } + + return 1; +} diff --git a/ccan/foreach/foreach.c b/ccan/foreach/foreach.c new file mode 100644 index 00000000..07108b67 --- /dev/null +++ b/ccan/foreach/foreach.c @@ -0,0 +1,158 @@ +#include +#include +#include +#include +#include + +#if !HAVE_COMPOUND_LITERALS || !HAVE_FOR_LOOP_DECLARATION +/* This list is normally very short. */ +static LIST_HEAD(iters); + +struct iter_info { + struct list_node list; + const void *index; + unsigned int i, num; +}; + +static void free_old_iters(const void *index) +{ + struct iter_info *i, *next; + + list_for_each_safe(&iters, i, next, list) { + /* If we're re-using an index, free the old one. + * Otherwise, if it's past i on the stack, it's old. Don't + * assume stack direction, but we know index is downstack. */ + if (i->index == index + || (((uintptr_t)index < (uintptr_t)&i) + == ((uintptr_t)&i < (uintptr_t)i->index))) { + list_del(&i->list); + free(i); + } + } +} + +static struct iter_info *find_iter(const void *index) +{ + struct iter_info *i; + + list_for_each(&iters, i, list) { + if (i->index == index) + return i; + } + abort(); +} + +static struct iter_info *new_iter(const void *index) +{ + struct iter_info *info = malloc(sizeof *info); + info->index = index; + info->i = info->num = 0; + list_add(&iters, &info->list); + return info; +}; + +#if HAVE_COMPOUND_LITERALS +void _foreach_iter_init(const void *i) +{ + free_old_iters(i); + new_iter(i); +} + +unsigned int _foreach_iter(const void *i) +{ + struct iter_info *info = find_iter(i); + return info->i; +} + +unsigned int _foreach_iter_inc(const void *i) +{ + struct iter_info *info = find_iter(i); + return ++info->i; +} +#else /* Don't have compound literals... */ +int _foreach_term = 0x42430199; + +/* We count values at beginning, and every time around the loop. We change + * the terminator each time, so we don't get fooled in case it really appears + * in the list. */ +static unsigned int count_vals(struct iter_info *info, va_list *ap) +{ + unsigned int i; + int val = 0; + + for (i = 0; i < info->num || val != _foreach_term; i++) { + val = va_arg(*ap, int); + } + _foreach_term++; + return i; +} + +int _foreach_intval_init(const void *i, int val, ...) +{ + va_list ap; + struct iter_info *info; + + free_old_iters(i); + info = new_iter(i); + + va_start(ap, val); + info->num = count_vals(info, &ap); + va_end(ap); + + return val; +} + +bool _foreach_intval_done(const void *i) +{ + struct iter_info *info = find_iter(i); + return info->i == info->num; +} + +int _foreach_intval_next(const void *i, int val, ...) +{ + struct iter_info *info = find_iter(i); + va_list ap; + unsigned int num; + + va_start(ap, val); + info->num = count_vals(info, &ap); + va_end(ap); + + info->i++; + assert(info->i <= info->num); + if (info->i == info->num) + return 0; + + va_start(ap, val); + for (num = 0; num < info->i; num++) + val = va_arg(ap, int); + + va_end(ap); + return val; +} + +void *_foreach_ptrval_init(const void *i, const void *val, ...) +{ + struct iter_info *info; + + free_old_iters(i); + info = new_iter(i); + + return (void *)val; +} + +void *_foreach_ptrval_next(const void *i, const void *val, ...) +{ + struct iter_info *info = find_iter(i); + va_list ap; + unsigned int num; + + info->i++; + va_start(ap, val); + for (num = 0; num < info->i; num++) + val = va_arg(ap, void *); + va_end(ap); + return (void *)val; +} +#endif /* !HAVE_COMPOUND_LITERALS */ +#endif /* !HAVE_COMPOUND_LITERALS || !HAVE_FOR_LOOP_DECLARATION */ diff --git a/ccan/foreach/foreach.h b/ccan/foreach/foreach.h new file mode 100644 index 00000000..16471894 --- /dev/null +++ b/ccan/foreach/foreach.h @@ -0,0 +1,107 @@ +#ifndef CCAN_FOREACH_H +#define CCAN_FOREACH_H +#include "config.h" +#include +#include +#include + +#if HAVE_COMPOUND_LITERALS +#if HAVE_FOR_LOOP_DECLARATION +/** + * foreach_int - iterate over a fixed series of integers + * @i: the int-compatible iteration variable + * @val: one or more integer-compatible values + * + * This is a convenient wrapper function for setting a variable to one or + * more explicit values in turn. continue and break work as expected. + * + * Example: + * int i; + * foreach_int(i, 0, -1, 100, 0, -99) { + * printf("i is %i\n", i); + * } + */ +#define foreach_int(i, val, ...) \ + for (unsigned _foreach_i = ((i) = val, 0); \ + _foreach_i < sizeof((int[]) { val, __VA_ARGS__ })/sizeof(val); \ + (i) = (int[]) { val, __VA_ARGS__, 0 }[++_foreach_i]) + +/** + * foreach_ptr - iterate over a non-NULL series of pointers + * @i: the pointer iteration variable + * @val: one or more compatible pointer values + * + * This is a convenient wrapper function for setting a variable to one + * or more explicit values in turn. None of the values can be NULL; + * that is the termination condition (ie. @i will be NULL on + * completion). continue and break work as expected. + * + * Example: + * const char *p; + * foreach_ptr(p, "Hello", "world") { + * printf("p is %s\n", p); + * } + */ +#define foreach_ptr(i, val, ...) \ + for (unsigned _foreach_i = (unsigned long)((i) = (val), 0); \ + (i); \ + (i) = ((FOREACH_TYPEOF(val)[]){(val), __VA_ARGS__, NULL}) \ + [++_foreach_i]) \ + _foreach_no_nullval(_foreach_i, i, \ + ((void *[]){ val, __VA_ARGS__}))) +#else /* !HAVE_FOR_LOOP_DECLARATION */ +/* GCC in C89 mode still has compound literals, but no for-declarations */ +#define foreach_int(i, val, ...) \ + for ((i) = (val), _foreach_iter_init(&(i)); \ + _foreach_iter(&(i)) < sizeof((int[]) { (val), __VA_ARGS__ }) \ + / sizeof(int); \ + (i) = (int[]) { (val), __VA_ARGS__, 0 }[_foreach_iter_inc(&(i))]) + +#define foreach_ptr(i, val, ...) \ + for ((i) = (val), _foreach_iter_init(&(i)); \ + (i); \ + (i) = ((FOREACH_TYPEOF(val)[]){ (val), __VA_ARGS__, 0 }) \ + [_foreach_iter_inc(&(i))], \ + _foreach_no_nullval(_foreach_iter(&(i)), i, \ + ((void *[]){ val, __VA_ARGS__}))) + +void _foreach_iter_init(const void *i); +unsigned int _foreach_iter(const void *i); +unsigned int _foreach_iter_inc(const void *i); + +#endif /* !HAVE_FOR_LOOP_DECLARATION */ + +/* Make sure they don't put NULL values into array! */ +#define _foreach_no_nullval(i, p, arr) \ + assert((i) >= sizeof(arr)/sizeof(arr[0]) || (p)) + +#if HAVE_TYPEOF +#define FOREACH_TYPEOF(val) __typeof__(&*(val)) +#else +#define FOREACH_TYPEOF(val) void * +#endif + +#else /* !HAVE_COMPOUND_LITERALS */ + +/* No compound literals, but it's still (just) possible. */ +#define foreach_int(i, val, ...) \ + for (i = _foreach_intval_init(&(i), val, __VA_ARGS__, \ + _foreach_term); \ + !_foreach_intval_done(&i); \ + i = _foreach_intval_next(&(i), val, __VA_ARGS__, \ + _foreach_term)) + +#define foreach_ptr(i, val, ...) \ + for (i = _foreach_ptrval_init(&(i), val, __VA_ARGS__, NULL); \ + (i); \ + i = _foreach_ptrval_next(&(i), val, __VA_ARGS__, NULL)) + +extern int _foreach_term; +int _foreach_intval_init(const void *i, int val, ...); +bool _foreach_intval_done(const void *i); +int _foreach_intval_next(const void *i, int val, ...); +void *_foreach_ptrval_init(const void *i, const void *val, ...); +void *_foreach_ptrval_next(const void *i, const void *val, ...); +#endif /* !HAVE_COMPOUND_LITERALS */ + +#endif /* CCAN_FOREACH_H */ diff --git a/ccan/foreach/test/run-break.c b/ccan/foreach/test/run-break.c new file mode 100644 index 00000000..c7bc529a --- /dev/null +++ b/ccan/foreach/test/run-break.c @@ -0,0 +1,38 @@ +#include +#include +#include +#include +#include + +static int count_iters(void) +{ + unsigned int count = 0; +#if !HAVE_COMPOUND_LITERALS || !HAVE_FOR_LOOP_DECLARATION + struct iter_info *i; + + list_for_each(&iters, i, list) + count++; +#endif + return count; +} + +int main(void) +{ + int i, j, sum; + + plan_tests(2); + + sum = 0; + foreach_int(i, 0, 1, 2, 3, 4) { + foreach_int(j, 0, 1, 2, 3, 4) { + sum += i*j; + if (j == i) + break; + } + } + ok1(sum == 65); + ok1(count_iters() <= 2); + + return exit_status(); +} + diff --git a/ccan/foreach/test/run-nested.c b/ccan/foreach/test/run-nested.c new file mode 100644 index 00000000..13ab4667 --- /dev/null +++ b/ccan/foreach/test/run-nested.c @@ -0,0 +1,102 @@ +#include +#include +#include +#include +#include + +static int test_int_recursion(unsigned int level) +{ + int i, sum = 0; + + foreach_int(i, 0, 1, 2, 3, 4) { + sum += i; + if (i > level) + sum += test_int_recursion(i); + } + return sum; +} + +static int test_ptr_recursion(const char *level) +{ + int sum = 0; + const char *i; + + foreach_ptr(i, "0", "1", "2", "3", "4") { + sum += atoi(i); + if (atoi(i) > atoi(level)) + sum += test_ptr_recursion(i); + } + return sum; +} + +static int count_iters(void) +{ + unsigned int count = 0; +#if !HAVE_COMPOUND_LITERALS || !HAVE_FOR_LOOP_DECLARATION + struct iter_info *i; + + list_for_each(&iters, i, list) + count++; +#endif + return count; +} + +int main(void) +{ + int i, j, sum; + const char *istr, *jstr; + + plan_tests(12); + + sum = 0; + foreach_int(i, 0, 1, 2, 3, 4) + foreach_int(j, 0, 1, 2, 3, 4) + sum += i*j; + diag("sum = %i\n", sum); + diag("iters = %i\n", count_iters()); + ok1(sum == 100); + ok1(count_iters() <= 2); + + /* Same again... reusing iterators. */ + sum = 0; + foreach_int(i, 0, 1, 2, 3, 4) + foreach_int(j, 0, 1, 2, 3, 4) + sum += i*j; + diag("sum = %i\n", sum); + diag("iters = %i\n", count_iters()); + ok1(sum == 100); + ok1(count_iters() <= 2); + + sum = test_int_recursion(0); + diag("sum = %i\n", sum); + diag("iters = %i\n", count_iters()); + ok1(sum == 160); + ok1(count_iters() <= 2 + 5); /* 5 is max depth of recursion. */ + + sum = 0; + foreach_ptr(istr, "0", "1", "2", "3", "4") + foreach_ptr(jstr, "0", "1", "2", "3", "4") + sum += atoi(istr)*atoi(jstr); + diag("sum = %i\n", sum); + diag("iters = %i\n", count_iters()); + ok1(sum == 100); + ok1(count_iters() <= 2 + 5 + 2); + + /* Same again... reusing iterators. */ + sum = 0; + foreach_ptr(istr, "0", "1", "2", "3", "4") + foreach_ptr(jstr, "0", "1", "2", "3", "4") + sum += atoi(istr)*atoi(jstr); + diag("sum = %i\n", sum); + diag("iters = %i\n", count_iters()); + ok1(sum == 100); + ok1(count_iters() <= 2 + 5 + 2); + + sum = test_ptr_recursion("0"); + diag("sum = %i\n", sum); + diag("iters = %i\n", count_iters()); + ok1(sum == 160); + ok1(count_iters() <= 2 + 5 + 2); + return exit_status(); +} + diff --git a/ccan/foreach/test/run.c b/ccan/foreach/test/run.c new file mode 100644 index 00000000..d12b6274 --- /dev/null +++ b/ccan/foreach/test/run.c @@ -0,0 +1,29 @@ +#include +#include +#include +#include +#include + +int main(void) +{ + int i, expecti; + const char *p, *expectp[] = { "hello", "there", "big", "big", "world" }; + + plan_tests(11); + + expecti = 0; + foreach_int(i, 0, 1, 2, 3, 4) { + ok1(i == expecti); + expecti++; + } + + expecti = 0; + foreach_ptr(p, "hello", "there", "big", "big", "world") { + ok1(strcmp(expectp[expecti], p) == 0); + expecti++; + } + ok1(p == NULL); + + return exit_status(); +} + diff --git a/config.h b/config.h index 82537b28..52c6fdd4 100644 --- a/config.h +++ b/config.h @@ -18,6 +18,8 @@ #define HAVE_BUILTIN_POPCOUNTL 1 #define HAVE_BUILTIN_TYPES_COMPATIBLE_P 1 #define HAVE_BYTESWAP_H 1 +#define HAVE_COMPOUND_LITERALS 1 +#define HAVE_FOR_LOOP_DECLARATION 0 #define HAVE_GETPAGESIZE 1 #define HAVE_LITTLE_ENDIAN 1 #define HAVE_MMAP 1 -- 2.39.2