author | Paul Mackerras <paulus@samba.org> | |
Wed, 19 Dec 2007 23:03:35 +0000 (10:03 +1100) | ||
committer | Paul Mackerras <paulus@samba.org> | |
Wed, 19 Dec 2007 23:03:35 +0000 (10:03 +1100) | ||
commit | f3ea5ede23a2f8a7514583d2665e7a72aad7c9b8 | |
tree | b09f0ff33bfddfd27532951b9ed289c156323fb8 | tree | snapshot |
parent | 24f7a667e69262525beba726dded2fb221d9be27 | commit | diff |
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>
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 | diff | blob | history |