In a previous post I introduced a way of bodging coroutines in C by disregarding our better judgment and raw-dogging it and managing many stack pointers ourselves like a bunch of maniacs.

In this post, I slightly modify that library to add support for generators, which are a type of coroutine that can “return” values to sites that know how to ask them nicely.

Generators

So, generators are sort of commonplace in python, javascript et al. but are quite painful to implement in languages like C++. Prior to coroutines in C++20 your best chance was implementing some sort of input iterator class which does the work for you; classically this imposes a lot of restrictions since the “calculation and return sites” are sort of smeared into the iterator’s operator++ and operator* methods, as well as the fact that all of your state has to be managed manually—which makes nontrivial iterators painful to implement (think of managing any nontrivial backtracking explicitly).

Since the call stack structure implicitly manages this sort of thing, it’s actually quite natural to use coroutines and their self-owned stacks as an independent little island you can use to produce any values you need, hand them over to whomever is interested, and then resume your operations as required.

The Basic Idea

Our strategy for implementing this (in the kludgiest way possible), is to augment the coroutine state information with an out of band return channel (ie. a void* you can just put stuff into) and a flag indicating the coroutine runtime whether any particular coroutine is ready to be resumed if the opportunity arises.

This enables us to specialize coroutines into generators, which are spawned and immediately paused; we return the generator’s creator an id so that the creator may retrieve values at a later point. Upon querying a generator for a value, we can search through the coroutines extant at that point, find the particular generator referred to by the id, and unpause it. We then yield execution until the generator has been paused again; this indicates the coroutine backing up that has decided it is done processing its current value and we can then query for that value in the coroutine’s out of band return channel.

Should we not find a particular generator’s id, it means it has been reaped and therefore we can return NULL for any subsequent queries for values.

On the generator’s side, it observes the program “as if” it’s screaming at the void (*) with the coro_return function. What it does behind the scenes is marking it’s coroutine as paused, storing the pointer in the oob channel and yielding back execution.

Code Snippet

You may want to check out the full source code for the modified header and its accompanying example. The highlights are these functions here:

void const* coro_gen(void (*fn)(void*), void* arg) {
	coro_spawn(fn, arg);
	_.items[_.count - 1].paused = true;
	return (void const*) _.items[_.count - 1].id;
}

void* coro_next(void const* generator) {
	bool found = true;
	while (found) {
		found = false;
		// search for generator, unpause it and yield
		for (size_t i = 0; i < _.count; i++) {
			if (_.items[i].id != (size_t) generator)
				continue;
			found = true;
			_.items[i].oob = NULL;
			_.items[i].paused = false;
			coro_yield();
			break; 
		}
		// search for generator, if it's paused, it's finished
		// and we can return it's out of band pointer, otherwise
		// it's still doing work and we have to yield again
		for (size_t i = 0; found && i < _.count; i++) {
			if (_.items[i].id != (size_t) generator)
				continue;
			if (_.items[i].paused) // finished
				return _.items[i].oob;
			coro_yield(); 
		}
		// if we never found the generator, it's already dead,
		// and we have nothing to wait for, and can return a 
		// NULL value.
	}
	return NULL;
}

void coro_return(void* ptr) {
	current()->oob = ptr;
	current()->paused = true;
	coro_yield();
}

An interesting remark to make is that you need to search through the coroutines twice in coro_next for the obvious reason that the size of that array, as well as absolute position of the coroutines therein may change between one yield and another.

Caveats

As is becoming tradition, what can go wrong? Well, a lot, and I haven’t tested this much more than barely at all. But… but it works AFAIK. This is also a shit way of accomplishing this; you’d probably want smarter ways of organizing the coroutines once they have the possibility of being paused. Arguably, they should be stored in an associative container (such as stb’s hash maps) of sorts so that querying is fast, you may even want to have two such maps, so that you don’t iterate through coroutines you know ex ante won’t be resumed; heck, you might even want to keep track of what has paused a particular coroutine, so that you coro_next can pause the current thread while it waits for the generator.

But that’s way more involved than what is befitting of such a temperamental and wildly non-conforming idea as buggering the program stack bare skin on silicon action.