From ab580acea4b1b79daaca0c8727b810073a610e2a Mon Sep 17 00:00:00 2001 From: Jon Seymour Date: Thu, 7 Jul 2005 02:39:34 +1000 Subject: [PATCH] Add a topological sort procedure to commit.c This introduces an in-place topological sort procedure to commit.c. Given a list of commits, sort_in_topological_order() will perform an in-place topological sort of that list. The invariant that applies to the resulting list is: a reachable from b => ord(b) < ord(a) This invariant is weaker than the --merge-order invariant, but is cheaper to calculate (assuming the list has been identified) and will serve any purpose where only a minimal topological order guarantee is required. Signed-off-by: Jon Seymour Signed-off-by: Linus Torvalds --- commit.h | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'commit.h') diff --git a/commit.h b/commit.h index 491b2c148f..c24ab21061 100644 --- a/commit.h +++ b/commit.h @@ -54,4 +54,17 @@ struct commit *pop_most_recent_commit(struct commit_list **list, struct commit *pop_commit(struct commit_list **stack); int count_parents(struct commit * commit); + +/* + * Performs an in-place topological sort of list supplied. + * + * Pre-conditions: + * all commits in input list and all parents of those + * commits must have object.util == NULL + * + * Post-conditions: + * invariant of resulting list is: + * a reachable from b => ord(b) < ord(a) + */ +void sort_in_topological_order(struct commit_list ** list); #endif /* COMMIT_H */ -- cgit v1.2.3