author | Jon Seymour <jon.seymour@gmail.com> | |
Wed, 6 Jul 2005 16:39:34 +0000 (02:39 +1000) | ||
committer | Linus Torvalds <torvalds@g5.osdl.org> | |
Wed, 6 Jul 2005 17:19:04 +0000 (10:19 -0700) | ||
commit | ab580acea4b1b79daaca0c8727b810073a610e2a | |
tree | 51ac13f6cc73bfdadf8ca08a93db46e9f6a5ee50 | tree | snapshot |
parent | 9e9824ba0e641095f1cbc01c724d8e0a382c0580 | commit | diff |
[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>
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>
commit.c | diff | blob | history | |
commit.h | diff | blob | history |