[PATCH 1/3] Eliminate recursion in setting/clearing marks in commit list
- From
Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
- Date
- Dec 26, 2011, 12:04 UTC
- Message-ID
- <1324901080-23215-1-git-send-email-pclouds@gmail.com>
From: Nguyen Thai Ngoc Duy <pclouds@gmail.com>
Recursion in a DAG is generally a bad idea because it could be very deep. Be defensive and avoid recursion in mark_parents_uninteresting() and clear_commit_marks().
mark_parents_uninteresting() learns a trick from clear_commit_marks() to avoid malloc() in (dorminant) single-parent case.
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> --- commit.c | 13 +++++++++++-- revision.c | 45 +++++++++++++++++++++++++++++---------------- 2 files changed, 40 insertions(+), 18 deletions(-)
diff --git a/commit.c b/commit.c index 73b7e00..628066c 100644 --- a/commit.c +++ b/commit.c @@ -421,7 +421,8 @@ struct commit *pop_most_recent_commit(struct commit_list **list, return ret; } -void clear_commit_marks(struct commit *commit, unsigned int mark) +static void clear_commit_marks_1(struct commit_list **plist, + struct commit *commit, unsigned int mark) { while (commit) { struct commit_list *parents; @@ -436,12 +437,20 @@ void clear_commit_marks(struct commit *commit, unsigned int mark) return; while ((parents = parents->next)) - clear_commit_marks(parents->item, mark); + commit_list_insert(parents->item, plist); commit = commit->parents->item; } } +void clear_commit_marks(struct commit *commit, unsigned int mark) +{ + struct commit_list *list = NULL; + commit_list_insert(commit, &list); + while (list) + clear_commit_marks_1(&list, pop_commit(&list), mark); +} + void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark) { struct object *object; diff --git a/revision.c b/revision.c index 8764dde..7cc72fc 100644 --- a/revision.c +++ b/revision.c @@ -139,11 +139,32 @@ void mark_tree_uninteresting(struct tree *tree) void mark_parents_uninteresting(struct commit *commit) { - struct commit_list *parents = commit->parents; + struct commit_list *parents = NULL, *l; + + for (l = commit->parents; l; l = l->next) + commit_list_insert(l->item, &parents); while (parents) { struct commit *commit = parents->item; - if (!(commit->object.flags & UNINTERESTING)) { + l = parents; + parents = parents->next; + free(l); + + while (commit) { + /* + * A missing commit is ok iff its parent is marked + * uninteresting. + * + * We just mark such a thing parsed, so that when + * it is popped next time around, we won't be trying + * to parse it and get an error. + */ + if (!has_sha1_file(commit->object.sha1)) + commit->object.parsed = 1; + + if (commit->object.flags & UNINTERESTING) + break; + commit->object.flags |= UNINTERESTING; /* @@ -154,21 +175,13 @@ void mark_parents_uninteresting(struct commit *commit) * wasn't uninteresting), in which case we need * to mark its parents recursively too.. */ - if (commit->parents) - mark_parents_uninteresting(commit); - } + if (!commit->parents) + break; - /* - * A missing commit is ok iff its parent is marked - * uninteresting. - * - * We just mark such a thing parsed, so that when - * it is popped next time around, we won't be trying - * to parse it and get an error. - */ - if (!has_sha1_file(commit->object.sha1)) - commit->object.parsed = 1; - parents = parents->next; + for (l = commit->parents->next; l; l = l->next) + commit_list_insert(l->item, &parents); + commit = commit->parents->item; + } } }
-- 1.7.8.36.g69ee2