1 files changed, 137 insertions, 95 deletions

diff --git a/lib/libalpm/delta.c b/lib/libalpm/delta.c
index 12fb9bd7..fdb4d99b 100644
--- a/lib/libalpm/delta.c
+++ b/lib/libalpm/delta.c
@@ -21,13 +21,14 @@
 
 #include <stdlib.h>
 #include <string.h>
+#include <limits.h>
 
 /* libalpm */
 #include "delta.h"
+#include "alpm_list.h"
 #include "util.h"
 #include "log.h"
-#include "alpm_list.h"
-#include "alpm.h"
+#include "graph.h"
 
 /** \addtogroup alpm_deltas Delta Functions
  * @brief Functions to manipulate libalpm deltas
@@ -78,129 +79,170 @@ unsigned long SYMEXPORT alpm_delta_get_size(pmdelta_t *delta)
 
 /** @} */
 
-/** Calculates the combined size of a list of delta files.
- * @param deltas the list of pmdelta_t * objects
- * @return the combined size
- */
-unsigned long _alpm_delta_path_size(alpm_list_t *deltas)
+static alpm_list_t *delta_graph_init(alpm_list_t *deltas)
 {
-	unsigned long sum = 0;
-	alpm_list_t *dlts = deltas;
-
-	while(dlts) {
-		pmdelta_t *d = alpm_list_getdata(dlts);
-		sum += d->delta_size;
+	alpm_list_t *i, *j;
+	alpm_list_t *vertices = NULL;
+	/* create the vertices */
+	for(i = deltas; i; i = i->next) {
+		char *fpath, *md5sum;
+		pmgraph_t *v = _alpm_graph_new();
+		pmdelta_t *vdelta = i->data;
+		vdelta->download_size = vdelta->delta_size;
+		v->weight = ULONG_MAX;
+
+		/* determine whether the delta file already exists */
+		fpath = _alpm_filecache_find(vdelta->delta);
+		md5sum = alpm_get_md5sum(fpath);
+		if(fpath && md5sum && strcmp(md5sum, vdelta->delta_md5) == 0) {
+			vdelta->download_size = 0;
+		}
+		FREE(fpath);
+		FREE(md5sum);
+
+		/* determine whether a base 'from' file exists */
+		fpath = _alpm_filecache_find(vdelta->from);
+		md5sum = alpm_get_md5sum(fpath);
+		if(fpath && md5sum && strcmp(md5sum, vdelta->from_md5) == 0) {
+			v->weight = vdelta->download_size;
+		}
+		FREE(fpath);
+		FREE(md5sum);
 
-		dlts = alpm_list_next(dlts);
+		v->data = vdelta;
+		vertices = alpm_list_add(vertices, v);
 	}
 
-	return(sum);
+	/* compute the edges */
+	for(i = vertices; i; i = i->next) {
+		pmgraph_t *v_i = i->data;
+		pmdelta_t *d_i = v_i->data;
+		/* loop a second time so we make all possible comparisons */
+		for(j = vertices; j; j = j->next) {
+			pmgraph_t *v_j = j->data;
+			pmdelta_t *d_j = v_j->data;
+			/* We want to create a delta tree like the following:
+			 *          1_to_2
+			 *            |
+			 * 1_to_3   2_to_3
+			 *   \        /
+			 *     3_to_4
+			 * If J 'from' is equal to I 'to', then J is a child of I.
+			 * */
+			if(strcmp(d_j->from, d_i->to) == 0
+					&& strcmp(d_j->from_md5, d_i->to_md5) == 0) {
+				v_i->children = alpm_list_add(v_i->children, v_j);
+			}
+		}
+		v_i->childptr = v_i->children;
+	}
+	return(vertices);
 }
 
-/** Calculates the combined size of a list of delta files that are not
- * in the cache.
- * @param deltas the list of pmdelta_t * objects
- * @return the combined size
- */
-unsigned long _alpm_delta_path_size_uncached(alpm_list_t *deltas)
-{
-	unsigned long sum = 0;
-	alpm_list_t *dlts = deltas;
-
-	while(dlts) {
-		pmdelta_t *d = alpm_list_getdata(dlts);
-		char *fname = _alpm_filecache_find(d->delta);
+static unsigned long delta_vert(alpm_list_t *vertices,
+		const char *to, const char *to_md5, alpm_list_t **path) {
+	alpm_list_t *i;
+	pmgraph_t *v;
+	while(1) {
+		v = NULL;
+		/* find the smallest vertice not visited yet */
+		for(i = vertices; i; i = i->next) {
+			pmgraph_t *v_i = i->data;
+
+			if(v_i->state == -1) {
+				continue;
+			}
 
-		if(!fname) {
-			sum += d->delta_size;
+			if(v == NULL || v_i->weight < v->weight) {
+				v = v_i;
+			}
+		}
+		if(v == NULL || v->weight == ULONG_MAX) {
+			break;
 		}
 
-		FREE(fname);
-
-		dlts = alpm_list_next(dlts);
-	}
+		v->state = -1;
 
-	return(sum);
-}
+		v->childptr = v->children;
+		while(v->childptr) {
+			pmgraph_t *v_c = v->childptr->data;
+			pmdelta_t *d_c = v_c->data;
+			if(v_c->weight > v->weight + d_c->download_size) {
+				v_c->weight = v->weight + d_c->download_size;
+				v_c->parent = v;
+			}
 
-/** Calculates the shortest path from one version to another.
- * The shortest path is defined as the path with the smallest combined
- * size, not the length of the path.
- * The algorithm is based on Dijkstra's shortest path algorithm.
- * @param deltas the list of pmdelta_t * objects that a package has
- * @param from the version to start from
- * @param to the version to end at
- * @param path the current path
- * @return the list of pmdelta_t * objects that has the smallest size.
- * NULL (the empty list) is returned if there is no path between the
- * versions.
- */
-static alpm_list_t *shortest_delta_path(alpm_list_t *deltas,
-		const char *from, const char *to, alpm_list_t *path)
-{
-	alpm_list_t *d;
-	alpm_list_t *shortest = NULL;
+			v->childptr = (v->childptr)->next;
 
-	/* Found the 'to' version, this is a good path so return it. */
-	if(strcmp(from, to) == 0) {
-		return(path);
+		}
 	}
 
-	for(d = deltas; d; d = alpm_list_next(d)) {
-		pmdelta_t *v = alpm_list_getdata(d);
+	v = NULL;
+	unsigned long bestsize = 0;
 
-		/* If this vertex has already been visited in the path, go to the
-		 * next vertex. */
-		if(alpm_list_find_ptr(path, v)) {
-			continue;
-		}
+	for(i = vertices; i; i = i->next) {
+		pmgraph_t *v_i = i->data;
+		pmdelta_t *d_i = v_i->data;
 
-		/* Once we find a vertex that starts at the 'from' version,
-		 * recursively find the shortest path using the 'to' version of this
-		 * current vertex as the 'from' version in the function call. */
-		if(strcmp(v->from, from) == 0) {
-			alpm_list_t *newpath = alpm_list_copy(path);
-			newpath = alpm_list_add(newpath, v);
-			newpath = shortest_delta_path(deltas, v->to, to, newpath);
-
-			if(newpath != NULL) {
-				/* The path returned works, now use it unless there is already a
-				 * shorter path found. */
-				if(shortest == NULL) {
-					shortest = newpath;
-				} else if(_alpm_delta_path_size(shortest) > _alpm_delta_path_size(newpath)) {
-					alpm_list_free(shortest);
-					shortest = newpath;
-				} else {
-					alpm_list_free(newpath);
-				}
+		if(strcmp(d_i->to, to) == 0
+				|| strcmp(d_i->to_md5, to_md5) == 0) {
+			if(v == NULL || v_i->weight < v->weight) {
+				v = v_i;
+				bestsize = v->weight;
 			}
 		}
 	}
 
-	alpm_list_free(path);
+	alpm_list_t *rpath = NULL;
+	while(v != NULL) {
+		pmdelta_t *vdelta = v->data;
+		rpath = alpm_list_add(rpath, vdelta);
+		v = v->parent;
+	}
+	*path = alpm_list_reverse(rpath);
+	alpm_list_free(rpath);
 
-	return(shortest);
+	return(bestsize);
 }
 
 /** Calculates the shortest path from one version to another.
  * The shortest path is defined as the path with the smallest combined
  * size, not the length of the path.
- * @param deltas the list of pmdelta_t * objects that a package has
- * @param from the version to start from
- * @param to the version to end at
- * @return the list of pmdelta_t * objects that has the smallest size.
- * NULL (the empty list) is returned if there is no path between the
- * versions.
+ * @param deltas the list of pmdelta_t * objects that a file has
+ * @param to the file to start the search at
+ * @param to_md5 the md5sum of the above named file
+ * @param path the pointer to a list location where pmdelta_t * objects that
+ * have the smallest size are placed. NULL is set if there is no path
+ * possible with the files available.
+ * @return the size of the path stored, or ULONG_MAX if path is unfindable
  */
-alpm_list_t *_alpm_shortest_delta_path(alpm_list_t *deltas, const char *from,
-		const char *to)
+unsigned long _alpm_shortest_delta_path(alpm_list_t *deltas,
+		const char *to, const char *to_md5, alpm_list_t **path)
 {
-	alpm_list_t *path = NULL;
+	alpm_list_t *bestpath = NULL;
+	alpm_list_t *vertices;
+	unsigned long bestsize = ULONG_MAX;
+
+	ALPM_LOG_FUNC;
+
+	if(deltas == NULL) {
+		*path = NULL;
+		return(bestsize);
+	}
+
+	_alpm_log(PM_LOG_DEBUG, "started delta shortest-path search\n");
+
+	vertices = delta_graph_init(deltas);
+
+	bestsize = delta_vert(vertices, to, to_md5, &bestpath);
+
+	_alpm_log(PM_LOG_DEBUG, "delta shortest-path search complete\n");
 
-	path = shortest_delta_path(deltas, from, to, path);
+	alpm_list_free_inner(vertices, _alpm_graph_free);
+	alpm_list_free(vertices);
 
-	return(path);
+	*path = bestpath;
+	return(bestsize);
 }
 
 /** Parses the string representation of a pmdelta_t object.