[pacman-dev] alpm_list functions

[Nagy Gabor]

> On Sat, Dec 01, 2007 at 12:43:21AM +0100, Nagy Gabor wrote:
> > Some notes:
> > 2.
> > +		alpm_list_t *modified =
> > alpm_list_diff(_alpm_db_get_pkgcache(db), dblist, _alpm_pkg_cmp); I
> > would prefer "intersect(dbcache, joined)", because usually joined
> > is a smaller list than dblist, but we have no such function. 3.
> > alpm_list_diff is quite fast (n+m), but it needs to order lists
> > first O(nlogn)+O(mlogm); however dbcache is initially(?) ordered.
> > Note: We had some alpm_list problems nowadays, after this patch
> > alpm_list_diff function becomes crucial...
> > 
> 
> Slightly off-topic, but a note related to list_diff and list_intersect
> function : fileconflicts have apparently its own functions
> (check_filedifference and check_fileconflicts).
> I wonder if these could be replaced to use generic list functions
> instead.

+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.

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.

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!

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 [*]

Bye