Re: [PATCH] describe: rewrite name_rev() iteratively

[Jeff King <peff@peff.net>]

On Mon, Apr 07, 2014 at 01:47:14AM +0300, Dragos Foianu wrote:

> The "git describe --contains" command uses the name_rev() function which
> is currently a recursive function. This causes a Stack Overflow when the
> history is large enough.
> 
> Rewrite name_rev iteratively using a stack on the heap. This slightly
> reduces performance due to the extra operations on the heap, but the
> function no longer overflows the stack.

You can avoid the heap overhead by using an array for your stack, and
only resizing it when necessary. Like this:

    struct rev_stack {
            int nr, alloc;
            struct rev_data *data;
    };

    static struct rev_data *rev_stack_push(struct rev_stack *stack)
    {
            ALLOC_GROW(stack->data, stack->nr + 1, stack->alloc);
            return &stack->data[stack->nr++];
    }

    static void rev_stack_pop(struct rev_stack *stack)
    {
            stack->nr--;
    }

    static void rev_stack_init(struct rev_stack *stack)
    {
            stack->nr = stack->alloc = 0;
            stack->data = NULL;
    }

    static void rev_stack_release(struct rev_stack *stack)
    {
            free(stack->data);
            rev_stack_init(stack);
    }

Usage would be something like:

    struct rev_data *data = rev_stack_push(&stack);
    data->commit = commit;
    data->tip_name = tip_name;
    ...

IOW, you push first to allocate the space, and then do your
make_rev_data, rather than the other way around.

The downside is that your allocation is always as big as the deepest
recursion so far, so you hold on to the memory a little longer than
necessary. I think that's a good tradeoff versus an extra malloc() for
every commit.

-Peff