Code

gitk: New infrastructure for working out branches & previous/next tags
authorPaul Mackerras <paulus@samba.org>
Sat, 16 Jun 2007 10:29:25 +0000 (20:29 +1000)
committerPaul Mackerras <paulus@samba.org>
Sat, 23 Jun 2007 10:55:22 +0000 (20:55 +1000)
commite11f12331552427113bcfd3721008ffc7227aac0
treeaebc4cb978a0107627bebeda96ea760242c8c2f9
parent7e12f1a6291032a311ab592e42fd38f5ec358c0e
gitk: New infrastructure for working out branches & previous/next tags

Instead of working out descendent heads and descendent & ancestor
branches in a two-pass algorithm, this reads and stores a simplified
version of the graph topology, and works out descendent/ancestor
tags and descendent heads on demand (with a bit of caching).

The advantages of this are, first, that we now don't have to use
--topo-order on the git rev-list process.  Secondly, we don't have
to re-read the whole graph when tags or heads change or even when
the graph changes.  Since we can cope with parents coming before
children, we can update the graph by running a git rev-list with
arguments that just give us the new commits, and merge the new
commits into the simplified graph.

The graph is simplified in the sense that commits with exactly one
parent and one child (which is >90% of them in most cases) are grouped
together into arcs joining nodes or 'branch/merge points', which are
the commits that don't have exactly 1 parent and 1 child.  This reduces
the size of the graph substantially and decreases the time to traverse
it correspondingly.

Signed-off-by: Paul Mackerras <paulus@samba.org>
gitk