[pacman-dev] alpm_list functions

[Nagy Gabor]

Sun, 2 Dec 2007 00:02:20 +0100 -n
Xavier <shiningxc at gmail.com> írta:

> On Sat, Dec 01, 2007 at 11:43:19PM +0100, Nagy Gabor wrote:
> > 
> > +1
> > And I was totally wrong, alpm_list_diff is SLOW, I thought that it
> > uses a more clever algorithm <- so it doesn't sort anything [*], and
> > alpm_list_diff(_alpm_db_get_pkgcache(db), dblist, _alpm_pkg_cmp) is
> > also much slower than I expected.
> > 
> 
> Ok, I found your previous mail a bit strange, I understand now.
> 
> > Some other notes:
> > 1. Why pkgcache is sorted? Do we use this somewhere? Yes, sorted
> > lists are more efficient, we can find or remove elements faster,
> > but as I see, we don't assume anywhere that this is a sorted list
> > [well, we call list_add_sorted in add_pkgincache, but this is
> > slower then pkg_add_last ;-]. Probably no, and that's why you
> > didn't know about this.
> > 
> 
> Well, I'm confused. First you seemed to think it was a good idea to
> sort the list at the base, and then use this for having more
> efficient functions. And now, it seems like you are saying it's a bad
> idea...
To be clear: _Currently_ we don't benefit (in speed) from our sorted
pkgcaches -- but they are sorted now <- this is bad. Hmm... maybe sorted
pkgcache is good for 'pacman -Qi', and well, this makes our
search-for-provider method deterministic. So now I could answer my 'Why
pkgcache is sorted?' question. Usually I don't have clear opinion about
complex things first, I just try to find pros and contras (and
listen yours) and _then_ make decision.

> 
> > 2. I warn you, that alpm_list_intersect would be a funny function:
> > that would be _asymmetric_, because we use a compare function for
> > compare: In the example above:
> > intersect(dbcache, joined) finds the to-be-modified local packages,
> > but intersect(joined, dbcache) finds packages in the target which
> > has old version installed, these are not the same!
> > 
> 
> I don't understand this at all.
alpm_pkg_cmp(package1, package2) == 0 doesn't mean that 'package1 ==
package2', this just implies that they have the same pkgname. So how do
you define intersection? Which package (package1 or package2) do you
want to select to intersect of A and B?

> > 3. pointercmp and satisfycmp warning. These are NOT real compare
> > functions, so you should NEVER use ptrcmp in a clever (like in
> > check_fileconflicts) alpm_list_diff. Probably this is the main
> > reason for [*]
> > 
> 
> I don't understand this either. check_fileconflicts uses strcmp,
> what's the problem with this?
This was just a warning, that they are not real compare-functions
(trichotomy doesn't hold) and you should keep this in mind, when you
want to use clever chk_filedifference-like fast alpm_list_diff algorithm
(you can easily say first that the current ptrcmp would be enough for a
simple 'A - B' set operation, because an 'a equals b' function is
enough for doing this, but it isn't.)

Bye