gitk: Implement date mode in the new framework
authorPaul Mackerras <paulus@samba.org>
Wed, 19 Dec 2007 23:03:35 +0000 (10:03 +1100)
committerPaul Mackerras <paulus@samba.org>
Wed, 19 Dec 2007 23:03:35 +0000 (10:03 +1100)
commitf3ea5ede23a2f8a7514583d2665e7a72aad7c9b8
treeb09f0ff33bfddfd27532951b9ed289c156323fb8
parent24f7a667e69262525beba726dded2fb221d9be27
gitk: Implement date mode in the new framework

This restores date mode, which lists commits by date, as far as possible
given the constraint that parents come after all their children.  To
implement this in the new framework, we (1) only join a new commit onto
an existing arc if the arc is the last arc created, (2) treat arcs as
seeds unless they have a child arc that comes later, and (3) never
decrease the token value for an arc.

This means we get lots of "seeds", which exposed some quadratic behaviour
in adding and removing seeds.  To fix this, we add a vbackptr array, which
points to the arc whose vleftptr entry points to us, and a vlastins array,
which shows where in an arc's vdownptr/vleftptr list we last inserted a
parent, which acts as a hint of a good place to start looking for where to
insert a new child.

This also ensures the children array elements stay in sorted order at all
times.  We weren't resorting the children lists when reassigning tokens
in renumbervarc.  Since the children lists are now always sorted, we don't
have to search through all elements to find the one with the highest token;
we can just use the last element.

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