[ccan] [PATCH] RFC: generator: Generators for C

[David Gibson]

Yeah, yeah, I should finish one module before making another.  What
can I say, I like my Python generators and I was intrigued to see if I
could do it in C.

This draft is very limited - generators can't take parameters and
always return ints.  I have some ideas on how to fix that, but for now
wanted to send this out for comment.  Frankly, I'm kind of stoked it
worked even this much.

Generators are a limited for of co-routine, which people may be familiar
with from Python.  This module adds an implementation of generators for C.

Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
---
 ccan/generator/LICENSE     |  1 +
 ccan/generator/_info       | 56 +++++++++++++++++++++++++++++++++++++++++++
 ccan/generator/generator.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++
 ccan/generator/generator.h | 47 ++++++++++++++++++++++++++++++++++++
 ccan/generator/test/run.c  | 37 ++++++++++++++++++++++++++++
 5 files changed, 201 insertions(+)
 create mode 120000 ccan/generator/LICENSE
 create mode 100644 ccan/generator/_info
 create mode 100644 ccan/generator/generator.c
 create mode 100644 ccan/generator/generator.h
 create mode 100644 ccan/generator/test/run.c

diff --git a/ccan/generator/LICENSE b/ccan/generator/LICENSE
new file mode 120000
index 0000000..dc314ec
--- /dev/null
+++ b/ccan/generator/LICENSE
@@ -0,0 +1 @@
+../../licenses/LGPL-2.1
\ No newline at end of file
diff --git a/ccan/generator/_info b/ccan/generator/_info
new file mode 100644
index 0000000..0d9bc6b
--- /dev/null
+++ b/ccan/generator/_info
@@ -0,0 +1,56 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * generator - generators for C
+ *
+ * Generators are a limited form of coroutines, which provide a useful
+ * way of expressing certain problems, while being much simpler to
+ * understand than general coroutines.
+ *
+ * Instead of returning a single value, a generator can "yield" a
+ * value at various points during its execution.  Whenever it yields,
+ * the "calling" function resumes and obtains the newly yielded value
+ * to work with.  When the caller asks for the next value from the
+ * generator, the generator resumes execution from the last yield and
+ * continues onto the next.
+ *
+ * Example:
+ *	#include <stdio.h>
+ *	#include <ccan/generator/generator.h>
+ *
+ *	generator_def(simple_gen)
+ *	{
+ *      	yield(1);
+ *		yield(3);
+ *		yield(17);
+ *	}
+ *
+ *	int main(int argc, char *argv[])
+ *	{
+ *		struct generator_state *gen = simple_gen();
+ *		int val;
+ *
+ *		while(generator_getnext(gen, val)) {
+ *			printf("Generator returned %d\n", val);
+ *		}
+ *
+ *		return 0;
+ *	}
+ *
+ * License: LGPL (v2.1 or any later version)
+ * Author: David Gibson <david at gibsond.dropbear.id.au>
+ */
+int main(int argc, char *argv[])
+{
+	/* Expect exactly one argument */
+	if (argc != 2)
+		return 1;
+
+	if (strcmp(argv[1], "depends") == 0) {
+		return 0;
+	}
+
+	return 1;
+}
diff --git a/ccan/generator/generator.c b/ccan/generator/generator.c
new file mode 100644
index 0000000..0201de0
--- /dev/null
+++ b/ccan/generator/generator.c
@@ -0,0 +1,60 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+
+#include <stdlib.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+#include <ccan/generator/generator.h>
+
+#define STATE_SIZE 8192
+#define STACK_SIZE (STATE_SIZE - sizeof(struct generator_state))
+
+static void *stack(void *p)
+{
+	return (void *)((ptrdiff_t)p & ~(STATE_SIZE - 1));
+}
+
+static struct generator_state *state(void *p)
+{
+	return (struct generator_state *)((char *)stack(p) + STACK_SIZE);
+}
+
+static void wrapper(void)
+{
+	struct generator_state *s;
+
+	s = state(&s);
+	s->fn(s);
+	s->complete = true;
+	setcontext(&s->caller);
+}
+
+struct generator_state *__generator_start(void (*fn)(struct generator_state *))
+{
+	void *ss;
+	struct generator_state *s;
+
+	if (posix_memalign(&ss, STATE_SIZE, STATE_SIZE) < 0)
+		abort();
+
+	s = state(ss);
+
+	s->complete = false;
+	s->fn = fn;
+
+	getcontext(&s->gen);
+
+	s->gen.uc_stack.ss_sp = ss;
+	s->gen.uc_stack.ss_size = STACK_SIZE;
+
+	makecontext(&s->gen, wrapper, 0);
+
+	return s;
+}
+
+void generator_cleanup(struct generator_state *s)
+{
+	void *stack = (char *)s - STACK_SIZE;
+
+	free(stack);
+}
diff --git a/ccan/generator/generator.h b/ccan/generator/generator.h
new file mode 100644
index 0000000..a152980
--- /dev/null
+++ b/ccan/generator/generator.h
@@ -0,0 +1,47 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+#ifndef CCAN_GENERATOR_H
+#define CCAN_GENERATOR_H
+#include "config.h"
+
+#include <stdlib.h>
+#include <stdbool.h>
+#include <ucontext.h>
+
+struct generator_state {
+	bool complete;
+	void (*fn)(struct generator_state *);
+	ucontext_t gen;
+	ucontext_t caller;
+	int ret;
+};
+
+struct generator_state *__generator_start(void (*)(struct generator_state *));
+
+#define generator_def(name) \
+	static void __generator__##name(struct generator_state *__generator__state__); \
+	static struct generator_state *name(void) \
+	{ \
+		return __generator_start(__generator__##name); \
+	} \
+	static void __generator__##name(struct generator_state *__generator__state__)
+
+#define yield(val) \
+	do { \
+		__generator__state__->ret = (val); \
+		if (swapcontext(&__generator__state__->gen, \
+				&__generator__state__->caller) < 0)	\
+			abort(); \
+	} while (0)
+
+#define generator_getnext(s, v)			\
+	({ \
+		if (!(s)->complete  && swapcontext(&(s)->caller, \
+						   &(s)->gen) < 0)	\
+			abort(); \
+		(v) = (s)->ret; \
+		(s)->complete; \
+	})
+
+void generator_cleanup(struct generator_state *s);
+
+#endif /* CCAN_GENERATOR_H */
diff --git a/ccan/generator/test/run.c b/ccan/generator/test/run.c
new file mode 100644
index 0000000..ca8a80b
--- /dev/null
+++ b/ccan/generator/test/run.c
@@ -0,0 +1,37 @@
+#include <ccan/generator/generator.h>
+#include <ccan/tap/tap.h>
+
+#include <ccan/generator/generator.c>
+
+generator_def(gen1)
+{
+	yield(1);
+	yield(3);
+	yield(17);
+}
+
+static void test1(void)
+{
+	struct generator_state *state1 = gen1();
+	int val;
+
+	ok1(!generator_getnext(state1, val));
+	ok1(val == 1);
+	ok1(!generator_getnext(state1, val));
+	ok1(val == 3);
+	ok1(!generator_getnext(state1, val));
+	ok1(val == 17);
+	ok1(generator_getnext(state1, val));
+	generator_cleanup(state1);
+}
+
+int main(void)
+{
+	/* This is how many tests you plan to run */
+	plan_tests(7);
+
+	test1();
+
+	/* This exits depending on whether all tests passed */
+	return exit_status();
+}
-- 
1.9.3