[pacman-dev] [patch] alpm_removedeps bug+fix && alpm_depcmp-discussion

[Xavier]

2007/6/19, ngaba at petra.hos.u-szeged.hu <ngaba at 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? ;)