11 files changed, 380 insertions, 1 deletions

diff --git a/lib/libalpm/Makefile.am b/lib/libalpm/Makefile.am
index 69482396..49ce14c6 100644
--- a/lib/libalpm/Makefile.am
+++ b/lib/libalpm/Makefile.am
@@ -18,6 +18,7 @@ libalpm_la_SOURCES = \
 	cache.h cache.c \
 	conflict.h conflict.c \
 	db.h db.c \
+	delta.h delta.c \
 	deps.h deps.c \
 	error.h error.c \
 	group.h group.c \
diff --git a/lib/libalpm/alpm.h b/lib/libalpm/alpm.h
index 6eda2106..5f37d825 100644
--- a/lib/libalpm/alpm.h
+++ b/lib/libalpm/alpm.h
@@ -45,6 +45,7 @@ extern "C" {
 
 typedef struct __pmdb_t pmdb_t;
 typedef struct __pmpkg_t pmpkg_t;
+typedef struct __pmdelta_t pmdelta_t;
 typedef struct __pmgrp_t pmgrp_t;
 typedef struct __pmserver_t pmserver_t;
 typedef struct __pmtrans_t pmtrans_t;
@@ -207,12 +208,23 @@ alpm_list_t *alpm_pkg_get_optdepends(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_requiredby(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_conflicts(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_provides(pmpkg_t *pkg);
+alpm_list_t *alpm_pkg_get_deltas(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_replaces(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_files(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_backup(pmpkg_t *pkg);
 unsigned short alpm_pkg_has_scriptlet(pmpkg_t *pkg);
 
 /*
+ * Deltas
+ */
+
+char *alpm_delta_get_from(pmdelta_t *delta);
+char *alpm_delta_get_to(pmdelta_t *delta);
+unsigned long alpm_delta_get_size(pmdelta_t *delta);
+char *alpm_delta_get_filename(pmdelta_t *delta);
+char *alpm_delta_get_md5sum(pmdelta_t *delta);
+
+/*
  * Groups
  */
 const char *alpm_grp_get_name(const pmgrp_t *grp);
diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c
index 5671b4a2..2301411a 100644
--- a/lib/libalpm/alpm_list.c
+++ b/lib/libalpm/alpm_list.c
@@ -379,6 +379,24 @@ alpm_list_t SYMEXPORT *alpm_list_strdup(const alpm_list_t *list)
 }
 
 /**
+ * @brief Copy a list, without copying data.
+ *
+ * @param list the list to copy
+ *
+ * @return a copy of the original list
+ */
+alpm_list_t SYMEXPORT *alpm_list_copy(const alpm_list_t *list)
+{
+	const alpm_list_t *lp = list;
+	alpm_list_t *newlist = NULL;
+	while(lp) {
+		newlist = alpm_list_add(newlist, lp->data);
+		lp = lp->next;
+	}
+	return(newlist);
+}
+
+/**
  * @brief Create a new list in reverse order.
  *
  * @param list the list to copy
diff --git a/lib/libalpm/alpm_list.h b/lib/libalpm/alpm_list.h
index a2a06f4c..8fce2804 100644
--- a/lib/libalpm/alpm_list.h
+++ b/lib/libalpm/alpm_list.h
@@ -60,6 +60,7 @@ alpm_list_t *alpm_list_remove(alpm_list_t *haystack, const void *needle, alpm_li
 alpm_list_t *alpm_list_remove_node(alpm_list_t *node);
 alpm_list_t *alpm_list_remove_dupes(const alpm_list_t *list);
 alpm_list_t *alpm_list_strdup(const alpm_list_t *list);
+alpm_list_t *alpm_list_copy(const alpm_list_t *list);
 alpm_list_t *alpm_list_reverse(alpm_list_t *list);
 
 /* item accessors */
diff --git a/lib/libalpm/be_files.c b/lib/libalpm/be_files.c
index 2bfdb956..59155cfe 100644
--- a/lib/libalpm/be_files.c
+++ b/lib/libalpm/be_files.c
@@ -44,6 +44,7 @@
 #include "error.h"
 #include "handle.h"
 #include "package.h"
+#include "delta.h"
 
 
 /* This function is used to convert the downloaded db file to the proper backend
@@ -484,6 +485,24 @@ int _alpm_db_read(pmdb_t *db, pmpkg_t *info, pmdbinfrq_t inforeq)
 		fp = NULL;
 	}
 
+	/* DELTAS */
+	if(inforeq & INFRQ_DELTAS) {
+		snprintf(path, PATH_MAX, "%s/%s-%s/deltas", db->path, info->name, info->version);
+		if((fp = fopen(path, "r"))) {
+			while(!feof(fp)) {
+				fgets(line, 255, fp);
+				_alpm_strtrim(line);
+				if(!strcmp(line, "%DELTAS%")) {
+					while(fgets(line, 512, fp) && strlen(_alpm_strtrim(line))) {
+						info->deltas = alpm_list_add(info->deltas, _alpm_delta_parse(line));
+					}
+				}
+			}
+			fclose(fp);
+			fp = NULL;
+		}
+	}
+
 	/* INSTALL */
 	if(inforeq & INFRQ_SCRIPTLET) {
 		snprintf(path, PATH_MAX, "%s/%s-%s/install", db->path, info->name, info->version);
diff --git a/lib/libalpm/db.h b/lib/libalpm/db.h
index 3ee49770..16e12986 100644
--- a/lib/libalpm/db.h
+++ b/lib/libalpm/db.h
@@ -33,8 +33,9 @@ typedef enum _pmdbinfrq_t {
 	INFRQ_DEPENDS = 0x04,
 	INFRQ_FILES = 0x08,
 	INFRQ_SCRIPTLET = 0x10,
+	INFRQ_DELTAS = 0x20,
 	/* ALL should be sum of all above */
-	INFRQ_ALL = 0x1F
+	INFRQ_ALL = 0x3F
 } pmdbinfrq_t;
 
 /* Database */
diff --git a/lib/libalpm/delta.c b/lib/libalpm/delta.c
new file mode 100644
index 00000000..00ed46cb
--- /dev/null
+++ b/lib/libalpm/delta.c
@@ -0,0 +1,265 @@
+/*
+ *  delta.c
+ *
+ *  Copyright (c) 2007 by Judd Vinet <jvinet@zeroflux.org>
+ * 
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 
+ *  USA.
+ */
+
+#include "config.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+/* libalpm */
+#include "delta.h"
+#include "util.h"
+#include "log.h"
+#include "alpm_list.h"
+#include "alpm.h"
+
+/** \addtogroup alpm_deltas Delta Functions
+ * @brief Functions to manipulate libalpm deltas
+ * @{
+ */
+
+char SYMEXPORT *alpm_delta_get_from(pmdelta_t *delta)
+{
+	ALPM_LOG_FUNC;
+
+	/* Sanity checks */
+	ASSERT(delta != NULL, return(NULL));
+
+	return(delta->from);
+}
+
+char SYMEXPORT *alpm_delta_get_to(pmdelta_t *delta)
+{
+	ALPM_LOG_FUNC;
+
+	/* Sanity checks */
+	ASSERT(delta != NULL, return(NULL));
+
+	return(delta->to);
+}
+
+unsigned long SYMEXPORT alpm_delta_get_size(pmdelta_t *delta)
+{
+	ALPM_LOG_FUNC;
+
+	/* Sanity checks */
+	ASSERT(delta != NULL, return(-1));
+
+	return(delta->size);
+}
+
+char SYMEXPORT *alpm_delta_get_filename(pmdelta_t *delta)
+{
+	ALPM_LOG_FUNC;
+
+	/* Sanity checks */
+	ASSERT(delta != NULL, return(NULL));
+
+	return(delta->filename);
+}
+
+char SYMEXPORT *alpm_delta_get_md5sum(pmdelta_t *delta)
+{
+	ALPM_LOG_FUNC;
+
+	/* Sanity checks */
+	ASSERT(delta != NULL, return(NULL));
+
+	return(delta->md5sum);
+}
+
+/** @} */
+
+/** 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)
+{
+	unsigned long sum = 0;
+	alpm_list_t *dlts = deltas;
+
+	while(dlts) {
+		pmdelta_t *d = (pmdelta_t *)alpm_list_getdata(dlts);
+		sum += d->size;
+
+		dlts = alpm_list_next(dlts);
+	}
+
+	return(sum);
+}
+
+/** 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 = (pmdelta_t *)alpm_list_getdata(dlts);
+		char *fname = _alpm_filecache_find(d->filename);
+
+		if(!fname) {
+			sum += d->size;
+		}
+
+		FREE(fname);
+
+		dlts = alpm_list_next(dlts);
+	}
+
+	return(sum);
+}
+
+/** 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;
+
+	/* 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);
+
+		/* If this vertex has already been visited in the path, go to the
+		 * next vertex. */
+		if(alpm_list_find(path, v))
+			continue;
+
+		/* 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);
+			alpm_list_free(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);
+				}
+			}
+		}
+	}
+
+	return(shortest);
+}
+
+/** 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.
+ */
+alpm_list_t *_alpm_shortest_delta_path(alpm_list_t *deltas, const char *from,
+		const char *to)
+{
+	alpm_list_t *path = NULL;
+
+	path = shortest_delta_path(deltas, from, to, path);
+
+	return(path);
+}
+
+/** Parses the string representation of a pmdelta_t object.
+ *
+ * This function assumes that the string is in the correct format.
+ *
+ * @param line the string to parse
+ *
+ * @return A pointer to the new pmdelta_t object
+ */
+pmdelta_t *_alpm_delta_parse(char *line)
+{
+	pmdelta_t *delta;
+	char *tmp = line, *tmp2;
+
+	delta = malloc(sizeof(pmdelta_t));
+
+	tmp2 = tmp;
+	tmp = strchr(tmp, ' ');
+	*(tmp++) = '\0';
+	strncpy(delta->from, tmp2, DLT_VERSION_LEN);
+
+	tmp2 = tmp;
+	tmp = strchr(tmp, ' ');
+	*(tmp++) = '\0';
+	strncpy(delta->to, tmp2, DLT_VERSION_LEN);
+
+	tmp2 = tmp;
+	tmp = strchr(tmp, ' ');
+	*(tmp++) = '\0';
+	delta->size = atol(tmp2);
+
+	tmp2 = tmp;
+	tmp = strchr(tmp, ' ');
+	*(tmp++) = '\0';
+	strncpy(delta->filename, tmp2, DLT_FILENAME_LEN);
+
+	strncpy(delta->md5sum, tmp, DLT_MD5SUM_LEN);
+
+	return(delta);
+}
+
+/* vim: set ts=2 sw=2 noet: */
diff --git a/lib/libalpm/delta.h b/lib/libalpm/delta.h
new file mode 100644
index 00000000..67dbeb47
--- /dev/null
+++ b/lib/libalpm/delta.h
@@ -0,0 +1,45 @@
+/*
+ *  delta.h
+ * 
+ *  Copyright (c) 2007 by Judd Vinet <jvinet@zeroflux.org>
+ * 
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 
+ *  USA.
+ */
+#ifndef _ALPM_DELTA_H
+#define _ALPM_DELTA_H
+
+#include "alpm.h"
+
+#define DLT_FILENAME_LEN 512
+#define DLT_VERSION_LEN  64
+#define DLT_MD5SUM_LEN   33
+
+struct __pmdelta_t {
+	char from[DLT_VERSION_LEN];
+	char to[DLT_VERSION_LEN];
+	unsigned long size;
+	char filename[DLT_FILENAME_LEN];
+	char md5sum[DLT_MD5SUM_LEN];
+};
+
+unsigned long _alpm_delta_path_size(alpm_list_t *deltas);
+unsigned long _alpm_delta_path_size_uncached(alpm_list_t *deltas);
+pmdelta_t *_alpm_delta_parse(char *line);
+alpm_list_t *_alpm_shortest_delta_path(alpm_list_t *deltas, const char *from, const char *to);
+
+#endif /* _ALPM_DELTA_H */
+
+/* vim: set ts=2 sw=2 noet: */
diff --git a/lib/libalpm/package.c b/lib/libalpm/package.c
index 9e45b1d5..4f6f5a9e 100644
--- a/lib/libalpm/package.c
+++ b/lib/libalpm/package.c
@@ -446,6 +446,20 @@ alpm_list_t SYMEXPORT *alpm_pkg_get_provides(pmpkg_t *pkg)
 	return pkg->provides;
 }
 
+alpm_list_t SYMEXPORT *alpm_pkg_get_deltas(pmpkg_t *pkg)
+{
+	ALPM_LOG_FUNC;
+
+	/* Sanity checks */
+	ASSERT(handle != NULL, return(NULL));
+	ASSERT(pkg != NULL, return(NULL));
+
+	if(pkg->origin == PKG_FROM_CACHE && !(pkg->infolevel & INFRQ_DELTAS)) {
+		_alpm_db_read(pkg->origin_data.db, pkg, INFRQ_DELTAS);
+	}
+	return pkg->deltas;
+}
+
 alpm_list_t SYMEXPORT *alpm_pkg_get_replaces(pmpkg_t *pkg)
 {
 	ALPM_LOG_FUNC;
@@ -722,6 +736,7 @@ void _alpm_pkg_free(pmpkg_t *pkg)
 	FREELIST(pkg->groups);
 	FREELIST(pkg->provides);
 	FREELIST(pkg->replaces);
+	FREELIST(pkg->deltas);
 	if(pkg->origin == PKG_FROM_FILE) {
 		FREE(pkg->origin_data.file);
 	}
diff --git a/lib/libalpm/package.h b/lib/libalpm/package.h
index 42ebe0e0..daaeb360 100644
--- a/lib/libalpm/package.h
+++ b/lib/libalpm/package.h
@@ -75,6 +75,7 @@ struct __pmpkg_t {
 	alpm_list_t *requiredby;
 	alpm_list_t *conflicts;
 	alpm_list_t *provides;
+	alpm_list_t *deltas;
 	/* internal */
 	pmpkgfrom_t origin;
 	/* Replaced 'void *data' with this union as follows:
diff --git a/lib/libalpm/po/POTFILES.in b/lib/libalpm/po/POTFILES.in
index caf68c30..97df339e 100644
--- a/lib/libalpm/po/POTFILES.in
+++ b/lib/libalpm/po/POTFILES.in
@@ -9,6 +9,7 @@ lib/libalpm/cache.c
 lib/libalpm/conflict.c
 lib/libalpm/db.c
 lib/libalpm/deps.c
+lib/libalpm/delta.c
 lib/libalpm/error.c
 lib/libalpm/group.c
 lib/libalpm/handle.c