S.l.e!ep.￠%

重写

常见的方式是重写末端的通信管道，把它作为一个可调用的函数。这有个简单的例子。

int decompressor(void) {
    static int repchar;
    static int replen;
    if (replen > 0) {
        replen--;
        return repchar;
    }
    c = getchar();
    if (c == EOF)
        return EOF;
    if (c == 0xFF) {
        replen = getchar();
        repchar = getchar();
        replen--;
        return repchar;
    } else
        return c;
}

void parser(int c) {
    static enum {
        START, IN_WORD
    } state;
    switch (state) {
        case IN_WORD:
        if (isalpha(c)) {
            add_to_token(c);
            return;
        }
        got_token(WORD);
        state = START;
        /* fall through */

        case START:
        add_to_token(c);
        if (isalpha(c))
            state = IN_WORD;
        else
            got_token(PUNCT);
        break;
    }
}

当然你不需要两个都重写；只修改一个就可以。如果把解压片段重写为以上形式，那么每次调用它都返回一个字符，原始的解析代码片段中就可以把调用getchar()改为调用decompressor()，这样程序看起来舒心多了。相反的，如果把解析代码重写为上面的形式，那么每次调用都会输入一个字符，原始的解压代码中可以通过调用parser()替换掉了调用emit()。如果你是个贪婪的人你可以把两个函数都重写，都作为被调用者。

这就是我的真实观点。和两个重写后的函数相比原始的代码丑陋无比，在这里当两个进程被写为调用者而不是被调用者时更易读了。如果你试图通过解析器推断出语法，或者通过解压器了解解压数据格式，只需阅读下代码就可以，同时你会发现原始的代码清晰些，重写后的代码格式上不太清晰，如果没有嵌入另外一者的代码这会更好些。

Knuth协程

在《计算机程序设计艺术》中，Donald Knuth提供了一个解决这类问题的方法。他的方法是彻底丢掉堆栈的概念，不要再想一个进程作为调用者，另一个作为被调用者，把他们当做平等的协作者关系。

实际上就是：把传统的“调用”稍微改为一个不同的方式。新的“调用”将在某个地方保存返回值而不是堆栈上，并且还能跳转到另一个保存返回值的指定位置上。因此，解码器每次生成一个字符，就保存它的程序计数器并且跳转到上次解析器的位置-解析器每次都需要一个新的字符，它保存自己的程序计数器并且跳转到上次解码器的位置。程序可以在两个函数之间来回自如的传递需要的数据了。

基于栈的协程

我们真正想要的是在C中模仿Knuth协程调用原语的能力。我们必须接受这个现实，在C语言中，一个函数将作为调用者，另一个作为被调用者。对于调用者我们没有任何问题；我们按照原始算法写代码就可以，无论什么时候，如果它生成一个字符那么它就需要调用另一个函数。

被调用者有很多问题。对于被调用者，我们想要一个函数，该函数具有“返回并继续”的操作：从函数返回后，当再次调用它，只需要在上次位置继续执行就可以。比如，我们希望写这样一个函数

int function(void) {
    int i;
    for (i = 0; i < 10; i++)
        return i;   /* won't work, but wouldn't it be nice */
}

连续调用这个函数10次，返回0-9的数字。

我们怎么能实现这个呢？好吧，我们可以用一个goto语句将控制跳转到这个函数中的任何一点。所以如果我们有一个状态变量，我们可以这样做：

int function(void) {
    static int i, state = 0;
    switch (state) {
        case 0: goto LABEL0;
        case 1: goto LABEL1;
    }
    LABEL0: /* start of function */
    for (i = 0; i < 10; i++) {
        state = 1; /* so we will come back to LABEL1 */
        return i;
        LABEL1:; /* resume control straight after the return */
    }
}

达夫设备（Duff's Device）

C语言中著名的"达夫设备"利用case语句在其匹配switch语句子块中也是合法的这一事实。Tom Duff利用这个方法优化输出回路：

switch (count % 8) {
        case 0:        do {  *to = *from++;
        case 7:              *to = *from++;
        case 6:              *to = *from++;
        case 5:              *to = *from++;
        case 4:              *to = *from++;
        case 3:              *to = *from++;
        case 2:              *to = *from++;
        case 1:              *to = *from++;
                       } while ((count -= 8) > 0);
    }

int function(void) {
    static int i, state = 0;
    switch (state) {
        case 0: /* start of function */
        for (i = 0; i < 10; i++) {
            state = 1; /* so we will come back to "case 1" */
            return i;
            case 1:; /* resume control straight after the return */
        }
    }
}

#define crBegin static int state=0; switch(state) { case 0:
#define crReturn(i,x) do { state=i; return x; case i:; } while (0)
#define crFinish }
int function(void) {
    static int i;
    crBegin;
    for (i = 0; i < 10; i++)
        crReturn(1, i);
    crFinish;
}

这差不多就是我们想要的了。我们可以通过这种一返回就控制下一个调用回复的方式，用crReturn从函数返回。当然，我们必须遵守一些基本规则（用crBegin和crFinish包住函数体；声明所需的所有保存在acrReturn中的静态局部变量；绝不要在一个显式switch语句中设置一个crReturn）；但那些并不会限制我们太多。

剩下的唯一问题是传给crReturn的第一个参数。就像在上一节引进一个新标签一样，我们必须避免与已存在的标签名冲突，确保所有给crReturn的状态参数都是不同的。这影响是相当小的 -- 编译器会抓住它并并不让它在运行时出错 -- 但我们还是要避免这样做。

虽然这可以解决，ANSI C还是提供了扩展到当前行号的专门的宏名：__LINE__，因此我们可以把crReturn重写成：

#define crReturn(x) do { state=__LINE__; return x; \
                         case __LINE__:; } while (0)

评估

现在我们有了这个畸形的东西，让我们来重写下原始的代码片段吧。

int decompressor(void) {
    static int c, len;
    crBegin;
    while (1) {
        c = getchar();
        if (c == EOF)
            break;
        if (c == 0xFF) {
            len = getchar();
            c = getchar();
            while (len--)
	        crReturn(c);
        } else
	    crReturn(c);
    }
    crReturn(EOF);
    crFinish;
}

void parser(int c) {
    crBegin;
    while (1) {
        /* first char already in c */
        if (c == EOF)
            break;
        if (isalpha(c)) {
            do {
                add_to_token(c);
		crReturn( );
            } while (isalpha(c));
            got_token(WORD);
        }
        add_to_token(c);
        got_token(PUNCT);
	crReturn( );
    }
    crFinish;
}

我们已经重写了解码器和解析器都作为了被调用者，不需要像最后一次那样大规模的重写。每个函数的结构恰好是原始结构的镜像，读者能够通过解析器推断出相应的语法，或者通过解码器了解到解压数据格式，比起读那些状态机代码简单多了。一旦你适应了新的格式，你就会发现控制流程非常直观：当解压器产生一个字符，它就调用crReturn将这个字符传给调用函数，并等待当需要下一个字符时再次被调用。当解析器需要一个新字符时，它通过crReturn返回，并等待下一次被调用时通过参数c传入新的字符。

这里代码里还有一个小的结构变化：parser()中getchar()放在了循环的结尾而不是开头了，这是因为当进入函数时，第一个字符已经通过c传进来了。我们应该可以接受这个小的结构改变，或者如果我们真的对此抱有轻盈态度，我们可以认为在parse()传入数据前，需要一次“初始化”调用。

当然像前面一样，我们不必把两个函数都使用协程的宏重写，修改一个足矣；另一个可以作为他的被调用者。

我们已经取得了我们想要达到的目标：一个可移植的ANSI C在生产者和消费者之间传递数据，而不用状态机重写代码。我们已经通过把一个switch语句的生僻的功能结合C的预处理创建一个隐式的状态机。

编码规范

当然，这种方式违背了书上的编码规范，在公司代码中尝试这样使用你会受到严厉的警告！在宏定义中，你的大括号没有完全匹配，子区块中使用了case，至于crReturn宏中内容不完整···使用这种不负责任的编码实践你没有被解雇真是一种奇迹。你应该感到自行惭愧。

我需要声明下编码规范在这里不适用。在这篇文章里我展示的例子不是很长，也不复杂，即使使用状态机重写也能看懂。但是随着函数变长，重写的难度越来愈大，并且失去了代码清晰度，越来越糟糕。

考虑下，如果一个函数有下面的代码块构成

case STATE1:
    /* perform some activity */
    if (condition) state = STATE2; else state = STATE3;

对于读者来说从函数建立下面的小模块也不是很难

LABEL1:
    /* perform some activity */
    if (condition) goto LABEL2; else goto LABEL3;

一个调用者，一个被调用者。是的，这两个函数在可视结构上是一样的，它们提供的底层算法都非常少。因为使用协程宏想要解雇你的人同样会因为你写的连接goto语句的小块函数而怒斥你！这次它们做对了，因为这样的函数布局破坏了算法的结构。

编程规范目标就是为了清晰。像switch，return和case语句把这些重要的东西隐藏到“不清晰”的宏中，从编程标准角度来看你已经破坏了程序的语法结构，违背了代码清晰的要求。但是我们这样做是为了突出程序的算法结构，而算法结构也正好是读者想要了解的！

任何的编码规范坚持语法的清晰度而牺牲了算法的清晰度都应该被重写。如果你的老板因为使用这个技巧而解雇你，当安保人员把你拖走时要不断告诉他们。

风骚般的编码

在正儿八经的应用程序中，协程很少使用，因为它依赖于静态变量，因此不能重入或者支持多线程。理想情况下，在真实应用程序中，你可能想在多个不同的上下文中调用同一个函数，并且在给定的一个上下文中每次调用时，都能在这个上下文中上一次返回的位置继续执行。

这很容易做到，我们增加一个新的函数参数——一个上下文结构的指针；我们将所有的局部变量和协程用到的状态变量都声明成结构体中的元素.

这样写丑了点，因为突然间你不得不使用ctx->i作为循环计数器而不是之前使用的i；事实上所有重要的变量都成了协程上下文结构体中的元素。但是这消除了重入的问题，并且没有影响到程序的结构。

（当然，要是C有Pascal语言的with语句，我们就可以将这个间接的引用隐藏掉，但是很遗憾没有这些。对于C++语言，我们可以把协程的两个函数设计成类的成员函数，所有的局部变量设计成类的成员变量，从而将作用域的问题隐藏掉）

这儿包含的C语言头文件实现了一套预定义的协程使用的宏。在文件中定义了二套宏函数，前缀分别是scr和ccr。scr宏是一套简单的实现，用于可以使用静态变量的情况；ccr宏更高级一些，能支持重入。在头文件的注释中有完整的说明。

需要注意的是，VC++ 6并不喜欢这种协程技巧，因为其默认的debug状态（Program Database for Edit and Continue）对__LINE__宏的支持有点儿怪。如果想用VC++ 6编译一个使用了协程的宏，你就要关掉Edit and Continue。（在project settings中，选择c/c++标签，在General中，将Debug info改为Program Database for Edit and Continue之外的其他值)。

（这个头文件是MIT许可的，所以你可以任意使用，没有任何限制。如果你发现MIT对你的使用方式有限制，可以给我发邮件，我会考虑给你授权。）

使用 这个链接 获得coroutine.h。

感谢您的阅读。分享才有快乐！

参考文献

• Donald Knuth,计算机编程艺术, 卷 1. Addison-Wesley, ISBN 0-201-89683-4. Section 1.4.2 describes coroutines in the "pure" form.
• http://www.lysator.liu.se/c/duffs-device.html 是 Tom Duff's自己关于Duff策略的讨论。注意，右下角，暗示着Duff有可能独立的完成这样的协程技巧或者其他类似的东西。

  更新与, 2005-03-07: Tom Duff 在一篇博客评论中证实了这一点。“revolting way to use switches to implement interrupt driven state machines”这篇文章中和他最初在邮件中说的确实一样.

• PuTTY是一个 Win32 Telnet 和 SSH 客户端。SSH协议其中一部分使用了协程技巧.，据我所知，这是一个在生产代码中最糟糕的C代码片段的轮子。