foreach: new module
authorRusty Russell <rusty@rustcorp.com.au>
Tue, 2 Nov 2010 01:25:33 +0000 (11:55 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Tue, 2 Nov 2010 01:25:33 +0000 (11:55 +1030)
ccan/foreach/_info [new file with mode: 0644]
ccan/foreach/foreach.c [new file with mode: 0644]
ccan/foreach/foreach.h [new file with mode: 0644]
ccan/foreach/test/run-break.c [new file with mode: 0644]
ccan/foreach/test/run-nested.c [new file with mode: 0644]
ccan/foreach/test/run.c [new file with mode: 0644]
config.h

diff --git a/ccan/foreach/_info b/ccan/foreach/_info
new file mode 100644 (file)
index 0000000..a00ee8b
--- /dev/null
@@ -0,0 +1,70 @@
+#include <stdio.h>
+#include <string.h>
+#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 <rusty@rustcorp.com.au>
+ *
+ * Example:
+ *     // Figure out how to get usage: message out of a program.
+ *     #include <ccan/foreach/foreach.h>
+ *     #include <stdio.h>
+ *     #include <stdlib.h>
+ *     #include <string.h>
+ *     #include <err.h>
+ *
+ *     // 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("</dev/null 2>&1 | grep -qiw usage:"));
+ *             sprintf(command, "%s %s </dev/null 2>&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 <progname>\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 (file)
index 0000000..07108b6
--- /dev/null
@@ -0,0 +1,158 @@
+#include <ccan/foreach/foreach.h>
+#include <ccan/list/list.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <stdarg.h>
+
+#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 (file)
index 0000000..1647189
--- /dev/null
@@ -0,0 +1,107 @@
+#ifndef CCAN_FOREACH_H
+#define CCAN_FOREACH_H
+#include "config.h"
+#include <stddef.h>
+#include <assert.h>
+#include <stdbool.h>
+
+#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 (file)
index 0000000..c7bc529
--- /dev/null
@@ -0,0 +1,38 @@
+#include <ccan/foreach/foreach.h>
+#include <ccan/tap/tap.h>
+#include <stdio.h>
+#include <string.h>
+#include <ccan/foreach/foreach.c>
+
+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 (file)
index 0000000..13ab466
--- /dev/null
@@ -0,0 +1,102 @@
+#include <ccan/foreach/foreach.h>
+#include <ccan/tap/tap.h>
+#include <stdio.h>
+#include <string.h>
+#include <ccan/foreach/foreach.c>
+
+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 (file)
index 0000000..d12b627
--- /dev/null
@@ -0,0 +1,29 @@
+#include <ccan/foreach/foreach.h>
+#include <ccan/tap/tap.h>
+#include <stdio.h>
+#include <string.h>
+#include <ccan/foreach/foreach.c>
+
+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();
+}
+       
index 82537b28878bfc3e5c7fbf499e69191732c9a9ff..52c6fdd4f848ba471960c4ac4a33966c23898e5d 100644 (file)
--- 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