summaryrefslogtreecommitdiff
path: root/lib/libalpm/deps.h
diff options
context:
space:
mode:
authorNagy Gabor <ngaba@petra.hos.u-szeged.hu>2007-06-10 23:51:20 +0200
committerDan McGee <dan@archlinux.org>2007-06-10 22:13:58 -0400
commit544bcbe6641bb94a429a9c149893bc0b07fd2619 (patch)
tree7e88da506f5c1269a8014688c08b4bec63505eb9 /lib/libalpm/deps.h
parent8588b4823b579bc41909734f5a13a420d64487d6 (diff)
downloadpacman-544bcbe6641bb94a429a9c149893bc0b07fd2619.tar.xz
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 <shiningxc@gmail.com> Signed-off-by: Dan McGee <dan@archlinux.org>
Diffstat (limited to 'lib/libalpm/deps.h')
-rw-r--r--lib/libalpm/deps.h9
1 files changed, 9 insertions, 0 deletions
diff --git a/lib/libalpm/deps.h b/lib/libalpm/deps.h
index 8f3a9b91..132f21f4 100644
--- a/lib/libalpm/deps.h
+++ b/lib/libalpm/deps.h
@@ -42,6 +42,15 @@ struct __pmdepmissing_t {
pmdepend_t depend;
};
+/* Graphs */
+struct __pmgraph_t {
+ int state; /* 0: untouched, -1: entered, other: leaving time */
+ void *data;
+ struct __pmgraph_t *parent; /* where did we come from? */
+ alpm_list_t *children;
+ alpm_list_t *childptr; /* points to a child in children list */
+};
+
pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdeptype_t type,
pmdepmod_t depmod, const char *depname,
const char *depversion);