Kontynuacje/Coroutines/Generatory w C++/gcc/linux

Question

Tło: Próbuję dowiedzieć się, jak zaimplementować kontynuacje/coroutines/generators (niezależnie od tego, jak się nazywa), stawiając ten problem z zabawkami. Środowisko to C++ 11 na gcc 4.6 i linux 3.0 x86_64. Nie przenośne jest w porządku, ale używanie zewnętrznej biblioteki (boost.coroutine, COROUTINE itp.) Jest niedozwolone. Myślę, że longjmp(3) i/lub makecontext(2) i przyjaciele mogą pomóc, ale nie jestem pewien.

Opis

Poniżej Parser zabawka ma analizowania sekwencji as i bs o równej długości. tj.

((a+)(b+))+ 

w taki sposób, że długość drugiej produkcji w nawiasach jest równa trzeciej.

Po znalezieniu produkcji (np. Aaabbb) wyprowadza liczbę znalezionych a (np. 3).

Kod:

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

Problem:

Jak widać stan stosu consume połączenia muszą być zapisane po yield nazywa a następnie produce zyski. Po ponownym wywołaniu produce, consume musi zostać ponownie uruchomiony przez powrót z yield. Wyzwanie polegałoby na zmodyfikowaniu sposobu działania i implementacji , aby działały zgodnie z przeznaczeniem.

(. Oczywiście reimplementing zużywają tak, że zapisuje i odbudowuje jej stan celowość ćwiczenia)

myślę, co należy zrobić, jest coś takiego jak w przykładzie na dole strony makecontext człowieka: http://www.kernel.org/doc/man-pages/online/pages/man3/makecontext.3.html , ale nie jest jasne, jak przetłumaczyć to na ten problem. (I muszę spać)

Rozwiązanie:

(Dzięki Chris Dodd projektu)

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

Answer 1

Jego dość prosta w użyciu makecontext/swapcontext za to - użyć makecontext aby stworzyć nowy kontekst kontekstowy i zamianę kontekstu, aby zamienić między nimi. W twoim przypadku potrzebujesz jednego dodatkowego programu do obsługi nieskończonej pętli consume, a ty uruchamiasz i produkujesz w głównym kontekście.

Więc main powinien zadzwonić getContext + makecontext aby utworzyć nowy kontekst, który uruchomi zużywają pętla:

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

a następnie produce przełączy się na niej zamiast dzwonić consume bezpośrednio:

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

i wreszcie yield po prostu dzwoni swapcontext(&consume_ctxt, &main_ctxt);, aby wrócić do głównego kontekstu (który będzie kontynuowany w produce i natychmiast powróci).

Należy pamiętać, że od consume jest nieskończona pętla, nie trzeba martwić się zbytnio o to, co dzieje się, gdy powraca (tak link nigdy nie będzie używany)