summaryrefslogtreecommitdiff
path: root/commit.h
diff options
context:
space:
mode:
authorJon Seymour <jon.seymour@gmail.com>2005-07-07 02:39:34 +1000
committerLinus Torvalds <torvalds@g5.osdl.org>2005-07-06 10:19:04 -0700
commitab580acea4b1b79daaca0c8727b810073a610e2a (patch)
tree51ac13f6cc73bfdadf8ca08a93db46e9f6a5ee50 /commit.h
parent9e9824ba0e641095f1cbc01c724d8e0a382c0580 (diff)
downloadgit-ab580acea4b1b79daaca0c8727b810073a610e2a.tar.gz
[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 <jon.seymour@gmail.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'commit.h')
-rw-r--r--commit.h13
1 files changed, 13 insertions, 0 deletions
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 */