C++ / gcc / linux 中的 Continuations/Coroutines/Generators

Question

背景：我正在尝试通过提出这个玩具问题来弄清楚如何实现continuations / coroutines / generators（无论以下内容叫什么）。环境是C ++ 11在gcc 4.6和Linux 3.0 x86_64上。非可移植性很好，但不允许使用外部库（boost.coroutine，COROUTINE等）。我认为longjmp（3）和/或makecontext（2）可能有所帮助，但不确定。

描述：

以下玩具解析器应该解析长度相等的a和b序列。也就是说

((a+)(b+))+

使得第二个括号内的内容长度等于第三个括号内的内容长度。

当它找到一个产生式（例如 aaabbb），它会输出它所找到的 a 的数量（例如 3）。

代码：

#include <stdlib.h>
#include <iostream>
using namespace std;

const char* s;

void yield()
{
        // TODO: no data, return from produce
        abort();
}

void advance()
{
        s++;
        if (*s == 0)
                yield();
}

void consume()
{
        while (true)
        {
                int i = 0;

                while (*s == 'a')
                {
                        i++;
                        advance();
                }

                cout << i << " ";

                while (i-- > 0)
                {
                    if (*s != 'b')
                        abort();
                    advance();
                }
        }
}

void produce(const char* s_)
{
        s = s_;

        // TODO: data available, continue into consume()
        consume();
}

int main()
{
        produce("aaab");
        produce("bba");
        produce("baa");
        produce("aabbb");
        produce("b");

        // should print: 3 1 4

        return 0;
}

问题：

您可以看到，当调用yield并且produce返回时，必须保存consume的调用堆栈状态。 当再次调用produce时，通过从yield返回来重新启动consume。挑战在于修改produce调用consume的方式，并实现yield使其正常工作。

（显然，重新实现consume以保存和重建其状态会破坏练习的目的。）

我认为需要做的是类似于makecontext手册页面底部的示例http://www.kernel.org/doc/man-pages/online/pages/man3/makecontext.3.html，但不清楚如何将其转换为此问题。 （而我需要睡觉了）

解决方案：

（感谢Chris Dodd的设计）

#include <stdlib.h>
#include <iostream>
#include <ucontext.h>
using namespace std;

const char* s;
ucontext_t main_context, consume_context;

void yield()
{
    swapcontext(&consume_context, &main_context);
}

void advance()
{
    s++;
    if (*s == 0)
            yield();
}

void consume()
{
    while (true)
    {
            int i = 0;

            while (*s == 'a')
            {
                    i++;
                    advance();
            }

            cout << i << " ";

            while (i-- > 0)
            {
                    advance();
            }
    }
}

void produce(const char* s_)
{
    s = s_;

    swapcontext(&main_context, &consume_context);
}

int main()
{
    char consume_stack[4096];

    getcontext(&consume_context);
    consume_context.uc_stack.ss_sp = consume_stack;
    consume_context.uc_stack.ss_size = sizeof(consume_stack);
    makecontext(&consume_context, consume, 0);

    produce("aaab");
    produce("bba");
    produce("baa");
    produce("aabbb");
    produce("b");

    // should print: 3 1 4

    return 0;
}

- Andrew Tomazos

---

你是不是想说 longjmp？我不知道有任何名为 longjump 的函数。 - Ben Voigt

makecontext 被弃用了，如果我没记错的话。 - Alexandre C.

你为什么认为makecontext已经被弃用了？在man页面上并没有提到它的任何信息。 - Andrew Tomazos

哦，这里是：“SUSv2，POSIX.1-2001。POSIX.1-2008删除了makecontext()和swap-context()的规范，引用可移植性问题，并建议重写应用程序以改用POSIX线程。”虽然POSIX线程是抢占式的，可以创建一个全新的克隆进程，但我认为用户空间协作线程对于这种类型的问题来说更具性能优势。 - Andrew Tomazos

Answer 1

使用makecontext/swapcontext实现这个功能非常简单--使用makecontext创建一个新的协程上下文，并使用swapcontext在它们之间切换。在您的情况下，您需要一个额外的协程来运行consume无限循环，并在主上下文中运行main和produce。

因此，main应该调用getcontext+makecontext来创建一个新的上下文，以运行消费循环：

getcontext(&consume_ctxt);
// set up stack in consume_context
makecontext(&consume_ctxt, consume, 0);

这样一来，produce 将会切换到它而不是直接调用 consume :

void produce(const char* s_)
{
    s = s_; 
    swapcontext(&main_ctxt, &consume_ctxt);
}

最后，yield 只是调用 swapcontext(&consume_ctxt, &main_ctxt); 来切换回主上下文（它将在 produce 中继续并立即返回）。

请注意，由于 consume 是一个无限循环，所以您不需要太担心它返回时会发生什么（因此链接永远不会被使用）。

- Chris Dodd