Continuaciones/Corutinas/Generadores en C++/gcc/linux

Question

Antecedentes: Estoy tratando de encontrar la forma de implementar continuaciones/coroutines/generators (cualquiera que sea el siguiente) al plantear este problema de juguete. El entorno es C++ 11 en gcc 4.6 y linux 3.0 x86_64. No portátil está bien, pero no se permite el uso de una biblioteca externa (boost.coroutine, COROUTINE, etc.). Creo que longjmp(3) y/o makecontext(2) y amigos pueden ayudar, pero no estoy seguro.

Descripción:

La siguiente analizador juguete se supone para analizar secuencias de As y Bs de igual longitud. es decir

((a+)(b+))+ 

tal que la duración de la segunda producción entre corchetes es igual a la tercera.

Cuando encuentra una producción (por ejemplo, aaabbb), emite el número de a que encuentra (por ejemplo, 3).

Código:

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

Problema:

Como se puede ver el estado de la pila consume llamada debe ser salvado cuando yield se llama y luego vuelve produce. Cuando se llama de nuevo produce, debe reiniciarse consume volviendo desde yield. El desafío sería modificar la forma en que produce llama al consume, e implementar yield para que funcionen como se esperaba.

(. Obviamente reimplementar consumen por lo que se ahorra y reconstruye su estado en contra del propósito del ejercicio)

Creo que lo que hay que hacer es algo así como el ejemplo en la parte inferior de la página del manual makecontext: http://www.kernel.org/doc/man-pages/online/pages/man3/makecontext.3.html , pero no está claro cómo traducirlo a este problema. (Y necesito sueño)

Solución:

(Gracias a Chris Dodd para el diseño)

#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

Su bastante sencillo de usar makecontext/swapcontext para este - que utiliza makecontext para crear un nuevo contexto de coroutine y swapcontext para intercambiarlos. En su caso, necesita una coroutine adicional para ejecutar el bucle infinito consume, y ejecuta main y produce en el contexto principal.

Así main deben llamar getcontext + makecontext para crear un nuevo contexto en el que se ejecutará el bucle consumen:

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

y luego produce migrará hacia ella en lugar de llamar consume directamente:

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

y finalmente yield simplemente llama a swapcontext(&consume_ctxt, &main_ctxt); para volver al contexto principal (que continuará en produce y regresa inmediatamente).

Nota que desde consume es un bucle infinito, no tiene que preocuparse demasiado acerca de lo que sucede cuando vuelve (por lo que nunca será utilizado el enlace)