Thomas Rast <tr...@inf.ethz.ch> writes:
> Junio C Hamano <gits...@pobox.com> writes:
>
> The topo order algorithm can be modified to take advantage of
> [generation numbers], in order to provide incremental processing:
>
> Let S be the set of tentative sources
>
> Let U be the set of vertices whose out-edges are no known yet
> (i.e., the set of commits which haven't been loaded yet)
[...]
> while there are any vertices left:
>
> pick any tentative source C from S that we "want to emit"
>
> # Ascertain that no unknown commit (from U or further beyond) can be
> # a descendant of C
> while there is a D in U such that g(D) > g(C):
> load D
> remove D from U
> add the parents of D to U if they were not already loaded
> possibly remove some elements of S if their indegree became nonzero
>
> if C was removed from S:
> continue
>
> remove C from the graph and emit it
By the way, this does bump the runtime of the algorithm a bit, depending
on the data structure used for U. Recall that ordinary topo-sort with a
stack for S (i.e., --topo-order) runs linearly with the number of
vertices.
If we use a priority queue for U, which lets us get at the
highest-generation unknown commits easily, it potentially goes to n log n
if U reaches linear size at some point.
That shouldn't hurt too much of course, since on the one hand it should
rarely actually get that big, and OTOH --date-order has n log n runtime
anyway (using a priority queue for S).
Thanks for challenging me on my "it should work" feeling. It was quite
interesting to actually think it through and write down a workable
algorithm.
--
Thomas Rast
trast@{inf,student}.ethz.ch
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
