author | Paul Mackerras <paulus@samba.org> | |
Sat, 16 Jun 2007 10:29:25 +0000 (20:29 +1000) | ||
committer | Paul Mackerras <paulus@samba.org> | |
Sat, 23 Jun 2007 10:55:22 +0000 (20:55 +1000) | ||
commit | e11f12331552427113bcfd3721008ffc7227aac0 | |
tree | aebc4cb978a0107627bebeda96ea760242c8c2f9 | tree | snapshot |
parent | 7e12f1a6291032a311ab592e42fd38f5ec358c0e | commit | diff |
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>
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 | diff | blob | history |