[pacman-dev] _alpm_sortbydeps is slow and buggy

[Nagy Gabor]

Hi!

I don't really understand how this function does 'topological sorting',
but it is buggy. If n is the number of targets, maxscans=sqrt(n) is not
enough: See the following example:
Let the targets foo[1], ... foo[n]; where foo[i] depends on foo[j] iff
i<j. It's easy to see that the function would sort correctly these
target in 'n-1' steps; but it is stopped after sqrt(n) steps.
(libm seems to be needed for libalpm because of these _one_ sqrt()
only, so libm "depend" should be removed too).
In the example above O(n^3) operations needed (+ I think first compute
the dependency graph would much more effective; because for example we
compute (n-1) times that foo[n-1] depends on foo[n], which is
needless.). Well known O(n+e)~O(n^2) algorithms exists for topological
sorting (see google).
And I'm not sure that even maxscans=n enough (I cannot prove that
this algorithm is correct yet, this is probably my fault;), and I cannot
find an extreme example where this algorithm sucks.

Bye, Nagy Gabor