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