02 June, 2011

Mutual recursion without nested function calls in C

My friend Ryukzak has implemented mutual recursion library to use it without nested calls and thus memory overhead (stack). I decided I can do the same using ucontext. Here is a prototype (not generic) to calculate factorial:

struct Fac_state {
    int n;
    int acc;
};

void fac_times2(ucontext_t *other_context, ucontext_t *this_context,
               struct Fac_state *fstate)
{
    while (1) {
        fstate->acc *= fstate->n;
        fstate->n--;
        swapcontext(this_context, other_context);
    }
}


int factorial(int n)
{
    char iterator_stack[SIGSTKSZ];
    struct Fac_state fstate = {n, 1};

    ucontext_t this_context, other_context;

    other_context.uc_stack.ss_sp   = iterator_stack;
    other_context.uc_stack.ss_size = sizeof(iterator_stack);
    getcontext(&other_context);

    makecontext(&other_context, (void (*)(void)) fac_times2,
                3, &this_context, &other_context, &fstate);

    while (1) {
        if (fstate.n == 0)
            break;
        swapcontext(&this_context, &other_context);
    }
    return fstate.acc;
}

One more example in my next post.

No comments: