[PATCH] Add a topological sort procedure to commit.c
authorJon Seymour <jon.seymour@gmail.com>
Wed, 6 Jul 2005 16:39:34 +0000 (02:39 +1000)
committerLinus Torvalds <torvalds@g5.osdl.org>
Wed, 6 Jul 2005 17:19:04 +0000 (10:19 -0700)
commitab580acea4b1b79daaca0c8727b810073a610e2a
tree51ac13f6cc73bfdadf8ca08a93db46e9f6a5ee50
parent9e9824ba0e641095f1cbc01c724d8e0a382c0580
[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>
commit.c
commit.h