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)

    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)

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.

To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to