Merry solstice, everyone.

Beowulf Movie

Soulless two hour-long videogame cutscene. Avoid.

Coroutines in C

Ran into a design issue while working on this programming problem.

I'm storing words in a trie:

struct trie_node {
        const char *key;
        struct trie_node children[NCHILDREN];
};

... and the procedure that enumerates all words in the trie that correspond to a given sequence of digits is naturally recursive:

static const char *digit_to_char[] = {
        "oqz",
        "ij",   "abc",  "def",
        "gh",   "kl",   "mn",
        "prs",  "tuv",  "wxy"
};
 
/* print out all words in the trie that match a sequence
   of digits */
void find_matches(const struct trie_node *node,
  const char *digits)
{
  const char d = *digits;
 
  if (node->key)
    puts(node->key);
 
  if (d != '\0') {
    const char *p;
 
    for (p = digit_to_char[d - '0']; *p != '\0'; ++p) {
      int next = *p - 'a';
      if (node->children[next] != NULL)
        find_matches(node->children[next], digits + 1);
    }
  }
}

Now, we don't want to simply print out the words, we want to use them to solve the problem, so they must be passed to the problem solving code somehow. We have many options here (mixing the problem solving code with the trie-traversing code does not count as an option):

• Pass a pointer to a callback function to find_matches; where it now prints out the match, it would call this function for every word it found. This is the C way of doing things.
• Turn the function find_matches into an iterator - we'd have a struct to store the search state, and a "method" to return the next match (I actually went with this approach in my solution, and it was accepted). Unfortunately, this means turning our clean recursive code into a stack-based state machine monster.

Another, perhaps less well-known, alternative would involve co- routines. Where find_matches now prints out a result, it would return the result back to the caller; when it gets called again, the state of find_matches is restored to how it was before the return.

While in Scheme we could do this with call-with-current-continuation, there doesn't seem to be a portable or easy way to do something like this in C. Simon Tatham presents a clever trick using Duff's device, but, alas, it doesn't help us in this case, since find_matches is recursive. There are also a couple of co-routine libraries for C out there. I had a bit of fun with bi over ICQ yesterday fixing this one to make it work with newer versions of gcc (bi sent a patch to the author).

Anyway, here are two solutions to the original problem - one of them uses an iterator, and another one uses a co-routine hack built on top of pthreads, inspired by this article (pretend the cr_* stuff at the beginning of the source file is hidden in a library, and the user is not even aware that threads are involved).