From 941ba8db57f2d075aee48b002ee30686288cb502 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Nguy=E1=BB=85n=20Th=C3=A1i=20Ng=E1=BB=8Dc=20Duy?= Date: Sat, 14 Jan 2012 19:19:53 +0700 Subject: Eliminate recursion in setting/clearing marks in commit list MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 (dominant) single-parent case. Signed-off-by: Nguyễn Thái Ngọc Duy Signed-off-by: Junio C Hamano --- commit.c | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-) (limited to 'commit.c') diff --git a/commit.c b/commit.c index 44bc96d44d..c7aefbfd28 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; -- cgit v1.2.1