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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html