[PATCH 2/2] index-pack: a naive attempt to flatten find_unresolved_deltas

[pclouds@gmail.com]

From: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>

This seems to work for me. But I think this approach uses (much?) more
memory because it turns a tree of calls into a flat list of calls and
keep the list until the end, while the recursive version only has to
keep one call chain at a time.

Any ideas how to improve it?

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/index-pack.c |   57 +++++++++++++++++++++++++++++++++++++------------
 1 files changed, 43 insertions(+), 14 deletions(-)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 9855ada..d4c182f 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -565,18 +565,31 @@ static void resolve_delta(struct object_entry *delta_obj,
 	nr_resolved_deltas++;
 }
 
+struct fud_stack {
+	struct base_data base_;
+	struct base_data *base;
+	struct base_data *prev_base;
+};
+
 static void find_unresolved_deltas(struct base_data *base,
 				   struct base_data *prev_base)
 {
+	struct fud_stack **stack = NULL;
+	int stk, stack_nr = 0, stack_alloc = 0;
 	int i, ref_first, ref_last, ofs_first, ofs_last;
 
-	/*
-	 * This is a recursive function. Those brackets should help reducing
-	 * stack usage by limiting the scope of the delta_base union.
-	 */
-	{
+	ALLOC_GROW(stack, stack_nr + 1, stack_alloc);
+	stack[stack_nr] = xmalloc(sizeof(struct fud_stack));
+	stack[stack_nr]->base = base;
+	stack[stack_nr]->prev_base = prev_base;
+	stack_nr++;
+
+	for (stk = 0; stk < stack_nr; stk++) {
 		union delta_base base_spec;
 
+		base = stack[stk]->base;
+		prev_base = stack[stk]->prev_base;
+
 		hashcpy(base_spec.sha1, base->obj->idx.sha1);
 		find_delta_children(&base_spec,
 				    &ref_first, &ref_last, OBJ_REF_DELTA);
@@ -588,34 +601,50 @@ static void find_unresolved_deltas(struct base_data *base,
 
 		if (ref_last == -1 && ofs_last == -1) {
 			free(base->data);
-			return;
+			free(stack[stk]);
+			stack[stk] = NULL;
+			continue;
 		}
 
 		link_base_data(prev_base, base);
 
+		ALLOC_GROW(stack, stack_nr +
+			   (ref_last - ref_first + 1) +
+			   (ofs_last - ofs_first + 1),
+			   stack_alloc);
+
 		for (i = ref_first; i <= ref_last; i++) {
 			struct object_entry *child = objects + deltas[i].obj_no;
-			struct base_data result;
 
 			assert(child->real_type == OBJ_REF_DELTA);
-			resolve_delta(child, base, &result);
+			stack[stack_nr] = xmalloc(sizeof(struct fud_stack));
+			stack[stack_nr]->base = &stack[stack_nr]->base_;
+			resolve_delta(child, base, stack[stack_nr]->base);
 			if (i == ref_last && ofs_last == -1)
 				free_base_data(base);
-			find_unresolved_deltas(&result, base);
+			stack[stack_nr]->prev_base = base;
+			stack_nr++;
 		}
 
 		for (i = ofs_first; i <= ofs_last; i++) {
 			struct object_entry *child = objects + deltas[i].obj_no;
-			struct base_data result;
-
 			assert(child->real_type == OBJ_OFS_DELTA);
-			resolve_delta(child, base, &result);
+			stack[stack_nr] = xmalloc(sizeof(struct fud_stack));
+			stack[stack_nr]->base = &stack[stack_nr]->base_;
+			resolve_delta(child, base, stack[stack_nr]->base);
 			if (i == ofs_last)
 				free_base_data(base);
-			find_unresolved_deltas(&result, base);
+			stack[stack_nr]->prev_base = base;
+			stack_nr++;
 		}
 	}
-	unlink_base_data(base);
+
+	for (stk = stack_nr - 1; stk >= 0; stk--)
+		if (stack[stk]) {
+			unlink_base_data(stack[stk]->base);
+			free(stack[stk]);
+		}
+	free(stack);
 }
 
 static int compare_delta_entry(const void *a, const void *b)
-- 
1.7.8.36.g69ee2