From 2baad220138b10582c55ef942466f2b8df18944f Mon Sep 17 00:00:00 2001 From: =?utf8?q?Nguy=E1=BB=85n=20Th=C3=A1i=20Ng=E1=BB=8Dc=20Duy?= Date: Sat, 14 Jan 2012 19:19:54 +0700 Subject: [PATCH] index-pack: eliminate recursion in find_unresolved_deltas MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Current find_unresolved_deltas() links all bases together in a form of tree, using struct base_data, with prev_base pointer to point to parent node. Then it traverses down from parent to children in recursive manner with all base_data allocated on stack. To eliminate recursion, we simply need to put all on heap (parse_pack_objects and fix_unresolved_deltas). After that, it's simple non-recursive depth-first traversal loop. Each node also maintains its own state (ofs and ref indices) to iterate over all children nodes. So we process one node: - if it returns a new (child) node (a parent base), we link it to our tree, then process the new node. - if it returns nothing, the node is done, free it. We go back to parent node and resume whatever it's doing. and do it until we have no nodes to process. Signed-off-by: Nguyễn Thái Ngọc Duy Signed-off-by: Junio C Hamano --- builtin/index-pack.c | 111 +++++++++++++++++++++++++++---------------- 1 file changed, 70 insertions(+), 41 deletions(-) diff --git a/builtin/index-pack.c b/builtin/index-pack.c index af7dc37a4..38ff03a5c 100644 --- a/builtin/index-pack.c +++ b/builtin/index-pack.c @@ -34,6 +34,8 @@ struct base_data { struct object_entry *obj; void *data; unsigned long size; + int ref_first, ref_last; + int ofs_first, ofs_last; }; /* @@ -221,6 +223,15 @@ static NORETURN void bad_object(unsigned long offset, const char *format, ...) die("pack has bad object at offset %lu: %s", offset, buf); } +static struct base_data *alloc_base_data(void) +{ + struct base_data *base = xmalloc(sizeof(struct base_data)); + memset(base, 0, sizeof(*base)); + base->ref_last = -1; + base->ofs_last = -1; + return base; +} + static void free_base_data(struct base_data *c) { if (c->data) { @@ -553,58 +564,76 @@ static void resolve_delta(struct object_entry *delta_obj, nr_resolved_deltas++; } -static void find_unresolved_deltas(struct base_data *base, - struct base_data *prev_base) +static struct base_data *find_unresolved_deltas_1(struct base_data *base, + struct base_data *prev_base) { - 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. - */ - { + if (base->ref_last == -1 && base->ofs_last == -1) { union delta_base base_spec; hashcpy(base_spec.sha1, base->obj->idx.sha1); find_delta_children(&base_spec, - &ref_first, &ref_last, OBJ_REF_DELTA); + &base->ref_first, &base->ref_last, OBJ_REF_DELTA); memset(&base_spec, 0, sizeof(base_spec)); base_spec.offset = base->obj->idx.offset; find_delta_children(&base_spec, - &ofs_first, &ofs_last, OBJ_OFS_DELTA); - } + &base->ofs_first, &base->ofs_last, OBJ_OFS_DELTA); - if (ref_last == -1 && ofs_last == -1) { - free(base->data); - return; - } + if (base->ref_last == -1 && base->ofs_last == -1) { + free(base->data); + return NULL; + } - link_base_data(prev_base, base); + link_base_data(prev_base, base); + } - for (i = ref_first; i <= ref_last; i++) { - struct object_entry *child = objects + deltas[i].obj_no; - struct base_data result; + if (base->ref_first <= base->ref_last) { + struct object_entry *child = objects + deltas[base->ref_first].obj_no; + struct base_data *result = alloc_base_data(); assert(child->real_type == OBJ_REF_DELTA); - resolve_delta(child, base, &result); - if (i == ref_last && ofs_last == -1) + resolve_delta(child, base, result); + if (base->ref_first == base->ref_last && base->ofs_last == -1) free_base_data(base); - find_unresolved_deltas(&result, base); + + base->ref_first++; + return result; } - for (i = ofs_first; i <= ofs_last; i++) { - struct object_entry *child = objects + deltas[i].obj_no; - struct base_data result; + if (base->ofs_first <= base->ofs_last) { + struct object_entry *child = objects + deltas[base->ofs_first].obj_no; + struct base_data *result = alloc_base_data(); assert(child->real_type == OBJ_OFS_DELTA); - resolve_delta(child, base, &result); - if (i == ofs_last) + resolve_delta(child, base, result); + if (base->ofs_first == base->ofs_last) free_base_data(base); - find_unresolved_deltas(&result, base); + + base->ofs_first++; + return result; } unlink_base_data(base); + return NULL; +} + +static void find_unresolved_deltas(struct base_data *base) +{ + struct base_data *new_base, *prev_base = NULL; + for (;;) { + new_base = find_unresolved_deltas_1(base, prev_base); + + if (new_base) { + prev_base = base; + base = new_base; + } else { + free(base); + base = prev_base; + if (!base) + return; + prev_base = base->base; + } + } } static int compare_delta_entry(const void *a, const void *b) @@ -684,13 +713,13 @@ static void parse_pack_objects(unsigned char *sha1) progress = start_progress("Resolving deltas", nr_deltas); for (i = 0; i < nr_objects; i++) { struct object_entry *obj = &objects[i]; - struct base_data base_obj; + struct base_data *base_obj = alloc_base_data(); if (is_delta_type(obj->type)) continue; - base_obj.obj = obj; - base_obj.data = NULL; - find_unresolved_deltas(&base_obj, NULL); + base_obj->obj = obj; + base_obj->data = NULL; + find_unresolved_deltas(base_obj); display_progress(progress, nr_resolved_deltas); } } @@ -783,20 +812,20 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved) for (i = 0; i < n; i++) { struct delta_entry *d = sorted_by_pos[i]; enum object_type type; - struct base_data base_obj; + struct base_data *base_obj = alloc_base_data(); if (objects[d->obj_no].real_type != OBJ_REF_DELTA) continue; - base_obj.data = read_sha1_file(d->base.sha1, &type, &base_obj.size); - if (!base_obj.data) + base_obj->data = read_sha1_file(d->base.sha1, &type, &base_obj->size); + if (!base_obj->data) continue; - if (check_sha1_signature(d->base.sha1, base_obj.data, - base_obj.size, typename(type))) + if (check_sha1_signature(d->base.sha1, base_obj->data, + base_obj->size, typename(type))) die("local object %s is corrupt", sha1_to_hex(d->base.sha1)); - base_obj.obj = append_obj_to_pack(f, d->base.sha1, - base_obj.data, base_obj.size, type); - find_unresolved_deltas(&base_obj, NULL); + base_obj->obj = append_obj_to_pack(f, d->base.sha1, + base_obj->data, base_obj->size, type); + find_unresolved_deltas(base_obj); display_progress(progress, nr_resolved_deltas); } free(sorted_by_pos); -- 2.30.2