2007/6/19, ngaba@petra.hos.u-szeged.hu <ngaba@petra.hos.u-szeged.hu>:
To Nagy : I don't even understand why this assumption is needed : * assumptions: alpm_list_add adds new member to the end of the list, so we can reuse the list pointer
As far as I can tell, this isn't needed, so please explain more in detail :)
OK, you are right. To be perfect, this is not needed, but this cause a big performance boost: If this assumption is true, you can simply leave the "ready" variable and the "while(!ready)" stuff, because every dependencies will be found in the first loop (ready is just a safety variable now...). This wonderful fact proves the speed-up IMHO. However, if we want to keep the nice feature that this function keeps topo sort, this is needed. However, the algorithm (expected to) works fine when input list is not topo sorted (I put it in the comment just as a suggestion, because topo sort is slow, and small list's topo-sort is faster).
Ok that's why I thought, that assumption would be needed only if the while (!ready) wasn't there. That wasn't clear at all when reading your comments in the patch :) Anyway, it took me a while to figure out how it could still be correct when removing this while loop, but as you said, this would rely on the list being topo sorted. I believe that if the list was sorted, it would be correct indeed.
Anyway, this assumption is _used_ in alpm_resolvedeps, so I put that comment to the patch as a reminder.
As I already said, I didn't understand this part yet, but just because it's done here doesn't mean it's good. (and Dan said it was wrong) I thought you already knew that all pacman code wasn't 100% perfect, otherwise, you wouldn't want to change it, would you? ;)