Предыстория: Я пытаюсь понять, как реализовать продолжения/корутины/генераторы (как бы это ни называлось), поставив эту игрушечную задачу. Окружение - 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
#include
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
так, чтобы они функционировали как положено.
(Очевидно, что переделка consume так, чтобы он сохранял и восстанавливал свое состояние, противоречит цели упражнения.)
Я думаю, что нужно сделать что-то вроде примера внизу страницы руководства makecontext: http://www.kernel.org/doc/man-pages/online/pages/man3/makecontext.3.html, но не ясно, как перевести его на эту проблему. (и мне нужно спать)
Решение:
(Спасибо Крису Додду за дизайн)
#include
#include
#include
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;
}