From 544bcbe6641bb94a429a9c149893bc0b07fd2619 Mon Sep 17 00:00:00 2001 From: Nagy Gabor Date: Sun, 10 Jun 2007 23:51:20 +0200 Subject: Implement simple topological sort algorithm for sortbydeps Based on the "depth first search" algorithm, for more infos visit: http://en.wikipedia.org/wiki/Topological_sorting The previous algorithm used by sortbydeps was too slow, and to work around it the number of steps needed to get correct result was reduced greatly. So it produced wrong results in several cases : 1) smoke001.py 2) http://bugs.archlinux.org/task/7229 More here: http://archlinux.org/pipermail/pacman-dev/2007-April/008057.html Signed-off-by: Chantry Xavier Signed-off-by: Dan McGee --- lib/libalpm/deps.c | 138 +++++++++++++++++++++++++++++++---------------------- 1 file changed, 82 insertions(+), 56 deletions(-) (limited to 'lib/libalpm/deps.c') diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 52fdd9ac..66b2d77c 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -29,7 +29,6 @@ #ifdef __sun__ #include #endif -#include /* libalpm */ #include "deps.h" @@ -46,6 +45,28 @@ extern pmhandle_t *handle; +static 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->parent = NULL; + graph->children = NULL; + graph->childptr = NULL; + } + return(graph); +} + +static void _alpm_graph_free(void *data) +{ + pmgraph_t *graph = data; + alpm_list_free(graph->children); + free(graph); +} + pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdeptype_t type, pmdepmod_t depmod, const char *depname, const char *depversion) @@ -108,11 +129,10 @@ int _alpm_depmiss_isin(pmdepmissing_t *needle, alpm_list_t *haystack) 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; + alpm_list_t *vptr; + pmgraph_t *vertex; ALPM_LOG_FUNC; @@ -120,65 +140,69 @@ alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, pmtranstype_t mode) return(NULL); } + _alpm_log(PM_LOG_DEBUG, _("started sorting dependencies")); + + /* We create the vertices */ for(i = targets; i; i = i->next) { - newtargs = alpm_list_add(newtargs, i->data); - numtargs++; + pmgraph_t *vertex = _alpm_graph_new(); + vertex->data = (void *)i->data; + vertices = alpm_list_add(vertices, vertex); } - maxscans = (int)sqrt(numtargs); + /* 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 child = 0; + for(k = alpm_pkg_get_depends(p_i); k && !child; k = k->next) { + pmdepend_t *depend = alpm_splitdep(k->data); + child = alpm_depcmp(p_j, depend); + free(depend); + } + if(child) vertex_i->children = + alpm_list_add(vertex_i->children, vertex_j); + } + vertex_i->childptr = vertex_i->children; + } - _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; + vptr = vertices; + vertex = vertices->data; + while(vptr) { + /* mark that we touched the vertex */ + vertex->state = -1; + int found = 0; + while(vertex->childptr && !found) { + pmgraph_t *nextchild = (vertex->childptr)->data; + vertex->childptr = (vertex->childptr)->next; + if (nextchild->state == 0) { + found = 1; + nextchild->parent = vertex; + vertex = nextchild; + } + else if(nextchild->state == -1) { + _alpm_log(PM_LOG_WARNING, _("dependency cycle detected\n")); + } } - 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; + if(!found) { + newtargs = alpm_list_add(newtargs, vertex->data); + /* mark that we've left this vertex */ + vertex->state = 1; + vertex = vertex->parent; + if(!vertex) { + vptr = vptr->next; + while(vptr) { + vertex = vptr->data; + if (vertex->state == 0) break; + vptr = vptr->next; } - /* 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(qname, tmptargs)) { - change = 1; - tmptargs = alpm_list_add(tmptargs, q); - } - break; - } - } - } - free(depend); - } - if(!_alpm_pkg_find(alpm_pkg_get_name(p), tmptargs)) { - tmptargs = alpm_list_add(tmptargs, p); } } - alpm_list_free(newtargs); - newtargs = tmptargs; } + _alpm_log(PM_LOG_DEBUG, _("sorting dependencies finished")); if(mode == PM_TRANS_TYPE_REMOVE) { @@ -189,6 +213,8 @@ alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, pmtranstype_t mode) newtargs = tmptargs; } + alpm_list_free_inner(vertices, _alpm_graph_free); + return(newtargs); } -- cgit v1.2.3