Продолжения / Сопрограммы / Генераторы в C ++ / gcc / linux - PullRequest
Новая
       13

Продолжения / Сопрограммы / Генераторы в C ++ / gcc / linux

5 голосов
/ 26 января 2012

Справочная информация: Я пытаюсь выяснить, как реализовать продолжения / сопрограммы / генераторы (как бы ни называлось следующее), поставив эту игрушечную проблему. Средой является C ++ 11 на gcc 4.6 и linux 3.0 x86_64. Непереносимо, но использование внешней библиотеки (boost.coroutine, COROUTINE и т. Д.) Не допускается. Я думаю longjmp(3) и / или makecontext(2) и друзья могут помочь, но не уверены.

Описание:

Следующий игрушечный синтаксический анализатор должен анализировать последовательности as и bs одинаковой длины. т.е. 

((a+)(b+))+

такой, что длина второго скобочного производства равна третьему.

Когда он находит производство (например, aaabbb), он выводит число a s, которое он находит (например, 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;
}

Проблема:

Как видите, состояние consume стека вызовов должно быть сохранено, когда вызывается yield, а затем возвращается produce. Когда produce вызывается снова, consume необходимо перезапустить, вернувшись с yield. Задача состоит в том, чтобы изменить способ produce вызовов consume и внедрить yield, чтобы они функционировали должным образом.

(Очевидно, переопределение потребления так, чтобы оно сохраняло и восстанавливало свое состояние, нарушало цель упражнения.)

Я думаю, что нужно сделать, это что-то вроде примера внизу справочной страницы makecontext: http://www.kernel.org/doc/man-pages/online/pages/man3/makecontext.3.html,, но не совсем понятно, как перевести это на эту проблему. (и мне нужно спать)

Решение:

(Спасибо Крису Додду за дизайн) 

#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;
}

1 Ответ

3 голосов
/ 26 января 2012

Для этого довольно просто использовать makecontext / swapcontext - вы используете makecontext для создания нового контекста сопрограммы и swapcontext для переключения между ними. В вашем случае вам нужна одна дополнительная сопрограмма для запуска бесконечного цикла consume, и вы запускаете main и производите в главном контексте.

Так что 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 - это бесконечный цикл, вам не нужно слишком беспокоиться о том, что произойдет, когда он вернется (поэтому ссылка никогда не будет использоваться)

...