summaryrefslogtreecommitdiff
path: root/lib/libalpm/delta.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libalpm/delta.c')
-rw-r--r--lib/libalpm/delta.c266
1 files changed, 266 insertions, 0 deletions
diff --git a/lib/libalpm/delta.c b/lib/libalpm/delta.c
new file mode 100644
index 00000000..8daac0c5
--- /dev/null
+++ b/lib/libalpm/delta.c
@@ -0,0 +1,266 @@
+/*
+ * 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 "error.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
+ * @{
+ */
+
+const char SYMEXPORT *alpm_delta_get_from(pmdelta_t *delta)
+{
+ ALPM_LOG_FUNC;
+
+ /* Sanity checks */
+ ASSERT(delta != NULL, return(NULL));
+
+ return(delta->from);
+}
+
+const 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);
+}
+
+const char SYMEXPORT *alpm_delta_get_filename(pmdelta_t *delta)
+{
+ ALPM_LOG_FUNC;
+
+ /* Sanity checks */
+ ASSERT(delta != NULL, return(NULL));
+
+ return(delta->filename);
+}
+
+const 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_ptr(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;
+
+ CALLOC(delta, 1, sizeof(pmdelta_t), RET_ERR(PM_ERR_MEMORY, NULL));
+
+ 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: */