[pacman-dev] [patch] patch IV rewritten for git
Nagy Gabor
ngaba at petra.hos.u-szeged.hu
Sun Jun 10 17:08:23 EDT 2007
Hi!
Some comments:
1. This is a simple topological sort algorithm, based on
the "depth first search" algorithm, for more info plz visit:
http://en.wikipedia.org/wiki/Topological_sorting
(An alternative algorithm for...)
Usually this is done by a recursive way but I not prefer that,
because this version is more expressive to me (however this looks
more difficult, because we need some extra variables to precisely
store the current state).
2. As I noted in the patch (TODO), the most CPU-cost part of the
algorithm is to build the graph, so this should somehow combined with
depcheck (because that function does this too...)
So, here is the patch:
----------------------
diff --git a/lib/libalpm/Makefile.am b/lib/libalpm/Makefile.am
index 29a2f02..afbfed0 100644
--- a/lib/libalpm/Makefile.am
+++ b/lib/libalpm/Makefile.am
@@ -43,7 +43,7 @@ libalpm_la_SOURCES = \
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 --git a/lib/libalpm/alpm.h b/lib/libalpm/alpm.h
index d4c584f..e6c905f 100644
--- a/lib/libalpm/alpm.h
+++ b/lib/libalpm/alpm.h
@@ -50,6 +50,7 @@ typedef struct __pmsyncpkg_t pmsyncpkg_t;
typedef struct __pmdepend_t pmdepend_t;
typedef struct __pmdepmissing_t pmdepmissing_t;
typedef struct __pmconflict_t pmconflict_t;
+typedef struct __pmgraph_t pmgraph_t;
/*
* Library
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
index b6f8cc8..ceee5c1 100644
--- a/lib/libalpm/deps.c
+++ b/lib/libalpm/deps.c
@@ -29,7 +29,6 @@
#ifdef __sun__
#include <strings.h>
#endif
-#include <math.h>
/* libalpm */
#include "deps.h"
@@ -46,6 +45,27 @@
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)
+{
+ alpm_list_free(graph->sons);
+ free(graph);
+}
+
pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdeptype_t type,
pmdepmod_t depmod, const char *depname,
const char *depversion)
@@ -108,11 +128,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 +139,64 @@ 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 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(son) vertex_i->sons=alpm_list_add(vertex_i->sons, vertex_j);
+ }
+ vertex_i->sonptr=vertex_i->sons;
+ }
- _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) {
+ 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"));
+ }
}
- 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(qname, tmptargs)) {
- change = 1;
- tmptargs = alpm_list_add(tmptargs, q);
- }
- break;
- }
- }
+ if(!found) {
+ newtargs = alpm_list_add(newtargs, vertex->data);
+ vertex->state = 1; //we leave this vertex
+ vertex = vertex->father;
+ if(!vertex) {
+ while(vptr = vptr->next) {
+ vertex = vptr->data;
+ if (vertex->state == 0) 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 +207,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);
}
diff --git a/lib/libalpm/deps.h b/lib/libalpm/deps.h
index 8f3a9b9..56028a4 100644
--- a/lib/libalpm/deps.h
+++ b/lib/libalpm/deps.h
@@ -42,6 +42,18 @@ struct __pmdepmissing_t {
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);
+
pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdeptype_t type,
pmdepmod_t depmod, const char *depname,
const char *depversion);
diff --git a/src/pacman/Makefile.am b/src/pacman/Makefile.am
index 6a7f4e4..1ab5916 100644
--- a/src/pacman/Makefile.am
+++ b/src/pacman/Makefile.am
@@ -26,11 +26,11 @@ pacman_SOURCES = \
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
pacman_static_LDADD = $(top_builddir)/lib/libalpm/.libs/libalpm.la \
- -ldownload
+ -ldownload -lm
# vim:set ts=2 sw=2 noet:
More information about the pacman-dev
mailing list