[pacman-dev] [PATCH] alpm_checkdeps clean-up <- some notes

Xavier shiningxc at gmail.com
Sat Dec 1 16:04:56 EST 2007

On Sat, Dec 01, 2007 at 12:43:21AM +0100, Nagy Gabor wrote:
> Some notes:
> 1.
> +	joined = alpm_list_join(alpm_list_copy(remove), alpm_list_copy(upgrade));
> +	dblist = alpm_list_diff(_alpm_db_get_pkgcache(db), joined, _alpm_pkg_cmp);
> +	alpm_list_free(joined);
> Well, this is done immediately after checkdeps call, which may be
> unneeded (remove == NULL or upgrade == NULL, this is a usual case), and
> dblist shouldn't be calculated if reverse==0 and we don't need it
> (packages have no dependencies or satisfied by upgrade list).

Right, feel free to do these little optimizations :)

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

Maybe that would also make that part clearer, especially if you rename joined
to targets or something :)
That would also add yet another list function, and I'm not sure there will be
many use cases for it, but it's general enough, so it's acceptable imo.

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

This would depend on the order in which readdir reads the file on the
filesystem, right? So on the order on the filesystem?
I am not sure if there is any garanty it will always be in the order we want
(on any filesystem, any os), but I may be totally off, so hopefully someone
else knows better :)

Hmm, how am I supposed to rebase your unneeded patch now? :)
Seems like the "causingpkg" is now hidden behind the alpm_list_find +
satisfycmp function.

> Summary:
> Overall the new version is much more powerful (imho) if it must check
> many targets, but point 1. shows that the current resolvedeps may
> becomes slower after this patch, because checkdeps is called on all
> packages (but see also my resolvedeps patch, which reduces checkdeps
> calls in "usual" cases -- not smoke001.py-like)

Hm ok. let's discuss that in that other thread.

More information about the pacman-dev mailing list