[Frugalware-git] pacman-g2: _pacman_sortbydeps(): use topological sort

Miklos Vajna vmiklos at frugalware.org
Mon Nov 12 01:35:51 CET 2007


Git-Url: http://git.frugalware.org/gitweb/gitweb.cgi?p=pacman-g2.git;a=commitdiff;h=0700a6a31bfb119778cc71ffad5d123b1f37be95

commit 0700a6a31bfb119778cc71ffad5d123b1f37be95
Author: Miklos Vajna <vmiklos at frugalware.org>
Date:   Mon Nov 12 01:25:24 2007 +0100

_pacman_sortbydeps(): use topological sort
- this is a port of commit 544bcbe6641bb94a429a9c149893bc0b07fd2619 of pacman.git
- original author: Nagy Gabor <ngaba at petra.hos.u-szeged.hu>
- note that his commit uses less memory than the original one

diff --git a/lib/libpacman/deps.c b/lib/libpacman/deps.c
index 443c9ae..46c94d3 100644
--- a/lib/libpacman/deps.c
+++ b/lib/libpacman/deps.c
@@ -45,6 +45,22 @@

extern pmhandle_t *handle;

+static pmgraph_t *_pacman_graph_new(void)
+{
+	pmgraph_t *graph = NULL;
+
+	graph = (pmgraph_t *)malloc(sizeof(pmgraph_t));
+	memset(graph, 0, sizeof(pmgraph_t));
+	return(graph);
+}
+
+static void _pacman_graph_free(void *data)
+{
+	pmgraph_t *graph = data;
+	FREELISTPTR(graph->children);
+	FREE(graph);
+}
+
pmdepmissing_t *_pacman_depmiss_new(const char *target, unsigned char type, unsigned char depmod,
const char *depname, const char *depversion)
{
@@ -102,69 +118,76 @@ int _pacman_depmiss_isin(pmdepmissing_t *needle, pmlist_t *haystack)
pmlist_t *_pacman_sortbydeps(pmlist_t *targets, int mode)
{
pmlist_t *newtargs = NULL;
-	pmlist_t *i, *j, *k, *l;
-	int change = 1;
-	int numscans = 0;
-	int numtargs = 0;
+	pmlist_t *i, *j, *k;
+	pmlist_t *vertices = NULL;
+	pmlist_t *vptr;
+	pmgraph_t *vertex;

if(targets == NULL) {
return(NULL);
}

+	_pacman_log(PM_LOG_DEBUG, _("started sorting dependencies"));
+
+	/* We create the vertices */
for(i = targets; i; i = i->next) {
-		newtargs = _pacman_list_add(newtargs, i->data);
-		numtargs++;
+		pmgraph_t *vertex = _pacman_graph_new();
+		vertex->data = (void *)i->data;
+		vertices = _pacman_list_add(vertices, vertex);
}

-	_pacman_log(PM_LOG_DEBUG, _("started sorting dependencies"));
-	while(change) {
-		pmlist_t *tmptargs = NULL;
-		change = 0;
-		if(numscans > sqrt(numtargs)) {
-			_pacman_log(PM_LOG_DEBUG, _("possible dependency cycle detected"));
-			continue;
+	/* 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 _pacman_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 = _pacman_pkg_getinfo(p_i, PM_PKG_DEPENDS); k && !child; k = k->next) {
+				pmdepend_t depend;
+				_pacman_splitdep(k->data, &depend);
+				child = _pacman_depcmp(p_j, &depend);
+			}
+			if(child) {
+				vertex_i->children = _pacman_list_add(vertex_i->children, vertex_j);
+			}
}
-		numscans++;
-		/* run thru targets, moving up packages as necessary */
-		for(i = newtargs; i; i = i->next) {
-			pmpkg_t *p = (pmpkg_t*)i->data;
-			for(j = _pacman_pkg_getinfo(p, PM_PKG_DEPENDS); j; j = j->next) {
-				pmdepend_t dep;
-				pmpkg_t *q = NULL;
-				if(_pacman_splitdep(j->data, &dep)) {
-					continue;
-				}
-				/* look for dep.name -- if it's farther down in the list, then
-				 * move it up above p
-				 */
-				for(k = i->next; k; k = k->next) {
-					q = (pmpkg_t *)k->data;
-					if(!strcmp(dep.name, q->name)) {
-						if(!_pacman_pkg_isin(q->name, tmptargs)) {
-							change = 1;
-							tmptargs = _pacman_list_add(tmptargs, q);
-						}
-						break;
-					}
-					if(!change) {
-						for(l = _pacman_pkg_getinfo(q, PM_PKG_PROVIDES); l; l = l->next) {
-							if(!strcmp(dep.name, (char*)l->data)) {
-								if(!_pacman_pkg_isin((char*)l->data, tmptargs)) {
-									change = 1;
-									tmptargs = _pacman_list_add(tmptargs, q);
-								}
-								break;
-							}
-						}
-					}
-				}
+		vertex_i->childptr = vertex_i->children;
+	}
+
+	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) {
+				_pacman_log(PM_LOG_DEBUG, _("dependency cycle detected"));
}
-			if(!_pacman_pkg_isin(p->name, tmptargs)) {
-				tmptargs = _pacman_list_add(tmptargs, p);
+		}
+		if(!found) {
+			newtargs = _pacman_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;
+				}
}
}
-		FREELISTPTR(newtargs);
-		newtargs = tmptargs;
}
_pacman_log(PM_LOG_DEBUG, _("sorting dependencies finished"));

@@ -176,6 +199,8 @@ pmlist_t *_pacman_sortbydeps(pmlist_t *targets, int mode)
newtargs = tmptargs;
}

+	_FREELIST(vertices, _pacman_graph_free);
+
return(newtargs);
}

diff --git a/lib/libpacman/deps.h b/lib/libpacman/deps.h
index 7b483dd..9af72bc 100644
--- a/lib/libpacman/deps.h
+++ b/lib/libpacman/deps.h
@@ -38,6 +38,14 @@ typedef struct __pmdepmissing_t {
pmdepend_t depend;
} pmdepmissing_t;

+typedef struct __pmgraph_t {
+	int state; /* 0: untouched, -1: entered, other: leaving time */
+	void *data;
+	struct __pmgraph_t *parent; /* where did we come from? */
+	pmlist_t *children;
+	pmlist_t *childptr; /* points to a child in children list */
+} pmgraph_t;
+
pmdepmissing_t *_pacman_depmiss_new(const char *target, unsigned char type, unsigned char depmod,
const char *depname, const char *depversion);
int _pacman_depmiss_isin(pmdepmissing_t *needle, pmlist_t *haystack);


More information about the Frugalware-git mailing list