From: David Gibson Date: Thu, 25 Feb 2016 11:07:17 +0000 (+1100) Subject: generator: Generators for C X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=707a8c0a899a4b645bcf778f7ea79565d6f3f13e generator: Generators for C Generators are a limited form 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 --- diff --git a/Makefile-ccan b/Makefile-ccan index 2c80720c..a0be58f8 100644 --- a/Makefile-ccan +++ b/Makefile-ccan @@ -64,6 +64,7 @@ MODS_WITH_SRC := aga \ err \ failtest \ foreach \ + generator \ grab_file \ hash \ heap \ diff --git a/ccan/generator/LICENSE b/ccan/generator/LICENSE new file mode 120000 index 00000000..dc314eca --- /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 00000000..a6570e37 --- /dev/null +++ b/ccan/generator/_info @@ -0,0 +1,71 @@ +#include "config.h" +#include +#include + +/** + * 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 + * #include + * + * generator_def_static(simple_gen, int) + * { + * generator_yield(1); + * generator_yield(3); + * generator_yield(17); + * } + * + * int main(int argc, char *argv[]) + * { + * generator_t(int) gen = simple_gen(); + * int *ret; + * + * while ((ret = generator_next(gen)) != NULL) { + * printf("Generator returned %d\n", *ret); + * } + * + * return 0; + * } + * + * Author: David Gibson + * License: LGPL (v2.1 or any later version) + * + * Ccanlint: + * // We need several gcc extensions + * objects_build_without_features FAIL + * tests_compile_without_features FAIL + * tests_helpers_compile_without_features FAIL + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/build_assert\n"); + printf("ccan/ptrint\n"); + printf("ccan/alignof\n"); + printf("ccan/cppmagic\n"); + return 0; + } + + if (strcmp(argv[1], "testdepends") == 0) { + printf("ccan/str\n"); + return 0; + } + + return 1; +} diff --git a/ccan/generator/generator.c b/ccan/generator/generator.c new file mode 100644 index 00000000..d2176656 --- /dev/null +++ b/ccan/generator/generator.c @@ -0,0 +1,54 @@ +/* Licensed LGPLv2.1+ - see LICENSE file for details */ +#include +#include +#include + +#include + +#include + +#define DEFAULT_STATE_SIZE 8192 +#define STATE_ALIGN ALIGNOF(struct generator_) + +void *generator_new_(generator_wrapper_ *fn, size_t retsize) +{ + char *base; + size_t size = DEFAULT_STATE_SIZE; + void *ret; + struct generator_ *gen; + + base = malloc(size); + if (!base) + abort(); + + retsize = (retsize + STATE_ALIGN) & ~(STATE_ALIGN - 1); + ret = base + size - retsize; + gen = (struct generator_ *)ret - 1; + + gen->base = base; + gen->complete = false; + + getcontext(&gen->gen); + + gen->gen.uc_stack.ss_sp = gen->base; + gen->gen.uc_stack.ss_size = (char *)gen - base; + + if (HAVE_POINTER_SAFE_MAKECONTEXT) { + makecontext(&gen->gen, (void *)fn, 1, ret); + } else { + ptrdiff_t si = ptr2int(ret); + ptrdiff_t mask = (1UL << (sizeof(int) * 8)) - 1; + int lo = si & mask; + int hi = si >> (sizeof(int) * 8); + + makecontext(&gen->gen, (void *)fn, 2, lo, hi); + } + + return ret; +} + +void generator_free_(void *ret) +{ + struct generator_ *gen = generator_state_(ret); + free(gen->base); +} diff --git a/ccan/generator/generator.h b/ccan/generator/generator.h new file mode 100644 index 00000000..6b2bd92f --- /dev/null +++ b/ccan/generator/generator.h @@ -0,0 +1,202 @@ +/* Licensed under LGPLv2.1+ - see LICENSE file for details */ +#ifndef CCAN_GENERATOR_H +#define CCAN_GENERATOR_H +#include "config.h" + +#if !HAVE_UCONTEXT +#error Generators require working ucontext.h functions +#endif + +#if !HAVE_TYPEOF +#error Generators require typeof +#endif + +#if !HAVE_STATEMENT_EXPR +#error Generators require statement expressions +#endif + +#include +#include +#include +#include + +#include +#include +#include + +/* + * Internals - included just for the use of inlines and macros + */ + +struct generator_ { + ucontext_t gen; + ucontext_t caller; + bool complete; + void *base; +}; + +static inline struct generator_ *generator_state_(const void *ret) +{ + return (struct generator_ *)ret - 1; +} + +struct generator_incomplete_; + +#define generator_rtype_(gen_) \ + typeof((*(gen_))((struct generator_incomplete_ *)NULL)) + +#if HAVE_POINTER_SAFE_MAKECONTEXT +#define generator_wrapper_args_() void *ret +#else +#define generator_wrapper_args_() int lo, int hi +#endif +typedef void generator_wrapper_(generator_wrapper_args_()); + +void *generator_new_(generator_wrapper_ *fn, size_t retsize); +void generator_free_(void *ret); + +/* + * API + */ + +/** + * generator_t - type for an in-progress generator + * @rtype: type of values the generator yield + */ +#define generator_t(rtype_) \ + typeof(rtype_ (*)(struct generator_incomplete_ *)) + +/** + * generator_declare - declare (but don't define) a generator function + * @name: name for the generator + * @rtype: return type for the generator + * + * Declares (as an extern) a generator function named @name, which + * will yield return values of type @rtype. + * + * Example: + * generator_declare(count_to_3, int); + */ +#define generator_declare(name_, rtype_) \ + generator_t(rtype_) name_(void) + +/** + * generator_def - define a generator function + * @name: name for the generator + * @rtype: return type for the generator + * + * Define a generator function named @name yielding return values of + * type @rtype. The generator_def() line is followed immediately by a + * block containing the generator's code. + * + * Example: + * generator_def(count_to_3, int) + * { + * generator_yield(1); + * generator_yield(2); + * generator_yield(3); + * } + */ +#define generator_def_(name_, rtype_, storage_) \ + static void name_##_generator_(rtype_ *ret_); \ + static void name_##_generator__(generator_wrapper_args_()) \ + { \ + struct generator_ *gen; \ + CPPMAGIC_IFELSE(HAVE_POINTER_SAFE_MAKECONTEXT) \ + () \ + (ptrdiff_t hilo = ((ptrdiff_t)hi << (8*sizeof(int))) \ + + (ptrdiff_t)lo; \ + rtype_ *ret = (rtype_ *)int2ptr(hilo); \ + BUILD_ASSERT(sizeof(struct generator_ *) \ + <= 2*sizeof(int));) \ + gen = generator_state_(ret); \ + name_##_generator_(ret); \ + gen->complete = true; \ + setcontext(&gen->caller); \ + assert(0); \ + } \ + storage_ generator_t(rtype_) name_(void) \ + { \ + return generator_new_(name_##_generator__, \ + sizeof(rtype_)); \ + } \ + static void name_##_generator_(rtype_ *ret_) +#define generator_def(name_, rtype_) \ + generator_def_(name_, rtype_, ) + +/** + * generator_def_static - define a private / local generator function + * @name: name for the generator + * @rtype: return type for the generator + * + * As generator_def, but the resulting generator function will be + * local to this module. + */ +#define generator_def_static(name_, rtype_) \ + generator_def_(name_, rtype_, static) + +/** + * generator_yield - yield (return) a value from a generator + * @val: value to yield + * + * Invoke only from within a generator. Yield the given value to the + * caller. This will stop execution of the generator code until the + * caller next invokes generator_next(), at which point it will + * continue from the generator_yield statement. + */ +#define generator_yield(val_) \ + do { \ + struct generator_ *gen_ = generator_state_(ret_); \ + int rc; \ + *(ret_) = (val_); \ + rc = swapcontext(&gen_->gen, &gen_->caller); \ + assert(rc == 0); \ + } while (0) + +/** + * generator_next - get next value from a generator + * @gen: a generator state variable + * + * Returns a pointer to a (correctly typed) buffer containing the next + * value yielded by @gen, or NULL if @gen is finished. The buffer + * contents is only valid until the next time @gen is called or + * manipulated. + */ +static inline void *generator_next_(void *ret_) +{ + struct generator_ *gen = generator_state_(ret_); + int rc; + + if (gen->complete) + return NULL; + + rc = swapcontext(&gen->caller, &gen->gen); + assert(rc == 0); + + return gen->complete ? NULL : ret_; +} +#define generator_next(gen_) \ + ((generator_rtype_(gen_) *)generator_next_(gen_)) + +/** + * generator_next_val - store next value from a generator + * @val: a variable of type suitable to store the generator's return + * type (lvalue) + * @gen: a generator state variable + * + * Returns 'true' if @gen yielded a new value, false if @gen is + * complete. If a new value was yielded, it is stored in @val. + */ +#define generator_next_val(val_, gen_) \ + ({ \ + generator_rtype_(gen_) *ret; \ + ret = generator_next(gen_); \ + if (ret) \ + (val_) = *ret; \ + !!ret; \ + }) + +#define generator_free(gen_) \ + generator_free_((generator_rtype_(gen_) *)(gen_)) + +#endif /* CCAN_GENERATOR_H */ diff --git a/ccan/generator/test/api.c b/ccan/generator/test/api.c new file mode 100644 index 00000000..a5770fd2 --- /dev/null +++ b/ccan/generator/test/api.c @@ -0,0 +1,62 @@ +#include +#include +#include + +#include "example-gens.h" + +generator_def_static(genx, const char *) +{ + generator_yield("one"); + generator_yield("two"); + generator_yield("three"); + generator_yield("four"); +} + +static void test1(void) +{ + generator_t(int) state1 = gen1(); + int *ret; + + ok1((ret = generator_next(state1)) != NULL); + ok1(*ret == 1); + ok1((ret = generator_next(state1)) != NULL); + ok1(*ret == 3); + ok1((ret = generator_next(state1)) != NULL); + ok1(*ret == 17); + ok1((ret = generator_next(state1)) == NULL); + + /* Test that things don't go bad if we try to invoke an + * already completed generator */ + ok1((ret = generator_next(state1)) == NULL); + + generator_free(state1); +} + +static void testx(void) +{ + generator_t(const char *) statex = genx(); + const char *val; + + ok1(generator_next_val(val, statex)); + ok1(streq(val, "one")); + ok1(generator_next_val(val, statex)); + ok1(streq(val, "two")); + ok1(generator_next_val(val, statex)); + ok1(streq(val, "three")); + ok1(generator_next_val(val, statex)); + ok1(streq(val, "four")); + ok1(!generator_next_val(val, statex)); + generator_free(statex); +} + +int main(void) +{ + /* This is how many tests you plan to run */ + plan_tests(8 + 9); + + test1(); + testx(); + + /* This exits depending on whether all tests passed */ + return exit_status(); +} diff --git a/ccan/generator/test/compile_fail-1.c b/ccan/generator/test/compile_fail-1.c new file mode 100644 index 00000000..38e623a3 --- /dev/null +++ b/ccan/generator/test/compile_fail-1.c @@ -0,0 +1,21 @@ +#include +#include + +#include + +#include + +#include "example-gens.h" + +int main(int argc, char *argv[]) +{ +#ifdef FAIL + int *g = gen1(); +#else + generator_t(int) g = gen1(); +#endif + + printf("%d", *generator_next(g)); + + exit(0); +} diff --git a/ccan/generator/test/compile_fail-2.c b/ccan/generator/test/compile_fail-2.c new file mode 100644 index 00000000..7f241314 --- /dev/null +++ b/ccan/generator/test/compile_fail-2.c @@ -0,0 +1,21 @@ +#include +#include + +#include + +#include + +#include "example-gens.h" + +int main(int argc, char *argv[]) +{ +#ifdef FAIL + generator_t(char) g = gen1(); +#else + generator_t(int) g = gen1(); +#endif + + printf("%d", *generator_next(g)); + + exit(0); +} diff --git a/ccan/generator/test/compile_fail-3.c b/ccan/generator/test/compile_fail-3.c new file mode 100644 index 00000000..9347efc0 --- /dev/null +++ b/ccan/generator/test/compile_fail-3.c @@ -0,0 +1,24 @@ +#include +#include + +#include + +#include + +generator_def_static(intgen, int) +{ +#ifdef FAIL + generator_yield("a"); +#else + generator_yield(1); +#endif +} + +int main(int argc, char *argv[]) +{ + generator_t(int) g = intgen(); + + printf("%d", *generator_next(g)); + + exit(0); +} diff --git a/ccan/generator/test/compile_fail-4.c b/ccan/generator/test/compile_fail-4.c new file mode 100644 index 00000000..f7297cff --- /dev/null +++ b/ccan/generator/test/compile_fail-4.c @@ -0,0 +1,23 @@ +#include +#include + +#include + +#include + +#include "example-gens.h" + +int main(int argc, char *argv[]) +{ + generator_t(int) g = gen1(); +#ifdef FAIL + char *val; +#else + int val; +#endif + + generator_next_val(val, g); + printf("%d", val); + + exit(0); +} diff --git a/ccan/generator/test/compile_fail-5.c b/ccan/generator/test/compile_fail-5.c new file mode 100644 index 00000000..ba8ced9e --- /dev/null +++ b/ccan/generator/test/compile_fail-5.c @@ -0,0 +1,21 @@ +#include +#include + +#include + +#include + +#include "example-gens.h" + +int main(int argc, char *argv[]) +{ +#ifdef FAIL + int *g = NULL; +#else + generator_t(int) g = gen1(); +#endif + + generator_free(g); + + exit(0); +} diff --git a/ccan/generator/test/example-gens.c b/ccan/generator/test/example-gens.c new file mode 100644 index 00000000..c5540116 --- /dev/null +++ b/ccan/generator/test/example-gens.c @@ -0,0 +1,10 @@ +#include + +#include "example-gens.h" + +generator_def(gen1, int) +{ + generator_yield(1); + generator_yield(3); + generator_yield(17); +} diff --git a/ccan/generator/test/example-gens.h b/ccan/generator/test/example-gens.h new file mode 100644 index 00000000..cf4ce3bc --- /dev/null +++ b/ccan/generator/test/example-gens.h @@ -0,0 +1,8 @@ +#ifndef _EXAMPLE_GENS_H +#define _EXAMPLE_GENS_H + +#include + +generator_declare(gen1, int); + +#endif /* _EXAMPLE_GENS_H */