[pacman-dev] [patch] IV. deps.c/sortbydeps rewritten
Nagy Gabor
ngaba at petra.hos.u-szeged.hu
Sun Apr 22 13:00:29 EDT 2007
Hi!
I implemented a standard topological sort algorithm. I'm not satisfied
yet, because I must compute the edges in O(n^2) time
(checkdeps also does this (and more), so its result should be used
somehow). If my algorithm is OK, then extra contains a dep circle ;-)
This is not radically faster anyway, but at least (hopefully) produces
good result.
Here is the patch:
-------------------
diff -Naur pacman-lib/lib/libalpm/deps.c pacman-lib.new/lib/libalpm/deps.c
--- pacman-lib/lib/libalpm/deps.c 2007-04-22 14:54:33.000000000 +0200
+++ pacman-lib.new/lib/libalpm/deps.c 2007-04-22 18:34:36.000000000 +0200
@@ -30,7 +30,6 @@
#include <strings.h>
#endif
#include <libintl.h>
-#include <math.h>
/* libalpm */
#include "deps.h"
@@ -47,6 +46,38 @@
extern pmhandle_t *handle;
+pmgraph_t *_alpm_graph_new(void)
+{
+ pmgraph_t *graph = NULL;
+
+ graph = (pmgraph_t *)malloc(sizeof(pmgraph_t));
+ if(graph) {
+ graph->state = 0;
+ graph->data = NULL;
+ graph->father = NULL;
+ graph->sons = NULL;
+ graph->sonptr = NULL;
+ }
+ return(graph);
+}
+
+void _alpm_graph_free(pmgraph_t *graph)
+{
+ FREELISTPTR(graph->sons);
+ free(graph);
+}
+
+pmgraph_t *_alpm_graph_finduntouched(alpm_list_t *vertices)
+{
+ alpm_list_t *i;
+ pmgraph_t *found = NULL;
+ for (i = vertices; i && !found; i = i->next) {
+ pmgraph_t *vertex = i->data;
+ if (vertex->state == 0) found = vertex;
+ }
+ return(found);
+}
+
pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdeptype_t type,
pmdepmod_t depmod, const char *depname,
const char *depversion)
@@ -109,11 +140,9 @@
alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, pmtranstype_t mode)
{
alpm_list_t *newtargs = NULL;
- alpm_list_t *i, *j, *k, *l;
- int change = 1;
- int numscans = 0;
- int numtargs = 0;
- int maxscans;
+ alpm_list_t *i, *j, *k;
+ alpm_list_t *vertices = NULL;
+ pmgraph_t *vertex;
ALPM_LOG_FUNC;
@@ -121,65 +150,64 @@
return(NULL);
}
- for(i = targets; i; i = i->next) {
- newtargs = alpm_list_add(newtargs, i->data);
- numtargs++;
- }
-
- maxscans = (int)sqrt(numtargs);
-
_alpm_log(PM_LOG_DEBUG, _("started sorting dependencies"));
- while(change) {
- alpm_list_t *tmptargs = NULL;
- change = 0;
- if(numscans > maxscans) {
- _alpm_log(PM_LOG_DEBUG, _("possible dependency cycle detected"));
- continue;
- }
- numscans++;
- /* run thru targets, moving up packages as necessary */
- for(i = newtargs; i; i = i->next) {
- pmpkg_t *p = i->data;
- _alpm_log(PM_LOG_DEBUG, " sorting %s", alpm_pkg_get_name(p));
- for(j = alpm_pkg_get_depends(p); j; j = j->next) {
- pmdepend_t *depend = alpm_splitdep(j->data);
- pmpkg_t *q = NULL;
- if(depend == NULL) {
- continue;
- }
- /* look for depend->name -- if it's farther down in the list, then
- * move it up above p
- */
- for(k = i->next; k; k = k->next) {
- q = k->data;
- const char *qname = alpm_pkg_get_name(q);
- if(!strcmp(depend->name, qname)) {
- if(!_alpm_pkg_find(qname, tmptargs)) {
- change = 1;
- tmptargs = alpm_list_add(tmptargs, q);
- }
- break;
- }
- for(l = alpm_pkg_get_provides(q); l; l = l->next) {
- const char *provname = l->data;
- if(!strcmp(depend->name, provname)) {
- if(!_alpm_pkg_find(provname, tmptargs)) {
- change = 1;
- tmptargs = alpm_list_add(tmptargs, q);
- }
- break;
- }
- }
- }
+
+ /* We create the vertices */
+ for(i = targets; i; i = i->next) {
+ pmgraph_t *vertex = _alpm_graph_new();
+ vertex->data = (void *)i->data;
+ vertices = alpm_list_add(vertices, vertex);
+ }
+
+ /* We compute the edges */
+ for(i = vertices; i; i = i->next) {
+ pmgraph_t *vertex_i = i->data;
+ pmpkg_t *p_i = vertex_i->data;
+ //TODO: this should be somehow combined with _alpm_checkdeps
+ for(j = vertices; j; j = j->next) {
+ pmgraph_t *vertex_j = j->data;
+ pmpkg_t *p_j = vertex_j->data;
+ int son=0;
+ for(k = alpm_pkg_get_depends(p_i); k && !son; k = k->next) {
+ pmdepend_t *depend = alpm_splitdep(k->data);
+ son = alpm_depcmp(p_j, depend);
free(depend);
}
- if(!_alpm_pkg_find(alpm_pkg_get_name(p), tmptargs)) {
- tmptargs = alpm_list_add(tmptargs, p);
+ if(son) vertex_i->sons=alpm_list_add(vertex_i->sons, vertex_j);
+ }
+ vertex_i->sonptr=vertex_i->sons;
+ }
+
+ vertex = vertices->data;
+ while(vertex) {
+ vertex->state = -1; // we touched this vertex
+ int found = 0;
+ while(vertex->sonptr && !found) {
+ pmgraph_t *nextson = (vertex->sonptr)->data;
+ vertex->sonptr = (vertex->sonptr)->next;
+ if (nextson->state == 0) {
+ found = 1;
+ nextson->father = vertex;
+ vertex = nextson;
}
+ else if(nextson->state == -1) {
+ _alpm_log(PM_LOG_WARNING, _("dependency cycle detected\n"));
+ /* We add remaining targets */
+ for(i = targets; i; i = i->next)
+ if(!_alpm_pkg_find(alpm_pkg_get_name(i->data), newtargs))
+ newtargs = alpm_list_add(newtargs, i->data);
+ goto cleanup;
+ }
+ }
+ if(!found) {
+ newtargs = alpm_list_add(newtargs, vertex->data);
+ vertex->state = 1; //we leave this vertex
+ vertex = vertex->father;
+ if(!vertex) vertex=_alpm_graph_finduntouched(vertices);
}
- FREELISTPTR(newtargs);
- newtargs = tmptargs;
}
+cleanup:
+
_alpm_log(PM_LOG_DEBUG, _("sorting dependencies finished"));
if(mode == PM_TRANS_TYPE_REMOVE) {
@@ -190,6 +218,8 @@
newtargs = tmptargs;
}
+ _FREELIST(vertices, _alpm_graph_free);
+
return(newtargs);
}
@@ -234,12 +264,12 @@
for(j = alpm_pkg_get_requiredby(oldpkg); j; j = j->next) {
pmpkg_t *p;
found = 0;
- if((p = _alpm_db_get_pkgfromcache(db, j->data)) == NULL) {
- /* hmmm... package isn't installed.. */
+ if(_alpm_pkg_find(j->data, packages)) {
+ /* this package also in the upgrade list, so don't worry about it */
continue;
}
- if(_alpm_pkg_find(alpm_pkg_get_name(p), packages)) {
- /* this package also in the upgrade list, so don't worry about it */
+ if((p = _alpm_db_get_pkgfromcache(db, j->data)) == NULL) {
+ /* hmmm... package isn't installed.. */
continue;
}
for(k = alpm_pkg_get_depends(p); k; k = k->next) {
@@ -271,12 +301,8 @@
for(l = _alpm_db_get_pkgcache(db); l; l = l->next) {
pmpkg_t *pkg = l->data;
- if(strcmp(alpm_pkg_get_name(pkg), alpm_pkg_get_name(oldpkg)) == 0) {
- /* well, we know this one succeeds, but we're removing it... skip it */
- continue;
- }
-
- if(alpm_depcmp(pkg, depend)) {
+ if(alpm_depcmp(pkg, depend) && !_alpm_pkg_find(alpm_pkg_get_name(pkg), packages)) {
+ /* we ignore packages that will be updated because we know that updated ones don't satisfy depend.*/
_alpm_log(PM_LOG_DEBUG, _("checkdeps: dependency '%s' satisfied by installed package '%s'"),
depend->name, alpm_pkg_get_name(pkg));
satisfied = 1;
@@ -319,36 +345,12 @@
}
found = 0;
- /* check database for literal packages */
+ /* check database for satisfying packages */
for(k = _alpm_db_get_pkgcache(db); k && !found; k = k->next) {
pmpkg_t *p = (pmpkg_t *)k->data;
found = alpm_depcmp(p, depend);
}
- /* check database for provides matches */
- if(!found) {
- alpm_list_t *m;
- for(m = _alpm_db_whatprovides(db, depend->name); m && !found; m = m->next) {
- /* look for a match that isn't one of the packages we're trying
- * to install. this way, if we match against a to-be-installed
- * package, we'll defer to the NEW one, not the one already
- * installed. */
- pmpkg_t *p = m->data;
- alpm_list_t *n;
- int skip = 0;
- for(n = packages; n && !skip; n = n->next) {
- pmpkg_t *ptp = n->data;
- if(strcmp(alpm_pkg_get_name(ptp), alpm_pkg_get_name(p)) == 0) {
- skip = 1;
- }
- }
- if(skip) {
- continue;
- }
- found = alpm_depcmp(p, depend);
- }
- FREELISTPTR(k);
- }
/* check other targets */
for(k = packages; k && !found; k = k->next) {
pmpkg_t *p = k->data;
@@ -370,52 +372,55 @@
}
}
} else if(op == PM_TRANS_TYPE_REMOVE) {
- /* check requiredby fields */
for(i = packages; i; i = i->next) {
- pmpkg_t *tp = i->data;
- if(tp == NULL) {
+ pmpkg_t *rempkg = i->data;
+
+ if(rempkg == NULL) {
+ _alpm_log(PM_LOG_DEBUG, _("null package found in package list"));
continue;
}
- found=0;
- for(j = alpm_pkg_get_requiredby(tp); j; j = j->next) {
- /* Search for 'reqname' in packages for removal */
- char *reqname = j->data;
- alpm_list_t *x = NULL;
- for(x = packages; x; x = x->next) {
- pmpkg_t *xp = x->data;
- if(strcmp(reqname, alpm_pkg_get_name(xp)) == 0) {
- found = 1;
- break;
- }
+ for(j = alpm_pkg_get_requiredby(rempkg); j; j = j->next) {
+ pmpkg_t *p;
+ found = 0;
+ if(_alpm_pkg_find(j->data, packages)) {
+ /* this package also in the remove list, so don't worry about it */
+ continue;
}
- if(!found) {
- /* check if a package in trans->packages provides this package */
- for(k = trans->packages; !found && k; k=k->next) {
- pmpkg_t *spkg = NULL;
- if(trans->type == PM_TRANS_TYPE_SYNC) {
- pmsyncpkg_t *sync = k->data;
- spkg = sync->pkg;
- } else {
- spkg = k->data;
- }
- if(spkg) {
- if(alpm_list_find_str(alpm_pkg_get_provides(spkg), tp->name)) {
- found = 1;
+ if((p = _alpm_db_get_pkgfromcache(db, j->data)) == NULL) {
+ /* hmmm... package isn't installed.. */
+ continue;
+ }
+ for(k = alpm_pkg_get_depends(p); k; k = k->next) {
+ pmdepend_t *depend = alpm_splitdep(k->data);
+ if(depend == NULL) {
+ continue;
+ }
+ /* if rempkg satisfied this dep, we try to find an other satisfyer (which won't be removed)*/
+ if(alpm_depcmp(rempkg, depend)) {
+ int satisfied = 0;
+ for(l = _alpm_db_get_pkgcache(db); l; l = l->next) {
+ pmpkg_t *pkg = l->data;
+ if(alpm_depcmp(pkg, depend) && !_alpm_pkg_find(alpm_pkg_get_name(pkg), packages)) {
+ _alpm_log(PM_LOG_DEBUG, _("checkdeps: dependency '%s' satisfied by installed package '%s'"),
+ depend->name, alpm_pkg_get_name(pkg));
+ satisfied = 1;
+ break;
}
}
- }
- if(!found) {
- _alpm_log(PM_LOG_DEBUG, _("checkdeps: found %s as required by %s"),
- reqname, alpm_pkg_get_name(tp));
- miss = _alpm_depmiss_new(alpm_pkg_get_name(tp), PM_DEP_TYPE_DEPEND,
- PM_DEP_MOD_ANY, j->data, NULL);
- if(!_alpm_depmiss_isin(miss, baddeps)) {
- baddeps = alpm_list_add(baddeps, miss);
- } else {
- FREE(miss);
+ if(!satisfied) {
+ _alpm_log(PM_LOG_DEBUG, _("checkdeps: found %s as required by %s"),
+ alpm_pkg_get_name(rempkg), alpm_pkg_get_name(p));
+ miss = _alpm_depmiss_new(p->name, PM_DEP_TYPE_DEPEND, depend->mod,
+ depend->name, depend->version);
+ if(!_alpm_depmiss_isin(miss, baddeps)) {
+ baddeps = alpm_list_add(baddeps, miss);
+ } else {
+ FREE(miss);
+ }
}
}
+ free(depend);
}
}
}
diff -Naur pacman-lib/lib/libalpm/deps.h pacman-lib.new/lib/libalpm/deps.h
--- pacman-lib/lib/libalpm/deps.h 2007-04-22 14:54:33.000000000 +0200
+++ pacman-lib.new/lib/libalpm/deps.h 2007-04-22 16:59:20.000000000 +0200
@@ -42,6 +42,19 @@
pmdepend_t depend;
};
+/* Graphs */
+struct __pmgraph_t {
+ int state; //0: untouched, -1: entered, other: leaving time
+ void *data;
+ struct __pmgraph_t *father; //where did we come from?
+ alpm_list_t *sons;
+ alpm_list_t *sonptr; // points to a son in the sons list
+};
+
+pmgraph_t *_alpm_graph_new(void);
+void _alpm_graph_free(pmgraph_t *graph);
+pmgraph_t *_alpm_graph_finduntouched(alpm_list_t *vertices);
+
pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdeptype_t type,
pmdepmod_t depmod, const char *depname,
const char *depversion);
@@ -53,7 +66,6 @@
int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *syncpkg,
alpm_list_t *list, alpm_list_t *trail, pmtrans_t *trans,
alpm_list_t **data);
-
#endif /* _ALPM_DEPS_H */
/* vim: set ts=2 sw=2 noet: */
diff -Naur pacman-lib/lib/libalpm/Makefile.am pacman-lib.new/lib/libalpm/Makefile.am
--- pacman-lib/lib/libalpm/Makefile.am 2007-04-22 14:54:33.000000000 +0200
+++ pacman-lib.new/lib/libalpm/Makefile.am 2007-04-22 18:06:04.000000000 +0200
@@ -39,7 +39,7 @@
versioncmp.h versioncmp.c
libalpm_la_LDFLAGS = -no-undefined -version-info $(LIB_VERSION_INFO)
-libalpm_la_LIBADD = -larchive -ldownload -lm
+libalpm_la_LIBADD = -larchive -ldownload
if HAS_DOXYGEN
all: doxygen.in
diff -Naur pacman-lib/src/pacman/Makefile.am pacman-lib.new/src/pacman/Makefile.am
--- pacman-lib/src/pacman/Makefile.am 2007-04-22 14:54:33.000000000 +0200
+++ pacman-lib.new/src/pacman/Makefile.am 2007-04-22 18:11:40.000000000 +0200
@@ -28,7 +28,7 @@
util.h util.c
pacman_LDADD = $(top_builddir)/lib/libalpm/.libs/libalpm.la \
- -ldownload
+ -ldownload -lm
pacman_static_SOURCES = $(pacman_SOURCES)
pacman_static_LDFLAGS = $(LDFLAGS) -all-static
-----------------------
bye, ngaba
More information about the pacman-dev
mailing list